mlsanityData to 14 Oct 2026

Sharp Integrality Gaps in Calibration Distance

arXiv 2610.05679 ↗First posted 5 Oct 2026cs.LG math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 9 of its 12 references that are in the map. First posted on arXiv 5 Oct 2026.

Builds on

9 of 12 references.

References · 9

  1. 2022A Unifying Theory of Distance from Calibrationcited by 53
  2. 2024On the Distance from Calibration in Sequential Predictioncited by 19
  3. 2025Can a calibration metric be both testable and actionable?cited by 12
  4. 2024Testing Calibration in Nearly-Linear Timecited by 10
  5. 2025Truthfulness of Decision-Theoretic Calibration Measurescited by 10
  6. 2025Smooth Calibration and Decision Makingcited by 10
  7. 2025A Perfectly Truthful Calibration Measurecited by 5
  8. 2026The Importance of Being Smoothly Calibratedcited by 3
  9. 2026Computational and Statistical Hardness of Calibration Distancecited by 1

Built on by

Not cited yet.