High-dimensional online calibration from harmonic weights

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 $\Vert \cdot {\Vert }_L$. For forecasting $d$ binary outcomes simultaneously ($Y=[0,1{]}^d$), we give the first algorithm that achieves $\epsilon$-calibration in a number of rounds that is polynomial in $d$ for every fixed accuracy. It requires $d^{O(1/\epsilon )}$ rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting ($Y={\Delta }_d$), we obtain the same $d^{O(1/\epsilon )}$ rate, improving the $d^{\tilde{O}(1/{\epsilon }^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 $\epsilon$-calibration after $\exp (O(\gamma (Y,L)/\epsilon ))$ 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.