# Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 22 Mar 2023.

## Builds on (most cited first, 23 of 23)

- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning](https://mlsanity.com/paper/2010.05627/) (2020)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023)
- [High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2106.05958/) (2021)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injections](https://mlsanity.com/paper/2102.07006/) (2021)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)

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

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [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)
- [Limit Theorems for Stochastic Gradient Descent with Infinite Variance](https://mlsanity.com/paper/2410.16340/) (2024)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [DADA: Dual Averaging with Distance Adaptation](https://mlsanity.com/paper/2501.10258/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.19379/) (2026)
- [Statistical Inference for Stochastic Gradient Descent: Beyond Finite Variance](https://mlsanity.com/paper/2605.26000/) (2026)
- [Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates](https://mlsanity.com/paper/2408.09891/) (2024)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization](https://mlsanity.com/paper/2605.18999/) (2026)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)
- [Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruption](https://mlsanity.com/paper/2606.18778/) (2026)
- [New Bounds for the Last Iterate of the Stochastic subGradient Method](https://mlsanity.com/paper/2606.24879/) (2026)

## Abstract (arXiv)

Recently, several studies consider the stochastic optimization problem but in a heavy-tailed noise regime, i.e., the difference between the stochastic gradient and the true gradient is assumed to have a finite p-th moment (say being upper bounded by σp for some σ≥0) where p∈(1,2], which not only generalizes the traditional finite variance assumption (p=2) but also has been observed in practice for several different tasks. Under this challenging assumption, lots of new progress has been made for either convex or nonconvex problems, however, most of which only consider smooth objectives. In contrast, people have not fully explored and well understood this problem when functions are nonsmooth. This paper aims to fill this crucial gap by providing a comprehensive analysis of stochastic nonsmooth convex optimization with heavy-tailed noises. We revisit a simple clipping-based algorithm, whereas, which is only proved to converge in expectation but under the additional strong convexity assumption. Under appropriate choices of parameters, for both convex and strongly convex functions, we not only establish the first high-probability rates but also give refined in-expectation bounds compared with existing works. Remarkably, all of our results are optimal (or nearly optimal up to logarithmic factors) with respect to the time horizon T even when T is unknown in advance. Additionally, we show how to make the algorithm parameter-free with respect to σ, in other words, the algorithm can still guarantee convergence without any prior knowledge of σ. Furthermore, an initial distance adaptive convergence rate is provided if σ is assumed to be known.