# Breaking the T2/3 Barrier for Sequential Calibration

arXiv: https://arxiv.org/abs/2406.13668 · HTML: https://mlsanity.com/paper/2406.13668/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2024.

## Built on by (most cited first, 19 of 19)

- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [Truthfulness of Calibration Measures](https://mlsanity.com/paper/2407.13979/) (2024)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Testable and Actionable Calibration for Full Swap Regret](https://mlsanity.com/paper/2605.17749/) (2026)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)
- [Efficient Sequential Calibration with O(T2/3-ε) Error Bound](https://mlsanity.com/paper/2607.12928/) (2026)
- [Optimal Recalibration of an Online Predictor](https://mlsanity.com/paper/2607.19689/) (2026)
- [Improved and Oracle-Efficient Online ℓ1-Multicalibration](https://mlsanity.com/paper/2505.17365/) (2025)
- [Improved Multi-Dimensional Forecasting for Swap Regret](https://mlsanity.com/paper/2606.29533/) (2026)
- [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026)
- [Truthful Calibration Measures for Sequential Prediction](https://mlsanity.com/paper/2608.21348/) (2026)
- [High-dimensional online calibration from harmonic weights](https://mlsanity.com/paper/2610.07740/) (2026)

## Abstract (arXiv)

A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences under the standard ℓ1 calibration error metric, which was initially studied by Foster & Vohra (1998). They derived an algorithm with O(T2/3) calibration error after T time steps, and showed a lower bound of Omega(T1/2). These bounds remained stagnant for two decades, until Qiao & Valiant (2021) improved the lower bound to Omega(T0.528) by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the O(T2/3) upper bound on calibration error of Foster & Vohra. We do this by introducing a variant of Qiao & Valiant's game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved upper bound for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error O(T2/3 - varepsilon) for some varepsilon > 0, improving Foster & Vohra's upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of Qiao & Valiant, namely Omega(T0.54389). Our lower bound is obtained by an oblivious adversary, marking the first ω(T1/2) calibration lower bound for oblivious adversaries.