# Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2019.

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

- [AdaSAM: Boosting Sharpness-Aware Minimization with Adaptive Learning Rate and Momentum for Training Deep Neural Networks](https://mlsanity.com/paper/2303.00565/) (2023)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks](https://mlsanity.com/paper/2403.05293/) (2024)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent](https://mlsanity.com/paper/2310.18455/) (2023)
- [Transient growth of accelerated optimization algorithms](https://mlsanity.com/paper/2103.08017/) (2021)
- [Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms](https://mlsanity.com/paper/2209.11920/) (2022)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [On the Generalization of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2102.13653/) (2021)
- [Does Momentum Help? A Sample Complexity Analysis](https://mlsanity.com/paper/2110.15547/) (2021)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)
- [A Nonlinear Time-Series Theory for Constant-step SGD with Momentum](https://mlsanity.com/paper/2610.16034/) (2026)

## Abstract (arXiv)

Momentum methods such as Polyak's heavy ball (HB) method, Nesterov's accelerated gradient (AG) as well as accelerated projected gradient (APG) method have been commonly used in machine learning practice, but their performance is quite sensitive to noise in the gradients. We study these methods under a first-order stochastic oracle model where noisy estimates of the gradients are available. For strongly convex problems, we show that the distribution of the iterates of AG converges with the accelerated O(√kappalog(1/varepsilon)) linear rate to a ball of radius varepsilon centered at a unique invariant distribution in the 1-Wasserstein metric where kappa is the condition number as long as the noise variance is smaller than an explicit upper bound we can provide. Our analysis also certifies linear convergence rates as a function of the stepsize, momentum parameter and the noise variance; recovering the accelerated rates in the noiseless case and quantifying the level of noise that can be tolerated to achieve a given performance. In the special case of strongly convex quadratic objectives, we can show accelerated linear rates in the p-Wasserstein metric for any p≥ 1 with improved sensitivity to noise for both AG and HB through a non-asymptotic analysis under some additional assumptions on the noise structure. Our analysis for HB and AG also leads to improved non-asymptotic convergence bounds in suboptimality for both deterministic and stochastic settings which is of independent interest. To the best of our knowledge, these are the first linear convergence results for stochastic momentum methods under the stochastic oracle model. We also extend our results to the APG method and weakly convex functions showing accelerated rates when the noise magnitude is sufficiently small.