Instance-Adaptive Online Multicalibration

arXiv:2605.09273v1 Announce Type: new Abstract: 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.

Source: arXiv cs.LG | 2026-05-12