# Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2023.

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [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)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [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)
- [Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences](https://mlsanity.com/paper/2311.14127/) (2023)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [The Convergence Behavior of Adam under Heavy-Tailed Noise](https://mlsanity.com/paper/2607.27383/) (2026)
- [Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation](https://mlsanity.com/paper/2605.15388/) (2026)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

In this work, we study the convergence in high probability of clipped gradient methods when the noise distribution has heavy tails, ie., with bounded pth moments, for some 1<p≤2. Prior works in this setting follow the same recipe of using concentration inequalities and an inductive argument with union bound to bound the iterates across all iterations. This method results in an increase in the failure probability by a factor of T, where T is the number of iterations. We instead propose a new analysis approach based on bounding the moment generating function of a well chosen supermartingale sequence. We improve the dependency on T in the convergence guarantee for a wide range of algorithms with clipped gradients, including stochastic (accelerated) mirror descent for convex objectives and stochastic gradient descent for nonconvex objectives. This approach naturally allows the algorithms to use time-varying step sizes and clipping parameters when the time horizon is unknown, which appears impossible in prior works. We show that in the case of clipped stochastic mirror descent, problem constants, including the initial distance to the optimum, are not required when setting step sizes and clipping parameters.