mlsanityData to 14 Oct 2026

Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise

arXiv 2506.11214 ↗First posted 12 Jun 2025math.OC cs.AI cs.CCcited by 11

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose practical normalized stochastic first-order methods with Polyak momentum, multi-extrapolated momentum, and recursive momentum for solving unconstrained optimization problems. These methods employ dynamically updated algorithmic parameters and do not require explicit knowledge of problem-dependent quantities such as the Lipschitz constant or noise bound. We establish first-order oracle complexity results for finding approximate stochastic stationary points under heavy-tailed noise and weakly average smoothness conditions -- both of which are weaker than the commonly used bounded variance and mean-squared smoothness assumptions. Our complexity bounds either improve upon or match the best-known results in the literature. Numerical experiments are presented to demonstrate the practical effectiveness of the proposed methods.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 29 of its 37 references that are in the map. First posted on arXiv 12 Jun 2025.

Builds on

29 of 37 references.

References · 29

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  3. 2014Microsoft COCO: Common Objects in Contextcited by 17,608
  4. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  5. 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,307
  6. 2015Flickr30k Entities: Collecting Region-to-Phrase Correspondences for Richer Image-to-Sentence Modelscited by 1,362
  7. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  8. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  9. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  10. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  12. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
17 more
  1. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  2. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  3. 2020Momentum Improves Normalized SGDcited by 139
  4. 2020The Heavy-Tail Phenomenon in SGDcited by 124
  5. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  6. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  7. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  8. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  9. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  10. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  11. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  12. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 43
  13. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  14. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  15. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  16. 2024Non-convex Stochastic Composite Optimization with Polyak Momentumcited by 9
  17. 2019Smoothness parameter of power of Euclidean normcited by 6

Built on by

Cited by year (2026 to 14 Oct)

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

11 papers.

  1. 2025Low-rank Orthogonalization for Large-scale Matrix Optimization with Applications to Foundation Model Trainingcited by 18
  2. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  3. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
  4. 2025DeMuon: A Decentralized Muon for Matrix Optimization over Graphscited by 4
  5. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 4
  6. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  7. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  8. 2026The Convergence Behavior of Adam under Heavy-Tailed Noisecited by 2
  9. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  10. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  11. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0