betaFeedback

WorksComputer Science

A Matching Lower Bound for Online Smooth Calibration

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.

Introduction

We study the sequential binary forecasting problem of Foster and Vohra [9]. Over TT rounds, a forecaster and an adversary interact as follows. At each round t∈[T]t \in[T], the forecaster predicts a probability pt∈[0,1]p_t \in[0,1] that the next binary outcome equals 1, and the adversary simultaneously selects the outcome xt∈{0,1}x_t \in\{0,1\}. Both ptp_t and xtx_t are then revealed, and may factor into the subsequent actions of both players. This problem abstracts many applications in which probabilistic predictions are issued sequentially, including weather forecasting ([3, 6]), uncertainty quantification of machine learning models ([12]), fair risk prediction ([16]), and forecasting for downstream decision makers ([19]).

A natural requirement for the predictions to be interpretable as probabilities is calibration (Dawid, [6]): among the rounds on which the forecaster predicts a value α\alpha, the outcome should equal 1 in an α\alpha fraction of them. Formally, the forecaster is perfectly calibrated if ∑t=1T(xt−pt)1{pt=α}=0\sum_{t=1}^{T}(x_t-p_t)\mathbf{1}\{p_t=\alpha\}=0 for every α∈[0,1]\alpha\in[0,1]. The most widely used measure of the violation of this condition is the ℓ1\ell_1 calibration error, also known as the expected calibration error (ECE),

ECE⁡(x,p)=∑α∈[0,1]∣∑t=1T(xt−pt)1{pt=α}∣.\operatorname{ECE}(x,p)=\sum_{\alpha\in[0,1]}\left|\sum_{t=1}^{T}(x_t-p_t)\mathbf{1}\{p_t=\alpha\}\right|.

where only the values α∈{p1,…,pT}\alpha\in\{p_1,\ldots,p_T\} contribute to the sum. However, ECE is discontinuous in the predictions. Suppose that xx contains equally many 0s and 1s. Then predicting pt=1/2p_t = 1/2 in every round gives zero ECE. If each ptp_t is instead perturbed to 1/2+ϵt1/2 + \epsilon_t for tiny, distinct, nonzero ϵt\epsilon_t, then every round falls into its own bin, and ECE jumps to Ω(T)\Omega(T), although the predictions are essentially unchanged.

This sensitivity motivates the smooth calibration error [18, 2], which tests the residuals against all bounded Lipschitz functions of the predictions,

smCE⁡(x,p)=sup⁡f∈F∑t=1Tf(pt)(xt−pt),\operatorname{smCE}(x,p) = \sup_{f \in\mathcal{F}} \sum_{t=1}^{T} f(p_t)(x_t-p_t),

where F\mathcal{F} is the class of 1-Lipschitz functions from [0,1][0,1] to [−1,1][-1,1]. Since nearby predictions receive nearby weights, smCE is robust to small perturbations of the predictions, and in the example above it remains small.

For smooth calibration error, however, a gap remains in the sequential setting. Qiao and Zheng [22] gave a forecaster that achieves O(T)O(\sqrt{T}) smooth calibration error against any adversary. It might appear obvious that this rate is tight, since independent fair outcomes make the cumulative residual ∣∑t(xt−pt)∣\left|\sum_t(x_t-p_t)\right| of order T\sqrt{T} when the forecaster predicts 1/21/2. Surprisingly, Qiao and Zheng [22] showed that this argument is incorrect: against independent fair outcomes, a forecaster can compensate for past residuals with slightly biased predictions, and achieve only polylogarithmic smooth calibration error. Their adversary circumvents this by generating fair outcomes until the error is large and then stopping early with constant outcomes, which yields an Ω(T1/3)\Omega(T^{1/3}) lower bound. This leaves the following question:

Is Ω(T) smooth calibration error unavoidable in sequential prediction?\mathit{Is\ }\Omega(\sqrt{T})\mathit{\ smooth\ calibration\ error\ unavoidable\ in\ sequential\ prediction?}

In this paper, we answer this question affirmatively, against both adaptive and oblivious adversaries. We first construct a new adaptive adversary whose outcome mean moves with the forecaster’s cumulative residual, which makes compensating for past residuals costly, and show that it forces every forecaster to incur Ω(T)\Omega(\sqrt{T}) expected smooth calibration error, improving the Ω(T1/3)\Omega(T^{1/3}) lower bound of Qiao and Zheng [22] and matching the known O(T)O(\sqrt{T}) upper bound. We further convert this adversary into an oblivious one, which simulates the interaction against the forecaster’s average prediction before the game, and show that the same lower bound holds even when the outcome sequence is fixed in advance. Since smooth calibration error lower bounds both calibration distance and lower calibration distance up to a constant factor, our results also imply matching Θ(T)\Theta(\sqrt{T}) bounds for these two measures in both settings. A comparison of our results with directly related previous results is summarized in Table 1.

TypeReferencesmCELowerCalDistCalDist
Upper BoundQiao and Zheng [22]O(T)O(\sqrt{T})O(T)O(\sqrt{T})O(T)O(\sqrt{T})
Lower BoundQiao and Zheng [22]Ω(T1/3)\Omega(T^{1/3})Ω(T1/3)\Omega(T^{1/3})Ω(T1/3)\Omega(T^{1/3})
Lower BoundThis WorkΩ(T)\Omega(\sqrt{T})Ω(T)\Omega(\sqrt{T})Ω(T)\Omega(\sqrt{T})

Table 1. Comparison of upper and lower bounds on the minimax expected calibration error in the simultaneous forecasting protocol. All of the upper bounds and our lower bounds hold against both adaptive and oblivious adversaries. In this table, T≥1T \ge1 is the total number of interactions, smCE stands for smooth calibration error, LowerCalDist stands for lower calibration distance, and CalDist stands for calibration distance. The lower bounds on lower calibration distance and calibration distance are direct consequences of the lower bound on smooth calibration error, as detailed in Remark 3.2.

Notation. For a positive integer nn, let [n]={1,…,n}[n] = \{1,\ldots,n\}. We write E\mathbb{E} and P\mathbb{P} for expectation and probability, and 1{⋅}\mathbb{1}\{\cdot\} for an indicator. We use calligraphic letters for sets and strategies. The notation O(⋅)O(\cdot) and Ω(⋅)\Omega(\cdot) hides universal positive constants, and Θ(⋅)\Theta(\cdot) denotes matching bounds in both directions. We write a≲ba \lesssim b if a≤Cba \leq Cb for a universal constant C>0C > 0, and a≍ba \asymp b if a≲ba \lesssim b and b≲ab \lesssim a.

Related Work

Sequential Calibration. Sequential calibration studies probabilistic forecasting of binary outcomes, where the forecaster issues a prediction before observing each outcome and the outcomes may depend on previously revealed predictions. Foster and Vohra [9] established the existence of randomized forecasters that achieve asymptotic calibration. Foster [8] subsequently gave an algorithm based on Blackwell’s approachability theorem. For the classical ℓ1\ell_1 calibration error, these approaches yield an O(T2/3)O(T^{2/3}) expected error, and Hart [14] gave a direct minimax proof of this rate. Dagan et al. [5] improved the upper bound to O(T2/3−ϵ)O(T^{2/3-\epsilon}) for a universal constant ϵ>0\epsilon> 0. For smooth calibration error and calibration distance, Qiao and Zheng [22] established an O(T)O(\sqrt{T}) expected error. Arunachaleswaran et al. [1] subsequently proposed the Almost-One-Step-Ahead algorithm, an explicit deterministic forecaster that guarantees calibration distance at most 2T+12\sqrt{T} + 1 on every outcome sequence. Calibration has also been studied across multiple subpopulations ([16, 13]), in omniprediction ([10]), and for forecasts used by downstream decision makers ([19, 17]), including guarantees based on smooth calibration ([15, 11]).

Calibration Lower Bounds and Adversary Design. For the classical ℓ1\ell_1 calibration error, independent fair outcomes already yield an Ω(T)\Omega(\sqrt{T}) lower bound. Qiao and Valiant [21] strengthened this to Ω(T0.528)\Omega(T^{0.528}) via early stopping and sidestepping. Dagan et al. [5] further obtained an Ω(T0.54389)\Omega(T^{0.54389}) lower bound with an oblivious adversary, whose outcomes are generated independently of the forecaster’s predictions. For smooth calibration error and calibration distance, Qiao and Zheng [22] proved an Ω(T1/3)\Omega(T^{1/3}) lower bound with an adversary that generates independent fair bits until a history-dependent stopping time and then repeats a fixed outcome. Our adversary retains the constant continuation after stopping, but replaces the fair bits with Bernoulli outcomes whose mean depends on the cumulative forecasting residual. The extension of this lower bound to oblivious adversaries follows the standard reduction from adaptive to oblivious adversaries in online learning ([4]), which does not apply to calibration error in general, since no deterministic forecaster achieves sublinear ECE ([20, 7]).

Preliminaries

We consider an online binary forecasting game between a forecaster and an adversary over T≥1T \ge1 rounds. At each round t∈[T]t \in[T], the forecaster predicts a probability pt∈[0,1]p_t \in[0,1] and the adversary simultaneously selects an outcome xt∈{0,1}x_t \in\{0,1\}, after which both are revealed. The prediction ptp_t may be randomized and may depend on the history (xs,ps)s<t(x_s,p_s)_{s<t}, but not on the current outcome xtx_t. Formally, a forecaster strategy A\mathcal{A} consists of an internal random variable ξ\xi, drawn before the game independently of the adversary, and deterministic maps (At)t=1T(A_t)_{t=1}^{T}, such that the prediction at round tt is pt=At(x<t,p<t;ξ)p_t = A_t(x_{<t},p_{<t};\xi), where x<t=(x1,…,xt−1)x_{<t}=(x_1,\ldots,x_{t-1}) and p<t=(p1,…,pt−1)p_{<t}=(p_1,\ldots,p_{t-1}); in particular, by induction, ptp_t is a deterministic function of x<tx_{<t} and ξ\xi. Therefore, for simplicity, we drop the dependence on the previous predictions and write pt=At(x<t;ξ)p_t=A_t(x_{<t};\xi) in place of At(x<t,p<t;ξ)A_t(x_{<t},p_{<t};\xi). Depending on how the adversary generates the revealed outcome xtx_t, we consider two settings.

  • In the adaptive setting, xtx_t may be randomized and may depend on the history (xs,ps)s<t(x_s,p_s)_{s<t}, but not on the current prediction ptp_t.

  • In the oblivious setting, the adversary fixes the entire outcome sequence before the game, without observing the forecaster’s predictions, and reveals one outcome per round. In particular, xtx_t cannot depend on any of the forecaster’s predictions.

We write x:=(x1,…,xT)x := (x_1,\ldots,x_T) and p:=(p1,…,pT)p := (p_1,\ldots,p_T) for the outcome and forecast sequences. The forecaster aims to keep the smooth calibration error ([18, 2]) of the realized sequences small. Our goal is to characterize the minimax smooth calibration error in both settings,

VT⋄:=inf⁡Asup⁡B∈B⋄EA,B[smCE⁡(x,p)],⋄∈{adp,obv},(1)V_T^\diamond:= \inf_{\mathcal{A}}\sup_{\mathcal{B}\in\mathcal{B}^\diamond}\mathbb{E}_{\mathcal{A},\mathcal{B}}[\operatorname{smCE}(x,p)], \qquad\diamond\in\{\mathrm{adp},\mathrm{obv}\}, \tag*{(1)}

where A\mathcal{A} ranges over all forecaster strategies Badp\mathcal{B}^{\mathrm{adp}} and Bobv\mathcal{B}^{\mathrm{obv}} denote the sets of adaptive and oblivious adversary strategies, respectively, and (x,p)(x,p) is generated by the interaction between A\mathcal{A} and B\mathcal{B}. That is, EA,B\mathbb{E}_{\mathcal{A},\mathcal{B}} is taken over both the internal randomness ξ\xi of A\mathcal{A} and the randomness of B\mathcal{B}. In particular, for a fixed outcome sequence x∈{0,1}Tx\in\{0,1\}^{T}, we write Bx\mathcal{B}_x for the oblivious adversary that reveals xx, in which case EA,Bx\mathbb{E}_{\mathcal{A},\mathcal{B}_x} is taken over ξ\xi only. Since every oblivious adversary is a special case of an adaptive one, i.e., Bobv⊆Badp\mathcal{B}^{\mathrm{obv}}\subseteq\mathcal{B}^{\mathrm{adp}}, we have VTobv≤VTadpV_T^{\mathrm{obv}}\le V_T^{\mathrm{adp}}. In both settings, smCE⁡(x,p)\operatorname{smCE}(x,p) is the smooth calibration error defined as follows.

Definition 3.1 (Smooth calibration error). Let F\mathcal{F} be the class of all 1-Lipschitz functions from [0,1][0,1] to [−1,1][-1,1]. The smooth calibration error of (x,p)(x,p) is

smCE⁡(x,p)=sup⁡f∈F∑t=1Tf(pt)(xt−pt).(2)\operatorname{smCE}(x,p)=\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}f(p_t)(x_t-p_t). \tag*{(2)}

Definition 3.1 requires the forecaster to be calibrated around every value u∈[0,1]u\in[0,1], while treating nearby forecasts as essentially the same. Specifically, for any fixed u∈[0,1]u\in[0,1], among the rounds in which the forecaster predicts approximately uu, the outcome should equal 1 in approximately a uu fraction of them. Suppose this fails around some uu, say the residuals ∑t:pt≈u(xt−pt)\sum_{t:p_t\approx u}(x_t-p_t) add up to a large positive amount. Then a test ff that is a small positive bump centered around uu and vanishes elsewhere collects this residual while ignoring all other rounds, so smCE⁡\operatorname{smCE} is large. On the other hand, the Lipschitz constraint prevents ff from fluctuating rapidly near uu. Consequently, the residuals ∑t:pt=u′(xt−pt)\sum_{t:p_t=u'}(x_t-p_t) for all u′≈uu'\approx u are effectively grouped together, and an over-prediction at one value can be offset by an under-prediction at a nearby value. This makes smCE⁡\operatorname{smCE} robust to small perturbations of the forecasts, in contrast to the classical expected calibration error (ECE), which treats every forecast value as a separate bin and can change drastically under arbitrarily small perturbations. In short, smCE asks the forecaster to be calibrated at every scale coarser than the resolution of its forecasts, which is the property that matters when forecasts are used by downstream decision makers with smooth responses.

Remark 3.2 (Distance-based measures). Besides smCE, two distance-based calibration measures have been studied: the calibration distance and the lower calibration distance [22] (Błasiok et al. 2023). The calibration distance is the ℓ1\ell_1 distance from pp to the nearest perfectly calibrated forecast sequence,

CalDist⁡(x,p)=inf⁡z∈C(x)∑t=1T∣pt−zt∣,\operatorname{CalDist}(x,p)=\inf_{z\in\mathcal{C}(x)}\sum_{t=1}^{T}|p_t-z_t|,

where C(x)={z∈[0,1]T:∑t:zt=u(xt−u)=0 for all u∈[0,1]}\mathcal{C}(x)=\left\{z\in[0,1]^T:\sum_{t:z_t=u}(x_t-u)=0\text{ for all }u\in[0,1]\right\} is the set of perfectly calibrated forecast sequences. The lower calibration distance relaxes this by allowing randomized repairs,

LowerCalDist⁡(x,p)=inf⁡D∈C(x)∑t=1TEu∼Dt[∣pt−u∣],\operatorname{LowerCalDist}(x,p)=\inf_{\mathcal{D}\in\mathcal{C}(x)}\sum_{t=1}^{T}\mathbb{E}_{u\sim D_t}[|p_t-u|],

where C(x)\mathcal{C}(x) is the set of all D=(Dt)t=1T\mathcal{D}=(D_t)_{t=1}^{T} such that each DtD_t is a finitely supported distribution on [0,1][0,1] and ∑t=1T(xt−α)Dt(α)=0\sum_{t=1}^{T}(x_t-\alpha)D_t(\alpha)=0 for every α∈[0,1]\alpha\in[0,1]. Since every z∈C(x)z\in\mathcal{C}(x) corresponds to the point masses Dt=δztD_t=\delta_{z_t} in C(x)\mathcal{C}(x), we have LowerCalDist⁡(x,p)≤CalDist⁡(x,p)\operatorname{LowerCalDist}(x,p)\leq\operatorname{CalDist}(x,p). Moreover, Błasiok et al. (2023, Theorem 7.3) implies 12smCE⁡(x,p)≤LowerCalDist⁡(x,p)\frac{1}{2}\operatorname{smCE}(x,p)\leq\operatorname{LowerCalDist}(x,p). Therefore, any lower bound on smCE yields a lower bound of the same order on both LowerCalDist and CalDist.

Adversaries and Lower Bounds

In this section, we show that the O(T)O(\sqrt{T}) upper bound is tight against both adaptive and oblivious adversaries. In Section 4.1, we construct a single adaptive adversary that forces every forecaster to incur Ω(T)\Omega(\sqrt{T}) expected smooth calibration error. In Section 4.2, we further extend this adversary, together with the induced lower bound, to oblivious adversaries.

Adaptive Adversary

We summarize the adversary in Algorithm 1, which follows the early-stopping design of Qiao and Zheng [22]. In particular, the adversary keeps track of the cumulative residual

St=∑s=1t(xs−ps),S0=0,S_t=\sum_{s=1}^{t}(x_s-p_s),\qquad S_0=0,

and operates in two phases separated by the threshold r=T/3r=\sqrt{T}/3: an active phase, in which the outcomes are random, and a frozen phase, in which the outcomes are constant. We explain the design of each phase in turn.

Freezing a Large Residual. We start with the easy case. Note that STS_T is the score of the constant test f≡1f \equiv1 and −ST-S_T is the score of f≡−1f \equiv-1, so that smCE(x,p)≥∣ST∣(x,p) \ge|S_T|. Hence, once the residual reaches the threshold, i.e., ∣St∣≥r|S_t| \ge r at some round tt, the adversary only needs to keep it there until the end. This is achieved by raising the flag frozen and repeating the constant outcome b=1{St>0}b = 1\{S_t > 0\} in all remaining rounds. If b=1b = 1, every later increment xt−pt=1−ptx_t-p_t = 1-p_t is nonnegative whatever the forecaster predicts, and symmetrically for b=0b = 0. Therefore ∣St∣|S_t| never decreases after the crossing, and smCE(x,p)≥r=Ω(T)(x,p) \ge r = \Omega(\sqrt{T}).

Random Outcomes Force the Forecaster to Adjust. It remains to handle forecasters that keep the residual below the threshold. In the active phase, the adversary draws xt∼Bernoulli⁡(qt)x_t \sim\operatorname{Bernoulli}(q_t) using fresh randomness, so that the residual behaves like a random walk. To see this, let vt=qt(1−qt)v_t = q_t(1-q_t) be the conditional variance of xtx_t. Ignoring the frozen phase for the moment and summing the expected increments of St2S_t^2 over all rounds, we obtain

E[ST2]≈E[∑t=1Tvt]+2E[∑t=1TSt−1(qt−pt)].(3)\mathbb{E}[S_T^2] \approx\mathbb{E}\left[\sum_{t=1}^{T} v_t\right] + 2\mathbb{E}\left[\sum_{t=1}^{T} S_{t-1}(q_t-p_t)\right]. \tag*{(3)}

When qtq_t is bounded away from 0 and 1, vtv_t is bounded away from zero, so the first sum is of order TT. Hence, if the forecaster makes no adjustment, for example, pt=qtp_t=q_t, then the residual grows to order T\sqrt{T} and reaches the threshold with constant probability. The only way to keep the residual small is to make the cross term in (3) negative, that is, to choose ptp_t such that qt−ptq_t-p_t has the opposite sign of St−1S_{t-1}, which pushes the residual back toward zero.

Penalizing the Adjustment. Such adjustment is detected by the affine test f(u)=1/2−uf(u)=1/2-u. Indeed, conditioning on the history and the current prediction, we have

E[(1/2−pt)(xt−pt)∣history,pt]=(1/2−pt)(qt−pt)=(qt−pt)2+(1/2−qt)(qt−pt).(4)\mathbb{E}[(1/2-p_t)(x_t-p_t)\mid\text{history},p_t]=(1/2-p_t)(q_t-p_t)=(q_t-p_t)^2+(1/2-q_t)(q_t-p_t). \tag*{(4)}

In Qiao and Zheng [22], the outcomes in the active phase are fair bits with qt=1/2q_t=1/2, so the adjustment is penalized only by the quadratic term (qt−pt)2(q_t-p_t)^2. Being second order, this penalty is mild, and the forecaster can control the residual through many small adjustments at little cost. To make the penalty harsher, we let the mean depend on the residual,

qt=12+λSt−1,λ=14r,(5)q_t=\frac{1}{2}+\lambda S_{t-1},\qquad\lambda=\frac{1}{4r}, \tag*{(5)}

so that 1/2−qt=−λSt−11/2-q_t=-\lambda S_{t-1} has the opposite sign of St−1S_{t-1}. The second term in (4) then becomes −λSt−1(qt−pt)-\lambda S_{t-1}(q_t-p_t), which is positive precisely when the forecaster adjusts. In other words, the cross term that the forecaster must make negative to control the residual in (3) reappears with the opposite sign in the affine score. This intensified penalty is the key to the sharper lower bound.

Lower Bounds under Adaptive Adversary

The following theorem presents the lower bound induced by the adaptive adversary in Algorithm 1. Its full proof is deferred to Appendix § 7.§ 1.

Algorithm 1 Residual-Dependent Adversary

1: Input: horizon TT; set r←T/3r \leftarrow\sqrt{T}/3, λ←1/(4r)\lambda\leftarrow1/(4r) 2: S←0S \leftarrow0; frozen ←\leftarrow false 3: for t=1,…,Tt = 1,\ldots,T do 4: &nbsp;&nbsp;&nbsp;&nbsp;if frozen then 5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;xt←bx_t \leftarrow b 6: &nbsp;&nbsp;&nbsp;&nbsp;else 7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Draw xt∼Bernoulli⁡(1/2+λS)x_t \sim\operatorname{Bernoulli}(1/2 + \lambda S) 8: &nbsp;&nbsp;&nbsp;&nbsp;end if 9: &nbsp;&nbsp;&nbsp;&nbsp;Reveal xtx_t, observe the forecaster’s prediction ptp_t, and set S←S+xt−ptS \leftarrow S + x_t - p_t 10: &nbsp;&nbsp;&nbsp;&nbsp;if frozen = false and ∣S∣≥r\lvert S\rvert\ge r then 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;​frozen ←\leftarrow true; b←1{S>0}b \leftarrow\mathbb{1}\{S > 0\} 12: &nbsp;&nbsp;&nbsp;&nbsp;end if 13: end for

Theorem 4.1 (Lower bound against adaptive adversaries). For every integer T≥1T \ge1, let BT\mathcal{B}_T denote the adversary in Algorithm 1. Then every randomized forecasting strategy A\mathcal{A} satisfies

EA,BT[smCE⁡(x,p)]≥9155T.(6)\mathbb{E}_{\mathcal{A},\mathcal{B}_T}[\operatorname{smCE}(x,p)] \ge\frac{9}{155}\sqrt{T}. \tag*{(6)}

Consequently, the minimax smooth calibration error against adaptive adversaries satisfies VTadp≥9T/155V_T^{\mathrm{adp}} \ge9\sqrt{T}/155.

Theorem 4.1 shows that the adversary in Algorithm 1 forces every forecaster to incur Ω(T)\Omega(\sqrt{T}) expected smooth calibration error. This lower bound matches the O(T)O(\sqrt{T}) upper bounds of Qiao and Zheng [22]; Arunachaleswaran et al. [1] up to a universal constant, and thus characterizes the minimax rate of smooth calibration error against adaptive adversaries.

Proof Overview. We now give a brief overview of why this adversary achieves the Ω(T)\Omega(\sqrt{T}) lower bound. Adding λ/2\lambda/2 times (3) to the sum of (4) over all rounds cancels the cross terms and roughly leaves

E[∑t=1T(1/2−pt)(xt−pt)]+λ2E[ST2]≥λ2E[∑t=1Tvt]≳λT,\mathbb{E}\left[\sum_{t=1}^{T}(1/2-p_t)(x_t-p_t)\right] + \frac{\lambda}{2}\mathbb{E}[S_T^2] \ge\frac{\lambda}{2}\mathbb{E}\left[\sum_{t=1}^{T}v_t\right] \gtrsim\lambda T,

whatever the forecaster does, where we drop the nonnegative terms involving (qt−pt)2(q_t-p_t)^2. Consequently, every forecaster faces a dichotomy: either the residual reaches the threshold and the frozen phase forces error at least rr, or the game stays in the active phase for most of the TT rounds and the affine test collects a score of order λT≳T/r\lambda T \gtrsim T/r. As a result, the forecaster always incurs an error of order at least min⁡{r,T/r}\min\{r,T/r\}, and choosing r≍Tr \asymp\sqrt{T} yields the desired Ω(T)\Omega(\sqrt{T}) rate.

Oblivious Adversary

In this subsection, we extend the adaptive adversary of Section 4.1 to the oblivious setting. At a high level, the adversary simulates the entire interaction between Algorithm 1 and the forecaster Algorithm 2 Oblivious Residual-Dependent Adversary

1: Input: horizon TT and forecasting strategy A\mathcal{A}; set r←T/3r \leftarrow\sqrt{T}/3, λ←1/(4r)\lambda\leftarrow1/(4r) 2: // Simulation before the game 3: S←0S \leftarrow0; frozen ←\leftarrow false 4: for t=1,…,Tt = 1,\ldots,T do 5: Set xt←bx_t \leftarrow b if frozen, and draw xt∼Bernoulli⁡(1/2+λS)x_t \sim\operatorname{Bernoulli}(1/2+\lambda S) otherwise 6: Set S←S+xt−μtS \leftarrow S+x_t-\mu_t, where μt←Eξ[At(x<t;ξ)]\mu_t \leftarrow\mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)] 7: if frozen = false and ∣S∣≥r|S| \ge r then 8: frozen ←\leftarrow true; b←1{S>0}b \leftarrow\mathbb{1}\{S>0\} 9: end if 10: end for

Ensure: x=(x1,…,xT)x=(x_1,\ldots,x_T)

before the game, with the forecaster’s actual predictions replaced by their expectations. The detailed mechanism is summarized in Algorithm 2, whose adversary we denote by BTobv\mathcal{B}^{\mathrm{obv}}_T. In the following, we fix a forecasting strategy A\mathcal{A} with internal random variable ξ\xi, and recall from § 3 that its prediction at round tt is At(x<t;ξ)\mathcal{A}_t(x_{<t};\xi).

In particular, Algorithm 2 simulates the interaction between the adversary in Algorithm 1 and a deterministic forecaster Aˉ\bar{\mathcal{A}}, which predicts the average of A\mathcal{A} over its internal randomness. Formally, given the past outcome x<t=(x1,…,xt−1)x_{<t}=(x_1,\ldots,x_{t-1}), Aˉ\bar{\mathcal{A}} predicts

μt=Eξ[At(x<t;ξ)](7)\mu_t=\mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)] \tag*{(7)}

at each round tt. Following Algorithm 1, as long as the residual SS between the simulated outcomes and the predictions of Aˉ\bar{\mathcal{A}} stays below the threshold rr, the adversary draws xt∼Bernoulli⁡(1/2+λS)x_t\sim\operatorname{Bernoulli}(1/2+\lambda S), whose mean moves with the residual. Once the threshold is reached, the adversary repeats the constant outcome that preserves the sign of the residual. Since the simulation uses only the description of A\mathcal{A} but not its realized predictions, the outcome sequence is independent of the internal randomness ξ\xi, so that BTobv\mathcal{B}^{\mathrm{obv}}_T is a valid oblivious adversary. After the simulation, the adversary reveals the simulated outcomes x=(x1,…,xT)x=(x_1,\ldots,x_T) one per round in the actual game, regardless of the forecaster’s actual predictions. Note that BTobv\mathcal{B}^{\mathrm{obv}}_T is a randomized oblivious adversary, i.e., a distribution over outcome sequences x∈{0,1}Tx\in\{0,1\}^T, rather than a single sequence. As we show below, replacing the forecaster’s predictions with their expectations does not help the forecaster. Consequently, this distribution forces a large expected smooth calibration error on at least one sequence in its support, which yields the fixed sequence in Theorem 4.2, so that the lower bound of Theorem 4.1 carries over to oblivious adversaries.

Lower Bounds under Oblivious Adversary

The following theorem presents the lower bound induced by the oblivious adversary in Algorithm 2. Its full proof is deferred to Appendix § 7.§ 2.

Theorem 4.2 (Lower bound against oblivious adversaries). For every integer T≥1T\ge1 and every randomized forecasting strategy A\mathcal{A}, there exists an outcome sequence x∈{0,1}Tx\in\{0,1\}^T such that the oblivious adversary Bx\mathcal{B}_x satisfies

EA,Bx[smCE⁡(x,p)]≥9155T,(8)\mathbb{E}_{\mathcal{A},\mathcal{B}_x}[\operatorname{smCE}(x,p)]\ge\frac{9}{155}\sqrt{T}, \tag*{(8)}

