The Heavy-Tail Phenomenon in SGD

Abstract

In recent years, various notions of capacity and complexity have been proposed for characterizing the generalization properties of stochastic gradient descent (SGD) in deep learning. Some of the popular notions that correlate well with the performance on unseen data are (i) the `flatness' of the local minimum found by SGD, which is related to the eigenvalues of the Hessian, (ii) the ratio of the stepsize $\eta$ to the batch-size $b$, which essentially controls the magnitude of the stochastic gradient noise, and (iii) the `tail-index', which measures the heaviness of the tails of the network weights at convergence. In this paper, we argue that these three seemingly unrelated perspectives for generalization are deeply linked to each other. We claim that depending on the structure of the Hessian of the loss at the minimum, and the choices of the algorithm parameters $\eta$ and $b$, the SGD iterates will converge to a \emph{heavy-tailed} stationary distribution. We rigorously prove this claim in the setting of quadratic optimization: we show that even in a simple linear regression problem with independent and identically distributed data whose distribution has finite moments of all order, the iterates can be heavy-tailed with infinite variance. We further characterize the behavior of the tails with respect to algorithm parameters, the dimension, and the curvature. We then translate our results into insights about the behavior of SGD in deep learning. We support our theory with experiments conducted on synthetic data, fully connected, and convolutional neural networks.

References in corpus (10)

• Improving Generalization Performance by Switching from Adam to SGD
• The large learning rate phase of deep learning: the catapult mechanism
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Multiplicative noise and heavy tails in stochastic optimization
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Non-Gaussianity of Stochastic Gradient Noise
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• Matrix Concentration for Products
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise

Cited by in corpus (22)

• Multiplicative noise and heavy tails in stochastic optimization
• Bayesian Neural Network Priors Revisited
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Robust, Accurate Stochastic Optimization for Variational Inference
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• On the Distributional Properties of Adaptive Gradients
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds
• A Fully Spiking Hybrid Neural Network for Energy-Efficient Object Detection
• Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections
• Fractional moment-preserving initialization schemes for training deep neural networks
• Learning Curves for SGD on Structured Features
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Heavy-Tail Phenomenon in Decentralized SGD
• Good Classifiers are Abundant in the Interpolating Regime
• Eliminating Sharp Minima from SGD with Truncated Heavy-tailed Noise
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent