Instance-Adaptive Online Multicalibration
This work provides a unified algorithm for online multicalibration that adapts to instance difficulty, benefiting practitioners who need robust yet efficient calibration in dynamic environments.
The paper presents an efficient algorithm for online multicalibration that adapts to varying difficulty levels, achieving worst-case optimal rate of O~(T^{2/3}) while automatically improving to O~(√T) in stochastic settings and O~(√(JT)) for piecewise-stationary means with J segments.
We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between benign and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known $\widetilde O(T^{2/3})$ worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of $\widetilde O(\sqrt T)$, and for piecewise-stationary means with $J$ segments its rate is $\widetilde O(\sqrt{JT})$. More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.