betaFeedback

Reading v1View latest version

WorksComputer Science

A Matching Lower Bound for Online Smooth Calibration

Abstract

We study smooth calibration error in sequential binary prediction, which measures how far a sequence of probabilistic forecasts is from being calibrated and, unlike the classical expected calibration error, is robust to small perturbations of the forecasts. Against adaptive adversaries, 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. In this paper, we close this gap by constructing a new adversary whose outcome mean moves with the forecaster's cumulative residual. This design makes compensating for past residuals costly, and forces every forecaster to incur an expected smooth calibration error of Ω(T)Ω(\sqrt{T}). This lower bound matches the known upper bound up to universal constants, and further implies Ω(T)Ω(\sqrt{T}) lower bounds for calibration distance and lower calibration distance. Overall, our results settle the minimax rates of these calibration measures in sequential prediction. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

Introduction

We study the sequential binary forecasting problem introduced by Foster and Vohra [7]. 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, 5]), uncertainty quantification of machine learning models ([10]), fair risk prediction ([14]), and forecasting for downstream decision makers ([17]).

A natural requirement for the predictions to be interpretable as probabilities is calibration ([5]): 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 [16, 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 [19] 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 [19] 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)\Omega(\sqrt{T}) smooth calibration error unavoidable in sequential prediction?

In this paper, we answer this question affirmatively. We 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 [19] and matching the known O(T)O(\sqrt{T}) upper bound. Since smooth calibration error lower bounds both calibration distance and lower calibration distance up to a constant factor, our result also implies matching Θ(T)\Theta(\sqrt{T}) bounds for these two measures. A comparison of our results and directly related previous results are summarized in Table 1.

Table 1. Comparison of upper and lower bounds on the minimax expected calibration error in the simultaneous adaptive forecasting protocol. 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 consequence of the lower bound on smooth calibration error, as detailed in Remark 3.2.

TypeReferencesmCELowerCalDistCalDist
Upper BoundQiao and Zheng [19]O(T)O(\sqrt{T})O(T)O(\sqrt{T})O(T)O(\sqrt{T})
Lower BoundQiao and Zheng [19]Ω(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})

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{⋅}\mathbf{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 [7] established the existence of randomized forecasters that achieve asymptotic calibration. Foster [6] subsequently gave an algorithm based on Blackwell’s approachability theorem, which randomizes between two neighboring forecast values. For the classical ℓ1\ell_1 calibration error, these approaches yield an O(T2/3)O(T^{2/3}) expected error, and Hart [12] gave a direct minimax proof of this rate. Dagan et al. [4] improved the upper bound to O(T2/3−ϵ)O(T^{2/3-\epsilon}) for a universal constant ϵ>0\epsilon> 0, using a forecaster based on the sign-preservation-with-reuse game. For smooth calibration error and calibration distance, Qiao and Zheng [19] established an O(T)O(\sqrt{T}) expected error through a minimax argument and online learning over a Lipschitz function class. 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 ([14, 11]), in omniprediction ([8]), and for forecasts used by downstream decision makers ([17, 15]), including guarantees based on smooth calibration ([13, 9]).

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 [18] strengthened this to Ω(T0.528)\Omega(T^{0.528}) via early stopping and sidestepping. Their adversary generates Bernoulli outcomes in successive phases and adjusts the probabilities according to the signs of the accumulated forecasting errors, so that errors from earlier phases are difficult to cancel, and its analysis relies on a combinatorial sign-preservation game. Dagan et al. [4] 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 [19] 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. They also showed that, without this stopping mechanism, independent fair outcomes admit a forecaster with only polylogarithmic expected error. Our adversary retains the constant continuation after stopping, but replaces the fair bits with Bernoulli outcomes whose mean depends on the cumulative forecasting residual. Combined with an exact stopped quadratic identity, this yields an Ω(T)\Omega(\sqrt{T}) lower bound on the expected smooth calibration error, matching the known upper bound.

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\}. Both ptp_t and 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 opponent’s action at round tt. Both are then revealed. We write x:=(x1,…,xT)\boldsymbol{x} := (x_1,\ldots,x_T) and p:=(p1,…,pT)\boldsymbol{p} := (p_1,\ldots,p_T) for the outcome and forecast sequences. The forecaster aims to keep the smooth calibration error ([16, 2]) of the realized sequences small. Our goal is to characterize the minimax smooth calibration error

VTsm:=inf⁡Asup⁡BEA,B[smCE⁡(x,p)],(1)V_T^{\mathrm{sm}} := \inf_{\mathcal{A}} \sup_{\mathcal{B}} \mathbb{E}_{\mathcal{A},\mathcal{B}}[\operatorname{smCE}(\boldsymbol{x},\boldsymbol{p})], \tag*{(1)}

