acceptodds
Under review as a conference paper at ICLR 2027

Efficient Sequential Calibration with Error Bound

Abstract

We study the online binary sequential calibration problem. A recent breakthrough by dagan2024breaking overcomes the classical \(T^2/3\) barrier for calibration error. Building on this result, we present an efficient randomized forecaster that achieves a computationally expected calibration error \(O(T^2/3-\varepsilon)\) for some constant \(\varepsilon>0\). Our forecaster combines the SPR-Calibration procedure dagan2024breaking with an outer Blackwell-style correction layer. The SPR-Calibration procedure controls calibration with respect to a surrogate sequence of conditional-mean estimates, while the correction layer controls the additional error incurred when these surrogates are used to approximate the true outcomes. The analysis decomposes the total calibration error into the surrogate calibration error and the residual discrepancy between the surrogate sequence and the true outcomes. The former is bounded by the SPR-Calibration guarantee in dagan2024breaking, and the latter is controlled using a quadratic potential argument together with the sparsity of the SPR-Calibration forecaster.

Primary area:
learning theory
Keywords:
Online L_1 calibration, Blackwell's approachability, computationally efficient algorithm

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_JMbjOpenReview ↗
Rating
4
Confidence
3(−1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Consider a sequential prediction setting - every day, an adversary reveals a context x_t, a learner makes some (mixed) prediction p_t, and the adversary reveals the label y_t. The adversary’s choices at round t can be adaptive and adversarial, meaning they can depend on the entire transcript and realizations of randomness in all rounds t’<t, but not the learner’s prediction p_t. A learner is (L1) calibrated if, on average over the rounds the learner make’s some prediction p_t, the realized outcome by the adversary is approximately p_t. A long line of work studies calibration in this adversarial setting. Classic results [FV98, Hart25] prove that the worst-case rate of calibration error is O(T^{2/3}). Notably, Hart’s result uses the minimax theorem to prove the existence of a calibrated learner, but does not construct one, as the proof assumes that in each round t, the learner has access to the true conditional label distribution from which the adversary is drawing that round’s y_t. Recent work [D+25] broke this long-standing T^2/3 barrier by also proving existence of a calibrated strategy that achieves calibration error O(T^{2/3-eps}). Their proof is non-constructive, as it, similarly to Hart’s, relies on the minimax theorem and thus allows the learner to access the adversary’s mixed strategy in each round.

This paper gives a constructive, computationally efficient algorithm that improves the T^{2/3} upper bound for sequential calibration error. The crux of the algorithm is to estimate the conditional mean of the adversary in each round t, and then pass this estimate to the procedure of Dagan et al (which the algorithm uses as a black-box). The final calibration error of the algorithm depends on the rate of Dagan et al’s algorithm and the quality of the estimate. The conditional mean is estimated via a Blackwell-style approach by solving a finite LP. The final calibration error is given by bounding the discrepancy of this surrogate estimate via a potential argument and then combining it with the bound from Dagan et al.

Critical strengths

The paper is well-written - the exposition is clear. The paper does a good job introducing the relevant related machinery of sequential calibration and clearly states how they use prior work and what ideas are novel to the paper.

Using a Blackwell approach to estimate the conditional means to then use that in the Dagan et al subroutine is a clever idea which was enjoyable to read.

Critical weaknesses

None

Questions for authors

The novel idea in the paper is in Section 3.2 which is the slightly difficult to read. If possible, it would be great to add some explanatory text / intuition here. The rest of the paper is extremely clear but I can imagine this being slightly difficult to parse for readers unfamiliar with Blackwell style machinery. Might be frustrating since this is where the main idea is. For e.g., a sentence explaining what R_{p, t-1} is and why it is useful.

There’s a lot of discussion about the sparsity of Dagan et al’s forecaster and using it in the bound is presented somewhat tersely -- if I’m understanding correctly, to control the expected L1 calibration error via the L2 potential without a naive blowup in the dimension -- but another sentence or two of explanation here might be useful for the reader.

2 comments

Thank you for your thoughtful follow-up. We would like to clarify the nature of the changes in our revision.

The original gap in Lemma 4 arose from our reliance on a lemma from an earlier version of Dagan et al. (2025), whose argument did not directly justify the claimed bound. As reviewer unfc pointed out, the updated version of Dagan et al. (2025) provides a revised construction that addresses this issue. Our changes in the appendix essentially follow this updated construction, which we have reformulated and adapted to the setting of our paper. In particular, the additional technical details concerning the full and reduced transcripts and the rollback-and-reuse mechanism originate from the updated construction of Dagan et al. (2025), rather than from a new approach introduced in our revision.

We would also like to emphasize that the central idea and proof structure of our main result remain unchanged. The main contribution of our paper is the use of a Blackwell-style approachability argument to efficiently simulate the SPR-CALIBRATION procedure without access to the conditional means. Throughout the analysis in the main ext, SPR-CALIBRATION is treated as a black box, and our proof relies only on its calibration-error and prediction-sparsity guarantees. The revised construction affects how these guarantees are established, but does not change how they are used in our main algorithm or proof.

We agree that the additional technical details make the appendix more involved. However, since these details concern the implementation and justification of the existing SPR-CALIBRATION subroutine rather than the central Blackwell-style argument of our work.

We appreciate your feedback and hope this clarification helps distinguish the necessary technical correction from the main conceptual contribution.

Thanks for the clarification. I understand now that the revision comes primarily from the updated construction of Dagan et al, which I was unaware of before. I maintain my original positive review of the paper.

Reviewer_ds9yOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper proves a computationally efficient upper bound of O(T^{2/3-\eps}) for online calibration. The technique combines Blackwell Approachability with the SPR game algorithm from (Dagan et al. 2025).

Critical strengths

The paper presents efforts to fulfill the Blackwell approachability using the SPR game algorithm with a computation cost of O(T^{7/2}logT). This provides a more computationally efficient algorithm than the original SPR game algorithm.

Critical weaknesses

I have several concerns:

  1. I think the paper's technique is solid, but the novelty is a bit unclear to me. Blackwell approachability has been used to design an efficient algorithm for online calibration with sample complexity O(T^{2/3}). It is not a surprising result that the SPR game can be used to implement an efficient algorithm for Blackwell Approachability. I personally would think find this paper more interesting if it gave a technique different from the SPR game that is more efficient.
  2. My biggest concern with this paper is why the result is interesting. My understanding is that the Blackwell's approachability has computation cost O(TlogT). If that's the case, why is the algorithm presented in this paper, with a runtime of O(T^{7/2}logT), interesting, given that the sample complexity has just improved from O(T^{2/3}) to O(T^{2/3-\eps})?
Questions for authors

I am wondering whether the authors attempted to determine whether the algorithm is more computationally efficient through small experiments comparing it with the algorithm in [ABH11]*? Could there be any observable improvements in practice?

*Jacob Abernethy, Peter L. Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent.

Reviewer_ufncOpenReview ↗
Rating
4(+3)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers online prediction to minimize Expected Calibration Error (ECE). Hart gives a minimax proof that the rate O(T2/3)O(T^{2/3}) is achievable. This paper attempts to give a computationally efficient algorithm for online (sequential) ECE minimization at O(T2/3−ϵ)O(T^{2/3-\epsilon}). The prior paper of Dagan et al (2025) shows such a predictor exists, but does not give a computationally tractable algorithm for it. This is an important question, and it is an important result to obtain. I hope that the authors are able to fix the gap in the proof.

There seems to be a gap in Lemma 4. Specifically, Lemma 4. In this proof ss is a bound on the reduced transcript length. The actual transcript length can be longer. However, in the proof it assumes the actual execution has length t<st < s. I have attempted to evaluate whether this is easy to fix or not. Here is what I expect:

  • I believe Lemma 4 is false for Algorithm 5 (I believe that there is a counter example).

  • In Dagan et al. (arxiv v4) has some changes from prior versions that can be incorporated into the algorithms and their bookkeeping. (Section 4.1 and Appendix A.2).

Thus, probably the fix is not so serious given the literature. However, I think it's the authors' job to make this case to us.

Edit: the authors fix of the error in the paper looks to me like it checks out. I'm revising my score to "accept".

Critical strengths
  • This is a well known and important problem. Progress such as the claimed results should be published in top venues.

  • The prose of the paper is quite good.

Critical weaknesses
  • It appears that Lemma 4 establishes a weaker condition than it claims, and this is material for the correctness of the result.

  • The technical parts of the paper are quite dense and hard to follow. I struggled to even read some of the statements of lemmas, which were not self contained.

Questions for authors

Can you please describe whether and how you can address the gap in Lemma 4?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.