Binghui Peng, Columbia University

Abstract

In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $exp(d)$ days to achieve non-trivial calibration.

In this talk, I will present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $epsilon > 0$, our forecaster becomes $epsilon$-calibrated after $T = d^{O(1/epsilon^2)}$ days, importantly, this guarantee holds against an adaptive adversary. Our result resolves open questions posed by [Abernethy-Mannor'2011, Hazan-Kakade'2012].

In addition to its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows.

Paper link: https://arxiv.org/abs/2504.09096, to appear in FOCS 2025.