A Simple Convergence Proof of Adam and Adagrad

Abstract

We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension $d$, and the total number of iterations $N$. This bound can be made arbitrarily small, and with the right hyper-parameters, Adam can be shown to converge with the same rate of convergence $O(d\ln (N)/\sqrt{N})$. When used with the default parameters, Adam doesn't converge, however, and just like constant step-size SGD, it moves away from the initialization point faster than Adagrad, which might explain its practical success. Finally, we obtain the tightest dependency on the heavy ball momentum decay rate ${\beta }_1$ among all previous convergence bounds for non-convex Adam and Adagrad, improving from $O((1-{\beta }_1{)}^{-3})$ to $O((1-{\beta }_1{)}^{-1})$.

final TMLR version

References in corpus (5)

• On the Convergence of Adam and Beyond
• Adaptive Bound Optimization for Online Convex Optimization
• Jukebox: A Generative Model for Music
• Comparison of Batch Normalization and Weight Normalization Algorithms for the Large-scale Image Classification
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network

Cited by in corpus (9)

• Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• On the fast convergence of minibatch heavy ball momentum
• Analytic natural gradient updates for Cholesky factor in Gaussian variational approximation
• Local Methods with Adaptivity via Scaling
• Learning dynamical systems from data: Gradient-based dictionary optimization
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• Frequency-aware SGD for Efficient Embedding Learning with Provable Benefits
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization