Calibration distance, introduced by Błasiok, Gopalan, Hu, and Nakkiran in 2023, has become a standard way to measure how far a probabilistic predictor is from being perfectly calibrated. Mingda Qiao's new paper studies the basic algorithmic questions: given a data distribution, or only samples from it, how hard is it to compute or estimate this distance?

The results are sharply split. When the distribution has a uniform marginal over the label space and labels are noiseless, the paper gives an efficient algorithm that computes the calibration distance exactly, improving on the earlier O(1/√|X|) additive approximation for that special case. But if either assumption is dropped, the problem becomes NP-hard. The paper also extends the algorithm to a polynomial-time approximation scheme for the general computational problem.

On the statistical side, the paper pins down the sample complexity of one-sided estimation: Θ(1/ε³) samples are both sufficient and necessary for the empirical calibration distance to exceed the true distance by at most ε. For two-sided estimation, however, a polynomial dependence on the domain size is unavoidable, matching the behavior of learning-based baselines. The positive results rely on sparsifying both the distribution and the predictor, while the hardness proofs introduce new techniques for certifying lower bounds on calibration distance, a task that is co-NP-complete in general. The paper is set to appear at SODA 2027.