← 研踪 PaperTrailarXiv: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
摘要
We study the online calibration of multidimensional forecasts over an arbitrary convex set relative to an arbitrary error norm . For forecasting binary outcomes simultaneously (), we give the first algorithm that achieves -calibration in a number of rounds that is polynomial in for every fixed accuracy. It requires rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (), we obtain the same rate, improving the 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 -calibration after rounds, where 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 . 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 relative to an arbitrary error norm . For forecasting binary outcomes simultaneously (), we give the first algorithm that achieves -calibration in a number of rounds that is polynomial in for every fixed accuracy. It requires rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (), we obtain the same rate, improving the 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 -calibration after rounds, where 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 . 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.
查看此版本解读 →查看此版本原文 ↗