A Simple Convergence Proof of Adam and Adagrad

2020/03/05 by Alexandre Défossez, Léon Bottou, Défossez, Alexandre +5 · 11 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2003.02395

openalex publication_date 2020/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(dln(N)/√(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 β₁ among all previous convergence bounds for non-convex Adam and Adagrad, improving from O((1-β₁)^-3) to O((1-β₁)^-1).

Citations

• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

Cited by

• Alada: Alternating Adaptation of Momentum Method for Memory-Efficient Matrix Optimization
• ADAM Optimization with Adaptive Batch Selection
• Gradient Descent with Provably Tuned Learning-rate Schedules
• Adam Simplified: Bias Correction Debunked
• DP-AdamW: Investigating Decoupled Weight Decay and Bias Correction in Private Deep Learning
• Why Federated Optimization Fails to Achieve Perfect Fitting? A Theoretical Perspective on Client-Side Optima
• Implicit Bias of Per-sample Adam on Separable Data: Departure from the Full-batch Regime
• A Simple First-Order Algorithm for Full-Rank Equality Constrained Optimization
• Cautious Weight Decay
• A regret minimization approach to fixed-point iterations
• AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates

Related

• On the Convergence of AdaGrad(Norm) on \R^d: Beyond Convexity, Non-Asymptotic Rate and Acceleration
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond
• Revisiting Convergence of AdaGrad with Relaxed Assumptions