CoChat
Sign Up
PreprintCited by 4Stochastic Gradient Optimization TechniquesAdvanced Optimization Algorithms ResearchOptimization and Variational Analysis

The DOI matches its DataCite record.

Modified Loss of Momentum Gradient Descent: Fine-Grained Analysis

Open access
Cattaneo, Matias D., Shigida, Boris·2025·arXiv
DOI 10.48550/arxiv.2509.08483arXiv 2509.08483
Open this paper in CoChat — free accountOpen PDF

Abstract

We analyze gradient descent with Polyak (1964) heavy-ball momentum (HB) whose fixed momentum hyperparameter $β\in (0, 1)$ provides exponential decay of memory. Building on Kovachki and Stuart (2021), we prove that on an exponentially attractive invariant manifold the algorithm is exactly plain gradient descent with a modified loss, provided that the step size $h$ is small enough. Although the modified loss does not admit a closed-form expression, we describe it up to $O(h^{\mathcal{R}})$-errors for arbitrary finite order $\mathcal{R}$, and prove global (finite "time" horizon) trajectory approximation bounds $O(h^{\mathcal{R}})$. We then conduct a fine-grained analysis of the combinatorics underlying the memoryless approximations of HB, in particular, finding a rich family of polynomials in $β$ hidden inside which include and lie coefficient-wise in between Eulerian and Narayana polynomials. We prove that these polynomials are $h$-polynomials of certain graph-associahedra. As corollaries of the main results, we derive continuous modified equations of arbitrary finite approximation order (with rigorous bounds) and the principal flow that approximates the HB dynamics, generalizing Rosca et al. (2023). Approximation theorems cover both full-batch and mini-batch HB. The results shed new light on the main features of HB and outline a roadmap for similar analysis of other optimization algorithms.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2509.08483

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 56

  1. Arseniy Andreyev and Pierfrancesco Beneventano. "Edge of Stochastic Stability: Revis- iting the Edge of Stability for SGD". arXiv preprint arXiv:2412.20553 (2025) (cit. on p. 6). · arXiv
  2. Chengming Bai et al. "Post-groups, (Lie-)Butcher groups and the Yang-Baxter equation". Mathematische Annalen 388.3 (2024), pp. 3127-3167 (cit. on p. 9). · DOI
  3. David Barrett and Benoit Dherin. "Implicit Gradient Regularization". International Con- ference on Learning Representations. 2021 (cit. on pp. 7, 41).
  4. Pierfrancesco Beneventano. "On the Trajectories of SGD Without Replacement". arXiv preprint arXiv:2312.16143 (2024) (cit. on p. 4). · arXiv
  5. Wolf-Jürgen Beyn. "Numerical methods for dynamical systems". Advances in Numerical Analysis 1 (1991), pp. 175-236 (cit. on p. 7).
  6. Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher. "Combinatorial parame- ters in bargraphs". Quaestiones Mathematicae 39.5 (2016), pp. 619-635 (cit. on p. 24). · DOI
  7. Léon Bottou, Frank E Curtis, and Jorge Nocedal. "Optimization methods for large-scale machine learning". SIAM review 60.2 (2018), pp. 223-311 (cit. on p. 4).
  8. V. M. Buchstaber and V. D. Volodin. "Sharp upper and lower bounds for nestohedra". Izvestiya: Mathematics 75.6 (2011). English translation of Izv. Ross. Akad. Nauk Ser. Mat. 75:6 (2011), 17-46, pp. 1107-1133 (cit. on p. 29). · DOI
  9. John C Butcher. "An algebraic theory of integration methods". Mathematics of Compu- tation 26.117 (1972), pp. 79-106 (cit. on p. 29).
  10. MP Calvo, A Murua, and JM Sanz-Serna. "Modified equations for ODEs". Contemporary Mathematics 172 (1994), pp. 63-74 (cit. on p. 7).
  11. Matias D. Cattaneo, Jason Matthew Klusowski, and Boris Shigida. "On the Implicit Bias of Adam". Proceedings of the 41st International Conference on Machine Learning. Vol. 235. Proceedings of Machine Learning Research. PMLR, 2024, pp. 5862-5906 (cit. on p. 7).
  12. Matias D. Cattaneo and Boris Shigida. "How Memory in Optimization Algorithms Im- plicitly Modifies the Loss". Advances in Neural Information Processing Systems. Vol. 38. Curran Associates, Inc., 2025, pp. 156059-156096 (cit. on pp. 4, 14). · DOI · Paper page
  13. Philippe Chartier, Ernst Hairer, and Gilles Vilmart. "Algebraic structures of B-series". Foundations of Computational Mathematics 10.4 (2010), pp. 407-427 (cit. on p. 9).
  14. Philippe Chartier, Ernst Hairer, and Gilles Vilmart. "Numerical integrators based on mod- ified differential equations". Mathematics of Computation 76.260 (2007), pp. 1941-1953 (cit. on p. 7).
  15. Jeremy Cohen et al. "Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability". International Conference on Learning Representations. 2021 (cit. on p. 6).
  16. Curtis Coker. "Enumerating a class of lattice paths". Discrete mathematics 271.1-3 (2003), pp. 13-28 (cit. on p. 23).
  17. Timo Eirola. "Aspects of backward error analysis of numerical ODEs". Journal of Com- putational and Applied Mathematics 45.1-2 (1993), pp. 65-73 (cit. on p. 7).
  18. Mohammad Farazmand. "Multiscale analysis of accelerated gradient methods". SIAM Journal on Optimization 30.3 (2020), pp. 2337-2354 (cit. on pp. 7, 39). · DOI
  19. William G. Faris. "Rooted tree graphs and the Butcher group: Combinatorics of elemen- tary perturbation theory". Sojourns in Probability Theory and Statistical Physics -II. Ed. by Vladas Sidoravicius. Vol. 299. Springer Proceedings in Mathematics & Statistics. Singapore: Springer, 2019, pp. 135-166 (cit. on pp. 8, 9, 30). · DOI
  20. Kang Feng. "Formal power series and numerical algorithms for dynamical systems". Proc. International Conference on Scientific Computation, Hangzhou, China. 1991, pp. 28-35 (cit. on p. 7).
  21. Neil Fenichel. "Persistence and smoothness of invariant manifolds for flows". Indiana Uni- versity Mathematics Journal 21.3 (1971), pp. 193-226 (cit. on p. 3).
  22. Pierre Foret et al. "Sharpness-aware Minimization for Efficiently Improving Generaliza- tion". International Conference on Learning Representations. 2021 (cit. on p. 41).
  23. Christopher A. Francisco, Jeffrey Mermin, and Jay Schweig. "A survey of Stanley-Reisner theory". Connections between Algebra, Combinatorics, and Geometry. Vol. 76. Springer Proceedings in Mathematics & Statistics. Springer, 2014, pp. 209-234 (cit. on p. 25).
  24. Avrajit Ghosh et al. "Implicit regularization in Heavy-ball momentum accelerated stochas- tic gradient descent". The Eleventh International Conference on Learning Representations. 2023 (cit. on pp. 7, 39, 41).
  25. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. The MIT Press, 2016 (cit. on p. 3).
  26. David F Griffiths and Jesús María Sanz-Serna. "On the scope of the method of modified equations". SIAM Journal on Scientific and Statistical Computing 7.3 (1986), pp. 994- 1008 (cit. on p. 7).
  27. Vineet Gupta, Tomer Koren, and Yoram Singer. "Shampoo: Preconditioned Stochas- tic Tensor Optimization". Proceedings of the 35th International Conference on Machine Learning. Vol. 80. Proceedings of Machine Learning Research. PMLR, 2018, pp. 1842-1850 (cit. on p. 41).
  28. Ernst Hairer. "Backward analysis of numerical integrators and symplectic methods". An- nals of Numerical Mathematics 1 (1994), pp. 107-132 (cit. on p. 7).
  29. Ernst Hairer, Christian Lubich, and Gerhard Wanner. Geometric numerical integration. 2nd ed. Springer-Verlag, Berlin, 2006. isbn: 978-3-540-30666-5 (cit. on pp. 7, 38). · DOI
  30. Ernst Hairer and Gerhard Wanner. "On the Butcher group and general multi-value meth- ods". Computing 13.1 (1974), pp. 1-15 (cit. on p. 29).
  31. Kaiming He et al. "Deep residual learning for image recognition". Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016, pp. 770-778 (cit. on p. 3).
  32. Tong He et al. "Bag of tricks for image classification with convolutional neural networks". Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019, pp. 558-567 (cit. on p. 3).
  33. Morris W Hirsch, Charles Chapman Pugh, and Michael Shub. "Invariant manifolds". Bul- letin of the American Mathematical Society 76.5 (1970), pp. 1015-1019 (cit. on p. 3).
  34. Adalbert Kerber. Applied Finite Group Actions. 2nd ed. Vol. 19. Algorithms and Com- binatorics. Berlin and Heidelberg: Springer Berlin Heidelberg, 1999, pp. xxv+454. isbn: 978-3-540-65941-9 (cit. on p. 8). · DOI
  35. Nitish Shirish Keskar et al. "On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima". International Conference on Learning Representations. 2017 (cit. on p. 4).
  36. Diederik P. Kingma and Jimmy Ba. "Adam: A Method for Stochastic Optimization". International Conference on Learning Representations. 2015 (cit. on p. 41).
  37. Nikola B. Kovachki and Andrew M. Stuart. "Continuous Time Analysis of Momentum Methods". Journal of Machine Learning Research 22.17 (2021), pp. 1-40 (cit. on pp. 1, 3, 7, 10, 11, 39, 43, 48).
  38. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. "ImageNet Classification with Deep Convolutional Neural Networks". Advances in Neural Information Processing Sys- tems. Vol. 25. Curran Associates, Inc., 2012 (cit. on p. 3).
  39. Bochen Lyu et al. "Heavy-Ball Momentum Method in Continuous Time and Discretization Error Analysis". Advances in Neural Information Processing Systems. Vol. 38. Curran Associates, Inc., 2025, pp. 134262-134298 (cit. on p. 7). · DOI
  40. Dominic Masters and Carlo Luschi. "Revisiting small batch training for deep neural net- works". arXiv preprint arXiv:1804.07612 (2018) (cit. on p. 4). · arXiv
  41. Taiki Miyagawa. "Toward Equation of Motion for Deep Neural Networks: Continuous-time Gradient Descent and Discretization Error Analysis". Advances in Neural Information Processing Systems. Ed. by Alice H. Oh et al. 2022 (cit. on p. 7).
  42. B.T. Polyak. "Some methods of speeding up the convergence of iteration methods". USSR Computational Mathematics and Mathematical Physics 4.5 (1964), pp. 1-17. issn: 0041- 5553 (cit. on pp. 1, 3, 41). · DOI · Paper page
  43. Alexander Postnikov, Victor Reiner, and Lauren Williams. "Faces of generalized permu- tohedra". Documenta Mathematica 13 (2008), pp. 207-273 (cit. on pp. 25, 29).
  44. Simon J.D. Prince. Understanding Deep Learning. The MIT Press, 2023 (cit. on pp. 3, 4).
  45. Sebastian Reich. "Backward error analysis for numerical integrators". SIAM Journal on Numerical Analysis 36.5 (1999), pp. 1549-1570 (cit. on p. 7).
  46. Mihaela Rosca et al. "On a continuous time model of gradient descent dynamics and instability in deep learning". Transactions on Machine Learning Research (2023). issn: 2835-8856 (cit. on pp. 1, 6, 7, 37, 39, 40).
  47. Bin Shi et al. "Understanding the acceleration phenomenon via high-resolution differential equations". Mathematical Programming 195.1 (2022), pp. 79-148 (cit. on p. 7).
  48. Samuel Smith, Erich Elsen, and Soham De. "On the Generalization Benefit of Noise in Stochastic Gradient Descent". Proceedings of the 37th International Conference on Machine Learning. Vol. 119. Proceedings of Machine Learning Research. PMLR, 2020, pp. 9058-9067 (cit. on p. 4).
  49. Samuel L Smith et al. "On the Origin of Implicit Regularization in Stochastic Gradient Descent". International Conference on Learning Representations. 2021 (cit. on pp. 4, 7, 41).
  50. Andrew M Stuart and Anthony R Humphries. Dynamical systems and numerical analysis. Vol. 2. Cambridge University Press, 1998 (cit. on p. 7).
  51. Ilya Sutskever et al. "On the importance of initialization and momentum in deep learning". Proceedings of the 30th International Conference on Machine Learning. Vol. 28. Proceed- ings of Machine Learning Research. Atlanta, Georgia, USA: PMLR, 2013, pp. 1139-1147 (cit. on p. 3).
  52. Robert F Warming and B Jeanne Hyett. "The modified equation approach to the stability and accuracy analysis of finite-difference methods". Journal of Computational Physics 14.2 (1974), pp. 159-179 (cit. on p. 7).
  53. Stephen Wiggins. Normally hyperbolic invariant manifolds in dynamical systems. Vol. 105. Springer Science & Business Media, 2013 (cit. on p. 3).
  54. James H Wilkinson. "Error analysis of floating-point computation". Numerische Mathe- matik 2.1 (1960), pp. 319-340 (cit. on p. 7).
  55. Saining Xie et al. "Aggregated residual transformations for deep neural networks". Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017, pp. 1492-1500 (cit. on p. 3).
  56. Yang Zhao, Hao Zhang, and Xiuyuan Hu. "Penalizing Gradient Norm for Efficiently Im- proving Generalization in Deep Learning". Proceedings of the 39th International Confer- ence on Machine Learning. Vol. 162. Proceedings of Machine Learning Research. PMLR, 2022, pp. 26982-26992 (cit. on p. 41).

Cited by

Sorted by citations

Metadata

Authors
Cattaneo, M. D., & Shigida, B.
Affiliations
Princeton University (US)
Venue
arXiv
Publisher
arXiv
Published
2025
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2509.08483
arXiv
2509.08483
OpenAlex
W4417070075
Cited by
4
References
0
Citations by year
2026: 3 · 2025: 1
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (2241575, 2019432)
  • John Simon Guggenheim Memorial Foundation
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
Keywords
heavy-ball momentum, gradient descent, trajectory approximation, Narayana polynomials, Eulerian polynomials, h-polynomials, graph associahedra, mini-batch optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review