Adaptive regret comes at a constant — but unavoidable — multiplicative cost. We pin down the exact frontier and exhibit matching algorithms.
Journal JMLR 27(81) Bandits and online learning
On the Price of Adaptivity in Online Convex Optimization
Cite this paper
On the Price of Adaptivity in Online Convex Optimization
@inproceedings{singh2026price,
title = {On the Price of Adaptivity in Online Convex Optimization},
author = {Maya Singh and Renat Ostrovsky},
booktitle = {JMLR 27(81)},
year = {2026}
}