# Computational and Statistical Hardness of Calibration Distance

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 19 Mar 2026.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (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)
- [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)
- [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)
- [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)
- [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)
- [Can a calibration metric be both testable and actionable?](https://mlsanity.com/paper/2502.19851/) (2025)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Truthfulness of Decision-Theoretic Calibration Measures](https://mlsanity.com/paper/2503.02384/) (2025)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [Truthfulness of Calibration Measures](https://mlsanity.com/paper/2407.13979/) (2024)
- [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025)
- [The Importance of Being Smoothly Calibrated](https://mlsanity.com/paper/2603.16015/) (2026)
- [On the Within-Group Fairness of Screening Classifiers](https://mlsanity.com/paper/2302.00025/) (2023)

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

- [Sharp Integrality Gaps in Calibration Distance](https://mlsanity.com/paper/2610.05679/) (2026)

## Abstract (arXiv)

The distance from calibration, introduced by Blasiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predictors. We study the fundamental problems of computing and estimating this quantity, given either an exact description of the data distribution or only sample access to it. We give an efficient algorithm that exactly computes the calibration distance when the distribution has a uniform marginal and noiseless labels, which improves the O(1/√|X|) additive approximation of Qiao and Zheng (COLT 2024) for this special case. Perhaps surprisingly, the problem becomes mathsfNP-hard when either of the two assumptions is removed. We extend our algorithm to a polynomial-time approximation scheme for the general case. For the estimation problem, we show that Theta(1/ε3) samples are sufficient and necessary for the empirical calibration distance to be upper bounded by the true distance plus ε. In contrast, a polynomial dependence on the domain size -- incurred by the learning-based baseline -- is unavoidable for two-sided estimation. Our positive results are based on simple sparsifications of both the distribution and the target predictor, which significantly reduce the search space for computation and lead to stronger concentration for the estimation problem. To prove the hardness results, we introduce new techniques for certifying lower bounds on the calibration distance -- a problem that is hard in general due to its textsfco-NP-completeness.