cs.LGMar 16, 2026

The Importance of Being Smoothly Calibrated

Authors: Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, Pranay Tankala

Organizations: Apple · UT Austin · Harvard

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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].

Figures & tables

Figure 1: A typical PLD μ\mu , with μb=Pr⁡(p,y)∼μ[y=b]\mu_{b}=\Pr_{(\mathbf{p},\mathbf{y})\sim\mu}[\mathbf{y}=b] . Note that μ0+μ1=1\mu_{0}+\mu_{1}=1 .
Figure 2: Visualization of the proof of Lemma 2.6 .
Figure 3: Optimal transport to calibration for each case of Theorem 5.1 . In cases (a) and (b), the predictions are concentrated entirely on the points 1/2±ε1/2\pm\varepsilon , but in cases (c) and (d), they are instead scattered nearby.
More in this topic

Model Calibration

Model calibration aligns predicted confidence or model outputs with observed outcomes and measurements to support more reliable decisions.

See all 214 papers

Explore similar work

CardsList
Jul 22, 2026

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 (ε,ε2)(\varepsilon, \varepsilon^2)-recalibration for Lipschitz proper losses in T≈ε−3T \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 K2\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 ε2\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 K2\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.

Lunjia Hu, Kevin Tian, Chutong Yang

Northeastern University · University of Texas at Austin

Model CalibrationOnline Calibration
AskPDF
Jun 18, 2026

Optimal Deterministic Multicalibration and Omniprediction

A model is multicalibrated on a collection of group weights GG if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each g∈Gg \in G. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal O~(ε−3)\widetilde O(\varepsilon^{-3}) sample complexity rate for ε\varepsilon-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].

Georgy Noarov, Aaron Roth

University of Pennsylvania

Minimax EstimationModel CalibrationMulticalibration
AskPDF
Jun 16, 2026

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(T)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 Ω(T)Ω(\sqrt{T}) regret instead of the optimal O(log⁡T)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 O~(T)\tilde O(\sqrt{T}) regret for every bounded proper loss and O(log⁡T)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

University of Colorado Boulder · University of Southern California and Google Research · University of Victoria +1

Follow-the-Perturbed-LeaderProbabilistic ForecastingProper Scoring RulesRegret Minimization
AskPDF