# High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise

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

## Key facts

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

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

- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [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)
- [Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2206.01095/) (2022)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Clip21: Error Feedback for Gradient Clipping](https://mlsanity.com/paper/2305.18929/) (2023)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)
- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [High Probability Analysis for Non-Convex Stochastic Optimization with Clipping](https://mlsanity.com/paper/2307.13680/) (2023)
- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [Flexible risk design using bi-directional dispersion](https://mlsanity.com/paper/2203.14434/) (2022)
- [Extragradient Method for (L0, L1)-Lipschitz Root-finding Problems](https://mlsanity.com/paper/2510.22421/) (2025)
- [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)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)
- [Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothness](https://mlsanity.com/paper/2610.06070/) (2026)

## Abstract (arXiv)

Stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm to result in a highly suboptimal objective value, whereas theoretical guarantees are usually proved for the expectation of the objective value. Thus, it is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth stochastic convex optimization have complexity bounds with the dependence on the confidence level that is either negative-power or logarithmic but under an additional assumption of sub-Gaussian (light-tailed) noise distribution that may not hold in practice. In our paper, we resolve this issue and derive the first high-probability convergence results with logarithmic dependence on the confidence level for non-smooth convex stochastic optimization problems with non-sub-Gaussian (heavy-tailed) noise. To derive our results, we propose novel stepsize rules for two stochastic methods with gradient clipping. Moreover, our analysis works for generalized smooth objectives with H"older-continuous gradients, and for both methods, we provide an extension for strongly convex problems. Finally, our results imply that the first (accelerated) method we consider also has optimal iteration and oracle complexity in all the regimes, and the second one is optimal in the non-smooth setting.