Efficient Sequential Calibration with OpT 2{3´ϵq Error Bound Zihan Zhang Department of CSE, HKUST [email protected]
arXiv:2607.12928v1 [cs.LG] 14 Jul 2026
Abstract We study the online binary sequential calibration problem. A recent breakthrough by Dagan et al. (2025) overcomes the classical T 2{3 barrier for calibration error. Building on this result, we present an efficient randomized forecaster that achieves an expected calibration error OpT 2{3´ε q for some constant ε ą 0. Our forecaster combines the SPR-C ALIBRATION procedure (Dagan et al., 2025) with an outer Blackwell-style correction layer. The SPR-C ALIBRATION procedure controls calibration with respect to a surrogate sequence of conditional-mean estimates, while the correction layer controls the additional error incurred when these surrogates are used to approximate the true outcomes. The analysis decomposes the total calibration error into the surrogate calibration error and the residual discrepancy between the surrogate sequence and the true outcomes. The former is bounded by the SPR-C ALIBRATION guarantee in Dagan et al. (2025), and the latter is controlled using a quadratic potential argument together with the sparsity of the SPR-C ALIBRATION forecaster.
1
Introduction
Calibration captures a basic reliability requirement for probabilistic predictions: when a forecaster repeatedly assigns probability p to an event, the event should occur on roughly a p-fraction of those rounds. This notion is important because probability forecasts are often used directly in downstream decisions, such as risk assessment, medical prediction, weather forecasting, and machine-learning systems that report confidence scores (Dawid, 1982; Guo et al., 2017; Kuleshov et al., 2018; Hébert-Johnson et al., 2018). In these applications, the numerical value of a forecast matters, not only the ranking of alternatives: a prediction of 0.8 should be interpretable as an event that happens about 80% of the time. Sequential calibration studies how to achieve this reliability guarantee when predictions are made online and the data may arrive adaptively or non-stationarily. In this work, we consider the online sequential calibration problem initiated by Foster and Vohra (1998). At each round t, a forecaster announces a probability pt P r0, 1s for a binary outcome yt P t0, 1u. The standard ℓ1 -calibration error after T rounds is ˇ ˇ ˇ ÿ ˇˇ ÿ ˇ CalErrT “ pp ´ yt qˇ , ˇ ˇ ˇ pPPT tďT :pt “p
where PT is the set of distinct predictions used by the forecaster. Classical algorithms achieve calibration error of order T 2{3 . One way to obtain this rate is through a discretization and Blackwell-approachability argument (Foster, 1999): the forecaster restricts predictions to a finite grid of size m, controls the calibration residuals ? over this grid using an approachability strategy, and balances the approachability term Op mT q with the discretization term OpT {mq. Optimizing over m gives m — T 1{3 , and hence calibration error OpT 2{3 q. This
approach is conceptually clean and computationally efficient, but it also highlights the longstanding OpT 2{3 q barrier. A recent breakthrough by Dagan et al. (2025) showed that the classical OpT 2{3 q upper bound is not intrinsic. They introduced an algorithm, which we refer to as SPR-C ALIBRATION, that achieves a calibration error bound of order OpT 2{3´ε q for some constant ε ą 0, thereby breaking the T 2{3 barrier for the first time. Despite this breakthrough, obtaining an efficient OpT 2{3´ε q guarantee in the sequential setting is not immediate. The SPR-C ALIBRATION algorithm (Dagan et al., 2025) is analyzed through a minimax reduction that allows the proof to work in a full-information model, where the forecaster is given the conditional mean et “ Eryt | Ft´1 s at each round. This idea goes back to the minimax proof of calibration (Hart, 2022): if the forecaster knew the adversary’s mixed strategy, then it could simply predict the induced conditional probability of the next outcome; the minimax theorem then converts this observation into the existence of a randomized forecasting strategy that is calibrated against every adversary. However, this minimax transformation is primarily an existence argument rather than a computationally tractable algorithm. It then naturally raises the question: Is there an efficient algorithm with OpT 2{3´ε q calibration error? In this work, we answer this problem affirmatively. Theorem 1. There exists a forecaster (see Algorithm 5), such that for any sequence tyt uTt“1 P t0, 1uT , the expected calibration error ErCalErrT s is bounded by Oplog2 pT q ¨ T 2{3´εAB {18 q, where εAB ą 0 is the same as the constant ε in Theorem 1.3 of Dagan et al. (2025). Moreover, the computation cost of the algorithm is OpT 7{2 log2 pT qq. Our algorithm is based a natural combination of the SPR-C ALIBRATION procedure of Dagan et al. (2025) with an outer Blackwell-style correction layer. At each round t, the algorithm first forms a surrogate estimate ert of the conditional mean and then passes this value to the calibration procedure of Dagan et al. (2025). Since calibration is ultimately measured against the realized outcome yt , using the surrogate ert introduces an additional source of error. To control this error, the algorithm augments the underlying calibration procedure with a Blackwell-style correction layer. The analysis separates the total calibration error into two components: et uTt“1 , and the discrepancy between the surrogate the calibration error with respect to the surrogate sequence tr means and the realized outcomes. The first component is controlled directly by the guarantee of Dagan et al. (2025); the second is bounded using a quadratic potential argument together with the sparsity property of their calibration algorithm.
1.1
Related Works
Calibration and adversarial forecasting. Calibration has a long history as a criterion for evaluating probabilistic forecasts. Dawid (1982) emphasized calibration as a basic consistency requirement for subjective probabilities, and Foster and Vohra (1998) initiated the adversarial sequential calibration problem studied in this paper. Their work showed that randomized forecasters can be calibrated against arbitrary binary outcome sequences and gave the classical OpT 2{3 q calibration-error guarantee. Several subsequent works gave alternative proofs and perspectives on calibration, including the myopic minimax construction (Fudenberg and Levine, 1999), the Blackwell-approachability proof (Foster, 1999), the minimax proof (Hart, 2022), and the geometric approachability proof (Mannor and Stoltz, 2010). Approachability, regret, and calibration. Blackwell’s approachability theorem (Blackwell, 1956) is one of the central tools behind adversarial calibration. In the approachability formulation, calibration residuals are 2
treated as coordinates of a vector-valued payoff, and the forecaster chooses predictions so that the cumulative payoff approaches an appropriate target set. This connection was made explicit by Foster (1999) and was further developed through geometric and online-learning viewpoints (Mannor and Stoltz, 2010; Abernethy et al., 2011). Calibration is also closely related to regret minimization: Foster and Vohra (1999) connected calibration and internal regret, and calibrated learning rules are known to lead to correlated equilibrium in repeated games (Foster and Vohra, 1997). The broader connections between prediction of individual sequences, regret, and game-theoretic learning are surveyed in Cesa-Bianchi and Lugosi (2006). Rates for sequential calibration. The optimal rate of ℓ1 -calibration error has been a central question in sequential calibration. The classical upper bound is OpT 2{3 q, obtained by balancing the discretization error of a finite grid with an approachability-type residual term (Foster ? and Vohra, 1998; Abernethy et al., 2011). For many years, the only general lower bound was the trivial Ωp T q bound obtained from independent fair coin ? flips. Qiao and Valiant (2021) gave the first super- T lower bound, proving an ΩpT 0.528 q lower bound via the sign-preservation game. Dagan et al. (2025) recently broke the T 2{3 upper-bound barrier by introducing sign preservation with reuse (SPR), proving that improved SPR strategies yield calibration error OpT 2{3´ε q for some constant ε ą 0. They also improved the lower bound to ΩpT 0.54389 q, leaving a gap between the known upper and lower exponents.
2
Problem Setting
We follow the sequential calibration setup of Dagan et al. (2025). Fix a time horizon T . At each round t P rT s, the forecaster outputs a probability prediction pt P r0, 1s, and the environment outputs an outcome yt P t0, 1u. The prediction pt is interpreted as the forecaster’s announced probability that yt “ 1. The adversary may be adaptive, in the sense that its choice at time t may depend on the past history Ht :“ tpps , ys q : s ă tu, but it does not observe the current prediction pt before choosing yt . Let Pt :“řtps : s ď tu denote the set of distinct probability values actually output up to time t. Define Et ppq “ sďt:ps “p pp ´ ys q. The cumulative ℓ1 -calibration error at time t is CalErrt :“
ÿ pPPt
ˇ ˇ ˇ ÿ ˇˇ ÿ ˇ |Et ppq| “ pp ´ ys qˇ . ˇ ˇsďt:p “p ˇ pPPt
s
When the forecaster is randomized, all quantities above are random variables. We measure performance by expected calibration error ErCalErrT s, where the expectation is over the forecaster’s internal randomness. We next recall the sign-preservation with reuse game, abbreviated as SPR, introduced in Dagan et al. (2025). Definition 1 (Sign-preservation with reuse). For n, s P N, the game SPRpn, sq is played between two players, called Player-P and Player-L. The game consists of n cells, indexed by rns “ t1, . . . , nu, all of which are initially empty. The game lasts for at most s rounds. In each round, the following steps occur: 1. Player-P may terminate the game. Otherwise, Player-P chooses an empty cell j P rns. 2. After observing j, Player-L may remove any subset of the ´ signs in cells strictly to the left of j, and any subset of the ` signs in cells strictly to the right of j. 3. Player-L then places either a ` sign or a ´ sign in cell j. 3
A cell whose sign has been removed becomes empty and may therefore be chosen again in a later round. Player-P aims to maximize the number of signs remaining on the board at the end of the game, while Player-L aims to minimize this quantity.
3
The SPR-C ALIBRATION Algorithm
In this section, we recall the SPR-C ALIBRATION construction of Dagan et al. (2025) and the properties needed in our analysis.
3.1
Deterministic Implementation of SPR-C ALIBRATION
This subsection specifies the version of SPR-C ALIBRATION used by our outer algorithm. For completeness, we present the main algorithm of Dagan et al. (2025) in Algorithm 1, together with its key subroutines: simulateGame in Algorithm 2, the recursive A-procedure in Algorithm 3, and the recursive B-procedure in Algorithm 4. The feature needed by Algorithm 5 is a deterministic one-step transition. Given the pre-round state S (see Definition 2), a round index t, and an input z P r0, 1s, define StepSPR pS, t, zq “ pp, S ` q, where p is the forecast returned by one round of SPR-C ALIBRATION and S ` is the resulting state. We fix all loop orders, tie-breaking rules, and boundary conventions below, so this transition is well-defined. We then set PredictSPR pS, t, zq :“ p, UpdateSPR pS, t, zq :“ S ` . Scales and SPR instances. Let τ :“ rlog2 T s, and let T :“ 2τ . Run the first T rounds of a subroutine initialized for the padded horizon T . Since T ď T ă 2T , this padding changes all asymptotic bounds by at most a constant factor. We assume τ ě 2; the finitely many smaller horizons can be handled by any fixed forecasting rule. Fix an integer 1 ď h ă τ . Define Ih :“ t1, . . . , τ ´ hu, Ji :“ ti ` 1, . . . , i ` hu and Ci :“ t1, . . . , 2i u. For every i P Ih , j P Ji , and ℓ P t0, 1u, the subroutine maintains one SPR instance Gi,j,ℓ with cell set Ci . The index i specifies the spatial resolution, j specifies the time scale, and ℓ separates the even and odd dyadic intervals at resolution 2´pi`1q . Cells, intervals, and forecast values. For z P r0, 1s, let mi pzq :“ min i pzq ` 1. We define mi pzq mod 2 and ci pzq :“ mi pzq´ℓ 2 ` ˘ cellpi, j, zq :“ ci pzq, Gi,j,ℓi pzq .
␣X i`1 \ i`1 ( 2 z ,2 ´ 1 , ℓi pzq :“
Thus, j selects the SPR instance at the desired time scale, while i and z determine the parity and cell.
4
For c P Ci and ℓ P t0, 1u, write m “ 2pc ´ 1q ` ℓ and define $„ ˙ m m`1 ’ ’ ’ & 2i`1 , 2i`1 , intervalpc, Gi,j,ℓ q :“ „ i`1 ȷ ’ 2 ´1 ’ ’ ,1 , % 2i`1
m ă 2i`1 ´ 1, m “ 2i`1 ´ 1.
In this way, every z P r0, 1s is assigned to a unique cell1 . For a sign σ P t`, ´u, define $ maxt0, 2pc ´ 1q ` ℓ ´ 1u ’ ’ , σ “ `, & 2i`1 probpc, σ, Gi,j,ℓ q :“ i`1 ’ ’ % mint2pc ´ 1q ` ℓ ` 2, 2 u , σ “ ´. i`1 2 The SPR state. To formalize the subroutines that we borrow from the SPR-C ALIBRATION algorithm of Dagan et al. (2025), we first give a precise definition of the state of an SPR-C ALIBRATION instance. Definition 2 (SPR state). For each instance G “ Gi,j,ℓ , the subroutine stores biasG : Ci Ñ R, the accumulated surrogate bias in each cell, σG : Ci Ñ t`, ´, ∅u, the current SPR sign configuration, LG , the mutable state of the explicit A{B labeler. Initially, we set biasG pcq “ 0 and σG pcq “ ∅ for every instance G and cell c. The labeler state LG is initialized by Aroot :“ A. initializep1, 2i , 0q. G Accordingly, a query to calibration cell c is passed directly to the labeler as query c. The complete state is SPR Slocal “ tbiasG , σG , LG uiPIh ,jPJi ,ℓPt0,1u .
(1)
Moreover, to deal with the reduced transcript (see Definition 3), we need to keep a record of all historical states as follows: SPR StSPR “ tSlocal,s usďt´1 ,
(2)
SPR is the local state defined as (1) at round s. where Slocal,s
During the learning process, the state StSPR is updated to according to the changes in biasG , σG , and LG for each instance G “ Gi,j,ℓ . Deterministic conventions. All loops are executed in increasing lexicographic order of their indices. If more than one cell is admissible in the bias-removal phase, the smallest admissible cell is selected. Finally, define sgnpbq “ ` for b ě 0 and sgnpbq “ ´ for b ă 0. These conventions make the algorithm deterministic. Placement of bias. Given an input z, the algorithm first attempts to reduce a previously accumulated bias of sufficiently large magnitude. If no such bias-reduction update is available, the algorithm selects an SPR instance on which the cell containing z has sufficiently small current bias and adds the new bias 1
We use this half-open interval convention to make the interval assignment explicit.
5
Algorithm 1 SPR-C ALIBRATION (Algorithm 1 in Dagan et al. (2025)) Require: Pre-round state S, round index t, and input z P r0, 1s. 1: Bias-removal phase. 2: for i P Ih in increasing order do 3: for j P Ji in increasing order do 4: pc, Gq Ð cellpi, j, zq. Ź Locate the SPR instance. 5: B Ð tc1 ă c : biasG pc1 q ă ´1u Y tc1 ą c : biasG pc1 q ą 1u. Ź Find cells with removable bias. 6: if B ‰ ∅ then 7: c̄ Ð min B. Ź Deterministic rule to rank the cells. , σ Ð sgnpbiasG pc̄qq, / . p Ð probpc̄, σ, Gq, 8: Ź Update the selected SPR instance G. / biasG pc̄q Ð biasG pc̄q ` pz ´ pq. 9: Update S according to (2). Ź Update the state S after updating the SPR instance G. 10: return pp, Sq. 11: end if 12: end for 13: end for 14: Bias-placement phase. 15: for i P Ih in increasing order do 16: for j P Ji in increasing order do 17: pc, Gq Ð cellpi, j, zq. Ź Locate the SPR instance. 18: if | biasG pcq| ă 2j´i then 19: if σG pcq “ ∅ then 20: simulateGamepc, Gq. Ź Call the SPR instance; the labeling procedure LG is updated. 21: end if , σ Ð σG pcq, / . p Ð probpc, σ, Gq, 22: Ź Update the selected SPR instance G. / biasG pcq Ð biasG pcq ` pz ´ pq. 23: Update S according to (2). Ź Update the state S after updating the SPR instance G. 24: return pp, Sq. 25: end if 26: end for 27: end for
contribution to that cell. In particular, if the selected cell does not carry an SPR sign, the algorithm first invokes simulateGame to place one. The simulateGame subroutine. A call to simulateGame performs one legal move of the SPR game on an SPR instance whose queried cell is empty. It removes every minus sign strictly to the left of the queried cell and every plus sign strictly to its right, asks the explicit A{B strategy for the new sign, and records that sign in the queried cell. The explicit A{B Player–L strategy. Each SPR instance uses the deterministic Player–L strategy of Dagan et al. (2025). It is defined by two mutually recursive procedures, A and B. An A-object controls an interval rl, rs and an integer bias parameter b. At a leaf it returns sgnpbq. At an internal node it delegates to its currently active B-object and restarts that object whenever the latter returns the restart symbol K. A B-object splits its interval into two halves, stores one child A-object for each half, and uses four phases to compare how often the two halves have been queried. The parameter M is a running guess for the relevant execution length and implements a doubling mechanism. All counters, phases, child objects, and pointers are
6
Algorithm 2 simulateGamepc, Gq Require: An empty cell c P Ci “ r2i s of an SPR instance G “ Gi,j,ℓ . Ź Remove the ´ signs left to c.
1: 2: for each c1 P Ci with c1 ă c do 3: if σG pc1 q “ ´ then 4: σG pc1 q Ð ∅. 5: end if 6: end for 7: 8: for each c1 P Ci with c1 ą c do 9: if σG pc1 q “ ` then 10: σG pc1 q Ð ∅. 11: end if 12: end for 13: s Ð LG . labelpcq. 14: σG pcq Ð s.
Ź Remove the ` signs right to c.
Ź Run the SPR procedure to decide the sign of c.
Algorithm 3 Player–L procedure A (Algorithm 3 in Dagan et al. (2025)) Require: Integers 1 ď l ď r and bias parameter b P Z. 1: Procedure A. initializepl, r, bq: 2: if l ă r then 3: recentB Ð B. initializepl, r, b, 1q. 4: else 5: recentB Ð ∅. 6: end if 7: count Ð 0. 8: Procedure A. labelpsq, where s P rl, rs: 9: if l “ r then 10: return sgnpbq. 11: else 12: count Ð count `1. 13: σ Ð recentB . labelpsq. 14: if σ “K then 15: recentB Ð B. initializepl, r, b, countq. 16: count Ð 1. 17: return recentB . labelpsq. 18: else 19: return σ. 20: end if 21: end if
part of the labeler state LG . Thus, after LG is included in StSPR , a call to simulateGame is a deterministic function of the copied state and the queried cell.
3.2
Theoretical Guarantees of SPR-C ALIBRATION
We recall several properties of SPR-C ALIBRATION from Dagan et al. (2025). The half-open interval convention used in our presentation only makes the assignment of dyadic boundary points explicit. It preserves the containment, ordering, and dyadic counting properties used in the cited proofs, and therefore does not affect the following bounds.
7
Algorithm 4 Player–L procedure B (Algorithm 4 in Dagan et al. (2025)) Require: Integers 1 ď l ă r, bias parameter b P Z, and guess parameter M P N. 1: Procedure B. initializepl, r, b, M q: 2: m Ð tpl ` rq{2u. 3: Ar0s Ð A. initializepl, m, bq. 4: Ar1s Ð A. initializepm ` 1, r, bq. 5: prevHalf Ð ´1. 6: countHalfr0s Ð 0, countHalfr1s Ð 0. 7: phase Ð 1. 8: Procedure B. labelpsq, where s P rl, rs: 9: half Ð 0 if s ď m, and half Ð 1 otherwise. 10: countHalfrhalfs Ð countHalfrhalfs ` 1. 11: if phase “ 1 then 12: if countHalfrhalfs “ M and M ď countHalfr1 ´ halfs ď 2M then 13: phase Ð 2. 14: else if countHalfrhalfs “ M and countHalfr1 ´ halfs ą 2M then 15: phase Ð 3. 16: end if 17: else if phase “ 2 then 18: if half ‰ prevHalf then 19: return K. 20: end if 21: if countHalfrhalfs “ 2 countHalfr1 ´ halfs ` 1 then 22: phase Ð 3. 23: end if 24: else if phase “ 3 then 25: if countHalfrhalfs “ tcountHalfr1 ´ halfs{2u ` 1 then 26: phase Ð 4. 27: if half “ 0 then 28: Ar0s Ð A. initializepl, m, b ` 1q. 29: else 30: Ar1s Ð A. initializepm ` 1, r, b ´ 1q. 31: end if 32: end if 33: else if phase “ 4 then 34: if countHalfrhalfs ą countHalfr1 ´ halfs then 35: return K. 36: end if 37: end if 38: σ Ð Arhalfs. labelpsq. 39: prevHalf Ð half. 40: return σ.
Let LAB be the deterministic Player–L strategy implemented by Algorithms 3 and 4, with the root A-instance initialized on the n-cell board with bias parameter b “ 0. We write SimABn for the composite transition implemented by simulateGame: on a legal query to an empty cell, it first performs the SPR sign-removal step, then advances the A{B labeling state, and finally places the sign returned by that state. ` ˘m A full transcript of this composite process is a finite sequence H “ ptr , cr , σr q r“1 , where t1 ă ¨ ¨ ¨ ă tm are the ambient calibration rounds, cr P rns is empty immediately before the r-th call, and σr P t`, ´u is the sign returned by the evolving A{B state.
8
For a signed call pc, σq and a later queried cell c1 , define $ 1 ’ &1, σ “ ´ and c ă c , ` ˘ kill pc, σq, c1 :“ 1, σ “ ` and c ą c1 , ’ % 0, otherwise. Thus, killppc, σq, c1 q “ 1 when the sign-removal step of a call to c1 erases the sign σ previously placed at c. Definition 3 (Reduced transcript). Set ` R0 :“ H. ˘ Having constructed Rr´1 , repeatedly delete the last entry pt, c, σq of the current list while kill pc, σq, cr “ 1, and then append ptr , cr , σr q. Let RedpHq :“ Rm and rlenpHq :“ |RedpHq| . The signs in RedpHq are inherited from the full transcript. This is a deterministic realization of the adjacent-deletion reduction used in the proof of Lemma A.2 of Dagan et al. (2025). By recording the SPR state associated with every prefix of the reduced transcript, the A/B labeling procedure on reduced transcripts is deterministic and well defined. More precisely, at step τ , let Rτ ´1 be the current r Ð Rτ ´1 . When R r is reduced transcript and let cτ be the incoming cell. We initialize a temporary transcript R r and restore the state nonempty and its last entry pt, c, σq is killed by the request cτ , we remove pt, c, σq from R r associated with the shortened transcript. If R becomes empty, we restore the initial state. Once this deletionr is empty or its last entry is not killed by cτ . We then query the and-rollback procedure terminates, either R r } ptτ , cτ , στ q, where Player–L strategy at cτ using the restored state, obtaining a label στ , and define Rτ :“ R } denotes concatenation. Finally, we record the state resulting from this query as the state associated with the new reduced transcript Rτ . Let SurvpHq be the number of occupied cells on the actual board after executing the full transcript H. Definition 4 ( Reduced-execution value of the composite A{B procedure). For n, m, s P N, define the horizon-restricted value Valred AB pn; m, sq :“ max SurvpHq, H
where the maximum is over all full legal transcripts H generated by SimABn against arbitrary adaptive choices of Player–P, subject to |H| ď m and rlenpHq ď s. We also define the uniform reduced-execution value red Valred AB pn, sq :“ sup ValAB pn; m, sq. 1ďmďT
Lemma 1. For any input sequence z1 , . . . , zT P r0, 1s, if SPR-C ALIBRATION is run with input tzt uTt“1 , then the bias term satisfies ˇ ˇ ¸ ˜ ˇ ˇ τÿ ´h i`h τÿ ´h i`h ÿ ˇ ÿ ÿ ÿ ˇ i τ ´j`1 ˇ pzt ´ pt qˇˇ ď O 2j´i Valred q` mint2i , 2τ ´h´i u . AB p2 , 2 ˇ ˇ ˇ i“1 j“i`1 i“1 j“i`1 pPPT tPrT s:pt “p Proof. By the argument of Corollary A.3 in Dagan et al. (2025), the reduced transcript makes at most 2τ ´j`1 calls to simulateGame for the SPR instance Gi,j,ℓ . Suppose that Player–L follows the recursive A{B labeling strategy LAB . Then, by Lemmas A.1 and A.4 of Dagan et al. (2025), together with the definition of Valred AB pn, sq, the bias contribution generated by the instance Gi,j,ℓ is bounded by ´ ¯ ` i τ ´j`1 ˘ O 2j´i Valred ` mint2i , 2τ ´h´i u . AB 2 , 2 Summing this bound over 1 ď i ď τ ´ h, i ` 1 ď j ď i ` h and ℓ P t0, 1u gives the claimed bound.
9
Lemma 2. It holds that τ ÿ
|PT | ď
¯ ´ ¯ ´ O mint2i , 2τ ´h´i u “ O 2pτ ´hq{2 .
i“1
Proof. This is the active-cell counting bound of Lemma A.4 of Dagan et al. (2025). Its dyadic counting argument is unaffected by the endpoint tie-breaking convention fixed above. Lemma 3. There exist constants CAB ě 1 and α, β ą 0 satisfying q :“ α ` β ă 1 such that, for every n, s ě 1, ! ) α β Valred pn, sq ď min n, s, C n s . AB AB q 1´εAB Consequently, defining εAB :“ 1 ´ q ą 0 and γ :“ 1`q “ 2´ε , we have the uniform bound AB 1 p1`qq γ Valred AB pn, sq ď CAB pnsq .
In particular, for every ρ ě 0,
´ ¯ ` ˘ ρ Valred “ O nγp1`ρq . AB n, n
Proof. Fix n, s ě 1, and consider an arbitrary legal play of length t ď s. Let Rσ denote the number of surviving signs of type σ P t´1, `1u. The root A-instance of the A{B strategy has bias parameter zero. Therefore, Lemma 5.1 of Dagan et al. (2025) gives constants C0 , α, β ą 0, with α ` β ă 1, such that Rσ ď C0 nα tβ for each σ P t´1, `1u. Summing over the two sign types and using t ď s, we obtain R´1 ` R`1 ď 2C0 nα sβ . Thus, after setting CAB :“ 2C0 , α β Valred AB pn, sq ď CAB n s .
The bound Valred AB pn, sq ď mintn, su follows directly from the rules of the SPR game. This proves ! ) α β Valred . AB pn, sq ď min n, s, CAB n s Therefore, we have that
1
q
1
1`q 1`q “ C 1`q pnsqγ . Valred AB pn, sq ď CAB pnsq AB
By choosing s “ nρ , we obtain ´ ¯ ` ˘ 1{p1`qq ρ ρ γ γp1`ρq Valred n, n ď C pn ¨ n q “ O n . AB AB
By Lemma 1 and Lemma 3, we have that Lemma 4. For any input sequence z1 , . . . , zT P r0, 1s, when SPR-C ALIBRATION is executed with input pzt qTt“1 , the resulting bias term satisfies ˇ ˇ ˜ ¸ ˇ ˇ τÿ ´h i`h τÿ ´h ÿ ˇ ÿ ÿ ˇ ˇ pzt ´ pt qˇˇ ď O 2j´i`γpi`τ ´jq ` log2 pT q ¨ mint2i , 2τ ´h´i u . ˇ ˇ ˇ i“1 j“i`1 i“1 pPPT tPrT s:pt “p 10
4
Algorithm
We present our main algorithm in Algorithm 5. The algorithm maintains an instance of SPR-C ALIBRATION. The main difficulty in applying SPR-C ALIBRATION is that the conditional means tet uTt“1 are not available to the forecaster. To address this, we use a Blackwell-style correction layer to construct, at each round t P rT s, a surrogate estimate ert of et . This surrogate is then passed as the input to the SPR-C ALIBRATION instance. Let X “ t0, η, 2η, . . . , N ηu be a grid with threshold η “ T ´1{2 and N “ t1{ηu. At each round t, let StSPR denote the internal state of the SPR-C ALIBRATION instance used by Algorithm 5 before round t and Pt “ tps : s ď tu. For each x P X and p P Pt´1 , we define
Dt pxq :“ PredictSPR pStSPR , t, xq ÿ Rp,t´1 :“ pys ´ ẽs q
(3) (4)
săt:ps “p
px,t´1 :“ RD pxq,t´1 . In particular, if Dt pxq R Pt´1 , we use the default Moreover, for each x P X , define R t px,t´1 “ RD pxq,t´1 “ 0. initialization R t px,t´1 defined above, we solve the following Blackwell-style minimax program to Given the quantities R obtain an optimal distribution µt P ∆pX q, where ∆pX q denotes the set of probability distributions over X . ÿ px,t´1 py ´ xq. βt “ min max µpxqR (5) µP∆pX q yPt0,1u
xPX
Then the algorithm samples the surrogate mean ert „ µt , and commits the deterministic SPR-C ALIBRATION steps: pt “ Dt pr et q “ PredictSPR pStSPR , t, ert q, SPR St`1 “ UpdateSPR pStSPR , t, ert q.
After outputting the forecast pt and observing the true outcome yt , we update Pt and the residuals Rp,t for all p P Pt .
5
Analysis
In this section, we present the proof of Theorem 1. The proof consists of two parts: bounding the calibration error and the computational cost.
5.1
Proof of Calibration Error
Set the hyperparameters of SPR-C ALIBRATION as τ “ rlog2 T s, and choose the scale ř parameter h ď τ later. Recall Pt “ tps : s ď tu. For t P rT s and p P Pt , recall the outer residual Rp,t “ sďt:ps “p pys ´ ers q if p P Pt . Define Rp,t “ 0 if p R Pt . For every p P PT , ÿ ÿ ÿ pyt ´ pq “ pr et ´ pq ` pyt ´ ert q. tPrT s:pt “p
tPrT s:pt “p
11
tPrT s:pt “p
Algorithm 5 Blackwell-Wrapped SPR-C ALIBRATION Require: Horizon T , grid X . 1: Initialize the internal state S1SPR of SPR-C ALIBRATION 2: Initialize the set of actually predicted values P0 Ð H 3: for t “ 1, 2, . . . , T do 4: Define Dt pxq following (3) for all x P X ; px,t´1 “ RD pxq,t´1 . 5: For all x P X , set R t 6: Choose µt P ∆pX q by solving the finite minimax optimization ÿ px,t´1 py ´ xq µpxqR min max µP∆pX q yPt0,1u
7: 8:
xPX
Sample an internal surrogate mean ert „ µt . Feed ert to SPR-C ALIBRATION and update SPR-C ALIBRATION: ` ˘ SPR ppt , St`1 q Ð PredictSPR pStSPR , t, ert q, UpdateSPR pStSPR , t, ert q .
(6)
9: if pt R Pt´1 then 10: Pt Ð Pt´1 Y tpt u 11: Rpt ,t´1 Ð 0 12: else 13: Pt Ð Pt´1 14: end if 15: Observe the outcome yt P t0, 1u. 16: Update the external Blackwell residual: Rpt ,t Ð Rpt ,t´1 ` yt ´ ert . 17: For all p P Pt ztpt u, set Rp,t Ð Rp,t´1 . 18: end for
Therefore, ˇ ˇfi « ff ˇ ÿ ˇˇ ÿ ÿ ˇ ˇ et ´ pqˇˇfl ` E ErCalErrT s ď E – pr |Rp,T | . ˇ ˇ ˇ pPPT tPrT s:pt “p pPP T looooooooooooooooomooooooooooooooooon loooooooomoooooooon »
SPR-C ALIBRATION bias term
(7)
Blackwell residual term
Bound of the SPR-C ALIBRATION bias term. The bound of the SPR-C ALIBRATION bias directly follows the result in Dagan et al. (2025). By Lemma 4, we have that ˇ ˇfi » ¨ ˛ ˇ ˇ τÿ ´h i`h ÿ ˇ ÿ ÿ ÿ ÿ ˇ ˇ E– pr et ´ pqˇˇfl ď O˝ 2j´i 2γpi`τ ´jq ` mint2i , 2τ ´h´i u‚. (8) ˇ ˇ i“1 j“i`1 pPPT ˇtPrT s:pt “p iďτ ´h jďi`h Bound of the Blackwell ` pτ ´hq{2 ˘ residual term. By the property of SPR-C ALIBRATION (see Lemma 2), we have that |PT | ď O 2 . Then by Cauchy’s inequality, we have that «
¨g « ff˛ f ´a ¯ ÿ f 2 ‚ď O |Rp,T | ď O ˝e2pτ ´hq{2 E Rp,T ErΦT s ¨ 2pτ ´hq{4 , ff
ÿ E pPPT
pPPT
12
(9)
where we define Φt “ ErΦT s.
ř
2 pPPt Rp,t for t P rT s and Φ0 “ 0. Then we have the following lemma to bound
`? ˘ Lemma 5. ErΦT s “ O p T ` ηT q2 . If η “ OpT ´1{2 q, then ErΦT s “ OpT q. By Lemma 5 and (9), we have that E
”ř
ı
pPPT |Rp,T |
? ď Op T ¨ 2pτ ´hq{4 q.
1´εAB Putting all together. Recall that η “ T ´1{2 . Let εAB be defined in Lemma 3 and let γ “ 2´ε . We then AB have that
ErCalErrT s ¨ ˛ τÿ ´h i`h τÿ ´h ÿ ¯ ´? ÿ ď O˝ 2j´i 2γpi`τ ´jq ` mint2i , 2τ ´h´i u‚` O T ¨ 2pτ ´hq{4 i“1 j“i`1
˜ ďO
τÿ ´h
i“1 jďi`h
2hp1´γq`γτ ` log2 pT q ¨
i“1
? mint2i , 2τ ´h´i u ` T ¨ 2pτ ´hq{4
ÿ
¸
iďτ ´h
¯ ? ď O log2 pT q ¨ 2h`γpτ ´hq ` log2 pT q ¨ 2pτ ´hq{2 ` T ¨ 2pτ ´hq{4 ´ ¯ ď O log2 pT q ¨ 2h`γpτ ´hq ` log2 pT q ¨ 23τ {4´h{4 . ´
Here, (10) follows from the inequality j ´ i ď h and the fact that while (11) follows from pτ ´ hq{2 ď 3τ {4 ´ h{4.
(10) (11)
řτ ´h
i τ ´h´i u “ Op2pτ ´hq{2 q, i“1 mint2 , 2
¯ ´ ε 2 2`εAB ´ AB 3 18 By choosing h “ 3´4γ pT q ¨ T . τ “ τ , we have that ErCalErr s ď O log T 2 5´4γ 6´εAB
5.2
Computational cost
We give a fully explicit implementation of Algorithm 5. The purpose of the argument is only to establish a polynomial running time, so we use direct scans and deep copies rather than more sophisticated persistent data structures. Let K “ r1{ηs. Recall also that τ “ rlog2 T s, T “ 2τ ă 2T and h ď τ ´ 1. Lemma 6. Algorithm 5, using transition from Section 3.1 and the explicit A{B labeler, can ´ 7 the deterministic ¯ be implemented in time O T 2 log T . Proof. We prove by bounding the cost of one deterministic SPR transition and the additional work performed by the outer wrapper. Size of the SPR state. For every i P Ih “ t1, . . . , τ ´ hu, j P Ji “ ti ` 1, . . . , i ` hu and ℓ P t0, 1u, the algorithm maintains a board Gi,j,ℓ with 2i cells. Its bias array and sign array use Op2i q words. The live state of the explicit A{B labeler also uses Op2i q words. Indeed, its recursively stored objects form a binary tree with Op2i q nodes, and every node stores only a constant number of counters, pointers, phase variables, and integer parameters. When a labeler object is restarted, the old object is discarded, so obsolete versions are not retained.
13
Thus, one board requires Op2i q words, and the local SPR state has size ¸ ˜ τÿ ´h τÿ ´h i`h ¯ ´ ÿ ÿ 2i “ O h2τ ´h . Op2i q “ O h i“1 j“i`1 ℓPt0,1u
i“1
Taking the historical recording of the local SPR states into consideration, the complete SPR state has size OpT h2τ ´h q. The same bound applies to the one-time initialization cost and to the cost of making a deep copy of the state. Cost of one SPR transition. Consider StepSPR pS, t, zq for a fixed input z P r0, 1s. In the bias-removal phase, for each pair pi, jq, the parity of z selects one of the two boards Gi,j,0 and Gi,j,1 . A direct scan of that finds an admissible cell in Op2i q time if one exists. Hence a complete bias-removal scan costs ´ board ` ˘ řτ ´h i ¯ O h i“1 2 “ O h2τ ´h . The bias-placement phase performs only Ophτ q constant-time current-cell checks, except that it may make one call to simulateGame. Suppose that simulateGame is called on a board with 2i cells. Scanning the sign array, constructing the reduced transcripts, and carrying out all else legal deletions costs Op2i q, It remains to bound the cost of the A{B label query. A call to the recursive A{B procedure follows a root-to-leaf path of depth at most i. At each depth, the corresponding A-object can restart its current B-object i at most once before returning a sign. Eagerly initializing a B-object ˘ an interval of length at most 2 costs ` τ ´hon i i Op2 q. Therefore, the deliberately coarse bound Opi2 q ď O τ 2 holds for one label query. Combining the bias-removal phase, the bias-placement phase, and the possible game simulation gives that the time cost of StepSPR pS, t, zq is bounded by Opτ 2τ ´h q. Computing all preview predictions.
For each x P X , the algorithm:
1. makes a deep copy of StSPR ; 2. evaluates StepSPR pStSPR , t, xq on the scratch copy; 3. records only the resulting prediction Dt pxq; and 4. discards the scratch copy. ` ˘ Consequently, computing all K values Dt pxq costs O T Kτ 2τ ´h time. Because the scratch state is reused, this requires only one scratch copy, rather than K simultaneous copies. Solving the finite minimax problem. The minimax optimization problem (5) has K variables, corresponding to the distribution over the K grid points, and only two constraints, corresponding to the two possible outcomes y “ 0 and y “ 1. Therefore, it can be solved within OpK 2 q time. Putting all together.
After sampling ert , the algorithm commits exactly one SPR transition:
SPR ppt , St`1 q “ StepSPR pStSPR , t, ert q. ` ˘ ` ˘ This costs O τ 2τ ´h . Therefore, the total cost of round t is O T Kτ 2τ ´h ` K 2 . Summing over the T ? ` ˘ rounds and including the one-time initialization cost gives O T 2 Kτ 2τ ´h ` T K 2 . Using K “ Op T q,
14
τ “ Oplog T q, and 2τ ´h ď 2τ ă 2T , we obtain ¯ ´ 7 ´ ¯ O T 2 Kτ 2τ ´h ` T K 2 “ O T 2 log T .
5.3
Proof of Lemma 5
`? ˘ Lemma 5 (restatement). ErΦT s “ O p T ` ηT q2 . If η “ OpT ´1{2 q, then ErΦT s “ OpT q. Proof. Recall that X is the grid with interval length η. At round t, the wrapper chooses a distribution µt P ∆pX q by solving the finite minimax problem (5) as ÿ px,t´1 py ´ xq. βt “ min max µpxqR µP∆pX q yPt0,1u
xPX
By Von Neumann’s minimax theorem βt “ “
max
” ı px,t´1 py ´ xq min Ey„q R
max
px,t´1 pEy„q rys ´ xq min R
qP∆pt0,1uq xPX qP∆pt0,1uq xPX
px,t´1 py ´ xq. “ max min R yPr0,1s xPX
(12)
Fix any y P r0, 1s, and let x˚ pyq P arg minxPX |y ´ x|. Then |y ´ x˚ pyq| ď η. Therefore, ˇ ˇ px,t´1 py ´ xq ď ˇˇR px˚ pyq,t´1 ˇˇ η. min R xPX
ˇ ˇ ? ˇp ˇ px˚ pyq,t´1 py ´ xq ď η ?Φt´1 . Taking the maximum over Since ˇR Φt´1 , we have minxPX R x˚ pyq,t´1 ˇ ď ? y P r0,”1s gives βt ď ıη Φt´1 . Since µt is optimal for the finite minimax problem, for both y P t0, 1u, px,t´1 py ´ xq ď βt ď η ?Φt´1 . Recalling that R px,t´1 “ RD pxq,t´1 for all x P X , we always have Ex„µt R t a “ ‰ Ex„µt RDt pxq,t´1 pyt ´ xq ď βt ď η Φt´1 .
(13)
Let Ft denote the σ-field after the t-th round. So the adversary chooses yt (or its distribution) conditioned on Ft . We then have that a ErΦt ´ Φt´1 | Ft´1 s “ Ex„µt r2RDt pxq,t´1 pyt ´ xq ` pyt ´ xq2 | Ft´1 s ď 2η Φt´1 ` 1, which implies ErΦt s ´ ErΦt´1 s ď 2ηEr
a
Φt´1 s ` 1.
? ? Let Zt “ ErΦt s for t ě 0. By Jensen’s inequality, Er Φt´1 s ď Zt´1 . Therefore, a Zt ď Zt´1 ` 1 ` 2η Zt´1 . ? ř ´1 ? Summing over t yields ZT ď T ` 2η Tt“0 Zt . Let MT “ max0ďtďT Zt . Then MT2 ď T ` 2ηT MT . 15
Solving this quadratic inequality gives MT ď ηT `
a ? η 2 T 2 ` T ď 2ηT ` T .
Hence
¯ ´? ZT ď MT2 ď O p T ` ηT q2 . ? ? If η ď T ´1{2 , then T ` ηT “ Op T q, and therefore ErΦT s “ OpT q.
6
Discussion
In this paper, we develop an efficient algorithm that achieves OpT 2{3´ε q calibration error. Our algorithm is based on a simple combination of the SPR-C ALIBRATION algorithm in Dagan et al. (2025) and a Blackwellapproachability correction argument. The resulting improvement exponent ε is inherited from the SPR guarantee in Dagan et al. (2025); in particular, any improvement in the value of the underlying SPR game would translate directly into a stronger efficient calibration bound.
References Abernethy, J., Bartlett, P. L., and Hazan, E. (2011). Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 27–46. PMLR. Blackwell, D. (1956). An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1–8. Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge University Press. 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, STOC ’25, pages 2007–2018, New York, NY, USA. Association for Computing Machinery. Dawid, A. P. (1982). The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605–610. Foster, D. P. (1999). A proof of calibration via blackwell’s approachability theorem. Games and Economic Behavior, 29(1–2):73–78. Foster, D. P. and Vohra, R. V. (1997). Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1–2):40–55. Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika, 85(2):379–390. Foster, D. P. and Vohra, R. V. (1999). Regret in the on-line decision problem. Games and Economic Behavior, 29(1–2):7–35. Fudenberg, D. and Levine, D. K. (1999). An easier way to calibrate. Games and economic behavior, 29(1-2):131–137. Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. (2017). On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1321–1330. PMLR. 16
Hart, S. (2022). Calibrated forecasts: The minimax proof. 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, pages 1939–1948. PMLR. Kuleshov, V., Fenner, N., and Ermon, S. (2018). Accurate uncertainties for deep learning using calibrated regression. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2796–2804. PMLR. Mannor, S. and Stoltz, G. (2010). A geometric proof of calibration. Mathematics of Operations Research, 35(4):721–727. 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, pages 456–466. ACM.
17