mlsanityData to 7 Oct 2026

On the fast convergence of minibatch heavy ball momentum

arXiv 2206.07553 ↗First posted 15 Jun 2022cs.LG cs.DS cs.NAcited by 11

Not on the map. Why?

Abstract (arXiv)

Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of acceleration in the literature. In this work, we aim to close the gap between theory and practice by showing that stochastic heavy ball momentum retains the fast linear rate of (deterministic) heavy ball momentum on quadratic optimization problems, at least when minibatching with a sufficiently large batch size. The algorithm we study can be interpreted as an accelerated randomized Kaczmarz algorithm with minibatching and heavy ball momentum. The analysis relies on carefully decomposing the momentum transition matrix, and using new spectral norm concentration bounds for products of independent random matrices. We provide numerical illustrations demonstrating that our bounds are reasonably sharp.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 36 of its 64 references that are in the map. First posted on arXiv 15 Jun 2022.

Builds on

36 of 64 references.

References · 36

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  7. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  8. 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 313
  9. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  10. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  11. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  12. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
24 more
  1. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  2. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  3. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 117
  4. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  5. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  6. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  7. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  8. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 54
  9. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  10. 2018On the insufficiency of existing momentum schemes for Stochastic Optimizationcited by 46
  11. 2019Understanding the Role of Momentum in Stochastic Gradient Methodscited by 42
  12. 2016Stochastic Heavy Ballcited by 40
  13. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  14. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  15. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  16. 2015A geometric alternative to Nesterov's accelerated gradient descentcited by 21
  17. 2016A Simple Practical Accelerated Method for Finite Sumscited by 18
  18. 2019Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distancescited by 15
  19. 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 15
  20. 2017A Robust Accelerated Optimization Algorithm for Strongly Convex Functionscited by 14
  21. 2017Linearly convergent stochastic heavy ball method for minimizing generalization errorcited by 13
  22. 2013An Accelerated Randomized Kaczmarz Algorithmcited by 12
  23. 2018Robust Accelerated Gradient Methods for Smooth Strongly Convex Functionscited by 12
  24. 2018Direct Acceleration of SAGA using Sampled Negative Momentumcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 3; 2025: 2; 2026: 2.

11 papers.

  1. 2023Fast Diffusion Modelcited by 20
  2. 2023When and Why Momentum Accelerates SGD:An Empirical Studycited by 17
  3. 2023Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noisecited by 9
  4. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  5. 2023Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normalitycited by 6
  6. 2025Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillationcited by 5
  7. 2024Randomized Kaczmarz with geometrically smoothed momentumcited by 3
  8. 2026SHANG++: Robust Stochastic Acceleration under Multiplicative Noisecited by 2
  9. 2025Both Asymptotic and Non-Asymptotic Convergence of Quasi-Hyperbolic Momentum using Increasing Batch Sizecited by 1
  10. 2024(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentumcited by 0
  11. 2026Perfect Parallelization in Mini-Batch SGD with Classical Momentum Accelerationcited by 0