Pith. sign in

REVIEW 2 major objections 2 minor 55 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

Stochastic gradient descent with momentum is algorithmically stable for smooth convex problems.

2026-06-29 13:59 UTC pith:BCEB2LJN

load-bearing objection SGDM stability without Lipschitz via trajectory errors closes the momentum generalization conjecture, but check the uniformity for high momentum. the 2 major comments →

arxiv 2605.28517 v1 pith:BCEB2LJN submitted 2026-05-27 cs.LG cs.AI

Stochastic Gradient Descent with Momentum is Algorithmically Stable

Yunwen Lei , Zimeng Wang , Xiaoming Yuan This is my paper
classification cs.LG cs.AI
keywords stochastic gradient descent with momentumalgorithmic stabilitygeneralization boundsconvex optimizationPolyak momentumNesterov momentumon-average stability
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses the open question of whether momentum in stochastic gradient descent harms generalization. It proves that SGDM remains algorithmically stable by deriving tight on-average model stability bounds that hold for smooth convex problems. The bounds apply to every momentum value in the interval from zero up to but not including one and avoid any Lipschitz assumption on the loss. They achieve tightness by using the fact that optimization error stays small along the algorithm trajectory. The stability results are then paired with new optimization error bounds to produce optimal excess population risk guarantees for both Polyak and Nesterov momentum.

Core claim

The authors introduce a generalized SGDM framework that covers both Polyak's and Nesterov's momentum. They establish tight on-average model stability bounds for smooth and convex problems. These bounds exploit small optimization error bounds along the trajectory, apply to any momentum parameter in [0, 1), and do not require the commonly assumed Lipschitzness of loss functions. They further derive optimization error bounds for the generalized SGDM and combine them with the stability analysis to obtain optimal excess population risk bounds.

What carries the argument

On-average model stability bounds in the generalized SGDM framework, which quantify model sensitivity to data perturbations by exploiting small optimization errors along the trajectory.

Load-bearing premise

The optimization problems are smooth and convex and the optimization error stays small along the algorithm trajectory.

What would settle it

A smooth convex problem on which SGDM with momentum near one produces excess population risk strictly larger than the optimal rate predicted by the bounds, even though optimization error along the trajectory remains small.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Stability bounds hold for every momentum parameter in the interval [0, 1).
  • No Lipschitz continuity of the loss function is required.
  • Optimal excess population risk bounds are achieved for both Polyak's and Nesterov's momentum.
  • The results apply inside the generalized SGDM framework that unifies the two momentum schemes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stability technique could be tested on other accelerated first-order methods if comparable trajectory error bounds can be shown.
  • On convex problems the choice of momentum value appears free from generalization penalties once optimization error is controlled.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper introduces a generalized SGDM framework encompassing Polyak and Nesterov momentum, and claims to establish tight on-average model stability bounds for smooth convex problems. These bounds exploit small optimization error along the trajectory, apply to any momentum parameter in [0,1), and avoid the standard Lipschitzness assumption on losses. The paper further derives optimization error bounds for generalized SGDM and combines them with the stability results to obtain optimal excess population risk bounds.

Significance. If the central claims hold, the work would resolve the open question of whether momentum degrades generalization, delivering optimal excess-risk guarantees for a widely used family of optimizers. The avoidance of Lipschitzness via trajectory-specific optimization error is a technical strength, as is the uniformity over the full momentum interval [0,1). The combination of stability and optimization analyses to reach optimality is a clear contribution to the algorithmic-stability literature.

major comments (2)
  1. [§4 and §5] §4 (stability analysis) and the abstract: the on-average stability bounds are derived by exploiting 'small optimization error bounds along the trajectory' to dispense with Lipschitzness. This step is load-bearing; the optimization-error results in §5 must therefore guarantee that the error remains sufficiently small uniformly for every momentum parameter in [0,1) and for the step-size regimes used in the stability theorems. No such uniform verification is provided, and the skeptic concern that the error may grow for momentum near 1 is not addressed.
  2. [Theorem 5.1] Theorem 5.1 / Corollary 5.2 (optimization error): the stated rates appear to depend on the momentum parameter in a way that could violate the 'small error' hypothesis used in the preceding stability argument when the momentum approaches 1. A concrete check (e.g., an explicit upper bound on the trajectory error that is independent of momentum or that scales appropriately) is required to close the argument.
