[talks] Naman Agarwal will present his general exam on Monday, May 9th, 2016 at 3pm in CS 302.
ngotsis at CS.Princeton.EDU
Mon May 2 14:20:17 EDT 2016
Naman Agarwal will present his general exam on Monday, May 9th, 2016 at 3pm in CS 302.
The members of his committee are Elad Hazan (adviser), Sanjeev Arora, and Barbara Engelhardt.
Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below.
Stochastic optimization and, in particular, first-order stochastic methods are a cornerstone of modern machine learning due to their extremely efficient per-iteration computational cost. Second-order methods, while able to provide faster per-iteration convergence, have been much less explored due to the high cost of computing the second-order information. In this talk I will present a second-order stochastic method for optimization problems arising in machine learning based on novel matrix randomization techniques that match the per-iteration cost of gradient descent, yet enjoy the linear-convergence properties of second-order optimization. We further show that the algorithm can be coupled generically with known first order algorithms and matrix sampling techniques to match the best known theoretical guarantees as well as improve these guarantees for a broad class of parameters. The algorithm also adapts well in the case when inputs are sparse . I will also demonstrate the efficacy of the algorithm empirically on several standard convex benchmarks.
This is joint work with Brian Bullins and Elad Hazan
Books/Lecture Notes -
Introduction to Online Convex Optimization : E. Hazan
Numerical Optimization: Jorge Nocedal and Stephen J. Wright
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems : S. Bubeck and N. Cesa-Bianchi
Research Papers -
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization: J. Duchi, E. Hazan and Y. Singer
Accelerating Stochastic Gradient Descent using Predictive Variance Reduction : R. Johnson and T. Zhang
Convergence rates of sub-sampled Newton methods : M. Erdogdu and A. Montanari
Escaping from Saddle Points — Online Stochastic Gradient Descent for Tensor Decomposition : R. Ge, F. Huang, C. Jin, Y. Yuan
Cubic regularization of Newton method and its global performance : Y. Nesterov and B.T. Polyak
On the saddle point problem for non-convex optimization, R. Pascanu, Y.N. Dauphin, S. Ganguli and Y. Bengio
Fast and Simple PCA via Convex Optimization : D. Garber and E. Hazan
On Graduated Optimization for Stochastic Non-Convex Problems : E. Hazan, K. Levi and S. Shalev-Shwartz
Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization : J. Abernety, E. Hazan and A. Rakhlin
The price of Bandit Optimization : V. Dani, S. M. Kakade and T. P. Hayes
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback : S. Bubeck, N. Cesa-Bianchi and S. M. Kakade
Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier : J. Abernathy and E. Hazan
Clustering with Bregman Divergences : A. Banerjee, S. Merugu, I. S. Dhillon and J. Ghosh
More information about the talks