Sharp Rates in Online Calibration: Two-Test Lower Bounds and Kernel Geometry

Calibrated forecasting in online adversarial settings has been widely studied and occupies a central place in online learning theory. Yet, fundamental gaps still remain in our understanding of minimax rates for a number of key notions of online calibration. In particular, tight online rates for the central smooth calibration and calibration distance notions have remained open, with a substantial gap between the known $\Omega (T^{1/3})$ and $O(\sqrt{T})$ bounds. In this work, we settle the minimax rate for both notions at $\Theta (\sqrt{T})$, with the tight lower bound witnessed by a single oblivious adversary. To do so, we develop a simple and general lower-bounding two-test principle, which forces the forecaster to incur $\Omega (\sqrt{T})$ calibration error via a single carefully constructed pair of calibration tests. We next demonstrate the wide applicability of our two-test principle. As an example, we settle the minimax rate of the above calibration notions under delayed feedback. Next, we apply our principle to online kernel calibration, which admits Vovk's classical $O(\sqrt{T})$ upper bound. We obtain the first matching $\Omega (\sqrt{T})$ lower bounds for a wide class of kernels, including the Gaussian and Laplace ones. Yet, we then show that the broader kernel calibration landscape is far too nuanced to permit kernel-agnostic $\sqrt{T}$-type rates: instead, kernels that permit various degrees of inter-prediction cancellation can be exploited by the learner to obtain faster rates of $\Theta (\log T)$ or even $\Theta (1)$. This opens up an investigation of minimax calibration rates for different kernel geometries.