2025/04/12 by Binghui Peng, Peng, Binghui · 1 voice · 1 citation
#cs.LG #cs.DS #cs.GT #stat.ML
paper · pdf · doi:10.48550/arxiv.2504.09096
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 work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy ε> 0, our forecaster becomes ε-calibrated after T = dO(1/ε2) days. We complement this result with a lower bound, proving that at least T = dΩ(log(1/ε)) rounds are necessary to achieve ε-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite 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.