# The Price of Adaptivity in Stochastic Convex Optimization

arXiv: https://arxiv.org/abs/2402.10898 · HTML: https://mlsanity.com/paper/2402.10898/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method](https://mlsanity.com/paper/1907.02707/) (2019)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization](https://mlsanity.com/paper/1706.06569/) (2017)
- [Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting](https://mlsanity.com/paper/2006.07507/) (2020)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates](https://mlsanity.com/paper/2301.11294/) (2023)

## Built on by (most cited first, 11 of 11)

- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization](https://mlsanity.com/paper/2507.09093/) (2025)
- [The Sample Complexity of Parameter-Free Stochastic Convex Optimization](https://mlsanity.com/paper/2506.11336/) (2025)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [An Elementary Proof of the Near Optimality of LogSumExp Smoothing](https://mlsanity.com/paper/2512.10825/) (2025)
- [Clipping the Price of Adaptivity at the Tail](https://mlsanity.com/paper/2606.22669/) (2026)

## 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.