mlsanityData to 7 Oct 2026

The Price of Adaptivity in Stochastic Convex Optimization

arXiv 2402.10898 ↗First posted 16 Feb 2024math.OC cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a "price of adaptivity" (PoA) that, roughly speaking, measures the multiplicative increase in suboptimality due to uncertainty in these parameters. When the initial distance to the optimum is unknown but a gradient norm bound is known, we show that the PoA is at least logarithmic for expected suboptimality, and double-logarithmic for median suboptimality. When there is uncertainty in both distance and gradient norm, we show that the PoA must be polynomial in the level of uncertainty. Our lower bounds nearly match existing upper bounds, and establish that there is no parameter-free lunch. En route, we also establish tight upper and lower bounds for (known-parameter) high-probability stochastic convex optimization with heavy-tailed and bounded noise, respectively.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 28 of its 53 references that are in the map. First posted on arXiv 16 Feb 2024.

Builds on

28 of 53 references.

References · 28

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  3. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  4. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  5. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  6. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  7. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  8. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 60
  9. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  10. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  11. 2019Revisiting the Polyak step sizecited by 55
  12. 2022Making SGD Parameter-Freecited by 50
16 more
  1. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  2. 2017Online Learning Without Prior Informationcited by 36
  3. 2019Lipschitz Adaptivity with Multiple Learning Rates in Online Learningcited by 36
  4. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  5. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  6. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  7. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  8. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  9. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  10. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 23
  11. 2017A Unified Approach to Adaptive Regularization in Online and Stochastic Optimizationcited by 19
  12. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  13. 2014Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theorycited by 16
  14. 2024Tuning-Free Stochastic Optimizationcited by 13
  15. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  16. 2023Coin Sampling: Gradient-Based Bayesian Inference without Learning Ratescited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 5; 2026: 2.

11 papers.

  1. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  2. 2024High-probability minimax lower boundscited by 11
  3. 2024Fully Unconstrained Online Learningcited by 10
  4. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  5. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  6. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  7. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
  8. 2025The Sample Complexity of Parameter-Free Stochastic Convex Optimizationcited by 1
  9. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  10. 2025An Elementary Proof of the Near Optimality of LogSumExp Smoothingcited by 0
  11. 2026Clipping the Price of Adaptivity at the Tailcited by 0