On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks

Abstract

The gradient noise (GN) in the stochastic gradient descent (SGD) algorithm is often considered to be Gaussian in the large data regime by assuming that the \emph{classical} central limit theorem (CLT) kicks in. This assumption is often made for mathematical convenience, since it enables SGD to be analyzed as a stochastic differential equation (SDE) driven by a Brownian motion. We argue that the Gaussianity assumption might fail to hold in deep learning settings and hence render the Brownian motion-based analyses inappropriate. Inspired by non-Gaussian natural phenomena, we consider the GN in a more general context and invoke the \emph{generalized} CLT, which suggests that the GN converges to a \emph{heavy-tailed} $\alpha$-stable random vector, where \emph{tail-index} $\alpha$ determines the heavy-tailedness of the distribution. Accordingly, we propose to analyze SGD as a discretization of an SDE driven by a Lévy motion. Such SDEs can incur `jumps', which force the SDE and its discretization \emph{transition} from narrow minima to wider minima, as proven by existing metastability theory and the extensions that we proved recently. In this study, under the $\alpha$-stable GN assumption, we further establish an explicit connection between the convergence rate of SGD to a local minimum and the tail-index $\alpha$. To validate the $\alpha$-stable assumption, we conduct experiments on common deep learning scenarios and show that in all settings, the GN is highly non-Gaussian and admits heavy-tails. We investigate the tail behavior in varying network architectures and sizes, loss functions, and datasets. Our results open up a different perspective and shed more light on the belief that SGD prefers wide minima.

arXiv comment32 pages. arXiv admin note: substantial text overlap with arXiv:1901.06053

References in corpus (18)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Revisiting Small Batch Training for Deep Neural Networks
• Three Factors Influencing Minima in SGD
• Levy Anomalous Diffusion and Fractional Fokker--Planck Equation
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• WNGrad: Learn the Learning Rate in Gradient Descent
• Traditional and Heavy-Tailed Self Regularization in Neural Network Models
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Non-Gaussianity of Stochastic Gradient Noise
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization
• Once more on comparison of tail index estimators
• Gradient Estimates and Ergodicity for SDEs Driven by Multiplicative Lévy Noises via Coupling

Cited by in corpus (14)

• The Heavy-Tail Phenomenon in SGD
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds
• Law of large numbers and central limit theorem for wide two-layer neural networks: the mini-batch and noisy case
• Heavy-Tail Phenomenon in Decentralized SGD
• Isotropic SGD: a Practical Approach to Bayesian Posterior Sampling
• Eliminating Sharp Minima from SGD with Truncated Heavy-tailed Noise
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent