首个多项式时间在线校准算法，解决高维预测的维度灾难问题。
High dimensional online calibration in polynomial time
- 随机选择基于近期频次的子预测器组合
- 仅需 $d^{O(1/ε^2)}$ 天即可达到 $ε$-校准
- 理论简洁且适用于高维概率预测场景
在在线（序列）校准中，预测者需在 $T$ 天内对有限结果空间 $[d]$ 预测概率分布，目标是实现校准。尽管已知存在渐近校准策略，但其受维度诅咒影响：最优算法需 $/exp(d)$ 天才能达到非平凡校准。本文提出首个渐近校准策略，在多项式轮数内保证非平凡校准。对任意精度 $ε>0$，我们的预测者在 $T = d^{O(1/ε^2)}$ 天后达到 $ε$-校准。我们进一步给出下界，证明至少需要 $T = d^{Ω(/log(1/ε))}$ 轮才能实现 $ε$-校准。该结果解决了 [Abernethy-Mannor'11, Hazan-Kakade'12] 提出的开放问题。算法受近期交换后悔最小化突破 [Peng-Rubinstein'24, Dagan et al.'24] 启发，虽具强理论保障，但形式极为简洁直观：从一组子预测器中随机选择，每组基于最近时间窗口的实证结果频率进行预测。
原文摘要 · Abstract (English)
In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $\exp(d)$ days to achieve non-trivial calibration. In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $ε> 0$, our forecaster becomes $ε$-calibrated after $T = d^{O(1/ε^2)}$ days. We complement this result with a lower bound, proving that at least $T = d^{Ω(\log(1/ε))}$ rounds are necessary to achieve $ε$-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。