Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent

Abstract

In the vanishing learning rate regime, stochastic gradient descent (SGD) is now relatively well understood. In this work, we propose to study the basic properties of SGD and its variants in the non-vanishing learning rate regime. The focus is on deriving exactly solvable results and discussing their implications. The main contributions of this work are to derive the stationary distribution for discrete-time SGD in a quadratic loss function with and without momentum; in particular, one implication of our result is that the fluctuation caused by discrete-time dynamics takes a distorted shape and is dramatically larger than a continuous-time theory could predict. Examples of applications of the proposed theory considered in this work include the approximation error of variants of SGD, the effect of minibatch noise, the optimal Bayesian inference, the escape rate from a sharp minimum, and the stationary covariance of a few second-order methods including damped Newton's method, natural gradient descent, and Adam.

arXiv commentCamera-ready version for the Thirty-eighth International Conference on Machine Learning (ICML 2021). 12 + 14 pages, 6 + 3 figures, 1 + 0 table. *First two authors contributed equally

References in corpus (21)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Three Factors Influencing Minima in SGD
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Quasi-hyperbolic momentum and Adam for deep learning
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• From Averaging to Acceleration, There is Only a Step-size
• The large learning rate phase of deep learning: the catapult mechanism
• Generalization in Deep Networks: The Role of Distance from Initialization
• Theory of Deep Learning IIb: Optimization Properties of SGD
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Multiplicative noise and heavy tails in stochastic optimization
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• Is deeper better? It depends on locality of relevant features
• On the Distributional Properties of Adaptive Gradients
• Improved generalization by noise enhancement

Cited by in corpus (1)

• Enhance Diffusion to Improve Robust Generalization