mlsanityData to 14 Oct 2026

A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta

arXiv 2206.11124 ↗First posted 22 Jun 2022cs.LG math.OC stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

Mini-batch SGD with momentum is a fundamental algorithm for learning large predictive models. In this paper we develop a new analytic framework to analyze noise-averaged properties of mini-batch SGD for linear models at constant learning rates, momenta and sizes of batches. Our key idea is to consider the dynamics of the second moments of model parameters for a special family of "Spectrally Expressible" approximations. This allows to obtain an explicit expression for the generating function of the sequence of loss values. By analyzing this generating function, we find, in particular, that 1) the SGD dynamics exhibits several convergent and divergent regimes depending on the spectral distributions of the problem; 2) the convergent regimes admit explicit stability conditions, and explicit loss asymptotics in the case of power-law spectral distributions; 3) the optimal convergence rate can be achieved at negative momenta. We verify our theoretical predictions by extensive experiments with MNIST, CIFAR10 and synthetic problems, and find a good quantitative agreement.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 30 of its 68 references that are in the map. First posted on arXiv 22 Jun 2022.

Builds on

30 of 68 references.

References · 30

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  3. 2021Explaining Neural Scaling Lawscited by 363
  4. 2018Measuring the Effects of Data Parallelism on Neural Network Trainingcited by 193
  5. 2020Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernelcited by 187
  6. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  7. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 157
  8. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  9. 2020Frequency Bias in Neural Networks for Input of Non-Uniform Densitycited by 140
  10. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  11. 2020The Gaussian equivalence of generative models for learning with shallow neural networkscited by 113
  12. 2021Neural Networks as Kernel Learners: The Silent Alignment Effectcited by 106
18 more
  1. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  2. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
  3. 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 91
  4. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  5. 2018On the insufficiency of existing momentum schemes for Stochastic Optimizationcited by 49
  6. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  7. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  8. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  9. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  10. 2016On the Influence of Momentum Acceleration on Online Learningcited by 24
  11. 2019'Zhores' -- Petaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in Skolkovo Institute of Science and Technologycited by 23
  12. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 16
  13. 2021Learning curves for Gaussian process regression with power-law priors and targetscited by 15
  14. 2019Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefitscited by 13
  15. 2022Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regimecited by 11
  16. 2022Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditionscited by 9
  17. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  18. 2014Algorithms in Real Algebraic Geometry: A Surveycited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 2; 2025: 3; 2026: 3.

11 papers.

  1. 2026A Defense of the Quadratic Modelcited by 14
  2. 2023Exact Mean Square Linear Stability Analysis for SGDcited by 11
  3. 2025Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Modelscited by 7
  4. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  5. 2025On the Effectiveness of the z-Transform Method in Quadratic Optimizationcited by 3
  6. 2026On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentialscited by 3
  7. 2022NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizercited by 2
  8. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  9. 2025Corner Gradient Descentcited by 1
  10. 2023Loss Dynamics of Temporal Difference Reinforcement Learningcited by 0
  11. 2026Zeroth-Order Optimization at the Edge of Stabilitycited by 0