High-dimensional online calibration from harmonic weights
Abstract
We study the online calibration of multidimensional forecasts over an arbitrary convex set Y⊆ℝd relative to an arbitrary error norm |·|L. For forecasting d binary outcomes simultaneously (Y=[0,1]d), we give the first algorithm that achieves ε-calibration in a number of rounds that is polynomial in d for every fixed accuracy. It requires dO(1/ε) rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (Y=Δd), we obtain the same dO(1/ε) rate, improving the dÕ(1/ε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 ε-calibration after exp(O(γ(Y,L)/ε)) rounds, where γ(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.
Related
- An F-Type Normal-Reference Calibration for High-Dimensional Covariance Testing
- Large-scale linear hypothesis testing for high-dimensional online M-estimation
- Multiple harmonic star sums involving central binomial coefficients as weights
- When does conformal calibration need censoring weights? Cause-of-failure prediction sets under competing risks
- Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
BibTeX
@misc{fishelson2026highdimensional,
title = {{High-dimensional online calibration from harmonic weights}},
author = {Maxwell Fishelson and Mehryar Mohri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07740},
eprint = {2610.07740},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07740},
}
RIS
TY - UNPB
TI - High-dimensional online calibration from harmonic weights
AU - Maxwell Fishelson
AU - Mehryar Mohri
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07740
UR - https://arxiv.org/abs/2610.07740
AB - We study the online calibration of multidimensional forecasts over an arbitrary convex set Y⊆ℝ^d relative to an arbitrary error norm |·|_L. For forecasting d binary outcomes simultaneously (Y=[0,1]^d), we give the first algorithm that achieves ε-calibration in a number of rounds that is polynomial in d for every fixed accuracy. It requires d^O(1/ε) rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (Y=Δ_d), we obtain the same d^O(1/ε) rate, improving the d^Õ(1/ε^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 ε-calibration after exp(O(γ(Y,L)/ε)) rounds, where γ(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.
ER -