Truthfulness of Calibration Measures
Authors: Nika Haghtalab
Mingda Qiao
Kunhe Yang
Eric Zhao
Venue: NeurIPS 2024 poster (2024)
Keywords: Calibration measures
online learning
sequential calibration
Primary area: online_learning

Abstract: We study calibration measures in a sequential prediction setup. In addition to rewarding accurate predictions (completeness) and penalizing incorrect ones (soundness), an important desideratum of calibration measures is *truthfulness*, a minimal condition for the forecaster not to be incentivized to exploit the system. Formally, a calibration measure is truthful if the forecaster (approximately) minimizes the expected penalty by predicting the conditional expectation of the next outcome, given the prior distribution of outcomes. We conduct a taxonomy of existing calibration measures. Perhaps surprisingly, all of them are far from being truthful. We introduce a new calibration measure termed the *Subsampled Smooth Calibration Error (SSCE)*, which is complete and sound, and under which truthful prediction is optimal up to a constant multiplicative factor. In contrast, under existing calibration measures, there are simple distributions on which a polylogarithmic (or even zero) penalty is achievable, while truthful prediction leads to a polynomial penalty.

Truthfulness of Calibration Measures
Nika Haghtalab, Mingda Qiao, Kunhe Yang, and Eric Zhao University of California, Berkeley
fnika, mingda. qiao, kunheyang, eric. zh) aberkeley edu
Abstract
We study calibration measures in a sequential prediction setup. In addition to re- warding accurate predictions (completeness) and penalizing incorrect ones (sound- ness), an important desideratum of calibration measures is truthfulness, minimal condition for the forecaster not to be incentivized exploit the system. Formally, a calibration measure is truthful if the forecaster (approximately) minimizes the expected penalty by predicting the conditional expectation of the next outcome, given the prior distribution of outcomes. We conduct a taxonomy of existing cali- bration measures. Perhaps surprisingly, all of them are far from being truthful. We introduce new calibration measure termed the Subsampled Smooth Calibration Error (SSCE), which is complete and sound, and under which truthful prediction is optimal up constant multiplicative factor. In contrast, under existing calibration measures, there are simple distributions on which polylogarithmic (or even zero) penalty is achievable, while truthful prediction leads to polynomial penalty.
Introduction
Probability forecasting a central prediction task to wide range of domains and applications, such as finance, meteorology, and medicine [MW84] DF83 WM68 JOKOM12 KSB2I [CV15 BF 02 CAT16]. For forecasts to be useful, a common minimum requirement is that they are calibrated, i.c. the predictions are unbiased conditioned on the predicted value. Formally, for a sequence of T binary events, a forecaster who predicts probabilities in [0, 1] is perfectly calibrated if for every a [0, 1]. among the time steps which a is predicted, an fraction of the outcomes is indeed 1. Since perfectly calibrated forecasts are often unachievable, calibration measures have been introduced to quantify some form of deviation from perfectly calibrated forecasts. Common examples of these measures include the expected calibration error (ECE) FV98). the smooth calibration error KF08) and the distance from calibration [BGHN23.
As these calibration measures are commonly used to evaluate the performance of forecasters, is important that their use encourages forecasters to incorporate the highest quality information available to them (e.g., via their expert knowledge or side information) about the next outcome. This desideratum, formally referred to as truthfulness, requires that a calibration measure incentivizes the forecasters to predict truthfully when the true distribution of the next outcome is known to them. Lack of truthfulness can have severe consequences: it serves poor measure of quality of forecasts, tempts forecasters to make deliberately biased predictions in order to game the system, and erodes trust in predictions provided by third-party forecasters. Given the importance of truthfulness, set out to identify calibration measures that demonstrate truthfulness.
While truthfulness of calibration measures has not been systematically investigated to date, evidence of the lack of truthfulness of some calibration measures has emerged in recent literature. For example. [F2T QV2I) noted that forecaster can lower their ECE by predicting according to the past. This observation was applied in the algorithm of [FE2]] and motivated the "sidestepping" technique in the lower bound proof of (QV2T). More recently, (QZ24) highlighted a large gap in the truthfulness of a recently proposed calibration measure (called the distance from calibration (BGHN23) by
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

showing that in a simple setup of predicting i.i.d. outcomes, the truthful forecaster incurs distance of S2(VT) from calibration but there is a forecasting algorithm that achieves (T) distance from calibration. We call this a polylog(T)-{(( (VV) truthfulness gap. On the other hand, we say that a calibration measure (a, 3) -truthullll if predicting the next outcome according to its conditional distribution incurs a measure that is no more than aOPT B, where OPT is the minimum value of the calibration measure achievable by any forecaster. Faced with evidence that some calibration measures suffer from large truthfulness gaps, we will systematically examine the truthfulness (or gap thereof) of a wide range of calibration measures.
For truthful calibration measure to also be useful it must distinguish accurate predictions from inaccurate ones. After all, a measure that is uniformly 0 regardless of the quality of predictions is perfectly truthful (formally (1, O)-rrutfful) but provides no insights into the quality of the predictions. We formalize the minimum requirement for a measure to be useful by its completeness and soundness when predicting i.i.d. Bernoulli outcomes. The former requires that predicting the outcomes according to the correct parameter of the generating Bernoulli distribution incurs no or (T)) penalty, whereas the latter requires the penalty to be (T(T) when predictions systematically deviate from the correct parameter. An equally important feature of a calibration measure is that defines an ideal that could be asymptotically achieved for all prediction tasks. This is formalized by the existence of forecasting algorithms with an (T) penalty in the adversarial sequential prediction setting [FV98], where the sequence of outcomes is produced by an adaptive adversary.
With these desiderata in place (namely truthfulness, soundness, completeness, and asymptotic calibration), we ask whether there are calibration measures that simultaneously satisfy all these criteria? We answer this question in three parts:
Part I: We show that existing calibration measures do not simultaneously meet these criteria. We conduct a taxonomy of several existing calibration measures in terms of their completeness, soundness and truthfulness (formally defined in Section 2 We show that almost all of them have large truthfulness gaps: There are simple distributions on which an (11) (or even zero) penalty is achievable, while truthful predictions lead to poly(T') penalty; see Table for details.
Indeed, this lack of truthfulness not limited to specific or contrived distributions. the next theorem which we will prove in Appendix B. we strengthen these findings by showing that commonly used notion of calibration systematically ly suffers large truthfulness gaps in most forecasting instances.
Theorem 1.1 (Informal). For every product distribution with marginals bounded away from and 1, the truthful forecaster incurs S2VTT) smooth calibration error but there exists a forecasting algorithm that incurs only polylog(T") smooth calibration error.
notable exception in Table iss the class of calibration measures induced by proper scoring rules, i.e., loss functions for probabilistic predictions that are optimized by truthful forecasts. By definition, these calibration measures are (1, -rrttuffll. However, none of them is complete: as we show in Appendix A even on i.i.d. Bernoulli trials, the optimal and truthful predictions incur an ?(TT) penalty,
Part II: We introduce a new calibration measure, called SSCE, that is sound, complete, and approximately truthful. We do this using simple adjustment to an existing notion of calibration measure: we subsample a subset of the time steps and evaluate the smooth calibration error (KF08) on this sampled set only. We call this the Subsampled Smooth Calibration Error (SSCE) and formally define it in Section 2 Our main result is that SSCE is (O(1), -rrttulff
Theorem 1.2 (Main Theorem). There exists a universal constant e > 0 such that the SSCE is (c. -)-truthful. Furthermore, the SSCE is complete and sound.
As shown in Table I to the best of our knowledge, SSCE is the first calibration measure that simultaneously achieves completeness, soundness, and toivial truthfulness.
While our methodology for constructing this calibration measure is simple, the analytical steps required to establish the (O(1), ()) Oj-truthfulness guarantee are far from simple. We dedicate most of the main body of this paper to illustrating the proof ideas in series of warmups to Theorem T.2
Part II: There is a forecasting algorithm that achieves O(VT) SSCE even in the adversarial setting. While our study of truthfulness of calibration measures is necessarily focused when the

---

Calibration Measure
Complete?
Sound?
Truthful?
Expected Calibration Error, Maximum Swap Regret
0-Q(T) gap
Smooth Calibration, Distance from Calibration, Interval Calibration, Kernel Calibration
v
0-2(VT) gap
U-Calibration Error
v
O(1)-R(VT)) gap
Proper Scoring Rules
(1,0)-truthull
Subsampled Smooth Calibration Error
(0(1), -)-ruutulll
Table 1: Evaluation of existing calibration measures along with SSCE, in terms of completeness. soundness and truthfulness (Definitions 2.2 and 2.5). An a-ß truthfulness gap means that there is a prediction instance on which forecasting according to the true conditional distribution of the next outcome incurs more than 3 penalty, but there a forecasting strategy that incurs at most a penalty. See Appendix for more details.
forecaster knows the conditional distribution the next outcome, it is important to ensure that, even in the adversarial setting, sublinear penalty be achieved for this calibration measure. For this, we study the sequential calibration setting (e.g.. [FV98) where the outcome at time is chosen by an adaptive adversary who has observed the sequence of earlier outcomes and predictions. We show that an O(VT) SSCE is achievable.
Theorem 1.3. In the adversarial sequential calibration setting, there is deterministic strategy for the forecaster that achieves an OVVT) SSCE.
An interesting and important feature of this result is that it achieves an O(VT) rate whereas an O(vT) rate for the expected calibration error is known to impossible to achieve [Q2I]. Together our Theorems 1.2 and 1.3 establish that SSCE is truthful and useful calibration measure.
1.1
Related Work
There is large body of work on calibration, notion that dates back to the 1950s Bri50 Daw82 Daw85] and has been applied to game theory [FV97 HPY23). machine learning [GPSW17] and
algorithmic fairness [KMR17 PRW+ 17 HJKRRIS HIZ23 l. We will restrict our discussion to sequential calibration and the systematic study of calibration measures, which are the closest to this work.
Sequential calibration. Foster and Vohra [FV98 first proved that one can achieve asymptotic calibration on arbitrary and adaptive outcomes. Formally, they gave a forecasting algorithm with an ((T2/3) ECE in expectation, when predicting T binary outcomes chosen by an adaptive adversary. Subsequent work gave alternative and simpler proofs of the result [FL99 Fos99] Har22), extended
the result to other calibration measures K FHI8 FH21 QZ24), and proved lower bounds on the
optimal ECE [QV1). Most closely related to our approach is the work of (FRSTTI) who studied a stronger notion that requires calibration on a family of checking rules, where each checking rule specifies subset of the time horizon. Despite the apparent similarity, their notion is qualitatively different from the SSCE, since we take an expectation over the subsampled horizon, whereas they take the maximum. In particular, no forecaster be calibrated in their definition if the checking rule family contains all subsets of [T', since there always exists checking rule that strongly correlates with the outcomes.
Calibration measures. The recent work of Blasiok, Gopalan, Hu and Nakkiran [GHN23 initiated the rigorous study of calibration measures. Their work focused on the offline setup, where there a known marginal distribution over the feature space, and each predictor maps the feature space to [0, 1]. They proposed to use the distance from calibration the distance from the predictor to the closest predictor that is perfectly calibrated- as the ground truth, and studied whether existing
3

---

calibration measures are consistent with it. Note that completeness and soundness are defined differently in [BGHN23] a calibration measure called complete (resp., sound) if it is upper (resp.. lower) bounded by a polynomial of the distance from calibration. Since the distance from calibration far from being truthful in the online setup (as shown by [Q224), our definition of completeness and soundness set up minimal conditions for an error metric to be regarded as measuring calibration, rather than enforcing closeness to the distance from calibration.
Subsampling. Our new calibration measure is derived from subsampling the time horizon. This simple idea has been shown to be effective in various different contexts, including privacy amplifica- tion in differential privacy (e.g.. [Ste22] Section 6)), handling adversarial corruptions [BLMT22]. as well as adaptive data analysis [Ba23]
Proper scoring rules. Proper scoring rules WM68 are error metrics for probabilistic forecasts that are optimized when the forecaster predicts according to the true distribution. While the error metrics induced by proper scoring rules are (perfectly) truthful by definition, as we show in Appendix [A] they are qualitatively different from the usual calibration measures and, in particular, do not meet the completeness criterion. We note that a recent line of work [CY21 NNW21 LHSW22 PW22 HSLW23] studied the optimization of scoring rules, namely, finding the proper scoring rule that maximally incentivizes the forecaster to exert effort to obtain additional information.
2 Preliminaries
Sequential prediction. We consider the following prediction setup: First, a sequence x E {0.1)7 ii is
sampled from distribution D. At each step E [T]. the forecaster makes a prediction pt E [0, 1]. after
which 2, is revealed. Formally, a deterministic forecaster is a function A: U (0, 1) - [0, 1]. where A(b1, 62. .2...... bi-1) specifies the forecaster's prediction at step t if the first - I observations match b1:(t-1)- Distribution DD and forecaster A naturally induce a joint distribution of pr.p) E
(0, 1) x [0, 1)2 via sampling x ~ DD and predicting pt = (tt1,,
Note that could have defined the forecaster function of both the outcomes 11:(t-1) and the predictions P1:(t-1) in the past. This alternative definition is equivalent to ours, since P1:(t-1) would be uniquely determined by 21:(t-1). We could also have considered randomized forecasters, which are specified by distributions over deterministic forecasters. However, as we will see later, restricting attention to deterministic forecasters does not affect the subsequent definitions.
Calibration measures. The quality of the forecaster's predictions the setting above is quantified by calibration measures. Formally, a calibration measure CM is a family of functions {CMT T e N}. where each CMr maps {0, 1)" x [o, 11"d to [0, T]. We will frequently omit the subscript T, since it is usually clear from the context. With respect to calibration measure CM, the expected penalty incurred by forecaster A on distribution D defined as errcm AD, = ((..)))((DAA) [CM(x, p)).
where (xr, p) (D,A) denotes sampling a sequence x and predictions p from the joint distribution induced by DD and A.
One example of calibration measures is the smooth calibration error introduced by [K008 that is defined as smCE(æ, p) == sup JEF E f(,)) Pt), where is the family of 1-Lipschitz func- tions from [0, 1] to [1, In this work, we introduce a new calibration measure called Subsampled Smooth Calibration Error (SSCE) that is defined by subsampling a subset of the time horizon, and evaluating the smooth calibration eιror on it. We will formally define this measure next. In the following, USi denotes the uniform distribution over a finite set S. For a T -dddimenioonal vector and S S [T' æ denotes the [S| -immessiioaa vector formed by the entries of x indexed by S. Definition 2.1 (Subsampled Smooth Calibration Error). For a sequence of outcomes æ E (0, 1)2 and predictions p E [0, 1J". . the Subsampled Smooth Calibration Error (SSCE) is defined as
T
SSCE(æ,p) ==
E (--Unif(2(zT)
(smCE(zls, (o.Uni((o.1))))
E
sup [EF t=1
yi f(p)) (x+ pt)
Completeness and soundness. as complete (intuitively "accurate" predictions have a small penalty) and sound (intuitively "inaccurate" predictions have a large penalty).
We give minimal conditions for a calibration measure to be regarded

---

Definition 2.2 (Completeness and soundness). A calibration measure CM is complete if: (1) For any z E {0, 1)", CMr x) = 0; (2) For any a E [0, 11, Bo
CMr(x, a Ir) = (T). The calibration measure is sound if: (1) For any E {0, 132, CMr(z. IT x)) =Q(T); (2) For any 3 E [0, 1] such that a + 3. -r....rr-BBmuulll
CMr 8 Ir) = (T). Here, 0.()) and (., may hide constant factors that depend on the parameters in the subscript.
Truthfulness. To define the truthfulness of calibration measure, we introduce the truthful fore- caster and the optimal error for distribution D.
Definition 2.3 (Truthful forecaster). With respect distribution D A((0, the truthful
forecaster is defined (D) (D),b,,,.......b..... PraND Et F1((t-1) -b.(t-1)-
Arguably, A (D) is the only forecaster that makes the "right" predictions on distribution 'D. Definition 2.4 (Optimal error). The optimal ervor on distribution D A({ 13") with respect to calibration measure CM is defined as OPTcM = inf errem (a, where A ranges over all deterministic foremmitsttticrrreeatee
Note that by an averaging argument, the definition of OPTcM (D) is unchanged if we take an infimum over randomized forecasters.
calibration measure is truthful if, on every distribution, the truthful forecaster near-optimal.
Definition 2.5 (Truthfulness of calibration measures). A calibration measure CM is (a, 3)-truthful
if. for every D E A({O, 1)7). errc A ( (D)) I a OPTcM (D) + B. Conversely, CM is said to have a-3 truthfulness gap if. for some distribution D, OPTcM and errcm (D, Atruthful (D)) 2 8.
3 Technical Overview
In this section, we briefly discuss the main technical ideas and challenges behind the proofs of Theo-
rems 1.1 1.2 and I.3] We provide more details
main result, i.e., that SSCE is (O(1), --tttulffll, in Sections 4 through [ Theorem 1.3 follows from a recent result of [ACRS24] on minimizing
the distance from calibration in the adversarial setup, along with new result connecting SSCE to distance from calibration, and is proved in Section 7
We defer the proof of Theorem T.1 to
Appendix
B
A simple distribution that witnesses truthfulness gaps. Inspired by [QV21 Example 2]. we consider the distribution D specified as follows: The time horizon is divided into T/3 blocks of length 3, each with a uniformly random bit, followed by a zero and one. Within each block, the truthful forecaster predicts 1/2, 0 and 1 in order. Then, among the steps on which 1/2 is predicted, the frequency of ones typically 1/2 + (1/VV). This deviation results in a ((V)) penalty under most calibration measures (concretely, all calibration measures in the first
of Table
there is a different strategy that ensures perfect calibration, and thus a zero penalty under most calibration measures. Within each block, the forecaster predicts 1/2 the first step. If the bit turns out to be 1, the forecaster maintains perfect calibration by predicting 1/2 on the second step, on which the outcome is known be O: otherwise, the forecaster accomplishes the same by predicting 1/2 the third step. Therefore, the distribution D witnesses 0-Q(VT)) truthfulness gap for every calibration measure in the first two rows of Table
However,
The importance of subsampling in the SSCE becomes apparent in light of the example above. On distribution D, the truthful forecaster has to pay a ((VT) cost for the mild deviation from the expectation, while strategic forecaster avoids this deviation by correlating the predictions with the biases in the past. With the subsampling, however, the forecaster is no longer sure about the biases that factor into the penalty. This ensures that, compared to truth-telling, the benefit from predicting strategically is marginal, and thus makes the truthfulness guarantee in Theorem 1.2 possible.
5

---

Establishing truthfulness via martingale inequalities. We prove that the SSCE is (0(1), 0)- truthful in three steps: (1) Define complexity measure (D) of distribution D; (2) Show that errssce (2, Atruhfuul (D)) (D)): (3) Show that (P)) = ()(r(D)).
As we elaborate in Section 5 the crux of Step (2) is to control the expected deviation a martingale (M))sEsT with respect to filtration (Fe) by the its realized variance Var, == Ex=1 Var [Mg [Bs-1]. which is highly non-trivial as the two processes (Me) and (Varz) correlated. In more detail, the filtration (F₂) corresponds to the randomness in x ~ D. while (M,) tracks the biases in the predictions (on subset of the time horizon) tested by Lipschitz function. We note that such bound would easily follow from "off-the-shelf" concentration inequalities for martingales (e.g.. Freedman'ss inequality (Fre75)), if the total realized variance Varr were uniformly bounded. However, in general, Varr may vary drastically, and directly applying these concentration inequalities would introduce an extra super-constant factor. Our workaround is "doubling trick" that divides the time horizon into epochs, the realized variances in which grow exponentially. We then apply Freedman's 's inequality to each epoch separately. In Section 5] formulate toy random walk problem that highlights this challenge and demonstrates our solution to it, which is of independent interest.
Similarly, we show in Section 6 the crux of Step (3) is to establish another martingale inequality. We first show that for fixed x and P. we have SSCE(2: (x,p) = ((VNT), where N₂ = Ei=1 1 [|x, psl 2 1/2]. Furthermore, over the randomness in x ~ D. the realized variance process (Var,) defined above is shown to lower bound (N₂), i.e., (N₂ - Var,) is a sub-martingale.
However, the desired result requires the lower bound TE [VNT] 2(1) E [v [Varr]. which does
not follow from IE' [NT Varr] 2 0 in general. This challenge necessitates more careful analysis tailored to the specific properties of the processes (N,) and (Var.).
Deterministic forecasting strategy via reduction to smCE. We build on the result of [ACRS24] showing the existence of deterministic forecasting strategy guaranteeing an O(VT) bound on smCE. In particular, we show via a standard chaining argument that SSCE upper bounded by smCE plus variance term that can be upper bounded by OvvT). The result of [ACRS24) then implies a deterministic forecasting algorithm achieving an (VT)) SSCE.
Warmup: The Product Distribution Case
As warmup, in this section, start by showing that SSCE is (0(1), O(log -ruutulllll for product distributions. This is a weaker version of Theorem T.2 in terms both the truthfulness parameters 5 and 6
of SSCE and the restriction product distributions. In Sections remove these restrictions and improve the analysis truthfulness.
we outline how will
For distribution D I Bernoulli(p)). take 2² VaraND
EI p p;) as complexity measure of the distribution of outcomes. We will show that errssce (D, Atruthfull (D)) ((a + log T) and ssTSE = [o)) - O(1).
ΣL Z4 =
4.1 Upper Bound the SSCE of the Truthful Forecaster
We first show that the truthful forecaster for D, which predicts pt pt at every step f, gives EgED (SSCE( p))) O(a + log T). For this purpose, suffices to prove
E |smCE(x, D~D
O(a + log
since for each fixed S S [T]. applying (I) to ælss and p*1s gives EnED |smCE(Ø)sss psls)] < (a + log 7), and taking an expectation over Unif(2!TT) gives the desired bound on SSCE.
Recall that E. |smCE(xr px),)) = E suP Eh, f(+) (xz -rt) If we replace F with the family of constant functions from 10 to [-1, 11. the right-hand side would reduce to
p²)
T
E
Σ
p3)
5
E
Σ We pi)
Var IND
Σ
D>D

---

Therefore, to prove the upper bound in I we need to show that the family of one one-dimensional Lipschitz functions is not significantly richer than constant functions.
At a high level, this is done by taking finite coverings of Lipschitz functions and using Dudley's chaining technique [Dud87] to upper bound the value of this stochastic process. In more detail, let Fo be the smallest ô-covering of F in the uniform norm, i.e., for each f F, there exists fo E Fo fallæ I 6. It well-known that Fo = e0(1/8) and a chaining argument gives
such that |lf
T
Ollog T)
T Σ s(tt)) (0z pt)
sup Σ FEF 1=1
(oz - ppi) 11+ s(Pt)
Σ
E
max 9E9 1=1
(2)
RND
where G8 = [fo -ff-ffffo fa/2 : fo E Fs, f8/2 E F6/2, llfo f8/21loo S 38/2].
remains to bound the second term of 2 Note that for a fixed because of the independence of IAS, g(p)) (Iz p?) is independent across t [7]. Therefore, we can control the tail probability
of Em=g(pt)
g(pt) - (2'e- - pt) by Bernstein inequalities. For each fixed 8, using a Bernstein tail bound, taking a union bound over g E Go. and noting that |G&l s [Ja
F/5/2 = E 0(108), we have
T
((t) (ore - pp)) < 0(6) o ( (Vo² log Gas + log |95) = 0 1).
E
max
awD
gEgs
Plugging this into 2 proves and thus the desired bound Ex~D [SSCE(2, O(o + log T)..
4.2 Lower Bound the Optimal SSCE
Next, we lower bound OPT (D) by showing that every forecasting strategy must incur an (()
SSCE on D. Recall that SSCE(x, x. p) is given by
T
sup Σ y/ f(p)) (xe - pt) SEF t=1
E U~Uni(((o.1)T)
Σ 1=1
U/ (xt - pr)
where we use the fact that F contains the constant functions and -1
Fix 10,1)T, 1 and let N ET= 1 [|z, - pel 2 1/2]. Over the randomness in y ~ (n0, 133),, the quantity ΣT= He Me-(xx-p.). by the central limit theorem, approximately dis-
tributed as normal distribution with variance Dim 1 1 (z+ pp:) 2 ΣT 16 [ 2 1/2]
Q(N), so its expected absolute value is ((VN).
Now it remains to lower bound the expectation of VN induced by an arbitrary forecaster. Condition- ing on 21:[t-1), 2x always follows Bernoulli(p)). ). Thus, regardless of the choice of Pt E [0, 1], the condition ju+, - pel 2 1/2 holds with probability at least min , 1 -rt} 2 pē (1 pF)) Then, over the T steps, we expect that N 2 - (1 - p))) 2(0²) holds with probability (2(1), )), as long as = ((1). This gives the desired lower bound E [SSCE(,, R E VN 2(()) O()).
Upper Bound the SSCE of the Truthful Forecaster
To extend the proof strategy sketched in Section to non-product distributions, the first chal- lenge is to define an appropriate complexity measure of general distribution D. Consider the stochastic process (VartJosesT defined as Var, = E'=1 P1 - pt), where x and
pf R.DDD | -'1-0-1) = 11:(t-1) now a random variable that denotes the conditional expecta-
tion of F after observing #1:(t-1)- The "right" definition turns out to be roughly (D) == E [Var]] In this section, we prove the following weaker upper bound the SSCE incurred by the truthful forecaster. We provide a stronger bound (Theorem C.I in Appendix C
Theorem 5.1. For any D E A((),))T), errssce (D, Auuthful (D) = (E Varr + log T)-
Proof sketch. We begin by repeating the chaining argument in Section 4 Recall that, for any 6 > 0.
there is a a d-covering Fs of F in the oc-nrm that has size e 0(1/5), Letting TT TT)()) denote the mapping
7

---

of function f onto the covering Fo such that |f - =o( S 6, we can write for any M E Z+:
SSCE(I, 2--M T
E ymUnif((o,1)"))
Σ FEF
sup
yt (T2 (f)(pi) T2 (f)(pt)) (xx Pc)
=:
To control the expectation of each Wi. we note that the set 9 = - (f) T21
is
of size at most [ - Furthermore, every function E Gb. satisfies
llgllcc 1| (f) 12)=+(()lle I (f) flloo + Ilf т2i (f)l = 0(2-*)
for some f F. We apply the following technical lemma, which we prove in Appendix C
Lemma 5.2. Given function f [0 - [-,,]] and E {0, 13, consider the martingale
Mc(f. v) Σ s=1 V/+ f(z))- (Ix- -?) where x~ D. Then, for any finite family G of functions
from [0, 1| to - and any {0, 1), have
E RPD
max M1 (f. FEG
s 0 Iog |9] log + Vlog
E
[Vaar]) )
END
Applying Lemma 5.2 to each GR scaled up by a O(2*) factor and noting that log Gul S log F2 12g
k| = 0(2²) gives
M
errssce (D,CE((D,C A (D)) 52 T
0
(2 (o:t))0(220
log + 2
E aND
Varr
k=0
22-M M, T
0 (og T 2 E
[Vaarr
znD
< T +
M log T' +
Varr]
2nD
Choosing M (llogT) proves the theorem.
We remark that the proof of Lemma 5.2 is highly non-trivial. As mentioned in Section such an upper bound would follow from Freedman's inequality, if Varr were always bounded by (B [ (arr)) ))) However, general, applying Freedman's 's inequality to each My 3) nec- essarily requires additional union bound over possible values of Varr, and introduces super- constant multiplicative factor.
The challenge in dealing with the randomness in Varr is captured by the following toy problem:
Random walk with early stopping: Let (Xt)osser be the random walk such that X, 0 and each X, X,-1 independently follows Unif {+1)). Let be arbitrary stopping time with respect to (Xt). Prove that E [ < (1))E[(T)
Indeed, the above corresponds to a special case of Lemma 5.2 which: (1) the sequence p* starts with entry 1/2, and may switch to entry 0 at any point, depending on the realization of 2,5; (2) the family 9 consists of two constant functions and
One might be tempted to prove E [|x+I]| < O(1) E [vF] by first proving E for all t E [T], and then applying the law of total expectation. Such an approach is doomed to fail, because the stopping time might significantly bias the conditional expectation of X-| on some event 5 = tg. e.g., by stopping at time to only if X > /hg-
O(vi)
Our workaround is inspired by the standard doubling trick in online learning. We break the time horizon into epocks of geometrically increasing lengths: the k-th epoch contains 2* steps. We break XX, into the displacements accumulated in different epochs; their sum clearly upper bounds [x]]-

---

Furthermore, we can show that, conditioning reaching epoch k, the displacement within the epoch is (2)2). This allows us to establish the desired inequality via
Oloo T'
E [[xx|]=000
Σ
Pr [T reaches epoch kij V2 S ((1) [VV]]
To prove Lemma 5.2 we extend this technique to a general martingale MT y) by dividing the time horizon into epochs according to the doubling of Var,, and then applying Freedman's inequality to each epoch.
Towards a stronger upper bound. our actual proof, we use a slightly different complexity measure o,, (D) = IE (Varr))] where 7xx) = if < 1 and 7xx) = v otherwise. Roughly speaking, this definition accounts for the fact that sum independent Bernoulli random variables behaves quite differently when its mean is close to To remove the extra log" - term in Theorem 5.1 our actual proof also uses a variant of Lemma 5.2 Lemma C which involves more careful application of Freedman's 's incquality tailored to specific coverings of Lipschitz functions.
Lower Bound the Optimal SSCE
In this section, we outline weaker lower bound on the optimal SSCE achievable distribution. Theorem 6.1. For any D A((0, SPT (D) Q(E (VVar)) O(1).
Similar to the product distribution case (Section 4) the key quantity in the proof the stochastic
process (No)ogtgr defined as N₂ == E n, and ne == [|x - pal 2 1/2). This is formalized by the following lemma, which applies to any realization of x, p, and Nr Ei= 1 || pel 1/2]:
Lemma 6.2. For any x E {0, T and p E 1J we have SSCE(r, p) 2 (VNT).
remains to lower bound the quantity E [VNz] induced by an arbitrary forecaster. As argued earlier, conditioning on (1:(t-1)> we always have Pr [n, = 1] 2 pt (1 (1-pi) = Var, - Var, where sub-martingale, which implies
Pž and Var, are defined as in Section Thus, (N, Var,)
[NT] 2 E [Varr]. However, this does imply that E [NN] 2 ?(E [ <Varr) ). fact, such an inequality does not hold in general: When pi = and pt = for 2 2, [VNT] could be Oc)), yet E [VVary] = ((VE) > O(e).
The following technical lemma circumvents this counterexample by subtracting constant term from the right-hand side:
Lemma 6.3. The stochastic process (Ne)uetr satisfies E [/N QQ(E [vVarr] 0(1).
Note that Theorem 6.1 directly follows from Lemmas 6.2 and 6.3 which we prove in Appendix D.I
To avoid the extra 1(() term in the lower bound, our actual proof (deferred to Appendix D.3 works
with the slightly different complexity measure a, (D) == E (v(rr) defined in Section 5
7 Forecasting with O(VT) SSCE
In this section, we prove Theorem 1.3 which states the existence of a deterministic forecaster that incurs an O(VT) SSCE against all adaptive adversaries. Recall the definition the smooth calibration error (smCE) from Section 2 Using standard chaining arguments, show the following relation between SSCE and smCE, whose proof we defer to Appendix
Lemma 7.1. For any x E {0, 1)T and p E [0,
1 SSCE(#,,)) < SMCE(I,,)) O(VT),
where the O(-) notation hides universal constant that does not depend on x or p.
Theorem 1.3 follows from the lemma above and recent result of [ACR244]

---

Proof of Theorem 1.3 It was shown by ACRS24 that there exists a deterministic forecaster with an TT)T) distance from calibration (CalDist(r, (z, p)) against every adaptive adversary in the adversarial sequential calibration setup. Lemma 7.1 together with the inequality smCC(( p) I CalDist(x, from [BGHN23] Lemma 5.4 and Theorem 7.3] implies that
SSCE(æ,, p) I CalDist(z,)) O(VT),
so the same forecaster incurs an SSCE of ((VT) as well.
8 Discussion
We formulate three natural desiderata of calibration measures that evaluate the quality of probabilistic forecasts: truthfulness, completeness, and soundness. They serve as minimal requirements for an error metric to be considered as measuring calibration and not to create a significant incentive for forecasters to predict untruthfully. While existing calibration measures fail to simultaneously meet all these criteria, we propose the new calibration measure (SSCE) that is shown be approximately truthful via non-trivial analysis. In the following, we discuss two natural directions of future work.
Inherent trade-offs among different desiderata? As shown in Table the SSCE and the error metrics induced by proper scoring rules give trade-off between truthfulness and completeness: The former is complete and approximately truthful, while the latter perfectly truthful but not complete. Is there calibration measure that achieves the best of both worlds? Taking step back, while definition of truthfulness seems natural, the completeness and soundness criteria, as defined, only serve minimal requirements. It still remains explore ways to formally quantify the latter two, and investigate the inherent quantitative trade-offs among truthfulness, completeness and soundness.
Truthfulness against adaptive adversaries? One may wonder whether the truthfulness guarantee of SSCE can be extended to handle adaptive adversaries as well. Assuming that the forecaster is given an adversary's 's (randomized) strategy for choosing 2; based T1:(1-1) and P1:(t-1). is it still approximately optimal to always predict the conditional probability? Here, "adaptive" emphasizes that 24 may depend on both (i:(t-1) and Pı:(t-1); the formulation in Section 2 is equivalent that Ie only depends on 2 Z1:(t-1)-
Unfortunately, as we show in Appendix G such guarantee does not hold for SSCE, and is unlikely to hold for any natural calibration measure: An adversary can "force" the forecaster to predict untruthfully by "threatening" to increase the variance of the subsequent bits. However, this adversary is highly contrived and unrealistic for practical scenarios. We may thus identify reasonable restrictions on the adaptive adversary to sidestep this counterexample.
9
Acknowledgements
This work is supported in part by the National Science Foundation under grants CCF-2145899 and the Graduate Research Fellowship Program under grant DGE 2146752, the Office of Naval Research under grant NO00 100014-24-1-2159, an Alfred P. Sloan fellowship. a Schmidt Sciences A12050 fellowship, and Google Research Scholars award. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies.
10

---

References
[ACRS24] Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi. An elementary predictor obtaining 2vT distance to calibration. arXiv preprint arXiv:2402. 1410,, 2024.
[BF+02] Henri Berestycki, Igor Florent, et al. Asymptotics and calibration of local volatility models. Quantitative finance, 2(1):61, 2002.
[BGHN23] Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Symposium Theory of Computing (STOC), pages 1727-1740, 2023.
[Bla23] Guy Blanc. Subsampling suffices for adaptive data analysis. In Symposium on Theory of Computing (STOC), pages 999-1012, 2023.
[BLMT22] Guy Blanc, Jane Lange, Ali Malik, and Li- Ling Tan. On the power of adaptivity in statistical adversaries. In Conference Learning Theory (COLT), pages 5030-5061, 2022.
[Bri50] Glenn W. Brier. Verification of forecasts expressed in terms of probability, Monthly Weather Review, 78(1):1-3, 1950.
[CAT16] Cynthia S Crowson, Elizabeth Atkinson, and Terry M Themnau, Assessing calibration of prognostic risk scores. Statistical methods in medical research, 2524):1692-1706 2016.
[CY21] Yiling Chen and Fang-Yi Yi Yu. Optimal scoring rule design. MXXv:2107.074222 2021.
arXiv preprint
[Daw82] A. P. Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):0056610 1982.
[Dww85] A. P. Dawid. Calibration- empirical probability. The Annals of Statistics, 13(4:11251 1985.
[DF83] Morris H DeGroot and Stephen Fienberg. The comparison and evaluation of forecast- ers. Journal of the Royal Statistical Society: Series D (The Statistician), 32(1-2):12-22, 1983.
[ud87] R. M. Dudley. Universal donsker classes and metric entropy. The Annals of Probability, (5(4):1306-133) 1987.
[FH18] Dean P. Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-293, 2018.
[FH21] Dean P. Foster and Sergiu Hart. Forecast hedging and calibration. Journal of Political Economy, 129(12):344734400 2021.
[FL99] Drew Fudenberg and David K. Levine. An easier way to calibrate. Economic Behavior, 29 133111333 1999.
Games and
[Fos99] Dean P. Foster. A proof of calibration via blackwell's approachability theorem. Games and Economic Behavior, 29(1-2):3377, 1999.
[Fre75] David Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1 3(1):100-118, 1975.
[FRST11] Dean P. Foster, Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Complexity- based approach to calibration with checking rules. In Conference on Learning Theory (COLT), pages 293-314, 2011.
[FV97] Dean Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40-55, 1997.

---

[FV98] Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379- 390, 1998.
[GPSWI7] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning (ICML), pages 1321-1330, 2017.
[Har22] Sergiu Hart. Calibrated forecasts: The minimax proof. arXiv:2209.05800 2022.
arXiv preprint
[H]KRRI8] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multical- ibration: Calibration for the commutationally-dnntiibbb masses. In International Conference on Machine Learning (ICML), pages 1939-1948, 2018.
[HJ723] Nika Haghtalab, Michael Jordan, and Eric Zhao. unifying perspective on multi- calibration: Game dynamics for multi-objective learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 72464-72506, 2023.
[HPY23] Nika Haghtalab, Chara Podimata, and Kunhe Yang. Calibrated Stackelberg games: Learning optimal commitments against calibrated agents. In Advances in Neural Information Processing Systems (NeurIPS), pages 61645-61677, 2023.
[HSLW23] Jason D. Hartline, Liren Shan, Yingkai Li, and Yifan Wu. Optimal scoring rules for nulti-dimensional effort. In Conference on Learning Theory (COLT), pages 2023.
[HW24] Lunjia Hu and Yifan Wu. Predict minimize swap regret for all payoff-bounded tasks. arXiv preprint arXiv:2404. 13503, 2024.
[JOKOM22] Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila Ohno-Machado. Calibrating predictive model estimates support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263 222244 2012.
[KF08] Sham M. Kakade and Dean P. Foster. Deterministic calibration and Nash equilibrium. Journal of Computer and System Sciences, 74(1):115-130, 2008.
[KLST23] Robert Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. U-calibration: Forecasting for an unknown agent. In Conference on Learning Theory (COLT), pages 5143-5145, 2023.
[KMR17] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Innovations in Theoretical Computer Science (ITCS), pages 43:1-43:23, 2017.
[KSB21] Benjamin Kompa, Jasper Snoek, and Andrew L Beam. Second opinion needed: communicating uncertainty in medical machine learning. NPJ Digital Medicine, 4(1):4, 2021.
[KSJ18] Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kernel mean embeddings. In International Conference on Machine Learning (ICML), pages 2805-2814, 2018.
[LHSW22] Yingkai Li, Jason D. Hartline, Liren Shan, and Yifan Wu. Optimization of scoring 2022.
rules. In Economics and Computation (EC), pages
[MW84] Allan H Murphy and Robert Winkler. Probability forecasting in meteorology. Journal of the American Statistical Association, 79(387):489-500 1984.
[NNW21] Eric Neyman, Georgy Noarov, and Matthew Weinberg. Binary scoring rules that incentivize precision. In Economics and Computation (EC), pages 718-733, 2021.
[NRRX23] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional unbiased prediction for sequential decision making. In OPT 2023: Optimization for Machine Learning, 2023.
12

---

[PRW 17] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q. Weinberger. On fairness and calibration. Advances in Neural Information Processing Systems (NIPS), pages 5680-5689. 2017.
[PW22] Maneesha Papireddygari and Bo Waggoner. Contracts with information acquisition, via scoring rules. In Economics and Computation (EC), pages 703-704, 2022.
[QV21] Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Symposium on Theory of Computing (STOC), pages 456-466, 2021.
[QZ24] Mingda Qiao and Letian Zheng. On the distance from calibration in sequential predic- tion. In Conference on Learning Theory (COLT), pages 4307-4357, 2024.
[RS24] Aaron Roth and Mirah Shi. Forecasting for swap regret for all downstream agents. arXiv preprint arXiv:2402.08753 2024.
[S] I. G. Shevtsova. An improvement of convergence rate estimates in the Lyapunov theorem. Doklady Mathematics, 82(3):862 864, 2010.
[Ste22] Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:22 20002200.00977 2022.
[VCVI5] Ben Van Calster and Andrew J Vickers. Calibration of risk prediction models: impact on decision-analytie performance. Medical decision making, 35(2):162-169, 2015.
[WM68] Robert Winkler and Allan H. Murphy. "Good" probability assessors. Journal of Applied Meteorology and Climatology, 7(5)7551-758, 1968.
13

---

Calibration Measure
Complete?
Sound?
Truthful?
Expected Calibration Error
0-Ω((T' gap
Maximum Swap Regret
0-2(TT) gap
Smooth Calibration Error
0-R(vT) gap
Distance from Calibration
0-2(vV) gap
Interval Calibration Error
/
/
0-2(vV) gap
Laplace-Kens Kernel Calibration Error
0-2(vT) gap
U-Calibration Error
d
0(1)-R(VT) gap
Proper Scoring Rules
(1,0)-truthful
smCE + VT
v
(O(1), 0)-truthllll
Subsampled Smooth Calibration Error
(O(1), 0)-truthuul
Table 2: Evaluation of previous calibration measures along with SSCE, in terms of completeness, soundness and truthfulness (Definitions 2.2 and 2.5 Every calibration measure, except SSCE, either lacks completeness or has a significant truthfulness gap.
A Taxonomy of Existing Calibration Measures
In this section, prove that the existing calibration measures in Table 2 either have large truthfulness gap or lack completeness.
In these proofs, the biases induced by specific outcomes and predictions will be frequently used: With respect to outcomes x E {0, 1)a and predictions p E [0, 1)", the bias associated with value [0, 1] is defined as
A
(os pe) pp: a)
A.1 Existing Calibration Measures
The expected calibration error. A common calibration measure is the sum of L1 errors of each level set, known as the L1 calibration error or the Expected Calibration Error (ECE); On {0, 1)" and [0, 1)"", the expected calibration eтrоr is defined as
ECE(2,p)
Σ 0.
Σ c pc) 1pp at)
Σ Aal
ac(0.1]
Note that the summand A,, is non-zero only if a (p,,p2,.... ...p.....p................ ,r.....,,,,,,,, pr). so the summations above essentially finite and well-defined.
The smooth calibration error.
The smooth calibration error KF08 is defined
T Σ f(:)) (x+ - Pc) =sup fEF ae [0.1)
smCE(x,p) = suu fEF
Σ f(a)
Ans
where is the family of 1-Lipschitz functions from [0, 1] to [-1, 1). Again, since A, * holds only if {pi, (pi.p2..... .Pr), }. the summation above is finite and well-defined.
14

---

The distance from calibration. The distance from calibration, introduced by BGH and extended to the sequential setup by [Z244. defined as:
CalDist(a,p))
min |lp 4/11. (EC(a)
where
T C(x) = pe [0, Va E [0, 1]. > (xL- pr) 1/p = a] = =0]
the set of predictions that are perfectly calibrated for x.
Interval calibration. The interval calibration error of [BGHN23 relaxes the ECE to binned version while penalizing the use long intervals. Formally, an interval partition I is finite collection of intervals {11, ..,... } that form partition of [0, 1]. The interval calibration error is defined
as:
T
I
intCE(x,p) == inf
(xt p.) 1 pe E L.] Σ
ΣD t=
len(4:)
Ipc E 4.]
where the infimum is over all interval partitions I, and len(1) denotes the length of interval I. Note that the first summation inside the infimum is analogous to the ECE, except that the biases associated with all values within the same interval added together. The second summation gives the total lengths of the intervals into which the 7 predictions fall.
Laplace-kernel calibration. The suplace-kerned calibration error [BGHN23] is special case of the maximum mean calibration error introduced by [KSJ18). It can be viewed as a variant of the smooth calibration error, in which the family F of Lipschitz functions replaced by
Ff R: 11 1
where ||
||2 denotes the f2 norm of functions, and S' is the derivative of f. Namely,
kCE (CEL:P(x,p))))))))))))))))))>)) = sup Σ f(p)) (x. pc). fEF
U-calibration.
The definition of the U-calibration enror [LLT223 is based proper scoring
rules. A (bounded) scoring rule is a function S: :00,1) x [0, 1] [-1,1]. A scoring rule is proper if it holds for every a E [0, 1] that
E arg min [E((0.] 2nd Bernoulli(())
E
[S(x,8))
In other words. when the outcome æ is drawn from follow Bernoulli(a), predicting the true parameter minimizes the expected loss. The U-calibration error is then defined as
T
T
UCal(x, p) = sup
Σ
S(I,, Pc) - inf
Σ a(x) aE(0.1]
where the supremum over all proper scoring rules. Note that for each fixed S, the expression inside the supremum is exactly the external regret of the forecaster, i.c., the excess loss compared to the best fixed prediction hindsight.
Maximum swap regret. A recent line of work [NRRX23 RS24 HW24 considers strengthen- ing of U-calibration, in which the external regret is replaced with the swap regret. In particular, HH244 showed that the resulting calibration measure, termed the Maximum Swap Regret (MSR), is polynomially related to the ECE after scaling by factor of 1/T:
ECE p)
MSR(I, p)
2ECE p).))
T
15

