Smooth ECE: Principled Reliability Diagrams via Kernel Smoothing
Authors: Jaroslaw Blasiok
Preetum Nakkiran
Venue: ICLR 2024 poster (2024)
Keywords: calibration
reliability
ECE
theory
Primary area: general machine learning (i.e., none of the above)
TL;DR: A theoretically-principled construction of reliability diagrams, and a new associated calibration measure.

Abstract: Calibration measures and reliability diagrams are two fundamental tools for measuring and interpreting the calibration of probabilistic predictors. Calibration measures quantify the degree of miscalibration, and reliability diagrams visualize the structure of this miscalibration. However, the most common constructions of reliability diagrams and calibration measures --- binning and ECE --- both suffer from well-known flaws (e.g. discontinuity). We show that a simple modification fixes both constructions: first smooth the observations using an RBF kernel, then compute the Expected Calibration Error (ECE) of this smoothed function. We prove that with a careful choice of bandwidth, this method yields a calibration measure that is well-behaved in the sense of (Blasiok, Gopalan, Hu, and Nakkiran 2023) --- a consistent calibration measure. We call this measure the SmoothECE. Moreover, the reliability diagram obtained from this smoothed function visually encodes the SmoothECE, just as binned reliability diagrams encode the BinnedECE.   We also release a Python package with simple, hyperparameter-free methods for measuring and plotting calibration: "pip install relplot."
Code at: https://github.com/apple/ml-calibration

Published as a conference paper at ICLR 2024
SMOOTH ECE: PRINCIPLED RELIABILITY DIAGRAMS VIA KERNEL SMOOTHING
Jaroslaw Blasiok Columbia University
Preetum Nakkiran Apple
ABSTRACT
Calibration measures and reliability diagrams are two fundamental tools for mea- suring and interpreting the calibration of probabilistic predictors. Calibration mea- sures quantify the degree of miscalibration, and reliability diagrams visualize the structure of this miscalibration. However, the most common constructions of reli- ability diagrams and calibration measures- - binning and ECE- both suffer from well-known flaws (e-g. discontinuity). We show that simple modification fixes both constructions: first smooth the observations using an RBF kernel, then com- pute the Expected Calibration Error (ECE) of this smoothed function. We prove that with a careful choice of bandwidth, this method yields a calibration measure that well-behaved the sense of Blasiok, Gopalan, Hu, and Nakkiran (2023)- a consistent calibration measure. We call this measure the SmoothECE. Moreover, the reliability diagram obtained from this smoothed function visually encodes the SmoothECE, just as binned reliability diagrams encode the BinnedECE.
We also release a Python package with simple, hyperparameter-free methods for measuring and plotting calibration: 'pip install relplot'. Code at: htttps://gtten com/ apwpl//m-caalbrattttt
INTRODUCTION
Calibration is fundamental aspect of probabilistic predictors, capturing how well predicted prob- abilities of events match their true frequencies (Dawid, 1982). For example, a weather forecasting model is perfectly calibrated (also called "perfectly reliable")) if among the days it predicts 10% chance of rain, the observed frequency of rain is exactly 10%. There are two key questions in studying calibration: First, for given predictive model, how do we measure its overall amount of miscalibration? This is useful for ranking different models by their reliability, and determining how much to trust a given model's predictions. Methods for quantifying miscalibration are known as calibration measures. Second, how do we convey where the miscalibration occurs? This is useful for better understanding an individual predictor's behavior (where is likely to be over- vs. under- confident), well for re-calibration- modifying the predictor to make it better calibrated. The standard way to convey this information is known as a reliability diagram. Unfortunately. in ma- chine learning, the most common methods of constructing both calibration measures and reliability diagrams suffer from well-known flaws, which we describe below.
The most common choice of calibration measure in machine learning is the Expected Calibration Error (ECE), more specifically its empirical variant the Binned ECE (Naeini et al., 2015). The ECE is known to be unsatisfactory for many reasons; for example, it is discontinuous functional, so changing the predictor by an infinitesimally small amount may change its ECE drastically' (Kakade & Foster, 2008; Foster & Hart, 2018: Blasiok al., 2023). Moreover, the ECE is impossible to estimate efficiently from samples (Lee et al., 2022; Arrieta-Ibarra et al., 2022), and its sample- efficient variant, the Binned ECE, is overly sensitive to choice of bin widths (Nixon et al., 2019; Kumar et al., 2019; Minderer et al., 2021). These shortcomings have been well-documented in the community, which motivated proposals of new, netter-behaved calibration measures (e.g. Roelofs et al. (2022); Arricta-Ibarra et al. (2022); Lee et al. (2022)).
See Figure and Appendix E. for an illustration of this discontinuity.

---

