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

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

## 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 (most cited first, 30 of 30)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel](https://mlsanity.com/paper/2010.15110/) (2020)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Finite Versus Infinite Neural Networks: an Empirical Study](https://mlsanity.com/paper/2007.15801/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Frequency Bias in Neural Networks for Input of Non-Uniform Density](https://mlsanity.com/paper/2003.04560/) (2020)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [The Gaussian equivalence of generative models for learning with shallow neural networks](https://mlsanity.com/paper/2006.14709/) (2020)
- [Neural Networks as Kernel Learners: The Silent Alignment Effect](https://mlsanity.com/paper/2111.00034/) (2021)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [On the insufficiency of existing momentum schemes for Stochastic Optimization](https://mlsanity.com/paper/1803.05591/) (2018)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [From Averaging to Acceleration, There is Only a Step-size](https://mlsanity.com/paper/1504.01577/) (2015)
- [On the Influence of Momentum Acceleration on Online Learning](https://mlsanity.com/paper/1603.04136/) (2016)
- ['Zhores' -- Petaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in Skolkovo Institute of Science and Technology](https://mlsanity.com/paper/1902.07490/) (2019)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits](https://mlsanity.com/paper/1901.07114/) (2019)
- [Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime](https://mlsanity.com/paper/2206.02927/) (2022)
- [Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions](https://mlsanity.com/paper/2202.00992/) (2022)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [Algorithms in Real Algebraic Geometry: A Survey](https://mlsanity.com/paper/1409.1534/) (2014)

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

- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [Exact Mean Square Linear Stability Analysis for SGD](https://mlsanity.com/paper/2306.07850/) (2023)
- [Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models](https://mlsanity.com/paper/2502.05074/) (2025)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [On the Stability of Nonlinear Dynamics in GD and SGD: Beyond Quadratic Potentials](https://mlsanity.com/paper/2602.14789/) (2026)
- [NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer](https://mlsanity.com/paper/2209.14937/) (2022)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [Corner Gradient Descent](https://mlsanity.com/paper/2504.12519/) (2025)
- [Loss Dynamics of Temporal Difference Reinforcement Learning](https://mlsanity.com/paper/2307.04841/) (2023)
- [Zeroth-Order Optimization at the Edge of Stability](https://mlsanity.com/paper/2604.14669/) (2026)

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