# Stronger Calibration Lower Bounds via Sidestepping

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

## Built on by (most cited first, 30 of 38)

- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Calibrated Forecasts: The Minimax Proof](https://mlsanity.com/paper/2209.05863/) (2022)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [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)
- [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)
- [Towards Certification of Uncertainty Calibration under Adversarial Attacks](https://mlsanity.com/paper/2405.13922/) (2024)
- [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Faster online calibration without randomization: interval forecasts and the power of two choices](https://mlsanity.com/paper/2204.13087/) (2022)
- [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)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)
- [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)
- [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)
- [Instance-Adaptive Online Multicalibration](https://mlsanity.com/paper/2605.09273/) (2026)

## Abstract (arXiv)

We consider an online binary prediction setting where a forecaster observes a sequence of T bits one by one. Before each bit is revealed, the forecaster predicts the probability that the bit is 1. The forecaster is called well-calibrated if for each p ∈ [0, 1], among the np bits for which the forecaster predicts probability p, the actual number of ones, mp, is indeed equal to p · np. The calibration error, defined as sump |mp - p np|, quantifies the extent to which the forecaster deviates from being well-calibrated. It has long been known that an O(T2/3) calibration error is achievable even when the bits are chosen adversarially, and possibly based on the previous predictions. However, little is known on the lower bound side, except an Omega(√T) bound that follows from the trivial example of independent fair coin flips. In this paper, we prove an Omega(T0.528) bound on the calibration error, which is the first super-√T lower bound for this setting to the best of our knowledge. The technical contributions of our work include two lower bound techniques, early stopping and sidestepping, which circumvent the obstacles that have previously hindered strong calibration lower bounds. We also propose an abstraction of the prediction setting, termed the Sign-Preservation game, which may be of independent interest. This game has a much smaller state space than the full prediction setting and allows simpler analyses. The Omega(T0.528) lower bound follows from a general reduction theorem that translates lower bounds on the game value of Sign-Preservation into lower bounds on the calibration error.