Traditional optimization theory relies on a comforting assumption: when we sample a mini-batch of data to calculate a stochastic gradient, the noise surrounding that estimate is well-behaved. Specifically, standard proofs assume that gradient noise is light-tailed (such as a sub-Gaussian distribution) and possesses a uniformly bounded variance. Under this assumption, the sample mean of a mini-batch is a highly reliable indicator of the true gradient direction, allowing Stochastic Gradient Descent (SGD) to smoothly slide down the loss landscape.
However, modern deep learning has broken this assumption. In large language models, attention-based architectures, and complex distributed systems, gradients frequently exhibit heavy-tailed noise characterized by extreme, spiky outliers.
To design optimizers that do not collapse in these environments, we must understand why the sample mean fails and how alternative geometric mechanisms can restore stability.
The Fragility of the Sample Mean
When gradient noise is heavy-tailed, extreme outliers occur far more frequently than a Gaussian distribution would ever predict. In mathematical terms, the variance of the gradient distribution can become effectively infinite; only lower-order fractional moments (such as the $p$-th moment for some $1 < p \le 2$) remain finite.
As Nguyen et al. note, this phenomenon is highly prevalent in modern attention models. When variance is infinite, the Law of Large Numbers no longer guarantees that the sample mean will rapidly concentrate around the true mean. Instead, taking the average of a mini-batch leaves the optimizer highly vulnerable to outliers.
Imagine calculating a mini-batch gradient where nine samples suggest moving slightly left, but a single heavy-tailed outlier sample points violently to the right. Because standard SGD relies on the sample mean, that single outlier will dominate the calculation. The resulting update step will be massive, catastrophically displacing the model's weights and causing the optimizer to oscillate wildly or diverge entirely, as highlighted by Gorbunov et al..
Standard Mean-Based Update (Fragile):
[Small Gradient] + [Small Gradient] + [EXPLOSIVE OUTLIER] ---> [Massive, Destructive Step]
Robust Median-Based Update (Stable):
[Small Gradient] + [Small Gradient] + [EXPLOSIVE OUTLIER] ---> [Controlled, Stable Step]
To counter this sensitivity, researchers have shifted away from simple sample means toward robust estimators. For instance, Holland et al. propose replacing the sample mean with coordinate-wise M-estimators to protect the gradient step from extreme values.
Shifting from Mean to Median via Gradient Clipping
The most common empirical remedy for exploding gradients in deep learning is gradient clipping, which caps a gradient's norm if it exceeds a chosen threshold. While long treated as a heuristic trick, recent theory reveals a profound mathematical justification for why clipping tames heavy tails.
Schaipp et al. demonstrate that gradient clipping can be formally viewed through the lens of a Stochastic Proximal Point method as a way of tracking the median of the gradients rather than their mean.
Why does this matter? The median is inherently robust to heavy tails. If an outlier is infinitely large, it still only counts as a single vote "above the threshold" when computing a median. By bounding the influence of any single gradient spike, clipping effectively converts an infinite-variance problem into a well-behaved, bounded-variance problem.
This insight allows theoreticians to discard sub-Gaussian assumptions entirely. By utilizing gradient clipping, Sadiev et al. derived optimal high-confidence complexity bounds for stochastic optimization and variational inequalities under unbounded variance, proving that stable convergence paths can be guaranteed solely by assuming finite fractional moments.
Changing the Geometry via Gradient Normalization
While gradient clipping is highly effective, it introduces a frustrating practical challenge: choosing and tuning the clipping threshold hyperparameter. If the threshold is too high, explosive outliers still destabilize training; if it is too low, valid gradient information is zeroed out.
An alternative approach alters the geometry of the optimization step entirely through Gradient Normalization. Instead of thresholding gradients based on an arbitrary constant, Normalized SGD (NSGD) divides each gradient update by its own magnitude, forcing every step to have a uniform length.
Zijian Liu challenges the assumption that manual gradient clipping is the only path to optimality, proving that Batched Normalized SGD with Momentum (NSGDM) achieves optimal convergence rates under heavy-tailed noise without any explicit clipping thresholds.
The intuition behind normalization is geometric. When a heavy-tailed distribution produces an enormous gradient spike, a standard optimizer scales the step size proportionally to that spike. NSGD, by contrast, strips away the magnitude and only preserves the direction of the update. As Hübler et al. demonstrate, this geometric adjustment naturally neutralizes the explosive power of heavy-tailed outliers, offering a simpler, parameter-free alternative that achieves optimal sample complexity.