PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$

Eric Dai, Maxwell Fishelson

arXiv:2610.07623v1stat.MLcs.DScs.GTcs.LG

TL;DR

Sequential forecasting asks how to improve the classical 2/3 exponent for expected cumulative calibration error, after earlier work reduced it only by an unspecified amount. The paper combines a two-phase SPR labeling strategy with a sharper reduction using O(log T) game instances, establishing a calibration bound with an explicit exponent.

  • Problem

    The classical expected cumulative calibration-error bound has exponent 2/3, and the later improvement by Dagan et al. specifies no exponent, leaving the size of the improvement open.

    Source: Sequential calibration · p. 2

  • Method

    A two-phase recursive SPR labeling strategy gives separate space-and-time bounds, which the paper passes to calibration through a modified reduction using O(log T) instances.

    Source: §1.1 · pp. 2–3, §3.2 · p. 6

  • Results

    The paper establishes an explicit calibration exponent by choosing parameters that satisfy sufficient conditions for its SPR bound and applying the reduction.

    Source: §1.1 · p. 2, §3.1 · p. 6, §3.2 · p. 8

  • Takeaways & Limitations

    The work makes the improvement below the classical calibration exponent explicit through its labeling bound, sharper reduction, and feasible parameter choice.

    Source: §3.1 · p. 6, §3.2 · p. 8

    The forecasting setting assumes the forecaster does not know the adversary's conditional probability of the next outcome given the history.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

Probability forecasts are calibrated when predicted probabilities match empirical outcome frequencies: among events assigned a probability $p$, we'd hope that the fraction of positive outcomes is close to $p$. We study the problem of sequential forecasting of binary outcomes. The classical $O(T^{2/3})$ bound on expected cumulative $\ell_1$-calibration error established by Foster and Vohra stood for over two decades until Dagan et al. reduced the exponent $2/3$ by an unspecified constant. We establish a new two-phase recursive labeling strategy for the sign-preservation-with-reuse game that yields the bound $O(n^{\alpha}t^\beta)$ for all choices of space and time. We then sharpen the reduction from upper bounds on sign preservation to calibration by modifying the equivalence of Dagan et al. to use only $O(\log T)$ instances of the sign-preservation-with-reuse game. This lets us establish an explicit bound of $O(T^{0.662942288})$, the first explicit exponent below $2/3$ for sequential calibration, by combining both improvements and choosing explicit feasible parameters.

1 Introduction

The paper studies sequential calibration, where forecasts should match observed outcome frequencies, and asks how far the classical 2/3 error exponent can be reduced explicitly. It develops a sharper sign-preservation route to calibration and reports an explicit improvement over that classical exponent.

Sequential calibration.

  • The open quantitative question is how much the sequential calibration exponent can be reduced: Dagan et al. crossed 2/3 by an unspecified constant, while Foster and Vohra established the classical O(T^2/3) bound.Calibration groups predictions by probability and compares each group's positive-outcome count with its predicted mass.Source: Sequential calibration · p. 2

1.1 Our contributions

  • The paper gives an explicit upper bound on expected cumulative calibration error, improving the classical exponent of 2/3 by more than 0.00372.The result applies to a randomized forecaster against any adversary.Source: §1.1 · p. 2
  • The sign-preservation-with-reuse game (SPR) provides the combinatorial route from labeling strategies to calibration; Dagan et al. connect preserving O(n^1−ε) signs to error O(T^2/3−ε/18).The paper builds on Qiao and Valiant's [QV21] sign-preservation game.Source: §1.1 · p. 2
  • A two-phase recursive labeling strategy runs on interval halves until request counts balance, then adjusts its bias toward one sign type.It separately bounds newly placed signs and signs surviving from earlier epochs, with bounds depending on both cell count and round count.Source: §1.1 · pp. 2–3
  • The modified calibration reduction analyzes an O(n^αt^β) labeling bound at each partition scale and uses O(log T) SPR instances, rather than O((log T)^2).Its analysis sums conditional-mean contributions across space and bias scales and balances them against outcome fluctuations.Source: §1.1 · p. 3
  • The final calibration exponent depends on explicit labeling-strategy parameters chosen to satisfy sufficient inequalities for the SPR upper bound.The paper presents these feasible parameters as the basis for its explicit calibration bound.Source: §1.1 · p. 3

