mlsanityData to 7 Oct 2026

Parameter-free Regret in High Probability with Heavy Tails

arXiv 2210.14355 ↗First posted 25 Oct 2022stat.ML cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work in unbounded domains considers only in-expectation results for sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability at most δ, for all comparators u our algorithm achieves regret tildeO(| u | T^1/mathfrakp log (1/δ)) for subgradients with bounded mathfrakpth moments for some mathfrakp ∈ (1, 2].

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 25 of its 54 references that are in the map. First posted on arXiv 25 Oct 2022.

Builds on

25 of 54 references.

References · 25

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019On the Convergence of Adam and Beyondcited by 834
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  5. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  6. 2020Estimating means of bounded random variables by bettingcited by 164
  7. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  8. 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 125
  9. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  10. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  11. 2019Online Control with Adversarial Disturbancescited by 92
  12. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
13 more
  1. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  2. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  3. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  4. 2022Making SGD Parameter-Freecited by 50
  5. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 42
  6. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  7. 2017Online Learning Without Prior Informationcited by 36
  8. 2017Parameter-free online learning via model selectioncited by 34
  9. 2019Parameter-Free Online Convex Optimization with Sub-Exponential Noisecited by 28
  10. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 25
  11. 2019Combining Online Learning Guaranteescited by 22
  12. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  13. 2019Adaptive scale-invariant online algorithms for learning linear modelscited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 5; 2025: 6; 2026: 9.

26 papers.

Sort:

  1. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  2. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  3. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  4. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  5. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  6. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  7. 2023Normalized Gradients for Allcited by 18
  8. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  9. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
  10. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  11. 2024Fully Unconstrained Online Learningcited by 10
  12. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
14 more
  1. 2024Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noisecited by 3
  2. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  3. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
  4. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  5. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  6. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  7. 2026The Convergence Behavior of Adam under Heavy-Tailed Noisecited by 1
  8. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  9. 2026Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffscited by 0
  10. 2026High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batchcited by 0
  11. 2026Policy-Controlled Generalized Share: A General Framework with a Transformer Instantiation for Strictly Online Switching-Oracle Trackingcited by 0
  12. 2026A Perturbation Approach to Unconstrained Linear Banditscited by 0
  13. 2026Online Conformal Prediction with Corrupted Feedbackcited by 0
  14. 2026Parameter-Free Dynamic Regret under Heavy-Tailed Noisecited by 0