# Stochastic Gradient Descent with Momentum is Algorithmically Stable

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 57 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 30 of 34)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [A Unified Analysis of Stochastic Momentum Methods for Deep Learning](https://mlsanity.com/paper/1808.10396/) (2018)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Three-Way Trade-Off in Multi-Objective Learning: Optimization, Generalization and Conflict-Avoidance](https://mlsanity.com/paper/2305.20057/) (2023)
- [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel](https://mlsanity.com/paper/2107.12723/) (2021)
- [Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2002.10583/) (2020)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [On the Generalization of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/1809.04564/) (2018)

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

- [Geometric Moment Contraction for Stochastic Nesterov Acceleration](https://mlsanity.com/paper/2609.31303/) (2026)

## 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.