High-dimensional online calibration from harmonic weights

We study the online calibration of multidimensional forecasts over an arbitrary convex set Ysubseteqℝ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 varepsilon-calibration in a number of rounds that is polynomial in d for every fixed accuracy. It requires dO(1/varepsilon) rounds, exponentially improving the dimension dependence of previous bounds. For multi-class forecasting (Y=Deltad), we obtain the same dO(1/varepsilon) rate, improving the d^widetildeO(1/varepsilon2) 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(γ(Y,L)/varepsilon)) 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.