where p=(At(x<t;ξ))t=1Tp = (\mathcal{A}_t(x_{<t};\xi))_{t=1}^{T} is the forecast sequence of A\mathcal{A} on xx. Consequently, the minimax smooth calibration error against oblivious adversaries satisfies VTobv≥9T/155V_T^{\mathrm{obv}} \ge9\sqrt{T}/155.

Theorem 4.2 shows that the Ω(T)\Omega(\sqrt{T}) lower bound continues to hold against oblivious adversaries, with the same constant as Theorem 4.1. Since VTobv≤VTadpV_T^{\mathrm{obv}} \le V_T^{\mathrm{adp}}, combining it with the O(T)O(\sqrt{T}) upper bounds of Qiao and Zheng [22]; Arunachaleswaran et al. [1] gives VTobv≳VTadp≳TV_T^{\mathrm{obv}} \gtrsim V_T^{\mathrm{adp}} \gtrsim\sqrt{T}, which settles the minimax rate of smooth calibration error in both settings. Moreover, recall from Remark 3.2 that smCE⁡(x,p)≤2LowerCalDist⁡(x,p)≤2CalDist⁡(x,p)\operatorname{smCE}(x,p) \le2\operatorname{LowerCalDist}(x,p) \le2\operatorname{CalDist}(x,p) for every outcome sequence xx and forecast sequence pp. Combining this with Theorem 4.2 immediately leads to the following corollary.

Corollary 4.3 (Calibration distance lower bound). For every integer T≥1T \ge1 and every randomized forecasting strategy A\mathcal{A}, the oblivious adversary BxB_x in Theorem 4.2 satisfies

EA,Bx[CalDist⁡(x,p)]≥EA,Bx[LowerCalDist⁡(x,p)]≥9310T.\mathbb{E}_{\mathcal{A},B_x}[\operatorname{CalDist}(x,p)] \ge\mathbb{E}_{\mathcal{A},B_x}[\operatorname{LowerCalDist}(x,p)] \ge\frac{9}{310}\sqrt{T}.

Corollary 4.3 matches, up to a universal constant, the O(T)O(\sqrt{T}) upper bounds on both distance-based measures in Qiao and Zheng [22], which hold against adaptive and hence oblivious adversaries.

Proof Overview. We now give a brief overview of why this adversary achieves the Ω(T)\Omega(\sqrt{T}) lower bound. The proof of Theorem 4.1 only uses the four tests F0={u↦±1,u↦1−u,u↦−u}\mathcal{F}_0 = \{u \mapsto\pm1, u \mapsto1-u, u \mapsto-u\}, whose maximal score

Φ(x,p):=max⁡f∈F0∑t=1Tf(pt)(xt−pt)=max⁡{∣S(x,p)∣,A(x,p)+12∣S(x,p)∣}(9)\Phi(x,p) := \max_{f \in\mathcal{F}_0}\sum_{t=1}^{T} f(p_t)(x_t-p_t) = \max\left\{|S(x,p)|, A(x,p) + \frac{1}{2}|S(x,p)|\right\} \tag*{(9)}

is convex in pp, since S(x,p)=∑t(xt−pt)S(x,p) = \sum_t(x_t-p_t) is affine and A(x,p)=∑t(1/2−pt)(xt−pt)A(x,p) = \sum_t(1/2-p_t)(x_t-p_t) is a convex quadratic in pp. Hence, for every fixed outcome sequence xx, since Φ≤smCE⁡\Phi\le\operatorname{smCE} and Φ(x,⋅)\Phi(x,\cdot) is convex, Jensen’s inequality gives EA,Bx[smCE⁡(x,p)]≥Φ(x,Eξ[p])\mathbb{E}_{\mathcal{A},B_x}[\operatorname{smCE}(x,p)] \ge\Phi(x,\mathbb{E}_{\xi}[p]), where Eξ[p]=(Eξ[At(x<t;ξ)])t=1T\mathbb{E}_{\xi}[p] = (\mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)])_{t=1}^{T} is exactly the forecast sequence of A‾\overline{\mathcal{A}} on xx. That is, the forecaster A\mathcal{A} performs no better than its deterministic average A‾\overline{\mathcal{A}}. Meanwhile, since Algorithm 2 simulates Algorithm 1 against A‾\overline{\mathcal{A}}, the proof of Theorem 4.1 gives Ex∼BTobv[Φ(x,μ)]≥9T/155\mathbb{E}_{x\sim B^{\mathrm{obv}}_T}[\Phi(x,\mu)] \ge9\sqrt{T}/155, where μ=(μ1,…,μT)\mu= (\mu_1,\ldots,\mu_T) is the simulated forecast sequence. Combining the two bounds yields Theorem 4.2.

Conclusion

In this paper, we study the minimax smooth calibration error in sequential binary prediction against both adaptive and oblivious adversaries. In particular, we construct a new adaptive adversary whose outcome mean moves with the forecaster’s cumulative residual and which switches to constant outcomes once the residual becomes large, so that any attempt to compensate for past residuals is penalized by an affine test. We further convert it into an oblivious adversary that simulates this interaction against the forecaster’s average prediction before the game, which loses nothing since the tests used in our analysis have a convex maximal score. We show that both adversaries force every forecaster to incur Ω(T)\Omega(\sqrt{T}) expected smooth calibration error, which improves the Ω(T1/3)\Omega(T^{1/3}) lower bound of Qiao and Zheng [22] and matches the known O(T)O(\sqrt{T}) upper bound, thereby settling the minimax rates of smooth calibration error, as well as of calibration distance and its relaxation, in both settings up to universal constants.

Acknowledgment

The proof ideas are partially developed by GPT-6 Astra under the authors’ guidance. The authors re-organized the proof, verified the proof details, prepared the draft, and take full responsibility for the contents.

Proofs of Main Results

In this section, we provide the full proofs of Theorems 4.1 and 4.2. We first set up the notation and establish a lemma on the interaction with the adaptive adversary, which is shared by both proofs.

Fix an arbitrary, possibly randomized, forecasting strategy A\mathcal{A}, let ξ\xi be its internal random variable, and let Gt=σ(ξ,x1,…,xt)\mathcal{G}_t = \sigma(\xi, x_1, \ldots, x_t) for t=0,1,…,Tt = 0,1,\ldots,T. Since pt=At(x<t;ξ)p_t = \mathcal{A}_t(x_{<t};\xi), the predictions p1,…,ptp_1,\ldots,p_t are Gt−1\mathcal{G}_{t-1}-measurable. Moreover, on the active rounds of Algorithm 1, the outcome xtx_t is drawn from Bernoulli⁡(qt)\operatorname{Bernoulli}(q_t) using fresh randomness that is independent of ξ\xi and of the history. We lower bound the calibration error through two kinds of tests, namely the constant tests f≡1f \equiv1 and f≡−1f \equiv-1, and the affine test f(u)=1/2−uf(u) = 1/2-u, which lead to the following scores:

St=∑s=1t(xs−ps),At=∑s=1t(1/2−ps)(xs−ps).S_t = \sum_{s=1}^{t}(x_s-p_s), \qquad A_t = \sum_{s=1}^{t}(1/2-p_s)(x_s-p_s).

Moreover, we track the first round τ\tau at which the residual reaches the threshold rr,

τ=min⁡({t∈[T]:∣St∣≥r}∪{T}).\tau= \min\left(\{t \in[T] : |S_t| \ge r\} \cup\{T\}\right).

and let H={∣Sτ∣≥r}H = \{|S_\tau| \ge r\} be the event that the threshold is reached, so that τ=T\tau= T on HcH^c. Since max⁡s≤t∣Ss∣\max_{s \le t}|S_s| is Gt\mathcal{G}_t-measurable, τ\tau is a stopping time with respect to {Gt}t=0T\{\mathcal{G}_t\}_{t=0}^{T}.

Lemma A.1. For every integer T≥1T \ge1 and every randomized forecasting strategy A\mathcal{A}, let BT\mathcal{B}_T be the adaptive adversary in Algorithm 1. Then the quantity M:=max⁡{∣Sτ∣,Aτ+∣Sτ∣/2}M := \max\{|S_\tau|, A_\tau+ |S_\tau|/2\} satisfies

EA,BT[M]≥9155T.\mathbb{E}_{\mathcal{A},\mathcal{B}_T}[M] \ge\frac{9}{155}\sqrt{T}.

Proof. We first compute E[Aτ]\mathbb{E}[A_\tau] as follows:

E[Aτ]=∑t=1TE[1{t≤τ}(1/2−pt)(xt−pt)]=∑t=1TE[E[1{t≤τ}(1/2−pt)(xt−pt)∣Gt−1]].\begin{aligned} \mathbb{E}[A_\tau] = \sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{t \le\tau\}(1/2-p_t)(x_t-p_t)\right] \\ &= \sum_{t=1}^{T}\mathbb{E}\left[\mathbb{E}\left[\mathbb{1}\{t \le\tau\}(1/2-p_t)(x_t-p_t)\mid\mathcal{G}_{t-1}\right]\right]. \end{aligned}

For each fixed tt, the indicator 1{t≤τ}\mathbb{1}\{t \le\tau\} is Gt−1\mathcal{G}_{t-1}-measurable, since {t≤τ}={∣Ss∣<r for all s<t}\{t \le\tau\} = \{|S_s| < r\text{ for all }s < t\}, and so are ptp_t and qt=1/2+λSt−1q_t = 1/2+\lambda S_{t-1}. Moreover, on {t≤τ}\{t \le\tau\}, round tt is active, so that E[xt∣Gt−1]=qt\mathbb{E}[x_t\mid\mathcal{G}_{t-1}] = q_t. Therefore,

E[1{t≤τ}(1/2−pt)(xt−pt)∣Gt−1]=1{t≤τ}(1/2−pt)(qt−pt)=1{t≤τ}[(qt−pt)2−λSt−1(qt−pt)].\begin{aligned} \mathbb{E}\left[\mathbb{1}\{t \le\tau\}(1/2-p_t)(x_t-p_t)\mid\mathcal{G}_{t-1}\right] = \mathbb{1}\{t \le\tau\}(1/2-p_t)(q_t-p_t) \\ &= \mathbb{1}\{t \le\tau\}\left[(q_t-p_t)^2-\lambda S_{t-1}(q_t-p_t)\right]. \end{aligned}

where the last equality uses 1/2−pt=(1/2−qt)+(qt−pt)1/2-p_t=(1/2-q_t)+(q_t-p_t) and 1/2−qt=−λSt−11/2-q_t=-\lambda S_{t-1}. Consequently, we see that

E[AT]=∑t=1TE[1{t≤τ}((qt−pt)2−λSt−1(qt−pt))]=E[∑t=1τ((qt−pt)2−λSt−1(qt−pt))].(10)\mathbb{E}[A_T]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbf{1}\{t\leq\tau\}\left((q_t-p_t)^2-\lambda S_{t-1}(q_t-p_t)\right)\right] =\mathbb{E}\left[\sum_{t=1}^{\tau}\left((q_t-p_t)^2-\lambda S_{t-1}(q_t-p_t)\right)\right]. \tag*{(10)}

Similarly, we write ST2S_T^2 as the telescoping sum ST2=∑t=1T1{t≤τ}(St2−St−12)S_T^2=\sum_{t=1}^{T}\mathbf{1}\{t\leq\tau\}(S_t^2-S_{t-1}^2), where each increment satisfies St2−St−12=2St−1(xt−pt)+(xt−pt)2S_t^2-S_{t-1}^2=2S_{t-1}(x_t-p_t)+(x_t-p_t)^2. Therefore,

E[ST2]=∑t=1TE[1{t≤τ}(2St−1(xt−pt)+(xt−pt)2)]=∑t=1TE[E[1{t≤τ}(2St−1(xt−pt)+(xt−pt)2)∣Gt−1]].\begin{aligned} \mathbb{E}[S_T^2]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbf{1}\{t\leq\tau\}\left(2S_{t-1}(x_t-p_t)+(x_t-p_t)^2\right)\right] \\ &=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{E}\left[\mathbf{1}\{t\leq\tau\}\left(2S_{t-1}(x_t-p_t)+(x_t-p_t)^2\right)\mid\mathcal{G}_{t-1}\right]\right]. \end{aligned}

For each fixed tt, all of 1{t≤τ}\mathbf{1}\{t\leq\tau\}, St−1S_{t-1}, ptp_t, and qtq_t are Gt−1\mathcal{G}_{t-1}-measurable. Moreover, on {t≤τ}\{t\leq\tau\}, we have E[xt−qt∣Gt−1]=0\mathbb{E}[x_t-q_t\mid\mathcal{G}_{t-1}]=0 and E[(xt−qt)2∣Gt−1]=vt\mathbb{E}[(x_t-q_t)^2\mid\mathcal{G}_{t-1}]=v_t, where vt=qt(1−qt)v_t=q_t(1-q_t) is the variance of Bernoulli(qt)(q_t). Therefore, writing xt−pt=(xt−qt)+(qt−pt)x_t-p_t=(x_t-q_t)+(q_t-p_t) and expanding,

E[1{t≤τ}(2St−1(xt−pt)+(xt−pt)2)∣Gt−1]=1{t≤τ}[vt+(qt−pt)2+2St−1(qt−pt)],\mathbb{E}\left[\mathbf{1}\{t\leq\tau\}\left(2S_{t-1}(x_t-p_t)+(x_t-p_t)^2\right)\mid\mathcal{G}_{t-1}\right] =\mathbf{1}\{t\leq\tau\}\left[v_t+(q_t-p_t)^2+2S_{t-1}(q_t-p_t)\right],

since all terms that are linear in xt−qtx_t-q_t vanish in conditional expectation. Consequently, we see that

E[ST2]=∑t=1TE[1{t≤τ}[vt+(qt−pt)2+2St−1(qt−pt)]]=E[∑t=1τ[vt+(qt−pt)2+2St−1(qt−pt)]].(11)\begin{aligned} \mathbb{E}[S_T^2]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbf{1}\{t\leq\tau\}\left[v_t+(q_t-p_t)^2+2S_{t-1}(q_t-p_t)\right]\right] \\ &=\mathbb{E}\left[\sum_{t=1}^{\tau}\left[v_t+(q_t-p_t)^2+2S_{t-1}(q_t-p_t)\right]\right]. \tag*{(11)} \end{aligned}

Adding λ/2\lambda/2 times (A.2) to (A.1) cancels the cross terms, which yields

E[AT+λ2ST2]=(1+λ2)E[∑t=1τ(qt−pt)2]+λ2E[∑t=1τvt].(12)\mathbb{E}\left[A_T+\frac{\lambda}{2}S_T^2\right] =\left(1+\frac{\lambda}{2}\right)\mathbb{E}\left[\sum_{t=1}^{\tau}(q_t-p_t)^2\right] +\frac{\lambda}{2}\mathbb{E}\left[\sum_{t=1}^{\tau}v_t\right]. \tag*{(12)}

Now, taking expectations in the bound M≥AT+∣ST∣/2M\geq A_T+|S_T|/2 and applying (A.3), we obtain

E[M]≥E[AT]+12E[∣ST∣]≥λ2E[∑t=1τvt]+12E[∣ST∣−λST2],\mathbb{E}[M]\geq\mathbb{E}[A_T]+\frac{1}{2}\mathbb{E}[|S_T|] \geq\frac{\lambda}{2}\mathbb{E}\left[\sum_{t=1}^{\tau}v_t\right] +\frac{1}{2}\mathbb{E}[|S_T|-\lambda S_T^2],

where we drop the nonnegative term (1+λ/2)E[∑t≤τ(qt−pt)2](1+\lambda/2)\mathbb{E}\left[\sum_{t\leq\tau}(q_t-p_t)^2\right]. We now show that both remaining terms are well behaved. First, since ∣Sτ−1∣<r|S_{\tau-1}|<r and each increment of the residual has magnitude at most one, we have ∣Sτ∣≤r+1|S_\tau|\leq r+1. Since r=T/3≥1/3r=\sqrt{T}/3\geq1/3, we further have r+1≤4r=1/λr+1\leq4r=1/\lambda, so that λ∣Sτ∣≤1\lambda|S_\tau|\leq1 and the last term is nonnegative. Second, on every active round t≤τt\leq\tau, we have ∣St−1∣<r|S_{t-1}| < r, so that ∣qt−1/2∣=λ∣St−1∣<λr=1/4|q_t - 1/2| = \lambda|S_{t-1}| < \lambda r = 1/4 by the choice λ=1/(4r)\lambda= 1/(4r). Hence qt∈(1/4,3/4)q_t \in(1/4, 3/4), which implies vt≥3/16v_t \ge3/16. Therefore, writing m=E[M]m = \mathbb{E}[M], we obtain

m≥3λ32E[τ]=9128TE[τ].(13)m \ge\frac{3\lambda}{32}\mathbb{E}[\tau] = \frac{9}{128\sqrt{T}}\mathbb{E}[\tau]. \tag*{(13)}

That is, a long active phase forces a large affine score. On the other hand, we have M≥∣Sτ∣≥r1{H}M \ge|S_\tau| \ge r\mathbf{1}\{H\}, so that P(H)≤m/r=3m/T\mathbb{P}(H) \le m/r = 3m/\sqrt{T}, i.e., reaching the threshold often forces a large constant score. Since τ=T\tau= T on HcH^c, it follows that

E[τ]≥TP(Hc)≥T−3mT.\mathbb{E}[\tau] \ge T\mathbb{P}(H^c) \ge T - 3m\sqrt{T}.

Substituting this into (A.4) gives m≥9T/128−27m/128m \ge9\sqrt{T}/128 - 27m/128, i.e., m≥9T/155m \ge9\sqrt{T}/155. This completes the proof of Lemma A.1.

Proof of Theorem 4.1

Proof of Theorem 4.1. By Lemma A.1, it suffices to show that smCE⁡(x,p)\operatorname{smCE}(x,p) is lower bounded by M=max⁡{∣Sτ∣,Aτ+∣Sτ∣/2}M = \max\{|S_\tau|, A_\tau+ |S_\tau|/2\}. If τ<T\tau< T, the threshold is reached at round τ\tau, and every later outcome equals b=1{Sτ>0}b = \mathbf{1}\{S_\tau> 0\}. Hence every later increment xt−ptx_t - p_t has the same sign as SτS_\tau. If τ=T\tau= T, there are no later rounds. Therefore, the constant test f≡1f \equiv1 if Sτ≥0S_\tau\ge0, and f≡−1f \equiv-1 otherwise, has score ∣ST∣≥∣Sτ∣|S_T| \ge|S_\tau|, which gives the first lower bound. For the second lower bound, suppose Sτ≥0S_\tau\ge0 and consider f(u)=1−u=(1/2−u)+1/2f(u) = 1-u = (1/2-u)+1/2. Its score over the first τ\tau rounds is Aτ+Sτ/2A_\tau+ S_\tau/2, and its score in every later round is (1−pt)(1−pt)≥0(1-p_t)(1-p_t) \ge0. Similarly, if Sτ<0S_\tau< 0, the test f(u)=−u=(1/2−u)−1/2f(u) = -u = (1/2-u)-1/2 has score Aτ−Sτ/2A_\tau- S_\tau/2 over the first τ\tau rounds and score (−pt)(0−pt)≥0(-p_t)(0-p_t) \ge0 in every later round. All these tests belong to the class F0⊆F\mathcal{F}_0 \subseteq\mathcal{F} of the four tests in (9). In summary, we have

smCE⁡(x,p)≥Φ(x,p)≥max⁡{∣Sτ∣,Aτ+12∣Sτ∣}=M.(14)\operatorname{smCE}(x,p) \ge\Phi(x,p) \ge\max\left\{|S_\tau|, A_\tau+ \frac{1}{2}|S_\tau|\right\} = M. \tag*{(14)}

Taking expectations and applying Lemma A.1 completes the proof of Theorem 4.1.

Proof of Theorem 4.2

We first show that, for a fixed outcome sequence, randomizing the predictions cannot decrease the restricted objective Φ\Phi in (9) below its value at the averaged predictions.

Lemma A.2 (Convexity). For every fixed x∈{0,1}Tx \in\{0,1\}^{T}, the map p↦Φ(x,p)p \mapsto\Phi(x,p) is convex on [0,1]T[0,1]^{T}. Consequently, every random vector y∈[0,1]Ty \in[0,1]^{T} satisfies

E[smCE⁡(x,y)]≥E[Φ(x,y)]≥Φ(x,E[y]).(15)\mathbb{E}[\operatorname{smCE}(x,y)] \ge\mathbb{E}[\Phi(x,y)] \ge\Phi(x,\mathbb{E}[y]). \tag*{(15)}

Proof. The score S(x,p)=∑t=1T(xt−pt)S(x,p) = \sum_{t=1}^{T}(x_t-p_t) is affine in pp, so ∣S(x,p)∣|S(x,p)| is convex in pp. Moreover, expanding each summand of A(x,p)A(x,p) gives

A(x,p)=∑t=1T(1/2−pt)(xt−pt)=∑t=1T(pt2−(xt+1/2)pt+xt2).A(x,p) = \sum_{t=1}^{T}(1/2-p_t)(x_t-p_t) = \sum_{t=1}^{T}\left(p_t^2-(x_t+1/2)p_t+\frac{x_t}{2}\right).

which is a sum of convex quadratic functions of pp. Hence A(x,p)+∣S(x,p)∣/2A(x,p)+|S(x,p)|/2 is convex in pp. Since the pointwise maximum of convex functions is convex, Φ(x,⋅)\Phi(x,\cdot) is convex by (9). The first inequality in (A.6) follows from Φ≤smCE⁡\Phi\le\operatorname{smCE}, since F0⊆F\mathcal{F}_0 \subseteq\mathcal{F}, and the second inequality follows from Jensen’s inequality.

We are now ready to prove Theorem 4.2.

Proof of Theorem 4.2. Fix a randomized forecasting strategy A\mathcal{A} with internal random variable ξ\xi, and let A‾\overline{\mathcal{A}} be the deterministic forecaster in Algorithm 2, which predicts Eξ[At(x<t;ξ)]\mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)] at each round tt. For every x∈{0,1}Tx \in\{0,1\}^{T}, define the expected smooth calibration error of A\mathcal{A} on xx and the forecast sequence of A‾\overline{\mathcal{A}} on xx, respectively, as

g(x):=EA,Bx[smCE⁡(x,p)],p‾(x):=(Eξ[At(x<t;ξ)])t=1T,g(x) := \mathbb{E}_{\mathcal{A},B_x}[\operatorname{smCE}(x,p)], \qquad\overline{p}(x) := \left(\mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)]\right)_{t=1}^{T},

where p=(At(x<t;ξ))t=1Tp = \left(\mathcal{A}_t(x_{<t};\xi)\right)_{t=1}^{T} is the forecast sequence of A\mathcal{A} on xx. For every fixed xx, the outcome sequence does not depend on ξ\xi, so that Eξ[p]=p‾(x)\mathbb{E}_{\xi}[p] = \overline{p}(x) by definition. Applying Lemma A.2 with y=py=p, we obtain

g(x)≥Φ(x,p‾(x))for every x∈{0,1}T.(16)g(x) \ge\Phi(x,\overline{p}(x)) \quad\text{for every } x \in\{0,1\}^{T}. \tag*{(16)}

Next, let x=(x1,…,xT)x = (x_1,\ldots,x_T) be the random outcome sequence generated by BTobv\mathcal{B}^{\mathrm{obv}}_T in Algorithm 2. By construction, the simulation in Algorithm 2 is exactly the interaction between Algorithm 1 and the deterministic forecaster A‾\overline{\mathcal{A}}, whose prediction at round tt is p‾(x)t=Eξ[At(x<t;ξ)]\overline{p}(x)_t = \mathbb{E}_{\xi}[\mathcal{A}_t(x_{<t};\xi)]. Consequently, (x,p‾(x))(x,\overline{p}(x)) has the same distribution as the outcome and forecast sequences generated by the interaction between A‾\overline{\mathcal{A}} and BT\mathcal{B}_T. Applying (A.5) and Lemma A.1 to the deterministic forecaster A‾\overline{\mathcal{A}}, we obtain

Ex∼BTobv[Φ(x,p‾(x))]=EA‾,BT[Φ(x,p)]≥9155T.(17)\mathbb{E}_{x \sim\mathcal{B}^{\mathrm{obv}}_T}\left[\Phi(x,\overline{p}(x))\right] = \mathbb{E}_{\overline{\mathcal{A}},\mathcal{B}_T}[\Phi(x,p)] \ge\frac{9}{155}\sqrt{T}. \tag*{(17)}

Since the left-hand side of (A.8) is an average of Φ(x,p‾(x))\Phi(x,\overline{p}(x)) over x∼BTobvx \sim\mathcal{B}^{\mathrm{obv}}_T, there exists x∈{0,1}Tx \in\{0,1\}^{T} such that Φ(x,p‾(x))≥9T/155\Phi(x,\overline{p}(x)) \ge9\sqrt{T}/155. Plugging this into (A.7), we obtain that, for this specific xx,

EA,Bx[smCE⁡(x,p)]≥Φ(x,p‾(x))≥9155T,\mathbb{E}_{\mathcal{A},B_x}[\operatorname{smCE}(x,p)] \ge\Phi(x,\overline{p}(x)) \ge\frac{9}{155}\sqrt{T},

which proves (8). Finally, since Bx∈BobvB_x \in\mathcal{B}^{\mathrm{obv}} and A\mathcal{A} is arbitrary, (1) gives VTobv≥9T/155V_T^{\mathrm{obv}} \ge9\sqrt{T}/155, which completes the proof of Theorem 4.2.

References

  1. [1]Arunachaleswaran, E. R., Collina, N., Roth, A. and Shi, M. (2025). An elementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM.DOI
  2. [2]Blasiok, J., Gopalan, P., Hu, L. and Nakkiran, P. (2023). A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing.arxiv.org/abs/2211.16886
  3. [3]Brier, G. W. (1950). Verification of forecasts expressed in terms of probability. Monthly weather review 78 1–3.doi.org/10.1175/1520-0493(1950)078<0001:vofeit>2.0.co;2
  4. [4]Cesa-Bianchi, N., Lugosi, G. et al. (2006). Prediction, learning, and games, vol. 1. Cambridge university press, Cambridge.
  5. [5]Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R. and Okoroafor, P. (2025). Breaking the t^(2/3) barrier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing.
  6. [6]Dawid, A. P. (1982). The well-calibrated bayesian. Journal of the American statistical Association 77 605–610.
  7. [7]Dawid, A. P. (1985). Comment: The impossibility of inductive inference. Journal of the American Statistical Association 80 340–341.DOI
  8. [8]Foster, D. P. (1999). A proof of calibration via blackwell’s approachability theorem. Games and Economic Behavior 29 73–78.
  9. [9]Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika 85 379–390.DOI
  10. [10]Garg, S., Jung, C., Reingold, O. and Roth, A. (2024). Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM.arxiv.org/abs/2307.08999
  11. [11]Gopalan, P., Stavropoulos, K., Talwar, K. and Tankala, P. (2026). The importance of being smoothly calibrated. In 7th Symposium on Foundations of Responsible Computing (FORC 2026).
  12. [12]Guo, C., Pleiss, G., Sun, Y. and Weinberger, K. Q. (2017). On calibration of modern neural networks. In International conference on machine learning. PMLR.arxiv.org/abs/1706.04599
  13. [13]Gupta, V., Jung, C., Noarov, G., Pai, M. M. and Roth, A. (2022). Online multivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).DOI
  14. [14]Hart, S. (2025). Calibrated forecasts: The minimax proof. In Matching, Dynamics and Games for the Allocation of Resources: Essays in Celebration of David Gale’s 100th Birthday. Springer, 153–159.arxiv.org/abs/2209.05863
  15. [15]Hartline, J., Wu, Y. and Yang, Y. (2025). Smooth calibration and decision making. In 6th Symposium on Foundations of Responsible Computing (FORC 2025).
  16. [16]Hébert-Johnson, U., Kim, M., Reingold, O. and Rothblum, G. (2018). Multicalibration: Calibration for the (computationally-identifiable) masses. In International conference on machine learning. PMLR.
  17. [17]Hu, L. and Wu, Y. (2024). Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE.DOI
  18. [18]Kakade, S. M. and Foster, D. P. (2008). Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences 74 115–130.
  19. [19]Kleinberg, R., Paes Leme, R., Schneider, J. and Teng, Y. (2023). U-calibration: Forecasting for an unknown agent. In Proceedings of Thirty Sixth Conference on Learning Theory. PMLR.arxiv.org/abs/2307.00168
  20. [20]Oakes, D. (1985). Self-calibrating priors do not exist. Journal of the American Statistical Association 80 339–339.DOI
  21. [21]Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.arxiv.org/abs/2012.03454
  22. [22]Qiao, M. and Zheng, L. (2024). On the distance from calibration in sequential prediction. In The Thirty Seventh Annual Conference on Learning Theory. PMLR.arxiv.org/abs/2402.07458

Paper details

vlnc:W_bheuz6kv
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents