Research
Sharp Integrality Gaps in Calibration Distance
arXiv:2610.05679v1 Announce Type: new Abstract: We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absol
arXiv:2610.05679v1 Announce Type: new Abstract: 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 = 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.
Related
- Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift
- Conformal Calibration Transfer
- Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling
- An analysis of binary isotonic regression: degrees of freedom and implications for calibration
Source: arXiv cs.LG | 2026-10-06