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

arXiv: https://arxiv.org/abs/2402.00389 · HTML: https://mlsanity.com/paper/2402.00389/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients](https://mlsanity.com/paper/1705.07774/) (2017)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity](https://mlsanity.com/paper/2310.17998/) (2023)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration](https://mlsanity.com/paper/2101.05471/) (2021)
- [Domain-independent Dominance of Adaptive Methods](https://mlsanity.com/paper/1912.01823/) (2019)
- [High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise](https://mlsanity.com/paper/2311.02000/) (2023)

## 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).