Naman Agarwal will present his FPO "Second-Order Optimization Methods for Machine Learning" on Wednesday, 7/18/2018 at 2:00 PM in CS 402
The members of his committee are as follows: Readers: Yoram Singer and Yuxin Chen; Nonreaders: Elad Hazan (Adviser), Sanjeev Arora and Mark Braverman
All are welcome to attend. Please see below for abstract.
In recent years first-order stochastic methods have emerged as the state-of-the-art in largescale
machine learning optimization. This is primarily due to their efficient per-iteration
complexity. Second-order methods, while able to provide faster convergence, are less
popular due to the high cost of computing the second-order information. The main problem
considered in this thesis is can efficient second-order methods for optimization problems
arising in machine learning be developed that improve upon the best known first-order
methods.
We consider the ERM model of learning and propose linear time second-order algorithms
for both convex as well as non-convex settings which improve upon the state-of-the-art
first-order algorithms. In the non-convex setting second-order methods are also shown to
converge to better quality solutions efficiently. For the convex case the proposed algorithms
make use of a novel estimator for the inverse of a matrix and better sampling techniques
for stochastic methods derived out of the notion of leverage scores. For the non-convex
setting we propose an efficient implementation of the cubic regularization scheme proposed
by Nesterov and Polyak.
Furthermore we develop second-order methods for achieving approximate local minima
on Riemannian manifolds which match the convergence rate of their Euclidean counterparts.
Finally we show the limitations of second/higher-order methods by deriving oracle
complexity lower bounds for such methods on sufficiently smooth convex functions.