Timezone: »

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

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #56
in Posters Tue »
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 the norm version of AdaGrad (AdaGrad-Norm) converges to a stationary point at the $\mathcal{O}(\log(N)/\sqrt{N})$ rate in the stochastic setting, and at the optimal $\mathcal{O}(1/N)$ rate in the batch (non-stochastic) setting -- in this sense, our convergence guarantees are ``sharp''. In particular, both our theoretical results and extensive numerical experiments imply that AdaGrad-Norm is robust to the \emph{unknown Lipschitz constant and level of stochastic noise on the gradient}.
Keywords: Optimization

Author Information

Rachel Ward (University of Texas)
Xiaoxia 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