acceptodds
Under review as a conference paper at ICLR 2027

Sharp Rates in Online Calibration: Two-Test Lower Bounds and Kernel Geometry

Abstract

Calibrated forecasting in online adversarial settings has been widely studied and occupies a central place in online learning theory. Yet, fundamental gaps still remain in our understanding of minimax rates for a number of key notions of online calibration. In particular, tight online rates for the central smooth calibration and calibration distance notions have remained open, with a substantial gap between the known and bounds. In this work, we settle the minimax rate for both notions at , with the tight lower bound witnessed by a single oblivious adversary. To do so, we develop a simple and general lower-bounding two-test principle, which forces the forecaster to incur calibration error via a single carefully constructed pair of calibration tests. We next demonstrate the wide applicability of our two-test principle. As an example, we settle the minimax rate of the above calibration notions under delayed feedback. Next, we apply our principle to online kernel calibration, which admits Vovk's classical upper bound. We obtain the first matching lower bounds for a wide class of kernels, including the Gaussian and Laplace ones. Yet, we then show that the broader kernel calibration landscape is far too nuanced to permit kernel-agnostic -type rates: instead, kernels that permit various degrees of inter-prediction cancellation can be exploited by the learner to obtain faster rates of or even . This opens up an investigation of minimax calibration rates for different kernel geometries.

Primary area:
learning theory
Keywords:
calibration, online calibration, lower bounds, kernel calibration, online learning, approachability

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_AcYfOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies minimax rates for online calibration. The main contribution is a two-test lower-bound principle, which establishes matching Ω(T)\Omega(\sqrt{T}) lower bounds for smooth calibration and calibration distance, closing the gap between the previously known lower and upper bounds. The paper also studies online kernel calibration and shows that different kernel geometries can lead to rates of Θ(T)\Theta(\sqrt{T}), Θ(log⁡T)\Theta(\log T), or Θ(1)\Theta(1).

Critical strengths

The paper appears to resolve an open problem by closing the existing minimax rate gap for smooth calibration and calibration distance. The two-test lower-bound principle seems to be a useful theoretical contribution. The results on kernel calibration are also interesting. The paper is well written and easy to follow.

Critical weaknesses

I am not familiar with the online calibration literature, so I cannot reliably assess the novelty and significance of the results relative to existing work. Although the mathematical arguments appear reasonable from my limited reading, I am also unable to assess the correctness of all the technical proofs with sufficient confidence.

Questions for authors

NA

1 comment

Thank you so much for your time and review, and your positive assessment. We're glad you found the paper well written!

Reviewer_mZUDOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a central open problem in online calibration theory: the minimax rates of smooth calibration and calibration distance. The authors propose a simple and general ``two-test'' lower-bound principle that rigorously establishes a Θ(T)\Theta(\sqrt{T}) lower bound against a single oblivious adversary, thereby closing the long-standing gap. They further extend the framework to the delayed-feedback setting and to online kernel calibration.

Critical strengths
  1. The paper closes the long-standing Ω(T1/3)−O(T)\Omega(T^{1/3})-O(\sqrt{T}) gap for smooth calibration and calibration distance, establishing the tight rate Θ(T)\Theta(\sqrt{T}). The two-test lower-bound principle is elegant and requires only an oblivious adversary (no adaptive adversary is needed), giving it good generality.

  2. The framework naturally extends to delayed feedback and yields matching tight bounds. It also provides the first matching Ω(T)\Omega(\sqrt{T}) lower bounds for a broad class of kernels that includes the Gaussian and Laplace kernels.

Critical weaknesses

There is a gap in motivation and completeness between the main line of the paper (Sections 2–3) and Section 4. While the fast rates O(log⁡T)O(\log T), O(1)O(1) for kernel calibration in Section 4 are mathematically correct, they rely heavily on somewhat artificial constructions of specific geometric properties (e.g., finite cancellation cover, strict correction). The paper offers little discussion of what these cancellation mechanisms actually mean for real prediction tasks. As a result, Section 4 feels more like a technical enumeration of the rate landscape than a coherent continuation of the main story, weakening overall coherence and interpretability.

Questions for authors
  1. The authors claim that certain kernel structures can achieve O(1)O(1) calibration error via Algorithm 1. Have they considered running small-scale numerical experiments to illustrate these theoretical results? Such experiments could help readers build intuition more quickly.
  2. Given that the introduction presents ``rates determined by kernel geometry'' as an important open direction, could Section 4 discuss more explicitly what general patterns the existing examples reveal, or at least attempt a more structured classification (even if incomplete)?
  3. The ``common response + uniform margin'' conditions of the two-test principle are very effective. At present they appear to be carefully engineered specifically to block cross-prediction cancellation. Have the authors considered giving these two conditions a more general geometric / function-space interpretation, or abstracting them into more intrinsic properties?
