arXiv：cs.LG· Maxwell Fishelson, Mehryar Mohri·· 4 小时前AI 评分38
高维在线校准：基于调和权重的多维预测校准算法
High-dimensional online calibration from harmonic weights
AI 导读
研究者提出首个针对 d 个二元结果同时预测的在线校准算法，达到 ε-校准所需的轮数对维度 d 呈多项式级（d^{O(1/ε)}），相比此前边界实现了维度依赖的指数级改进。
正文
Abstract:We study the online calibration of multidimensional forecasts over an arbitrary convex set $Y\subseteq\mathbb{R}^d$ relative to an arbitrary error norm $\|\cdot\|_{L}$. For forecasting $d$ binary outcomes simultaneously ($Y=[0,1]^d$), we give the first algorithm that achieves $\varepsilon$-calibration in a number of rounds that is polynomial in $d$ for every fixed accuracy. It requires $d^{O(1/\varepsilon)}$ rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting ($Y=\Delta_d$), we obtain the same $d^{O(1/\varepsilon)}$ rate, improving the $d^{\widetilde{O}(1/\varepsilon^2)}$ bounds of Peng and Fishelson et al.
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 norm. More generally, it achieves $\varepsilon$-calibration after $\exp(O(\gamma(Y,L)/\varepsilon))$ rounds, where $\gamma(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 $L$. This optimality result may be of independent interest.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07740 [stat.ML] |
| (or arXiv:2610.07740v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07740 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Maxwell Fishelson [view email]
[v1]
Tue, 6 Oct 2026 04:36:12 UTC (123 KB)
来源：arXiv：cs.LG · arxiv.org