Optimal Recalibration Algorithm Achieves Simultaneous Calibration and Calibeating

The paper tackles the problem of recalibrating an online predictor: given an arbitrary sequence of forecasts (hints), the learner must output new predictions that are calibrated while incurring minimal excess error under a proper loss. The authors introduce an algorithm that achieves (ε, ε²)-recalibration for Lipschitz proper losses in roughly ε⁻³ rounds, leveraging an imbalanced variant of the simultaneous Blackwell approachability reduction framework from HTY26. They prove this tradeoff is optimal by establishing a matching lower bound for recalibration against squared loss. Additionally, they provide a companion K₂-recalibration theorem that attains the same tradeoffs up to a logarithmic factor.

As a main application, the recalibration algorithms are combined with the online refinement method of FH23 to simultaneously achieve ε-calibration and ε²-calibeating for smooth proper losses at the same asymptotic rate. This improves upon prior works that achieved these properties separately or with a worse ε dependence. In particular, the K₂ variant answers a question from CHJL26 on simultaneously achieving near-optimal calibeating and calibration rates. The authors also extend the results to settings with multiple hint sequences and empirically validate their algorithms on a classification dataset undergoing distribution shift.