minor comments (2)
  1. [§2] The definition of the generalized SGDM update (Eq. (3) or (4)) should explicitly state the range of the momentum parameter and any implicit assumptions on the step-size schedule.
  2. [§1] A short remark comparing the obtained stability rates with the classical uniform-stability bounds of Hardt et al. (2016) would help readers situate the improvement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for pinpointing the need to make the uniformity of the optimization-error bounds explicit. The concerns are well-taken and can be resolved by adding a short clarifying statement and corollary; we outline the responses below.

read point-by-point responses

  1. Referee: [§4 and §5] §4 (stability analysis) and the abstract: the on-average stability bounds are derived by exploiting 'small optimization error bounds along the trajectory' to dispense with Lipschitzness. This step is load-bearing; the optimization-error results in §5 must therefore guarantee that the error remains sufficiently small uniformly for every momentum parameter in [0,1) and for the step-size regimes used in the stability theorems. No such uniform verification is provided, and the skeptic concern that the error may grow for momentum near 1 is not addressed.

    Authors: We agree that an explicit uniformity statement is desirable for readability. The analysis in Section 5 already yields an optimization-error bound whose leading term is independent of β (the momentum parameter appears only in constants that remain bounded for β ∈ [0,1) under the step-size schedule used in the stability theorems). Nevertheless, to remove any ambiguity we will insert a short corollary immediately after Theorem 5.1 that states the uniform trajectory-error bound and verifies that it is small enough for the stability argument in Section 4. This addition will be purely expository and will not alter any proofs. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 / Corollary 5.2 (optimization error): the stated rates appear to depend on the momentum parameter in a way that could violate the 'small error' hypothesis used in the preceding stability argument when the momentum approaches 1. A concrete check (e.g., an explicit upper bound on the trajectory error that is independent of momentum or that scales appropriately) is required to close the argument.

    Authors: The leading term of the optimization-error bound in Theorem 5.1 is O(1/√T) and does not depend on β; any β-dependent factors are absorbed into constants that remain finite and uniform on [0,1). We will add an explicit, β-independent upper bound on the trajectory error (derived directly from the proof of Theorem 5.1) as a new corollary. This will directly confirm that the error stays sufficiently small for every β used in the stability results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; independent derivation of optimization bounds then stability

full rationale

The paper first derives optimization error bounds for generalized SGDM on smooth convex problems, then uses those bounds to establish on-average stability without requiring Lipschitzness. The two analyses are sequential and non-referential; stability exploits the (separately proven) small trajectory errors rather than assuming them or feeding stability back into optimization. No self-citations, fitted parameters, or ansatzes are load-bearing in the central claims. This is the standard non-circular structure for such generalization analyses.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based on abstract only; no free parameters or invented entities mentioned. Axioms are the problem class and trajectory error assumption.

axioms (2)
  • domain assumption The optimization problems are smooth and convex.
    Stated in abstract as the setting for the bounds.
  • domain assumption Optimization error bounds are small along the trajectory.
    Exploited in the stability bounds per abstract.

pith-pipeline@v0.9.1-grok · 5715 in / 1236 out tokens · 50002 ms · 2026-06-29T13:59:08.939573+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2605.28517 by Xiaoming Yuan, Yunwen Lei, Zimeng Wang.

