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

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 (5)

• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• No More Pesky Learning Rates
• Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics

Cited by in corpus (1)

• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models