where A\mathcal{A} and B\mathcal{B} range over all forecaster and adversary strategies, and p\boldsymbol{p} and x\boldsymbol{x} are the trajectories sampled jointly through the interaction and the distribution given by A\mathcal{A} and B\mathcal{B}, respectively, and smCE⁡(x,p)\operatorname{smCE}(\boldsymbol{x},\boldsymbol{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)(\boldsymbol{x},\boldsymbol{p}) is

smCE⁡(x,p)=sup⁡f∈F∑t=1Tf(pt)(xt−pt).(2)\operatorname{smCE}(\boldsymbol{x},\boldsymbol{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 around uu and vanishes elsewhere collects this residual while ignoring all other rounds, so 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 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 ([2, 19]). The calibration distance is the ℓ1\ell_1 distance from p\boldsymbol{p} to the nearest perfectly calibrated forecast sequence,

CalDist⁡(x,p)=inf⁡z∈C(x)∑t=1T∣pt−zt∣,\operatorname{CalDist}(\boldsymbol{x},\boldsymbol{p}) = \inf_{\boldsymbol{z} \in\mathcal{C}(\boldsymbol{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}(\boldsymbol{x}) = \left\{\boldsymbol{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=1TEqt∼Dt[∣pt−qt∣],\operatorname{LowerCalDist}(\boldsymbol{x},\boldsymbol{p}) = \inf_{\mathcal{D} \in\mathcal{C}(\boldsymbol{x})} \sum_{t=1}^{T} \mathbb{E}_{q_t \sim\mathcal{D}_t}[|p_t-q_t|],

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)\le\operatorname{CalDist}(x,p). Moreover, Blasiok et al. [2] implies 12smCE⁡(x,p)≤LowerCalDist⁡(x,p)\frac{1}{2}\operatorname{smCE}(x,p)\le\operatorname{LowerCalDist}(x,p). Therefore, any lower bound on smCE yields a lower bound of the same order on both LowerCalDist and CalDist.

Adaptive Adversary and Lower Bounds

In this section, we show that the O(T)O(\sqrt{T}) upper bound is tight by constructing a single adaptive adversary that forces every forecaster to incur Ω(T)\Omega(\sqrt{T}) expected smooth calibration error. We describe the adversary in Section 4.1, state the main result in Section 4.2, and prove it in Section 5.

Construction of the adversary

We summarize the adversary in Algorithm 1, which follows the early-stopping design of Qiao and Zheng [19]. 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∣\operatorname{smCE}(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=\mathbb{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)\operatorname{smCE}(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 00 or 11, 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 manage 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.

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 learner’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|S| \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

Penalizing the Adjustment. Such adjustment is detected by the affine test f(u)=1/2−uf(u)=1/2-u. Indeed, conditioning as before,

E[(1/2−pt)(xt−pt)∣history,pt]=(1/2−pt)(qt−pt)=(qt−pt)2+(1/2−qt)(qt−pt).(4)\mathbb{E}\left[(1/2-p_t)(x_t-p_t)\mid\text{history},p_t\right]=(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 [19], 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.

We provide a quick overview of why this adversary achieves Ω(T)\Omega(\sqrt{T}) lower bound. To show this, we add λ/2\lambda/2 times (3) to the sum of (4) over all rounds. This 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]\approx\lambda T,

whatever the forecaster does, where the low order term ∑t=1T(qt−pt)2\sum_{t=1}^{T}(q_t-p_t)^2 is ignored. 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=r−1T\lambda T=r^{-1}T. As a result, we see that the learner always pays for min⁡{r,T/r}\min\{r,T/r\}. Picking r≍Tr\asymp\sqrt{T} leads to the desired Ω(T)\Omega(\sqrt{T}) rate.

Main Results

In this section, we state our main result: the adversary in Algorithm 1 forces every forecaster to incur smooth calibration error of order T\sqrt{T}.

Theorem 4.1 (Smooth calibration lower bound). 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 satisfies VTsm≥9T/155V_T^{\mathrm{sm}} \ge9\sqrt{T}/155.

Theorem 4.1 shows that the O(T)O(\sqrt{T}) upper bound of Qiao and Zheng [19] is tight up to a universal constant, improving their Ω(T1/3)\Omega(T^{1/3}) lower bound. Moreover, recall from Remark 3.2 that smCE⁡(x,p)≲LowerCalDist⁡(x,p)≲CalDist⁡(x,p)\operatorname{smCE}(x,p) \lesssim\operatorname{LowerCalDist}(x,p) \lesssim\operatorname{CalDist}(x,p) for every outcome sequence xx and forecast sequence pp. Combining this with Theorem 4.1 immediately leads to the following corollary.

Corollary 4.2 (Calibration distance lower bound). For every integer T≥1T \ge1, every randomized forecasting strategy A\mathcal{A} satisfies

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

Corollary 4.2 matches the O(T)O(\sqrt{T}) upper bounds on both distance-based measures in Qiao and Zheng [19] up to a universal constant.

Proof of Theorem 4.1

In this section, we provide the full proof of Theorem 4.1.

Proof of Theorem 4.1. Fix an arbitrary, possibly randomized, forecasting strategy A\mathcal{A}. Let G0\mathcal{G}_0 be the trivial σ\sigma-algebra on the probability space, and let Gt=σ(x1,p1,…,xt,pt)\mathcal{G}_t = \sigma(x_1,p_1,\ldots,x_t,p_t) for t∈[T]t \in[T]. Then xtx_t and ptp_t are independent conditioned on Gt−1\mathcal{G}_{t-1}, since the forecaster and the adversary make their decisions simultaneously, and neither observes the other’s private randomness. We lower bound smCE⁡(x,p)\operatorname{smCE}(x,p) 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}.

Our first step is to show that smCE⁡(x,p)\operatorname{smCE}(x,p) is lower bounded by the maximum of ∣Sτ∣|S_\tau| and Aτ+∣Sτ∣/2A_\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≡sign⁡(Sτ)f \equiv\operatorname{sign}(S_\tau) 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. Both tests are 1-Lipschitz and take values in [−1,1][-1,1]. In summary, we have

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

We now take expectations on both sides of (7) to obtain a lower bound on E[smCE⁡(x,p)]\mathbb{E}[\operatorname{smCE}(x,p)]. To do this, 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\}. Moreover, on {t≤τ}\{t\le\tau\}, round tt is active, so that xt∼Bernoulli⁡(qt)x_t\sim\operatorname{Bernoulli}(q_t), where qt=1/2+λSt−1q_t=1/2+\lambda S_{t-1} is Gt−1\mathcal{G}_{t-1}-measurable. Since xtx_t and ptp_t are independent conditioned on Gt−1\mathcal{G}_{t-1}, we have E[xt−qt∣Gt−1,pt]=0\mathbb{E}[x_t-q_t\mid\mathcal{G}_{t-1},p_t]=0 on {t≤τ}\{t\le\tau\}. Therefore,

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

Consequently, we see that

E[Aτ]=∑t=1TE[1{t≤τ}E[(qt−pt)2−λSt−1(qt−pt)∣Gt−1]]=∑t=1TE[1{t≤τ}((qt−pt)2−λSt−1(qt−pt))]=E[∑t=1τ((qt−pt)2−λSt−1(qt−pt))].(8)\begin{aligned} \mathbb{E}[A_\tau]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{t\le\tau\}\mathbb{E}\left[(q_t-p_t)^2-\lambda S_{t-1}(q_t-p_t)\mid\mathcal{G}_{t-1}\right]\right] \\ &=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{t\le\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*{(8)} \end{aligned}

Similarly, we write Sτ2S_\tau^2 as the telescoping sum Sτ2=∑t=1T1{t≤τ}(St2−St−12)S_\tau^2=\sum_{t=1}^{T}\mathbb{1}\{t\le\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[Sτ2]=∑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_\tau^2]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{t\le\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[\mathbb{1}\{t\le\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, both 1{t≤τ}\mathbb{1}\{t\le\tau\} and St−1S_{t-1} are Gt−1\mathcal{G}_{t-1}-measurable. Moreover, on {t≤τ}\{t\le\tau\}, recall that E[xt−qt∣Gt−1,pt]=0\mathbb{E}[x_t-q_t\mid\mathcal{G}_{t-1},p_t]=0, and similarly E[(xt−qt)2∣Gt−1,pt]=vt\mathbb{E}[(x_t-q_t)^2\mid\mathcal{G}_{t-1},p_t]=v_t, where vt=qt(1−qt)v_t=q_t(1-q_t) is the variance of Bernoulli(qt)(q_t). Therefore,

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

where the second equality uses E[xt−qt∣Gt−1,pt]=0\mathbb{E}[x_t-q_t\mid\mathcal{G}_{t-1},p_t]=0 for the term 2St−1(xt−qt)2S_{t-1}(x_t-q_t), and the last equality uses this identity again for the cross term 2(xt−qt)(qt−pt)2(x_t-q_t)(q_t-p_t), together with E[(xt−qt)2∣Gt−1,pt]=vt\mathbb{E}[(x_t-q_t)^2\mid\mathcal{G}_{t-1},p_t]=v_t.

Consequently, we see that

E[Sτ2]=∑t=1TE[1{t≤τ}E[vt+(qt−pt)2+2St−1(qt−pt)∣Gt−1]]=∑t=1TE[1{t≤τ}[vt+(qt−pt)2+2St−1(qt−pt)]]=E[∑t=1T[vt+(qt−pt)2+2St−1(qt−pt)]].(9)\begin{aligned} \mathbb{E}[S_\tau^2]=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{1}\{t\leq\tau\}\mathbb{E}\left[v_t+(q_t-p_t)^2+2S_{t-1}(q_t-p_t)\mid\mathcal{G}_{t-1}\right]\right] \\ &=\sum_{t=1}^{T}\mathbb{E}\left[\mathbb{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}^{T}\left[v_t+(q_t-p_t)^2+2S_{t-1}(q_t-p_t)\right]\right]. \tag*{(9)} \end{aligned}

Adding λ/2\lambda/2 times (9) to (8) cancels the cross terms, which yields

E[Aτ]+λ2E[Sτ2]=(1+λ2)E[∑t=1τ(qt−pt)2]+λ2E[∑t=1τvt].(10)\mathbb{E}[A_\tau]+\frac{\lambda}{2}\mathbb{E}[S_\tau^2]=\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*{(10)}

Now, taking expectations in the bound smCE⁡(x,p)≥Aτ+∣Sτ∣/2\operatorname{smCE}(x,p)\geq A_\tau+|S_\tau|/2 from (7) and applying (10), we obtain

E[smCE⁡(x,p)]≥E[Aτ]+12E[∣Sτ∣]≥λ2E[∑t=1τvt]+12E[∣Sτ∣−λSτ2],\mathbb{E}[\operatorname{smCE}(x,p)]\geq\mathbb{E}[A_\tau]+\frac{1}{2}\mathbb{E}[|S_\tau|]\geq\frac{\lambda}{2}\mathbb{E}\left[\sum_{t=1}^{\tau}v_t\right]+\frac{1}{2}\mathbb{E}[|S_\tau|-\lambda S_\tau^2],

where we drop the nonnegative term (1+λ/2)E[∑t≤τ(qt−pt)2](1+\lambda/2)\mathbb{E}[\sum_{t\leq\tau}(q_t-p_t)^2]. 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\geq3/16. Therefore, writing m=E[smCE⁡(x,p)]m=\mathbb{E}[\operatorname{smCE}(x,p)], we obtain

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

That is, a long active phase forces a large affine score. On the other hand, by (7), we have smCE⁡(x,p)≥∣Sτ∣≥r1{H}\operatorname{smCE}(x,p)\geq|S_\tau|\geq r\mathbb{1}\{H\}, so that P(H)≤m/r=3m/T\mathbb{P}(H)\leq 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]\geq T\mathbb{P}(H^c)\geq T-3m\sqrt{T}.

Substituting this into (11) gives m≥9T/128−27m/128m\geq9\sqrt{T}/128-27m/128, i.e., m≥9T/155m\geq9\sqrt{T}/155. This completes the proof of Theorem 4.1.

Conclusion

In this paper, we study the minimax smooth calibration error in sequential binary prediction against adaptive adversaries. In particular, we construct a new 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 show that this adversary forces 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 [19] and matches the known O(T)O(\sqrt{T}) upper bound, thereby settling the minimax rate of smooth calibration error, as well as of calibration distance and its relaxation, up to universal constants. Currently, our lower bound relies on an adversary that adapts to the forecaster’s past predictions. Determining the optimal rate against oblivious adversaries, whose outcomes cannot depend on the forecasts, remains an interesting direction for future work.

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.

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]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.
  5. [5]Dawid, A. P. (1982). The well-calibrated bayesian. Journal of the American statistical Association 77 605–610.
  6. [6]Foster, D. P. (1999). A proof of calibration via blackwell’s approachability theorem. Games and Economic Behavior 29 73–78.
  7. [7]Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika 85 379–390.DOI
  8. [8]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
  9. [9]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).
  10. [10]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
  11. [11]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
  12. [12]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
  13. [13]Hartline, J., Wu, Y. and Yang, Y. (2025). Smooth calibration and decision making. In 6th Symposium on Foundations of Responsible Computing (FORC 2025).
  14. [14]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.
  15. [15]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
  16. [16]Kakade, S. M. and Foster, D. P. (2008). Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences 74 115–130.
  17. [17]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
  18. [18]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
  19. [19]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
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