Figure 1
Figure 1. Figure 1: Tests on different step sizes for (SGD-HB) (top row) and (SGD-N) (bottom row) with fixed momentum parameter β = 0.9. The y-axis records the Euclidean distance ∥wt − w′ t∥2. To ensure robustness and statistical significance, we conduct 100 independent repetitions for each configuration on each dataset. We report the average and standard deviation of the distance dt against the number of epochs (defined as t… view at source ↗
Figure 2
Figure 2. Figure 2: Tests on different momentum parameters for [PITH_FULL_IMAGE:figures/full_fig_p027_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 5 canonical work pages · 4 internal anchors

  1. [1]

    Agarwal, M

    A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Ravikumar. Information-theoretic lower bounds on the oracle complexity of convex optimization. InAdvances in Neural Information Processing Systems, pages 1–9, 2009

    2009

  2. [2]

    Attia and T

    A. Attia and T. Koren. Algorithmic instabilities of accelerated gradient descent.Advances in Neural Information Processing Systems, 34:1204–1214, 2021

    2021

  3. [3]

    Bassily, V

    R. Bassily, V. Feldman, C. Guzm´ an, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses.Advances in Neural Information Processing Systems, 33, 2020

    2020

  4. [4]

    Beck and M

    A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009

    2009

  5. [5]

    Bottou, F

    L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning.SIAM Review, 60(2):223–311, 2018

    2018

  6. [6]

    Bousquet and A

    O. Bousquet and A. Elisseeff. Stability and generalization.Journal of Machine Learning Research, 2(Mar): 499–526, 2002

    2002

  7. [7]

    Bousquet, Y

    O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610–626, 2020

    2020

  8. [8]

    C. Chang. LIBSVM data: Classification, regression, and multi-label.http://www. csie. ntu. edu. tw/˜ cjlin/libsvmtools/datasets/, 2008

    2008

  9. [9]

    Charles and D

    Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. InInternational Conference on Machine Learning, pages 744–753, 2018

    2018

  10. [10]

    L. Chen, H. Fernando, Y. Ying, and T. Chen. Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance.Journal of Machine Learning Research, 25(193):1–53, 2024

    2024

  11. [11]

    Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms.arXiv preprint arXiv:1804.01619, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  12. [12]

    T. Dang, M. Barsbey, A. Sonet, M. Gurbuzbalaban, U. Simsekli, and L. Zhu. Algorithmic stability of 27 stochastic gradient descent with momentum under heavy-tailed noise.arXiv preprint arXiv:2502.00885, 2025

    work page arXiv 2025

  13. [13]

    Deora, R

    P. Deora, R. Ghaderi, H. Taheri, and C. Thrampoulidis. On the optimization and generalization of multi-head attention.Transactions on Machine Learning Research, 2024

    2024

  14. [14]

    Elisseeff, T

    A. Elisseeff, T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms.Journal of Machine Learning Research, 6(Jan):55–79, 2005

    2005

  15. [15]

    Feldman and J

    V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. InConference on Learning Theory, pages 1270–1279, 2019

    2019

  16. [16]

    Ghadimi and G

    S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59–99, 2016

    2016

  17. [17]

    Gitman, H

    I. Gitman, H. Lang, P. Zhang, and L. Xiao. Understanding the role of momentum in stochastic gradient methods.Advances in Neural Information Processing Systems, 32, 2019

    2019

  18. [18]

    Hardt, B

    M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: stability of stochastic gradient descent. InInternational Conference on Machine Learning, pages 1225–1234, 2016

    2016

  19. [19]

    K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016

    2016

  20. [20]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. InInternational Conference on Learning Representations, 2015

    2015

  21. [21]

    Kuzborskij and C

    I. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. InInternational Conference on Machine Learning, pages 2820–2829, 2018

    2018

  22. [22]

    G. Lan. An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2): 365–397, 2012

    2012

  23. [23]

    LeCun, Y

    Y. LeCun, Y. Bengio, and G. Hinton. Deep learning.Nature, 521(7553):436–444, 2015

    2015

  24. [24]

    Lei and Y

    Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809–5819, 2020

    2020

  25. [25]

    Y. Lei, Z. Wang, and X. Yuan. From convergence to generalization: Stability of stationary-point learning algorithms.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2026

    2026

  26. [26]

    Loizou and P

    N. Loizou and P. Richt´ arik. Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods.Computational Optimization and Applications, 77(3):653–710, 2020

    2020

  27. [27]

    Nesterov

    Y. Nesterov. Gradient methods for minimizing composite functions.Mathematical Programming, 140(1): 125–161, 2013

    2013

  28. [28]

    Nesterov.Introductory Lectures on Convex Optimization: A Basic Course, volume 87

    Y. Nesterov.Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013

    2013

  29. [29]

    Y. E. Nesterov. A method for solving the convex programming problem with convergence rate O(1/k2). In Dokl. akad. nauk Sssr, volume 269, pages 543–547, 1983

    1983

  30. [30]

    G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theoretic generalization bounds for stochastic gradient descent. InConference on Learning Theory, pages 3526–3545. PMLR, 2021

    2021

  31. [31]

    L. M. Nguyen, P. H. Nguyen, P. Richt´ arik, K. Scheinberg, M. Tak´ aˇ c, and M. van Dijk. New convergence aspects of stochastic gradient algorithms.Journal of Machine Learning Research, 20(176):1–49, 2019

    2019

  32. [32]

    Nikolakakis, F

    K. Nikolakakis, F. Haddadpour, A. Karbasi, and D. Kalogerias. Beyond Lipschitz: sharp generalization and excess risk bounds for full-batch GD. InInternational Conference on Learning Representations, 2022

    2022

  33. [33]

    P. Ochs, Y. Chen, T. Brox, and T. Pock. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences, 7(2):1388–1419, 2014

    2014

  34. [34]

    P. Ochs, T. Brox, and T. Pock. iPiasco: inertial proximal algorithm for strongly convex optimization. Journal of Mathematical Imaging and Vision, 53(2):171–181, 2015

    2015

  35. [35]

    B. T. Polyak. Some methods of speeding up the convergence of iteration methods.USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964

    1964

  36. [36]

    N. Qian. On the momentum term in gradient descent learning algorithms.Neural Networks, 12(1):145–151, 1999

    1999

  37. [37]

    Ramezani-Kebrya, K

    A. Ramezani-Kebrya, K. Antonakopoulos, V. Cevher, A. Khisti, and B. Liang. On the generalization of stochastic gradient descent with momentum.Journal of Machine Learning Research, 25(22):1–56, 2024

    2024

  38. [38]

    Richards and I

    D. Richards and I. Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks 28 without the neural tangent kernel.Advances in Neural Information Processing Systems, 34, 2021

    2021

  39. [39]

    Robbins and S

    H. Robbins and S. Monro. A stochastic approximation method.Annals of Mathematical Statistics, pages 400–407, 1951

    1951

  40. [40]

    Schliserman and T

    M. Schliserman and T. Koren. Stability vs implicit bias of gradient methods on separable data and beyond. InConference on Learning Theory, pages 3380–3394, 2022

    2022

  41. [41]

    Sebbouh, R

    O. Sebbouh, R. M. Gower, and A. Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. InConference on Learning Theory, pages 3935–3971. PMLR, 2021

    2021

  42. [42]

    Shalev-Shwartz, O

    S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(Oct):2635–2670, 2010

    2010

  43. [43]

    Very Deep Convolutional Networks for Large-Scale Image Recognition

    K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition.arXiv preprint arXiv:1409.1556, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  44. [44]

    Srebro, K

    N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. InAdvances in Neural Information Processing Systems, pages 2199–2207, 2010

    2010

  45. [45]

    Sutskever, J

    I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. InInternational Conference on Machine Learning, pages 1139–1147, 2013

    2013

  46. [46]

    Taheri and C

    H. Taheri and C. Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width.Journal of Machine Learning Research, 25(156):1–41, 2024

    2024

  47. [47]

    Villa, L

    S. Villa, L. Rosasco, and T. Poggio. On learnability, complexity and stability. InEmpirical Inference: Festschrift in Honor of Vladimir N. Vapnik, pages 59–69. Springer, 2013

    2013

  48. [48]

    X. Wang, M. Johansson, and T. Zhang. Generalized polyak step size for first order optimization with momentum. InInternational Conference on Machine Learning, pages 35836–35863. PMLR, 2023

    2023

  49. [49]

    Y. Yan, T. Yang, Z. Li, Q. Lin, and Y. Yang. A unified analysis of stochastic momentum methods for deep learning.arXiv preprint arXiv:1808.10396, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  50. [50]

    T. Yang, Q. Lin, and Z. Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization.arXiv preprint arXiv:1604.03257, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  51. [51]

    H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. InInternational Conference on Machine Learning, pages 7184–7193. PMLR, 2019

    2019

  52. [52]

    Zeng and Y

    S. Zeng and Y. Lei. Stochastic gradient methods: Bias, stability and generalization.Journal of Machine Learning Research, 27(6):1–55, 2026

    2026

  53. [53]

    T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In International Conference on Machine Learning, pages 919–926, 2004

    2004

  54. [54]

    Zhang.Mathematical Analysis of Machine Learning Algorithms

    T. Zhang.Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023

    2023

  55. [55]

    Zhao, Y.-J

    P. Zhao, Y.-J. Zhang, L. Zhang, and Z.-H. Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization.Journal of Machine Learning Research, 25(98):1–52, 2024. 29

    2024