Technical Summary: Vanilla SGD with Momentum Survives Heavy-Tailed Noise

Problem Statement

Modern optimization relies heavily on Stochastic Gradient Descent (SGD) and its momentum-based variants. However, standard convergence analyses typically assume that stochastic noise possesses bounded variance (i.e., a finite second moment). Recent empirical evidence in deep learning and reinforcement learning suggests that stochastic noise often exhibits heavy-tailed distributions, where the variance may be unbounded, and only lower-order moments ($p \in (1, 2]$) are finite.

Under these heavy-tailed conditions, vanilla SGD is known to fail convergence. Consequently, the prevailing approach has been to employ specialized modifications such as gradient clipping or normalization to ensure stability. This paper investigates a fundamental question: Can vanilla SGD, specifically with momentum, converge under heavy-tailed noise without employing any gradient control mechanisms (clipping or normalization)?

Methodology

The authors propose a theoretical framework that shifts away from the standard $L$-smoothness assumption (which implies Lipschitz continuous gradients) and the bounded variance assumption. Instead, the analysis relies on two core assumptions:

1. Hölder Continuity of Gradients (Assumption 2.1): The gradient $\nabla f$ is assumed to be Hölder continuous with parameter $\nu \in (0, 1]$. This generalizes $L$-smoothness (where $\nu=1$) and allows for the use of a generalized descent lemma involving the term $\|y-x\|^{\nu+1}$ rather than $\|y-x\|^2$.
2. Bounded $p$-th Moment of Noise (Assumption 2.2): The stochastic noise is assumed to have a finite $p$-th moment for $p \in (1, 2]$, allowing for unbounded variance when $p < 2$.

Key Technical Tools:

• Generalized Descent Lemma: By utilizing the Hölder continuity, the authors derive an upper bound for the function decrease that depends on the $(\nu+1)$-th power of the step size and the gradient norm, rather than the squared norm.
• Moment Bounds: The analysis leverages inequalities (specifically Lemma 2.2 and Lemma 2.4) to bound the expectation of the $(\nu+1)$-th power of the stochastic gradient. A critical constraint derived is $\nu + 1 \le p$. This condition ensures that the moment bounds required for convergence are valid.
• Lyapunov Functions and Auxiliary Sequences: For the momentum case, the authors employ auxiliary sequences ($z_t$) and Lyapunov functions to decouple the momentum term from the gradient noise, facilitating the convergence proof for strongly convex, convex, and nonconvex objectives.

Key Contributions

The paper provides the first comprehensive convergence analysis for vanilla SGD with momentum under heavy-tailed noise without gradient clipping or normalization. The contributions are categorized by objective type:

1. Strongly Convex Functions:

   • Proves convergence in expectation for both vanilla SGD and vanilla SGD with momentum.
   • Establishes a convergence rate of $O(T^{-(p-1)})$ when $\nu + 1 = p$ for vanilla SGD.
   • For momentum, derives a rate of $O((1-\eta)^T + \eta^p)$, recovering classical results when $p=2$.

2. Convex Functions:

   • Establishes convergence in expectation for both variants.
   • Vanilla SGD achieves a rate of $O(\frac{\log T}{T^{(p-1)/p}})$.
   • Momentum-based SGD achieves $O(\frac{1}{\eta T} + \eta^{p-1})$.

3. Nonconvex Functions:

   • Proves convergence in expectation for the gradient norm $\mathbb{E}[\|\nabla f(x_t)\|]$.
   • Vanilla SGD achieves $O(\frac{\log T}{T^{(p-1)/p}})$.
   • Momentum-based SGD achieves $O(T^{-\frac{p-1}{2p}})$ when $p$ is known, and $O(T^{-\frac{p-1}{4}})$ when unknown.
   • Comparison: The authors note that while these rates are slightly inferior to those of normalized SGD with momentum (which achieves $O(T^{-\frac{p-1}{3p-2}})$), the results demonstrate that vanilla methods do not require explicit gradient control to converge, albeit at a slower rate.

Experimental Results

The theoretical findings are validated through experiments on synthetic functions and a real-world task:

• Synthetic Functions: The authors tested various combinations of the Hölder parameter $\nu$ and the tail index $\alpha$ (where $p < \alpha$).
  • Critical Condition: The experiments empirically confirm that the condition $\nu + 1 \le \alpha$ is necessary for stable convergence. When this condition is violated (i.e., in the upper-left region of the parameter space), the algorithm fails to converge.
  • Stability: Smaller values of $\nu$ (broader Hölder smoothness) allow for convergence under heavier tails (smaller $\alpha$), whereas standard $L$-smoothness ($\nu=1$) fails when $\alpha < 2$.
• WikiText-2 with Transformer-XL: Experiments on a language modeling task confirmed that vanilla SGD with momentum converges without clipping or normalization. However, normalized SGD with momentum achieved a lower loss faster, consistent with the theoretical finding that specialized methods offer superior rates.

Significance and Claims

The paper claims the following significance:

1. Fundamental Baseline: It establishes that vanilla SGD with momentum possesses inherent robustness against heavy-tailed noise, converging in expectation without the need for ad-hoc gradient control mechanisms like clipping or normalization. This provides a necessary theoretical baseline for understanding the limits of standard optimizers.
2. Theoretical Framework: By shifting from $L$-smoothness to Hölder smoothness, the paper offers a more general and realistic framework for analyzing stochastic optimization under heavy-tailed noise. It highlights the incompatibility between standard $L$-smoothness and strictly heavy-tailed noise ($p < 2$).
3. Inherent Limitations: While proving convergence, the results also reveal inherent limitations. The convergence rates of vanilla methods are sub-optimal compared to clipped or normalized variants, suggesting that while vanilla SGD survives heavy-tailed noise, specialized modifications are still required for optimal efficiency.
4. Condition $\nu + 1 \le p$: The work identifies this condition as a critical alignment between function smoothness and noise tail index, a finding supported by both theory and empirical observation.

In summary, the paper demonstrates that vanilla SGD with momentum is theoretically sound under heavy-tailed noise provided the function's smoothness and the noise's tail index satisfy specific constraints, challenging the notion that gradient control is strictly necessary for convergence, while simultaneously quantifying the performance cost of omitting such controls.