Robustness Analysis of Non-Convex Stochastic Gradient Descent using Biased Expectations

Kevin Scaman, Cédric MalherbeNeurIPS 2020 · OpenReview

Stochastic Gradient Descent (SGD) is the workhorse of modern machine learning, yet its remarkable resilience often defies traditional theoretical explanations. This paper provides a new mathematical lens for understanding why SGD continues to converge even when the "noise" in our gradients becomes extreme.

The Problem: Idealized Noise vs. Deep Learning Reality

Most theoretical analyses of SGD assume that gradient noise is well-behaved, typically requiring "bounded variance." In this idealized world, the noise lacks "heavy tails," meaning extreme, outlier-like gradient errors are vanishingly rare.

However, recent empirical research has shown that in Deep Learning—specifically in Natural Language Processing and Computer Vision—gradient noise is often heavy-tailed and can even exhibit infinite variance. Under these conditions, standard proofs of convergence fall apart. This creates a significant gap between the practical success of SGD on noisy, non-convex landscapes and our theoretical understanding of why the optimization process doesn't simply explode when it hits a massive noise spike.

Methods: Introducing Biased Expectations

To bridge this gap, the authors introduce a novel mathematical tool called Biased Expectations.

Think of a standard expectation as a simple average. A "biased expectation" (denoted as $\mu_s$) uses a distortion function to give more or less weight to the tails of a probability distribution.

  • When the parameter $s > 0$, it weights higher values more heavily, which is useful for analyzing sub-Gaussian noise.
  • When $s < 0$, it weights lower values more. This allows the authors to analyze distributions where the standard mean might be infinite, but the "bulk" of the probability mass still behaves predictably.
Distortion functions and resulting biased expectations for various probability distributions.

By applying this tool to the standard SGD update rule ($x_{t+1} = x_t - \eta G_t$), the authors derived a unified bound that works across multiple scenarios:

  1. Bounded/Deterministic noise: Recovering standard $O(1/T)$ convergence rates.
  2. Sub-Gaussian noise: Proving high-probability convergence rates of $O(\epsilon^{-2} \ln(1/\delta))$.
  3. Heavy-tailed noise: Proving that even if the expected error is infinite, the squared gradient norm still converges with high probability.

Experimental Validation

The authors validated their theoretical findings using the Airfoil Self-Noise Data Set from the UCI Machine Learning Repository. They performed ridge regression on this dataset and manually injected heavy-tailed noise (using a Student’s t-distribution with tail-index $b=1.5$) into the gradients to test the robustness theory.

Key Insights and Results

The introduction of biased expectations yields several critical insights for both theory and practice:

  • SGD is Naturally Robust: The paper mathematically confirms that SGD isn't easily disrupted by extreme noise. Even if a few iterations are derailed by a massive noise spike, the overall trajectory tends toward a stationary point. For heavy-tailed noise, the number of iterations to reach precision $\epsilon$ is $O(\epsilon^{-p} \delta^{-q})$ for $p, q > 2$. While slower than the sub-Gaussian case, it guarantees that convergence will happen.
  • The Logic of "Multi-start": The analysis explains why running the same optimization several times is a valid strategy. Since convergence is proven to happen with probability $1-\delta$, running multiple trials exponentially decreases the chance that all runs will be disrupted by heavy-tailed noise.
  • Optimal Step Sizes for Heavy Tails: For standard noise, practitioners typically use a step size $\eta \propto T^{-1/2}$. This paper shows that if your noise is heavy-tailed with tail-parameter $b$, the optimal step size is actually $\eta \propto T^{-1/b}$. This provides a concrete tuning knob for dealing with unstable training.
Empirical validation showing the average squared gradient norm convergence and biased expectation under heavy-tailed noise.

In their ridge regression tests, the biased expectation of the gradient norm aligned perfectly with theoretical predictions, and the $T^{-1/b}$ step-size schedule noticeably outperformed the standard $T^{-1/2}$ schedule in heavy-noise scenarios.

Limitations and Future Work

While this framework unifies several disparate proofs into a single analysis, it does have limitations:

  • Smoothness Assumption: The analysis assumes the objective function is smooth ($\beta$-Lipschitz gradients). It does not explicitly cover non-smooth landscapes, which are common in neural networks using activations like ReLU.
  • Complexity of Constants: The convergence bounds for heavy-tailed noise involve several constants that depend on specific tail behavior, which might be difficult for a practitioner to estimate on the fly.
  • Beyond Vanilla SGD: The paper focuses on standard SGD. Future work could extend this "biased expectation" framework to momentum-based optimizers like Adam or RMSProp, which dominate modern Deep Learning.

Summary updated

Abstract

This work proposes a novel analysis of stochastic gradient descent (SGD) for non-convex and smooth optimization. Our analysis sheds light on the impact of the probability distribution of the gradient noise on the convergence rate of the norm of the gradient. In the case of sub-Gaussian and centered noise, we prove that, with probability $1-\delta$, the number of iterations to reach a precision $\varepsilon$ for the squared gradient norm is $O(\varepsilon^{-2}\ln(1/\delta))$. In the case of centered and integrable heavy-tailed noise, we show that, while the expectation of the iterates may be infinite, the squared gradient norm still converges with probability $1-\delta$ in $O(\varepsilon^{-p}\delta^{-q})$ iterations, where $p,q &gt; 2$. This result shows that heavy-tailed noise on the gradient slows down the convergence of SGD without preventing it, proving that SGD is robust to gradient noise with unbounded variance, a setting of interest for Deep Learning. In addition, it indicates that choosing a step size proportional to $T^{-1/b}$ where $b$ is the tail-parameter of the noise and $T$ is the number of iterations leads to the best convergence rates. Both results are simple corollaries of a unified analysis using the novel concept of biased expectations, a simple and intuitive mathematical tool to obtain concentration inequalities. Using this concept, we propose a new quantity to measure the amount of noise added to the gradient, and discuss its value in multiple scenarios.
BibTeX
@inproceedings{scaman2020robustness,
  author = {Kevin Scaman and Cédric Malherbe},
  title = {{Robustness Analysis of Non-Convex Stochastic Gradient Descent using Biased Expectations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=xafrkYCMk27},
}
Figure