CISE Seminar: April 1, 2019 – Ashok Cutkosky, Google

BU Photonics Building
8 St. Mary’s Street, PHO 339
1:30pm-2:30pm

Ashok Cutkosky
Google

Preconditioned Online Learning without Preconditioning

In stochastic convex optimization, the rate of convergence is often dominated by the variance in the gradients. In order to combat this, one can make use of the covariance matrix of the gradients. This information allows an optimization algorithm to ignore irrelevant “noise directions”, which can lead to a much lower “effective variance” (in the best case reducing from the trace of the covariance matrix to its smallest eigenvalue). In an apparent effort to promote confusion with Newton’s method for non-stochastic optimization, this is often called “preconditioning”.

Unfortunately (similar to Newton’s method), preconditioning requires computing, storing, and inverting a matrix, which takes time and space at best quadratic in the problem dimension rather than the linear time of gradient descent. This is prohibitive for modern high-dimensional problems, so practitioners typically resort to linear time algorithms such as AdaGrad which approximate the covariance matrix by just its diagonal entries. In this talk, I will describe a technique that attempts to achieve full preconditioning while using only linear time and space. This technique never does worse than gradient descent or diagonal techniques such as AdaGrad, and in certain settings, it actually surpasses the guarantees provided by preconditioning algorithms that use the entire covariance matrix.

Ashok Cutkosky is currently a research scientist at Google. He obtained a Ph.D. in computer science from Stanford in 2018, a Masters in Medicine from Stanford in 2016, and a bachelors in Mathematics from Harvard in 2013. He is interested in optimization theory, and in adaptive learning algorithms in particular. He received the best student paper award at COLT in 2017, and he also enjoys card magic.

Faculty Host: Yannis Paschalidis
Student Hosts: Zhenxun Zhuang and Artin Spiridonoff