We study a sequential binary prediction setting where the forecaster is evaluated in terms of the calibration distance, which is defined as the $L_1$ distance between the predicted values and the set of predictions that are perfectly calibrated in hindsight. This is analogous to a calibration measure recently proposed by B{\l}asiok, Gopalan, Hu and Nakkiran (STOC 2023) for the offline setting. The calibration distance is a natural and intuitive measure of deviation from perfect calibration, and satisfies a Lipschitz continuity property which does not hold for many popular calibration measures, such as the $L_1$ calibration error and its variants. We prove that there is a forecasting algorithm that achieves an $O(\sqrt{T})$ calibration distance in expectation on an adversarially chosen sequence of $T$ binary outcomes. At the core of this upper bound is a structural result showing that the calibration distance is accurately approximated by the lower calibration distance, which is a continuous relaxation of the former. We then show that an $O(\sqrt{T})$ lower calibration distance can be achieved via a simple minimax argument and a reduction to online learning on a Lipschitz class. On the lower bound side, an $\Omega(T^{1/3})$ calibration distance is shown to be unavoidable, even when the adversary outputs a sequence of independent random bits, and has an additional ability to early stop (i.e., to stop producing random bits and output the same bit in the remaining steps). Interestingly, without this early stopping, the forecaster can achieve a much smaller calibration distance of $\mathrm{polylog}(T)$.

我们研究了一种顺序二进制预测设置，在其中预测者根据校准距离进行评估，该距离定义为预测值与事后完美校准的预测集之间的L1距离。我们证明了存在一种预测算法，可以在对手选择的T个二进制结果序列上期望实现O(√T)的校准距离，证明了校准距离可以通过较低的校准距离准确近似得出，并且可以通过在线学习和Lipschitz类的简单极小最大化方法实现O(√T)的较低的校准距离。我们还证明，即使在对手输出的独立随机比特序列时，并且具有提前停止（即，在剩余步骤中停止产生随机比特并输出相同的比特）的额外功能，无法避免出现Ω(T^(1/3))的校准距离。有趣的是，如果没有提前停止，预测者可以实现一个较小的校准距离为polylog(T)。

关于顺序预测中的校准距离