Truthfulness of Calibration Measures

Related works tackling truthfulness.

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

For 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, for 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.

Part III of the paper. We will use the extra page afforded by the camera-ready version to provide more details of Part III of our contributions. We 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}$. This 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}$. At 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.

Implications of adaptive adversary results.

One 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. We 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}$.

Apply subsampling to other measures.

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

Definition of soundness.

At 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. However, 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.

Constant factors.

While 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:

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

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

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

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

Connection to "event-conditional unbiasedness".

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

Truthfulness in an adversarial setting.

In 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. Intuitively, truthfulness requires that whenever the forecaster has additional side information about the next outcome, they should be encouraged to use it. Our 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.

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

Extension to multi-outcome spaces.

Central 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. We agree that the exact analysis and the bounds on the truthfulness for multi-outcome spaces would indeed be an interesting direction for future work.

Summary of paper.

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

Practical implications for lack of truthfulness.

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

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

We can also numerically compute the example on Lines 195---206, say for $T = 1000$ timesteps. The 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$. In 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$. That is, the incentive to lie according to the dishonest strategy is near-zero under our proposed calibration error.

Difference between $\mathsf{smECE}$ of [Blasiok-Nakkiran, ICLR'24] and the proposed $\mathsf{SSCE}$.

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

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

Impact of subsampling on reliability diagrams.

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

Definition in Lines 41--42.

We 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) and 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.