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

Zhiyuan Li, Sadhika Malladi, Sanjeev Arora

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 Ito Stochastic Differential Equations (SDEs), but formal justification for this approximation 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 Ito SDE approximation. (b) A theoretically motivated testable necessary condition for the SDE approximation and its most famous implication, the linear scaling rule, 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.

Introduction

In deep learning, the choice of learning rate (LR) is pivotal for generalization. To analyze the dynamics of Stochastic Gradient Descent (SGD), researchers often model its discrete steps as a continuous-time process using Itô Stochastic Differential Equations (SDEs). However, a significant gap exists: formal proofs for this approximation typically assume infinitesimally small learning rates, whereas practical applications rely on large LRs. Furthermore, verifying this approximation experimentally has been historically difficult due to the massive computational overhead of standard SDE simulation techniques like Euler-Maruyama, which require calculating full gradients and noise covariance matrices at every step.

This paper addresses three core questions:

  1. Can we efficiently simulate the SDEs used to model SGD?
  2. Does the SDE approximation hold in realistic training regimes?
  3. Why does the Linear Scaling Rule (LSR)—the practice of scaling LR proportionally with batch size—eventually break down?

Methodology: The SVAG Algorithm

The authors introduce Stochastic Variance Amplified Gradient (SVAG), a novel numerical method designed to bridge the gap between discrete SGD and continuous SDEs. SVAG simulates the SDE by taking a linear combination of two independently sampled batch gradients. This approach amplifies the noise variance while maintaining the expected gradient.

Comparison of SDE, SVAG, and SGD trajectories.

As the hyperparameter $l$ increases, the SVAG trajectory converges to the Itô SDE. This makes experimental verification of SDE-based theories computationally tractable for deep neural networks, allowing researchers to interpolate between discrete SGD ($l=1$) and continuous SDE ($l \to \infty$).

The Noise-Signal-Ratio (NSR) Condition

A key theoretical contribution is the derivation of a necessary condition for the validity of the SDE approximation. This condition is based on the Noise-Signal-Ratio (NSR). For an SDE to accurately represent SGD at equilibrium, the norm of the gradient must be significantly smaller than its variance.

This NSR condition provides a theoretical foundation for predicting the "critical batch size." Beyond this size, discretization errors become dominant, causing the discrete SGD trajectory to drift away from the continuous SDE path. This drift explains why the Linear Scaling Rule (LSR) eventually fails, leading to a degradation in generalization.

Experimental Results

The theories were validated using standard benchmarks (CIFAR-10, CIFAR-100, SVHN) with scale-invariant architectures like PreResNet-32 and VGG-19 (utilizing Batch or Group Normalization).

LSR Failure Prediction

The authors' formula for the critical batch size accurately predicted the point at which generalization performance drops. As shown in the figures below, once the batch size enters the "red zone" (determined by the NSR condition), there is a sharp spike in both training and test error.

Experimental validation of the critical batch size.

The Role of Noise

A surprising finding was that the specific distribution of noise is less important than its covariance. Replacing SGD's inherent noise with simple Gaussian noise (Noisy Gradient Descent) resulted in nearly identical test accuracy (~89% on CIFAR-10), whereas standard Gradient Descent without noise performed significantly worse (~75%). This suggests that the Itô SDE's reliance on Gaussian noise is a sufficient approximation for capturing generalization properties.

Conclusion and Future Work

This work clarifies the relationship between SGD and SDEs, providing both a simulation tool (SVAG) and a theoretical framework (NSR) to understand the limits of continuous-time modeling. While the results are robust for scale-invariant vision models, future work is needed to explore domains like NLP, where heavy-tailed noise might necessitate more complex SDE approximations. Additionally, the current analysis assumes the system reaches a steady-state equilibrium, which may not always hold in very short training runs.

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