Stochastic Gradient Descent with Momentum is Algorithmically Stable

• URL: http://arxiv.org/abs/2605.28517v1
• Date: Wed, 27 May 2026 14:17:38 GMT
• Title: Stochastic Gradient Descent with Momentum is Algorithmically Stable
• Abstract summary: gradient descent with momentum (SGDM) is one of the most widely used optimization algorithms in machine learning.<n>We develop a comprehensive generalization analysis of SGDM through the lens of algorithmic stability.
• Score: 20.643275323974425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  Bilevel optimization (SBO) has been integrated into many machine learning paradigms recently.<n>In this paper, we provide a systematic analysis of bilevel optimization methods.<n>Results do not require re-reading and are applicable to more general objective functions.
  arXiv  Detail & Related papers  (2026-04-05T12:12:58Z)
• Generalization and Optimization of SGD with Lookahead [20.363815126393884]
  Lookahead enhances deep learning models by employing a dual-weight update mechanism.<n>Most theoretical studies focus on its convergence on training data, leaving its generalization capabilities less understood.
  arXiv  Detail & Related papers  (2025-09-19T09:02:09Z)
• Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise [20.922456964393213]
  We establish generalization bounds for SGD with momentum (SGDm) under heavy-tailed noise.<n>For quadratic loss functions, we show that SGDm admits a worse generalization bound in the presence of momentum and heavy tails.<n>We develop a uniform-in-time discretization error bound, which to our knowledge, is the first result of its kind for SDEs with degenerate noise.
  arXiv  Detail & Related papers  (2025-02-02T19:25:48Z)
• Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality [7.793751573538388]
  gradient descent with momentum (SGDM) has been widely used in many machine learning and statistical applications. We analyze the finite-sample convergence rate of SGDM under the strongly convex settings. We show that, with a large batch size, the mini-batch SGDM converges faster than the mini-batch SGD to a neighborhood of the optimal value.
  arXiv  Detail & Related papers  (2023-05-28T08:49:24Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  We propose a novel, robust and accelerated iteration that relies on two key elements. The convergence and stability of the obtained method, referred to as NAG-GS, are first studied extensively. We show that NAG-arity is competitive with state-the-art methods such as momentum SGD with weight decay and AdamW for the training of machine learning models.
  arXiv  Detail & Related papers  (2022-09-29T16:54:53Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• On the Generalization of Stochastic Gradient Descent with Momentum [58.900860437254885]
  We first show that there exists a convex loss function for which algorithmic stability fails to establish generalization guarantees. For smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, and show that it admits an upper-bound on the generalization error. For the special case of strongly convex loss functions, we find a range of momentum such that multiple epochs of standard SGDM, as a special form of SGDEM, also generalizes.
  arXiv  Detail & Related papers  (2021-02-26T18:58:29Z)
• On the Generalization of Stochastic Gradient Descent with Momentum [84.54924994010703]
  momentum-based accelerated variants of gradient descent (SGD) are widely used when training machine learning models. We first show that there exists a convex loss function for which the stability gap for multiple epochs of SGD with standard heavy-ball momentum (SGDM) becomes unbounded. For smooth Lipschitz loss functions, we analyze a modified momentum-based update rule, i.e., SGD with early momentum (SGDEM) under a broad range of step-sizes.
  arXiv  Detail & Related papers  (2018-09-12T17:02:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.