Can SGD Handle Heavy-Tailed Noise?
math.OC, cs.LG
Submitted: 2025-08-06
Updated: 2026-10-02
Comments: 40 pages, 5 figures, 2 tables. Extended version of a paper accepted for publication in the SIAM Journal on Optimization
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Sources
- High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise
- Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed
- Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
- Lower Complexity Bounds for Minimizing Regularized Functions
- Gradient Method With Inexact Oracle for Composite Non-Convex Optimization
- Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
- Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
- Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
- Unified Optimal Analysis of the (Stochastic) Gradient Method
- Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD
- Exact convergence rate of the last iterate in subgradient methods
Related papers
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
- Incremental Learning in Mirror Flows
- Second-Order Optimization with Asynchronous Curvature
- Online Control via Counterfactual Tracking
- Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability