Abstract
This paper investigates the roles of gradient normalization and clipping in ensuring the convergence of Stochastic Gradient Descent (SGD) under heavy-tailed noise. While existing approaches consider gradient clipping indispensable for SGD convergence, we theoretically demonstrate that gradient normalization alone without clipping is sufficient to ensure convergence. Furthermore, we establish that combining gradient normalization with clipping offers significantly improved convergence rates compared to using either technique in isolation, notably as gradient noise diminishes. With these results, our work provides the first theoretical evidence demonstrating the benefits of gradient normalization in SGD under heavy-tailed noise. Finally, we introduce an accelerated SGD variant incorporating gradient normalization and clipping, further enhancing convergence rates under heavy-tailed noise.
Introduction
In the idealized world of optimization theory, gradient noise is often assumed to have bounded variance. However, in practical deep learning—particularly when training Large Language Models (LLMs)—noise is frequently "heavy-tailed," meaning extreme outlier gradients are common. Under these conditions, standard SGD often fails to converge.
Historically, the community has viewed gradient clipping (capping the gradient magnitude) as the essential safeguard against these heavy-tailed spikes. This research challenges that assumption by asking whether gradient normalization (scaling the gradient to a fixed length) can achieve convergence independently or if combining the two techniques provides a mathematical synergy that outperforms either in isolation.
Methodology: Mechanisms of Gradient Control
The authors analyze several algorithmic variants to provide a unifying theory of robust optimization:
- Normalized SGD (NSGD): The study demonstrates that simply dividing the momentum-based gradient by its norm is sufficient to guarantee convergence, provided the individual functions in the stochastic objective are smooth (Individual Lipschitzness).
- Normalized SGD with Clipping (NSGDC): By revisiting the combination of both techniques, the authors eliminate the "logarithmic factors" that typically clutter convergence rates, proving this combination is theoretically optimal.
- NSGD-VR: A variance-reduced version of normalized SGD designed to handle heavy-tailed noise while maintaining the efficiency of state-of-the-art methods like STORM.
- Accelerated NSGDC (A-NSGDC): A novel variant using two momentum terms designed for functions with second-order smoothness (Lipschitz Hessians). This represents the first time an accelerated rate has been proven for non-convex optimization under heavy-tailed noise.
Theoretical Results and Comparative Analysis
A primary contribution of this work is the establishment of a comprehensive "speed limit" map for these algorithms, comparing them against existing state-of-the-art (SOTA) methods.
As detailed in the table above, the proposed NSGDC (Theorem 3) achieves a convergence rate of $\mathcal{O}(T^{-\frac{p-1}{3p-2}})$, where $p \in (1, 2]$ describes the "heaviness" of the noise tails. This rate matches the known theoretical lower bound for this class of problems. Notably, the analysis shows that NSGDC significantly outperforms standard clipping-only SGD (SGDC), with the performance gap widening as the noise level diminishes.
Crucially, these results are independent of mini-batch size. While many recent theories require massive mini-batches for stability, this paper proves these algorithms work even with a mini-batch size of one, which is often linked to better generalization in deep learning practice.
Key Insights
- Normalization as a Safety Valve: Normalization acts as a natural stabilizer. Because the update step size is effectively capped, a single massive heavy-tailed gradient spike cannot displace the model parameters into divergence.
- Tightness and Recovery: The theory is "tight"; if the noise level is set to zero, the formulas perfectly recover the standard convergence rates for deterministic Gradient Descent, suggesting the analysis captures the true underlying physics of the algorithm.
- Acceleration Boost: Under second-order smoothness, the new A-NSGDC algorithm converges at a rate of $\mathcal{O}(T^{-\frac{2p-2}{4p-1}})$, which is provably faster than non-accelerated versions.
Limitations and Future Work
While the results are robust, the authors identify several areas for future exploration. Some "normalization-only" results rely on Individual Lipschitzness (smoothness of every data point), which is a stronger assumption than the standard Global Lipschitzness. Furthermore, there remains a gap in combining the accelerated scheme with variance reduction, as the second-order Taylor expansions used in acceleration are currently incompatible with how variance reduction tracks gradient changes. Finally, while this work focuses on results "in expectation," future work may seek to provide high-probability bounds for even stricter guarantees.
Summary updated