mlsanityData to 14 Oct 2026

Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity

arXiv 2310.17998 ↗First posted 27 Oct 2023cs.LG math.OCcited by 38

Not on the map. Why?

Abstract (arXiv)

Recently, Arjevani et al. [1] established a lower bound of iteration complexity for the first-order optimization under an L-smooth condition and a bounded noise variance assumption. However, a thorough review of existing literature on Adam's convergence reveals a noticeable gap: none of them meet the above lower bound. In this paper, we close the gap by deriving a new convergence guarantee of Adam, with only an L-smooth condition and a bounded noise variance assumption. Our results remain valid across a broad spectrum of hyperparameters. Especially with properly chosen hyperparameters, we derive an upper bound of the iteration complexity of Adam and show that it meets the lower bound for first-order optimizers. To the best of our knowledge, this is the first to establish such a tight upper bound for Adam's convergence. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate and to convert the first-order term in the Descent Lemma to the gradient norm, which may be of independent interest.

Key facts. Cited by 38 papers in the map (data through 14 Oct 2026). Builds on 29 of its 36 references that are in the map. First posted on arXiv 27 Oct 2023.

Builds on

29 of 36 references.

References · 29

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  6. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  7. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  8. 2016Pointer Sentinel Mixture Modelscited by 3,096
  9. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,626
  10. 2019On the Convergence of Adam and Beyondcited by 841
  11. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  12. 2023Symbolic Discovery of Optimization Algorithmscited by 434
17 more
  1. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  2. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 183
  3. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 174
  4. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 174
  5. 2020A Simple Convergence Proof of Adam and Adagradcited by 171
  6. 2020Momentum Improves Normalized SGDcited by 139
  7. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 126
  8. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 119
  9. 2022Adam Can Converge Without Any Modification On Update Rulescited by 114
  10. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  11. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  12. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  13. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  14. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  15. 2018Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov accelerationcited by 39
  16. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  17. 2018AdaShift: Decorrelation and Convergence of Adaptive Learning Rate Methodscited by 24

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 15; 2025: 5; 2026: 18.

38 papers.

Sort:

By area:

  1. 2024Why Transformers Need Adam: A Hessian Perspectivecited by 124
  2. 2025On the Convergence of Muon and Beyondcited by 31
  3. 2024BAdam: A Memory Efficient Full Parameter Optimization Method for Large Language Modelscited by 27
  4. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 26
  5. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
  6. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  7. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  8. 2024ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Ratecited by 18
  9. 2026MuonEq: Balancing Before Orthogonalization with Lightweight Equilibrationcited by 17
  10. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
  11. 2024Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variancecited by 14
  12. 2025Refining Adaptive Zeroth-Order Optimization at Easecited by 12
26 more
  1. 2024Understanding Adam Requires Better Rotation Dependent Assumptionscited by 11
  2. 2024Convergence Rate Analysis of LIONcited by 11
  3. 2025TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedbackcited by 11
  4. 2024A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGDcited by 9
  5. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  6. 2024Adaptive Batch Size Schedules for Distributed Training of Language Models with Data and Model Parallelismcited by 4
  7. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 4
  8. 2026Instruction-as-State: Environment-Guided and State-Conditioned Semantic Understanding for Embodied Navigationcited by 4
  9. 2025LightSAM: Parameter-Agnostic Sharpness-Aware Minimizationcited by 3
  10. 2026OLion: Approaching the Hadamard Ideal by Intersecting Spectral and ℓ∞ Implicit Biasescited by 3
  11. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  12. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 3
  13. 2024CAdam: Confidence-Based Optimization for Online Learningcited by 2
  14. 2026Structured Progressive Knowledge Activation for LLM-Driven Neural Architecture Searchcited by 2
  15. 2026MGUP: A Momentum-Gradient Alignment Update Policy for Stochastic Optimizationcited by 2
  16. 2026HomeAdam: Adam and AdamW Algorithms Sometimes Go Home to Obtain Better Provable Generalizationcited by 1
  17. 2026Dynamic Momentum Recalibration in Online Gradient Learningcited by 1
  18. 2026The Essence of Balance for Self-Improving Agents in Vision-and-Language Navigationcited by 1
  19. 2026Muse: Representation Geometry of Muon Beyond Normalized Momentumcited by 1
  20. 2026Second-Moment Memory in Coordinatewise Adamcited by 1
  21. 2024On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Normcited by 0
  22. 2026PowerStep: Memory-Efficient Adaptive Optimization via ℓp-Norm Steepest Descentcited by 0
  23. 2026Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approachcited by 0
  24. 2026Adam Converges in Nonsmooth Nonconvex Optimizationcited by 0
  25. 2026Convergence rates for the RMSprop optimizer with full control of the hyperparameterscited by 0
  26. 2026Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradientscited by 0