SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality

2021/02/08 by Courtney Paquette, Paquette, Courtney, Kiwon Lee +5 · 4 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Probability (math.PR) #Random Matrices and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2102.04396

openalex publication_date 2021/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a new framework, inspired by random matrix theory, for analyzing the dynamics of stochastic gradient descent (SGD) when both number of samples and dimensions are large. This framework applies to any fixed stepsize and the finite sum setting. Using this new framework, we show that the dynamics of SGD on a least squares problem with random data become deterministic in the large sample and dimensional limit. Furthermore, the limiting dynamics are governed by a Volterra integral equation. This model predicts that SGD undergoes a phase transition at an explicitly given critical stepsize that ultimately affects its convergence rate, which we also verify experimentally. Finally, when input data is isotropic, we provide explicit expressions for the dynamics and average-case convergence rates (i.e., the complexity of an algorithm averaged over all possible inputs). These rates show significant improvement over the worst-case complexities.

Citations

• A Stochastic Approximation Method
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp\n Minima
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Three Factors Influencing Minima in SGD
• An Investigation into Neural Net Optimization via Hessian Eigenvalue\n Density
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD\n Training and Sample Size
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning\n Dynamics

Cited by

• Universality of high-dimensional scaling limits of stochastic gradient descent
• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• Statistical Inference for Linear Functionals of Online Least-squares SGD when t \gtrsim d^1+δ
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent

Related

• High-dimensional limit theorems for SGD: Effective dynamics and critical scaling
• High-dimensional limit of one-pass SGD on least squares
• High-dimensional limit theorems for SGD: Momentum and Adaptive Step-sizes
• Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent
• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution