cs.LGNov 11, 2026

A Matching Lower Bound for Online Smooth Calibration

Authors: Kaixuan Ji, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

We study smooth calibration error in sequential binary prediction, a measure of how far probabilistic forecasts are from being calibrated that is robust to small perturbations of the forecasts. The minimax smooth calibration error is known to lie between Ω(T1/3)Ω(T^{1/3}) and O(T)O(\sqrt T)(Qiao and Zheng, 2024), where TT is the number of rounds. We close this gap for both adaptive and oblivious adversaries. We construct an adaptive adversary whose outcome mean moves with the forecaster's cumulative residual, which makes compensating for past residuals costly and forces every forecaster to incur Ω(T)Ω(\sqrt T) expected smooth calibration error. Simulating this adversary against the forecaster's average prediction yields an oblivious adversary with the same guarantee. These lower bounds match the known O(T)O(\sqrt T) upper bound up to universal constants, and are therefore minimax optimal. Our results also imply matching Θ(T)Θ(\sqrt T) bounds for calibration distance and lower calibration distance. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

Figures & tables

Explore similar work

Mar 16, 2026

The Importance of Being Smoothly Calibrated

Recent work has highlighted the centrality of smooth calibration [Kakade and Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous results on smooth calibration, both as a robust calibration measure, and as a step towards omniprediction, which enables predictions with low regret for downstream decision makers seeking to optimize some proper loss unknown to the predictor. We present a new omniprediction guarantee for smoothly calibrated predictors, for the class of all bounded proper losses. We smooth the predictor by adding some noise to it, and compete against smoothed versions of any benchmark predictor on the space, where we add some noise to the predictor and then post-process it arbitrarily. The omniprediction error is bounded by the smooth calibration error of the predictor and the earth mover's distance from the benchmark. We exhibit instances showing that this dependence cannot, in general, be improved. We show how this unifies and extends prior results [Foster and Vohra, 1998; Hartline, Wu, and Yang, 2025] on omniprediction from smooth calibration. We present a crisp new characterization of smooth calibration in terms of the earth mover's distance to the closest perfectly calibrated joint distribution of predictions and labels. This also yields a simpler proof of the relation to the lower distance to calibration from [Blasiok, Gopalan, Hu, and Nakkiran, 2023]. We use this to show that the upper distance to calibration cannot be estimated within a quadratic factor with sample complexity independent of the support size of the predictions. This is in contrast to the distance to calibration, where the corresponding problem was known to be information-theoretically impossible: no finite number of samples suffice [Blasiok, Gopalan, Hu, and Nakkiran, 2023].
Jun 19, 2024

Breaking the T2/3T^{2/3} Barrier for Sequential Calibration

A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences under the standard ℓ1\ell_1 calibration error metric, which was initially studied by Foster & Vohra (1998). They derived an algorithm with O(T2/3)O(T^{2/3}) calibration error after TT time steps, and showed a lower bound of Ω(T1/2)Ω(T^{1/2}). These bounds remained stagnant for two decades, until Qiao & Valiant (2021) improved the lower bound to Ω(T0.528)Ω(T^{0.528}) by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the O(T2/3)O(T^{2/3}) upper bound on calibration error of Foster & Vohra. We do this by introducing a variant of Qiao & Valiant's game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved upper bound for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error O(T2/3−ε)O(T^{2/3 - \varepsilon}) for some ε>0\varepsilon > 0, improving Foster & Vohra's upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of Qiao & Valiant, namely Ω(T0.54389)Ω(T^{0.54389}). Our lower bound is obtained by an oblivious adversary, marking the first ω(T1/2)ω(T^{1/2}) calibration lower bound for oblivious adversaries.
Jul 14, 2026

Efficient Sequential Calibration with O(T2/3−ε)O(T^{2/3-ε}) Error Bound

We study the online binary sequential calibration problem. A recent breakthrough by \citet{dagan2024breaking} overcomes the classical T2/3T^{2/3} barrier for calibration error. Building on this result, we present an efficient randomized forecaster that achieves an expected calibration error O(T2/3−ε)O(T^{2/3-\varepsilon}) for some constant ε>0\varepsilon>0. Our forecaster combines the SPR-Calibration procedure \citep{dagan2024breaking} with an outer Blackwell-style correction layer. The SPR-Calibration procedure controls calibration with respect to a surrogate sequence of conditional-mean estimates, while the correction layer controls the additional error incurred when these surrogates are used to approximate the true outcomes. The analysis decomposes the total calibration error into the surrogate calibration error and the residual discrepancy between the surrogate sequence and the true outcomes. The former is bounded by the SPR-Calibration guarantee in \citet{dagan2024breaking}, and the latter is controlled using a quadratic potential argument together with the sparsity of the SPR-Calibration forecaster.