3 comments

Thank you so much for your insightful reading of the paper. We answer your specific questions below.

  1. Thank you for suggesting an illustration of bounded-rate kernel calibration. While a numerical example could help, we think that a worked example showing how Algorithm 1 keeps the error bounded in the cosine family would be quite illustrative and explicit, and we will add one. For a short preview, recall that the kernel Kω(p,p′)=cos⁡(ω(p−p′))K_\omega(p,p')=\cos(\omega(p-p')) has feature vector ϕ(p)=(cos⁡(ωp),sin⁡(ωp))\phi(p)=(\cos(\omega p),\sin(\omega p)). For ω>2π\omega>2\pi, the learner can achieve a bounded calibration rate via just three forecasts: c−d,c,c+dc-d,c,c+d, where c=1/2c=1/2 and d=π/ωd=\pi/\omega. Writing v=ϕ(c)v=\phi(c), we have ϕ(c−d)=ϕ(c+d)=−v\phi(c-d) = \phi(c+d) = -v, so the accumulated error can be written as ZtvZ_t v. When Zt>0Z_t>0, predicting c−dc-d or cc with equal probability gives expected increment 12[(y−c)−(y−c+d)]v=−dv/2\tfrac12[(y-c)-(y-c+d)]v=-dv/2 for either outcome yy. Similarly, when Zt<0Z_t<0, mixing cc and c+dc+d equally gives +dv/2+dv/2. Thus the learner can always move the accumulated error toward zero in expectation regardless of the outcome. Since Algorithm 1 minimizes the worst-case score (including the quadratic term), its score is no larger than that of this strategy. The resulting potential bound is E[Vt+1∣Zt]≤(1−η2)Vt+2η2\mathbb E[V_{t+1}\mid Z_t]\le(1-\eta^2)V_t+2\eta^2 for η=d/4\eta=d/4 and Vt=cosh⁡(ηZt)V_t=\cosh(\eta Z_t). Starting from V0=1V_0=1, the inequality keeps EVt≤2\mathbb E V_t\le2, so the expected kernel calibration error satisfies E∣Zt∣≤(log⁡4)/η\mathbb E|Z_t|\le(\log 4)/\eta.

  2. For general positioning and high-level structural remarks about our kernel calibration contributions, please see the general response. We would further like to highlight that the "top-line" story of the paper (which is coherent and self-contained) is that our two-test lower bound machinery can without issues get Θ(T)\Theta(\sqrt{T}) rates not only for the main application (tight smooth calibration and calibration distance rates), but also many other settings, including the delayed-feedback setting and, importantly, a wide class of kernels — including the prominent Gaussian/Laplace case, but not limited to it. Yet, the rest of our kernel calibration results serve to substantially refine this story: (1) As we show, it turns out that Ω(T)\Omega(\sqrt{T}) lower bounds, and consequently our original two-test machinery, are sometimes provably inapplicable, because the minimax rate is faster for some kernels due to their feature maps' susceptibility to gaming-by-cancellation; formalizing how faster rates happen is both an algorithmic task (essentially, how to get sub-root-T approachability?), and a modeling task (what are good definitions of cancellation that enable such faster rates?) (2) Yet, it is still possible to extend the two-test paradigm to obtain more benign Ω(log⁡T)\Omega(\log T) bounds, which are tight for certain such fast kernels (we do note that our two-test logarithmic lower bound uses distinct, and intricate, potential-function bounding machinery than the "main" two-test bound; we leave it open to potentially unify these approaches into an even more general, slow/fast-rate two-test principle).

  3. The common-response and uniform-margin conditions also admit a geometric interpretation in terms of a cone of test directions. Briefly, take two functions x,zx,z in the test space with x(p)>0x(p)>0 throughout and consider the curve p↦(x(p),z(p))p\mapsto(x(p),z(p)). Suppose there is a range of slopes such that each line z=cxz=cx separates forecasts in order: for some rcr_c uniformly away from 0 and 1, z(p)≤cx(p)z(p) \le c x(p) for p<rcp<r_c and z(p)>cx(p)z(p) > c x(p) for p>rcp>r_c. Then any two distinct slopes c1<c2c_1<c_2 in this range give a pair of tests gci=cix−zg_{c_i}=c_i x-z enforcing an Ω(T)\Omega(\sqrt T) lower bound. Indeed, every mixture of the two tests corresponds to a line between them, so Appendix D.1 gives common response, and their gap (c2−c1)x(p)(c_2-c_1)x(p) is uniformly positive by continuity. Our original pair g−,g+g_-,g_+ is a special case of this family, with x=g+−g−x=g_+-g_-, z=−g−z=-g_-, and slopes 00 and 11, respectively. This interpretation thus also shows the freedom we have in choosing the witnesses. We will add this perspective to the paper.

Thank you for your reply. My main concerns regarding Section 4, motivation, Q1, and Q3 have been addressed. Additionally, I appreciate the objective discussion you provided in the General Response regarding the contributions of the paper and the existing open issues. Therefore, I have raised my score from 2 to 3. Please ensure that these clarifications, specific examples, and geometric explanations are incorporated into the final revised version.

Thanks! We appreciate it.

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

This paper studies minimax rates for online calibration under adversarial outcomes. Its primary contribution is to establish tight Θ(T)\Theta(\sqrt{T}) rates for smooth calibration and calibration distance, closing a previously open gap between the known Ω(T1/3)\Omega(T^{1/3}) lower bound and O(T)O(\sqrt{T}) upper bound. The key technical contribution is a general two-test lower-bounding principle: by constructing two test functions with suitable common-response and separation properties, the authors show that a learner cannot simultaneously keep both accumulated calibration errors small. Notably, the resulting lower bounds hold against a single oblivious adversary, without requiring adaptivity.

The paper further extends this framework to delayed feedback and kernel calibration. For kernel calibration, it establishes matching square-root lower bounds for broad classes of kernels, including Gaussian and Laplace kernels. More interestingly, it demonstrates that the minimax rate depends substantially on the geometry of the kernel's feature map. Certain cancellation properties allow faster rates of Θ(log⁡T)\Theta(\log T) or even Θ(1)\Theta(1). To establish these faster rates, the authors introduce an online minimax multiobjective algorithm and develop complementary upper- and lower-bound techniques. Overall, the paper provides both a resolution of important open rate questions and a framework for understanding the diverse behaviors of online kernel calibration.

Critical strengths
  • Establishing tight minimax rates for smooth calibration and calibration distance is a meaningful theoretical contribution. The results close a gap in the existing literature and provide a definitive characterization of the rates in these settings.

  • The two-test framework is conceptually appealing and appears broadly applicable. In particular, the result that a single oblivious adversary suffices is noteworthy, as it shows that adaptivity is not essential for obtaining the optimal lower bounds.

  • Beyond proving square-root lower bounds for familiar kernels, the paper identifies qualitatively different rate regimes arising from feature-map geometry. The examples demonstrating logarithmic and bounded calibration errors are particularly interesting because they show that even seemingly well-behaved kernels can exhibit substantially different minimax behavior.

  • The paper provides formal statements and proofs, with the main text presenting the central ideas and the appendices supplying the technical details. Despite the density of the presentation, the overall development follows a coherent mathematical framework.

Critical weaknesses
  • The introduction does not communicate the central ideas sufficiently clearly. Although the abstract is reasonably well written, the introduction is compressed and does not adequately develop the intuition behind the main technical challenge or explain how the proposed two-test principle overcomes it. In particular, the transition from the general lower-bound framework to the diverse kernel-specific results is difficult to follow on a first reading. A more gradual explanation of the key ideas and their relationships would substantially improve accessibility.

  • The manuscript is overly dense. The paper covers several substantial contributions within a limited main-text page budget. The resulting presentation makes it difficult to distinguish the central contributions from the more specialized extensions and technical developments. In particular, the kernel-calibration section introduces several distinct rate regimes, geometric criteria, and algorithmic tools in relatively quick succession. Better prioritization and a more intuitive explanation of the principal results would make the paper considerably easier to evaluate and understand.

  • The main lower-bound argument is elegant and useful, but its proof is relatively direct once the two test functions satisfying the required conditions have been identified. This raises a question about where the principal conceptual difficulty lies: in the general principle itself, or in constructing appropriate test functions for the different calibration settings. The paper would benefit from a clearer explanation of why this approach was not captured by previous lower-bound techniques and which obstacles it overcomes beyond the specific applications presented here.

Questions for authors
  1. Could the authors clarify more explicitly which aspect of the lower-bound construction constitutes the main conceptual breakthrough? In particular, why do existing lower-bound techniques fail to establish the desired Ω(T)\Omega(\sqrt{T}) rates, and what is the essential new insight that makes the two-test approach successful?

  2. Are there natural, verifiable conditions on a kernel or its feature map that would allow one to distinguish systematically between the Θ(T)\Theta(\sqrt{T}), Θ(log⁡T)\Theta(\log T), and Θ(1)\Theta(1) regimes? Which obstacles prevent the sufficient conditions developed in this paper from yielding a more general classification?

  3. Given the number of results and technical tools introduced, could the authors simplify or reorganize the main text to make the central contributions more accessible? In particular, could the paper provide a more unified explanation of how the two-test framework and the online minimax multiobjective algorithm complement each other?

  4. Is there a broader principle explaining why oblivious adversaries suffice for these calibration lower bounds? Could the authors identify settings in which the same approach is unlikely to work, or in which adaptivity might genuinely change the minimax rate?

1 comment

Thanks so much for your careful reading of our manuscript. We are committed to improving the exposition (indeed made nontrivial by the space constraints).

  1. On the lower-bound side, our main conceptual contribution is indeed to identify how just two calibration tests can force the minimax rate for classical calibration notions, under the right simple conditions. We view this simplicity as a key advantage, not a weakness. The difficulty to overcome was to turn ∼T\sim \sqrt T outcome fluctuations into Ω(T)\Omega(\sqrt{T}) calibration error despite the learner’s ability to offset earlier errors by changing its forecasts. Naive approaches fail: on independent fair-coin labels, O(log⁡3/2T)O(\log^{3/2} T) rates are attainable [QZ’24]. Instead, we have to construct an adversary that creates data “adaptively” to the learner, by “putting pressure” on two tests on which the learner cannot hide the T\sqrt{T} fluctuation, and only then, via a minimax argument, arrive at an oblivious (but complex) hard distribution. The best prior lower bound [QZ’24] used a pair of tests, too, but could only deduce a Ω(T1/3)\Omega(T^{1/3}) rate via an early-stopping argument. Our recognition is that one needs to impose two general, and minimax-rate-optimal, requirements on two tests, such that for any learner's distribution, Nature can choose a single outcome mean away from 0 and 1 that keeps both expected tests' error increments nonnegative in expectation; and that the uniform gap between the tests imprints the ∼T\sim \sqrt{T} outcome noise into the test error difference.

  2. Please see the general response for intended positioning of kernel calibration results. In terms of "natural, verifiable" conditions to distinguish between our kernel rates, we do give such conditions with the caveat that they apply separately to upper and lower bounds (characterizing the entire class of, e.g., O(1)O(1)-rate, kernels remains open). On the upper-bound side, all kernels admit O(T)O(\sqrt{T}) rates; kernels whose feature maps create enough linear dependencies between different predictions’ feature vectors (“cancellation cover”) admit O(log⁡T)O(\log T) rates; kernels whose feature maps make cancellations available to the learner in all test directions admit O(1)O(1) rates. On the lower-bound side, our main two-test theorem provides a checkable and intuitive construction of two tests that guarantee worst-case Ω(T)\Omega(\sqrt{T}) rate, whose “common response” conditions crucially let the adversary grow the learner’s expected error on both tests at once; and if one does not assume this common response property, then one can still obtain (Theorem 7) Ω(log⁡T)\Omega(\log T) if the adversary can come up with a pair of tests where it can grow the learner’s error on one of the tests without substantially improving the learner’s error on the other.

  3. The high-level sense of complementarity between our upper bound techniques and lower bound techniques is: The forecaster looks for cross-prediction cancellations to reduce the calibration error, and the adversary comes up with tests/labels such that error cancellation on some tests must incur extra error on other tests. First, our upper bounds are in fact all achievable via our Algorithm 1: the principle on which it operates is that the next prediction is always chosen so as to either cancel out some of the past calibration error (leading to O(1)O(1) rate), or to prevent it from growing fast (leading to O(log⁡T)O(\log T) or O(T)O(\sqrt{T}) rate). Second, our lower bounds are all guided by finding two “hard-to-cancel” calibration tests, albeit via different constructions to achieve root-T vs. log-T rates.

  4. Our proof constructs an adaptive adversary and then uses minimax to convert it into a single oblivious distribution. The key is that, at each prescribed outcome history, our two tests admit a common response to the fixed learner’s forecast distribution averaged over its private randomness. These responses already define a hard outcome law that can be sampled before play. Minimax then makes the law common to all learners. For the ECE calibration metric, by comparison, an adaptive adversary may choose its next outcome according to the sign of the error in a bucket the learner actually used. That sign can differ across runs with the same outcome history, and averaging over those runs can lose the information that made the adversary’s response effective, so it is not clear whether obliviousness can come for free. Indeed, for ECE, the breakthrough of [QV, STOC’21] used an adaptive adversary, and only later was a strong oblivious one found [DDF+, STOC’25]; whether an optimal-rate oblivious adversary exists remains open.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Author response

