- 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
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.
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.