High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise

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

Abstract

While the convergence behaviors of stochastic gradient methods are well understood in expectation, significant gaps remain in our understanding of their convergence with high probability—specifically where the convergence rate has a logarithmic dependency on the success probability parameter. In heavy-tailed noise settings, where stochastic gradient noise only possesses bounded $p$-th moments for $p \in (1, 2]$, existing literature has largely been limited to bounds in expectation or high-probability bounds requiring restrictive assumptions. This paper introduces a novel inductive analysis framework to establish new, time-optimal high-probability convergence bounds for Clipped-SGD under heavy-tailed noise for both convex and non-convex smooth objectives using minimal assumptions.

Introduction

In stochastic optimization, the standard convergence proofs for Stochastic Gradient Descent (SGD) typically rely on the assumption that gradient noise is "light-tailed" (e.g., Gaussian) or possesses a bounded variance. However, empirical evidence from modern deep learning—particularly in training large-scale language models like BERT or complex convolutional networks—suggests that gradient noise is often heavy-tailed. In these scenarios, the variance may be extremely large or even infinite, causing standard SGD to diverge.

While gradient clipping is a common heuristic used to stabilize training, theoretical guarantees have primarily focused on convergence "on average" (in expectation). Proving high-probability convergence—ensuring a single run of the algorithm succeeds with a rate depending logarithmically on the failure probability—is much more challenging. Previous attempts to bridge this gap either restricted the noise to the $p=2$ (bounded variance) case or required "strong" assumptions, such as assuming the true gradients themselves are bounded, which excludes even simple quadratic functions.

The Clipped-SGD Framework

The authors analyze a variant of SGD known as Clipped-SGD. In this algorithm, the stochastic gradient $\hat{\nabla} f(x)$ is modified before the update step. If the norm of the gradient exceeds a threshold $\lambda$, it is scaled down:

$$\text{Update: } x_{t+1} = x_t - \eta \cdot \text{clip}(\hat{\nabla} f(x_t), \lambda)$$

This mechanism introduces a fundamental bias-variance trade-off. Clipping the gradient introduces bias (the clipped vector is no longer an unbiased estimator of the true gradient) but significantly reduces the variance by capping the impact of extreme noise events. The technical challenge lies in selecting a clipping threshold $\lambda$ and a step size $\eta$ that balance this trade-off effectively across the entire optimization trajectory.

A Novel Inductive Analysis

The core contribution of this work is a novel inductive analysis framework. Traditional high-probability proofs often struggle because they cannot guarantee that the iterates stay within a region where the gradients are well-behaved. The authors overcome this by using induction to show that, with high probability, the iterates remain within a controlled distance of the optimum (in the convex case) or maintain a controlled function value gap (in the non-convex case).

Key technical pillars of this framework include:

  • Freedman’s Inequality: A concentration inequality for martingales used to bound the cumulative error of the noisy gradients.
  • Surrogate Sequences: To satisfy the boundedness requirements of concentration inequalities, the authors construct "surrogate" sequences that are bounded by design. They then prove that these surrogates are identical to the actual SGD iterates with high probability.
  • Minimal Assumptions: Unlike prior work, this analysis only requires the noise to have a bounded $p$-th moment ($p \in (1, 2]$). It does not require the true gradients to be bounded, making the theory applicable to a much broader class of functions, including standard quadratic losses.

Key Results and Convergence Rates

The paper establishes high-probability convergence rates that match known lower bounds up to logarithmic factors, making them time-optimal. A critical feature of these results is the "logarithmic confidence"—the bounds depend on the failure rate $\delta$ only through $\log(1/\delta)$.

1. Convex Setting

For smooth convex objectives, the framework achieves a convergence rate of: $$O\left(T^{\frac{1-p}{p}}\right)$$ This result generalizes previous findings that were limited to the $p=2$ case, providing a robust guarantee for any heavy-tailed distribution with a $p$-th moment.

2. Non-Convex Setting

For smooth non-convex objectives, the authors establish a rate of: $$O\left(T^{\frac{2-2p}{3p-2}}\right)$$ This represents the first high-probability bound for non-convex optimization under such minimal noise assumptions. The analysis reveals that in the non-convex setting, the squared norm of the gradient can effectively "absorb" some estimation error, leading to a distinct convergence profile compared to the convex case.

Discussion and Future Directions

This work provides a rigorous theoretical foundation for the success of gradient clipping in the presence of heavy-tailed noise. By moving beyond "in expectation" analysis, it offers guarantees that are more relevant to practitioners who require reliability in individual training runs.

However, several avenues for future research remain. The current theory requires prior knowledge of problem parameters (such as the initial distance to the optimum) to tune the clipping threshold $\lambda$. Future work could explore adaptive clipping mechanisms that do not require such tuning. Additionally, extending this inductive framework to accelerated gradient methods or momentum-based optimizers like Adam—which features implicit normalization—could further bridge the gap between theory and the state-of-the-art in deep learning.

Summary updated

Abstract

While the convergence behaviors of stochastic gradient methods are well understood \emph{in expectation}, there still exist many gaps in the understanding of their convergence with \emph{high probability}, where the convergence rate has a logarithmic dependency on the desired success probability parameter. In the \emph{heavy-tailed noise} setting, where the stochastic gradient noise only has bounded $p$-th moments for some $p\in(1,2]$, existing works could only show bounds \emph{in expectation} for a variant of stochastic gradient descent (SGD) with clipped gradients, or high probability bounds in special cases (such as $p=2$) or with extra assumptions (such as the stochastic gradients having bounded non-central moments). In this work, using a novel analysis framework, we present new and time-optimal (up to logarithmic factors) \emph{high probability} convergence bounds for SGD with clipping under heavy-tailed noise for both convex and non-convex smooth objectives using only minimal assumptions.
BibTeX
@misc{nguyen2023high,
  author = {Ta Duy Nguyen and Thien Hang Nguyen and Alina Ene and Huy L. Nguyên},
  title = {{High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise}},
  year = {2023},
  eprint = {2302.05437},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.05437},
}
Figure