Published as a conference paper at ICLR 2024
Binned Reliability
Smooth Reliability (ours)
1.0
1.0
EC 0.161
SmECE 0.138 0.016
0.8
0.8
0.4
0.2
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.2
0.6
0.8
1.0
f
f
Figure 1: Left: Traditional reliability diagram based on binning, which is equivalent histogram regression. Right: Proposed reliability diagram based on kernel regression, with our theoretically- justified choice of bandwidth. The width of the red line corresponds to the density of predictions, and the shaded region shows bootstrapped confidence intervals. Plot generated by our Python package.
Recently, Blasiok et al. (2023) proposed a theoretical definition of what constitutes a "good" cali- bration measure. The key principle is that good measures should provide upper and lower bounds on the calibration distance dCE, which is the Wasserstein distance between the joint distribution of prediction-outcome pairs, and the of perfectly calibrated such distributions (formally defined in Definition 5 below). Calibration measures which satisfy this property are called consistent calibra- tion measures. In light of this line of work, one may think that the question of which calibration measure to choose is largely resolved: simply pick consistent calibration measure, such as Laplace Kernel Calibration Error / MMCE (Blasiok et al., 2023; Kumar al., 2018), as suggested by Blasiok et al. (2023). However, this theoretical suggestion belies the practical reality: Binned ECE remains the most popular calibration measure used in practice, even in recent studics. We believe this is partly because Binned ECE enjoys an additional property: it can be visually represented by spe- cific kind of reliability diagram, namely the binned histogram. This raises the question of whether there are calibration measures which are consistent in the sense of Blasiok et al. (2023), and can also be represented by an appropriate reliability diagram. To be precise, we must discuss reliability diagrams more formally.
Reliability Diagrams. We consider measuring calibration in the setting of binary outcomes, for simplicity. Here, we have joint distribution (f.y) D over predictions [0, 1], and true outcomes E {0, 1}. We interpret f as the predicted probability that = 1. The "calibration function" p:: [0, 1] + [0, is defined the conditional expectation:
m(f) E(y fl.
A perfectly calibrated distribution, by definition, is one with diagonal calibration function: p(f) f. Reliability diagrams are traditionally thought of estimates of the calibration function μ (Naeini et al., 2014; Bröcker, 2008). In other words, reliability diagrams are one-dimensional regression methods, since the goal of regressing y on f exactly to estimate the regression function Efy f). The practice of "binning" to construct reliability diagrams (as in Figure left) can be equivalently thought as using histogram regression to regress on
With this perspective on reliability diagrams, one may wonder why histogram regression is still the most popular method, when more sophisticated regressors are available. One potential answer is that users of reliability diagrams have additional desiderata: it should be easy to visually read off reasonable calibration measure from the reliability diagram. For example, is easy to visually read off the Binned ECE from a binned reliability diagram, because it is simply the integrated absolute deviation from the diagonal:
BinnedECCE, = -f. (
2

---

Published as a conference paper at ICLR 2024
where k is the number of bins, f is the histogram regression estimate of y given f, and je is the "binned" version of f - formally the histogram regression estimate of given f. This relationship is even more transparent for the full (non-binnets ECE, where we have
ECE 1 1OCE=f.r
fl dF = -ad===lll Ellu(f) fl]
where jr is the true regression function as above. However, more sophisticated regression methods do not neccesarily have such tight relationships calibration measures. Thus we have situation where better calibration measures exist, but they are not accompanied by reliability diagrams, and conversely better reliability diagrams exist (i.e. regression methods), but they are not associated with consistent calibration measures. We address this situation here: we present new consistent calibration measure, SmoothECE, along with regression method which naturally encodes this cali- bration measure. The SmoothECCI is, per its name, equivalent to the ECE of a "smoothed" version of the original distribution, and the resulting reliability diagram can thus be interpreted as smoothed estimate of the calibration function.
We emphasize that the idea of smoothing is not new - Gaussian kernel smoothing has been ex- plicitly proposed as method for constructing reliability diagrams in the past (e.g. Bröcker (2008), as discussed in Arricta-Ibarra et al. (2022)). Our contribution is two-fold: first, we give strong the- oretical justification for kernel smoothing by proving it induces consistent calibration measure. Second, and of more practical relevance, we show how to chose the kernel bandwidth in a principled way, which differs significantly from existing recommendations.
1.1 OVERVIEW OF METHIO
We start by describing the regression method, which defines our reliability diagram. We are given i.i.d, observations ((1,31); ), (/2,3/2 ... (Jk: yt)} where fi E [0. 1] the i-th prediction, and ys E {0, 1) is the corresponding outcome. For example, if we are measuring calibration of an ML model on a dataset of validation samples, we will have fo = F(z,) for model F evaluated on sample 24, with ground-truth label yı- We would like to estimate the true calibration function juf) == Rff y]- Our estimate jf(()) is given by Nadaraya- -aataan Watson kernel regression (kernel smoothing) on this dataset (see Nadaraya (1964); Watson (1964); Simonoff (1996)):
A()) = K.Ko Ko (J. K.
(1)
That is, for a given / E [0, 1] our estimate of y is the weighted average all y,, where weights are given by the kernel function K2 (f.f.) fi). The choice of kemnl,, and in particular the choice of band- width o, is crucial for our method's 's theoretical guarantees. We use an essentially standard kernel (defined formally in Section 3): the Gaussian Kernel, reflected appropriately
handle boundary- effects of the interval [0, 1]. Our choice of bandwidth a is more subtle, but it is not a hyperparameter we describe the explicit algorithm for choosing o in Section 3. suffices say for now that the amount of smoothing a will end up being proportional to the reported calibration error.
Reliability Diagram We then construct reliability diagram in the standard way, by displaying plot of the estimated calibration function á along with a kernel density estimate of the predictions Ji (see Figure 1). These two estimates, compactly presented the same diagram, provide tool to quickly understand and visually assess calibration properties of a given predictor. Moreover, they can be used define a quantiative measure of overall degree of miscalibration, as we show below.
SmoothECE A natural measure of calibration can be easily computed from data in the above reliability diagram. Specifically, let 8(f) be the kernel density estimate of predictions: 8(f) == E. (f f.). Then, similar to the definition of ECE, we can integrate the deviation of á from the diagonal to obtain:
smECE, := / [I(C0)
tlb(t)dtt ((((t)))((t)dtt.
3

---

Published as a conference paper at ICLR 2024
The measure of calibration actually propose in Section 3, SmECE, is closely related but not identical to the above. Briefly, to define SmECE, we consider the kernel smoothing of the dif- ference between the outcome and the prediction (y:: fi) instead of just smoothing the outcomes Vs- As turns out, those choices lead to a calibration measure with better mathematical proper- ties: SmECE, is monotone decreasing as the kernel bandwidth is increased, and SmECE, at specific bandwidth choice and applied to the population distribution, is O for perfectly calibrated predictors.
We reiterate that the choice of the scale a is very important: too large or too small bandwidth will prevent the SmoothECE from being consistent calibration measure. In Section we will show how to algorithmically define the correct scale o². For the reliabilitt diagram, we suggest presenting the estimates ò and with the same scale o", and for this scale we indeed have SmECE,- s smECE,- (see Appendix A). Finally, note that we have been discussing finite-sample estimators of all quantities; the corresponding population quantities are defined analogously in Section 3.
1.2 SUMMARY OF OUR CONTRIBUTIONS
1. SmoothECF. We define new hyperparmeter-free calibration measure, which we call the SmoothECE (abbreviated smECE). We prove that the SmoothECE a consistent calibra- tion measure, in the sense of Blasiok et al. (2023). It also corresponds to natural notion of distance: if SmoothECE e, then the function f can be stochastically post-processed to make it perfectly calibrated, without perturbing f by more than E in L1.
2. Smoothed Reliability Diagrams. We show how to construct principled reliability di- agrams which visually encode the SmoothECE. These diagrams can be thought of as "smoothed" versions of the usual binned reliability diagrams, where we perform Nadaraya- Watson kernel smoothing with the Gaussian kernel.
3. Code. We develop a Python package which computes the SmoothECE and plots the asso- ciated smooth reliability diagram (link omitted for anonymity). hyperparameter-free efficient, and includes uncertainty quantification via bootstrapping. We include several experiments in Section 4, for demonstration purposes.
4. Extensions to general metries. On the theoretical side, investigate how far con- struction of SmoothECE generalizes. We show that the notion of SmoothECE introduced in this paper can indeed be defined for wider class of metrics the space of predictions [0, 1]. and we prove the appropriate generalization of our main theorem: that the SmECE for given metric is a consistent calibration measure with respect the same metric. Fi- nally, perhaps surprisingly, we show that under specific conditions on the metric (which are satisfied, for instance, by the diogit metric), the associated SmECE is in fact consistent calibration measure with respect to & metric.
Organization. We begin by discussing the closest related works (Section 2). In Section 3 formally define the SmoothECE and prove its mathematical and computational properties. To aid intuition, we discuss the justification behind our various design choices in Appendix A. We then prove the SmoothECE can be estimated efficiently with respect to both sample-complexigg and run- time (Section 3.4). Finally, we include experimental demonstrations of our method in Section 4, and conclude in Section 5. Extensions of our results to more general metrics are provided in Ap- pendix B.
RELATED WORKS
Reliability Diagrams and Binning, Reliability diagrams, as far as we are aware, had their origins in the early reliability tables constructed by the meteorological community (Hallenbeck, 1920). These early accounts of calibration already applied the practice of binning- discretizing predictions into bins, and estimating frequencies conditional on each bin. Plots of these tables turned into binned reliability diagrams (Murphy & Winkler, 1977; DeGroot & Fienberg, 1983), which was recently popularized in the machine learning community by a series of works including Zadrozny & Elkan (2001); Niculescu- Mizil & Caruana (2005); Guo et al. (2017). Binned reliability diagrams continue to be used in studies of calibration in deep learning, including in the GPT-4 tech report (Guo et al., 2017; Nixon al., 2019; Minderer al., 2021; Desai & Durrett, 2020; OpenAl, 2023).
4

---

Published as a conference paper at ICLR 2024
Reliability Diagrams Regression. The connection between reliability diagrams and regression methods has been noted in the literature (e.g. Bröcker (2008); Copas (1983); Stephenson et al. (2008)). For example, Stephenson et al. (2008) observes "one can consider binning be crude form of non-parametric smoothing." However, we remind the reader of a subtlety: our objective in this work is not identical to the regression objective, since we want estimator that is simultane- ously a reasonable regression and a consistent calibration measure. Our choice of bandwidth must thus carefully balance the two; cannot be simply be chosen to minimize the regression test loss.
Alternate Constructions. There have been various proposals to construct reliability diagrams which improve on binning, we mention several of them here. Many proposals can be seen as suggesting alternate regression techniques. to replace histogram regression. For example, some works suggest modifications to improve the binning method, such as adaptive bin widths or debiasing (Kumar et al., 2019; Nixon et al., 2019; Roelofs et al., 2022). These are closely related to data-dependent histogram estimators in the statistics literature (Nobel, 1996). Other works suggest using entirely different regression methods, including spline fitting (Gupta et al.), kernel smoothing (Bröcker, 2008; Popordanoska et al., 2022), and isotonic regression (Dimitriadis et al., 2021). The above methods for constructing regression- -assed reliability diagrams closely related to methods for calibration, since the ideal recalibration function is exactly the calibration function μ.. For example, isotonic regression (Barlow, 1972) has been used as both for recalibration (Zadrozny & Elkan, 2002; Naeini et al., 2015) and for reliability diagrams (Dimitriadis et al., 2021). Finally, Tygert (2020) and Arrieta-Ibant aeberr al. (2022) suggest visualizing reliability via numulative-distributiin plots. instead of estimating conditional expectations, While all the above proposals do improve upon binning in certain aspects, none of them ultimately induce consistent calibration measures in the sense of Blasiok et al. (2023). See Blasiok et al. (2023) for further discussion on the shortcomings of these measures.
Multiclass Calibration. We focus on binary calibration in this work. The multi- ceals- setting intro- duces several new complications- foremost, there no consensus on how best to define calibration measures in the multi-class setting; this is an active area of research (e.g. Vaicenavicius et al. (201 9); Kull et al. (2019); Widmann et al. (2020)). Howevever, our methods apply directly to any of the met- rics induced by the caattillass-t--bnaryy reductions of Gupta & Ramdas (2021), because these are determined by the standard calibration a related binary problem. This includes, for example, the multi-class confidence calibration.
Consistent Calibration Measures. We warn the reader that the terminology of consistent calibra- tion measure does refer the concept of statistical consistency. Rather, refers the definition introduced in Blasiok et al. (2023), to capture calibration measures which polynomially approximate the true (Wasserstein) distance to perfect calibration.
SMOOTH ECE
In this section we will define the calibration measure smECE. As it turns out, it has slightly better mathematical properties than SmECE defined Section 1.1, and those properties will allow us to chose the proper scale in more principled way moreover, we will be able to relate SmECE with SmECE.
Specifically, the measure SmECE, enjoys the following convenient mathematical properties, which we will prove in this section.
The SmECE, is monotone decreasing as we increase the smoothing parameter ø.
If D is perfectly calibrated distribution, then for any we have SmECE, (D) Indeed, for any a we have SmECE, (D) < ECE(D).
The smECE, is Lipschitz with respect to the Wasserstein distance on the space of distri- butions over 00, 1] x {0, 1}: for any D,, D, we have |sMECE, (D,) smE) S -
D2). This implies SmECE, < (1 + - )CCE(D).
For any distribution D and any a, there is (probabilistic) prot-pproessing K, such that if (ff. 3) ~ D. then the distribution D' of (x())), y) is perfectly calibrated, and moreover EE | x(f) & smECE, a. In particular dCF(D) smECE,
5

---

