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.
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.
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