2 Preliminaries

The preliminaries define sequential calibration as an online forecasting game and introduce sign-preservation-with-reuse (SPR), a related combinatorial game. The latter's remaining signs connect labeler strategies to upper bounds on calibration error.

2.1 Sequential calibration

  • Sequential calibration is a repeated game over a finite prediction set: the forecaster predicts and the adversary chooses a binary outcome without knowing the current prediction.The forecaster does not know the adversary's conditional probability of the next outcome given the history.Source: §2.1 · p. 3
  • Cumulative ℓ1-calibration error compares, for each prediction p, its positive-outcome count with p times the number of times that prediction was made.The target is a bound on expected error against every adversary, with expectation over both players' randomness.Source: §2.1 · p. 3

2.2 Sign-preservation-with-reuse game

  • In SPR, a pointer selects an empty cell and a labeler may remove minus signs to its left and plus signs to its right before placing a sign there.Reuse allows selection of previously emptied cells; the pointer maximizes and the labeler minimizes the number of signs remaining, which supplies upper bounds on calibration error.Source: §2.2 · p. 4

3 Overview of Theorem 1.1

The proof of Theorem 1.1 combines a new sign-preservation-with-reuse labeling strategy, a sharper reduction from calibration to that game, and explicit parameter selection.

3.1 Overview of Section 4

  • The two-phase recursive strategy runs on both halves until a balance condition holds, then continues with adjusted bias and separate bounds for new and persistent signs.It replaces Dagan et al.’s four-phase strategy.Source: §3.1 · p. 6

3.2 Overview of Section 5

  • The modified reduction uses O(log T) SPR instances rather than Dagan et al.’s O((log T)^2), applying separate space-time bounds O(n^αt^β).The overview says the admissible parameters are then chosen to maximize ε = 1 − α − β.Source: §3.2 · pp. 6, 8
  • The calibration analysis sums conditional-mean contributions across space and bias scales against outcome fluctuations, then selects admissible parameters to obtain the claimed exponent.The minimax step removes the forecaster’s access to conditional means.Source: §3.2 · p. 8

4 An improved labeling strategy for the sign-preservation-with-reuse game

This section develops a recursive Player-L labeling strategy with guarantees that depend separately on the number of cells and rounds, using two phases within each epoch. It completes the induction by bounding sign preservation across epochs, combining the two sign-type bounds at the root, and extending the guarantee to arbitrary board sizes through padding.

4 An improved labeling strategy for the sign-preservation-with-reuse game

  • Theorem 4.1 gives Player-L a strategy whose guarantee depends separately on the numbers of cells and rounds.The proof proceeds through a per-sign bound for the recursive strategy, then applies it to the root instance and pads to arbitrary board sizes.Source: §4 · p. 8

4.1 Description of the strategy

  • Each A instance runs successive B epochs: B first routes requests to half-interval children, then may answer a continuation using a shifted-bias A instance.B switches phases when the smaller half-count meets both the threshold relative to earlier epochs and the balance threshold; the continuation lasts floor(κth) requests.Source: §4.1 · pp. 9–10

4.2 Parameters and the labeling lemma

  • The per-sign labeling lemma assumes an admissible tuple of analysis parameters and constants controlling inherited signs, epochs, and epoch-end counts.The parameters α and β describe space- and time-dependence, while λ controls bias changes; ρ, κ, and δ govern the phase trigger and continuation.Source: §4.2 · pp. 10–12

