mlsanityData to 7 Oct 2026

On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Norm

arXiv 2402.00389 ↗First posted 1 Feb 2024math.OC cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Although adaptive gradient methods have been extensively used in deep learning, their convergence rates proved in the literature are all slower than that of SGD, particularly with respect to their dependence on the dimension. This paper considers the classical RMSProp and its momentum extension and establishes the convergence rate of frac1Tsumk=1T Eleft[|nabla f(xk)|1right]≤ O(frac√dCT1/4) measured by ℓ1 norm without the bounded gradient assumption, where d is the dimension of the optimization variable, T is the iteration number, and C is a constant identical to that appeared in the optimal convergence rate of SGD. Our convergence rate matches the lower bound with respect to all the coefficients except the dimension d. Since |x|2ll|x|1≤√d|x|2 for problems with extremely large d, our convergence rate can be considered to be analogous to the frac1Tsumk=1T Eleft[|nabla f(xk)|2right]≤ O(fracCT1/4) rate of SGD in the ideal case of |nabla f(x)|1=varTheta(√d|nabla f(x)|2).

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 39 references that are in the map. First posted on arXiv 1 Feb 2024.

Builds on

28 of 39 references.

References · 28

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2019On the Convergence of Adam and Beyondcited by 834
  3. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  4. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  6. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 282
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 181
  9. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 173
  10. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 172
  11. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  12. 2017Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradientscited by 136
16 more
  1. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
  2. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 117
  3. 2022Adam Can Converge Without Any Modification On Update Rulescited by 112
  4. 2023Convergence of Adam Under Relaxed Assumptionscited by 97
  5. 2018Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networkscited by 89
  6. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  7. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  8. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  9. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  10. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  11. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  12. 2023Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexitycited by 38
  13. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  14. 2021Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Accelerationcited by 25
  15. 2019Domain-independent Dominance of Adaptive Methodscited by 12
  16. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8

Built on by

Not cited yet.