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

Umut Simsekli, Lingjiong Zhu, Yee Whye Teh, Mert Gürbüzbalaban

Introduction

Stochastic Gradient Descent with Momentum (SGDm) is the workhorse of deep learning optimization. Traditionally, theoretical analyses of SGDm rely on the assumption that gradient noise follows a Gaussian distribution. However, recent empirical studies suggest that gradient noise in deep neural networks is often heavy-tailed, characterized by frequent large "jumps." This paper, presented at ICML 2020, introduces Fractional Underdamped Langevin Dynamics (FULD) to address the bias introduced by such noise, providing a framework to "retarget" the optimizer toward the true global minima.

The Problem of Heavy-Tailed Noise

In the framework of Underdamped Langevin Dynamics (ULD), optimization is modeled as a particle moving through a potential field (the loss landscape) subject to friction and random fluctuations. When these fluctuations are Gaussian, the system eventually settles into a Gibbs distribution centered at the loss minima.

However, when the noise is heavy-tailed—modeled by $\alpha$-stable Lévy motion—the standard ULD equations fail. Large jumps in velocity can "hurl" the parameters far from local minima, creating a persistent bias where the stationary distribution of the optimizer no longer aligns with the minima of the cost function.

Heavy-tailed distributions $p(x)$ and their corresponding Lévy process trajectories $L_t^\alpha$ for different tail indices $\alpha$. As $\alpha$ decreases, the tails become heavier and the trajectories exhibit more frequent large jumps.

Fractional Underdamped Langevin Dynamics (FULD)

To correct this bias, the authors propose FULD. The core innovation is a "retargeting" mechanism that modifies the system's kinetic energy. By replacing standard Brownian motion with $\alpha$-stable Lévy motion and deriving a specific drift function $c(v, \alpha)$, the authors ensure that the stationary distribution remains the desired Gibbs distribution $e^{-\beta f(x)}$.

The choice of kinetic energy is crucial. While Gaussian kinetic energy ($\frac{1}{2}v^2$) leads to instability under heavy tails, the authors propose an $\alpha$-stable kinetic energy. This formulation leads to a stable discretization that can be implemented as a practical optimization algorithm.

The drift function $c(v, \alpha)$ and the gradient of the $\alpha$-stable kinetic energy $\partial_v G_\alpha(v)$. The saturation of the gradient for large velocities provides a theoretical basis for implicit gradient clipping.

Theoretical Insights: Clipping and Natural Gradients

The FULD framework reveals deep connections between heavy-tailed noise and common deep learning heuristics:

  • Implicit Gradient Clipping: As shown in the figures above, the gradient of the $\alpha$-stable kinetic energy vanishes as velocity increases. This means the algorithm naturally "tames" extreme updates, effectively performing gradient clipping as a direct consequence of the physics of heavy-tailed noise.
  • Natural Gradient Connection: For the specific case of Cauchy noise ($\alpha=1$), the FULD update rule resembles a Natural Gradient update pre-conditioned by the diagonal part of the Fisher Information Matrix. This suggests that natural gradient methods may implicitly account for heavy-tailed gradient noise.

Experimental Results

The authors validated FULD across synthetic and real-world benchmarks:

  • Synthetic Quartic Potential: FULD successfully captured the target distribution in a 1D non-convex landscape where standard heavy-tailed SGDm failed.
  • Image Classification: On MNIST and CIFAR10, FULD with $\alpha < 2$ (specifically $\alpha = 1.75$) consistently outperformed standard SGDm. On CIFAR10, FULD achieved up to a 4.5% improvement in accuracy for certain architectures, demonstrating superior stability and convergence.

Conclusion

FULD provides a robust mathematical foundation for understanding and optimizing deep networks under heavy-tailed gradient noise. By retargeting the dynamics of momentum-based optimizers, it bridges the gap between theoretical physics and practical deep learning, offering a principled explanation for the effectiveness of techniques like gradient clipping.

Summary updated

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.
BibTeX
@inproceedings{simsekli2020fractional,
  author = {Umut Simsekli and Lingjiong Zhu and Yee Whye Teh and Mert Gürbüzbalaban},
  title = {{Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=n2WYuKPRUsJ},
}
Figure