4.3 Lemmas in the proof of Theorem 4.3

  • For a phase-2 continuation triggered by the right half, Lemma 4.4 bounds the remaining signs using inherited persistent signs, the two child instances, and the shifted-bias instance.The first visits to both halves delete nonpersistent inherited signs; a left-half trigger swaps sign types and exchanges the bias factors.Source: §4.3 · p. 13
  • For instances with t ≤ F, Lemma 4.5 bounds per-sign preservation using a path of returned signs with at most log2 t bias changes.Each bias change reduces the processed-request count by at least half, and each change shifts bias by one.Source: §4.3 · p. 14
  • Lemma 4.6 maintains persistent- and total-sign bounds at each epoch start, covering both u ≤ F and u > F cases.For u ≤ F, remaining signs are bounded by u; for u > F, Theorem 4.4 and the inherited inequalities establish the bounds, with a left-half trigger exchanging sign types.Source: §4.3 · p. 15

4.4 Completing the labeling induction

  • For n ≥ 2 and t > F, the proof applies space induction to both smaller halves and time induction to shifted instances; three cases finish the inner time induction, then the outer space induction.The cases are one half visited in phase 1, both halves visited in phase 1, or phase 2. A left-half trigger exchanges the roles of the two sign types.Source: §4.4 · pp. 16–17
  • Theorem 4.1 combines both sign-type bounds at the zero-bias root and extends the guarantee to arbitrary board sizes by padding to a power of two.The padded board size is a power of two N with n ≤ N < 2n.Source: §4.4 · p. 17

5 From sign-preservation bounds to calibration

This section converts separate space and time bounds for sign-preservation-with-reuse into an expected calibration guarantee using O(log T) instances. It controls prediction values, bias, variance, and prediction fluctuations, selects parameters, and then removes the forecaster’s access to conditional means.

5 From sign-preservation bounds to calibration

  • Theorem 5.1 converts opt(n, t) = O(n^αt^β) into an expected calibration guarantee against any adversary.The theorem assumes α, β ∈ (0, 1) and ε = 1 − α − β > 0; the supplied passage does not include the guarantee’s displayed bound.Source: §5 · p. 17

5.1 Description of the strategy

  • The strategy uses 4h − 2 = O(log T) SPR instances, versus O((log T)^2) in Dagan et al..At each partition level, intervals are split by index parity, with separate instances for the two parities.Source: §5.1 · p. 18

5.2 The scale-sum lemma

  • The scale-sum lemma bounds calibration error using coarsest- and finer-level SPR guarantees, used-cell counts, rounding, and prediction-wise fluctuations.The proof bounds conditional-mean bias through remaining signs and distinct predictions, then accounts for the zero-conditional-mean increments yt − et.Source: §5.2 · pp. 20–21

5.3 Lemmas for the proof of Theorem 5.2

  • Active endpoint biases stay within 2^(j−i) + 1 in magnitude, while inactive endpoint biases stay within 1.Each stored endpoint bias preserves its sign, and its magnitude can increase by at most 2^−(i+1) per round.Source: §5.3 · p. 21
  • Reduced transcripts undo wasted labeler moves and bound each instance’s sign count by opt(2^i, r_i,j,ℓ).The transcript restores the base labeler’s saved state when a prior sign is legally deleted; its recorded move count is at most r_i,j,ℓ.Source: §5.3 · p. 22
  • Lemma 5.6 bounds the number of distinct prediction values by 2^(i0+1) + 1 + 2^(τ−i0−h−1).The proof counts coarsest-level endpoints and additional values from counted parent intervals; the stored bias threshold limits how many parents can be counted.Source: §5.3 · pp. 23–24

5.4 Proof of Theorem 5.2

  • Theorem 5.2 separates calibration error into bias and martingale-fluctuation terms, bounding bias by O(h2^i0 + 2^(τ−i0−h) + S0 + S1) and using the prediction count to control variance.The bias bound combines contributions from placed cells and the two scale sums; the variance argument uses conditional-mean-zero increments and the bound on distinct predictions.Source: §5.4 · pp. 24–25

