First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise

Abstract

Stochastic gradient descent (SGD) has been widely used in machine learning due to its computational efficiency and favorable generalization properties. Recently, it has been empirically demonstrated that the gradient noise in several deep learning settings admits a non-Gaussian, heavy-tailed behavior. This suggests that the gradient noise can be modeled by using $\alpha$-stable distributions, a family of heavy-tailed distributions that appear in the generalized central limit theorem. In this context, SGD can be viewed as a discretization of a stochastic differential equation (SDE) driven by a Lévy motion, and the metastability results for this SDE can then be used for illuminating the behavior of SGD, especially in terms of `preferring wide minima'. While this approach brings a new perspective for analyzing SGD, it is limited in the sense that, due to the time discretization, SGD might admit a significantly different behavior than its continuous-time limit. Intuitively, the behaviors of these two systems are expected to be similar to each other only when the discretization step is sufficiently small; however, to the best of our knowledge, there is no theoretical understanding on how small the step-size should be chosen in order to guarantee that the discretized system inherits the properties of the continuous-time system. In this study, we provide formal theoretical analysis where we derive explicit conditions for the step-size such that the metastability behavior of the discrete-time system is similar to its continuous-time limit. We show that the behaviors of the two systems are indeed similar for small step-sizes and we identify how the error depends on the algorithm and problem parameters. We illustrate our results with simulations on a synthetic model and neural networks.

References in corpus (11)

• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Three Factors Influencing Minima in SGD
• Moments and Absolute Moments of the Normal Distribution
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Kramers' law: Validity, derivations and generalisations
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• First exit times of solutions of stochastic differential equations driven by multiplicative Levy noise with heavy tails
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization

Cited by in corpus (8)

• The Heavy-Tail Phenomenon in SGD
• A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)
• Mean first exit times of Ornstein-Uhlenbeck processes in high-dimensional spaces
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Small Noise Perturbations in Multidimensional Case