arXiv:2502.16387cs.LGcs.DS2025-02NeurIPS被引 13

提出新型校准方法,实现更优的预测误差与后悔值同时优化。

Simultaneous Swap Regret Minimization via KL-Calibration

  • 引入伪KL校准新概念,统一处理多种损失函数的校准问题。
  • 算法在T步内实现O(T^{1/3})的伪交换后悔和校准误差。
  • 适用于平滑可微的正规损失函数,适合在线学习与可靠性预测场景。

校准是确保概率预测可靠性的基础概念,需使其与真实结果一致。近年来研究聚焦于更易优化的校准度量,如鱼森等(2025)证明通过最小化平方损失的伪交换后悔,可实现O(T^{1/3})的伪ℓ₂-校准误差,并推广至所有有界正规损失。本文进一步拓展:(a) 算法对任意二阶连续可微的正规损失(如Tsallis熵)同时实现O(T^{1/3})的交换后悔;(b) 该边界不仅适用于基于预测分布的伪交换后悔,也适用于基于实际实现预测的真实交换后悔。为此,我们提出更强的(伪)KL校准概念,并证明其与(伪)交换后悔对数损失等价。我们证明存在算法达到O(T^{1/3}) KL校准误差,并给出显式算法实现伪KL校准误差。此外,同一算法以≥1−δ的概率实现O(T^{1/3}(log T)^{-1/3} log(T/δ))的交换后悔,从而保证O(T^{1/3}) ℓ₂-校准误差。技术贡献包括一种新的随机舍入方法与非均匀离散化方案,用于最小化对数损失下的交换后悔。

原文摘要 · Abstract (English)

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.

在线学习校准后悔最小化概率预测

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。