跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.07740 · v2

High-Dimensional Online Calibration from Harmonic Weights

首次提交 2026-10-06 12:36
版本更新 2026-11-14 02:59
雷达观测 2026-11-16 13:44
arXiv ↗PDF ↗

摘要

We study the online calibration of multidimensional forecasts over an arbitrary convex set Y⊆RdY\subseteq\mathbb{R}^d relative to an arbitrary error norm ∥⋅∥L\|\cdot\|_L. For forecasting dd binary outcomes simultaneously (Y=[0,1]dY=[0,1]^d), we give the first algorithm that achieves ε\varepsilon-calibration in a number of rounds that is polynomial in dd for every fixed accuracy. It requires dO(1/ε)d^{O(1/\varepsilon)} rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (Y=ΔdY=Δ_d), we obtain the same dO(1/ε)d^{O(1/\varepsilon)} rate, improving the dO~(1/ε2)d^{\widetilde{O}(1/\varepsilon^2)} bounds of Peng and Fishelson, Golowich, Mohri, and Schneider. Our algorithm is simple: on each round, it outputs a harmonically weighted distribution over harmonically smoothed past outcomes. The same algorithm works for every forecast set and error norm. More generally, it achieves ε\varepsilon-calibration after exp⁡(O(γ(Y,L)/ε))\exp(O(γ(Y,L)/\varepsilon)) rounds, where γ(Y,L)γ(Y,L) is a geometric parameter defined by a matrix discrepancy problem. The harmonic weights are motivated by the fact that the discrete Hilbert transform matrix achieves the optimal discrepancy up to a universal constant, simultaneously for every LL. This optimality result may be of independent interest. The same harmonic responses also yield an algorithm for high-dimensional Blackwell approachability. Its guarantees are governed by a sharpened geometric parameter that captures the joint geometry of the outcome and action sets.

作者备注:In-depth talk about this work: https://youtu.be/2aL0viNUveE

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-14 02:59 · 最新观测版本

High-Dimensional Online Calibration from Harmonic Weights

We study the online calibration of multidimensional forecasts over an arbitrary convex set Y⊆RdY\subseteq\mathbb{R}^d relative to an arbitrary error norm ∥⋅∥L\|\cdot\|_L. For forecasting dd binary outcomes simultaneously (Y=[0,1]dY=[0,1]^d), we give the first algorithm that achieves ε\varepsilon-calibration in a number of rounds that is polynomial in dd for every fixed accuracy. It requires dO(1/ε)d^{O(1/\varepsilon)} rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (Y=ΔdY=Δ_d), we obtain the same dO(1/ε)d^{O(1/\varepsilon)} rate, improving the dO~(1/ε2)d^{\widetilde{O}(1/\varepsilon^2)} bounds of Peng and Fishelson, Golowich, Mohri, and Schneider. Our algorithm is simple: on each round, it outputs a harmonically weighted distribution over harmonically smoothed past outcomes. The same algorithm works for every forecast set and error norm. More generally, it achieves ε\varepsilon-calibration after exp⁡(O(γ(Y,L)/ε))\exp(O(γ(Y,L)/\varepsilon)) rounds, where γ(Y,L)γ(Y,L) is a geometric parameter defined by a matrix discrepancy problem. The harmonic weights are motivated by the fact that the discrete Hilbert transform matrix achieves the optimal discrepancy up to a universal constant, simultaneously for every LL. This optimality result may be of independent interest. The same harmonic responses also yield an algorithm for high-dimensional Blackwell approachability. Its guarantees are governed by a sharpened geometric parameter that captures the joint geometry of the outcome and action sets.

查看此版本解读 →查看此版本原文 ↗