# Does Momentum Help? A Sample Complexity Analysis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 29 Oct 2021.

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

- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [On the insufficiency of existing momentum schemes for Stochastic Optimization](https://mlsanity.com/paper/1803.05591/) (2018)
- [On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings](https://mlsanity.com/paper/2002.12414/) (2020)
- [On the Influence of Momentum Acceleration on Online Learning](https://mlsanity.com/paper/1603.04136/) (2016)
- [Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances](https://mlsanity.com/paper/1901.07445/) (2019)

## Abstract (arXiv)

Stochastic Heavy Ball (SHB) and Nesterov's Accelerated Stochastic Gradient (ASG) are popular momentum methods in stochastic optimization. While benefits of such acceleration ideas in deterministic settings are well understood, their advantages in stochastic optimization is still unclear. In fact, in some specific instances, it is known that momentum does not help in the sample complexity sense. Our work shows that a similar outcome actually holds for the whole of quadratic optimization. Specifically, we obtain a lower bound on the sample complexity of SHB and ASG for this family and show that the same bound can be achieved by the vanilla SGD. We note that there exist results claiming the superiority of momentum based methods in quadratic optimization, but these are based on one-sided or flawed analyses.