mlsanityData to 7 Oct 2026

High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance

arXiv 2302.00999 ↗First posted 2 Feb 2023math.OC cs.LGcited by 60

Not on the map. Why?

Abstract (arXiv)

During recent years the interest of optimization and machine learning communities in high-probability convergence of stochastic optimization methods has been growing. One of the main reasons for this is that high-probability complexity bounds are more accurate and less studied than in-expectation ones. However, SOTA high-probability non-asymptotic convergence results are derived under strong assumptions such as the boundedness of the gradient noise variance or of the objective's gradient itself. In this paper, we propose several algorithms with high-probability convergence results under less restrictive assumptions. In particular, we derive new high-probability convergence results under the assumption that the gradient/operator noise has bounded central α-th moment for α ∈ (1,2] in the following setups: (i) smooth non-convex / Polyak-Lojasiewicz / convex / strongly convex / quasi-strongly convex minimization problems, (ii) Lipschitz / star-cocoercive and monotone / quasi-strongly monotone variational inequalities. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes studied in stochastic optimization.

Key facts. Cited by 60 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Feb 2023.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 11; 2025: 16; 2026: 24.

60 papers.

Sort:

  1. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  2. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  3. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  4. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  5. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  6. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  7. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  8. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
  9. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
  10. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  11. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  12. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
38 more
  1. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 8
  2. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 8
  3. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  4. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  5. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  6. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  7. 2023Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differencescited by 5
  8. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  9. 2024Parameter-free Clipped Gradient Descent Meets Polyakcited by 3
  10. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  11. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  12. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  13. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
  14. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  15. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  16. 2023Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimizationcited by 2
  17. 2025Functional multi-armed bandit and the best function identification problemscited by 2
  18. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  19. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
  20. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  21. 2026LionMuon: Alternating Spectral and Sign Descent for Efficient Trainingcited by 2
  22. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  23. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  24. 2023The Local Landscape of Phase Retrieval Under Limited Samplescited by 1
  25. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  26. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1
  27. 2025High-Probability Convergence Guarantees of Decentralized SGDcited by 1
  28. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  29. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  30. 2026Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Successcited by 1
  31. 2024Tracking the Median of Gradients with a Stochastic Proximal Point Methodcited by 0
  32. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  33. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 0
  34. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
  35. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  36. 2026A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithmscited by 0
  37. 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
  38. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0

50 most cited of 60 All 60 (JSON)