mlsanityData to 7 Oct 2026

Stochastic Gradient Descent with Momentum is Algorithmically Stable

arXiv 2605.28517 ↗First posted 27 May 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent with momentum (SGDM) is one of the most widely used optimization algorithms in machine learning. While optimization properties of SGDM have been extensively studied in the literature, it remains insufficiently understood whether and when SGDM can generalize well to unseen data. In particular, it has been conjectured that while momentum accelerates training, it may degrade generalization. In this paper, we close this gap by developing a comprehensive generalization analysis of SGDM through the lens of algorithmic stability. More specifically, we introduce a generalized SGDM framework that encompasses both Polyak's and Nesterov's momentum schemes, and establish tight on-average model stability bounds for smooth and convex problems. Notably, the obtained bounds exploit small optimization error bounds along the trajectory, apply to any momentum parameter in the interval [0, 1), and do not require the commonly assumed Lipschitzness of loss functions. We further derive optimization error bounds for the generalized SGDM, and combine them with our generalization analyses to obtain optimal excess population risk bounds for SGDM with both Polyak's and Nesterov's momentum.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 57 references that are in the map. First posted on arXiv 27 May 2026.

Builds on

34 of 57 references.

References · 34

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  10. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  11. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  12. 2019Sharper bounds for uniformly stable algorithmscited by 91
22 more
  1. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  2. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  3. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  4. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  5. 2018A Unified Analysis of Stochastic Momentum Methods for Deep Learningcited by 54
  6. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  7. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  8. 2019Understanding the Role of Momentum in Stochastic Gradient Methodscited by 42
  9. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  10. 2023Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidancecited by 35
  11. 2016Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimizationcited by 34
  12. 2014iPiano: Inertial Proximal Algorithm for Non-Convex Optimizationcited by 30
  13. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  14. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  15. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  16. 2020Scheduled Restart Momentum for Accelerated Stochastic Gradient Descentcited by 24
  17. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  18. 2018On the Generalization of Stochastic Gradient Descent with Momentumcited by 20
  19. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  20. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  21. 2023Generalized Polyak Step Size for First Order Optimization with Momentumcited by 15
  22. 2013On Learnability, Complexity and Stabilitycited by 4

Built on by

Not cited yet.