Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails

Ta Duy Nguyen, Alina Ene, Huy L. NguyênarXiv 2023 · DOI · arXiv

Abstract

In this work, we study the convergence in high probability of clipped gradient methods when the noise distribution has heavy tails, i.e., with bounded $p$-th moments, for some $1 < p \le 2$. We provide a novel "whitebox" analysis framework that avoids the sub-optimal logarithmic factors found in previous literature and allows for time-varying parameters when the total number of iterations is unknown. Our results achieve time-optimal convergence rates for convex, accelerated convex, and non-convex optimization problems.

Introduction

Stochastic Gradient Descent (SGD) is the workhorse of modern machine learning. However, its theoretical foundations often rely on the assumption of "light-tailed" noise, such as Gaussian distributions, where extreme outliers are statistically negligible. In practice, particularly in large-scale deep learning, gradient noise often exhibits "heavy-tailed" behavior where the variance may be infinite. In such environments, standard SGD fails to converge reliably.

To mitigate the impact of outliers, researchers employ gradient clipping, a technique that caps the magnitude of stochastic gradients. While the convergence of clipped methods "on average" (in expectation) is well-understood, proving that they work "with high probability" (e.g., $1 - \delta$) has remained a significant theoretical challenge. Previous analyses often suffered from sub-optimal $\log T$ factors and required the total number of iterations $T$ to be known in advance to set the clipping threshold. This paper introduces a tighter, more robust analysis framework that resolves these discrepancies.

The "Whitebox" Analysis Framework

The core contribution of this work is a shift from "black-box" concentration inequalities to a "whitebox" martingale approach. Traditionally, researchers apply standard inequalities (like Freedman’s inequality) at the end of a proof to bound the sum of errors. This paper instead delves into the underlying mechanics of the stochastic process.

Key Innovations:

  1. Supermartingale Construction: The authors construct a specific supermartingale sequence and bound its moment-generating function directly.
  2. History-Dependent Coefficients: Unlike prior work that used fixed coefficients ($z_t$) for the martingale, this framework utilizes coefficients that depend on the history of the algorithm's iterates. This allows the analysis to dynamically "absorb" errors as the optimization progresses.
  3. Algorithmic Versatility: This framework is applied across three major classes: Clipped Stochastic Mirror Descent (SMD) for convex problems, Clipped Accelerated SMD (ASMD) for faster convex convergence, and Clipped SGD for non-convex landscapes.

Theoretical Insights and Results

By analyzing the entire sequence as a single martingale rather than using a union bound over $T$ iterations, the authors eliminate the $\log T$ penalty. This makes the high-probability bounds as tight as the best-known "in expectation" bounds.

Optimal Convergence Rates

For noise with bounded $p$-th moments ($1 < p \le 2$), the paper establishes the following rates:

  • Convex Optimization: The convergence rate is $O(T^{ rac{1-p}{p}})$, matching the known theoretical lower bounds.
  • Non-convex Optimization: The rate is $O(T^{ rac{2-2p}{3p-2}})$, which is also time-optimal for this setting.
  • Acceleration and Interpolation: For accelerated methods, the analysis demonstrates an interpolation property. When noise is high, it matches the standard heavy-tail rate; as noise vanishes ($\sigma \to 0$), it recovers the $O(T^{-2})$ rate of deterministic accelerated gradient descent.

Practical Advantages

Beyond tighter bounds, the new analysis supports unknown horizons. Because it allows for time-varying step sizes ($\eta_t$) and clipping parameters ($\lambda_t$), the algorithm can be run indefinitely without needing to pre-specify the total number of iterations. Furthermore, for convex cases, the algorithm can be configured without precise knowledge of problem-specific constants like the initial distance to the optimum or the exact noise variance.

Limitations and Future Directions

While this work significantly advances the theory of robust optimization, several avenues for future research remain:

  • Non-Smooth Landscapes: The non-convex analysis currently requires the objective function to be $L$-smooth. Extending these high-probability results to non-smooth, non-convex problems is a remaining challenge.
  • Initialization Overhead: The mirror descent analysis requires a "good initial gradient estimate," which, while computable, adds a layer of complexity to the initialization phase.
  • Variational Inequalities: The authors suggest that the "whitebox" approach could be extended to variational inequalities, which are critical for understanding the stability of Generative Adversarial Networks (GANs).

Conclusion

This work provides the most refined high-probability analysis to date for clipped gradient methods under heavy-tailed noise. By removing the $\log T$ overhead and enabling parameter adaptivity, it bridges the gap between theoretical optimality and practical implementation in robust stochastic optimization.

Summary updated

Abstract

In this work, we study the convergence \emph{in high probability} of clipped gradient methods when the noise distribution has heavy tails, ie., with bounded $p$th moments, for some $1
BibTeX
@misc{nguyen2023improved,
  author = {Ta Duy Nguyen and Alina Ene and Huy L. Nguyên},
  title = {{Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails}},
  year = {2023},
  eprint = {2304.01119},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.01119},
}
Figure