cs.LGNov 11, 2026

A Matching Lower Bound for Online Smooth Calibration

Authors: Kaixuan Ji, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

We study smooth calibration error in sequential binary prediction, which measures how far a sequence of probabilistic forecasts is from being calibrated and, unlike the classical expected calibration error, is robust to small perturbations of the forecasts. Against adaptive adversaries, the minimax smooth calibration error is known to lie between Ω(T1/3)Ω(T^{1/3}) and O(T)O(\sqrt{T}) (Qiao and Zheng, 2024), where TT is the number of rounds. In this paper, we close this gap by constructing a new adversary whose outcome mean moves with the forecaster's cumulative residual. This design makes compensating for past residuals costly, and forces every forecaster to incur an expected smooth calibration error of Ω(T)Ω(\sqrt{T}). This lower bound matches the known upper bound up to universal constants, and further implies Ω(T)Ω(\sqrt{T}) lower bounds for calibration distance and lower calibration distance. Overall, our results settle the minimax rates of these calibration measures in sequential prediction. The proof ideas are partially developed by GPT-6 Astra under the authors' guidance.

Figures & tables

Explore similar work

CardsList
  1. The Importance of Being Smoothly Calibrated

    Mar 16, 2026Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1Model CalibrationProbability Calibration

  2. Breaking the T2/3T^{2/3} Barrier for Sequential Calibration

    Jun 19, 2024Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson +3Probability Calibration