Predict to Minimize Swap Regret for All Payoff-Bounded Tasks

Calibration allows predictions to be reliably in-terpreted as probabilities by decision makers. We propose a decision-theoretic calibration error, the Calibration Decision Loss (CDL), defined as the maximum improvement in decision payoff obtained by calibrating the predictions, where the maximum is over all payoff-bounded decision tasks. Vanishing CDL guarantees the payoff loss from miscalibration vanishes simultaneously for all downstream decision tasks. We show separations between CDL and existing calibration error metrics, including the most well-studied metric Expected Calibration Error (ECE). Our main technical contribution is a new efficient algorithm for online calibration that achieves near-optimal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O\left(\frac{\log T T}{\sqrt{T}}\right)$</tex> expected CDL, bypassing the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(T^{-0472})$</tex> lower bound for ECE by Qiao and Valiant [40]. The full version of the paper is titled Calibration Error for Decision Making. We strongly recommend that our readers read the full arXiv version (https://arxiv.org/abs/2404.13503).