We sincerely thank the reviewers for their careful and insightful reading of the manuscript. We take the expository feedback to heart and will revise the manuscript to improve the structure and flow, in particular adding introductory exposition (tying the different results and techniques in this manuscript together) as well as additional illustrative discussions in Section 4 (discussing the kernel calibration contributions). We hope our explanations below and in the individual responses will clarify both the overall map of our contributions and how our techniques fit together. For some common points:

Our contribution map. Our headline contribution is that we solve the longstanding open problem of determining the tight online smooth calibration rate: we pin it down at Θ(T)\Theta(\sqrt{T}), obtaining the same minimax rate for two other key calibration metrics, calibration distance and its “lower distance” variant. The previous state-of-the-art bound [QZ’24] has left a substantial gap Ω(T1/3)−O(T1/2)\Omega(T^{1/3}) - O(T^{1/2}) open, which our paper closes. Our tight bound is in fact witnessed by an oblivious adversary. Conceptually and technically, we distill our lower-bounding construction into a simple and revealing two-test lower bounding paradigm: A forecaster may try to correct past calibration error by choosing future predictions strategically, but the adversary can thwart such “cancellations” in the accumulated error via only a pair of carefully interrelated calibration tests. We show this paradigm has broad applicability: it lets one get tight rates for the same calibration notions even under delayed feedback; and it gives the first tight T\sqrt{T} online rates for a substantial class of kernel calibration metrics. Yet, for kernel calibration, we show our two-test approach does not cover all kernels: some turn out to admit sub-root-T tight rates. We thus develop another intricate two-test lower bound that gives the right Ω(log⁡T)\Omega(\log T) scaling for certain kernels, as well as new algorithmic ideas that let the forecaster obtain such sub-root-T rates for a variety of kernels.

On kernel calibration rates. The classification of all kernel calibration rates is, we believe, difficult and will require substantial follow-up work. We consider posing this open problem, and demonstrating its technical complexity and multifaceted nature, to be one of our manuscript’s contributions. The role of our paper is to set the stage for this further exploration. To provide further background on this: having noted that the two-test lower bound approach gives matching root-T lower bounds for the Laplace and Gaussian (and many other radial) kernels, we initially believed that the right classification for kernel calibration rates may simply be the dichotomy between root-T rates (for rich enough kernels) and Θ(1)\Theta(1) rates, for kernels with easy-to-spot exploitable cross-prediction cancellations. The trigonometric kernel family exhibits exactly this dichotomy: for Kω(p,p′)=cos⁡(ω(p−p′))K_\omega(p,p')=\cos(\omega(p-p')), Theorem 5 gives Θ(T)\Theta(\sqrt T) for 0<ω<2π0<\omega<2\pi and Θ(1)\Theta(1) for ω=0\omega=0 or ω≥2π\omega\ge2\pi. It was thus quite surprising to discover that kernels with tight log T rates exist — and that these log T rates can moreover arise via natural, even if nontrivial, lower and upper bound constructions. Here too we obtain an exact classification within a family: for the rank-two profiles satisfying the piecewise monotonicity and endpoint-plateau assumptions of Corollary 1, the rate is Θ(log⁡(T+1))\Theta(\log(T+1)) if pairs of forecasts with the same feature direction cover the whole interval in the sense of Definition 9, and Θ(T)\Theta(\sqrt T) otherwise. As such, we present the three rates O(1)-Theta(log T)-Theta(sqrt T) with the overall goal of noting that well-founded “in-between” tight rates exist for kernel calibration, with the log-T rate kernels playing the role of a certificate of such. The intention is for this provable existence of intermediate rates to motivate follow-up investigations into filling these gaps, with concrete leads provided by our techniques.

To expand our current results into a full classification of kernel rates, the main obstacle is: Can one define a parameterized “cancellation property” of kernel feature maps yielding tight calibration rates depending on the parameter? Such a general cancellation property, if indeed succinctly definable, may have a highly intricate geometric and combinatorial form. Our current definitions of cancellation properties, one giving O(1) rates and one O(log T) rates, are at a high level related, but have not been unified into a single criterion. On the algorithmic side, the picture looks more hopeful: our Algorithm 1 can give all of the rates we prove — but the caveat is that it is in reality a meta-algorithm, still requiring kernels’ cancellation properties as (meta-)input: cf. our O(log T) algorithm that feeds a kernel’s “cancellation cover” into Algorithm 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.