# High dimensional online calibration in polynomial time

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 40 references that are in the map.
- First posted on arXiv 12 Apr 2025.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering](https://mlsanity.com/paper/2012.00955/) (2020)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Revisiting the Calibration of Modern Neural Networks](https://mlsanity.com/paper/2106.07998/) (2021)
- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (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)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Calibration, Entropy Rates, and Memory in Language Models](https://mlsanity.com/paper/1906.05664/) (2019)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Forecasting for Swap Regret for All Downstream Agents](https://mlsanity.com/paper/2402.08753/) (2024)
- [Smooth Calibration, Leaky Forecasts, Finite Recall, and Nash Dynamics](https://mlsanity.com/paper/2210.07152/) (2022)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Breaking the T2/3 Barrier for Sequential Calibration](https://mlsanity.com/paper/2406.13668/) (2024)
- [Calibrated Forecasts: The Minimax Proof](https://mlsanity.com/paper/2209.05863/) (2022)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Full Swap Regret and Discretized Calibration](https://mlsanity.com/paper/2502.09332/) (2025)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces](https://mlsanity.com/paper/2310.19786/) (2023)

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

- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Swap Regret Minimization Through Response-Based Approachability](https://mlsanity.com/paper/2602.06264/) (2026)
- [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)
- [Defensive Generation](https://mlsanity.com/paper/2602.21390/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Efficient Opportunistic Approachability](https://mlsanity.com/paper/2602.21328/) (2026)
- [Smoothed Elicitation Complexity for Approximate Gamma-calibration of Discrete Classification Tasks](https://mlsanity.com/paper/2605.23017/) (2026)
- [Improved Multi-Dimensional Forecasting for Swap Regret](https://mlsanity.com/paper/2606.29533/) (2026)
- [High-dimensional online calibration from harmonic weights](https://mlsanity.com/paper/2610.07740/) (2026)

## Abstract (arXiv)

In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space [d] over a sequence of T days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require exp(d) days to achieve non-trivial calibration. In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy ε > 0, our forecaster becomes ε-calibrated after T = dO(1/ε2) days. We complement this result with a lower bound, proving that at least T = dOmega(log(1/ε)) rounds are necessary to achieve ε-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows.