Optimal Recalibration of an Online Predictor

Lunjia Hu; Kevin Tian; Chutong Yang

stat.MLJul 22, 2026

Optimal Recalibration of an Online Predictor

Authors: Lunjia Hu, Kevin Tian, Chutong Yang

Organizations: Northeastern University · University of Texas at Austin

Abstract

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 $(\varepsilon, \varepsilon^2)$ -recalibration for Lipschitz proper losses in $T \approx \varepsilon^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. We also prove a companion $\mathcal{K}_2$ -recalibration theorem that obtains the same tradeoffs up to a logarithmic factor. As our main application, we show how our recalibration algorithms can be combined with the online refinement method of [FH23] to obtain simultaneous $\varepsilon$ -calibration and $\varepsilon^2$ -calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\varepsilon$ dependence. In particular, the $\mathcal{K}_2$ variant answers a question of [CHJL26] on simultaneously achieving near-optimal calibeating and calibration rates. We also derive extensions to settings with multiple hint sequences. Finally, we empirically evaluate our algorithms on a classification dataset undergoing distribution shift.

Explore similar work

Jun 16, 2026stat.ML

Toward Simultaneously Optimal Regret in U-Calibration

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal

O(\sqrt{T})

regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur

Ω(\sqrt{T})

regret instead of the optimal

O(\log T)

regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves

\tilde O(\sqrt{T})

regret for every bounded proper loss and

O(\log T)

regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

Rafael Frongillo, Haipeng Luo, Nishant A. Mehta +1

Linear Regret Regret

Ask PDF

May 10, 2026cs.LG

Instance-Adaptive Online Multicalibration

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.

Zhiming Huang, Jamie Morgenstern, Aaron Roth +1

Learning-Augmented Algorithms Worst-Case Sensitivity

Ask PDF

May 12, 2026cs.LG

Adaptive Calibration in Non-Stationary Environments

Making calibrated online predictions is a central challenge in modern AI systems. Much of the existing literature focuses on fully adversarial environments where outcomes may be arbitrary, leading to conservative algorithms that can perform suboptimally in more benign settings, such as when outcomes are nearly stationary. This gap raises a natural question: can we design online prediction algorithms whose calibration error automatically adapts to the degree of non-stationarity in the environment, smoothly interpolating between i.i.d. and adversarial regimes? We answer this question in the affirmative and develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures. Specifically, with

T

being the number of rounds,

K

being the unknown number of i.i.d. segments of the environment, and

C\in[0,T]

being another unknown non-stationary measure defined as the minimal

\ell_1

deviation of the mean outcomes, our algorithms attain

\widetilde{O}(\min\{\sqrt{T}+(TC)^{\frac{1}{3}}, \sqrt{KT}\})

for

\ell_1

calibration error and

\widetilde{O}(\min\{(1+C)^{\frac{1}{3}}, K\})

for both

\ell_2

and pseudo KL calibration error. These bounds match the optimal rates in the stationary case (

C=0

and

K=1

) and recover known guarantees in the fully adversarial regime (

C, K=Ω(T)

). Our approach builds on and extends prior work [Hu et al., 2026, Luo et al., 2025], introducing an epoch-based scheduling together with a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.

Junyan Liu, Haipeng Luo, Lillian J. Ratliff

Non-Stationarity Recalibration Adversaries Environment

Ask PDF