mlsanityData to 7 Oct 2026

Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance

arXiv 2202.11632 ↗First posted 23 Feb 2022stat.ML cs.LG math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

We study stochastic convex optimization under infinite noise variance. Specifically, when the stochastic gradient is unbiased and has uniformly bounded (1+kappa)-th moment, for some kappa ∈ (0,1], we quantify the convergence rate of the Stochastic Mirror Descent algorithm with a particular class of uniformly convex mirror maps, in terms of the number of iterations, dimensionality and related geometric parameters of the optimization problem. Interestingly this algorithm does not require any explicit gradient clipping or normalization, which have been extensively used in several recent empirical and theoretical works. We complement our convergence results with information-theoretic lower bounds showing that no other algorithm using only stochastic first-order oracles can achieve improved rates. Our results have several interesting consequences for devising online/streaming stochastic approximation algorithms for problems arising in robust statistics and machine learning.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 23 of its 63 references that are in the map. First posted on arXiv 23 Feb 2022.

Builds on

23 of 63 references.

References · 23

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2020Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecited by 140
  5. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  6. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  7. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  8. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  9. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  10. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  11. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  12. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 42
11 more
  1. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  2. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  3. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  4. 2019An Introductory Guide to Fano's Inequality with Applications in Statistical Estimationcited by 30
  5. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  6. 2016Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entriescited by 18
  7. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  8. 2021Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injectionscited by 12
  9. 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
  10. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  11. 2021On Monte-Carlo methods in convex stochastic optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 3; 2025: 6; 2026: 5.

22 papers.

Sort:

By area:

  1. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  2. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  3. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  4. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  5. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
  6. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  7. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  8. 2025Mirror Flow Matching with Heavy-Tailed Priors for Generative Modeling on Convex Domainscited by 8
  9. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  10. 2023General Tail Bounds for Non-Smooth Stochastic Mirror Descentcited by 7
  11. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  12. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
10 more
  1. 2025Natural Gradient VI: Guarantees for Non-Conjugate Modelscited by 3
  2. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  3. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  4. 2022Optimal Algorithms for Stochastic Complementary Composite Minimizationcited by 1
  5. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  6. 2024Configurable Mirror Descent: Towards a Unification of Decision Makingcited by 1
  7. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  8. 2026When to use what Schatten-p norm in deep learning?cited by 0
  9. 2026Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruptioncited by 0
  10. 2026Parameter-Free Dynamic Regret under Heavy-Tailed Noisecited by 0