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

Abstract

We analyze a class of stochastic gradient algorithms with momentum on a high-dimensional random least squares problem. Our framework, inspired by random matrix theory, provides an exact (deterministic) characterization for the sequence of loss values produced by these algorithms which is expressed only in terms of the eigenvalues of the Hessian. This leads to simple expressions for nearly-optimal hyperparameters, a description of the limiting neighborhood, and average-case complexity. As a consequence, we show that (small-batch) stochastic heavy-ball momentum with a fixed momentum parameter provides no actual performance improvement over SGD when step sizes are adjusted correctly. For contrast, in the non-strongly convex setting, it is possible to get a large improvement over SGD using momentum. By introducing hyperparameters that depend on the number of samples, we propose a new algorithm sDANA (stochastic dimension adjusted Nesterov acceleration) which obtains an asymptotically optimal average-case complexity while remaining linearly convergent in the strongly convex setting without adjusting parameters.

arXiv comment39 pages, 7 figures

References in corpus (13)

• The generalization error of random features regression: Precise asymptotics and double descent curve
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• Measuring the Intrinsic Dimension of Objective Landscapes
• Accelerating SGD with momentum for over-parameterized learning
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
• The Role of Memory in Stochastic Optimization
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Stochastic Heavy Ball
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality