Near-optimal Swap Regret Minimization for Convex Losses
This work provides a significant improvement in the theoretical guarantees for online learning algorithms, specifically for swap regret minimization and calibration error, benefiting researchers and practitioners working on online decision-making and prediction systems.
This paper presents a randomized online algorithm that achieves a near-optimal $\widetilde O(\sqrt T)$ expected swap regret for Lipschitz convex losses on the unit interval, improving upon the previous best bound of $\widetilde O(T^{2/3})$. As a direct consequence, it provides an efficient online algorithm for minimizing calibration error for general elicitable properties, achieving the first $\widetilde O(\sqrt T)$ calibration error guarantee for median calibration without requiring Lipschitzness of the identification function.
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 of Fishelson et al. [2025b]. In addition, our algorithm is efficient: it runs in $\mathsf{poly}(T)$ 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.