Near-optimal Swap Regret Minimization for Convex Losses

Lunjia Hu, Jon Schneider, Yifan Wu
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3285-3313, 2026.

Abstract

We give a randomized online algorithm that guarantees near-optimal $\widetilde{O}(\sqrt{T})$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde{O}(T^{2/3})$ and answers an open question from prior work. In addition, our algorithm is efficient: it runs in polynomial time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde{O}(\sqrt{T})$ calibration error guarantee.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-hu26a, title = {Near-optimal Swap Regret Minimization for Convex Losses}, author = {Hu, Lunjia and Schneider, Jon and Wu, Yifan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3285--3313}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/hu26a/hu26a.pdf}, url = {https://proceedings.mlr.press/v336/hu26a.html}, abstract = {We give a randomized online algorithm that guarantees near-optimal $\widetilde{O}(\sqrt{T})$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde{O}(T^{2/3})$ and answers an open question from prior work. In addition, our algorithm is efficient: it runs in polynomial time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde{O}(\sqrt{T})$ calibration error guarantee.} }
Endnote
%0 Conference Paper %T Near-optimal Swap Regret Minimization for Convex Losses %A Lunjia Hu %A Jon Schneider %A Yifan Wu %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-hu26a %I PMLR %P 3285--3313 %U https://proceedings.mlr.press/v336/hu26a.html %V 336 %X We give a randomized online algorithm that guarantees near-optimal $\widetilde{O}(\sqrt{T})$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde{O}(T^{2/3})$ and answers an open question from prior work. In addition, our algorithm is efficient: it runs in polynomial time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde{O}(\sqrt{T})$ calibration error guarantee.
APA
Hu, L., Schneider, J. & Wu, Y.. (2026). Near-optimal Swap Regret Minimization for Convex Losses. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3285-3313 Available from https://proceedings.mlr.press/v336/hu26a.html.

Related Material