Multiplicative noise and heavy tails in stochastic optimization

Abstract

Although stochastic optimization is central to modern machine learning, the precise mechanisms underlying its success, and in particular, the precise role of the stochasticity, still remain unclear. Modelling stochastic optimization algorithms as discrete random recurrence relations, we show that multiplicative noise, as it commonly arises due to variance in local rates of convergence, results in heavy-tailed stationary behaviour in the parameters. A detailed analysis is conducted for SGD applied to a simple linear regression problem, followed by theoretical results for a much larger class of models (including non-linear and non-convex) and optimizers (including momentum, Adam, and stochastic Newton), demonstrating that our qualitative results hold much more generally. In each case, we describe dependence on key factors, including step size, batch size, and data variability, all of which exhibit similar qualitative behavior to recent empirical results on state-of-the-art neural network models from computer vision and natural language processing. Furthermore, we empirically demonstrate how multiplicative noise and heavy-tailed structure improve capacity for basin hopping and exploration of non-convex loss surfaces, over commonly-considered stochastic dynamics with only additive noise and light-tailed structure.

30 pages, 7 figures

References in corpus (24)

• MobileNetV2: Inverted Residuals and Linear Bottlenecks
• A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decay
• On Lazy Training in Differentiable Programming
• A Complete Recipe for Stochastic Gradient MCMC
• Extreme deviations and applications
• Power-law tails from multiplicative noise
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• Sub-Sampled Newton Methods II: Local Convergence Rates
• A Variational Analysis of Stochastic Gradient Algorithms
• Traditional and Heavy-Tailed Self Regularization in Neural Network Models
• The Heavy-Tail Phenomenon in SGD
• SGD: General Analysis and Improved Rates
• Bad Global Minima Exist and SGD Can Reach Them
• Budgeted Training: Rethinking Deep Neural Network Training Under Resource Constraints
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Non-Gaussianity of Stochastic Gradient Noise
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Mapping multiplicative to additive noise
• Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
• On the stationary tail index of iterated random Lipschitz functions
• Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions

Cited by in corpus (17)

• Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data
• 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
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• Strength of Minibatch Noise in SGD
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks
• Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds
• Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections
• Heavy-Tail Phenomenon in Decentralized SGD
• Good Classifiers are Abundant in the Interpolating Regime
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
• Eliminating Sharp Minima from SGD with Truncated Heavy-tailed Noise