---

A.2 (-Q(T) Truthfulness Gaps
We first prove the (T))(T) truthfulness gaps of the ECE and the MSR.
Proposition A.I. Both the expected calibration error and the maximum swap regret have 0-Q2(T)
truthfulness gap.
To establish Proposition A.I we follow a similar argument to the one in Section 3 We divide the time horizon into 3/3 triples, each containing a random bit followed by a zero and one. The truthful forecaster would predict the true probabilities for the T/3 random bits, which are designed to be close to 1 1/2 but distinct. This leads to a linear ECE. On the other hand, strategic forecaster may always predict 1/2 on the random bit. Then, based on the realization of the random bit, they use the subsequent deterministic bits to offset the bias. The resulting predictions are perfectly calibrated, and thus have a zero ECE. Finally, the relation between the ECE and the MSR gives the same truthfulness gap for the MSR.
Proof of Proposition Consider the distribution D defined as follows:
Let E2, ETyy be distinct values in [-1/4, chosen arbitrarily.
For each l E [T/3], set (Pix- 2: Pik- P(k) = (1/2 Ex, 0).
DD is the product distribution IT Bernoulli(p)).
By definition, the predictions made by the truthful forecaster are exactly given by p". Then, for each k E [2/3] and a = 1/2 + EN E [L/4,3/4], we have | = |2ax-2 al 2 1/4. This shows
errECE (D, (truthful (D)) 2 (T/3) (1/4) 9(T). By the inequality MSR(2,g) (CE(,.)) also have errMSR (D, Atuthfuul (D)) = ((T)..
On the other hand, consider the following alternative forecaster for D:
For each & E [T/3], predict Pst-2 1/2.
If 13k-2 Pak = 1.
0, predict P3a-1 0 and P3k 1/2; otherwise, predict p3k-1 1/2 and
Clearly, for each k [T]3], the steps E {3k 3k 1,333 have zero contribution Ao. A and 41/2. Therefore, this forecaster achieves a zero ECE on D. This proves OPTECE(() 0 and
establishes the 0-Ω((T) truthfulness gap for the ECE. Finally, the inequality MSR(g.g) < 2ECE(s..p)
T
implies that the same forecaster achieves zero MSR, which establishes OPT OPT 0 and the 0-Ω((T) truthfulness gap for the MSR.
A.3 (-R(VT) Truthfulness Gaps
Next, we prove the 0-Ω(vT) truthfulness gap for several calibration measures. The proof follows the argument outlined in Section 3
Proposition A.2. The smooth calibration error, the distance from calibration, the interval calibration error, and the Laplace-kernel calibration error all have a 0-92(V) truthfulness gap.
Proof. The truthfulness gaps of the four calibration measures are witnessed by the same product distribution D = II Bernoulli(p?), where (p5a-2: P5a) = (1/2, 0, 1) for every k E [T/3].
Truthful forecaster has S(VT) penalty. The truthful forecaster makes predictions that are identical to p². As a result, we have As = A = O. while A1/2 is distributed as the difference between sample from Binomial(T/3, 1/2) and its mean T/6. It then follows that |A1/2| > ((VTT)))))))) holds with probability 2(1). We will show that all four calibration measures evaluate to ((VT) in expectation.
16

---

For the smooth calibration error, we have
erramCE (D, Atruthfull (D))
E znD
[
E Xx-Binomaa((/3..112)
|| - T/611 =
For the distance from calibration, by [EGH233 Lemma 5.4 and Theorem 7.3], we have the inequality 2 smCEE p) I (a, p) for any z E {0, 1)" and p [0, 1]", so the truthful forecaster also gives errca (D, A truhhful (D)) ((VT).
For interval calibration, let Z be arbitrary interval partition, and 7 I be the interval that contains 1/2. If contains either 0 or 1, we must have (en(7) 2 1/2,, and the term Σ/= Σ len len(I:) 1 (p. E T.] will be at least 27/3 1/2 (((T). If does not contain 0 or 1, the summation Ex= (Ir- (ite-Pp) Pc) [Pe E 1] will be exactly A1/2- and the first term in the definition will be least |A1/2. I. It follows that intCE( p) 2 (VVT) with probability 2(1), so we have the lower bound (V(T).
erfincEE (DaicE(D,AA)) (truAtuuhhful
For Laplace-kernel calibration, let fo be an arbitrary function in F such that fo(1/2) > 0, e.g., can take fo(z) = ce -x² for a sufficiently small constant e > 0. Then, we have
kCE (ar,
Σ f(a) A. 2 2(11 141/2
sup SE(Jo. fo) aE|o,1]
It follows that efficE (D, A (D)) 2 2(1) [| ((VT).
Strategic forecaster has a zero penalty. Proposition A.I For each k [T/3].
Consider the same strategic forecaster as in the proof of
Predict P3k-2 = 1/2.
If 23k-2 = 0, predict (p38-1, = (0, 1/2); otherwise, predict (p3x-1,P3s) = (1/2, 1).
Clearly, this guarantees that A. = 0 holds for all [o. 1]. By definition, we have OPT (D) CaTcaIiitt (D) 0. It also easily follows that both intCE and kCE evaluate O. For intCE, we consider the interval partition I = {{0}, 1/2), [1/2), (1/2, (1}}} which witnesses intCE(x,,) 0. For kCE the summation Σ fpr) (I) - Pt) Eae(o.)) f(a) A. evaluates to 0 for all f F. This proves OPT (D) = OPTTKCEE
0.
A.4 0(1)-R(VT) Truthfulness Gap of U-Calibration
For the U-calibration error, we prove a slightly smaller truthfulness gap of O(I)-I(VT)) via more involved analysis.
Proposition A.3. The U-calibration error has an ((1)-R(VT) truthfulness gap.
Proof. We slightly different construction: the product distribution D I Bernoulli(pt) where p = 1/2 for < T/2 and pł = 1 for L T/2.
Truthful forecaster has an Qi (T) penalty. We first show that the truthful forecaster has an Q(VT) U-calibration error. Let random variable X x= x -
T/22 x; denote the number of ones among Consider the scoring rule
the first T/2 random bits. Note that X follows / defined as:
S(0, a) sgn(a 1/2) and a(1,a) sggn1122 a).
Note that S is proper, since for any [0, 1]. we have
E B>-Bemoulli
[S(z, 8)) (1 a) sg 1/2) + sennsgn - -) (1 2a) sgn(B 1/2),
which is always minimized at f
17

---

The total loss (w.Lt. S) incurred by the forecaster is then
T
(aa p.) = X (001))
= -
-
On the other hand, the total loss incurred by fixed prediction / E [0, 1] is given by:
Σ ((x, -) -
=T7/2+ X) sgn(1/2 + (7/2
2- - X) sgn(B - 1/2)
2X (sg((1112 (3.
By choosing 3 1, we can obtain total loss of -2X, Therefore, whenever X 2 T/4, we have
UCal(æ. 2 T/2 (-2X) 2(X-T/4)
When X < </44, we always have UCal((r, p) 2 0, since the trivial scoring rule S = 0 is proper. This shows that the truthful forecaster gives
erruca A truthful (D)) 2 x B--miinaaa(7/211/2
- T24), - Q(VT).
Strategic forecaster with an O(1) penalty. We consider an alternative forecaster A, which is
slightly more involved:
At every step S T/2, predict pt 5/88.
For t T/2 7/2 2,.... predict pt 5/8 until AAsal S 1 some time t. After that step. predict pt =
We first argue that the condition AAss I must hold at some point. Recall that TT22 st-
By Chernoff bound, X falls into (7/8,57/100 516 except with probability - Assuming this, we have As/s = X - (T/2) (5/8)= S 0 at time = T /2. Furthermore, if we hypothetically predict 5/8 for each of the last T/2 steps, we would have
A (X + T/2) T (5/8) > T/8 T/2 57/8 0
after all the T steps. Since As/8 changes by at most 1 at each step, we must hit the condition |A//8 S 1 at some point.
Therefore, except with an R(T) probability, we end up with As/s E [-1,1]. Furthermore, we predict at most two different values: 5/8 and 1. For every fixed proper scoring rule S {0. 1) x [0, + 1-1, 1]. we have
T
Σ S(I)p)) - inf Σ S(z,,
BE(U.1]
t=1
Σ S(z,, Pt) [p: a) inf
Σ S(z, B)
Ip: al
8E(0.1]
aE(5/8.1)
In the above, we divide the time horizon [T] into two parts, based whether 5/8 or is predicted.
The inequality holds since the rind side allows different values of 3 for different parts. Clearly, the term corresponding times the number of times is predicted, which evaluates to 0 by definition proper scoring rules.
has zero contribution, since reduces S(1, 1) inf inf 5(1,3)
The term corresponding to 5/8, on the other hand, is given by
No S(0, 5/8) + N1 S(1,5/8)) inf [No S(0, + N₁ -SL,
3E(0.1)
18

---

where each Ng denotes the number of steps on which 5/8 is predicted and the outcome is b E {0, 1]. By definition of proper scoring rules, the infimum is achieved by 3 No+N. and the above can be further simplified into
(No + N1) (S (8", (3"
where S(a, () == a S(L, + a) S(0, is the linear extension of S to 1]².
Let E(a) = S(a, a:) denote the uni-variate form of S. The following is standard fact about proper scoring rules (see e.g., [KLST23] Lemma and Corollary 2)).
Lemma A.. For any proper scoring rule S [0, 1J2 [-1, 1] and its uni variate form 8 [0, 1] +
[-1,1] 1]. it holds for all a, 8 E [0,1] that
+((a ((B) + (a= 3) (3)
* Ie"(a)) 2 for all a [0.
In partieular, we have
([(8"558) - S(5/ -8 -888 ((68)) s 2 - 5588
and
|S(5/8,5/8 5/8) 5(8", BB) (8(5/8) - {(3)) 2 - 55/8/
It follows that, assuming X E 51/66.
5 (No + -N1) = 4|A5/sl S 4.
UCal(x,p) S 4(No + N1) 8r -5/8 = 41
8
When X E [T/8, 57/16) does not hold (which happens with probability ) the U-calibration error is trivially upper bounded by O(T). It follows that
OPTuca errucal (Pr S <4+0 -4+0 0(1)
A.5 Lack of Completeness
Every scoring rule S : {0,1} x [0, + [0, 1] induces a calibration measure ( =
EL S(x, p.). When S is proper, it is easy to show that the resulting (S) is perfectly truthful,
i.e. (1,0)- trutthull
A drawback of such calibration measures is that they all lack completeness. Concretely, consider the squared loss S(x, = (x: pp)². When the outcomes 3 222 --. XT are independent and uniformly random bits, the "right" prediction Ps = 1/2 gives a total penalty of T/4, which is only a constant factor away from the maximum possible penalty of T'. This violates the completeness property in Definition 2.2] In contrast, as shown in Table almost all the other calibration measures would evaluate to < T' in this case. Such an asymptotic gap better justifies the intuition that pt 1/2 is much better prediction than, say, = 0.
More generally, unless the proper scoring rule S is trivial we may find (æo, po) {0, 1) (0. 1) such that S( Po) > O. Then, on a sequence of independent samples from Bernoulli(po). we have
E (emo
Pr (cM( (8) (z, Po i)] 2 T S(zo: X-~Bemoulli(fp))
[X = xn]
2 T S(xo Po) min (po, po] 9(T))
which violates the completeness condition in Definition 2.2
We also note that smCE(x. p) + vT gives calibration measure that is trivially truthful: Implicit in the proof of QQZ24, Theorem 3]. the truthful forecaster gives O(vT) smooth calibration error on every distribution D E A( 1)²), so it immediately gives a constant approximation of the optimal
'erre, we consider scoring rules with co-domain |0. 1]. since our definition of calibration measures (in Section requires them be bounded between 0 and 1' on length-T' sequences.
19

---

error, which is at least VT. However, this metric is not complete in the sense of Definition 2.2 since it evaluates to vT instead of () when (i.e., the predictions are binary and perfect). While SSCE also discourages the forecaster from "over-optimizing" the metric by introducing some additional noise, the subsampling procedure arguably more "organic" and better-justified than adding a vT term.
B Proof of Theorem 1.1
We prove Theorem 1.1 which we formally restate below.
Theorem B.1 (Formal version of Theorem 1.1). For every p¹ E [0,1]", on the product distribution
D II_ Bernoulli(pt). there is forecaster that achieves an O(log 3/2 T) smooth calibration
error and distance from calibration. Moreover, assuming that p* E [8, - 8) for fixed constant 6 E (0, 1/2), both sm)) and
(D) are D2 DIVTT).
B.1 The Upper Bound Part
We start by proving the upper bound part of Theorem B.I by designing a forecasting algorithm.
The forecasting algorithm. Our proof is based on an algorithm of [QZ24] that works for the special case that p = 1/2. Their algorithm starts by predicting 1/2 on the first T/2 steps. Depending on the realization of these T/2 random bits, it predicts slightly biased value for the next 7/2 steps, until the total bias (i.e., the partial sum of 4; Pt) becomes close to O at some point. If there is still time left, the algorithm repeats the above strategy for the remainder of the time horizon.
Roughly speaking, [QZ24) shows that a polylog(T) distance from calibration can be achieved by designing sub-routine with the following three properties:
Small bias: With high probability, the total bias is O(1) in magnitude at some time E [].
Proximity of predictions: During the sub-routine, the values being predicted lie short interval of length polylog(T)/
Sparsity of predictions: During the sub-routine, only ((1) different values are predicted.
To handle the general case that p' [0, 1]" is arbitrary, we design an alternative sub-routine, the behavior of which depends on whether the sequence p² is "sufficiently stationary" in some sense. Let [ffirtt == T/2 Σte Př and Psecond = T/2 I 2t=1/2+1 Př be the averages of the first and the second halves of the sequence, respectively. Let μ (Marst + Meecond) be the overall average.
Case |ptrat - ul > polylog(T)/vVT. When Mirst and μ are far away, we predict a piiatt every step. Without loss of generality, suppose that pfirst < p,, in which case we have
Pfrst < < 14,
where both inequalities hold with margin > (oolog(()//TT)) Then, with high probability the following two events happen: (1) The total bias negative at time T/2, i.e., holds that
ETI xa < a (T/2); (2) If we (hypothetically) predict the same value a for the second half, the bias will be positive in the end with high probability, i.e., ΣT He a T. Therefore, with high probability, the bias must be close to 0 at some point in T TJ. In this case, this sub-routine has all the desired properties.
Case 2: Mftret 14| < polylog(T)/ /TT. When Pfaet and μ are close, we use strategy
that is more similar to the algorithm of [QZ24). For the first half of the sequence, we predict a == Pfrst- Let Aira = Ei
a) denote the total bias at time T/2. Say that Airst 2 Then, we will predict / == Precoud Anee polylog(7)) in the second T/2
/T half of the sequence. The value of 3 is chosen such that we can offset the bias incurred in the first half (i.c., the A (T/2) term). We also introduce some additional bias (i.c.,
20

---

the polylog(T)/v3 term), so that we can return to zero bias with high probability. In this case, our sub-routine predicts different values (a and 8), and they only differ by polylog(T)/vT with high probability.
Formally, our algorithm is given in Algorithm II The actual algorithm is significantly more involved than the outline above. The complication due to the constraint that all predictions must lie [0, 1]. while our choice of /3 in Case 2 above might be invalid. We circumvent this issue by noting that B can be invalid only Mürst too close to either 0 or In that case, we will choose different value of a (i.e., the prediction for the first half), so that the sign of the bias at time T/2 is more predictable, and the resulting choice of will likely valid.
Algorithm I: Forecaster for Product Distributions
Input: Parameters Pi .2...... .P.. .P.....Pp.... Outcomes æ1, ,2....,,77 3r observed sequentially.
Output: Predictions Pt. PT.
t + 0; <- 0;
while ( < <T T do
r + 1; 1(T()) c- -
- 1; H(r) t- [T(r)/2]
if T()) = then predict pr 0 and break;
Piist H( Ex= p:: Heecoud + H|o 2
(r)
(r)
(+2H(()
alr) ( +Mseconal/2 Air) 0;
if (Piitt 11 / 2 then
HO
(1)) +- 1iintt + +1(r))/2
(r)
for i 1,2, (H(r) do
t t + Predict Pa + (r); Observe 24; (r) & A (r) + (xt - p.):
11
i (T) and A (r) S then break;
12
13
end
else
15
Piist I 11/2 then
16
if firtt 2 v
In Ho) then (r) < Marst
(r)
17
else (r) t- max Pfirst
2ilin In T(e) H(r)
0
18
else
19
if - -fist
Mirtt 2 10
(r)
T(T) H then (r)) Mist
else (r) +- min
(r) Pfrst +
211 211-1110 Inn 7(-)
20
M(0)
for ;= 1,2, 1,2,..., (+)) do
21
t Predict Pt + (r);
22
Observe 23; (r) + (r) + ( end
23
24
if A (r) 2 then g0r + min ((()
Mancond + +A(r)/H0
Tir
25
+
26
else
3(r) + max (r)
Peccond + A A (r))/)rr)
T(rr 2H
for i 1,2,.... (r) do
27
t t t+ Predict P. + G());
28
Observe x4; (r) + (r) (xt p.):
29
if (()) < then break;
30
end
end
21

---

The analysis. three steps:
We analyze Algorithm T and prove the upper bound in Theorem B.1 in the following
First, break the execution of Algorithm D jinto different rounds of the while-loop. and show that each round brings a polylog(T) smooth calibration error in expectation.
Then, using the simple observation that the smooth calibration error sub-additive, we obtain upper bound the overall smooth calibration error.
relation between smCE(x:, p) and CalDist(1; p) when p only contains few different values (shown by [QZ24) to translate the upper bound to one on the distance from calibration.
Finally,
The first step is the most technical. We fix r and condition on the value of t (equivalently, the value of (()) at the beginning of the r-th round. Note that the event = lo is solely determined by the realization of 21, 22,,42........ .........p.. Tta so conditioning on the value of t, the subsequent bits 2++1 through aT still distributed according D. Let sequences (+r) and (()) denote the outcomes and predictions made in the r-th round. Note that the two sequences are of the same length, though the length might vary.
We classify the rounds into three different types as follows:
Type 1: The condition Pfrrst
(r)
(
ll 1799
holds in the it-statement on Line 7
Type 2: Wiirtt
- -1(11) <
21n T(m) Hog and (r)) is set to / fert on either Line 16 or Line 19
Type 3: Pfrst
p())) <
T(r2 H(m
and (r) is not Pfrstt
Note that for fixed p", the type of a round is deterministic given r and T(r).
The three lemmas below give high-probabiliy, bounds on the smooth calibration error incurred during each round.
Lemma B.2, Conditioning on the value of Tf the r-th round is Type it holds with probability
1 1- ((1/T()) that
SmCE(x!)) ,p())))))))))))) 1.
Lemma B.3, Conditioning on the value of T(), if the r-th round is Type 2, it holds with probability
1 O01/0(110) that
smCE( (pr)) S 11+0 1 )
T(r)
(A() 1 fisst
+
log T(r)
T(r)
A
(r) fist
where A first denotes the value of A (r) at the end of the first for-loop (on Line 25
Lemma B.4, Conditioning on the value T(r),, the r-th round is Type holds with probability
1 ((1/T()) that
smCE( (1)) 51
( T(r)
1
(r) A
*
V1og
log T(r)
A
(r) first
T(r)
(Tr) where first denotes the value of (r) at the end of the first first for-loop (on Line 25
We first prove the upper bound part of Theorem B.1 Jsing the lemmas above.
Proof of Theorem B.I the upper bound part. By Lemmas
B.2 through B.4 regardless of the type of
the r-th round, it holds with probability 1 - 0 (1/T(r) that
+0 (v
log T(r) T(r)
!mCE(x!") .p()) 1
(r) first
A
(r) first
T()
22

---

where A (r)
first is regarded as 0 if the r-th round is Type 1. We say that the round if this upper bound smCE does not hold. Conditioning that T L, always have smCE(x p(r) s L,
since there are at most L steps the r-th round. Therefore, we have the inequality
( log L L.
smCE(x ,(()) $1+0)++++++00 (T.)
+0
(r)
+ L- [round r fails]
Best
first
We will upper bound the value of [smCE(x(1) p())] by taking an expectation over both sides of the above. Therefore, examine the expectation of I fiest! and first. conditioning 7
When the round is Type 1, there is nothing to upper bound. For Type rounds, A first is the difference between Xtrtt D 2is and its mean Ufirat H. Since the variance of Xtistt O(L), have Nest = OVLL) and E
(r)
(I).
first
Type 3 rounds are trickier. We assume that Pfirtt S 1/2; this is without loss of generality since the
Mirst > 1/2 case can be handled by completely symmetric argument. Then, A (r)
is the difference
first
between Xurst = Exet 2s and aH, and a may differ from Pfist by at most 2prna In This gives
H
(r) 12 first
= TE (Xfnst Mfrnt FF)*]] (Jiirst H aH)
E
I O(L + O( H In L).
Now we use the fact that when jfirrtt 1/2, the round Type only if prirtt < 100 implies
Tir) This
Op H in L) & O(VI log L),
which is dominated by the O(L) term. It then follows from Jensen's inequality that
E
first
S
E
first
O(VD).
Put everything together.
Therefore, we have the upper bound
(m) ,p()) [0//(t)=1
= L]
E
12 +0 ( log L (r)
(r) First
(()) = L + L. Pr round r fails ( L.]
S1+E
0
T.
fist
T.
1 + O OlVlog log L. 0(1/L) 0 O(ylog))
The second step applics our earlier conclusion that conditioning on T(r) = L. Taking another expectation over the randomness in T(r) shows that smCE(x(1)) (p(r)) = OVvlogT) T) for every r. Note that we have
O(VL) and E [ frrtt
O(L)
Rinst
T
smCE(x,p) p) = sup fEr
f fpt)) (xt Pt)
t=1
f( )- (x -p())
sup fEF
sup Σ
f(((") (a p(
JEF
Σ smC
23

---

Furthermore, there are at most (log T) rounds. It follows that E [smCE(x; p)] Ollog" 3/2 T).
Finally, note that in each round of the while-loop, the forecaster predicts most 2 different values (namely, (r) and g(r)). Therefore, the predictions P1, PP.....PT contain at most Olog T') different values. By [QZ24] Theorem 2], we conclude that
I [CalDist(z, - ((1) [smCE(z, (P,,P2,....
HD = (log T).
Now we prove Lemmas B.2 through B.4 In the proofs below, we frequently drop the superscript (r) since we only refer to the r-th round.
Proof of Lemma B.2 Recall that Type round is one in which the condition Mftee - μ4| 2
V T(m holds in the if-statement. We say that the round succeeds, if exit the for-loop
ing the "break" statement on Line 12 i.c., the condition > H and A holds at point (including in the last iteration where 2/)); otherwise, the round fails.
Note that only one value (namely, (r)) is predicted within the round. Thus, if the round succeeds, we have
smCE(111
(()) A
A (r)
remains control the probability for Type 1 round to fail. Consider random variables
H
Xfirst.
Σ
&s
and
X =
Σ xx-
amt+1
Note that both are sums of independent Bernoulli random variables, with E [Xfirt] E [X] = HpH. Also note that since a = (Mitstt + 12/2, we have
Pfirst Hl and
In T())
|Mirst al = 1p- al Mftest
-
2H1
Without loss of generality, suppose that (frrtt S μ. By an additive Chernoff bound, we have
Pr (Xirst/ HH a) & exp (-2H (a [ffiest) )²)
1
T(r)
and
Pr[X/(2H) S a) S exp (-4H (a 11²) T(r)'
Therefore, except with probability ((1/T(r) we have both Xtrt < aHl and X 2aH. other words, if the for-loop (hypothetically) runs all the 2H iterations, we would have (r) < at the end of the H-th iteration, and (rr) > 0 at the end of the 2H -H iteration. Since (r) changes by
|z, Prl < 1 within each iteration, there must be an iteration E (H H, .,..., 2H} at the end of which (+) falls into [0, 1]. By definition of Algorithm the r-th round succeeds.
we exit the for-loop at that time, and
Proof of Lemma B.3 Recall that in a Type 2 round, we have |Mrrst 14| <
2 In In'' and a Pfrst- Hf
Without loss of generality, suppose that Pärst 1/2; the case that Mftrett > 1/2 follows from completely symmetric argument. We say that Type 2 round succeeds if both conditions below are satisfied:
When chosen, the clipping (i.e., taking the minimum with or taking the maximum with 0) is not effective.
We exit the second for-loop through the break statement Line 30

---

Otherwise, the round fails.
Again, first upper bound the smooth calibration incurred within successful round, and then control the probability for a round to fail. Since only a and 3 are predicted in this round, we have
amCE(221) p
sup A. + f(3) Ap).
fEF
where Da and Ag are defined with respect to (r(2) and p(r) The above further given by suplf(8) (Aa + Ag) (a) f(8)) Ao]
seF
I suplf(3) (Aa + An) + sup [[((a) - f(3)) A.]
SEF
fEF
A.. + A + aa- 3 |
Note that 4.+ + As exactly the value of ( the end of the second for-loop, while A. is its value after the first for-loop, i..., A (r) and
first Then, assuming that the round succeeds, we have D Apl S 1
|a - 3 = Mftrst - $1 S Wfrrst
Hsecond
+
Msecoud - 3]
In T())
(r)
In T(r)
+
H
2H
log T'(r T(r)
0
(r) first
+0
T(r)
Plugging the above back into the upper bound on smCE ((())) round,
shows that in successful Type
(v log ((r) T(r)
smCE(x (()) 51+0
1 T(r)
(r) list
2
+0
14
(r) fistt
In the following, we show that a Type 2 round succeeds with probability 1 - 0(1/7()). Let Le=t+1 Ts. Note that Xtaa is sum of H independent Bernoulli random variables and E [X = Mirst H. Furthermore, we have A (r) bound, we have
Xutes Σ 1
first Xaest Minnt H. By additive Cheroof
In T())
In T(r
A S
Pr
Pr
X
Marst $
(3)
2H
T(*)
Recall that we need argue that no clipping applied when is chosen. We analyze the following two cases:
Case 1. A (r) first 2 0. In this case, we need to show that
A (r)
In T(r)
Usecond +
first
S1 1.
H
2H
Recall that we assumed jfrirtt S 1/2 and Pfrrst p
T
The latter further implies
H
Pfirst
Mssrond
= 2) (fiirst
11 < 8l
Thus, it suffices to prove that
8 T(r)
In (()
first
H
H
211 2
When
(A(r)
(r) first
la
T(t)
(i.e., the event in Equation
3 holds), the left-hand side above
is O Therefore, the probability that a clipping is applied is at most O(1TT(r)), where we absorb the constraint T()) 2 To into the hidden constant in O(.).
log Toe) T(m)
which is below 1/2 as long as (r)) exceeds some universal constant To.
25

---

Case 2. (r)
first 0. In this case, we need to show that
A
In T())
first
usecond
+
H
2H
Recall that the definition of Type 2 rounds implies Pfirtt prove that
10
T H
Thus, suffices to
In T())
2 T(r)
A
(r)
In T(r)
10
first
2 0.
H
H
H
2H
The above holds whenever the event in Equation happens, since 10 - 1/V2 1/v2 O.
2+2H Finally, we argue that, with high probability, we exit the second for-loop via the break statement.
Let Xsecond - 2i denote the total outcome in the second half. By symmetry, we only
deal with the case that A first 2 O, where we have 3 = Psecond + A (r)
first/ H +
In 2H
If the second
for-loop runs all the H iterations in full, at the end of it, the value of A (r) will be given by
H HIn
X second 3H = X second Msecond H
V
first
2
Note that the above is non-negative only if X second S Psecond H. V H which, by an additive Chernoff bound, holds with probability at most 1 1T)(), Therefore, with probability 1 - 1/7(), the value of A must fall into [-1,0] 0] during the second for-loop, and we will take the break statement accordingly.
Proof of Lemma B.4 Again, without loss of generality, suppose that fire S 1/2; the other case follows from completely symmetric argument. contrast to Type and Type rounds, we say that Type 3 round succeeds if all the following conditions hold simultaneously:
(r) first 0, i..., ( 0 holds at the end of the first for-loop (on Line 25
When 3 is chosen, the clipping (i.e., taking the minimum with 1) is not effective.
We exit the second for-loop through the break statement on Line 30
Otherwise, the round fails.
By the same argument as in the proof of Lemma
B.3 in successful Type round, we have
smCE(a(r), ((()) s 11+0
1
(r) i
12 + +
(
log T(r) T(r)
1 fist
(r)
T(r)
The only change in the argument is the upper bound on la B), since a is no longer equal to Hirnt Nevertheless, still have
aa B S lxx
Mfrrrt
Mirrtt
Msecondl
+
Msecond
3
2frrst In [(r)
Tnrr
2
(r) firat
In T(r)
+
+
H
H
H
2H
(v
logTo> T(r) (((r)
14
(r)
+
TTr
First
and the rest of the analysis goes through.
Thus, it remains to show that Type round succeods with probability - (11/(())) Let Xarst == E Zg. Note that Xaes is a sum of independent Bernoulli random variables and E [Xass]] = Miret H. By a multiplicative Chernoff bound, for any 6 2 O, we have
Pr [X < (1 Paraa
exp (-82para H/2)
26

---

V
((er)) Münn H
In particular, plugging
into the above gives
2ftrrstt In ((r)
1
Pr
Xfirst
H S jfrirtt
H
T
Recall that is chosen as the maximum between (firstt at least 1/T(r), we have Xttst/ H a, which is equivalent to A (r) 0 at the end of the first for-loop.
Pptrre In (r)
and 0. Thus, with probability
Then, we need to argue that when 3 is chosen, we have Msecond + / show the equivalent inequality:
2H S 1. We will
T(r)
(Hsccond - 1/22 + + /H
1/2.
2H
For the first term, note that since jr (Jifirst + Msocond /2, the assumption |Pfrrst - < v 2 T(e)
2
(V
implies |frrst
Msscond] = 0
log T(r) T
With the additional assumption that Pfirrt. S 1/2, we
have
(V
log T(r) T(r)
Psecond 1/2 < (fiirst 1/2) + |Paest - Msecond|
S O
For the second term, we note that, at the end of the first for-loop, A is given by
first -aH
(frrst
Pfirst
+ (fftiet a).
H
By an additive Chernoff bound, Xtaa
Mfrst S O
log T(r) T(m
holds with probabiilty 1-0(1/T()).
H
log T(r) T(r)
By our choice of a, jfrrst - a is always
Finally, the last term is clearly Therefore, as long as ((r) is larger than a universal constant To, the total
o
log
Plos
term is upper bounded by 1/2. Again, we can absorb the condition T 2 To into the big-O notation, so the second condition (that
log Ti Tim
clipped) is satisfied with probability
1 O(1/T(r))
Finally, we argue that we exit the second for-loop via the break statement with high probability. Let Xsecond := - # Is denote the total outcome in the second half. Recall that we have A > 0
the end the first for-loop, and that 3 (Aseoond + (r) /0)/H +
2H If the second for-loop
T()))
runs all the H iterations in full, the end of the value of (r) will be given by
(r) first + Xsecond 3H Xseoond Msecond H (m))
2
Note that the above is non negatieee only if Xgecoud S Psecoud H + Chernoff bound, holds with probability at most 1 (r) Therefore, with probability 1 - 1 (*), the value of A (r) must fall into [-1,0] 0) during the second for-loop, and we will take the break statement accordingly.
H la T(tr
which, by an additive
B.2
The Lower Bound Part
We prove the lower bound part of Theorem B.I via central limit theorem.
27

---

Proof of Theorem [.] the lower bound part. On the product distribution D the truthful forecaster predicts Pt Pi at every step t. Then, we have
(=1 (ernoulli(p)).
T
E |smCE(x,")) aND
=
sup LEF
f(t)) - (0t -pi)ppp) pī)
2 E IMD
Σ a pi)
IND
where we use the fact that F contains the constant functions f = and f = -1
Applying the Berry-Essead theorem [She10] to the random variable X == Σt (ae - pt) gives:
vr R, Pr|x < x-ool (zx) S Co To Po.
where (xx) CDF of the standard normal distribution, Co S 0.56 a universal constant, and
0g
E
[
pt)=
Σ pt -()) 2 VT8(1 8); 1=1
1=1
E
[1t - p77
pf - p?) ((pt)² + (1 -pt)
P0
max rE[T]
||x: - p[1-]
max (E(T]
p7(1-p7) ((p)
S 1.
In particular, taking -1 gives:
Pr X < -ool 2 (b-1) - 00
oo p = -(1)-
For all sufficiently large T, the O(I/vT) term dominated by the 211) term, which case we have
E Ism p²)] || 2 do Pr[X - onl ((VT).
Finally, by the inequality fsmC p) < CalDist(r, p) BGHN23 Lemma 5,4 and Theorem 7.3], the distance from calibration incurred by the truthful forecaster also ((VT).
C Supplemental Materials for Section 5
The following a tighter version Theorem 5.1
Theorem C.1. For any D E A((0,1)²), errssce (tuthfuu))))) O ([Varr))), where 1,
x, Vv, x 221. 1.
(x))
Proof. Given a function f [0. 1] + [-1, and binary vector y E {0,1)² 1)T we define the martingale M) = E.=1ve Vs f(pt) (Ix p.)) where ~ D and we use F, to denote the filtration
describing the randomness of Mr y) up to time and p. E [x F Note that, conditioned on F, I, is distributed as a Bernoulli with parameter p
We write the SSCE of truthful forecaster in terms of Mr v)
SSCE(2.p")= (-Unnf(HO.17T)
E
sup My (f.y)
feF
We now proceed via chaining and define the dyadic scale εy 21-k for A: = 0, 2, To cover the of Lipschitz functions F. we will use the sets of piecewise constant functions {Fa}azo described in Lemma C.2 For each function f E F, let (f) be close function in Fz, such that d(ʃ, mf)) < 28x- Observe that the covering Fe, is a singleton and that TT( always exists as Fe, is -oo-rivgi of F. Telescoping then gives
f(x) = (f(x) TM(((())) +
+o( -
[m())()) n: (())),
28

---

meaning that we have
T
SSCE(x,
sup
yr (f(rt) - TTM(() (ax - pt)
g)-Uni((001)))))
fEr
(Term A)
E
sup
To To(f)(t)) (xs Pī)
((Unii(((01))")
SEF 1=1
(Term B)
E
sup SEF
y1 (T(())( -.-1 (f)(()) (xx vi) (4)
you Unif(((.1))
(Term C)
MM to deterministically bound Term A by First, we can use that d(f(pt) TM TM (f)ptt) s 22-
E
sup FEF t=1
Σ
(f(p)) - =M((((())) (0x ps) 2
(O.
Second, observe that the image of (T( is singleton: [ F} 1: let this
unique function be denoted by fr. Then, Term reduces to _y-UUi(((0.117) (f y)). which
evaluates to after taking expectation over x ~ D, since for every y E (). (M&(f", ()) JoSiST forms a martingale. Third, we can observe that Tz(f) Tf- is function from (0, 1
{-22-(,0 0, 22-1) } that takes constant value along the segments [(j-1)2'- jj2-11) for j [2--1]. Thus, we can bound the summands of Term C by
E
sup SEF
D1 (T+(f)(P)) x(-1(f)(p7)) (xt pi)
g~Unni((o.11"")
2
T
E
sup
Σ t=1
y1 v v. (xt (p)) [22 S pt (j 1)2
(0.0
j=
2
<
Σ
21-1
E
sup
y/ v- (zr - -p)pp [j2 < (j 1)2
v~Uni((o,177))
=E(=1)
j=0
(:Mr("...kk)
Invoking Lemma C.9 with = {x + 1,-+ and I 1 have that for
all i [M]. E {0, 10..,..., 2'-1), and 10,13";
T 7
s 2 < =0++))22-1)
sup Mr(U,y,i,5) vE(+1)
548+ 8l12)
B>D
anD
Plugging this into Term C, we have
M
T
Term C < (48 + +8h1) 2)
21-1
Σ (1 () sp < (j+ + 1)21-1 (1+1))
BeD
z>D
==0
gi-1
< < < x )
(48 + 8
Σ
2
E
Σ ?
Σ (1-
1=1
Y=U
29

---

Using Lemma C33 we can simplify
2'
< < ( + (1-1)--1) )
E R0D
[Trm CJ < (48 + 8
Σ
21
22 1- E y
Σ
E
P(LL-
i=1
s <48 8 Σ 21-1/2
γ Σ pī (1- pt)
IND
= (48 + 8 (2 + 2V E by (Varr)].
AND
Plugging this into and observing that choose M be arbitrarily large, have as desired
E x>D
(SSCE(,,P')
- inf MEN
22 M T
E anD
[Term CJ]
$ (48 + 8ln2)
(2 (2+2x 222)
ly (Varr)]-
anD
C.1 Auxillary Lemmas
Covering Lipschitz functions. Let us first recall a standard covering of the class of Lipschitz
functions FF S [-1, 1] We will work with the metric d on the functions F induced by the co-norm; that is, for any f,g F, d(f,g) suPze[o.1] [f(x)) g(x)]. In this section, for > 0 and b > a where b-a E Z, we will use the shorthand [a, b)s == {a, a + 6, 6,...,b) .b to denote 3
endpoints of partitioning of [a, into segments of length 8. We will also use the shorthand [æ]s =
max {iő id < x, i E 33 to denote rounding down to the nearest multiple of ò.
Lemma C.2. For 5 > 0 where 1 E Z, consider all functions conditions
[0, 1] + [-1, that satisfy
Vz E [0, 1] f(x) E [-1,1]
(2) Vx E 00, 1], [1] [f f(x) 8
Vz E [0 -x)== f(x)))
This set functions, which we will denote by Fs, a 28-covering of the set of L-Lipschitz functions F: [0, 1] + [-1,1] in the metric d.
Proof. Fix 1-Lipschitz function f E F. Let f E Fo be the function in our covering where, for all E [0, 1/8. f'(x) = [f( Note that f' unique because the elements of F& can be identified by their image on j0, 1].. For any x E [0, 1], we have
(f(z) f'(x) [f(x) f((=]=)+++ (f' [((=)|+++ ((()))))
1x [x|,|| + 0 (((=)))) )((+)+))
26
where the first inequality is the triangle inequality, the second inequality uses the 1-Lipschitzness of f and that (x(x) f'(( [[x]] g and the third inequality uses the fact that [f(2) f'(=) < 8 and
la - [ < for all z 1.
x
x <
Bounding sums of 7. Consider the piecewise function (xx)
Vx,
x >
Lemma C.3. For all values 2....., Zn O, upper bound Dn
(xx)
vn > az).
Proof. First, suppose that El= F3 1. Then, >E 24.) Σn D1= D; and 2; for all i [n].
The claim is therefore equivalent to the trivial statement Ei=1 Et vn.
Σ Zt.
30

---

Now suppose that Ei=1 24 1. The
inequality gives
Σ
I S Vn,
Σ
Ti.
==1
1=1
By our assumption that Σi=1 Ti > 1, we have 7( EE== Tii =
Ei=1
Ti. We separately have that
Σ (x,)) 1 Σ Vza
iml
because 7(x)= =x S V for E [0, and 7(x)
Vi V for 2 1. Thus,
Σ (())) - Σ Vai S vi
Σ
xs = vn.7 Σ tr
iml
iml
C.2 Epochs of Doubling Realized Variance
Definition C.4. For I S [0, 1), consider the stochastic process (Var, defined as
Var, (I) = Σ pt - p2) lp. E I].
s=1
where x ~ D and pt = Pro 1o = 1| = x1 [ We define the epochs with respect to as the sequence TO, ... N where To O and, for each E [[log, (T)] + 2}.
Tk = min {t E [Tk-1 + 1, Var, Vart.,, 2 2*-1) u (00)
(5)
The epochs TO, Ti defined Definition C.4 partition the time steps a martingale into epochs such that the realized variance Var,(Z) increases by approximately 2 within the k-th epoch. In particular, we can understand Tı: as pointing to the last time step the kth epoch. The definition ensures that:
Epoch starts from time step 1, and ends at the earliest time step such that Var, (Z) 2 1 2².
For k 2 2, Epoch starts from the time step after the last step of Epoch & - 1, and ends at the earliest time step such that the total variance within the epoch reaches 2
We have the following technical facts about the epochs T. Fact C.5. The (fog22() (T)] 2)-th epoch is never complete, i.e., [[]o),(T)++
Proof. Our definition of Var, clearly guarantees Varr (I) - T, which implies Varr(Z) Var (I) < T < 2 (Tx2(()))+
and therefore, (T)22 = 00.
Fact C.6. For every epoch k E [[log2(T) 1 + 2}. the change in realized variance in epoch le is deterministically upper bounded by Var,, (I) - Varz,, (I) 2 + 1.
Proof. By definition, Var (Z) Var (I) < 2 Because pt [0, for all E [7], the
realized variance increases by most pf (1 (1-p)) pf) < in each timestep, i.c. Var,, (I) Var,,- 1. The fact follows by summing the two inequalities.
Fact C.7. For any epoch E [[loge(T)] + 2), the probability that the kth epoch ends is at most
I (2)2]] (2)
Pr IT < oo] < min
22
31

---

Proof. The sequence of realized variances Var1 (Z),... Varr is deterministicalyy non con-decreasing:
Thus, for every epoch k E [[log (T) + 2/.
Pr < co| - Pr [arr (Z) - Var 2 2 A Varr (I) 2
S Pr [1 [arr (I) 2 1I Varr(I) 2 2
Pr 1 [Var 2 1| Varr (Z) 2 V2
with the second inequality following T < xc implies Varr (Z) 2 1. We can next invoke Markov's
inequality Pr [X v
[ with v and 1 [Varr (T) 2 1] /arr (I) to recover
Pr 1 [[Var((Z) 221 11- Varr= v
2 (2) (2)21) (a)r
V25-1
Fact C.8. The exponentially weighted sum of probabilities that each epoch ends is at most
[ogg(()))+
Σ
V2k- P
<o0 < + 2) (V) 2 1] Varr(I)
oo)
Proof. We will prove the deterministic inequality
(1)g(T))+
V2h-1. [ oo] (2v2 + 2)1 [Varr(T) 2 1) Varr(();
the fact follows from taking an expectation on both sides.
Let K = max {k Tk < (o) be the number of completed epochs. When K 0, we have Varr < and both sides of the above reduce to O. Now, suppose that K 2 1, in which case we have Varr (I) 2 1. By telescoping, we can lower bound the realized variance by
Varr (I)
2 > 2k1
Separately, by definition of K, have
(T)+22
K+1
2 1 [ < 00/ =
Σ 2
k=
K+1
1 [Varr (I) 2 1
22k-
k=2
$ 1 [Vary 2 1| / (v2 +) 2)
with the second equality following from Vary (I) 1. Combining the previous two inequalities gives the desired inequality
[log (2)1+
V [ < <o0) (2V2 + 2)1 [Varr(T) 2 1). V Varr(I).
C.3 Random Walks with Early Stopping
We now prove technical result that the magnitude of random walk with random variance can be upper bounded by its (expected) standard deviation. Compared Lemma(5.2 the lemma below gives a bound that depends on >( (VVrr(Z)) (rather than the square root), and avoids the extra log [ log T'
term. While the leading factor (<x log [ is larger than the one in Lemma 5.2 ( Vlog [G], we will only apply the bound the case that [9] = O(1), where the difference between the two only constant factor.
32

---

Lemma C.9. Given function f [0, - [-1,1], y E {0.1)", and set I S [0, consider
the martingale Mi(f, I) Σ yt f(pt) (x.-p² 1 lp² E Σ}, where D, and pi
Pra'~D 1 (t=-) 11] Then, for any finite family & of functions from (0, 1] to |-1, 11.
any y {0, and any I [ [0, 11, have
E gwD
max (T, LE9
< <8(6+ log((g))
E (Vaar(())) ZND
where (Tr = E P:=1 - pt) lp: E I] is the realized variance restricted to subset I, and 1, Vr, 1.
(00) = I 1,
Proof. Let us decompose the horizon into epochs of doubling realized variance with respect to the subset I as per Definition C.4 Using defined in (5). we will write I = [T +1: min {T, T
denote the time steps composing epoch and write K max {k 7k < oo} to denote the number of completed epochs.
We will separately handle the contributions of epoch and those of later epochs.
First epoch. Since y/ E {0, 1) and Il I holds for every f E G, we can bound the expected contribution from the first epoch follows:
E D
max FEG
yt f(pt) (z+ - pp)
lpt E
I
<
E x>
x
pÊl
1
[pt
(6)
Note that for any E [0, 1] and Bernoulli random variable x Bernoulli(p).
E
I pl] Pr [x 0] 10 +r 1] pl 2p(1 p)-
thus follows that the process (Xt)usesT where
X₂
Σ [|2, p.l -2p
pt)l lpt e
is martingale, conditioning on any realization of 11:(t-1), we have
E 12, pil 2p v.) x1a-1]= By the optional stopping theorem, we have
E
[|x přl] 2p, p.) 0.
Bernulli(n
Σ | - płl - 21 - pī)]
jpt 2
= E [X,,,,] = -=
DND
Plugging this identity into 6 gives
E
max FEG
- f(pt) (x. 111- - lpt E I
<
2p (1 pi) Lip z]
IND
1=1
= 2 E [Var,, (I)
z>D
< 2 E [min f2, Varr(())
R>D
< 4 E [min (1, Varr (Z)) R>D
where the third step applies Fact C.6 with k 1.
33

---

Later epochs.
Applying a triangle inequality and the law of total expectation gives
max SEG
Σ
V1 f(((())) (xx 125-pt pt) 1 p I
anD
K+1
E
max JEG
Σ f(P() (xe pt) 1 1pt E
2=2
K+1
$
Σ
max FEG
Σ E
ye
f(p)) (Ie - p() 1 lpt E E
(8)
awD
[Tgg( +2)
T
Σ
max /E9 t=1
f(vt) (xx -T)) 1 1ot EIALE Tc]
2nD
k=2
[T)]
-2
Σ
Pr(ta-1 < oo]
max
A Tk-1 o0)
anD
fEg
where we define the process
My
Σ yt f(pt) (xa - pt) Pe EIALETA
In the above, the third step uses Fact C.5 namely that (T)]+ = co. inequality to obtain a maximal inequality for each of these M processes.
We can use Freedman's
Fact C.10. For every y E 10, and k 2 2, we can uniformly bound the process M defined in 99) over a finite class G of functions from [0, 1] to [-1.1] by
E
max M SEg
Tk-1 < 00
S /2 2 log ( + 2 log 9
BrD
Applying Fact to to each of the martingales M in ( gives
max SE9
Σ
ya f(p)) (xx p.) [pt E Z
w>
+1
[oga
(7)
Pr[ta-1 < oo) (2222222)))) (2 2 log (9]) + + 20og2lg9999 (9)).
(10)
To upper bound the right-hand side above, we use Fact C.8 to bound
(2')+2
Σ
Pr[me-1 < co) <0o
< E
[Vary (I) 2 1) Varr (2+ (2+2v2),
and use Fact C.7 to bound
[loga (7))+2
(2)+2
E [Var (I) 2 1] Varr II)
Pr(me-1 < col
min
1,
2)k-2)/2
2
2
< E
Varr (T) 2 11 /Var (2 V2).
Plugging these into 10 gives
max
(f.g.. Mn, (f. y. I. FEG
< E [VarT(I) 2 1]. (I) (2 222) 2 1olog + /2 /2log
< E [Varr (I) 2 1] (V)
8(5 + log (9]).
(11)
34

---

Combine bounds. claim
Combining and 11
and recalling the definition of % we recover our main
18 2>D
max MT (f fEg
I z>D
max Mr, (J: JEG
E
max Mr(J,,, M. LE9
x0D
[min {1, Varr (I) []]]] 85 + log ( .E E 1 [Varr(Z) 2 VarT(I)
< 4 anD
(v(Vart (Z) + 15
E z~D
(vVarr(T))
< 8. (6 + log (
E
[Var)
I~D
The second step above applies Inequalities and
The third holds since min(1,æ) S 7x) and
x 2 1] v S 7(z) hold for all x 2 0.
Let us recall Freedman's inequality [Fre75)
Lemma C.11. Consider marlingale Mn D with filtration (Ft) where JM, M,-1l S 1 for all 1 E [n]. For all v, y > O, we have the following bigh-probability bound on Mn:
x²
Pr 3m, Mn 2 I
E [M M2-1)² 1 S y S exp
2(x w)
We now prove Fact C.I0
Fact C.10. For every y 1), and k 2 2. we can uniformly bound the process M defined in over a finite class G of functions from
[0, 1] to [-1,1]
E
max M Tk-1 < 00 JE9
V2 + 2 log 9 + log 9l
RND
Proof. Fix any f G. For t o Is. we have trivially that for any 21:-1 E {0, ddc-vr' pi) 1 [ Ia pt I] - 31 1] 0.
E D'ND
[yee ((r)) (x/
Fort E Ig, since 1 [T--1 oo] and pt is measurable by F14-1, again have that [ee f(pī)- (#t -() 1 [t
E
4a A
P
Z
2' x1:--1
r'DD
= f(i)) 1 T e T
E z'DD
-1--1 pt
O.
This means that A is a martingale even conditioned on the event that Tk-1 < oc.
Our construction of epoch k in (5) further guarantees that the realized variance of M is determin- istically upper bounded by Var,, (I) - Var (I) 2 + 1 (Fact C.6). Thus,
2k + 2
PT p.) 1 t I Apt EI
E za BemBoullllip))
[ 1 I EI
Σ
E
- pT)² [(06-
|-1-111=1---- = E EI
A,DD
T
2
Σ
vr f(wi)²
E.
[(0] - pt)² | = = E A ET
2iND.
1=1
Σ
E xD
(M. M 2/-0-1 I1-t-1
(12)
[=1
35

---

where the first equality uses the definition of Bernoulli's 's variance; the second equality uses that, conditioned on Ff 2y Bermouli(pp:] ); and the second inequality uses that y I 1 and If())) s for all x E [0, 1].
We can thus use Freedman's 's inequality to bound the deviation of each martingale Ma First, observe that the quadratic formula gives the inequality exp
(( S if x 2 log(1/p) +
v /logg(() (p) + 2y log(L/p). We can therefore invoke Lemma C.11 with = 2 + 1 and
== 2 log(1 + /2 log(1/)) 2 log(1/p) + v Vlog (v) + 2y log(1/p)
x
to show that
T
2 Pr
M 2
R.
A
Σ
E
[MM
SaPJ-MMaa -M 1ai--=11::0 5 + [kl1k-1 <00
Applying
12
we can simplify this to
M 2 /2(22-1 1) log(1/p) +llog(1/D) Tk-1 <0
p
Pr
M 2 / log(1/p) + 21og(1/p) Tk- <00
2 Pr
We can then take a union bound over G for
2 log((g))))))))) + 1og((19) Tk-1 < <00 M FEG
p 2 Pr
max
Using the layer cake representation of expectation, we can convert this figh-probability bound into the expectation bound through change of variables
max M FEG
Th-1 00
/ Pr
max M 2 t Tk-1 o0 dt
JEg
= 1
V
2h Log (p)pp)) + 2 log([9] /p) dp
2
9l VT erfe
log ( log (9]) + 2 2 log (g],
where the last equality follows by Fact C.12 When [
1, compute the integral to be
E
max
M
Th-1 < 00
< 2
exp( log [g]) + v log [9]) + 2 + 2 log [
2 log G
22 12 2 log 9 + log [9]:
where the first inequality uses that erfc(2) < exp( (xp(-2#)
When g = 1, we again have
E
max
M SEg
Th-1
0
< 2k-1 2
S 2 (2 2 log (g]) + +2+ 2og [g)
Fact C.12. For k. n E R.4, the following integral equality holds
[' V ph+ 20+ 2 2lo((n/p) dp v (5 erfel PeffcV/Top Vog + Vlogn) +2 + log
where erfe denotes the complementary error function.
36

---

Proof. Let us first separate the integral into two parts:
L. 2
dp S.'d / log(n/p) dp+ + S 2log(n/p) dp.
2log(n/p) 1 log(n/p)
We bound the second integral easily. Since log(n/p) log logp,
S. 2 log(n/p) dp=
!. 2(log - log p) dp
log ( dp 2 { log dp 2 2oo n +
(13)
Now we consider the first integral. Let log(n/p). Then ne- and dp n du. When p log n. When p 0, goes co. Thus, the integral becomes:
f 2kt2 log(n/p) dp
log
V2k+lu (-ne du
nv 26+1
Vue- du.
Jlgn
The integral involving the error function erfe(z) be recognized:
/ Vue
1
du
-Vue
du
logn
log
log
2
lim (-vue-u) 1-000
Vlogne logn) logn)+
00 1 c du
jogg 2/
000 e
Vlogne e logn
du
2v
logn
00
Vlogne logn
dt
Vlonn
Vlgg +
Vi erfe /
logn).
n
2 (n)pp/)) dp is given by Thus, the integral 5o v
T " Cerffe/ooog) logn)
Vognn
nvTT erfel (Vlgn) + Vlogn]
nV/2+11
(14)
Summing
113 and 14 gives the claim.
C.4 Proof of Lemma 5.2
Lemma 5.2. Given a function f [0,1] - [-1,1] and E (0, 13,, consider the martingale
Mc(f. y) = E Us f(P)) (I, p=) where x ~ D. Then, for any finite family G of functions
from [0, 1] to [1 and any E {0.1)* 1)T, we have
E
max My (f.1) feg
< 0 [log |g] log + Vlog |6
E
TVVar
Proof. Let us decompose the martingale (f..v) into epochs of doubling realized variance with respect to I [0, 1] as per Definition CC.4
Using 7 as defined in ( we will write Jg. == [Tk-1
min (T, Tı }] to denote the time steps composing epoch and write K = max {]: Tk < 00) to
denote the number of completed epochs.
37

---

Applying a triangle inequality and the law of total expectation gives
E DND
max LEG
y/ f(P)) (xxe 14)
K+1
Σ Yt f(vt) (ote - pi)
max
DND
fEB
K+1
E
max
Σ rETx
ye f(Pi) (Iee - pt))
JEG
[og (T)++2 Σ
E
max EEG 1E
Σ Ye f(pt) (xe - př) 1 E [n]
RND
(oog((7)]++
Pr( < <00
E
max lEg
M Tk-1 < 00
(15)
anD
where we define the process M = Ei= f(rt) (xt - pt) 1 1 E Is]. In the above, the second equality uses Fact C.5
namely that (T)R
Applying Fact C.10 to each of the
martingales M
15
gives us
E
max FEG
Σ
Ve f(Pi) (Ir pi)
BND
(T))
Pr Pr|ma-1 xo) [V2+-I 2 [9]) + 2 log |
We upper bound some of the summands in the right-hand side by using Fact C.8 to bound
[lgga +2
Pr[rk-1 < o0) v < E [Vrr]] (2 + 2v2)..
This gives that
max lEg
Σ
y/ f(pt) (xt - pi)
IwD
$ (2 + 2og (g))) (T)]l + 2) + E Varr (2-2v2)(2 + 2//og (g]).
D Supplemental Materials for Section
Notation. For all stochastic processes (Xt), X -xmin(ta,7) Xe, to denote the increment within the time interval (tz, t2] (with X, 0 by default).
D.1 Proof of the Weaker Lower Bound
We restate and prove Lemmas 6.2 and 6.3
Lemma 6.2. For any x E {0. 1)T and p E 1]T, we have SSCE(x, p) 2 (VNT).
Proof. Recall that SSCE is defined using smCE, which is in turn supremum over the family F of Lipschitz functions. Since both f == 1 and f = -1 are included in F. for any realized sequences æ and p, we can lower bound SSCE(x,,)) p) as follows:
T
SSCE p)
Σ
Ue (xx Pc)
=E
Σ
2t +
Unii((
38

---

where we have defined 2, == (ye- (2, Pt)) to be zero-mean independent random variables, and j == Ei=1 0.5( pt). Now partition [T] into T1 and T2, where T₁ includes the all time steps such that 2 P.l 2 z. and T2 T Ti contains the remaining time steps. From the definition of Nr, it immediately follows that Nr = [Til. Letting Zi == Eter, Zn and Z2 = Eier, 2t, it remains to lower bound E [|Z| + Z2 al] by ((vNT).
We will first prove that E 2 1] 2 CVNT for a universal constant C > O. From the Berry-Esseen theorem (e.g. from [She10]) ) the CDF of Zi be approximated by the CDF of the standard normal
distribution as follows:
Ve E R, Pr[ S x on]
<xooo]
<(x) S Co % po:
where (xx) is the standard Gaussian CDF, Co is universal constant larger than 0.56, and
(ax - pc)² 2 1 VNr:
o0
[
V
4
4
Nr:
IET
LT
|
33
2t 1//2/8 1
max Po
xt p/12/4 _ 2
IET1
E
||
LET1
As result, lower bound the probability of [2 2 0.05 Nu follows:
Pr Z1 0.05 NT
2 Pr |r 0.2- aol
(oo 2 (VNT)
2 1 - Pr [2] S 0.2 mol)
(Z1 is symmetric)
2 2 - (1 20h/ V VNT)
(Berry-Esseen theorem)
Since Co < 0.56 and (00.2) 0.58, we can guarantee Pr [ 2 0.05 NT > 22(1) for all
NT > 8. When Ny < 7, have |Z = Nr/2 > 0.05 when all {z, E Ti are positive,
which happens with probability 2 Nr 2 2 2 = Therefore, we can always conclude that
E 1 2 0.05 Nr. Pr
7 2 0.05 / 2CNT
for some universal constant C >>0 0.
Finally, we consider the randomness of Ze and show that E [|2 + Zz + All 2 g V Applying the tower property of expectations, we have
| 21 Zz + All =
21 + Ze
Zz]
Consider the following two cases for the conditional expectation inside:
When 12 + 1l
> 1 VVT. we use Jensen's incquality and E [Z]]
0 to obtain
E 1 Za + m
Zz
E ZZ + Zo + μ Z2]
Zz + μu VNT.
* When [Z + μ| <
/Nr, we apply the triangle inequality and have
E
11
Zz + μ
Zz > E 7 || Zz + CVNr C /Nr = CVT.
Therefore, regardless of the realization of Zz, we always have E 1| + Ze + Ho
[z] > /N
Taking an expectation over the randomness of Zz gives the desired bound SSCE (z. p)
C. /Nr. 0
Lemma 6.3. The stochastic process (Ne)uery satisfies E [VNT] 2 Q(E [ Varr) 0(1).
Proof. Since NT 2 Vart/16 16 implies / NT 2 Varr/ 4, we have
VarT
Varr
VarT
WarT
Varr
V NT
2
1
Nr 2
1 Ny <
4
16
4
4
16
39

---

Therefore, to establish the inequality E [VNT] 2 Q [vVarr] O(1). it suffices to prove that the expectation of the second term-which we denote with M-iss upper bounded by O(1), i.e.
M = E Varr 1 [Nr < Varr/16] - 0(1)
(16)
We proceed by partitioning the range of Varr into subintervals of geometrically increasing length and enumerating all possibilities for which subinterval Vary falls into. If Vary S 1, its contribution to M is clearly (1)). Otherwise, we must have Vary E [2',2'+ 22+ for some / E N, which implies that Nr- < Varr 16 < 2 Therefore, we bound M by taking union bound over all such l's:
M Σ 0(1) +
Σ
E
Varr
[Nr 2 A Varr E 22
IEN
$ 01
Σ
21+
Pr [Ng < 2 Varr 2 21]
(17)
IEN
Now we bound Pr (NT < k/8 A Varr 2 A] for any fixed value of k (that plays the role of 2 by constructing a sub-martingale. We start by partitioning the time horizon [T'] into blocks based on the realized variance Var,, such that each block B3 == (bj-1, by] terminates upon the realized variance Varg, first exceeds 1. Formally, using notation Xtyitz == (min - -x,, to denote the increment of any process (X,) in (ti, t2] (with Xo- by default), the endpoints b, are defined recursively as:
bp = 0, by- == min (oo) U {t E [b,-1 + 1,7] Vars 2 1], Vj 1. We show in the following lemma that for each block By, the expected increment Ng, within By is lower bounded by a constant as long as B, terminates before T.
Lemma D.1. For the constant c = 1- 1/e, E NB, 2 21] - c. [b, co] For.i] 2 0.
We prove Lemma D.I in Appendix D.2 This lemma justifies that if we define A, as
Ao = 0, Aj A₃ = [Nv, 2 1] 1 1b, < xo| (j 2 1),
then (Az)520 forms a sub-martingale of bounded increment |4, أ || I 1, making it unlikely for any Aj to deviate significantly below 0. However, if Nrr < k/8 and Varr 2 k: then Av/2 must witness large deviation: on the one hand, block B2/2 should terminate properly because the variance in each block cannot exceed 2; on the other hand, Nr < k/8 implies that at most k/8 of these blocks can have a nonzero increment NB,. As result,
As/2 -,, 1 NB, 2 - c E,_1 1b, oo) S Ny c- (k/2) < -k/8. 1=
By applying the Azuma-Hoeffding inequality for submartingales, we can quantitatively bound the probability of such a large deviation by
Pr [Nr= < k/8 A Varr 2 k]
<
Pr [Aw/2 S kk/8] S e -k/64 k/64
Finally, plugging the above bound back into equation 17 gives us
M 0(1) + Σ IEN
2 e O())
We have thus established the inequality 16). which in turn proves the lemma.
D.2 Proof of Lemma D.1
Now prove Lemma
D.1 which restate below.
Lemma D.1. For the constant
1/c, E 1 NB, 21 1b, <o) Foj_1] 2 0.
Proof. We first show that for all / E [7], we have Pr [M, = 1 > (1 - pf), where F,-1 denotes the filtration generated by all the randomness up to time / 1 Note that conditioning on F,-1, Zt is distributed according to Bernoulli(p)). If the forecaster chooses p: > 1. the condition
40

---

10 Pol 2 1 holds when Ft = 0, which happens with probability 1 p?; otherwise it holds when It 1, which happens with probability p Therefore. regardless of the choice of pt. we have
Pr Pr [n = [t-1] ==*BBenoullippt))
10e Pa 2 1/2] 2 min (pi 1 p.) 2 P p?).
This allows us invoke Lemma D.5 with qi = Re, 7t == p. (1 pt). and 0 1. where we only consider the random process inside block B,. In this context, the stopping time 7i corresponds to the end of the block, i.e., by. Therefore, by applying Lemma at time step 1 we obtain
Abz-1 =Pr
-Pr(Ne No; [No; 2 1 Pb (1- e--e-) Pr [b
00 Fb; 1] 2 0
Fo, . 2 0, where c -=
- E 1 No, 2 1] 1 [bg < x3|
D.3 Stronger Lower Bound
In this section, we state and prove the stronger SSCE lower bound for all forecasters.
Theorem D.2. For any D E (((0, SPT S2E [<[arr)]), where the function ? is defined as ((x) = x 1 < x < v
1].
Proof of Theorem D.2 The theorem holds by combining Lemma 6.2 which lower bounds the SSCE by D (T))N)), and the stronger lower bound on E WN shown in Lemma D.3
0
Lemma D.3. There exists a universal constant C > 0 such that E |VNT] C- (-EE((arr)))) where
the function y is defined as 7(x) x 1 S x 1] VF 1 I 2 1].
Proof of Lemma D.3 The proof is also based on partitioning the time horizon into blocks B, (by-1. b,l each with approximately unit variance--a -similrr the approach used in proving Lemma 6.3 However, this proof involves more careful analysis of the growth of /N, by further grouping blocks into "epochs" and giving special treatment to the first epoch, where the cumulative variance is very small.
Specifically, consider the blocks B, = (bz-1,
by] defined by
by = 0, by = min {oo} U {t E [by-1 + 1,7] | Varb; 1:t 2 1}, Vj
Recall that the increment of Var, satisfies Var, Var, = P1 pt) 1/4. Thus, every block satisfies Varg, B, = Vara, - Vara,-1 (Varo,-1 - Vara, (Vart, Vara, S 1 + 1/4 = 5/4. We further group blocks into epochs such that the k-th epoch To = (Tk-1, TR. contains R 24 blocks:
To = B1. Tk
U
By, 44
(or equivalently, Ta b2*).
jE(2A-1.2% 1.2
In addition, we define N₂ as the sum of n, capped by in each block:
N₂ =
min(NB, 1}
Σ 1 [NB, 21]
Jt
Clearly, for all the realized sequences we have Ny 2 Ny and No.
S 2t where the latter is because
each block contributes at most 1 to Nr In the following, we will first analyze the growth of / N; in epochs l: 2 1, then provide a different analysis for the zeroth epoch.
In each epoch To with & > 1. We start by establishing the following lemma, which extends the characterization of Lemma D.I into epochs.
Lemma D.4 (Lower bound on No.). ) For any k 2 1, we have
NTy 2 2k-2 Pr PT(Te < oo].
41

---

Proof of Lemma D.4 According to Lemma D.1
we have that in each block Bj = (by- bzl.
E [ [NB; 2 c. 1 [b, < co]]
E
E BB,
1] - [b, < o0|
Po;
|] 2
where the first step uses the tower property of expectations, and - ! 2 2 Summing all the blocks in epoch Thp obtain
E
NT.
E No,
[ 2 1]]
E
(Definition of Ty and N,)
j
111
2
2 c E
1 <00
(Lemma D.1
24 1+1
2
2 c.EE
Tk
<00
(bj S b2z = Th for all j S 2
1=2
2 2 Pr [T < 00].
(c 2 1/2)
We have thus established Lemma D.4
With Lemma D.4.
we obtain lower bound by linearizing the increment V N₂ each block.
Ne
Nrr-
(Tre - (Niz - NNr..)
2 E
(Concavity of function /x)
2 1-1
Nrz - Nra.1] = 2 21
NTo
(Nr, 26
2 2 Pr [Te o0].
(Lemma D.4
The first step above can be alternatively justified by vā vb= a-b va+vb 2/a
2
a-b
which holds for all
2 b2b00 0.
In epoch To. We now analyze V NT, in epoch O. Note that the To contains only the first block B1, so this value is either depending on whether there exists [ - Pel 2 ]] =1
B₁ such that ne
Recall that in the proof of Lemmal D.I have shown that regardless of the choice of Pt.
Pr [4
Fr-1)=
Pr
| Pel 2 1/2] 2 (1 pp))
2t Bernoullll)))
Therefore, in the special case of product distributions (i.e., the sequence (pt) deterministic and each outcome ~ Pt is independent of other time steps), we can directly bound the probability that
No. as follows:
Pr
Noo
=
Pr nn 0]
2
[1 p1 př)
t=1
1=1
71 Σ t=1
1
2-
exp
P1 -pi)
1 -i-eexpp-- exp(- VarB_)
Varg,
where the last step follows from the inequality - -- x/2 when 0 S S 5/4, and the fact that Varg, < 5/4.
42

---

However, in the general case where the sequence (p:)) is itself random and depends on the history of x 's, such a direct argument fails. Instead, we use Lemma D. that extends the above analysis to this more general setting. Lemma D.G itself similar but more general statement than Lemma D.5 as it applicable even when the cumulative variance is smaller than the hard threshold Invoking Lemma D.6 with 4: == n2 F = pł (1 Pt), ) and the stopping time 7 as the earlier time step between the end of block B1 and the first time where fig = 1, we have
1 E [Var,];
Pr 2 1] 2 B [e-
Var.
2
2
where the last step again uses 1 - c 2 x/2 for x E [0,5/4] Moreover, since 5 4 1 2 1| 2 Var,:b,, also have
4 E Var
1 R [aar 2 2
[N 2 1] 2
Combining the two inequalities, obtain
E
NTo
= Pr (NB, 2 1| [N, 2 1]
2 E [aar, + Var = E [ara
4
2 E [[aar [ = co]]
(T1 = 00
Varr = VarB,) )
Putting everything together. obtain
Combining the lower bounds for epoch 0 and epochs k 2 1, we
E
Nr
=
E
N
+
Nr - Nr..
A21
2 E Varr 1 [n = =0]]= +
Σ
22-3. Pr
Pr(Te <
4
k21
E [[aar
1 [T co1]
Σ
00, =0) Σ
4
=
#21
Kic
2
Varr 1 [7 = o0] + Σ
[ <0, o0| -2
8/2
1
E Vart 1 [T| oo)
1 [T--1 < 00, -o] Vart
16
where the last step follows from the observation that the cumulative variance in each block cannot exceed 2, so oo implies that Varr < 2*+1, i.e. 2k/2 2 /Varr/ /V2. Finally, since = co is equivalent to Varr < 1, we have established that
1 E Varr 1 [Vary < <1] +]]+1 [Vary 2 1] /Var
1
E
N
N
= 16
E E>
16
The lemma follows from the fact that Ny 2 Ny always holds, which implies E [Nr]]
N
N 1o E (VVarr)).
D.4 Auxiliary Lemmas
Lemma D.5. Let Qi = E.si 9s. Rr Eesirs To be two (coupled) stochastic processes such that a E (0. 1), ri E [0, all E [T]. Let denote the filtration generated by all the randomness
up to time t. Suppose Tt is deterministic function on F,-1, and == Pr [ge 1 Fr-1] 2 Tt-
43

---

For any constant 0 > 0, define To to be stopping time chosen as the first time that R4 reaches 6, i..,
To min {t E [Z]] R 2 0}.
Let Q = Qu:to be the sum of 9s in the future until the stopping time To- If To, then we let
QT == 0. Consider random variables A₂" defined on the filtration F, as follows:
A. = Pr Q 2 1 Ft] - (1-e-10-Ri)) Pr [Te < 0o Etl.
Then we have A, 2 ffror every t S T and every event in Ft.
Proof of Lemma D.5 It suffices to prove the inequality conditioning on events in F, that are "atomic" in the sense that they uniquely determine the values of qi and r1:-- The general case would follow from the law of total probability. In particular, in the following proof, we may view the value of R as fixed when we analyze the quantity A..
We perform a backwards induction from t = ' to t = O. Consider the base case of t = T. If Rr 2 0,
we have
Ar = Pr Qr 2 1 Fr (1
c Rr)
Pr < 0o Frl 2 0.
0
50
Otherwise when Rr < 0, we have Pr [To < oo Fr] = O. which also implies Ar = =0 0.
We then assume A, 0, and show that the same holds for A,-1, where / 5 T. If R₁-1 2 0,
clearly have At-1 2 0, the factor (1 (0-R--())) would be non-negative. Therefore, it suffices to consider the case that Ra-1- < 0. In this case, the stopping time should be 2 t, so
we have Qi = qr + QT. We bound A,- by breaking the event Q 2 1 into two cases: either
l: 1, or q: = but Q 2 1. We have
Pr Qi 2 F--1
Pr Pr(g: 1 [r-1] + Pr [g: 0| F. [[-1] Pr [t 1 F1-1, =0]
= St + (1 - 8t) E Pr (ot 2 [F.] Rt-1, ge = o]
For the second term, apply the induction hypothesis of A, and get e 10 Rv)) (8-Ri) [ Pr [70 < 00
E
Pr QT 2 [F Fr-1, 4: = o] > E - e
F F- - o] F2]
v() -1-e-10-RB-1
(1 (1-e (0- 10-
R,
Pr [Te < co F1-1, 9: =0],
where the second step uses the fact that conditioning on Fi-1, Rs = R + Tr. As a result, we obtain
Pr (Qt 2 1 F. F--1] 2 st + (1 st) (1 -1- (0-- Pr < 00 F--1, = 0]. (18)
We also expand the conditional probability Pr (To < 00 Fr-1] as follows:
Pr [To oc
Fr-1]] = St Pr [To < x0 Fr-1, q: 1] + (1 st) Pr [To < o0 F.-1, = =0]
I st + (1 $: Pr Pr To < 00 Fr-1.
(19)
Combining the bounds in 18 and 19 we obtain
Ar- 2 St + (1 - 8t) [1 E (0- B---Ti)) Pr [To < 00 Fo-1, = 0]
(1- -1-e--0-Ri0 -00- 11 + (1- (1= Pr(7e < 00 Fr-1, =0)
= e (0- R1-1) + (1 8t) (e 10- (0- e 10- (e-- Pr (To < 00 |F-1, 0]
2 e (u-B. 1) (0t . t + 1 - e²
(bounding the probability by 1)
2 é (0- Ri-1) (P: nt + - e²+)
(st 2 from assumption)
(0- (re - 1) 2.
(Vz, - x 2 1 x))
We have thus proved that the claim also holds for / - 1. This completes the induction.
44

---

Lemma D.6. Let Qi = Ec. R.. = Es be two (coupled) stochastic processes such that de E {0, Tr for all (T]. F, denote the filtration generated by all the randomness up to time t. Suppose Tt is a deterministic funtitooo on Fr-1, and St = Pr [qt = [[r-1] 2 Tt-
For any constant > 0, define T to be stopping time chosen as the first time that either Rg reaches 1 or qi -, i.e.
T == m=) E [T] Rs 2t [T] qi =1.
Let Qi Qui and R Qu be the sum of 9s and rs in the future until the stopping time т, respectively. We also let QF R when t т. Consider random variables Ag 'ss defined on the filtration F, as follows:
A Pr Qt
F2
E
R F1
Then we have A 2 for every t & T and every event in Ft-
Proof of Lemma D. Using similar approach to that for Lemma D.5 we prove this claim via backwards induction from = T to & = 0. Again, we only consider the "atomic" events in Fr that uniquely determines the values of qı:z and ria, and thus whether S t; the general case follows from the law of total probability.
For the base case of = T, we have
Ar Pr
Q
2
Fr
+
E
RT
FT
- -1 0.
=0 2,
:
Now for $ T, we assume the claim holds for and analyze A, If S we immediately obtain A,- 2 0 since Q = R = 0. It remains to consider the case of r 2 t. For the first term
of A,-1 (the conditional probability), we have
Pr Q 21 1 F
Pr [: = 1 F.
+ Pr [4: = 0 F
Pr [0 2 1 FF = 0]
St (1 st) Pr
Q 21
Fi-1, =0
2 st (1 st) -Ri Fr-1. = o]
= (1 *) R Ft-1. lt =
where the inequality step follows from the induction hypothesis A 2 0.
On the other hand, the second term of A (the conditional expectation) can be bounded as
E
1 - e
R
F F--1
Pr
qt
F Fr-1
(1
(g: implies t and R r2)
+ Pr
q:
IF --
E 1 -
F.-1, Cr = 0]
= 8 e (1 8e) R2
e
- R
F Fr =0
2 - E e - (1
F = 0]
(Jensen's inequality for the convex function e-*)
Finally, combining the bounds for both terms of A we obtain
A = Pr
@+ 2 1
Fr-1 E - R F--1]
E
(1-+)) (1 st) R
Ft-1, =
Rd. -e- - st))
F FI-1. qt = 0
( R 2 1)
2 E
Ri
(e- - (1 s1) Fr-1. =
(s, 2 r by assumption)
0.
(e- > 1-1, Vo 2 0)
We have proved that Ar-1 2 0. As result, A, 2 for all t < T and all events in F,
45

---

E Proof of Theorem 1.2
In this section, we prove our main theorem (Theorem 1.2 by combining the theorems established in the previous sections, and then verifying the completeness and soundness of the SSCE.
Let D E A((0, 1)") be an arbitrary distribution and define the random Proof of Theorem 1.2 variable
Varr Σ Pi(L - p();
D, where Pž = Prann (of =1 221:(--1) 11)(t-1)-- By Theorems C.1 and D.2 the
truthful forecaster gives
errssCE (D, Atruthful (D)))
(D))= = LDD
(VVar)))
whereas
OPTscCE(D) =
1>( (Varr))) LrD
E
In the above, the O() and (2() notations hide universal constants that do not depend on D. Therefore, there exists universal constant such that the SSCE is (c, 0)-truthful.
Completeness.
Now we verify that the SSCE is complete. For any x {0, 1)", we have
SSCE(2,
E
sup Σ yr f(x)) (0t - 21)
((0.I)((
fEr
For any a E [0, 1). the upper bound
E
SSCE(#, a Tr)] = =0
(T)
4E' Bernoulli(a))
follows from applying Theorem C.1 to the product distribution D = -IIT_1 r=1 that (xx S /x for all 0.
Bernoulli(a) and the fact
Soundness. To show that the SSCE is sound, we first consider the case that E {0, 1 is arbitrary and the predictions are p TT r. Noting that the function i 1/2 is in the family F of 1 1-Lipschitz functions from [0, 1] to [-1, 1}, we have
SSCE(æ, Ir - xx)
E U-Unf((O.1TTT
sup fEF
f(1 xz) (xe (1 x1))
1=1
E
(x, 1/2) (2xr 1)
y~Unif((..117)
T
E y~Unif((.1177)
3/
Q(T),
where the third step holds since (x 1/2) (2x 1) 1/2 holds for every {0. 1}.
Finally, we fix a, 3 E [0, 1] such that a + 3. For fixed x, E {0, 1) we have
T
sup JEF
3/4 [(3) (xt B) =
Σ M/ (x+ - B)
46

---

Taking an expectation over 21...., FT Bernoulli(a) and y ~ Unif( 1)7) gives
T
E
SSCE(x, 8 B-r) = E
sup fEF
(xt - B) f(3)
Pe (em
tm1
E
V1 (xc B3)
x.
E
Vt
(at - 13)
M.M
Da. (T))
where the third step follows from Jensen's inequality E [|x] 2 | [X]]
F Proof of Lemma 7.1
Lemma 7.1. For any x E {0, 1)" and p [0.
SSCE p) < 2 smCE(I,p) + O(VT),
1
where the O()) notation hides a universal constant that does not depend on T, x or p.
We prove Lemma 7.1 via standard chaining argument.
Proof of Lemma
7.1
We decompose the SSCE as follows:
SSCE(x,,7
y1 ((t) (sx+ po)
E (0,)
sup fEr
1 1 -(pt)) (wi pt)
S
Σ 1/t - fET
sup
+ sup feF
> f(t) (x: - pt).
(0.
Note that the second term is exactly 5smCE(2,, (x, p), so it suffices to bound the first term by O(VT))
For notational convenience, let M ΣT (y+= )) f(P:) (z, - P.) for function f E F. We
will establish the following bound for any N and functions f2, .., fN from [0, to [-1, 1]:
sup (1) < O(VTloggN). EEIM]
E Un.U
(20)
Assuming Inequality 20). applying Dudley's chaining technique Dud87 to the d-covering F3 defined in Lemma
would give
sup ( fEF
S 1/' V [ol
d6
(chaining)
VT 1'' 8- dd
(log [sl ((1/)) from Lemma C.2
$ O(VT),
which implies the lemma.
47

---

Therefore, it remains to establish Inequality 20) We prove this using Hoeffding's 's inequality and union bound. For each i [M] and every & O, we have
N
M(
Pr sup [E[N]
2
(union bound)
1=1
N
25
exp
(Hoeffding's inequality)
E
(Ex
1=1
2s²
S N
exp
(Ifill> 5 Vi E [N]
T
Finally, the bound 20 holds by taking integral over 0: shorthanding X supie(N] M we have
+00
E E S
2r] dr $
min e 2/ ,1] dr O( O(VTlol N).
This completes the proof.
G
Supplemental Materials for Section
We justify the claim in Section 8 that it is impossible for the SSCE (and most natural calibration measures) incentivize truthful prediction against all adaptive adversaries.
Suppose that the adversary draws from Bernoulli(1/2) If the forecaster predicts = 0, all the subsequent bits are zeros; otherwise, the adversary keeps producing independent samples from (1/2).
Clearly, the truthful forecaster predicts Pt 1/2 at every step [T]. and the resulting outcome sequence is uniform over 1) The resulting SSCE is then (/2 in expectation. If the forecaster keeps predicting p: = 0 instead, the expectation of SSCE(x,p) p) is only O(1). Note that this impossibility holds for any calibration measure CM that satisfies
[My, (z, /r/ w(1)
2t cr Bernoull(
and
E 21 Bernoull
CMT(21 o -)- 0(1),
where denotes concatenation.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims match the theoretical results that we prove in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: This is a theoretical work, so the results hold for the specific problem setups and formulations, which we formally state in Section 2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
49

---

Justification:
All the theorems and claims are formally proved, either in the main paper or in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
50

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
iy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
51

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp://eaarrppp.cccppaaa//haaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification; This is theoretical work, and there is societal impact of the work performed to the best of our knowledge.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
52

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
53

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
54


Reviews:
[{"review_id": "bIYao9du0k", "reviewer": "Reviewer_74Zg", "summary": "This paper proposes revisiting the calibration measure by emphasizing three main desirable properties for the metric's behavior: rewarding accurate predictions, penalizing incorrect ones, and ensuring truthfulness. The authors define truthfulness as the ability to accurately predict the conditional expectation of future outcomes. The paper's core findings are twofold: first, it demonstrates that most calibration metrics do not adequately capture truthfulness; second, it argues that a small modification to the classical Expected Calibration Error (ECE)—specifically, subsampling the window in which the ECE is calculated and then averaging the results—is sufficient to meet all the desired properties. The whole article is a series of theoretical arguments supporting these claims.", "questions": "- Could you numerically highlight any meaningful difference between smECE and the proposed SSCE?\n\n- Does the introduced subsampling breaks to possibility to easily draw a reliability diagram as in (Blasiok & Nakkiran, 2023)?\n\n\n- The definition in line 41-42 is crucial to the paper and deserves to be more clearly introduced. It is formalized in page 5. This in general makes the paper quite convoluted (most of the point -even simple argument or definition- are understood after reading a long detour. For a > 50 pages technical paper it is quite painful and I personally just gave up reading it.)", "limitations": "Ok", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The claims appear to be supported by rigorous mathematical arguments, which, I found,  are also quite lengthy and challenging to follow.", "weaknesses": "The theoretical argument for including the notion of truthfulness is intriguing, but I couldn't discern any practical implications for omitting it. At the very least, we would expect some numerical demonstrations, even on simple toy examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary of paper.**\n\nWe believe that there is a possible typo or misunderstanding in the summary written by the reviewer---our new calibration measure, $\\mathsf{SSCE}$, is obtained from the smooth calibration error ($\\mathsf{smCE}$) plus subsampling, rather than from the ECE plus subsampling.\n\n**Practical implications for lack of truthfulness.**\n\nLines 30--32 include an explanation of the practical importance of truthfulness: If a calibration measure is far from being truthful, the forecaster is incentivized to \"overfit\" to the measure rather than figuring out the exact distribution of the next outcome. In many cases, this leads to predictions that are far from the true probabilities, and would weaken the trustworthiness of the forecasts.\n\nFor practical impact of the lack of truthfulness on a toy example, our informal discussion and calculations in Lines 195--206 as well as the formal proofs in Appendices A.2 and A.3 indeed provide one such example. In short, we gave simple examples on which: (1) the \"right\" predictions lead to a large error of $\\Omega(\\sqrt{T})$ or $\\Omega(T)$; whereas: (2) a different strategy that frequently makes \"wrong\" predictions has a much lower error of $0$. The analyses of these examples are indeed simple and elementary and we believe they serve as good examples for demonstrating how lack of truthfulness can lead to highly biased and qualitatively poor predictions.\n\nWe can also numerically compute the example on Lines 195---206, say for $T = 1000$ timesteps.\nThe expected calibration error $\\mathsf{smCE}$ of truthful prediction (average over 100 seeds) is $11.27$; the $\\mathsf{smCE}$ of the dishonest prediction strategy is deterministically $0$.\nIn contrast, the subsampled smooth calibration error $\\mathsf{SSCE}$ of truthful prediction is $8.83$, while the $\\mathsf{SSCE}$ of the dishonest prediction strategy is $8.85$.\nThat is, the incentive to lie according to the dishonest strategy is near-zero under our proposed calibration error.\n\n\n**Difference between $\\mathsf{smECE}$ of [Blasiok-Nakkiran, ICLR'24] and the proposed $\\mathsf{SSCE}$.**\n\nWe thank the reviewer for pointing us to this calibration measure. We believe that the smooth ECE is qualitatively different from the SSCE, both in terms of their definitions and their truthfulness guarantees. At a high level, the definition of $\\mathsf{smECE}$ aims to mitigate the discontinuity of the ECE introduced by the binning; this is in a similar spirit to $\\mathsf{smCE}$. However, even after this smoothing, the measure still allows the forecaster to \"predict to the past\" in an effort to minimize their penalty. On the other hand, our definition of $\\mathsf{SSCE}$ introducing an additional amount of randomness by subsampling the horizon, so that the benefit from \"predicting to the past\" is minimized.\n\nIn more detail, in our proof of Proposition A.2, we give a distribution $\\mathcal{D}$ on which: (1) truthful prediction typically leads to an $\\Omega(\\sqrt{T})$ bias at value $1/2$; (2) a different forecasting strategy achieves perfect calibration. Property (2) implies that the optimal error is $\\mathsf{OPT}_{\\mathsf{smECE}}(\\mathcal{D}) = 0$. Property (1), with a simple calculation, shows that truthful prediction leads to an $\\Omega(\\sqrt{T})$ $\\mathsf{smECE}$ (if we scale up the definition in [BN24] by a factor of $T$). In other words, $\\mathsf{smECE}$ has a $0$-$\\Omega(\\sqrt{T})$ truthfulness gap.\n\n**Impact of subsampling on reliability diagrams.**\n\nWhile the visualization of miscalibration is beyond the scope of this work, we believe that existing methods for producing reliability diagrams (e.g., the one introduced by [BN24]) can easily accommodate the subsampling. It suffices to sample a few independent subsets of the time horizon and generate the reliability diagram corresponding to each subsampled set. Then, we can either stack these diagrams together, or plot the confidence intervals computed from these trials.\n\n**Definition in Lines 41--42.**\n\nWe thank the reviewer for the comment, and would like to explain our decision on the organization. The formal definition of truthfulness requires the introduction of many concepts (those in Definitions 2.3, 2.4 and 2.5)\nand thus is relegated to the Preliminaries section. However, we do have informal definitions and explanations in the introduction (with forward pointers to Section 2). We believe this allows the readers to choose their own pace, e.g., either reading the paper in order and gradually building on the formality of the definitions or jumping to formal definitions and back.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UeCuwJjnM2", "reviewer": "Reviewer_M6FP", "summary": "The paper studies calibration measures in a sequential prediction setup. In addition to rewarding accurate predictions (completeness) and penalizing incorrect ones (soundness), the paper formalizes another desideratum of calibration measures — truthfulness. A calibration measure is truthful if the forecaster (approximately) minimizes the expected penalty by predicting the conditional expectation of the next outcome, given the prior distribution of outcomes. \n\nThe paper first shows that the existing calibration measures fail to simultaneously meet all these criteria (completeness, soundness, truthfulness). The paper then proposes a new calibration measure — Subsampled Smooth Calibration Error (SSCE) — that is shown to be approximately truthful via a non-trivial analysis.", "questions": "please see above.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed truthfulness desideratum for the calibration measure is well-motivated. The authors have provided several rigorous technical results to support the need of the proposed calibration measure (SSCE), including the failure of being truthful of existing calibration measures. The analysis and the results are non-trivial.", "weaknesses": "The proposed Subsampled Smooth Calibration Error is essentially the expected of the smooth calibration error over the uniformly randomly selected events. This seems to be related to the definition of “Event-conditional unbiasedness” proposed in “High-Dimensional Prediction for Sequential Decision Making”. Could authors comment a bit on this connection?\n\nIt is a bit unclear on how to understand the truthfulness in an adversary setting, especially given that in Definition 2.5 (Truthfulness of calibration measures), it requires a distribution over the sequence of the events. It might be helpful to clarify here a bit.\n\nDoes the authors have intuitions on how the current results could be extended if one consider multi-outcome space, instead of being binary?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Connection to \"event-conditional unbiasedness\".**\n\nIn our view, the event-conditional unbiasedness in [Definition 2.3, NRRX23] is a strengthening of the notion of \"calibration with checking rules\" from [FRST11], where each checking rule specifies a subset of time horizon $[T]$ on which the calibration error is evaluated, as discussed in Lines 109--115. Roughly speaking, event-conditional unbiasedness allows each checking rule to be violated up to a degree commensurate with the number of steps that the checking rule applies to. Therefore, event-conditional unbiasedness, like the notion from [FRST11], is of an worst-case flavor as it takes the maximum over the event family. Note that taking the worst case over all $2^T$ events lead to vacuous guarantees due to the large number of events. On the other hand, our proposed notion of SSCE is qualitatively different as it is an average-case notion which takes the expectation over all subsets of the time horizon. \n\n**Truthfulness in an adversarial setting.**\n\nIn our view, the truthfulness is a property of a calibration measure, and is independent of whether the measure is used in a stochastic or adversarial setup. \nIntuitively, truthfulness requires that whenever the forecaster has additional side information about the next outcome, they should be encouraged to use it.\nOur current formulation focuses on the \"stochastic\" scenario where the outcome sequence $y_{1:T}$ is drawn from some prior distribution, and this prior distribution is provided to the forecaster as side information. In this case, the forecaster is able to calculate the ground-truth probability of the next outcome $y_t$ from the history $y_{1:t-1}$, and they should truthfully forecast this ground-truth probability. Arguably, this serves as a minimal condition of truthfulness.\n\nFollowing our methodology, truthfulness can be naturally defined in adversarial settings as well, which we discuss in Section 7. In the adversarial setting, the next outcome is selected by an adversary, which may depend on both the historical outcomes $y_{1:t-1}$ and the forecaster's previous predictions $p_{1:t-1}$. In this setting, truthfulness would require that whenever the adversary's strategy is provided to the forecaster as side information, they should use that information to truthfully predict the ground-truth probability of $y_t$ under this strategy.\n\n**Extension to multi-outcome spaces.**\n\nCentral to our current proofs are the analyses of concentration (specifically, uniform convergence over the Lipschitz class) and anti-concentration. So, we expect that the results can be extended to the multi-outcome spaces via the high-dimensional analogues of such results.\nWe agree that the exact analysis and the bounds on the truthfulness for multi-outcome spaces would indeed be an interesting direction for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HzSZeImGdm", "reviewer": "Reviewer_ZWFw", "summary": "The paper initiates the study of truthful calibration measures. It introduces a set of requirements --- truthfulness, completeness, soundness, and asymptotic calibration --- that together define a novel and fruitful set of requirements on calibration measures. It explores the classic sequential binary prediction setting, and proves in that setting both that (1) an entire array of existing calibration metrics fail to satisfy at least one of these requirements, and (2) that a simple novel metric called SSCE (which is a smooth and subsampled calibration measure) actually satisfies all of these, in particular being only a constant factor away from perfect truthfulness.", "questions": "Can you give some crude but reasonable constant bound on the truthfulness constant c of SSCE? If that is possible, along with an explanation of how this bounding propagates through the outlined proof, that might also serve as additional explanation of the proof pipeline for the reader.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper is in my opinion strong both on the modeling (principled definitions leading to nontrivial theory) and on the technical side.\n\nThe paper presents a new array of results that evaluate calibration measures under a new angle not explicitly considered before: truthfulness (along with several other dimensions that make this requirement nontrivial, as without further restrictions even constant measures can be truthful as the authors remark). It is very appealing that this work successfully tackles both sides of the issue — on the one hand, it carefully analyzes an entire array of existing (including recent) calibration measures and derives principled bounds showcasing their lack of (optimal) truthfulness, but it also proposes a novel — even if simple — calibration metric that “smooths out” lack of truthfulness in prior measures via subsampling. In this way, it presents a principled framework on which future work could build to both explore and exploit truthful calibrated elicitation.\n\nThe technique, with which the main result — O(1) truthfulness of SSCE — is derived, is quite impressive; despite a simple formulation, the proof requires a careful martingale-based argument which necessitates careful twists on standard concentration/anticoncentration/other measure-theoretic results. Based on familiarity with related work, I believe this complexity is fully justified even the “elementary” nature of the statement; and I concur with the authors that this technique may be useful for further work as well.", "weaknesses": "Overall, this is a strong paper. It is not a flaw per se given that this is the first paper to model the “truthful” setting — and thus any and all reasonable modeling assumptions are great to have at this stage — but the main question I am not fully certain about is: how principled is the fashion in which “soundness” — i.e. the property that “bad” predictions should lead to linear (in T) calibration measure value — is defined? Meaning, the requirements imposed (that predicting the complement of the truth, or consistently predicting a bias different from the true underlying bias, are both bad) seem necessary but possibly not sufficient to correspond to what may be viewed as “consistently bad predictions”. It would be great if the authors could shed further light on this. (On the other hand, the other dimensions of inquiry (truthfulness/completeness/asymptotic calibration), I would argue, are indeed defined in a very principled way.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Definition of soundness.**\n\nAt a high level, soundness mirrors the completeness and requires that intuitively bad predictions should result in a high calibration error. In this paper, we establish minimal conditions for soundness by considering two particular types of bad predictions, (1) predicting the complement of the true outcomes, and (2) making consistently biased predictions relative to the true mean of the product of Bernoulli distributions. We agree with the reviewer that these conditions are necessary but not sufficient, and that it is an important open direction to explore more principled definitions of soundness. For example, our second requirement can be naturally extended to multiple Bernoulli distributions with different means, where predictions are deemed \"bad\" if they consistently deviate from the true means.\nHowever, in our paper, we have chosen to focus on the simplest version, as none of the measures we examined seems to have a problem with soundness.\n\n**Constant factors.**\n\nWhile we prioritized simplifying the proof over optimizing the constant factors, these constants can be easily tracked. We emphasize that these constants are only for demonstrations and likely can be improved with more careful analysis: \n\n- From Theorem C.1 (Line 897), the ratio between the truthful predictor's expected SSCE and $\\mathbb{E}[\\gamma(\\text{Var}_T)]$ is upper bounded by $(48 + 8\\ln 2)\\cdot(2 + 2\\sqrt{2}) \\le 259$.\n\n- From the proof of Lemma 6.2 (Lines 1062, 1063 and 1073), the ratio between the the optimal forecaster's expected SSCE and $\\mathbb{E}[\\sqrt{N_T}]$ is lower bounded by $0.05\\cdot 2^{-7}\\cdot (1/2) = 1/5120$. We expect that this ratio can be improved using a more careful analysis of the case where $N_T$ is small.\n\n- From Lemma D.3 (Line 1167), the ratio between $\\mathbb{E}[\\sqrt{N_T}]$ and $\\mathbb{E}[\\gamma(\\text{Var}_T)]$ is lower bounded by $1/16$. \n\nAs a result, the ratio between the expected SSCE of the truthful forecaster and that of the optimal forecaster is upper bounded by $259\\cdot 5120\\cdot 16 \\le 2.2\\cdot 10^7$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wL1dj3AE2V", "reviewer": "Reviewer_NYRM", "summary": "The authors evaluate a variety of existing calibration measures according to their completeness, soundness, along with truthfulness which is their main focus, by theoretically showing how the measures satisfy these aforementioned criteria. They discover that existing measures, despite being complete and sound, have large truthfulness gaps. They introduce a new method, SSCE, that makes a simple modification of smooth calibration error by subsampling time steps, that is also approximately truthful and the authors provide proofs for this.", "questions": "- What are the main implications of adaptive adversary results? If a sublinear penalty for SSCE is achievable, how would it perform on average or in a typical use case? \n\n- The subsampling time steps technique is applied to smooth calibration error to improve its truthfulness. Can it be more generalized and applied to different calibration measures to improve their truthfulness? Discussing this could help shed light on the generalizability of the approach.", "limitations": "yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is the first systematic, theoretical investigation of the truthfulness of a range of calibration measures.  \n\n- Extensive and rigorous proofs are provided for all claims.  \n\n- The paper introduces a novel calibration measure, the Subsampled Smooth Calibration Error (SSCE), which is both complete and sound while also being approximately truthful.  The proposed SSCE has the potential to be widely used.", "weaknesses": "- Given your definition of truthfulness that you base your analysis on, is it consistent with what previous works have defined, and do other works stress the crucialness for this aspect of calibration? I’d like to see more discussion on related works tackling truthfulness in calibration and its importance, particularly to help establish why such an approach like SSCE should be used in practice in the future over ECE or proper scoring rules that have trade offs.  \n\n\n- Despite the introduction claims that Part III of the paper (about the adversarial setting and theorem 1.3) is one of the main contributions, it is not featured prominently in the rest of the main body of the paper, nor is much written about it, so it is difficult to ascertain its importance in the context of the work. It would be beneficial to discuss this more, as most of the paper is devoted to Part II. \n\n- The paper lacks many practical examples which can make it hard to follow at times, particularly when the formulation (of notions such as soundness) differs from previous works. It would be helpful to have more examples such as in [FRST11].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Related works tackling truthfulness.**\n\nAs we mention in the paragraph starting on Line 34, to the best of our knowledge, no prior work has systematically investigated or formally defined the notion of truthfulness. Instead, they observed the lack of truthfulness in certain calibration measures, and then used this observation towards the design of algorithms / hard instances for those specific measures. Lack of the systematic study and definition of truthfulness also came as a surprise to us! This is the reason we believe our work makes a compelling contribution to the study of calibration.\n\nFor the camera-ready version, we will add more details of how and where truthfulness has played a role in prior work.  At a high level,\nfor the ECE, [FH21, QV21] noted that the forecaster can lower their ECE by predicting according to the past. This observation was applied in the algorithm of [FH21] and motivated the \"sidestepping\" technique in the lower bound proof of [QV21]. For smooth calibration and distance from calibration, [QZ24] used their observation (that both measures can be made $\\mathrm{polylog}(T)$ on independent coin flips) as a justification for why a strong lower bound cannot be easily proved on a sequence of random bits.\n\n**Part III of the paper.**\nWe will use the extra page afforded by the camera-ready version to provide more details of Part III of our contributions. \nWe agree that (while the rest of the paper focuses on showing that the calibration measure we introduce, $\\mathsf{SSCE}$, satisfies desirable properties like truthfulness) it is also important to know whether there even exist forecasting algorithms that perform well with respect to our proposed measure, $\\mathsf{SSCE}$.\nThis is the purpose of Part III, where we show that---just as there exist algorithms guaranteeing $O(\\sqrt T)$ $\\mathsf{smCE}$---there is an algorithm guaranteeing $O(\\sqrt T)$ $\\mathsf{SSCE}$.\nAt a technical level, our proof here (specifically Theorem 1.3 as proved in Appendix F) uses a key step from prior work [ACRS24]. In particular, we combine their deterministic algorithm, which guarantees $O(\\sqrt{T})$ $\\mathsf{CalDist}$ (and thus $\\mathsf{smCE}$), with our Lemma F.1 that bounds the difference between $\\mathsf{smCE}$ and $\\mathsf{SSCE}$ via standard chaining techniques.\n\n\n**Implications of adaptive adversary results.**\n\nOne particular implication is: In terms of the optimal error, predicting against an adaptive adversary is as easy as predicting a sequence of independent coin flips---it is possible to get an $O(\\sqrt{T})$ $\\mathsf{SSCE}$ in the former case while, by our Theorem 6.1, the optimal error in the latter case is $\\Omega(\\sqrt{T})$. This is not the case for every calibration measure; for example, expected calibration error $\\mathsf{ECE}$ does not have this property. \nWe also note that Theorem 6.1 provides a $O(\\sqrt{T})$ bound on $\\mathsf{SSCE}$ in the worst-case; in nicer cases, one should achieve lower $\\mathsf{SSCE}$. \n\n**Apply subsampling to other measures.**\n\nWe believe that understanding the extent to which the subsampling more generally helps with truthfulness is an excellent direction for future work! While, applying this technique more broadly is beyond the scope of this work, let us say a bit more about what we already suspect. Due to the discontinuities of expected calibration error $\\mathsf{ECE}$ and maximum swap regret $\\mathsf{MSR}$, we believe it to be impossible for our technique of subsampling timesteps to imbue either of the two calibration measures with bounded truthfulness guarantees.\nOur current analysis might still apply though for calibration measures similar to smoothed calibration error but where the Lipschitz function class (see L488) is replaced with other function classes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this is a solid paper.
Decision: Accept (poster)