Optimal Recalibration of an Online Predictor

We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary “hint” sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves $(\epsilon ,{\epsilon }^2)$-recalibration for Lipschitz proper losses in $T\approx {\epsilon }^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We also show this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. As an application, we show how our recalibration algorithm can be combined with the online refinement method of [FH23] to obtain simultaneous $\epsilon$-calibration and ${\epsilon }^2$-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\epsilon$ dependence. We also discuss extensions to settings with multiple hint sequences.