# Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 33 references that are in the map.
- First posted on arXiv 14 Feb 2023.

## Builds on (most cited first, 18 of 18)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [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)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2008.09055/) (2020)
- [Direct Acceleration of SAGA using Sampled Negative Momentum](https://mlsanity.com/paper/1806.11048/) (2018)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)

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

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [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)
- [Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise](https://mlsanity.com/paper/2506.11214/) (2025)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [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)
- [Efficient Distributed Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2502.04164/) (2025)
- [Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization](https://mlsanity.com/paper/2507.09093/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad](https://mlsanity.com/paper/2605.18694/) (2026)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Federated Stochastic Minimax Optimization under Heavy-Tailed Noises](https://mlsanity.com/paper/2511.04456/) (2025)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees](https://mlsanity.com/paper/2410.13954/) (2024)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [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)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)
- [Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity](https://mlsanity.com/paper/2601.19730/) (2026)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)
- [Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling](https://mlsanity.com/paper/2605.07634/) (2026)
- [Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?](https://mlsanity.com/paper/2605.27733/) (2026)
- [Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm](https://mlsanity.com/paper/2606.22466/) (2026)

## Abstract (arXiv)

We consider the stochastic optimization problem with smooth but not necessarily convex objectives in the heavy-tailed noise regime, where the stochastic gradient's noise is assumed to have bounded pth moment (p∈(1,2]). Zhang et al. (2020) is the first to prove the Omega(T^frac1-p3p-2) lower bound for convergence (in expectation) and provides a simple clipping algorithm that matches this optimal rate. Cutkosky and Mehta (2021) proposes another algorithm, which is shown to achieve the nearly optimal high-probability convergence guarantee O(log(T/δ)T^frac1-p3p-2), where δ is the probability of failure. However, this desirable guarantee is only established under the additional assumption that the stochastic gradient itself is bounded in pth moment, which fails to hold even for quadratic objectives and centered Gaussian noise. In this work, we first improve the analysis of the algorithm in Cutkosky and Mehta (2021) to obtain the same nearly optimal high-probability convergence rate O(log(T/δ)T^frac1-p3p-2), without the above-mentioned restrictive assumption. Next, and curiously, we show that one can achieve a faster rate than that dictated by the lower bound Omega(T^frac1-p3p-2) with only a tiny bit of structure, i.e., when the objective function F(x) is assumed to be in the form of mathbbEXi~D[f(x,Xi)], arguably the most widely applicable class of stochastic optimization problems. For this class of problems, we propose the first variance-reduced accelerated algorithm and establish that it guarantees a high-probability convergence rate of O(log(T/δ)T^frac1-p2p-1) under a mild condition, which is faster than Omega(T^frac1-p3p-2). Notably, even when specialized to the finite-variance case, our result yields the (near-)optimal high-probability rate O(log(T/δ)T-1/3).