# High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

## Built on by (most cited first, 30 of 31)

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [General Tail Bounds for Non-Smooth Stochastic Mirror Descent](https://mlsanity.com/paper/2312.07142/) (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)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [High Probability Analysis for Non-Convex Stochastic Optimization with Clipping](https://mlsanity.com/paper/2307.13680/) (2023)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails](https://mlsanity.com/paper/2405.17529/) (2024)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [A Large Deviations Perspective on Policy Gradient Algorithms](https://mlsanity.com/paper/2311.07411/) (2023)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees](https://mlsanity.com/paper/2410.13954/) (2024)
- [Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysis](https://mlsanity.com/paper/2411.06770/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.20399/) (2026)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [Robust and Fast Training via Per-Sample Clipping](https://mlsanity.com/paper/2605.02701/) (2026)
- [SGD Jittering: A Training Strategy for Robust and Accurate Model-Based Architectures](https://mlsanity.com/paper/2410.14667/) (2024)
- [Stochastic Gradient Descent Revisited](https://mlsanity.com/paper/2412.06070/) (2024)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)
- [Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?](https://mlsanity.com/paper/2605.27733/) (2026)
- [Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers](https://mlsanity.com/paper/2606.13287/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)
- [Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"older Smoothness](https://mlsanity.com/paper/2609.12785/) (2026)
- [High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/2609.32195/) (2026)

## Abstract (arXiv)

Stochastic gradient descent is one of the most common iterative algorithms used in machine learning and its convergence analysis is a rich area of research. Understanding its convergence properties can help inform what modifications of it to use in different settings. However, most theoretical results either assume convexity or only provide convergence results in mean. This paper, on the other hand, proves convergence bounds in high probability without assuming convexity. Assuming strong smoothness, we prove high probability convergence bounds in two settings: (1) assuming the Polyak-Lojasiewicz inequality and norm sub-Gaussian gradient noise and (2) assuming norm sub-Weibull gradient noise. In the second setting, as an intermediate step to proving convergence, we prove a sub-Weibull martingale difference sequence self-normalized concentration inequality of independent interest. It extends Freedman-type concentration beyond the sub-exponential threshold to heavier-tailed martingale difference sequences. We also provide a post-processing method that picks a single iterate with a provable convergence guarantee as opposed to the usual bound for the unknown best iterate. Our convergence result for sub-Weibull noise extends the regime where stochastic gradient descent has equal or better convergence guarantees than stochastic gradient descent with modifications such as clipping, momentum, and normalization.