mlsanityData to 7 Oct 2026

General Tail Bounds for Non-Smooth Stochastic Mirror Descent

arXiv 2312.07142 ↗First posted 12 Dec 2023cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we provide novel tail bounds on the optimization error of Stochastic Mirror Descent for convex and Lipschitz objectives. Our analysis extends the existing tail bounds from the classical light-tailed Sub-Gaussian noise case to heavier-tailed noise regimes. We study the optimization error of the last iterate as well as the average of the iterates. We instantiate our results in two important cases: a class of noise with exponential tails and one with polynomial tails. A remarkable feature of our results is that they do not require an upper bound on the diameter of the domain. Finally, we support our theory with illustrative experiments that compare the behavior of the average of the iterates with that of the last iterate in heavy-tailed noise regimes.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 14 of its 42 references that are in the map. First posted on arXiv 12 Dec 2023.

Builds on

14 of 42 references.

References · 14

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  3. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  4. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  5. 2018Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regressioncited by 42
  6. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  7. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  8. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  9. 2020Sharp Concentration Results for Heavy-Tailed Distributionscited by 15
  10. 2023Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailscited by 11
  11. 2022High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noisecited by 9
  12. 2022Stochastic Saddle Point Problems with Decision-Dependent Distributionscited by 6
2 more
  1. 2021Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Lojasiewicz Conditioncited by 3
  2. 2021Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problemscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 0; 2026: 4.

7 papers.

  1. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  2. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  3. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  4. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  5. 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
  6. 2026New Bounds for the Last Iterate of the Stochastic subGradient Methodcited by 0
  7. 2026Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noisecited by 0