Calibration is a fundamental concept that aims at ensuring the reliability of probabilistic predictions by aligning them with real-world outcomes. There is a surge of studies on new calibration measures that are easier to optimize compared to the classical $\ell_1$-Calibration while still having strong implications for downstream applications. One recent such example is the work by Fishelson et al. (2025) who show that it is possible to achieve $O(T^{1/3})$ pseudo $\ell_2$-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. In this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultaneously achieves $O(T^{1/3})$ swap regret for any proper loss with a twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pseudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's actual realized predictions. We achieve so by introducing a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret for log loss. We prove that there exists an algorithm that achieves $O(T^{1/3})$ KL-Calibration error and provide an explicit algorithm that achieves $O(T^{1/3})$ pseudo KL-Calibration error. Moreover, we show that the same algorithm achieves $O(T^{1/3}(\log T)^{-1/3}\log(T/δ))$ swap regret w.p. $\ge 1-δ$ for any proper loss with a smooth univariate form, which implies $O(T^{1/3})$ $\ell_2$-Calibration error. A technical contribution of our work is a new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret for log loss.

翻译：校准是一个基本概念，旨在通过使概率预测与现实结果对齐来确保其可靠性。相较于经典的$\ell_1$校准，近年来涌现出大量关于新校准度量的研究，这些度量更易于优化，同时对下游应用仍具有重要影响。Fishelson等人（2025）的最新工作即为一例，他们证明通过最小化平方损失的伪交换遗憾，可以实现$O(T^{1/3})$的伪$\ell_2$校准误差，这实际上意味着所有具有光滑单变量形式的有界适当损失函数均可达到相同界限。在本研究中，我们从以下方面显著推广了他们的结果：（a）除光滑单变量形式外，我们的算法还能同时对任何具有二阶连续可微单变量形式（如Tsallis熵）的适当损失函数实现$O(T^{1/3})$的交换遗憾；（b）我们的界限不仅适用于使用预测者分布度量损失的伪交换遗憾，也适用于使用预测者实际实现预测度量损失的真实交换遗憾。我们通过引入一种称为（伪）KL校准的新强校准概念实现这一目标，并证明其等价于对数损失的（伪）交换遗憾。我们证明了存在一种算法可实现$O(T^{1/3})$的KL校准误差，并给出一种显式算法实现$O(T^{1/3})$的伪KL校准误差。此外，我们证明同一算法能以概率$\ge 1-δ$对任何具有光滑单变量形式的适当损失函数实现$O(T^{1/3}(\log T)^{-1/3}\log(T/δ))$的交换遗憾，这意味着$O(T^{1/3})$的$\ell_2$校准误差。本研究的技术贡献在于提出了一种新的随机舍入程序和非均匀离散化方案，以最小化对数损失的交换遗憾。