WorksComputer Science
A Matching Lower Bound for Online Smooth Calibration
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 and (Qiao and Zheng, 2024), where 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 . This lower bound matches the known upper bound up to universal constants, and further implies 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.
Introduction
We study the sequential binary forecasting problem introduced by Foster and Vohra [7]. Over rounds, a forecaster and an adversary interact as follows. At each round , the forecaster predicts a probability that the next binary outcome equals 1, and the adversary simultaneously selects the outcome . Both and are then revealed, and may factor into the subsequent actions of both players. This problem abstracts many applications in which probabilistic predictions are issued sequentially, including weather forecasting ([3, 5]), uncertainty quantification of machine learning models ([10]), fair risk prediction ([14]), and forecasting for downstream decision makers ([17]).
A natural requirement for the predictions to be interpretable as probabilities is calibration ([5]): among the rounds on which the forecaster predicts a value , the outcome should equal 1 in an fraction of them. Formally, the forecaster is perfectly calibrated if for every . The most widely used measure of the violation of this condition is the calibration error, also known as the expected calibration error (ECE),
where only the values contribute to the sum. However, ECE is discontinuous in the predictions. Suppose that contains equally many 0s and 1s. Then predicting in every round gives zero ECE. If each is instead perturbed to for tiny, distinct, nonzero , then every round falls into its own bin, and ECE jumps to , although the predictions are essentially unchanged.
This sensitivity motivates the smooth calibration error [16, 2], which tests the residuals against all bounded Lipschitz functions of the predictions,
where is the class of 1-Lipschitz functions from to . Since nearby predictions receive nearby weights, smCE is robust to small perturbations of the predictions, and in the example above it remains small.
For smooth calibration error, however, a gap remains in the sequential setting. Qiao and Zheng [19] gave a forecaster that achieves smooth calibration error against any adversary. It might appear obvious that this rate is tight, since independent fair outcomes make the cumulative residual of order when the forecaster predicts . Surprisingly, Qiao and Zheng [19] showed that this argument is incorrect: against independent fair outcomes, a forecaster can compensate for past residuals with slightly biased predictions, and achieve only polylogarithmic smooth calibration error. Their adversary circumvents this by generating fair outcomes until the error is large and then stopping early with constant outcomes, which yields an lower bound. This leaves the following question:
Is smooth calibration error unavoidable in sequential prediction?
In this paper, we answer this question affirmatively. We construct a new adaptive adversary whose outcome mean moves with the forecaster’s cumulative residual, which makes compensating for past residuals costly, and show that it forces every forecaster to incur expected smooth calibration error, improving the lower bound of Qiao and Zheng [19] and matching the known upper bound. Since smooth calibration error lower bounds both calibration distance and lower calibration distance up to a constant factor, our result also implies matching bounds for these two measures. A comparison of our results and directly related previous results are summarized in Table 1.
Table 1. Comparison of upper and lower bounds on the minimax expected calibration error in the simultaneous adaptive forecasting protocol. In this table, is the total number of interactions, smCE stands for smooth calibration error, LowerCalDist stands for lower calibration distance, and CalDist stands for calibration distance. The lower bounds on lower calibration distance and calibration distance are direct consequence of the lower bound on smooth calibration error, as detailed in Remark 3.2.
Notation. For a positive integer , let . We write and for expectation and probability, and for an indicator. We use calligraphic letters for sets and strategies. The notation and hides universal positive constants, and denotes matching bounds in both directions. We write if for a universal constant , and if and .
Related Work
Sequential Calibration. Sequential calibration studies probabilistic forecasting of binary outcomes, where the forecaster issues a prediction before observing each outcome, and the outcomes may depend on previously revealed predictions. Foster and Vohra [7] established the existence of randomized forecasters that achieve asymptotic calibration. Foster [6] subsequently gave an algorithm based on Blackwell’s approachability theorem, which randomizes between two neighboring forecast values. For the classical calibration error, these approaches yield an expected error, and Hart [12] gave a direct minimax proof of this rate. Dagan et al. [4] improved the upper bound to for a universal constant , using a forecaster based on the sign-preservation-with-reuse game. For smooth calibration error and calibration distance, Qiao and Zheng [19] established an expected error through a minimax argument and online learning over a Lipschitz function class. Arunachaleswaran et al. [1] subsequently proposed the Almost-One-Step-Ahead algorithm, an explicit deterministic forecaster that guarantees calibration distance at most on every outcome sequence. Calibration has also been studied across multiple subpopulations ([14, 11]), in omniprediction ([8]), and for forecasts used by downstream decision makers ([17, 15]), including guarantees based on smooth calibration ([13, 9]).
Calibration Lower Bounds and Adversary Design. For the classical calibration error, independent fair outcomes already yield an lower bound. Qiao and Valiant [18] strengthened this to via early stopping and sidestepping. Their adversary generates Bernoulli outcomes in successive phases and adjusts the probabilities according to the signs of the accumulated forecasting errors, so that errors from earlier phases are difficult to cancel, and its analysis relies on a combinatorial sign-preservation game. Dagan et al. [4] further obtained an lower bound with an oblivious adversary, whose outcomes are generated independently of the forecaster’s predictions. For smooth calibration error and calibration distance, Qiao and Zheng [19] proved an lower bound with an adversary that generates independent fair bits until a history-dependent stopping time and then repeats a fixed outcome. They also showed that, without this stopping mechanism, independent fair outcomes admit a forecaster with only polylogarithmic expected error. Our adversary retains the constant continuation after stopping, but replaces the fair bits with Bernoulli outcomes whose mean depends on the cumulative forecasting residual. Combined with an exact stopped quadratic identity, this yields an lower bound on the expected smooth calibration error, matching the known upper bound.
Preliminaries
We consider an online binary forecasting game between a forecaster and an adversary over rounds. At each round , the forecaster predicts a probability and the adversary simultaneously selects an outcome . Both and may be randomized and may depend on the history , but not on the opponent’s action at round . Both are then revealed. We write and for the outcome and forecast sequences. The forecaster aims to keep the smooth calibration error ([16, 2]) of the realized sequences small. Our goal is to characterize the minimax smooth calibration error
where and range over all forecaster and adversary strategies, and and are the trajectories sampled jointly through the interaction and the distribution given by and , respectively, and is the smooth calibration error defined as follows.
Definition 3.1 (Smooth calibration error). Let be the class of all 1-Lipschitz functions from to . The smooth calibration error of is
Definition 3.1 requires the forecaster to be calibrated around every value , while treating nearby forecasts as essentially the same. Specifically, for any fixed , among the rounds in which the forecaster predicts approximately , the outcome should equal 1 in approximately a fraction of them. Suppose this fails around some , say the residuals add up to a large positive amount. Then a test that is a small positive bump around and vanishes elsewhere collects this residual while ignoring all other rounds, so smCE is large. On the other hand, the Lipschitz constraint prevents from fluctuating rapidly near . Consequently, the residuals for all are effectively grouped together, and an over-prediction at one value can be offset by an under-prediction at a nearby value. This makes smCE robust to small perturbations of the forecasts, in contrast to the classical expected calibration error (ECE), which treats every forecast value as a separate bin and can change drastically under arbitrarily small perturbations. In short, smCE asks the forecaster to be calibrated at every scale coarser than the resolution of its forecasts, which is the property that matters when forecasts are used by downstream decision makers with smooth responses.
Remark 3.2 (Distance-based measures). Besides smCE, two distance-based calibration measures have been studied: the calibration distance and the lower calibration distance ([2, 19]). The calibration distance is the distance from to the nearest perfectly calibrated forecast sequence,
where is the set of perfectly calibrated forecast sequences. The lower calibration distance relaxes this by allowing randomized repairs,
where is the set of all such that each is a finitely supported distribution on and for every . Since every corresponds to the point masses in , we have . Moreover, Blasiok et al. [2] implies . Therefore, any lower bound on smCE yields a lower bound of the same order on both LowerCalDist and CalDist.
Adaptive Adversary and Lower Bounds
In this section, we show that the upper bound is tight by constructing a single adaptive adversary that forces every forecaster to incur expected smooth calibration error. We describe the adversary in Section 4.1, state the main result in Section 4.2, and prove it in Section 5.
Construction of the adversary
We summarize the adversary in Algorithm 1, which follows the early-stopping design of Qiao and Zheng [19]. In particular, the adversary keeps track of the cumulative residual
and operates in two phases separated by the threshold : an active phase, in which the outcomes are random, and a frozen phase, in which the outcomes are constant. We explain the design of each phase in turn.
Freezing a Large Residual. We start with the easy case. Note that is the score of the constant test and is the score of , so that . Hence, once the residual reaches the threshold, i.e., at some round , the adversary only needs to keep it there until the end. This is achieved by raising the flag frozen and repeating the constant outcome in all remaining rounds. If , every later increment is nonnegative whatever the forecaster predicts, and symmetrically for . Therefore never decreases after the crossing, and .
Random Outcomes Force the Forecaster to Adjust. It remains to handle forecasters that keep the residual below the threshold. In the active phase, the adversary draws using fresh randomness, so that the residual behaves like a random walk. To see this, let be the conditional variance of . Ignoring the frozen phase for the moment and summing the expected increments of over all rounds, we obtain
When is bounded away from or , is bounded away from zero, so the first sum is of order . Hence, if the forecaster makes no adjustment, for example, , then the residual grows to order and reaches the threshold with constant probability. The only way to keep the residual small is to make the cross term in (3) negative, that is, to manage to choose such that has the opposite sign of , which pushes the residual back toward zero.
Algorithm 1 Residual-Dependent Adversary
Input: horizon ; set ,
; frozen false
for do
if frozen then
else
Draw
end if
Reveal , observe the learner’s prediction , and set
if frozen false and then
frozen true;
end if
end for
Penalizing the Adjustment. Such adjustment is detected by the affine test . Indeed, conditioning as before,
In Qiao and Zheng [19], the outcomes in the active phase are fair bits with , so the adjustment is penalized only by the quadratic term . Being second order, this penalty is mild, and the forecaster can control the residual through many small adjustments at little cost. To make the penalty harsher, we let the mean depend on the residual,
so that has the opposite sign of . The second term in (4) then becomes , which is positive precisely when the forecaster adjusts. In other words, the cross term that the forecaster must make negative to control the residual in (3) reappears with the opposite sign in the affine score.
We provide a quick overview of why this adversary achieves lower bound. To show this, we add times (3) to the sum of (4) over all rounds. This cancels the cross terms and roughly leaves
whatever the forecaster does, where the low order term is ignored. Consequently, every forecaster faces a dichotomy: either the residual reaches the threshold and the frozen phase forces error at least , or the game stays in the active phase for most of the rounds and the affine test collects a score of order . As a result, we see that the learner always pays for . Picking leads to the desired rate.
Main Results
In this section, we state our main result: the adversary in Algorithm 1 forces every forecaster to incur smooth calibration error of order .
Theorem 4.1 (Smooth calibration lower bound). For every integer , let denote the adversary in Algorithm 1. Then every randomized forecasting strategy satisfies
Consequently, the minimax smooth calibration error satisfies .
Theorem 4.1 shows that the upper bound of Qiao and Zheng [19] is tight up to a universal constant, improving their lower bound. Moreover, recall from Remark 3.2 that for every outcome sequence and forecast sequence . Combining this with Theorem 4.1 immediately leads to the following corollary.
Corollary 4.2 (Calibration distance lower bound). For every integer , every randomized forecasting strategy satisfies
Corollary 4.2 matches the upper bounds on both distance-based measures in Qiao and Zheng [19] up to a universal constant.
Proof of Theorem 4.1
In this section, we provide the full proof of Theorem 4.1.
Proof of Theorem 4.1. Fix an arbitrary, possibly randomized, forecasting strategy . Let be the trivial -algebra on the probability space, and let for . Then and are independent conditioned on , since the forecaster and the adversary make their decisions simultaneously, and neither observes the other’s private randomness. We lower bound through two kinds of tests, namely the constant tests and , and the affine test , which lead to the following scores:
Moreover, we track the first round at which the residual reaches the threshold ,
and let be the event that the threshold is reached, so that on . Since is -measurable, is a stopping time with respect to .
Our first step is to show that is lower bounded by the maximum of and . If , the threshold is reached at round , and every later outcome equals . Hence every later increment has the same sign as . If , there are no later rounds. Therefore, the constant test has score , which gives the first lower bound. For the second lower bound, suppose and consider . Its score over the first rounds is , and its score in every later round is . Similarly, if , the test has score over the first rounds and score in every later round. Both tests are 1-Lipschitz and take values in . In summary, we have
We now take expectations on both sides of (7) to obtain a lower bound on . To do this, we first compute as follows:
For each fixed , the indicator is -measurable, since . Moreover, on , round is active, so that , where is -measurable. Since and are independent conditioned on , we have on . Therefore,
Consequently, we see that
Similarly, we write as the telescoping sum , where each increment satisfies . Therefore,
For each fixed , both and are -measurable. Moreover, on , recall that , and similarly , where is the variance of Bernoulli. Therefore,
where the second equality uses for the term , and the last equality uses this identity again for the cross term , together with .
Consequently, we see that
Adding times (9) to (8) cancels the cross terms, which yields
Now, taking expectations in the bound from (7) and applying (10), we obtain
where we drop the nonnegative term . We now show that both remaining terms are well behaved. First, since and each increment of the residual has magnitude at most one, we have . Since , we further have , so that and the last term is nonnegative. Second, on every active round , we have , so that by the choice . Hence , which implies . Therefore, writing , we obtain
That is, a long active phase forces a large affine score. On the other hand, by (7), we have , so that , i.e., reaching the threshold often forces a large constant score. Since on , it follows that
Substituting this into (11) gives , i.e., . This completes the proof of Theorem 4.1.
Conclusion
In this paper, we study the minimax smooth calibration error in sequential binary prediction against adaptive adversaries. In particular, we construct a new adversary whose outcome mean moves with the forecaster’s cumulative residual and which switches to constant outcomes once the residual becomes large, so that any attempt to compensate for past residuals is penalized by an affine test. We show that this adversary forces every forecaster to incur expected smooth calibration error, which improves the lower bound of Qiao and Zheng [19] and matches the known upper bound, thereby settling the minimax rate of smooth calibration error, as well as of calibration distance and its relaxation, up to universal constants. Currently, our lower bound relies on an adversary that adapts to the forecaster’s past predictions. Determining the optimal rate against oblivious adversaries, whose outcomes cannot depend on the forecasts, remains an interesting direction for future work.
Acknowledgment
The proof ideas are partially developed by GPT-6 Astra under the authors’ guidance. The authors re-organized the proof, verified the proof details, prepared the draft, and take full responsibility for the contents.
References
- [1]Arunachaleswaran, E. R., Collina, N., Roth, A. and Shi, M. (2025). An elementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM.DOI
- [2]Blasiok, J., Gopalan, P., Hu, L. and Nakkiran, P. (2023). A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing.arxiv.org/abs/2211.16886
- [3]Brier, G. W. (1950). Verification of forecasts expressed in terms of probability. Monthly weather review 78 1–3.doi.org/10.1175/1520-0493(1950)078<0001:vofeit>2.0.co;2
- [4]Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R. and Okoroafor, P. (2025). Breaking the t^(2/3) barrier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing.
- [5]Dawid, A. P. (1982). The well-calibrated bayesian. Journal of the American statistical Association 77 605–610.
- [6]Foster, D. P. (1999). A proof of calibration via blackwell’s approachability theorem. Games and Economic Behavior 29 73–78.
- [7]Foster, D. P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika 85 379–390.DOI
- [8]Garg, S., Jung, C., Reingold, O. and Roth, A. (2024). Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM.arxiv.org/abs/2307.08999
- [9]Gopalan, P., Stavropoulos, K., Talwar, K. and Tankala, P. (2026). The importance of being smoothly calibrated. In 7th Symposium on Foundations of Responsible Computing (FORC 2026).
- [10]Guo, C., Pleiss, G., Sun, Y. and Weinberger, K. Q. (2017). On calibration of modern neural networks. In International conference on machine learning. PMLR.arxiv.org/abs/1706.04599
- [11]Gupta, V., Jung, C., Noarov, G., Pai, M. M. and Roth, A. (2022). Online multivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).DOI
- [12]Hart, S. (2025). Calibrated forecasts: The minimax proof. In Matching, Dynamics and Games for the Allocation of Resources: Essays in Celebration of David Gale’s 100th Birthday. Springer, 153–159.arxiv.org/abs/2209.05863
- [13]Hartline, J., Wu, Y. and Yang, Y. (2025). Smooth calibration and decision making. In 6th Symposium on Foundations of Responsible Computing (FORC 2025).
- [14]Hébert-Johnson, U., Kim, M., Reingold, O. and Rothblum, G. (2018). Multicalibration: Calibration for the (computationally-identifiable) masses. In International conference on machine learning. PMLR.
- [15]Hu, L. and Wu, Y. (2024). Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE.DOI
- [16]Kakade, S. M. and Foster, D. P. (2008). Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences 74 115–130.
- [17]Kleinberg, R., Paes Leme, R., Schneider, J. and Teng, Y. (2023). U-calibration: Forecasting for an unknown agent. In Proceedings of Thirty Sixth Conference on Learning Theory. PMLR.arxiv.org/abs/2307.00168
- [18]Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.arxiv.org/abs/2012.03454
- [19]Qiao, M. and Zheng, L. (2024). On the distance from calibration in sequential prediction. In The Thirty Seventh Annual Conference on Learning Theory. PMLR.arxiv.org/abs/2402.07458