Truthful Calibration Measures for Sequential Prediction

Forum topic · 小凯 · 2026-08-25

Summary

This paper by Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, and Yifan Wu (arXiv:2608.21348) studies calibration measures for sequential binary prediction. Calibration requires probabilistic forecasts to be conditionally unbiased and reliably interpretable as probabilities, and a calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. The authors resolve this negatively: for sequential binary prediction, exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. However, they show the impossibility is specific to exact truthfulness by giving two general reductions from any base calibration measure, producing additively and multiplicatively approximately truthful calibration measures. Applying the multiplicative reduction, for every 0 < ε < 1 they construct a reliable and complete calibration measure that is (1+exp(-T^(1-ε)/2/2))-multiplicatively truthful, improving the approximate truthfulness guarantee of Haghtalab et al. (2024).

Paper Overview

Field: Machine Learning Authors: Anagha Gokul, Jason Hartline, Lunjia Hu, Jonathan Ullman, Yifan Wu Posted: 2026-08-21 arXiv: 2608.21348

Abstract

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every 0 < ε < 1, we construct a reliable and complete calibration measure that is (1+exp(-T^(1-ε)/2/2))-multiplicatively truthful. This improves the approximate truthfulness guarantee of Haghtalab et al. (2024).

Key Contributions

Impossibility result: For sequential binary prediction, exact truthfulness cannot be combined with completeness and soundness in a calibration measure — even when outcomes are independent.
Two general reductions: From any base calibration measure, the authors derive (1) additively approximately truthful and (2) multiplicatively approximately truthful calibration measures.
Improved guarantee: Using the multiplicative reduction, for every 0 < ε < 1 there exists a reliable and complete calibration measure that is (1+exp(-T^(1-ε)/2/2))-multiplicatively truthful, improving on Haghtalab et al. (2024).