# On the Distance from Calibration in Sequential Prediction

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 8 of 8)

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Calibrated Forecasts: The Minimax Proof](https://mlsanity.com/paper/2209.05863/) (2022)
- [Faster Recalibration of an Online Predictor via Approachability](https://mlsanity.com/paper/2310.17002/) (2023)
- [Faster online calibration without randomization: interval forecasts and the power of two choices](https://mlsanity.com/paper/2204.13087/) (2022)

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

- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs](https://mlsanity.com/paper/2411.17582/) (2024)
- [Tractable Agreement Protocols](https://mlsanity.com/paper/2411.19791/) (2024)
- [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)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (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)
- [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [An Elementary Predictor Obtaining 2√T+1 Distance to Calibration](https://mlsanity.com/paper/2402.11410/) (2024)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Temporal Difference Calibration in Sequential Tasks: Application to Vision-Language-Action Models](https://mlsanity.com/paper/2604.20472/) (2026)
- [Beyond ECE: Calibrated Size Ratio, Risk Assessment, and Confidence-Weighted Metrics](https://mlsanity.com/paper/2605.01796/) (2026)
- [Augmented Feature Boosting for Multicalibration](https://mlsanity.com/paper/2609.33891/) (2026)
- [Sharp Integrality Gaps in Calibration Distance](https://mlsanity.com/paper/2610.05679/) (2026)

## Abstract (arXiv)

We study a sequential binary prediction setting where the forecaster is evaluated in terms of the calibration distance, which is defined as the L1 distance between the predicted values and the set of predictions that are perfectly calibrated in hindsight. This is analogous to a calibration measure recently proposed by Blasiok, Gopalan, Hu and Nakkiran (STOC 2023) for the offline setting. The calibration distance is a natural and intuitive measure of deviation from perfect calibration, and satisfies a Lipschitz continuity property which does not hold for many popular calibration measures, such as the L1 calibration error and its variants. We prove that there is a forecasting algorithm that achieves an O(√T) calibration distance in expectation on an adversarially chosen sequence of T binary outcomes. At the core of this upper bound is a structural result showing that the calibration distance is accurately approximated by the lower calibration distance, which is a continuous relaxation of the former. We then show that an O(√T) lower calibration distance can be achieved via a simple minimax argument and a reduction to online learning on a Lipschitz class. On the lower bound side, an Omega(T1/3) calibration distance is shown to be unavoidable, even when the adversary outputs a sequence of independent random bits, and has an additional ability to early stop (i.e., to stop producing random bits and output the same bit in the remaining steps). Interestingly, without this early stopping, the forecaster can achieve a much smaller calibration distance of polylog(T).