# Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees

arXiv: https://arxiv.org/abs/2410.13954 · HTML: https://mlsanity.com/paper/2410.13954/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 64 references that are in the map.
- First posted on arXiv 17 Oct 2024.

## Builds on (most cited first, 30 of 32)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)
- [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022)
- [Revisiting the Noise Model of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.02749/) (2023)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Stable behaviour of infinitely wide deep neural networks](https://mlsanity.com/paper/2003.00394/) (2020)
- [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2106.05958/) (2021)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)

## Built on by (most cited first, 1 of 1)

- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)

## Abstract (arXiv)

We study high-probability convergence in online learning, in the presence of heavy-tailed noise. To combat the heavy tails, a general framework of nonlinear SGD methods is considered, subsuming several popular nonlinearities like sign, quantization, component-wise and joint clipping. In our work the nonlinearity is treated in a black-box manner, allowing us to establish unified guarantees for a broad range of nonlinear methods. For symmetric noise and non-convex costs we establish convergence of gradient norm-squared, at a rate widetildeO(t-1/4), while for the last iterate of strongly convex costs we establish convergence to the population optima, at a rate O(t-zeta), where zeta ∈ (0,1) depends on noise and problem parameters. Further, if the noise is a (biased) mixture of symmetric and non-symmetric components, we show convergence to a neighbourhood of stationarity, whose size depends on the mixture coefficient, nonlinearity and noise. Compared to state-of-the-art, who only consider clipping and require unbiased noise with bounded p-th moments, p ∈ (1,2], we provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments. While the rate exponents in state-of-the-art depend on noise moments and vanish as p rightarrow 1, our exponents are constant and strictly better whenever p < 6/5 for non-convex and p < 8/7 for strongly convex costs. Experiments validate our theory, showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.