# Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 70 references that are in the map.
- First posted on arXiv 12 Jul 2025.

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

- [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)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [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)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [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)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [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)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Revisiting the Noise Model of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.02749/) (2023)
- [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)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Secure Distributed Optimization Under Gradient Attacks](https://mlsanity.com/paper/2210.15821/) (2022)
- [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)

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

- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)

## Abstract (arXiv)

We study convergence in high-probability of SGD-type methods in non-convex optimization and the presence of heavy-tailed noise. To combat the heavy-tailed noise, a general black-box nonlinear framework is considered, subsuming nonlinearities like sign, clipping, normalization and their smooth counterparts. Our first result shows that nonlinear SGD (N-SGD) achieves the rate widetildeO(t-1/2), for any noise with unbounded moments and a symmetric probability density function (PDF). Crucially, N-SGD has exponentially decaying tails, matching the performance of linear SGD under light-tailed noise. To handle non-symmetric noise, we propose two novel estimators, based on the idea of noise symmetrization. The first, dubbed Symmetrized Gradient Estimator (SGE), assumes a noiseless gradient at any reference point is available at the start of training, while the second, dubbed Mini-batch SGE (MSGE), uses mini-batches to estimate the noiseless gradient. Combined with the nonlinear framework, we get N-SGE and N-MSGE methods, respectively, both achieving the same convergence rate and exponentially decaying tails as N-SGD, while allowing for non-symmetric noise with unbounded moments and PDF satisfying a mild technical condition, with N-MSGE additionally requiring bounded noise moment of order p ∈ (1,2]. Compared to works assuming noise with bounded p-th moment, our results: 1) are based on a novel symmetrization approach; 2) provide a unified framework and relaxed moment conditions; 3) imply optimal oracle complexity of N-SGD and N-SGE, strictly better than existing works when p < 2, while the complexity of N-MSGE is close to existing works. Compared to works assuming symmetric noise with unbounded moments, we: 1) provide a sharper analysis and improved rates; 2) facilitate state-dependent symmetric noise; 3) extend the strong guarantees to non-symmetric noise.