[talks] 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

[Nicki Gotsis]

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. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20180710/93770d59/attachment.html>