Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo

Deep learning models often generalize remarkably well, even when the training process is chaotic. Standard optimization theory typically assumes that stochastic gradient noise is "nice"—following a neat bell curve with bounded variance. However, empirical evidence from training deep neural networks and reinforcement learning agents suggests that gradient noise is often "heavy-tailed." In practice, this means the training process is frequently buffeted by extreme, unpredictable gradient outliers that would break standard mathematical proofs.

While researchers have developed robust algorithms—such as gradient clipping and normalization—to ensure models converge under these wild conditions, a critical gap has remained: how do these heavy-tailed conditions affect generalization? If a model is trained amidst extreme noise, does it become less stable and more prone to overfitting? This paper provides the first systematic theoretical framework to answer that question, bridging a significant gap between optimization theory and real-world deep learning behavior.

A New Theoretical Framework: Stability and Truncation

To understand generalization under extreme noise, the authors build their framework on the concept of algorithmic stability. The core principle is intuitive: if changing a single sample in the training dataset doesn't significantly alter the final model, the model is considered "stable" and is highly likely to generalize well to unseen data.

To apply stability bounds to heavy-tailed noise, the authors introduce a novel truncation argument:

  1. Decomposition: They mathematically split the stochastic gradient noise into two distinct parts: a "truncated" portion (where gradients are capped at a specific threshold) and a "residual tail" (the rare, extreme outliers).
  2. Bounded $p$-th Moment ($p$-BCM): Instead of relying on the standard assumption of finite variance (which requires the second moment, $p=2$, to be bounded), they assume a much weaker condition. They require only that the $p$-th moment is finite for $p \in (1, 2]$. This mathematically accommodates much "messier" and more realistic noise.
  3. Threshold Optimization: The authors mathematically determine the optimal truncation threshold that perfectly balances the stability gained from the truncated portion against the bias introduced by ignoring the extreme tail.

Key Insights: How Algorithms Cope

The authors apply this framework to several popular robust algorithms, including Clipped SGD and Normalized SGD (NSGD), yielding several striking insights into how these methods handle extreme noise.

  • Normalization is a Natural Defense: One of the most fascinating takeaways is that for Normalized SGD, heavy-tailed noise does not negatively impact the stability bound. Because NSGD relies solely on the direction of the gradient and completely ignores its magnitude, it is inherently shielded from the "heaviness" of the extreme outliers.
  • The $p$ Trade-off: The generalization error bound is shown to scale as $\mathcal{O}(n^{-\frac{p-1}{p}})$. This reveals a clear "difficulty scale" for machine learning models. As $p$ approaches 1 (indicating heavier, wilder tails), generalization becomes significantly slower and harder to guarantee. Conversely, when $p=2$, the framework perfectly recovers existing standard variance bounds.
  • Momentum and Mini-batching as Stabilizers: Using a 1D toy example, the authors demonstrate why vanilla Normalized SGD can oscillate and fail to converge. Crucially, they prove that adding momentum or using larger mini-batches aren't just engineering tricks for faster training—they fundamentally improve the stability and generalization of the model under heavy-tailed conditions.

Main Results and Theoretical Bounds

The paper establishes a rigorous new generalization bound for nonconvex problems under the $p$-BCM assumption:

$$4\epsilon + C_p \sigma_p n^{-\frac{p-1}{p}}$$

where $\epsilon$ represents the stability parameter.

When comparing algorithms, the theoretical analysis proves that Normalized SGD (when equipped with mini-batching or momentum) achieves sharper population risk bounds than Clipped SGD. The results are highly consistent, matching state-of-the-art bounds for the "nice" $p=2$ case while providing the first-ever rigorous bounds for the challenging $1 < p < 2$ regime.

Limitations and Future Directions

As a foundational theoretical paper, the work relies on mathematical proofs rather than large-scale empirical benchmarks like ImageNet. The authors note several important avenues for future research:

  • The Smoothness Assumption: The current analysis assumes the loss function is "L-smooth" (meaning its slope doesn't change too abruptly). Because real-world architectures like ReLU networks are often non-smooth, extending this framework to the non-smooth regime is a critical next step.
  • High-Probability Bounds: The current results hold "in expectation" (on average across runs). Deriving "high-probability" bounds that guarantee performance for almost every individual training run remains a challenging but necessary direction.
  • Theoretical Lower Bounds: While the authors provide upper bounds on error, they have not yet proven that these are the best possible bounds (lower bounds). Establishing these would confirm the absolute mathematical limits of learning under heavy-tailed noise.

Summary updated

Abstract

The empirical evidence indicates that stochastic optimization with heavy-tailed gradient noise is more appropriate to characterize the training of machine learning models than that with standard bounded gradient variance noise. Most existing works on this phenomenon focus on the convergence of optimization errors, while the analysis for generalization bounds under the heavy-tailed gradient noise remains limited. In this paper, we develop a general framework for establishing generalization bounds under heavy-tailed noise. Specifically, we introduce a truncation argument to achieve the generalization error bound based on the algorithmic stability under the assumption of bounded $p$th centered moment with $p\in(1,2]$. Building on this framework, we further provide the stability and generalization analysis for several popular stochastic algorithms under heavy-tailed noise, including clipped and normalized stochastic gradient descent, as well as their mini-batch and momentum variants.
BibTeX
@inproceedings{chen2026stability,
  author = {Hongxu Chen and Ke Wei and Xiaoming Yuan and Luo Luo},
  title = {{Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=jHUEoBLQpn},
}
Figure