Breaking the \({T^{2/3}}\) Barrier for Sequential Calibration

Abstract. A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of time steps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences under the standard [Formula: see text] calibration error metric, which was initially studied by [D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390]. They derived an algorithm with [Formula: see text] calibration error after [Formula: see text] time steps, and showed a lower bound of [Formula: see text]. These bounds remained stagnant for two decades, until [ 30 ] improved the lower bound to [Formula: see text] by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the [Formula: see text] upper bound on calibration error of [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]. We do this by introducing a variant of [M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466]’s game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved upper bound for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error [Formula: see text] for some [Formula: see text], improving [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]’s upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of [ M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466 ], namely [Formula: see text]. Our lower bound is obtained by an oblivious adversary, marking the first [Formula: see text] calibration lower bound for oblivious adversaries.