Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise

Abstract

Stochastic gradient descent with momentum (SGDm) is one of the most popular optimization algorithms in deep learning. While there is a rich theory of SGDm for convex problems, the theory is considerably less developed in the context of deep learning where the problem is non-convex and the gradient noise might exhibit a heavy-tailed behavior, as empirically observed in recent studies. In this study, we consider a \emph{continuous-time} variant of SGDm, known as the underdamped Langevin dynamics (ULD), and investigate its asymptotic properties under heavy-tailed perturbations. Supported by recent studies from statistical physics, we argue both theoretically and empirically that the heavy-tails of such perturbations can result in a bias even when the step-size is small, in the sense that \emph{the optima of stationary distribution} of the dynamics might not match \emph{the optima of the cost function to be optimized}. As a remedy, we develop a novel framework, which we coin as \emph{fractional} ULD (FULD), and prove that FULD targets the so-called Gibbs distribution, whose optima exactly match the optima of the original cost. We observe that the Euler discretization of FULD has noteworthy algorithmic similarities with \emph{natural gradient} methods and \emph{gradient clipping}, bringing a new perspective on understanding their role in deep learning. We support our theory with experiments conducted on a synthetic model and neural networks.

arXiv comment20 pages, Published at International Conference on Machine Learning 2020

References in corpus (17)

• On the difficulty of training Recurrent Neural Networks
• Don't Decay the Learning Rate, Increase the Batch Size
• Levy Flight Superdiffusion: An Introduction
• Three Factors Influencing Minima in SGD
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• The Heavy-Tail Phenomenon in SGD
• Hamiltonian Descent Methods
• Multiplicative noise and heavy tails in stochastic optimization
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• 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
• Accurate and efficient numerical calculation of stable densities via optimized quadrature and asymptotics
• Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
• Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Stationary States in Bistable System Driven by Lévy Noise

Cited by in corpus (9)

• Multiplicative noise and heavy tails in stochastic optimization
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Generalized Energy Based Models
• Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks
• Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections
• On Proximal Policy Optimization's Heavy-tailed Gradients
• On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control
• Approximation of heavy-tailed distributions via stable-driven SDEs
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD