arXiv:2607.19689stat.MLcs.DS2026-07被引 1

提出在线预测校准新算法,实现误差与校准的最优权衡。

Optimal Recalibration of an Online Predictor

  • 基于黑威尔逼近框架设计在线校准算法,支持任意提示序列。
  • 在约 ε⁻³ 轮内达到 (ε, ε²) 校准,对平方损失为最优。
  • 可与在线优化结合,同时实现高精度校准与近优误差,适合分布漂移场景。

我们研究在线预测校准问题:给定任意预测提示序列,学习者需输出新预测,在满足校准的同时,相对于原预测的超额误差极小。本文提出一种在线算法,在 Lipschitz 正确损失下,可在约 ε⁻³ 轮内实现 (ε, ε²)-校准,并利用 [HTY26] 的同步黑威尔逼近扩展框架。我们证明该权衡对平方损失是紧的,即不可再优。还建立了配套的 𝒦₂-校准定理,结果相差一个对数因子。作为主要应用,将本算法与 [FH23] 的在线精炼方法结合,首次在相同渐近速率下同时实现平滑正确损失下的 ε-校准与 ε²-近优误差,优于以往分别达成或 ε 依赖更差的工作。其中 𝒦₂ 变体回答了 [CHJL26] 关于同时实现近优误差与校准率的问题。此外拓展至多提示序列情形。最后在发生分布漂移的分类数据集上进行实证评估。

原文摘要 · Abstract (English)

We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves $(\varepsilon, \varepsilon^2)$-recalibration for Lipschitz proper losses in $T \approx \varepsilon^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We show that this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. We also prove a companion $\mathcal{K}_2$-recalibration theorem that obtains the same tradeoffs up to a logarithmic factor. As our main application, we show how our recalibration algorithms can be combined with the online refinement method of [FH23] to obtain simultaneous $\varepsilon$-calibration and $\varepsilon^2$-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\varepsilon$ dependence. In particular, the $\mathcal{K}_2$ variant answers a question of [CHJL26] on simultaneously achieving near-optimal calibeating and calibration rates. We also derive extensions to settings with multiple hint sequences. Finally, we empirically evaluate our algorithms on a classification dataset undergoing distribution shift.

在线学习预测校准算法优化分布漂移

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