Multiplicative Noise and Heavy Tails in Stochastic Optimization

Liam Hodgkinson, Michael W. Mahoney

Introduction

Stochastic optimization is the workhorse of modern machine learning, yet the precise mechanisms underlying its success—particularly the role of stochasticity—remain partially understood. This paper demonstrates that the success of stochastic optimization in deep learning isn't just about generic "noise," but specifically multiplicative noise. By modeling optimizers as random recurrence relations, the authors show that this noise naturally creates "heavy-tailed" parameter distributions. These heavy tails are essential for hopping between basins and effectively exploring complex, non-convex loss landscapes.

The Limitations of Additive Noise Models

Traditional theory often treats the noise in Stochastic Gradient Descent (SGD) as a version of Gradient Descent with "additive Gaussian noise"—essentially, just a bit of static fuzz added to the signal. However, this simplified view fails to explain the "generalization gap" (why smaller batch sizes often lead to better models) or how optimizers manage to escape poor local minima in massive, high-dimensional spaces.

The authors argue that the noise in SGD is actually multiplicative, meaning the magnitude of the noise scales with the current state of the parameters. This property, they propose, is the secret sauce behind effective global exploration.

Methodological Approach

To capture these dynamics accurately, the authors move away from standard "continuous-time" approximations, which often smooth over critical discrete details. Instead, they model optimizers as discrete Markov random recurrence relations.

Key methodological contributions include:

  • Theoretical Universality: A rigorous proof (Theorem 1) showing that for a wide class of optimizers—including SGD, Adam, and Momentum—multiplicative noise leads to stationary distributions with power-law tails.
  • Tail Exponent Analysis: The characterization of the "tail exponent" ($\alpha$), where a smaller $\alpha$ indicates a "heavier" tail (i.e., more frequent large jumps in parameter space).
  • Comparative Simulations: An analysis comparing three distinct regimes—additive light-tailed noise, additive heavy-tailed noise, and multiplicative noise—to observe how each affects "basin hopping" in non-convex landscapes.

Key Insights and Ideas

Multiplicative Noise is Intrinsic

A major takeaway is that you do not need heavy-tailed data to produce heavy-tailed behavior. The structure of the optimization algorithm itself generates these tails because the local rate of convergence naturally varies across the data.

Basin Hopping vs. Smoothing

Additive noise tends to "smear" the loss landscape. While this makes it easier to move out of local minima, it loses resolution near the actual minima, preventing the optimizer from settling precisely. Multiplicative noise, on the other hand, allows for massive jumps (exploration) while still maintaining high "resolution" (exploitation) once the optimizer settles into a good basin.

Comparison of noise types on a non-convex objective across small, moderate, and strong noise regimes.

The Depth Connection

The research also uncovers a relationship between network architecture and optimization dynamics. As neural networks get deeper, the tail exponents of the SGD steps decrease. This means deeper models naturally exhibit heavier-tailed fluctuations, which may explain why they can be easier to optimize despite their immense complexity.

Empirical Validation

The paper validates its theoretical findings across multiple domains:

  • Synthetic 1D Objective: A non-convex function ($f(x) = \frac{1}{10}x^2 + 1 - \cos(x^2)$) was used to clearly visualize the differences between noise types and their basin-hopping capabilities.
  • Exploration Efficiency (Musk Dataset): Using a classification task with 168 attributes, PCA-projected trajectories showed that SGD exhibits frequent jumps between basins—a behavior that "perturbed GD" (GD with only additive noise) failed to replicate.
  • Empirical Validation of Depth (CIFAR-10): By training various Wide ResNet architectures (ResNet-9 to ResNet-68), the authors found that the tail exponent $\alpha$ dropped from ~6.1 for ResNet-9 to ~1.55 for ResNet-68, confirming that increased depth leads to heavier tails.

Limitations and Future Work

While this work provides a robust framework for understanding stochastic optimization, the authors note a few areas for future exploration:

  • Data Ordering: The current model assumes data is sampled i.i.d. (with replacement). In practice, ML practitioners usually cycle through data in fixed-order epochs, introducing a different dynamical structure not fully captured here.
  • Spectral vs. Probability Tails: This paper focuses on the probability distribution of the weights over time. Other prominent research focuses on the spectral distribution of the weight matrices. Unifying these two perspectives remains a major future goal.
  • Tighter Bounds: While the paper establishes the existence of power laws, the bounds on the tail exponents are currently broad. More specific analysis of different model architectures could lead to more precise predictions of generalization performance.

Summary updated

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. Modeling 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. Theoretical results are obtained characterizing this for a large class of (non-linear and even non-convex) models and optimizers (including momentum, Adam, and stochastic Newton), demonstrating that this phenomenon holds generally. 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. Furthermore, we empirically illustrate 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.
BibTeX
@inproceedings{hodgkinson2021multiplicative,
  author = {Liam Hodgkinson and Michael W. Mahoney},
  title = {{Multiplicative Noise and Heavy Tails in Stochastic Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=zr9dI21Nxj},
}
Figure