SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
arXiv:2102.04396
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.
References in corpus (20)
- Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- No More Pesky Learning Rates
- The generalization error of random features regression: Precise asymptotics and double descent curve
- Three Factors Influencing Minima in SGD
- Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
- Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
- An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
- The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
- Accelerating Stochastic Gradient Descent For Least Squares Regression
- Eigenstate Thermalization Hypothesis for Wigner Matrices
- The Heavy-Tail Phenomenon in SGD
- The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
- On the diffusion approximation of nonconvex stochastic gradient descent
- Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
- Matrix Concentration for Products
- Universal halting times in optimization and machine learning
- Average-case Acceleration Through Spectral Density Estimation