High-dimensional Online Calibration: Harmonic Weights and Harmonic Analysis
We study the online calibration of multidimensional forecasts over an arbitrary convex set. For forecasting over the hypercube, we give the first algorithm that achieves ε-calibration in a number of rounds polynomial in the dimension, exponentially improving on all previous bounds.
Our algorithm is remarkably simple: on each round, it predicts using a harmonically weighted distribution over harmonically smoothed past outcomes. The key to its success is a surprising property of the discrete Hilbert transform!