mlsanityData to 7 Oct 2026

High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise

arXiv 2311.02000 ↗First posted 3 Nov 2023math.OC cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the convergence of the Adaptive Moment Estimation (Adam) algorithm under unconstrained non-convex smooth stochastic optimizations. Despite the widespread usage in machine learning areas, its theoretical properties remain limited. Prior researches primarily investigated Adam's convergence from an expectation view, often necessitating strong assumptions like uniformly stochastic bounded gradients or problem-dependent knowledge in prior. As a result, the applicability of these findings in practical real-world scenarios has been constrained. To overcome these limitations, we provide a deep analysis and show that Adam could converge to the stationary point in high probability with a rate of Oleft(rm poly(log T)/√Tright) under coordinate-wise "affine" variance noise, not requiring any bounded gradient assumption and any problem-dependent knowledge in prior to tune hyper-parameters. Additionally, it is revealed that Adam confines its gradients' magnitudes within an order of Oleft(rm poly(log T)right). Finally, we also investigate a simplified version of Adam without one of the corrective terms and obtain a convergence rate that is adaptive to the noise level.

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

Builds on

29 of 38 references.

References · 29

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2016An overview of gradient descent optimization algorithmscited by 1,021
  6. 2019On the Convergence of Adam and Beyondcited by 834
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  8. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  9. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  10. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  11. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  12. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
17 more
  1. 2022Adam Can Converge Without Any Modification On Update Rulescited by 112
  2. 2023Convergence of Adam Under Relaxed Assumptionscited by 97
  3. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  4. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  5. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  6. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  7. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  8. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  9. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  10. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  11. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  12. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  13. 2018Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov accelerationcited by 39
  14. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  15. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  16. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  17. 2018A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Accelerationcited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 2; 2026: 1.

8 papers.

  1. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  2. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 14
  3. 2024Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variancecited by 14
  4. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 13
  5. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  6. 2025Simple Convergence Proof of Adam From a Sign-like Descent Perspectivecited by 4
  7. 2026MGUP: A Momentum-Gradient Alignment Update Policy for Stochastic Optimizationcited by 2
  8. 2024On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Normcited by 0