Published as a conference paper at ICLR 2024
a "reflected" version of the Gaussian kernel defined as follows. Let R IR + [0. 1] be the projection function which is identity on [0, 1], and collapses two points iff they differ by composition of reflections around integers. That is ι (2)) == (xr mod 2) if (ar mod 2) S 1, and (2 (x: mad 2)) otherwise. The Reflected Gaussian kernel [0 with scale o, is then given by
Reflected Gaussian Kernel. In all of our kemel applications,
Ko (2, =
Σ
o y)
Σ
d - 11),
(2)
BERR (x)
BEAR (v)
where @ is the probability density function of (O, 1), that is on (1) = use the Reflected Gaussian kernel in order alleviate the bias introduced by standard Gaussian kernel near the boundaries of the interval [0, 1].
/V2m222 We
3.1 DEFINING SMECE, AT SCALE
We now present the construction SmECE,, at a given scale a > 0. We will show how to pick
this in the subsequent section. Let D be distribution over [0, 1] {0, 1) of the pair of prediction
f E [0, 1] and outcome y E {0, 1}. For a given kernel K R - R we define the kernel smoothing of the residual y f as
( EULYDD f)
(3)
BLADDD (1,,)
This differs from the definition in Section 1.1, where we applied the kernel smoothing to the out- comes y instead. In many cases of interest, the probability distribution
going be an empirical probability distribution over finite set of pairs {(fi, y;)} of observed predictions ʃa and associated observed outcomes y/- In this case, the rD(() just weighted average of residuals (Ji w) where the weight of a given sample is determined by the kernel K(fi, t). This is equivalent to the Nadaraya- Watson kernel regression (a.k.a, a. kernel smoothing. see Nadaraya (1964); Watson (1964); Simonoff (1996)), estimating (y f) with respect the independent variable f.
We consider also the kernel density estimation 80, EL K(L,)) f). The SmECEx is now defined as
SmECE (D) =
(4)
This notion is close ECE of a smoothed distribution of (f, in sense which can be formalized (see Appendix A). For now, let us discuss the intuitive connection. For any distribution of prediction, and outcome (f, v), consider an expected residual r(() Ef ylf t). then
ECE(f. v) == / |r(t) (ty(t).
where j is measure of f. We can compare this with (4), where the conditional residual has been replaced by its smoothed version f, and the measure J4y has been replaced by d the measure of f + 17 for some noise 17. Equation (4) can be simplified by using the definitions of åp, and PD.K,
/ T k(t,f)( - f) dt. 1
SmECE (D) =
(5)
In what follows, we will be focusing on the reflected Gaussian kernel with scale o, KN and we shall use shorthand SmECE, to denote SmECE, KN.." We will now show how the scale a is chosen.
3.2 DEFINING SMECE: PROPER CHOICE OF SCALE
First, we observe that SmECE, satisfies a natural monotonicity property: increasing the smoothing scale decreases the SmECE,, (Proof of this and subsequent lemmas can be found in Appendix D.)
Lemma 1. For a distribution over [0, 1] x f0, 1} and 01 S a2 we have
smECE,, (D) 2 SMECE,; (D)-

---

Published as a conference paper at ICLR 2024
Several of our design choices were crucial to ensure this property: the choice of the reflected Gaus- sian kernel, and the choice to smooth the residual (y - as opposed to the outcome y. Note that since SmECE, (D) [o, 1], and for given predictor D, the function H SmECE, is increasing function of a, there is unique a² s.t. SmECE,- =a" (and we can find it efficiently using binary search). Thus
define:
Definition 2 (SmoothECF). We define SmECE(D) to be the unique o² satisfying SmECE, (D)
a². We also write this quantity as SMECE. for clarity.
3.3 SMECE A CONSISTENT CALIBRATION MEASURE
We will show that d, defined in the previous subsection is convenient scale which the SmECE of ID should be evaluated. The formal requirement that smECE, meets is captured by the notion of consistent calibration measure, introduced in Blasiok et al. (2023). We provide the definition below, but before we do, let us recall the definition of the Wasserstein metric.
For metric space (X,d), let consider ( be the space of all probability distributions X. We define the Wasserstein metric on the space A(X) (sometimes called earth-movers distance) Peyré al. (2019).
Definition 3 (Wasserstein distance). For two distributions J4, E ((X) we define the Wasserstein distance
Wilu, inf E d(a, v),
(ET(U.)) (2.9)r<
where T( v) is the family of all couplings of distributions μ and
Definition 4. A probability distribution 'D over [0, x {0,1} of prediction J and outcome y is perfectly calibrated if [D[yy]]] f. We denote the family of all perfectly calibrated distributions by P c. A(OO, 1] {0, 1)).
Definition 5 (Consistent calibration measure (Blasiok et al., 2023)). For probability distribution define the distance to calibration dCF(D) to be the Wasserstein distance to the nearest perfectly calibrated distribution, associated with metric d on [0, 1] x {0, 1} which puts two disjoint intervals infinitely far from each other.
D over [0, x {0.
Concretely
d((fi. (f2. = 11/- - f2l
in = 1/2 otherwise
and
aCE(D)
inf Wi (D, DEP
Finally, any function assigning to distributions over [0, 1] x (0. 1} a non-negative real calibration score, called consistent calibration measure if is polynomially upper and lower bounded by dCE, iee. there are constants Cı2 C22 O11, 02 s.f.
dCdCEDD) ((D) (D)
With this definition in hand, we prove the following.
Theorem 6. The measure (MECE(D) is consistent calibration measure.
This theorem is consequence of the following two inequalities. First of all, if we add the penalty proportional the scale of noise a, then SmECE, upper bounds the distance calibration.
Lemma 7. For any o. we have
dCE(D) S smECE, (D) +a.
On the other hand, as soon as the scale of the noise is sufficiently large compared to the distance to calibration, the smECE of predictor itself upper bounded as follows.
Lemma 8. Let (f. v) be any predictor: Then for any have
1 dCE(D).
smECE, (D) s

---

Published as a conference paper at ICLR 2024
In particular i 2 (D), then
SMECE, S 2 dCE(D).
This lemma, together with the fact that + SmECE, is non-increasing, directly implies that the fixpoint satisfies o < 2, P2/CE(() On the other hand, using Lemma 7, at this fixpoint we have dCE(D) S smECE, (D) 2xr.. That
dCE(D) SMECE. < 2 dCE(D),
proving the Theorem
3.4 SAMPLE AND RUNTIME EFFICIENCY
Here we prove that our method is efficient with respect to both sample complexity and runtime. We want to estimate SmECE of the underlying distribution 'D over [0, 1] {0, 1), using samples from this distribution. Specifically, let us sample independently at random m pairs (fi, ~ DD and let us define D to be the empirical distribution over the multiset {(f.. ys that is, to sample from D, pick uniformly random [m]] and output (fi, yc). Then, the plug-in estimator satisfies the following generalization bound.
2, then with probability at least 2/3 over the choice of independent random sample (fi, th (with (fr. ~ D), we have sinultanously for all a 2 do-
Theorem 9. For a given do > 0 mf 2 J0'E E-2,
|mEEEE (D) - smECE, (D) S.
In particular if SmECE, > On. then (with probability at least 2/3) we have |sMECE, (D) (D)) S.
The proof is in Appendix D.6. The success probability 2/3 can be amplified arbitrarily in the standard way, by taking the median of independent trials. Finally, clear that SmECE can be computed efficiently, by using the Fast Fourier Transform for convolutions. For completeness, in Appendix C we show that SmECE can be approximated up error in time O(n log + M loge log 3/2 M) in the RAM model, where A = 111
4 EXPERIMENTS
We include several experiments demonstrating our method on public datasets in various domains, from deep learning to meteorology. The sample sizes vary between several hundred 50K, show how our method behaves for different data sizes. In each setting, we compare the classical binned reliability diagram the smooth diagram generated by our Python package. Our diagrams include kernel density estimates of the predictions (at the same kernel bandwidth o* used to compute the SmoothECE). For binned diagrams, the number bins is chosen to be optimal for the regression test MSE loss, optimized via cross-validation.
Deep Networks. Figure 2a shows the confidence calibration of ResNet32 (He et al., 2016) on the ImageNet validation set (Deng et al., 2009). ImageNet an image classification task with 1000 classes, and has validation set of 50,000 samples. In this multi-class setting, the model outputs a distribution over = 1000 classes, f X Ak. Confidence calibration is defined as calibration of the pairs (argmax fe(x) [ff(x) v)), which is distribution over [0, 1] x (0. 1). That is, confidence calibration measures the agreement between confidence and correctness of the predictions. We use the publicly available data from Hollemans (2020), evaluating the models trained by Wightman (2019).
Solar Flares. Figure 2b shows the calibration of method for forecasting solar flares, over pe- riod of 731 days. We use the data from Leka et al. (2019), which was used to compare reliability diagrams in Dimitriadis et al. (2021). Specifically, we consider forecasts of the event that class
8

---

Published as a conference paper at ICLR 2024
BinnsECC
SmoothEC (Curs)
RisnedECE
SmoothECE (Ours)
1.
<03322: a.33
-8337
0.0
3.3
0.2
66
0.8
1o
0.0
64
3.6
1.0
0.
(a) ResNet33 on ImageNet.
(b) Solar flare forecasts.
UtnnedECCC
SmoothlCC (Cum)
ImmneDCC
SmoothOCC (Curs)
113 -1134
axtidd 01332 1UBe
1. -115
SuACE: rase exds
0.90
By 17
3.3
022
022
155
1.0
64
1.0
TT
de
(c) Rain forecasts in Finland.
(d) Synthetic data.
Figure 2: Comparison of binned reliability diagrams and our proposed smooth reliability diagrams, on several demonstration datasets.
C1.0+ solar flare occurs on given day, made by the DAFFS forecasting model developed by North- West Research Associates. Overall, such solar flares occur on 25.7% of the 731 recorded days. We use the preprocesssed data from the replication code at: https: htss://giitnn /githab......... com/ com/TimoDe TetoTiimDDiii iimi/ replic catt ion_DGG20. For further details of this dataset, we refer the reader to Dimitriadis et al. (2023, Section 6) and Leka et al. (2019).
Precipitation in Finland. Figure 2c shows the calibration of daily rain forecasts made by the Finnish Meteorological Institute (FMI) in 2003, for the city of Tampere in Finland. Forecasts made for the probability that precipitation exceeds 0. 0.2mm over a 24 hour period; the dataset includes records for 346 days (Nurmi, 2003).
Synthetic Data. For demonstration purposes, we apply our method to a simple synthetic dataset in Figure 2d. One thousand samples ft E [0, 1] are drawn uniformly in the interval [0, 1]. and the conditional distribution of labels Eiy; fa] is given by the green line in Figure 2d. Here, instead of kernel density estimates, show bootstrapped confidence bands around estimated regressor. Note that the true conditional distribution is non-monotonic in this example.
Limitations. One limitation of our method is that since it is generic, there may be better tools use in special cases, when we can assume more structure in the prediction distributions. For example, if the predictor is known to only output small finite set of possible probabilities, then it reasonable to simple estimate conditional probabilities by using these points as individual bins. The rain forecasts in Figure 2c have this structure, since the forecasters only predict probabilities in multiples 10% in such cases, using bins which are correctly aligned is a very reasonable option.
CONCLUSION
We have presented method of computing calibration error which is both mathematically well- behaved (i.e. consistent the sense of Blasiok et al. (2023)), and can be visually represented in a reliability diagram. We also released python package which efficiently implements our suggested method. We hope this work aids practitioners in computing, analyzing, and visualizing the reliability of probabilistic predictors.

---

Published as a conference paper at ICLR 2024
REFERENCES
Imanol Arrieta-lbarra, Paman Gujral, Jonathan Tannen, Mark Tygert, and Cherie Xu. Metrics of calibration for probabilistic predictions. arXiv preprint arXiv:2205. 09680, 2022.
R.E. Barlow. Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression. Wiley Series in Probability and Mathematical Statistics. 1972. ISBN 9780608 163352.
Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of dis- tance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Com- puting, pp. 1727-1740, New York, NY, USA, 2023, Association for Computing Machinery. ISBN 9781450399135.
Jochen Bröcker. Some remarks the reliability of categorical probability forecasts. Monthly weather review, 136(1 ((111):448845465 2008
Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. When does optimizing proper loss yield calibration?, 2023.
JB Copas. Plotting against x. Applied statistics, pp. 25-31, 1983.
A Philip Dawid, The well well-caaibrated bayesian. Journal of the American Statistical Association, 77 (379):605-616 1982.
Morris H DeGroot and Stephen E Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series D) (The Statistician), 32(1-2):12-22, 1983.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scall scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 245. leee, 2009.
Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 295- 302, 2020.
F. R. Deutsch and P. H. Maserick. Applications of the hahn-banach theorem in approximation theory. SIAM Review, 93)):116-530, 1967. ISSN 00361445. URL http::/wwe jstor. org/stable stsssablee2000 20279994.
Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high- dimensional gaussians with the same mean, 2018.
Timo Dimitriadis, Tilmann Gneiting, and Alexander I Jordan. Stable reliability diagrams for proba- bilistic classifiers. Proceedings of the National Academy of Sciences, 118(8):20016111118 2021.
Timo Dimitriadis, Tilmann Gneiting, Alexander Jordan, and Peter Vogel. Evaluating probabilistic classifiers: The triptych. arXiv preprint arXiv:230J.1088) 2023.
Dean P. Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynam- ics. Games Econ. Behav, 109:271-293, 2018. URL http:: http://odoooo.....o//// j....b........///
2017. 2017.12.00 022.
Parikshit Gopalan, Michael P Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multicalibra- tion. In Conference on Learning Theory, pp. 3193-3234. PMLR, 2022.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference Machine Learning, pp. 1321-1330. PMLR, 2017.
Chirag Gupta and Aaditya Ramdas. Top-label calibration and preprint arXiv:2 arXiv:2107.083355 107.00833. 2021.
binary reductions. arXiv
Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchisescu, and Richard Hartley. Calibration of neural networks using splines. International Conference Learning Representations.
10

---

Published as a conference paper at ICLR 2024
Cleve Hallenbeck. Forecasting precipitation in percentages of probability. Monthly Weather Review, 48(11):645 647, 1920.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Matthijs Hollemans.
Reliability diagrams.
https://giituub.com//bo...
seliability-diant
2020.
Sham Kakade and Dean Foster. Deterministic calibration and nash caciibbruuum.uurre of Computer and System Sciences,
2008.
Meelis Kull, Miquel Perello-Nieto, Markus Kängsepp. Hao Song, Peter Flach, al. Beyond temper- ature scaling: Obtaining well-calibrated multiclass probabilities with dirichlet calibration. arXiv preprint 1tt.::1990.225600 2019.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, pp. 3792-3803, 2019.
Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kernel mean embeddings. In International Conference on Machine Learning, pp. 2805- 2814. PMLR, 2018.
Donghwan Lee, Xinmeng Huang, Hamed Hassani, and Edgar Dobriban. T-cal: An optimal test for the calibration of predictive models. arXiv preprint arXiv:2203.0188 220.00185, 2022.
KD Leka, Sung-Hong Park, Kanya Kusano, Jesse Andries, Graham Barnes, Suzy Bingham, Shaun Bloomfield, Aoife E McCloskey, Veronique Delouille, David Falconer, et al. A comparison of flare forecasting methods. ii benchmarks, metrics, and performance results for operational solar flare forecasting systems. The Astrophysical Journal Supplement Series, 243(2):36, 2019.
Matthias Minderer, Josip Diolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. Advances in Neural Information Processing Systems, 34:15682 -5699 2021.
Allan H Murphy and Robert L. Winkler. Reliability of subjective probability forecasts of precipita- tion and temperature. Journal of the Royal Statistical Society Series C: Applied Statistics, 26(1): )): 41 41-47, 1977.
E. A. Nadaraya. On estimating regression. Theory of Probability & Its Applications, 91):141-142, 1964. doi: 10.1137/1109020 URL https::///// /oi.
Mahdi Pakdaman Nacini, Gregory F Cooper, and Milos Hauskrecht. Binary classifier calibration: Non-parametric approach. arXiv preprint 1rXiv:/401.3331 2014.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the... AAAI Conference Artificial Intel- ligence. AAAI Conference on Artificial Intelligence, volume 2015, pp. 2901. NIH Public Access, 2015.
Alexandru Niculescu- Mizil and Rich Caruana. Predicting good probabilities with supervised Iearn- ing. In Proceedings of the 22nd international conference on Machine learning, pp. 625-632. ACM, 2005.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measur- ing calibration in deep learning. In CVPR Workshops, volume 2, 2019.
Andrew Nobel. Histogram regression estimation using data-dependent partitions. The Annals of Statistics, 1483)-0044 1996.
Pertti Nurmi. Verifying probability of precipitation an example from finland. https: //www. wewcr.gev..u//profeetee. f potp html, 2003.

---

Published as a conference paper at ICLR 2024
OpenAl. Gpt-4 technical report, 2023.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ Machine Learning, 166-6))355-607, 2019.
Teodora Popordanoska, Raphael Sayer, and Matthew Blaschko. A consistent and differentiable Ip canonical calibration error estimator. Advances in Neural Information Processing Systems, 35: 7933-7946, 2022.
Rebecca Roelofs, Nicholas Cain, Jonathon Shlens, and Michael C Mozer. Mitigating bias in cali- bration error estimation. International Conference on Artificial Intelligence and Statistics, pp. 4036-4055 PMLR, 2022.
J.S. Simonoff. Smoothing Methods in Statistics. Springer Series in Statistics. Springer, 1996. ISBN 9780387947167. URL https: /books. google.. com/books http:/booksidddwfaogeed Pid==FIgNXI4 feIc. feIc.
David B Stephenson, Caio AS Coelho, and lan T Jolliffe. Two extra components in the brier score decomposition. Weather and Forecasting, 23(4):752-757, 2008.
Mark Tygert. Plots of the cumulative differences between observed and expected values of ordered bernoulli variates. arXiv preprint arXiv:2006602204, 2020.
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration classification. In The 22nd International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2019.
Geoffrey S. Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series (1961-2002), 26(4)3359-372, 1964. ISSN 0581572X. URL http: /wwww jww.r.sstrroooo stable/25049344
Nik Weaver. Lipschitz Algebras. WORLD SCIENTIFIC, 2nd edition, 2018. doi: 10.1 142/9911.
URL https: /tttps::/www... http:///wwwwwwwwcseeeeeoooooo.ee www.dscientiiiiccccccc...c.....e com/ doi /oi/abs// ///./1..1101 11l.1114/9999
David Widmann, Fredrik Lindsten, and Dave Zachariah. Calibration tests beyond classification. In International Conference on Learning Representations, 2020.
Ross Wightman. Pytorch image models.
https: http::////gthhbb..om//r/iigg
pytorch- wetorch-imagg--e image-modell 2019.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In leml, volume 1, pp. 199-616. Citeseer, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowl- edge discovery and data mining, pp. 694-699, ACM, 2002.
A DISCUSSION: DESIGN CHOICES
Here we discuss the motivation behind several design choices that may a-priori seem ad-hoc. In particular, the choice smooth the residuals ft) when computing the SmECE, but to smooth the outcomes directly when plotting the reliability diagram.
For the purpose of constructing the reliability diagram, it might be tempting to plot function (f()) == f(f) + (of smoothed residual as defined in (3), shifted back by the prediction f), as well as the smoothed density ô(t), as in the definition of SmECE. This is fairly reasonable approach, unfortunately has a particularly undesirable feature there is no reason for yt(t) = f(t) + to be bounded in the interval [0, 1]. It is therefore visually quite counter-intuitive, the plot of y(t) is supposed to be related with our guess on the average outcome y given (slightly noisy version of) the prediction l.
12

---

Published as a conference paper at ICLR 2024
As discussed in Section 1.1, we instead consider the kernel regression on y, as opposed to the kemell regression on the residual y J. and plot exactly this, together with the density 8. Specifically, let us define
ÚD.K (1) = EyaDD K (L,, J'y
(6)
Eyy=D (t,
and chose the reliability diagram a plot of a pair of functions + (() and / + 6D (1) the first plot is our estimation (based on the kernel regression) of the outcome for a given prediction the other is the estimation of the density of prediction As discussed in the Section 1.1, will focus specifically on the kernel K being the reflected Gaussian kernel, defined by (2).
It is now tempting define the calibration error related with this diagram, as an ECE of this new random variable over [0, 1] x {0, 1), analogously to the definition of SmECE, by considering
amECE,(D) := 1 (t) - t|62, (t) dt.
This definition can be readily interpreted: for a random pair (ff y) and an 7 ~ NO o) independent, can consider pair (f + 7. y). It turns out that
smECE, (D) = ECE((R(( + n).9),
where TH : IR + [0, 1] collapses points that differ by reflection around integers (see Section 1.1).
Unfortunately, despite being directly connected with more desirable reliability diagrams, and hav- ing more immediate interpretation as a ECE of a noisy prediction, this newly introduced measure smECE has its own problems, and is generally mathematically much poorer-behaved than SmECE. In particular it is no longer the case that if we start with the perfectly calibrated distribution, and ap- ply some smoothing with relatively large bandwidth a, the value of the integral (7) stays small. In fact it might be growing we add more smoothing?.
Nevertheless, if we chose the correct bandwidth o", as guided by the SmECE consideration, the integral (7), which is visually encoded by the reliability diagram we propose, should still be within constant factor from the actual SmECE a (D), and hence provides a consistent calibration measure
Lemma 10. For any have
smECE, (D) SmECE, co,
where = 22/T 0.8.
In particular, for s.t. smECE, (D) = 0", we have smECE, (D) ~ smECE,, (D).
(The proof can be found in Appendix D.3).
B GENERAL METRICS
Our previous discussion implicitly assumed the the trivial metric on the interval d(u, v) = Iu - v/- We will now explore which aspects of our results extend to more general metrics over the interval [o, 1]. This is relevant for example, our application downstream of the predictor is more sensitive to miscalibration near the boundaries.
The study of consistency measures with respect to general metrics is also motivated by the results of Blasiok et al. (2023). There it was shown that for any proper loss function I, there was associated metric dj on [0, 1] such that the predictor has small weak calibration error with respect to dy if and only if the loss I cannot be significantly improved by post-composition with Lipschitz function with respect to d,. Specifically, they proved
(D) S
E (f.)
[(( v)1 inf E ((((f) S / (CCE4( " (fu)>D
"This can be easily seen, if we consider the trivial perfectly calibrated distribution, where outcome y Bernouli(11/2 /22 and prediction f is deterministic 1/2. Then SmECE, (D) Ca for some constant C 0.79.
13

---

Published as a conference paper at ICLR 2024
where 00 [0, 1] ranges over all functions Lipschitz with respect to the dj metric, and wCE,, (D) is the weak calibration error (as introduced by Kakade & Foster (2008), and extended to general metrics in Blasiok et al. (2023), see Definition 11).
The most intuitive special case of the above result is the square loss function, which corresponds to trivial metric the interval d(u, 2) = Iu el. In practice, different proper loss functions are also extensively used - the prime example being the cross entropy loss [(f. v) == - In (1 (oo((/(1-v)) on [0, 1]. Thus, we may want to generalize our results to also apply to non-trivial metrics.
y) In(1 - p)). which is connected with the metric diogie (u,v)
log(e/(1-1)))) u))l
B.1 GENERAL DUALITY
We will prove a more general statement of the duality theorem in Blasiok al. (2023). Specifically, they showed that the minimization problem in the definition of the dCE. can be dualy expressed as a maximal correlation between residual := y - f and bounded Lipschitz function of the prediction J. This notion, which we will refer to as weak calibration error first appeared in Kakade & Foster (2008), and was further explored in Gopalan et al. (2022); Blasiok et al. (2023); Blasiok et al. (2023)². Definition 11 (Weak calibration error). For a distribution D over (0, 1|x (0, 1) of pairs of prediction and outcome, and a metric d on the space [0, 1] of all possible predictions, we define
wCE,(D)= == sup E- (f - y)w(f),
(8)
wE f-20~-
where the supremum is taken over all functions [0, - [-1,1] which are 1-Lipschitz with respect to the metric d.*
For the trivial metric the interval d(u,e) = ju v/. wCE was known to be linearly related with dCE by Blasiok et al. (2023). We show in this paper that the duality theorem connecting wCE and dCE holds much more generally, for broad family of metrics.
Theorem 12 (Blasiok et al. (2023)). If a metric on the interval satisfies d(u, v) 2 |l - ul then wCE, x dCE,,
The more general formulation provided by Theorem 12 can be shown by following closely the orig- inal proof step by step. We provide alternate proof (simplified and streamlined) in Appendix D.8.
B.2 THE dCE IS CONSISTENT CALIBRATION MEASURE WITH RESPECT TO E
As in turns out, for relatively wide family of metrics on the space of predictions (including the diogit metric), the associated calibration measures are consistent calibration measures with respect to the & metric. The main theorem prove in this section is the following.
Theorem 13. Ifa metric d : [0, 1]2 + [too} satisfies d(uu, v) Z Iu ul O.
ol and moreover for some
YE, Vu, v E [c,1-8] - E), d(u, v) S Iu uIE
then dCE, is a consistent calibration measure.
The proof of this theorem (as is the case for many proofs of consistency for calibration measures) heavily uses the duality Theorem 12 - since proving that a function is a consistent calibration measure amounts to providing a lower and upper bound, it is often convenient to use the dCE formulation for one bound and wCE for the other.
The lower bound in Theorem 13 is immediate since d(u, v) 2 (u v), the induced Wasser- stein distances on the space [0, 1] x {0,1) satisfy the same inequality, hence dCE, 2 dCE,, and dCE, 2 dCE/2 2 by Claim 31.
As it turns out, if the metric of interest is well-behaue except near the endpoints of the unit interval, we can also prove the converse inequality, and lower bound wCE(D) by polynomial of (D).
A Weak calibration was called smooth calibration error in Gopalan et al. (2022); Blasiok al. (2023). We revert back to the original terminology weak calibration error to avoid confusion with the notion smECE developed in this paper.
'In Blasiok al. (2023)
14

---

Published as a conference paper at ICLR 2024
Lemma 14. Let d [0, + R+ U foo) be any metric satisfying for some 0, VE, Vu, [e,1- =E,, d(u, v) S wu 2/=
then wCEa(D) S wCE(D), where q == max(c 1) (Proof in Appendix D.5.)
We are ready now prove the main theorem here
Proof of Theorem 13. We have ( 2 D)/ by our previous discussion, on the other hand Theorem 12 and Lemma 14 imply the converse inequality:
(D), x wCEa(D) S wCE(D) v dCE(D)
Corollary 15. For a metric induced by cross-entropy loss function drogis (u, 1) |n(uu(1-1)) In(v/(1- (1-)))] the WCEdrogue is a consistent calibration measure.
Proof. To verify the conditions of Theorem 13 it is enough check that logit(u) In(o/(1 v)) satisfies min(t, 1---- t) s de logit(() s C. Since di logit(()) =(I-zj these conditions are satisfied with and C =
d
B.3 GENERALIZED SMOOTHΣCE
We now generalize the definition of SmoothECE to other metrics, and show that remains consis- tent calibration measure with respect to its metric. Motivated by the logit example discussed above, concrete way to introduce non-trivee non-trivial metric on a space of predictions [0. 1]. is consider continuous and increasing function h [0, 1] + IR [oo and the metric obtained by pulling back the metric from [0, 1] through h, i.c. d, v) [h(u) h(v)l-
Using the isomorphism h between ((0. 1]. dr) and a subinterval of (RU(#oc), } |-),, we can introduce a generalization of the notion of SmECE, where the smoothing being applied in the image of h.
More concretely, for a probability distribution D over [0, {0, 1}, kernel K R R an increasing continuous map h: [0, 1] - TR. U {+oo} we define
R. and
(t) E(r Ktt,, N(F)) v)
BULD h())
(k.(()== = E K(I, K(I,WD)). (f.))
Again, we define
smECERA(P = | F (xx(())ka(())))
which simplifies to
SmECEKA(D) = 1
E K(t,h(f))(f - -v) dt. IOADDD
As it turns out, with the duality theorem in place (Theorem 12) the entire content of Section 3 can be carried over in this more general context without much trouble.
Specifically, if define smECE,,A SmECE where KN. is Gaussian kernel with scale a, then a + SmECE,,, (f, y) is non-increasing in a, and therefore there a unique fixed point a, s.t. σ_ smECE,..m.... (f.
We can now define SmECE, (f. v) := o.. and we have the following generalization of Theorem 6, showing that SmoothECE: remains consistent calibration even under different metrics.
15

---

Published as a conference paper at ICLR 2024
Theorem 16. For any increasing and continuous function h : [0, + R u {=oo),, if we define d, : [0, 1]2 + R2 to the metric (u, v) max(Ih(u) - ((()).22 2) then
dCE (D) S SmECE, (D) & VdCEA, (D).
(Proof in Appendix D.7.)
Note that if the function h is such that the associated metric d,, satisfies the conditions of Theo- rem 13, as an additional corollary we can deduce that SmECE,,h also a consistent calibration measure in a standard sense.
B.4 OBTAINING PERFECTLY CALIBRATED PREDICTOR VIA POST-PROCESSING
One of the appealing properties of the notion dCE as was introduced Blasiok et al. (2023), was the theorem stating that if predictor (S: y) close calibrated, then in fact nearby perfectly calibrated predictor can be obtained simply by post-processing all the predictions by a univariate function. Specifically, they showed that for distribution D over [0, 1] x {0, 1], there
[0,
[0. 1] such that for (f, y) ~ D the pair (x())..) v) is perfectly calibrated and moreover E |x(f) - - /dCE(D).
As it turns out, through the notion of smECE, we can prove a similar in spirit statement regarding the more general distances to calibration dCE,, The only difference is that we allow the post- processing K to randomized function.
Theorem 17. For any increasing function [0, 1] (oc)), }. and any distribution supported on [0, 1] x {0,1}. 11. there is a probabilistic function k [0, 1] + [0, 1] such that for (f.g) ~ D, the pair (H((),.) perfectly calibrated and
Ed (n(()) S amECE.,,.D)
where dy is the metric induced by h. In particular
Edi(s(f))f) /dCEa, (D).
Proof. Let us consider a distribution D over [0, 1] x {0, }} and monotone function h, such that smECE,,, d..
First, let us define the randomized function kι: let mo : - R be a projection of IR to (((0, 1J), and let 77 (O, o.). We define
ka(f) = h- hmo (b()) + n))
We claim that this Kn satisfy the following two properties:
1. EUAA) (d(f,(((f))
2. ECE(K'()).)) S...
Indeed, the first inequality is immediate:
Efd(f, K xf)) = EE(A()) no (h(() + 7)] S E < a..
The proof that ECE (f), y) S o. is identical to the proof Lemma 28, where such statement was shown for the standard metric (corresponding to h(z) x))
Finally, those two properties together imply the statement of the theorem: indeed, if ECE( y) < G., take (t) : E[y] f' t). In this pair (Mz2)")) y) is perfectly calibrated, and by definition of ECE, we have E (f²))) - f'l ECE y) Composing now K fig K1, we have
(((f) f < [E| K2 o K (f) k, (fIll BlIk, (f) - fll S a..
(f.))~
Moreover distribution D' of (R((),)) y) is perfectly calibrated.
16

---

Published as a conference paper at ICLR 2024
C ALGORITHMS
In this section we discuss how SmECE can be computed efficiently: for any o, the quantity smECE, can be approximated up to error in time (n + M log M- in the RAM model, where .M [E a '1 In order find an optimal scale o,, we need to perform binary search, involving log - evaluations of smECE,.
The explicit procedure to compute SmECE is given in Algorithm 2.
We shall first observe that the convolution with the reflected Gaussian kernel can be expressed in terms of convolution with a shift-invariant kernel. This is useful, since such a convolution can be implemented in time (M log M) using Fast Fourier Transform, where m is the size of the discretization.
Claim 18. For any function g [0.1] - R, the convolution with the reflected Gaussian kernel * KN can be equivalently computed as follows. Take an extension of to the entire real line g TR R.. defined as ğ(x)) == (()))()))) Then
[g RN,a((1) = lā K KN))((),
where KN 22)2/20)/v2TO0
x
is the standard Gaussian kernel Ko (t1,t2) = exp(-(t1
Proof. Elementary calculation.
1)1, convolve such restricted ğ with Gaussian, and restrict the convolution in turn to the interval e. Indeed, such restriction introduces very small enror, for every E [0, we have.
We can now restrict 9 to the interval [-7, + 1] where T :=
[1 [1[-TTT+1]] 9) * (x,e((t) (() s (1
+ (1-
S
In practice, is enough to reflect the function g only twice, around two of the boundary points (corresponding to the choice 1). For instance, when o < 0.38, the above bound implics that the introduced additive error is smaller than o², and the error term rapidly improves is getting smaller.
Let discuss computation of SmECE, for given scale To this end, we discretize the interval [0, 1]. splitting into M equal length sub-intervals. For sequence of observations (fr. y:) round each r; the nearest integer multiple of 1/M, mapping it to bucket h; round (M fi)- observation falling this bucket
In each bucket b E (0,... .Q....M M}. we collect the residues fi := E..,
y.).
In the next step, we apply the Claim 18, and produce wrapping h of the sequence h - extending integer multiples of 1/M in the interval [-T,T T 1] by pulling back through the map TR.
The method SmECE, then proceeds to compute convolution K with the discretization of the Gaussian kernel probability density function, i.e. K, exp(-t2 22 and K, == K, / Kr.
This convolution F := / K can be computed in time O Q), where Q = MT, using Fast Fourier Transform, and is implemented in standard mathematical libraries. Finally, we report the sum of absolute values of the residuals Σ [x as an approximation to SmECE, as an approximation smECE,.
17

---

Published as a conference paper at ICLR 2024
Algorithm 1: Efficient estimation SmECE,, at fixed scale o
Function Discretization( (f M) is
h - zeros(M - 1); for [n] do b - round M f:): h6 - hy + 2g:
end
return h;
end
Function Wrap(h, is
M +- len(h);
for [(2T 1)M do
j + (i mod 2M);
if M then
j < 2M - j:
end
h4 + hys
end
return h:
end
Function smECE(a, {fr, y1) is
h Discretization (fr, Vi l--
h Wrap(h, I log
K DiscreteGaussiaKeenell.,, 1o---__-111
F + h * K;
return EirTM
(T+I) 1
end
Algorithm 2: Efficient estimation of smECE,: using binary search over find root of decreasing function SmECE,
Data: (fe, 3.
Result: smECE.(((J..
1 1<00; O;
<- 1;
while 1> do
<- (u 1)/2;
smECE, (fr. v:l) < then
else
1 + o;
end
end
return
18

---

Published as a conference paper at ICLR 2024
D OMITTED PROOFS
D.1 PROOF OF THROREM 6
In this section will prove Lemma 21 and Lemma 23, two main steps in the proof of Theorem 6, corresponding to respectively lower and upper bound, As it turns out, those two lemmas are true for much wider class of kernels. The restriction the monotonicity property (Lemmaa 28), which was convenient for us to define the scale invariant measure SmECE. by considering fix-point scale o². In Appendix D.2 we will show that the Reflected Gaussian kernel satisfies the conditions of Lemma 21 and Lemma 23.
the kernel K' to be Gaussian kernel stems from
We will first define dual variant of dCE.
Definition 19. We define the weak calibration error to be the maximal correlation of the residual 1-Lipschilz,uuncion function and [-1, bounded function of a predictor, i.e.
( y) with 1-Lipschitz,
wCE(D) == sup E w
w()) -y), v),
where C is family of all ficiisschitt.uunctooin from [0, 1] to 1-1.
To show that SmECE' consistent calibration measure we will heavily use the duality theorem proved in Blasiok et al. (2023) the wCE and dCE are (up to a constant factor) equivalent. A similar statement proved in this paper, greater generality (see Theorem 12).
Theorem 20 (Blasiok et al. (2023)). For any distribution D over [0, 1] x {0, we have dCE(D) & wCE(D) S 2dCE(D).
Intuitively, this is useful since showing that new measure SmECE is a consistent calibration mea- sure corresponds to upper and lower bounding it by polynomials of dCE. With the duality theorem above, we can the minimization formulation dCE for one direction of the inequality, and the maximization formulation wCE for the other.
Indeed, will first show that wCE is upper bounded by SmECE if we add the penalty parameter for the "scale" of the kernel K.
Lemma 21. Let U C I be (possible infinite) interval containing [0. and K U x U + R be a non-negative symmetric kernel satisfying for every to E [0, 1]. ((t,, t) dt 1, and f
to (t, to, dt 7. Then
wCE(D) I SmECE (D) +
0. - [-1, and take n K as in the lemma statement. Since kernel K is nonnegative, and f (t,, (0) dt = O, we can sample triple f.y) s.t. (f.z) D. and f is distributed according density K(: f). In particular
Proof. Let us consider arbitrary I-Lipschitz function
ff
We can bound now
(w((( w)] S Blw( w)] E AIl (L
E
$ E w(F((f w)]
(9)
We now observe that
BI(f -)1f =t] Esy fff v) f(t),
Es K(t,f)
and the marginal density of f is exactly
m,(()= (1.0)D
K(t,f) 8(t)-
This leads to
E wf(f (oi(f-vv-- v)} = w (t) dt < ( smECEx
(10)
Combining (11) and (12) conclude the statement of this lemma.
n
19

---

Published as a conference paper at ICLR 2024
To show that smECEx (D) is upper bounded dCE, will first show that SmECE is zero for perfectly calibrated distributions, and then we will show that for cell-behaved kernels SmECEx(D) Lipschitz with respect the Wasserstein distance the space of distributions.
Claim 22. For any perfectly culibrated distribution DD and for any kernel K we have
SmECE (D) 0.
Proof. Indeed, by the definition of we have
f(t) Efy K(S,t)( v)
BSy Kfftt)
Since the distribution D is perfectly calibrated, we have E(SNNDDI( - y)lf] = 0, hence
E ((,( - - = E (f(f, - - = f.y
K(ftt)
E (Sa)DD
I(f - w)1fl] = 0.
(fa)~D
This means that the function F(t) is identically zero, and therefore
smECE [(()))((t) 0.
Lemma 23. Let K be a symmetric, non-negative kernel, such that for and let À S be a constant such that for any to, E [0, 1] we have j (to. K ((1,, s lto t1l/>. X. Let D1, D2 be pair of distributions over [0, 1] x 10. Then
smECE (Dt) SMECEx (D2)) & (1 +1 Wi(Di, D2).
Proof. We have
SMECE
/
E [t, f) 53| dt. (1.0ND
we have coupling (/i, S2, yn: y2) s.t. 18[/1- f2l 22|+ + 1n1 - -2ll s 5, (f1, y1) Dr and U2,
D2, then by triangle inequality decompose
>mECEx<(P) smECE xD2))
E (fi.fa.i
(K(L)) K(, fild
+
E
(tt,f))) - fol + +111 -
(1.2219322)
We can bound those two terms separately
/ ((t.) X Biff-fall - fell < 50/2, (1.J2.01)
E K(tt f2) =
E
(1.J2.01) and similarly
f E (K(,,)) - fal 1y y22)] de = E [ [((, f2) (If - f2l 1yn 1/2 = Se]lfifal+ler y24 S 8.
Corollary 24. Under the same assumptions on K as in Lemma 23, for any distribution D over 1] x 1).
smECE (D) < ( +11 dCE(D).
Proof. By definition there is a perfectly calibrated distribution D', such that W, (D, D') I dCE(D). By Claim 22, smECE (DD)) = 0, and the corollary follows directly from Lemma 23. n1
20

---

Published as a conference paper at ICLR 2024
D.2 FACTS ABOUT REFLECTED GAUSSIAN KERNEL
We wish to now argue that Lemma 21 and Lemma 23 imply the more specialized statements Lemma and Lemma 8 respectively of Lemma 21 and Lemma 23 with y and À proportional to We
the reflected Gaussian kernel N satisfies conditions
Lemma 25. Reflected Gaussian kernel NN,- defined by (2) satisfies
1. For every to, we have KN (t, to) dt =.
2. For every to we have f tn R to) dt 22/TO.
3. For every to, bn, we have J ( to)
to)) S Ito til/
Proof. For any given to. the function EN,,(to: is probability density function of random variable ato + 7)) where y ~ (N,0 and TH [0, 1] is defined in Section 1.1. In particular,
have [T(()) an(y)) I x vl.
The property 1 satisfied, since the (:,o(:: is probability density function.
The property 2 follows since
/ |t to KN dt dt= E
tol = IE IR + +1)
T + 1) - (R((t))
N0,00
N~110,0
E (0,0
m/ a 2//T.
Finally, the property 2 again follows from the same fact for Gaussian random variable: the integral [K (t,, to) KN (t, fo)l is just total variation distance between Rto 17) and (t(ti 7)
where y) ~ (O, o), but by data processing inequality we have
(V 7), TR((1 + n)) s (Vo + n,4 7) S 10 (2)(
Where the last bound the total variation distance between one-dimension Gaussians is special case of Theorem 1.3 Devroye et al. (2018)².
Definition 26. We say that a paramterized family of kernels K₂ : UXX + R where [0. 1] C U C RR a proper kernel family if for any σi S 02 there is a non-negative kernel Ho :U + and Ko₃ Kaz Hoyor
satisfying [ 1-1 S
Here the notation K is denotes
[K * (t,,) = / (tt, dt,
and
| 1-11- sup / [H(t, dt.
WEE Ju
Claim 27. The family of reflected Gaussian kernels KN is proper kernel family, with
Ko = Koa,N K
Vot-oz.N
Proof. Let 03 := vot-oz wish to show that K Koy,N Kog,N- In order to show this, it is enough to prove that for any f, we have f Koy,N f KøI,N Kos.N- This is true by Claim 18, since this property holds for standard Gaussian kernel Ko,.N Kog.N = K (it is here equivalent to saying that for two independent random variables Ze NNO,, 02) and Za N 03) we have Z2 + Zz ~ (1),
TThis special case, where the variances equal, in fact elementary calculation.
21

---

Published as a conference paper at ICLR 2024
D.3 USEFUL PROPERTIES OF SMECE.
Lemma 28 (Monotonicity of smECE). Let Ko be any proper kernel family parameterized by If
01 S 02, then
smECEk,, (D) 2 SMECEk., (D).
Proof. Let define
ho (t) = E (t,t,f((f - -y) - =(())(()) (f
such that
smECE (D) = | | :- / (t) dt.
Since 01 S 02 and Kg is proper kernel family, we can write Koz = Koi * Hor
We have now,
E (f Ko (.11) (on(())))) Ho
hoy Ho,,o
(f.9)
E (f - () * Ho Ho /.y
= E (f y) (o.())
l-V
hoz-
On the other hand for any function we have ||f Ho, oz lll
1 |f o2lli-11 and
|2 S 1 by the definition of proper kernel family. Therefore
Corollary 29, In particular for 02 have SmECE,, (D) < SMECE,, (D).
Proof. Reflected Gaussian kernels form proper kernel family by Claim 27.
Lemma 30. For any o, we have SmECE, = SMECE, + 2/T
Proof. Let
f(1) = Es, (N. fff
Es KN (t.
We have
|mECEE, (f.v) (f.vE - (8(() +)5(t) dt
- / BIKKNo ft. +| dt
|/ I (1, - dl
E.
|f 11-7p x2(
Z~N(ffa)
|2 |2|= V2/TT
2~.((.o))
22

---

Published as a conference paper at ICLR 2024
D.4 EQUIVALENCE BETWEEN DEFINITIONS OF dCE FOR TRIVIAL METRICS
The dCE(D) was defined in Blasiok et al. (2023) as a Wasserstein distance to the set of perfectly calibrated distributions over X = [0, 1] (0. 1). where X equipped with metric
[lfi fal if 1/2 otherwise
di ((S1, U1 (f2 v2))
8o
While generalizing the notion to that of dCE,,, where d is a general metric on [0, 1]. we chose a different metric on X (specifically, we put a different metric on the second coordinate), that is d((fi, v1), (f2, y2)) = d(fi, f2) + 1y/ - y2l-
As it turns out, for the case of trivial metric on the space of predictions, this choice is inconsequen- tial, but the new definition has better generalization properties.
Claim 31. For the metric & (2), = f1 - f2l. we have dCE S dCE, (D) - dCE(D), for some universal constant
Proof. The lower bound dCE,, I dCE is immediate, since dCE,,, is a distance of D to P with respect to a Wasserstein distance induced by the metric d, on [0, x (0. 1}. dCE is the Wasserstein distance with respect to the metric d2, and we have pointwise bound d1 (u, v) d2(u, v), implying W1,d, (D1, D2) S (P,,
The other bound follows from Theorem 12 and Theorem 20 20-dCIi and dCE, are within constant factor from wCE,,
D.5 PROOF OF LEMMA 14
Proof. Let take w(x): [0, - [-1, as in the definition of wCE,, 1-Lipschitz function with respect to the metric d, such that [E(y - f wf( wCEa(f. = E.
We wish to show that wCE(f, y) 2 c Indeed, let take (X) = w(Tr(z)) where :=
h, 1 - 7), ny : [0, 1] + is projection onto the interval I, and == e/C for some large constant
C.
Note that e is O(= Liipshitz with respect to the standard metric on [o, 1]. If EE - y) y) 2 e/2, we immediately have wCE(S,)) y) 2 gc+1 (we can w/ L test function, where L (ss-9) is a Lipeshitz constant for function w). Otherwise [( (w(() - w(f)) 2 e/2. Let us
call W2 == (w u) /2, such that B(f y) w2 2 e/4, and moreover supp(us) w22) C [0, W2 is L-Lipschitz with respect to d.
where
Since [0, 1] \/ has two connected components (0, and (1 -1-33 7, 1]. on one of those two connected
components correlation between the residual (y - f) and wy has to be at least E/8. Since the other case is analogous, let us assume for concreteness, that
E(y - f)wz(f) 2/8,
where (x) = (2( for x E [0, and wg (xx) = 0 otherwise.
We will show that this implies Pr(f A 1) e, and refer to Claim 32 to finish the argument. Indeed
E(y - (ly-f)ws(f) S E [(1 f)1lf STA 1|]+ S o] < Pr(f & 7AA 1)+>
hence
Pr(f ク 1) 2 c/8 e/116.
where we finally specify > = e/32.
To finish the proof, it is enough to show the following
Claim 32. For a random pair (f.y) of prediction and outcome, if Pr(f & y A = 1) 2 E or
Pr(f 2 7 A y 0) 2 where 7 = e/8, then wCF(J, 2 e
23

---

Published as a conference paper at ICLR 2024
Proof. We will only consider the case Pr(f S A 1) Let us take wxx) = max(1 - x/22, 0). We have
The other case is identical.
- T 2 Pr(s クイクツー - 2n 2 2
Since w OipsshLiis,hhiz, we have CE((sy) 2 6².
D.6 SAMPLE COMPLEXITY PROOF OF THEOREM 9
Lemma 33. Ler X [0, 1] I be a random function, satisfying with probability 1, || Jo (X( di S and sup (() & a. Assume moreover that for every t, we have [x) = O.
Consider now independent realizations X1, X2,.. X. : - R. each identically distributed as Xt).. and finally let
X(t) = Σ Xi(t).
Then
E X (0)
Proof. By Cauchy-Schwartz inequality ||X|| < || 1| =
||x hence
/ x(t)
E x
E
X
f B(X(1)
/
B(X())j
EII & [ S 1
Proof of Theorem 9. Let us first focus on the case o = Gu. For a pair (f.v) E [0, x f0, let us
define X x( [0, IR
x x(00) (1) Ka, (S,0)S - -y).
(mo) Note that SmECE, 0. (D) E X f. /m/ll. and similarly SmECE(D) E.f.yDD X (10) Define X (
f Il1.
(mo) Es.yD X (go) this is random function, since (fis y:) is chosen at
random from distribution D, and note that:
Random functions X (o0) for E {L...., m) are independent and identically distributed.
2. With probability 1, we have [|x(000)) ||, S maxy || (S. )11 = 2.
3. Similarly, with probability we have | aaxc
2 sup Kon (t1, s 20 hn.t2
4. For any [o, 1] and i {1,...,m) m., have B(X((00) (1) 0.
24

---

Published as a conference paper at ICLR 2024
Therefore, apply Lemma 33 deduce
E
m Σ
x
1
oom
hence, if m 000 by Chebyshev inequality with probability least 2/3 bound E (000) /mlli S &, and if this event holds, using triangle inequality
smECE,, (D) smECE,, (D)I =
Σ
X (00)
ll/m.
Finally, for o oo. note that x! = x! .NNNNNN N 0o8 (Claim 27) and therefore as soon as
|| E x || Se, E, we also have
Σ X /mlli =11 Σ 8(000 K N. NNN00200311
$ 11 Σ x(00) ||||||| Ss.
where
|| 11-1 sup (K(1,22))d SI.
This implies |sEECE, (D) SMECE, (D) for all 00.
Finally, if smECE. (D) a. 2 0o have smECE,, (D) a. hence smECE, (D) 2 0. E,
and by monotonicity smECE.. (D) 2 o. 6, implying SMECE. 2 a. Identical argument shows SmECE, S o, +
L
D.7 PROOF OF THROREM 16
The Lemma 21 and Lemma 23 have their correspondent versions the more general setting where metric is induced the space of predictions [0, 1] by monotone function h [0, 1] + R the proofs are almost identical to those supplied the special case, except we need to use the more general version of the duality theorem between wCE and dCE, with respect metric d (Theorem 12).
Lemma 34. Let h be an increasing function h: [0. - IR (=o0} and du(u, I h(v)) be the induced metric on [0, 1}. Assume moreover that K(t) is probability density function, such that for 17
we have IE |n) 7/. Finally, let us abuse the notation to define the associated kernel
on R. x R as K(x,y) K (xx v). Then
wCE.(f. I SmECEK, (f.v) +7
Proof. Let us consider an arbitrary I-Lipschitz function w [0. + [-1, with respect to da, and take K as the lemma statement. Let 1( 1). and let us take u - IR to be given by (() = w(h [t)), and note that ø is Lipschitz, since wo was Lipschitz with respect to dy- We can therefore extend to [-1, 1] valued Lipschitz function on the entire line IR Now for any S 1 we have (m(h()) + v) de (())) < |m), and we can bound
[w (w(s v)] E((((()) w) v)] |nlls vl
(f+))
EEI 4 b) (M+)) -v].
(1I)
We now observe that
Esy (((,)()))))))) =(1),
B( - ()) + =
Bi k(t,h())
25

---

Published as a conference paper at ICLR 2024
and
1)+n(() (t) = E K(t, h(f) = 8(t),
1.2
where Myty is the measure of k()) + +1--
This leads to
+)))))))(() E ()) - = (())F()8(()) & (F(O)8())))
S (f.y). (12)
Combining (11) and (12) we conclude the statement of this lemma.
Lemma 35. Let & be an perreassingfuncctio h j0, 1] - I [ and (u, v) [h(u) h(v)l be the induced metric on [0, 1].
Let (tt be probability density function of random variable, such that for T) K we have E = O, and let X I be a constant such that for any E, we have (V 17 + S E/ finally by the abuse of notation let us define te assocated kernel on R R as K(x, v) = K (x y). Then Then
( 1 +1
SmECEK,N.0 S
acEd, (D).
D.8 GENERAL DUALITY THEOREM (PROOF OF THEOREM 12)
Let P C A( 1] x fo, 1}) be the family of perfectly calibrated distributions. This set is cut from the full probability simplex A 1] {0, 13) by a family of linear constraints. specifically μ P if and only if
Vt, (1 t)p(t, 1) tu(t, 0) O.
Definition 36. Let F(H, R) be a family of all functions from H to R. For a convex set of probability
distributions 2 A(H), we define Q* F(H, IR) be a all functions g, s.t. for all 'D Q
we have EenD ( S O.
Claim 37. The P F(00 1] {0,1),R) is given by the following inequalities. A function H E P if and only if
Vt.
H(t,g) 5.
BerBer()
n
Lemma 38. Let Wi D2) be the Wasserstein distance between two distributions D1, D: A(O0, 1|x, {0, 1H) with arbitrary metric d on the set [0, 1] x {0, 1}. and let Q C A 1] x 1)) be a corvex set of probability distributions.
The value of the minimization problem
min W1(D1, D) D.EQ
equal
H(S.v)
(SuND
s.f. H is Lipschitz with respect to d,
H E Q".
Proof. Let us consider a linear space V of all finite signed Radon measures on X : [0, x {0, 1}. satisfying xxX) O. We equip this space with the norm ||д = EMD (04 n_) for measures (X) = 1 (and extended by |Aplly = A A|||4|| y to entire space). The dual of this space is (X) space of all Lipschitz functions X which of base point is inconsequential). The norm on Lipp(X) is |[ given by the Lipschitz constant of W (see Chapter 3 in Weaver (2018) for proofs and more extended discussion).
0 some fixed base point Zo X (the choice
For a function H on X and a measure 1a on X, we will write H(u) to denote f' W dp.
The weak duality is clear: for any Lipschitz function H and any distribution D, have H(D) < (Di) + (D,,,, D) = Wi (
For the strong duality, shall now apply the following simple corollary of theorem.
26

---

Published as a conference paper at ICLR 2024
Claim 39 (Deutsch & Maserick (1967), Theorem 2.5). Let (X, || [|x) be normed linear space,
To E X, and P C a convex set, and let dxx P) = inf PEP || pllx. Then there is w X", such
that ||0| x- and inf w(p) w(xx) d(x, P). PEP
Take a convex set P C V given by := by definition of the space V, and hence using the claim above, we deduce
== (D- y y E Q). Clearly minp, eQ Wi(D, d(00, P)
max inf Hp). d(0, P) M
Taking H which realizes this maximum, we can now consider shift H := i1 -- sup (Q), that
1E0
H º*, and verify
min Wi(D,D1) d(0, inf (p) H(D) sup qEQ
H(() H(D).
D,Eo
pEP
Corollary 40. For any metric d on [0, 1] {0, 1,. the (D) is equal to the value of the following maximization program
max
E H(f
(1D)~D
s.t. H is Lipschitz with respect to d
Vt. E H v) S 0.
B-re(())
Lemma 41. For any metric on [0, 1] if we define d to be a metric on [0,1] x {0,1) 1} given by d((Si,n)) (f2,w2) == d(f1, f2) + 1y V/l we have
wCF,(D) 2 (D)/2
Proof. We shall compare the value of wCEa(D) with the optimal value of the dual as in Corol- lary 40.
Let us assume that for a distribution D we have a function И 10, 1] x {0,1} + R. s.t.
B(f.)~D H(f.v) OPT, which is Lipschitz with respect to d. We wish to find function
w: : 0. 1] + [] which is Lipschitz with respect to d, s.t.
E (f - w)w(f) 2 OPT/2. F.3
Let us take
w(f) : -
We will show instead that w is 2-Lipschit,, [-1, 1] bounded and satisfies - (f (f) 2 OPT, and the statement of the lemma will follow by scaling.
Let us define w(f) = H(f 0) - H(f, 1). The condition
VS. E H(S.)) 5 ge-Ber(J)
is equivalent to f'w(]) 2 H(J,0). Hence
H(f.) = (J 1) + (1 - ()) - s (f -y)
which implies B(f - ( 2 E (f.v)..
Moreover, the function w(f) is bounded by construction of the metric d and the assumption that H ( y) was Lipschitz. Indeed [w(s) HH(.0) 0) H(S, 1)) < å((s, (f. 1.
n
27

---

Published as a conference paper at ICLR 2024
E CONSISTENT CALIBRATION MEASURES AND SMOOTHECE
Here we elaborate on the shortcomings of ECE, and resolution offered by SmoothECE, and the notion of a consistent calibration measure (Blasiok et al., 2023). One fundamental issue with the ECE is: it discontinuous in the underlying predictor, so a small change in the predictor can cause large change its ECE. A simple example this phenomenon was presented in the Introduction of Blasiok et al. (2023) (also formalized as Lemma 4.8 in the same work). Here, we will demonstrate this discontinuity visually, with related example.
In Figure 3, we construct three different distributions that are each small perturbations of one an- other. The top row shows samples 1/) 1] {0, }} from each distribution. The first dis- tribution (first column) is nearly perfectly calibrated. This is is evident from both the smoothECE diagram (middle row) and the binnedECE diagram (bottom row). To construct the second and third distributions, we shift each positive sample (y 1) slightly the right, and each negative sample (y = 0) slightly to the left. No sample moves more than 0.05 from its initial position in Distribution so this is small perturbation to the predictions f.. We that the smooth reliability diagram in the middle row does not change much between all three distributions, and the smECE metric itself also stays nearly constant (the smECE metric is listed in the upper-left of each plot).
However, by Distribution 3, the binned reliability diagram (bottom row) has changed drastically, and appears be significantly mis-calibrated. Moreover, the binned ECE metric (with 20 bins) has changed from 0.06 in the first distribution to 0.31 in the third distribution. The binned ECE thus incorrectly reports that Distribution 3 is far from calibrated. This essentially occurs because have shifted the positive and negative samples into disjoint bins by Distribution 3.
This example demonstrates how standard (binned) ECE is not robust to small perturbations in the predictor, and can severely over-estimate the calibration error. Smooth ECE, on the other hand, does suffer this flaw. The formal definition of a consistent calibration measure Blasiok et (2023) enforces this robustness/contnnity property. in addition to other natural theoretical properties. We refer to the exposition Blasiok al. (2023) for further theoretical details.
E. STATISTICAL CONSISTENCY
Our estimator of SmoothECE also satisfies the classical criteria of statistical consistency. Specifi- cally Theorem 9 shows that as the number of samples m + co, the finite-sample estimation error O. In fact, Theorem 9 is stronger than just asymptotic consistency- provides quantitative generalization bound.
28

---

Published as a conference paper at ICLR 2024
Distribution 1
Distribution 2
Distribution 3
Samples
SaECC 10.500 0.085
SVECE 1.000=20.00
SWZCE (0.44.0.4..2.. 0.966
SmoothECE
02
0.2
0.0
22
16 Mb
84
0.5
0.0
-
0.2
04
80
1.8
0.5
0.2
0.50000.000
302 0. 146
K01
0.30
BinnedECE
0.4
02
0:2
0.2
0.0 3.4 0.5
0.5
1.0
1.0
0.2
0.5
6.5
3.5
0.8
0.2
3.4
0.5
0.5
1.0
Figure 3: Continuity Demonstration. A demonstration of the discontinuous behavior of stan- dard (binned) ECE, and how this is addressed by our Smooth ECE. We construct three differ- distributions that are each small perturbations of another. The top row shows samples (fr. E [o, 1] x (0, 1} from each distribution. The first distribution is nearly perfectly calibrated. To construct the second and third distributions, we shift each positive sample (y 1) slightly to the right, and each negative sample (y = 0) slightly to the left. No sample moves more than 0.05 from its initial position in Distribution 1, so this is small perturbation see that the smooth reliability diagram in the middle row does not change much between all three distributions. However, the binned ECE in the bottom row changes drastically, and reports severe miscalibration on Distribution 3 - even though all three distributions are actually close to cali- brated. See Section for more details.
the predictions St. We
29


Reviews:
[{"review_id": "ONfoZN7WjD", "reviewer": "Reviewer_PxLa", "summary": "This paper proposed the smooth ECE, which uses kernel smoothing to compute the Expected Calibration Error(ECE) estimator. The proposed estimator is naturally related to a smoothed reliability diagram. The estimator is shown to be consistent and computationally efficient and sample-efficient.", "questions": "1. The authors emphasize at the end of section 2 that ”consistent calibration measure does not refer to the concept of statistical consistency“. Can the authors comment a bit on the statistical consistency properties of the proposed estimator? e.g. convergence to the ECE as sample size increases?\n \n2. On top of page 6, the reflected Gaussian kernel uses sum over $\\pi_{R}^{-1}(y)$, is this an infinite sum by the definition of $\\pi_{R}^{-1}(y)$? How is it computed in practice?\n\nMinor question\n\n3. In Deep Network paragraph of Section 4, it says \"ResNet32\", but it is \"ResNet34\" in Figure 2.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. It provides a nice alternative to the commonly used binned ECE estimator, which has the potential to be widely used in the model calibration literature. The theoretical property of the proposed estimator is carefully studied and the computational complexity is also addressed.", "weaknesses": "1. The major contribution of the paper is the new smooth ECE estimator over the commonly used Binned ECE. The paper discussed several disadvantages or flaws of the binned ECE in the introduction, but I think these flaws are not well demonstrated in the experiments, e.g. \"changing the predictor by an infinitesimally small amount may change its ECE drastically\", \"overly sensitive to the choice of bin widths.\" I think it is beneficial to include some synthetic experiments to demonstrate these problems of the Binned ECE estimator and show how the proposed estimator overcomes them. \n\n2. One property of the proposed estimator is consistent in the sense of (Blasiok 2023). It is different from statistical consistency, I think a bit more discussion on why this property is desirable is helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "QRoPYoFjJ3", "reviewer": "Reviewer_SRwZ", "summary": "The paper proposes a novel calibration metric called SmoothECE based on the use of kernels.\nCompared with the commonly used ECE, which is also referred as BinnedECE, it does not suffer from discontinuity.\nMore importantly, it is a consistent calibration measure and comes with a reliability diagram for visualization (unlike some other proposed metrics).\nEven though SmoothECE relies on the use of Gaussian kernels, it has a procedure to choose the kernel bandwidth, which makes it hyper-parameter free.\nCalibration of classifiers trained on common benchmarks are assessed by SmoothECE and compared with BinnedECE, showing that it performs similar to BinnedECE and is easy to visualize.\nA Python package is developed for this method to use.", "questions": "Can you clarify if SmECE is differentiable?\nIf so, can we include it in the loss while training classifiers?\n\nIn figure 2, what are the shaded areas for the smooth reliability diagrams?\nI thought they are kernel density estimates of the predictions but I don't understand why for (d), the red line is surrounded by that area.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**originality** The proposed SmoothECE is novel so do the theoretical results.\n\n**quality** The proposed method is sound. It's consistency is proved as a result of the combination of the use of reflected Gaussian kernels and the way to set $\\sigma$, which is very neat.\n\n**clarity** The paper is well-written and easy to follow.\n\n**significance** SmoothECE is a drop-in replacement of BinnedECE and can be potentially widely used by the community. Apart from this, as SmoothECE also alleviates the discontinuity problem of BinnedECE (to be confirmed in Questions), it can enable more work that rely on differentiating through calibration metrics, which is very prohibited by BinnedECE.", "weaknesses": "The experiment section is weak.\nIf the proposed method alleviates the discontinuity problem of BinnedECE (to be confirmed in Questions), some experiments showing how it can be beneficial (e.g. optimizing a loss involving the calibration metric) should be included.\n\nThe code is not provided.\nPerhaps the author(s) can use https://anonymous.4open.science to share it anonymously.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "3sBnxNDWZg", "reviewer": "Reviewer_1zec", "summary": "The paper proposes a way to replace the usual reliability diagram with a smoothed reliability diagram, thus resolving some known issues with using binning schemes. The ECE implied by the proposed smoothed reliability diagram is a consistent calibration measure.", "questions": "## Theory/method questions: \n- Page 3 bottom (initial proposal for smECE): I feel that the actual smECE defined in eq. (4) makes more sense than \\widetilde{smECE} de facto, so the \\widetilde{smECE} is slightly distracting. Is there a reason for not just introducing the actual smECE earlier?  \n- What is the reason for picking the fixed point \\sigma*? \n- Theorem 6: is this a good, bad, or ok \"rate\"? (perhaps in terms of the \\alpha_1 and \\alpha_2?) What does it mean in practice? Does the rate show up in experiments? \n- Could you share intuition for Lemma 7 and Lemma 8? \n \n## Experiment questions: \n- The experimental analysis focuses on producing some reliability diagrams. These look nice, but is there a way to show the benefits of the consistency property that is highlighted? \n- Is smECE as useful, less useful, more useful than the usual ECE for comparing the calibration of models?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "While a number of miscalibration measures that use kernels have been proposed, they are not \"human-interpretable\" like an l1-ECE is. In particular, they cannot be plotted on a reliability diagram. This paper thus fills an important gap. The proposed reliability diagram is also principled in that it leads to a consistent calibration measure, in the sense of Błasiok et al. (2023). \n\nThe paper is easy-to-follow, clearly describes the issue that is being targeted, and the proposed solution is well-contextualized with the latest literature.", "weaknesses": "In my opinion, the quality of the paper can be improved with more detailed research and better presentation. I have a number of questions, and I feel at least some of them should be answered before publication. (Thus I have given a contribution rating of 2 since I believe more evidence needs to be provided to show the proposed method indeed solves the problem satisfactorily.) \n\n## Theory/method questions: \n- Page 3 bottom (initial proposal for smECE): I feel that the actual smECE defined in eq. (4) makes more sense than \\widetilde{smECE} de facto, so the \\widetilde{smECE} is slightly distracting. Is there a reason for not just introducing the actual smECE earlier?  \n- What is the reason for picking the fixed point \\sigma*? \n- The discussion of Błasiok et al.'s work should be more detailed for someone unfamiliar with it. After Definition 5, I would expect some comments on why consistent calibration measures are a useful notion.  \n- Theorem 6: is this a good, bad, or ok \"rate\"? (perhaps in terms of the \\alpha_1 and \\alpha_2?) What does it mean in practice? Does the rate show up in experiments? \n- Could you share intuition for Lemma 7 and Lemma 8? \n \n## Experiment questions: \n- The experimental analysis focuses on producing some reliability diagrams. These look nice, but is there a way to show the benefits of the consistency property that is highlighted? \n- Can you show further evidence that the smECE is close to the true ECE in finite samples (on synthetic data)? Fig 1d is one simple setup. \n- Is smECE as useful, less useful, more useful than the usual ECE for comparing the calibration of models? \n\n\n## Minor comments: \n- Page 3 top. \"Thus we have a situation ... consistent calibration measures.\" I agree, and would further add that reliability diagrams are nice because they are interpretable by humans. Thus Widmann et al.'s kernel-ECE is very useful for comparison but its adoption has been limited due to the interpretability (aka, lack of reliability diagram) problem. \n- Page 3 bottom \\tilde{K} is used before being defined\n- Page 5 (center): the methods would in fact apply to any of the binary-reduction-based calibration notions discussed in the paper \"Top-label calibration and multiclass-to-binary reductions\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "qE0GOhCV7J", "reviewer": "Reviewer_MdfL", "summary": "The paper studies the limitations of well-known expected calibration error (ECE) and the associated reliability diagram used for quantifying the miscalibration of a machine learning model. Among the core limitations of ECE, the fundamental ones are: discontinuous functional and impossible to estimate efficiently from samples. The paper proposes smoothECE and a regression method, which is ECE of the smoothed version of the original distribution and so the associated reliability diagram reflects a smoothed estimate of the calibration function. It claims that kernel smoothing allows realizing a consistent calibration measure and it provides a way of choosing the kernel bandwidth. The paper shows that SmoothECE has desirable mathematical properties, including consistent calibration measure and being sample and runtime efficient. Experiments have been performed on Deep Networks, Solar Flares, meteorological data, and synthetic data to showcase the comparison between ECE and proposed SmoothECE.", "questions": "- It is a bit difficult to understand that, how the smooth reliability is visually more interpretable than the binned reliability. \n\n- To what extent, this smoothECE can be trusted as a standalone miscalibration measure?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Calibration is an important aspect of probabilistic predictors as they allow building a certain level of trust in the model’s predictions, therefore studying the limitations of prevalent miscalibration measures i.e. ECE is an important and relevant research direction. \n\n- The idea of applying kernel smoothing with automatic selection kernel bandwidth to the original distribution is simple. It has been shown that the resulting smoothECE has desirable mathematical properties. \n\n- Experimental results have been shown on different scenarios, including deep networks, rain forecasts, and solar flares forecasts.", "weaknesses": "- It would be interesting to see the results of SmoothECE on imbalanced (image) datasets such as SVHN.\n\n- The overall contributions of the paper seem a bit limited as it boils down to applying (Gaussian) kernel to the original distribution for obtaining a smoothed estimate of it (which is already done in the prior work) and a technique to determine the kernel bandwidth. \n\n- The empirical results are missing experiments on more image datasets, especially that cover out-of-distribution scenarios, and different types of networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)