mlsanityData to 14 Oct 2026

Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

arXiv 2510.11676 ↗First posted 13 Oct 2025math.OC cs.AI cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. %In this paper, we demonstrate that a vanilla stochastic algorithm---without additional modifications such as clipping or normalization---can achieve optimal complexity for these problems. In this paper, we analyze the first-order oracle complexity of vanilla stochastic algorithms---without additional modifications such as clipping or normalization---for solving these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity for finding an approximate optimal solution in expectation that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Moreover, we derive high-probability first-order oracle complexity bounds for the accelerated stochastic proximal subgradient method under heavy-tailed and sub-Weibull noise, respectively. Numerical experiments are further provided to illustrate the numerical behavior of the methods.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 32 of its 53 references that are in the map. First posted on arXiv 13 Oct 2025.

Builds on

32 of 53 references.

References · 32

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  3. 2020The Heavy-Tail Phenomenon in SGDcited by 124
  4. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  5. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  6. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  7. 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
  8. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  9. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 43
  10. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  11. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  12. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
20 more
  1. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  2. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 28
  3. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
  4. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 24
  5. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  6. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  7. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  8. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  9. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 17
  10. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  11. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  12. 2022On Optimal Universal First-Order Methods for Minimizing Heterogeneous Sumscited by 9
  13. 2019Smoothness parameter of power of Euclidean normcited by 6
  14. 2022Proximal Subgradient Norm Minimization of ISTA and FISTAcited by 6
  15. 2015Generalized Uniformly Optimal Methods for Nonlinear Programmingcited by 4
  16. 2022A single cut proximal bundle method for stochastic convex composite optimizationcited by 4
  17. 2023Massive MIMO with Cauchy Noise: Channel Estimation, Achievable Rate and Data Decodingcited by 2
  18. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  19. 2024Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimizationcited by 1
  20. 2025Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalizationcited by 1
  2. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
  3. 2026The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimizationcited by 0
  4. 2026Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noisecited by 0