AdaGrad stepsizes: sharp convergence over nonconvex landscapes

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. }