On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)

Zhiyuan Li, Sadhika Malladi, Sanjeev Arora

Introduction

Stochastic Gradient Descent (SGD) is widely considered the "secret sauce" behind the generalization capabilities of deep learning. However, its discrete, noisy steps make it notoriously difficult to analyze mathematically. To simplify this, researchers often approximate SGD as a continuous-time process using Stochastic Differential Equations (SDEs).

While this approximation is mathematically convenient, existing proofs only hold when the learning rate (LR) is infinitesimally small. In practice, deep neural networks are trained with the largest learning rates possible to achieve better generalization. This creates a significant "validity gap." If the SDE model is inaccurate for practical learning rates, foundational theories built upon it—such as the Linear Scaling Rule (LSR), which suggests learning rates can scale linearly with batch size—may be flawed.

This paper investigates whether modeling the discrete steps of SGD as a continuous SDE is actually valid for realistic deep learning scenarios, introducing new algorithms and theoretical conditions to bridge the gap.

Methods: Bridging the Validity Gap

To rigorously test the SDE approximation, the authors introduce three main contributions:

  1. SVAG (Stochastic Variance Amplified Gradient): The authors propose a novel discrete algorithm that acts as a bridge between SGD and SDEs. By taking a linear combination of gradients from two independent batches, SVAG amplifies the noise covariance by a factor of $l$ while keeping the expected gradient identical. As $l$ increases, SVAG's trajectory provably converges to the commonly used "Itô SDE" approximation.
Trajectory comparison of SDE, SVAG, and SGD
  1. Theoretical Necessary Conditions: Focusing on "scale-invariant" networks (e.g., those using BatchNorm or GroupNorm), the authors derive a testable condition for when the SDE approximation holds. They define "C-closeness," a metric measuring how well the SDE matches SGD in terms of weight norms, gradient norms, and noise covariance.
  2. LSR Failure Prediction: They develop a method to predict the "critical batch size"—the exact point where the Linear Scaling Rule breaks down—using data from just a single small-batch training run.

Key Insights and Results

The paper validates its findings using standard computer vision benchmarks like CIFAR-10, employing scale-invariant PreResNet-32 and VGG-19 architectures.

The "Shape" of Noise Doesn't Matter

A long-standing debate in machine learning is whether SGD's success stems from the specific "heavy-tailed" nature of its noise. This paper provides compelling evidence that non-Gaussian noise is not essential.

Train and Test Accuracy for GD, SGD, and NGD

Experiments demonstrate that "Noisy Gradient Descent" (NGD)—which uses simple Gaussian noise with matching covariance—performs almost identically to SGD. On CIFAR-10, SGD achieved 89.4% accuracy and NGD achieved 89.3%, while standard Gradient Descent (GD without noise) lagged significantly behind at 75.5%. This suggests the covariance (the second moment) is the primary driver of generalization, rather than the exact distribution shape.

The Noise-to-Signal Ratio (NSR) is the Gatekeeper

The SDE approximation is only valid if the learning rate is small compared to the Noise-to-Signal Ratio (NSR). If the learning rate is too high, the discrete "jumps" of SGD become too large for a continuous SDE to track accurately.

Practitioners often find that the Linear Scaling Rule fails at very large batch sizes. The authors explain that at large batch sizes, the NSR drops, making the "discretization error" dominant. Their theoretical condition successfully predicted this failure point empirically; for a specific PreResNet-32 setup, they correctly predicted the LSR would break around a batch size of 1024.

Limitations and Future Work

While the paper provides a robust framework for understanding SGD through SDEs, it has limitations. The most rigorous theoretical results apply specifically to scale-invariant networks. Architectures without normalization layers may require adjustments to the theory. Furthermore, the analysis assumes the network reaches a statistical "equilibrium" during training, which may not fully capture the initial transition phases.

Interestingly, the authors note that higher-order SDE approximations might not improve generalization. This suggests that the "failure" of the SDE model at high learning rates might actually be a feature—rather than a bug—of why SGD generalizes so well. Exploring this "beneficial failure" remains a promising direction for future research.

Summary updated

Abstract

It is generally recognized that finite learning rate (LR), in contrast to infinitesimal LR, is important for good generalization in real-life deep nets. Most attempted explanations propose approximating finite-LR SGD with Itô Stochastic Differential Equations (SDEs), but formal justification for this approximation (e.g., Li et al., 2019) only applies to SGD with tiny LR. Experimental verification of the approximation appears computationally infeasible. The current paper clarifies the picture with the following contributions: (a) An efficient simulation algorithm SVAG that provably converges to the conventionally used Itô SDE approximation. (b) A theoretically motivated testable necessary condition for the SDE approximation and its most famous implication, the linear scaling rule (Goyal et al., 2017), to hold.(c) Experiments using this simulation to demonstrate that the previously proposed SDE approximation can meaningfully capture the training and generalization properties of common deep nets.
BibTeX
@inproceedings{li2021validity,
  author = {Zhiyuan Li and Sadhika Malladi and Sanjeev Arora},
  title = {{On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=lIxuI53syEo},
}
Figure