# Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 7 Feb 2023.

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

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations](https://mlsanity.com/paper/1811.01558/) (2018)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis](https://mlsanity.com/paper/2106.02588/) (2021)
- [Asymptotic study of stochastic adaptive algorithm in non-convex landscape](https://mlsanity.com/paper/2012.05640/) (2020)
- [Linearly convergent stochastic heavy ball method for minimizing generalization error](https://mlsanity.com/paper/1710.10737/) (2017)
- [On minimal representations of shallow ReLU networks](https://mlsanity.com/paper/2108.05643/) (2021)
- [Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz condition](https://mlsanity.com/paper/2107.10123/) (2021)
- [Non-monotone Behavior of the Heavy Ball Method](https://mlsanity.com/paper/1811.00658/) (2018)
- [Conservative SPDEs as fluctuating mean field limits of stochastic gradient descent](https://mlsanity.com/paper/2207.05705/) (2022)
- [Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence](https://mlsanity.com/paper/2210.06819/) (2022)
- [Gradient-Type Methods for Optimization Problems with Polyak-Lojasiewicz Condition: Early Stopping and Adaptivity to Inexactness Parameter](https://mlsanity.com/paper/2212.04226/) (2022)
- [Finite-time stability for differential inclusions with applications to neural networks](https://mlsanity.com/paper/1804.08440/) (2018)

## Built on by (most cited first, 8 of 8)

- [mSAM: Micro-Batch-Averaged Sharpness-Aware Minimization](https://mlsanity.com/paper/2302.09693/) (2023)
- [ODE approximation for the Adam algorithm: General and overparametrized setting](https://mlsanity.com/paper/2511.04622/) (2025)
- [Stochastic Modified Flows, Mean-Field Limits and Dynamics of Stochastic Gradient Descent](https://mlsanity.com/paper/2302.07125/) (2023)
- [Effective continuous equations for adaptive SGD: a stochastic analysis view](https://mlsanity.com/paper/2509.21614/) (2025)
- [Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks](https://mlsanity.com/paper/2607.04233/) (2026)
- [Convergence rates of stochastic gradient method with independent sequences of step-size and momentum weight](https://mlsanity.com/paper/2408.02678/) (2024)
- [GradES: Significantly Faster Training in Transformers with Gradient-Based Early Stopping](https://mlsanity.com/paper/2509.01842/) (2025)
- [Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach](https://mlsanity.com/paper/2605.14663/) (2026)

## Abstract (arXiv)

We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-time counterpart in the context of non-convex optimization. In the small step-size regime and in the case of flat minima or large noise intensities, these bounds prove faster convergence of MSGD compared to plain stochastic gradient descent (SGD). The results are shown for objective functions satisfying a local Polyak-Lojasiewicz inequality and under assumptions on the variance of MSGD that are satisfied in overparametrized settings. Moreover, we analyze the optimal choice of the friction parameter and show that the MSGD process almost surely converges to a local minimum.