5.5 Proof of Theorem 5.1

  • Theorem 5.1 chooses i0 to balance the bias and variance terms, bounds S0 + S1 using opt(n, t) = O(n^αt^β), and extends the result to arbitrary sufficiently large horizons.The proof removes access to conditional means by computing them for each fixed randomized adversary and applying finite-game minimax to obtain one randomized forecaster with the same bound against any adversary.Source: §5.5 · pp. 25–27

6 Explicit parameters and the main theorem

The paper verifies an explicit parameter choice for its calibration bound. This yields an expected calibration error exponent below 0.662942288.

6 Explicit parameters and the main theorem

  • The six-parameter tuple is admissible, and the auxiliary values satisfy the stated conditions.The construction also specifies constants including F = 1010, Kp = 0.8812155678, and Kt = 0.9208553424.Source: §6 · p. 27
  • The proof applies the calibration theorem to the labeling strategy's uniform bound over integers n ≥ 1 and t ≥ 0.It uses the parameters and constant C specified for Theorem 6.1.Source: §6 · p. 27
  • 0.662942288 is a strict upper bound on the resulting calibration exponent.The proof verifies the exponent using the chosen parameters.Source: §6 · p. 27
  • Numerical search found a calibration exponent of approximately 0.66294228152554, only 6.3 · 10^-9 below the chosen exponent.The search maximizes ε subject to the parameter inequalities.Source: §6 · p. 27

A Verification of the explicit parameters

The appendix verifies the explicit parameter choices used in the proof of Theorem 6.1.

A Verification of the explicit parameters

A.1 Verification of the explicit bounds

The appendix verifies the explicit parameter tuple by checking the bounds required for admissibility, then verifies the resulting calibration exponent.

A.1 Verification of the explicit bounds

  • The phase 2 coefficients P and Q bound persistent and total signs, respectively, before rounding; their suprema reduce to four values for P and two for Q.The maximization is over the two-segment trigger domain.Source: §A.1 · pp. 29, 32, 33
  • The phase 1 coefficient M satisfies the two required inequalities under their respective count conditions.The conditions apply at the end of a phase 1 round and when a request triggers the transition to phase 2.Source: §A.1 · p. 30
  • The appendix reduces the conditions of Theorem 4.2 to three inequalities, whose verification enables checks of the phase 2 inequalities.The first two inequalities are hypotheses for verifying the four phase 2 inequalities.Source: §A.1 · p. 31
  • 80-digit mpmath interval arithmetic verifies outward upper bounds for M, D, P, and Q, which preserve the strict inequalities for the exact coefficients.The appendix also invokes a weighted concavity inequality when establishing bounds for unfinished epochs.Source: §A.1 · pp. 29, 30, 33
  • The six-parameter tuple is admissible after verification of auxiliary ranges, unfinished-epoch bounds, and the phase 1 and phase 2 inequalities.The proof also gives C = 1020/Kp = F^2/Kp as a sufficient choice for the induction.Source: §A.1 · p. 33
  • 0.662942288 strictly exceeds the exact calibration exponent 20342855641/30685711282.The exponent is obtained by substituting the chosen parameters into (2 + ε)/(3 + 2ε).Source: §A.1 · p. 33

A.2 Python code

Listing 1 independently verifies that the stated parameters satisfy Theorem 4.2’s inequalities and computes the resulting calibration exponent.

A.2 Python code

  • The script checks the stated parameters against Theorem 4.2’s inequalities and computes the calibration exponent.It reports PASS when all admissibility conditions and the exponent check succeed.Source: §A.2 · pp. 33, 35
  • The verification covers weighted concavity for unfinished epochs and waiting-count inequalities in Phase 1.The code notes that the same bounds certify the first-trigger inequality with its +1 term.Source: §A.2 · p. 35
  • Phase 2 checks three terminal inequalities in order—terminal_minus < K_p, terminal_plus < K_p, and terminal_total < K_t—and the code later asserts exponent < 0.662942288.Source: §A.2 · p. 35

Related papers

Loading 2610.07623v1…