Oral
AdaGrad stepsizes: sharp convergence over nonconvex landscapes
Rachel Ward · Xiaoxia Wu · Leon Bottou

Tue Jun 11th 04:40 -- 05:00 PM @ Hall B

Adaptive gradient methods such as AdaGrad and its variants update the stepsize in stochastic gradient descent on the fly according to the gradients received along the way; such methods have gained widespread use in large-scale optimization for their ability to converge robustly, without the need to fine tune parameters such as the stepsize schedule. Yet, the theoretical guarantees to date for AdaGrad are for online and convex optimization. We bridge this gap by providing strong theoretical guarantees for the convergence of AdaGrad over smooth, nonconvex landscapes. We show that AdaGrad converges to a stationary point at the optimal $O(1/\sqrt{N})$ rate (up to a $\log(N)$ factor), and at the optimal $O(1/N)$ rate in the non-stochastic setting . In particular, both our theoretical and numerical results imply that AdaGrad is robust to the \emph{unknown Lipschitz constant and level of stochastic noise on the gradient, in a near-optimal sense. }

Author Information

Rachel Ward (University of Texas)
Xiaoxia(Shirley) Wu (The University of Texas at Austin)

The department of mathematics

Leon Bottou (Facebook)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors