High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise
Not on the map. Why?
Abstract (arXiv)
In this work we study high probability bounds for stochastic subgradient methods under heavy tailed noise. In this setting the noise is only assumed to have finite variance as opposed to a sub-Gaussian distribution for which it is known that standard subgradient methods enjoys high probability bounds. We analyzed a clipped version of the projected stochastic subgradient method, where subgradient estimates are truncated whenever they have large norms. We show that this clipping strategy leads both to near optimal any-time and finite horizon bounds for many classical averaging schemes. Preliminary experiments are shown to support the validity of the method.
Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 8 of its 31 references that are in the map. First posted on arXiv 17 Aug 2022.
Builds on
8 of 31 references.
References · 8
- 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
- 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
- 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
- 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
- 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 19
- 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
- 2016Optimal Rates for Multi-pass Stochastic Gradient Methodscited by 8
Built on by
Citing papers per year: 2023: 4; 2024: 2; 2025: 1; 2026: 2.
9 papers.
- 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
- 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
- 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
- 2023General Tail Bounds for Non-Smooth Stochastic Mirror Descentcited by 7
- 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
- 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
- 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
- 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
- 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
- 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking30 Apr 2026
- 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization5 Feb 2026
- 2025Efficient Distributed Optimization under Heavy-Tailed Noise6 Feb 2025
- 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees17 Oct 2024
- 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates19 Aug 2024
- 2023General Tail Bounds for Non-Smooth Stochastic Mirror Descent12 Dec 2023
- 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise28 Oct 2023
- 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation22 Mar 2023
- 2023High Probability Convergence of Stochastic Gradient Methods28 Feb 2023