Information-theoretic Generalization Analysis for Expected Calibration Error
Authors: Futoshi Futami
Masahiro Fujisawa
Venue: NeurIPS 2024 poster (2024)
Keywords: information thery
information-theoretic generalization error analysis
generalization error
expected calibration error
calibration error
binning
Primary area: learning_theory
TL;DR: This paper offers a comprehensive analysis of the expected calibration error using the information-theoretic generalization analysis.

Abstract: While the expected calibration error (ECE), which employs binning, is widely adopted to evaluate the calibration performance of machine learning models, theoretical understanding of its estimation bias is limited. In this paper, we present the first comprehensive analysis of the estimation bias in the two common binning strategies, uniform mass and uniform width binning.
Our analysis establishes upper bounds on the bias, achieving an improved convergence rate. Moreover, our bounds reveal, for the first time, the optimal number of bins to minimize the estimation bias. We further extend our bias analysis to generalization error analysis based on the information-theoretic approach, deriving upper bounds that enable the numerical evaluation of how small the ECE is for unknown data. Experiments using deep learning models show that our bounds are nonvacuous thanks to this information-theoretic generalization analysis approach.

Information-Theoreti Generalization Analysis for Expected Calibration Error
Futoshi Futami"
Masahiro Fujisawa" t RIKEN AIP
Osaka University / RIKEN AIP futami futoshi. es@osaka-u ac. wwwtossh.essssaaaaaaa..
nasahroo..fjssaaerrkeu.
Abstract
While the expected calibration error (ECE), which employs binning, is widely adopted evaluate the calibration performance of machine learning models, the- oretical understanding of its estimation bias is limited. In this paper, we present the first comprehensive analysis of the estimation bias in the two common binning strategies, uniform mass and uniform width bimning. Our analysis establishes up- per bounds on the bias, achieving an improved convergence rate. Moreover, our bounds reveal, for the first time, the optimal number of bins to minimize the esti- mation bias. We further extend our bias analysis to generalization error analysis based on the information-theonn the numerical evaluation of how small the ECE for unknown data. Experiments using deep learning models show that our bounds are nonvacuous thanks to this information-theoreticc generalization analysis approach.
approach, deriving upper bounds that enable
Introduction
Ensuring reliable predictions from machine learning models holds paramount importance in risk- sensitive applications such as medical diagnosis [18]. To achieve this, it is essential not only to evaluate the accuracy of the point predictions models but also to precisely quantify the associated uncertainty. One effective approach to accomplishing this is to leverage the concept of calibration. In the classification context, the calibration performance is evaluated by how well predictive proba- bilities of a model align with the actual frequency of true labels, and close correspondence between them indicates that the model is well calibrated [7, 42]. Unfortunately. machine learning models are often not well calibrated [11, 24], prompting extensive research their calibration performance both theoretically and numerically. In this paper, we assume binary classification problem.
To evaluate the calibration performance, we often use the calibration error or true calibration error (TCE) [12, 31, 10]. This evaluates the disparity between the predicted probability of a model and the conditional expectation of the label given the model prediction, instead of the true label frequency. However, analytically computing the TCE challenging, primarily due to the intractability of the conditional expectation. One way to address this issue is by using the binning method [48]. This method enables the estimation of conditional expectations by dividing the probability range [o. 1] into B small intervals called bins and comparing the empirical mean of predictive probabilities and label frequencies within each bin, utilizing the finite test dataset denoted as S... The obtained estimator of the TCE is termed the (binned) expected calibration error (ECE).
Given that the ECE estimates the TCE, it is crucial to theoretically explore the bias between them, termed total bias in this paper, confirm the accuracy of calibration evaluation using the ECE. Fur- thermore, is vital identify the conditions under which our training algorithm achieves low ECE or TCE for unknown test datasets. This can be paraphrased as the importance of conducting gen- eralization error analysis under the ECE and TCE. Nevertheless, research on these aspects remains
"Equal contribution.
CCorresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

scant. Existing studies have only shown that the ECE underestimates the TCE [24] and have only analyzed the bias caused by a finite sample under specific conditions such as using uniform-maat masss binning (UMB) [13, 12]. Consequently, there remains a significant gap in the comprehensive the- oretical understanding of the biases introduced by binning (termed binning bias) and the statistical bias resulting from the use of finite test data samples. While these studies have concentrated on sce- narios utilizing UMB, there has been no corresponding analysis for uniform-wind width binning (UWB), which is also frequently employed in practice. This limitation could be due to the challenges posed by UWB, where the equal partitioning of probability intervals can lead to bins without any samples, making bias analysis difficult. Unfortunately. to the best of our knowledge, there are also no existing generalization analyses on the basis of the ECE and TCE.
To address the challenges outlined above, in this paper. we comprehensively analyze the ECE for both UWB and UMB. We derive the upper bounds of the total bias of the ECE using a newly derived concentration inequality (Corollary 1). Our bounds improve the order of convergence regarding the bin size. Furthermore, the optimal bin size that minimizes the total bias successfully derived from these results. With this optimal bin size. the total bias of the ECE exhibits rate of O(1/n 1/3) for both UWB and UMB, where The the number of test samples (Eq. (13)).
This bias analysis leads to our second novel contribution, providing the generalization error analysis for the ECE and TCE (Theorems 4 and 5) using the anformation-theoretti (TT) analysis [43, 15, 17]. Directly applying the existing IT analysis is, however, challenging because the ECE on the training dataset is longer represented by the sum of independent and identically distributed (i.i.d.) random variables w.r.t. the trained model. We circumvent this problem by applying a novel exponential moment inequality derived in the process of our bias analysis described above. We further connect our results to classical uniform convergence theory using the metric entropy of function classes, which allows us to discuss the convergence rate of our bounds under a broader range of models (Theorem 6). Using our generalization bounds, we theoretically explore the existing conjecture [11, 24] that recalibration with the reuse of training data leads to severe overfitting. We then show that our analysis successfully characterizes such an additional bias (Theorem 7). Numerical experiments using deep learning models confirm that our bound is nonvacuous and validate our findings.
2 Preliminaries
For a random variable denoted in capital letters, we express its realization with corresponding lower- case letters. Let Px denote the distribution of X, and let Prjx represent the conditional distribution of Y given X. We express the expectation of random variable X as Ex The symbol / 1(X; Y) represents the mutual information (MI) between X and Y. while [(x; Y IZ) is the conditional MI (CMI) between X and Y given Z. We further define [n]] {1, {1,..., n for n E N.
X J' be the domain of data, where X' and y {0, 1} are input and label spaces, respectively. Suppose D represents an unknown data distribution, and let Ser == (mm))= denote the training dataset consisting of n samples drawn i.i.d. from D. We also define the test dataset comprising the samples as Stc ~ Dite. Let fa X² -> [0, 1] be parametric probabilistic classifier that outputs a prediction of the probability Y = 1, and we denote its parameters as w E W C Rdd We consider randomized algorithm A: 2" x R + W. where R E R is the randomness of an algorithm, independent of all other random variables. For fixed R = r and Sur = s, A(s, r) is a deterministic function and f((s.)) (2) is the prediction at point x given s and r. We evaluate the accuracy of the trained predictor fo using the loss function 1 : W 2 + 1,, where I(A(ss)) r), 2) denotes the loss incurred by the prediction fa (x) for label y- For example, the zero-one loss is commonly used to evaluate the accuracy. Then, the training loss is given by Ls., = -m I(A(Str. R), Zm) and the test loss is given as Lg == I(AASS,, R). Z) where ~ D. We also define the expected version of them as Ls := RLs, and LD- = E...Z.RLZ.
We consider binary classification in this paper. Let
2.1 Calibration error and its estimator
In this section, we introduce a calibration metric and its corresponding estimator. The most widely known metric is the true calibration ervor (TCE) [31, 10, 12) defined as
TCE(f.)= = E [ [f (x) - f. (X)I],
(1)

---

conditioned on W w. Unfortunately, evaluating the TCE directly is challenging due to the intractable calculation of E (X)).. To avoid this issue, we often use the binning method [1 1, 48, 49]. This method estimates the TCE by partitioning the prediction probability range [0, 1] into B intervals I = {T.)_1 (called hins) and averaging within each bin using the evaluation dataset S. == mm mm= E 2"h where we assume ne 2 2B. For instance, we have S. Ste when the test dataset is used for evaluation. The TCE estimator on the basis of Z, with Se, is defined as
B EC = Epilfis. - It.s.h
(2)
where 1/: = Em= (u(xm)) P: == Mel =
- I (emm)),, (mm), ) and Vt.s. =
nhe
[4:1 Em=1 1 (m This estimator is called the expected calibration evvor (ECE)
There are two common methods construct I. One is uniform width binning (UWB) [11]. which divides the [0, 1] interval into equal widths as follows: I; = ((i 1)/B,
i/ B] for i in [B]. The other approach uniform mass binning (UMB) [48], which sets I so that each bin contains an equal number of samples. That is, we calculate predicted probabilities as fm f (zm) for Im E Se, let fim) be the m-th order statistics of , fn.). and then set 11 = (0, uı]; 12 = (i,, U2]: I = (uB-1, uyl for b E [B-1] 1] and ub = b(L.)/B)) with ug 1. Here, [x]] == max m
S x).
2.2 Biases of ECE and limitation of existing work
Given that the ECE is an estimator of the TCE, it is of practical importance to understand the nature of the bias defined as (TCE(f)) - ECE(f S.]l. We call this bias the total bias. To facilitate the total bias analysis, we adopt the following definition of the binned function of fw [24]:
B
fz(x) = Σ (X E I.] (o))E
(3)
2=1
which represents the conditional expectation within each bin. When we evaluate the ECE on Se = Ste. we expect that ECE(fw, Ste) will converge to TCE(fz) = [|E[ - fz())) with increasing Rie. However, TCE(fz) underestimates TCE(fw) [24, 10], that is,
TCE(fz) I TCE(fw),
(4)
which implies that ECE(fw) is biased estimator of TCE(fw). Therefore, comprehending the extent of this bias is crucial to an accurate calibration performance evaluation. Nevertheless, pre-
vious studies [24, 13, 12] have exclusively focused on the statistical bias in UMB, defined as (TCE( ECE(Sw: St.)l as discussed Section 1. This brings us to an analysis of the total bias for both UWB and UMB.
2.3 intormation-theoreee generalization error analysis
We now briefly outline the IT analysis using the evaluated CMI (eCMI) [34] that we utilize in study. Consider Ž E znx as an x 2 matrix, where each entry is drawn i.id. from D. We refer to this matrix (UI...., Un) Uniform( (0, 1)") independent of Ž. We denote the m-th row 2m with entries (Zm,0. Zm.1). In this setting, we consider Zo (Zm,um )==1 as the training dataset and Zo = (2m, (mm.0.))) ) as the test dataset with T4e = n, where Um = 1-Um- With these notations, we can see that L2 = 2m=1 (AAZz, R), Um, corresponds to the training error since Ls E2 Also, Lg = 1 Σ m== I(A(Zu, R), Zm.....) ( corresponds to the test error, LD = Æž The described settings, called the CMI setting [17], lead to the following theorem.
supersample. Each column of Ž has indexes {0, 1} associated with U
Theorem (Theorem 6.7 in Steinke & 7akynthinou [34]). Under the CMI setting, we have
E Ez,nv - L / 2 (cCMI(() + log 2),
(5)
3 Although some existing studies refer to Eq. (1) as the ECE, in this study, we follow the definitions of the TCE and ECE outlined by Roelofs et al. [31] and Gruber & Buettner [10] to make clear distinction from the estimator obtained through binning.
3

---

where eCMI(L) = [(i, R), 2) and [(A(Zu, R), Z) is an n. x 2 loss matrix obtained by applying ((A(Zu, .) elementwise to Z.
The reason we focus on ITT analysis is that it enables algorithm--ependdnt analysis. The conventional uniform convergence theory [37] focuses solely function classes derive bounds. However, recent findings suggest that models trained by some algorithms are not well calibrated but show high accuracy [11, 24]. Therefore, seems essential to incorporate information about not only the function class but also the algorithm in the ECE analysis. Hence, in this paper, we adopt the eCMI framework, which is the generalized analysis approach that maximizes the use of algorithmic information. Furthermore, because eCMI-based bounds can be estimated using training and test data, the generalization performance of the model can be evaluated numerically, making it desirable from a practical standpoint.
3 Proposed analysis of total bias in binned ECE
Here, we present our first main analyses of the bias analysis of the ECE as the estimator of the TCE. Our analysis primarily focuses on the total bias defined follows:
Biastot (Jws Ste) = (CC((()) ECE(S", S.o)l-
(6)
We can derive the following upper bound of Eq. (6) by using the triangle inequality,
Biastot (fws (ww See) < Biassin (fw: fz) + Biasstat (Fw: Ste),
where Biassin (Fws fI) = (C - TCE(fz) and Biasstat (fws S Ste) [TCE(S>)
ECE(Sw., S. We call the former as the binning bias, which arises from nonparametric estimation via binning, and the latter the statistical bias caused by estimation finite data points.
Before showing our results, we introduce the following assumption that is also used by Gupta & Ramdas [12] and Sun et al. [35]:
Assumption 1. Given W = (x) is absolutely continuous w.r.t. the Lebesgue measure.
This assumption means that (x) has a probability density, and it is satisfied without loss of gen- erality as elaborated in Appendix C in Gupta & Ramdas [12).
From Eq. (7), we can obtain an upper bound on the total bias by analyzing the binning and statistical
biases separately. First, we present the following results of our statistical bias analysis:
Theorem (Statistical bias analysis). Given W = w, under Assumption I, we have
TCE(f2) < Es,, ECE(ffs Ste),
(8)
2B Thke
(for UWB),
Es, Biasstat (far, Sto) S
(9)
2B 2
2B
(for UMB).
Proof sketch. First, we reformulate the ECE as ECE(f Swe) = ER LE (X.Y) (Y
1 fu (X)e,, and the TCE as TCF(fz) EB Σi= the empirical distribution of Ste. The proof of this reformulation is shown in Appendix C. Thanks to these transformations, our analysis does not have the problem that the UWB method can lead bins without any samples. By evaluating the exponential moment for UWB using McDiarmid's inequality under these reformulation, we have, for any X 2 0.
(Y
( where Sim. is
A.s. Biass (fw, Swe) < log e, MTTCE()) BCE(F < B log 2 X2/(2n..).
(10)
Using this, we can derive both the bias and the high probability bound. We can derive similar bound for UMB. The complete proof is provided in Appendix D.1.
Eq. (8) shows that ECE(Sw, Sto) overestimates TCE(Sz) in expectation. Combined with Eq. (4), we can see that ECF(/w Ste) cannot be the upper or lower bound of TCE(J.) expectation. This emphasizes the importance of the rigorous bias analysis of [TE((w) - ECE(f Ste)l-

---

Comparison with existing work: Eq. (9) provides better generality and a tighter bound than prior results. Our bound exhibits (( B/Bee) in expectation (and Op(y ( B/nec) in high probability w.r.t. Ste proved Appendix D.3.). In contrast, the existing analysis [13, 12, 24] provided a similar bound focused on UMB scale as O(B/ (ne) in expectation (and Op(y log B/ B/mte) in high prob- ability). In terms of generality, our derivation techniques can be applied to both UMB and UWB, whereas existing bounds are limited to UMB.
Pros of our proof technique: The proof procedure in existing work [13, 12, 24] involves (i) showing that the samples assigned to each bin are i.id., (ii) applying the Hoeffding inequality to derive concentration bounds separately for each bin, and (iii) summing up these error bounds across all bins. This approach results in slow convergence and only applicable UMB. On the other hand, our approach simultaneously handles all bins by utilizing the concentration inequality in Eq. (10) and provides the improved upper bound and can be used for both UWB and UMB. We offer more detailed explanation of this in Appendix D.6.
Next, show the results of our binning bias analysis under the following common assumption in the nonparametric estimation context [36].
Assumption 2. Given W = w, [())] satisfies L-Lipschitz continuity.
Theorem (Binning bias analysis). Given W w, under Assumptions I and 2, we have
H+
(for UWB),
Ess Biasbin (Swr fI) S
(11)
(1+
2B Tha
2og B
2B New
(for UMB).
Proof sketch. In Appendix D.4, we show that
Biassia (fwr fz) s ff
E| + (X) fz(X))-
We then derive the upper bound of the right-hand side from the definitions of bins in Section 2.1. For UWB, the upper bound is O11/B) B) because UWB divides the interval into equal widths. For UMB, need to evaluate how samples are split by bins. The complete proof is in Appendix D.4.
Substituting the results from Theorems 2 and 3 into Eq. (7) yields the following upper bound for the total bias.
Corollary 1. Given W = under Assumptions I and 2, we huve
1+h
2B log
(for UWB),
Es. Biasrot (Sor, Sto) S
Bhee
(12)
1+4 + (2+
2B Boggg Nio B
2B Nee
(for UMB)
The above result evidently implies trade-off concerning B. Intuitively, this indicates that while a larger number of bins, B, improves the precision of fu estimation, accurately estimating the conditional expectation requires greater sample size. We further determine the optimal number of
bins by minimizing the upper bound of Eq. (12) w.r.t. B, which results in B = Om 1/3, and gives
Es, Bias (fw, See) = 113)
(13)
Since the bin size has been tuned heuristically in practice, this result sheds light on how to choose it theoretically for both UMB and UWB rigorously.
Regarding tightness of Eq. (12): As we mentioned in Section 2.1, we use binning methods to
estimate intractable | (x)] in the TCE evaluation. Thus, the TCE evaluation can be viewed
as nonparametric estimation of a one-dimensional function on [0, 1]. According to Tsybakov [36],
the error in such nonparametric regression cannot be smaller than (11/n Our bound is convincing because its order aligns with that in Tsybakov [36]. We provide a detailed discussion in Appendix F.6 and F.7.
1/3) under Assumption 2.
We finally remark that the total bias of binning using UWB and UMB cannot be improved even assuming the Hölder continuity for B| (z)) instead of Assumption 2. This is because the binning bias includes the error term f. (X) - fx(X) = OL even under the Hölder continuity. Thus,
1/3, under the optimal bin size suffer from the slow converge Es,, Biasco Ste) ((L/11)
5

---

B= B=
-(mee (13))
(see Appendix D.5 for this proof), According to Tsybakov [36], the lower bound of
the nonparametric estimation ( (1(++1)) under 3-Hölder continuity. This implies that the binning method cannot leverage the underlying smoothness of the data distribution. Thus, the slow convergence is the fundamental limitation the binning scheme for both UMB and UWB.
Generalization error analysis in calibration error
Another goal of our study is to identify the conditions under which a training algorithm achieves low ECE or TCE on unknown data by analyzing the generalization error, which has been overlooked in previous studies. In this section, we present our theoretical analysis regarding these points.
4.1 Information-theoreti analysis of generalization error in ECE and TCE
The expected generalization enror between the ECE and TCE can be defined through the total bias notion, that is, RRS,, Biassor (fw, Sr) == S... TCE( - ECE ( S,,) In this section, we derive the upper bound of En, En,s, Bias (fw: Str) by analyzing the statistical and binning biases in the same manner as in Section 3. First, we derive the following upper bound of the statistical bias, Biasstat (fw, Su) == (TCE(fz) ECE(fu: Se,), using similar proof technique as in Theorem 2.
Theorem 4 (Generalization error bound of the ECE). Under the CMI setting and under Assump- tion 1, for both UWB and UMB, we have
8(cCMI()) + B Blog
ER,s., Biasstal , S ER ER.St..s St. (ECE(fw, Ste) ECE(fw, $
n
(14)
where eCMI(() = [(1; (1) and ī(U, R, 2) = |ECE(fA(22...) - Zu)1.
(15)
Proof sketch. We reformulate the ECE similarly to the proof outline in Theorem 2. Errors between the losses evaluated on the training and test data are similar to the left-hand side of Eq. (5); however, directly applying Eq. (5) leads to a suboptimal rate of O B/ BBBB/v /n). Therefore, we derive the extended version of Eq. (5) by correlating bins according to Eq. (10) and combining this with the Donsker- Varadhan lemma. The complete proof can be found in Appendix F.I.
Comparing Eq. (14) with Eq. (9) in Theorem we find that eCMI measures the additional bias that arises when evaluating the ECE using training data that are dependent on the trained model fo instead test data, which are independent ECE(/w: S.r) can be regarded as the expected generalization error of the ECE, and eCMI is the dominant term of the generalization gap. Therefore, if the trained model has a sufficiently low eCMI, it achieves good generalization performance in terms of the ECE. The behavior of eCMI clearly affects the convergence rate of this bound, which is discussed in Section 4.2. Moreover, our bound and eCMI are numerically evaluable and we confirm that our bound is numerically nonvacuous (see Section 6). We also show the application of our bound the setting of recalibration in Section 4.3.
In other words, the term ER,S (ESss,/EE(/vvr Sta)
In Appendix E, we derive the binning bias under the training data similar to Theorem 3. By com- bining this result with Theorem 4, we obtain the following generalization error bound for the TCE. Theorem 5 (Generalization error bound of the TCE). Under the CMI setting and under Assump- tions and we have
1+L
((CCMI()++ log
(for UWB), (16)
ER,S, Biastot (fw, Sw)s
1+L
8 ((cCMI(+BB log 2)
+(1+L)
2(CMMI
(for UMB)
In the above, cCMI()) is defined Eq. (15) and
[CMI == T T( (2);
(17)
where & denotes the n. X 2 matrix obtained by projecting each element of ā, and S (8) is the 2 matrix calculated by the elementwise application of A(Zu, (-) to ã.

---

When comparing Eq. (12) with the above results, it is observed that an additional bias, eCMI (in- cluding fCMI in UMB), derived from training data arises. This implies that the trained model shows a low TCE when it sufficiently reduces these additional biases and achieves small ECE. From a practical viewpoint, this implies that our bound can potentially be used as a theoretical guarantee for some recent training algorithms, which directly control the ECE under the training dataset [23, 29, 38j. Our theory might guarantee the ECE under test dataset for them.
Another interesting implication from our bounds is that we can derive the optimal bin size to mini- mize the upper bound in Theorem 5. If (CMI(( and fCMI are sufficiently small compared with n, for example, (log n) (we discuss this in Section 4.2), then, the optimal bin size can be derived as B (nn//3) by minimizing Eq. (16) w.r.t B. Such an optimal / leads
(18) According to Eq. (13) and the above result, we can anticipate that Eg.s., Biastot Str) is much smaller than Es, Bi (fw, Ste) because the number of training data is often much larger than that of test data (n >> The). This implies that if the model generalizes well, evaluating the ECE using the training dataset may better reduce the total bias than that using test dataset. Although proposing such a new TCE estimation method is beyond the scope of this paper, this represents an important direction for future research.
ER,S., Bias (fw: = O (log n //3//3).
4.2 On the behavior of eCMI and the order of total bias on metric entropy
In this section, we analyze how additional biases, i.e., eCMI()) and ICMI, behave. The initial ob- servation is that the following relation holds [17]: eCM1()) S fCMI < ((W; S). Furthermore, we can see that I(W;)) S) = (logn) under certain constrained conditions, such as the conditionally i.idd setting when fw (ar) is the underlying probability model for p(y|2; w) with W being com- pact and holding appropriate smoothness assumptions [14, 44]. Furthermore, fCMI can be upper bounded when the algorithms satisfy the various notions of stability [34]. For example, differential private algorithms and stochastic gradient Langevin dynamics (SGLD) [41] algorithms are included in this argument. A more detailed discussion can be found in Appendix F.4.
These arguments, however, hold true only for specific models and algorithms. Therefore, we extend Theorem 5 by utilizing the concept of metric entropy to overcome this issue.
Theorem 6 (Metric entropy). Let F be the function class fwr belongs to. Suppose that FF with the metric || oll has the metric entropy, log (FF, || -llos, 5), with the parameter 8 (> 0). That is, there exists set of functions Fs (J,,----SA((EF I| .)3 that consists of ê-cover of F. Then, under the CMI setting and under Assumptions I and 2, for any 8 E (0. 1/B] and for UWB, we have
+ L
/BB log 2N 11,, 6/B)
ER,S, Biastat (Jw, Std)
+ (2 1.88 +
(19)
B
n
See Appendix E.3 for the proof. Theorem 6 connects the IT-based bound to the uniform convergence theory. With this result, we can discuss the optimal number of bins across a broad spectrum of mod-
els. For example, we can obtain (NF, || | 6) > (Zg) d when fw is d-dimensional parametric function that is Lo-Lishhiitz continuous (Lo > 0) [37]. leading to the following upper bound:
+ 2L
8dB log(2Lo
ER Biastot (fw, Sw) <
(20)
B
n
where we set = O(1/B). This bound is minimized when B = On)2/3), resulting in a bias of Ollogn/n///0 which is consitent with Eq. (18).
The drawback of the above bound is that it depends on the model's dimensionality explicitly, making them unsuitable for large models such as neural networks. To address this issue, we can use the different combinatorial properties, such as the fat-shattering dimension. See Appendix E.3 for the detail.
4.3 Generalized error analysis recalibration and bias due to reuse of training data
As an application of our generalization emror bound, we analyze recalibration using a post-hoc re- calibration function, which is used when the trained model is not well calibrated. We focus on the
7

---

recalibration using UMB with recalibration data [35, 12]. In this setting, we first split overall data into the training, recalibration, and test datasets (see Appendix for details of this splitting strat- egy). After training Jur using the training dataset, we construct the recalibrated function h using the recalibration dataset Sre as
1 (1) Σ Sr fu(w)E
(21)
where yi,8, is the empirical mean of {ym Jim E Sre in the i-th bin defined as in Eq. (2) and fre is the number of the recalibration dataset. In short, Eq. (21) provides an estimator of the condi- tional expectation of Y given (x) by setting S. Ste. Gupta & Ramdas [12] clarified that the statistical bias of Eq. (21) is given by Es.. TCE(hI.s..) = [| |Az, (X)] - hz (X)]l Op(yB log ()eS. Since need to split the overall data into three datasets, this approach could be dataset may solve this problem some extent, it has been suggested that this method may cause performance degradation due to overfitting [24, 12].
and could result in a very loose bound. Although reusing the training
Our contribution here is quantifying the bias caused by overfitting due to the reuse of training data by utilizing our generalization error analysis in Section 4.1 as follows.
Theorem (Recalibration reusing the training dataset). Replacing Sie with Sir in Eq. (21), under the CMI setting and under Assumptions I and we have
2(1CM + B Bog
E ER, T.E(,,,EE(...). = ER.S.. Bla.s,, (X)] - 1I (X)] S 2/
where fCMT is defined in Eg. (17).
The complete proof is provided in Appendix E.4. In the above, fCMI corresponds to the additional bias caused by overfitting due to the reuse of S... This indicates that reusing S,, does not negatively affect the order of the bias if [CMI is smaller than other terms, as discussed in Sections 4.1 and 4.2. Since the size of Ser is much larger than that of S.e. the recalibration function ftr.s,, may exhibit a much smaller bias compared to kI, We investigate this possibility numerically in Section 6 by using the tighter version of Theorem 7 provided in Appendix E.4 (Corollary 4).
Related work
We have presented the results of our analyses of the total bias in the ECE and the generalization error for both the ECE and the TCE. Existing studies have primarily focused on the statistical bias, with little attention given to the binning bias. Gupta et al. [13] and Gupta & Ramdas [12] examined the statistical bias associated with UMB, but they did not address the binning bias as we did. In contrast, Kumar et al. [24] studied the binning bias but did not specify how this bias depends on n and B. Moreover, most analyses have concentrated on UMB and UWB has not been thoroughly analyzed. As outlined in the proof of Theorem 2, our approach allows us to analyze UWB even in cases where some bins do not have any data points by employing our reformulation and concentration inequality. It important to note that Roelofs et al. [31] studied the numerical behavior of the total bias in some practical models, whereas we focus on the theoretical aspect of the total bias. Recently, Sun et al. [35] have derived the optimal number of bins under the recalibration with UMB. Compared with this, we derived the optimal number of bins for UMB and UWB without recalibration under a similar Lipschitz assumption. This leads to the discussion of estimating the TCE from the nonparametric estimation. An additional discussion is summarized in Appendix F.
We have extended the existing eCMI bound [34, 15, 17, 40], which is used for analyzing general- ization performance in terms of prediction accuracy, calibration analysis. In addition, whereas existing eCMI bounds numerically evaluated eCMI and fCMI for discrete random variables such as zero-one loss, our analysis is conducted on continuous random variables as shown Eq. (15). We show in the next section that our bounds are still nonvacuous even for the continuous random variables. The IT analysis was also utilized by Russo & Zou [33] to study the bias caused by data reuse. Our analysis can be seen as extension of this approach to the ECE and recalibration.
8

---

Cap (ee calbrate)
Bound Gap (betler calibaat))
Daze calbtrste)
(batier brsta)
Buen lest
Figure 1: Behavior of the upper bound in Eq. (12) as n increases when UWB used. The following two terms: less calibrate and better calibrate refer to [ (0.5, -15) and / = (0.2, -1.9). respec- tively, where the former setting produces a worse value of the TCE estimator.
MNIST (Adam)
MNIST (SGLD)
CIFAR-10 (SGD)
CIFAR-10 (SGLD)
-2
UH5.3-52
Figure 2: Behavior the upper bound in Eq. (14) for various B as n increases (mean + std.). For clarity, only the results using UMB are shown. The ECE gap is shown for B |n|/3| since the change in B did not result in significant differences. We refer to Figure 5 in Appendix H.3 for detailed analysis of the relationship between (log-scaled) ECE gap values and bound values across different bin settings.
Experiments
In this section, we present experimental results validating our bounds (Section 6. 1) and the additional bias arising from reusing the training dataset for recalibration (Section 6.2).
6.1 Verification of our bounds
In this section, we empirically validate our theoretical findings Eq. (12), the nonvacuous nature of our bounds in Eq. (14), and confirm the efficiency of the optimal number of bins discussed in Section 4.1.
Experiments on synthetic datasets: We first conducted simple experiments on synthetic datasets following Zhang et al. [50]. In this experiment, we assume the distribution of Y as P(Y 1)
P(Y = 0) 2. and we adopt f.) = P(Y 1 x) 1/(1 + cxp(- the prediction model, where w = {.u. }1} are parameters. Under these settings. we can calculate the closed-form of ([(((((()))) in Eq. (1), which allows us to estimate the TCE through Monte Carlo integration. Next, we empirically evaluated the TCE gap, which is the empirical estimator of E.s., BiasBit (fwr, Sec), by calculating the difference between the TCE estimator and the ECE using UWB. Here, the optimal B that minimizes the upper bound of Eq. (14) is B [2n(1 + L)² /log 2)1/3 where L is estimated to be the maximum value of the gradient of the closed-form of E[ (X)J. We provide the details of the experimental settings Appendix G.I.
31z) as
Figure shows the results. The two leftmost figures show that the TCE gap is O(n when our optimal B is used. The other two figures show that the number of bins achieving the smallest upper bound is closest to the optimal B and its order is O(n -1/3,, where the candidates for are set as {n 1/2 n 1/3 n -1 1/4 2n - 1/2 2n 1/3 2n -1 1/4 3n 1/2 3n 1/3 3n 11/4. These observations show the validity of our theoretical findings through Corollary 1.
Experiments on image datasets: We further conducted two binary classification tasks on MNIST [25] using a convolutional neural network (CNN) and on CIFAR-10 [21] using ResNet. These models were trained using SGD with momentum for ResNet, Adam for CNN, and SGLD for both, following the strategy of Hellström & Durisi [17]. The details of our experimental settings summarized in Appendix G.2. We initially evaluated the sum of the right-hand side terms of

---

Table 1: Comparison of our method with existing recalibration in terms of the ECE gap and its upper bound in Theorem 7 (mean + std.). Lower values are better. We adopted B = [n2/3] J. The bound values for the existing recalibration method origi- nate from Corollary 4 in Appendix E.5. Here, we report the ECE gap as TCE because S......S.. ECE(h
ER. (Y]EE (X)]
S,, S... Ste) (existing recalibration meth- ods) ER.S., [ sh..s, (X)] hI.s., (X)] = ER.S.. S., ECE( Ste) (our recalibration
(x..s..()),
method) from the definition of recalibration.
Dataset
Optimizer
Methods
ТCE
Bound value
Recalib,
.0085 + .0016
.4755
Adam
Our recalib.
.0588 + .0026
.444 + .0000
MNIST (n = 4000)
Recalib.
.0011 + .0025
.8475
SGLD
Our recalib.
.0072 + .0007
.144 + .0000
Recalib.
.0139 = .0010
1.455
SGD
Our recalib.
.0197 .0044
.8665 + .0000
CIFAR- 10 (n- = 20000)
Recalib.
.0109 = .0012
1.455
SGLD
Our recalib.
.0089 + .0006
.0865 .0000
Eq. (14) and the ECE estimated using the training dataset, aiming to ascertain whether the disparity from the ECE estimated using the test dataset was adequately minimal. We call this disparity as We show the
the ECE gap, which is the estimator of St, [[EC[(ww S..) - (.EE(f,wSea results obtained when using UMB in Figure 2. These results show that our bound value becomes less than with appropriate setting of B. We also observed that the bound values decrease with n, whereas these values sometimes become vacuous for small n when is large. Adjusting B could pose challenges; however, notable trend towards acquiring relatively stable nonvacuous bounds can be observed when adopting B |nt//], even though this is the optimal choice only at the upper bound of TCE, as discussed in Theorems and Sections 4. and 4.2. Similar results are obtained when using UWB (see Figure 3 in Appendix H).
6.2 Confirming additional bias due to reusing training dataset in recalibration
In this section, we empirically confirm the efficiency of the method when using the complete training dataset for recalibration, referred to here as the reusing method. Table 1 illustrates that the reusing method reduces the statistical bias of the ECE more effectively than existing methods using inde- pendently created recalibration datasets (nhe 100). We also compared the tighter version of our bound in Theorem 7, Corollary 4, with the bound of the existing recalibration methods presented in Corollary 5 of Appendix E.5. Moreover,
bound values are lower than those for the exist- ing recalibration methods on the test dataset. These results suggest that reusing training data could be beneficial if the trained model generalizes well and eCMI is sufficiently small, as discussed in Section 4.3.
7 Conclusion and limitations
We provided the first comprehensive analysis of the bias associated with the ECE when using the test and training datasets. This leads to the derivation of the optimal bin size to minimize the total bias. Numerical experiments show that our upper bound of the bias nonvacuous for deep learning models thanks to the IT generalization error analysis. Despite rigorous analysis, our analysis still has limitations. Firstly, we focus on the binary classification; thus, the extension of our analysis to the multiclass classification setting is an important future direction. However, the application of our analytical techniques to this setting seems not clear. Additionally, our analysis cannot be applied to the higher-order TCE, in which we use the p-th norm in Eq. (1). These limitations should be addressed in future work to develop a more principled understanding of uncertainty.
10

---

Acknowledgments and Disclosure of Funding
We sincerely appreciate the anonymous reviewers for their insightful feedback. FF was supported by JSPS KAKENHI Grant Number JP23K1 6948. FF was supported by JST, PRESTO Grant Number JPMJPR22C8, Japan. MF was supported by RIKEN Special Postdoctoral Researcher Program. MF was supported by JST, ACT-X Grant Number JPMJAX210K, Japan.
References
[1] Alon, N., Ben-David, S., Cesa-Bianchi, N., and Haussler, D. Scale-sensitive dimensions, uniform convergence, and learnability, Journal of the ACM (JACM), 44(4):615-631, 1997.
[2] Bartlett, P. L. and Maass, W. Vapmik-chervonenkis dimension of neural nets. The handbook of brain theory and neural networks, pp. 1188-1192, 2003.
[3] Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013. ISBN 9780199535255. doi: 10. 00.000/4cmotoo00973119555555355 oso/99780199535555 001.0001.00.0... 0001.
URL httht:s:/// httppp//.....ttt htt.d/i..rg/11..100.0.10
[4] Carrell, A. M., Mallinar, N., Lucas, J., and Nakkiran, P. The calibration generalization gap. arXiv preprint arXiv:22/0.01964 2022.
[5] Clarke, B. S. and Barron, A. R. Jeffreys' prior is asymptotically least favorable under entropy risk. Journal of Statistical Planning and Inference, 41:37-60, 1994.
[6] Cover, T. M. and Thomas, J. A. Elements of Information Theory. John Wiley & Sons, 2012.
[7] Dawid, A. P. The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):00-611, 1982. doi: 10. 101000000114555) 10777777886.
[8] Farghly, T. and Rebeschini, P. Time-independent generalization bounds for sgld in non-convex settings. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang. P., and Vaughan, W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 19836-19846. Curran Associates, Inc., 2021.
[9] Futami, F. and Fujisawa, M. Time-independent information-theorede generalization bounds for sgld. Oh, A., Naumann, T., Globerson, A., Saenko. K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 8173-811111 Curran As- sociates, Inc., 2023.
[10] Gruber, S. and Buettner, F. Better uncertainty calibration via proper scores for classification and beyond. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 8618-8632. Cur- Associates, Inc., 2022.
[11] Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. 2017.
[12] Gupta, C. and Ramdas, A. Distribution-free calibration guarantees for histogram binning with- out sample splitting. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3942-3952, PMLR, 18-24 Jul 2021.
[13] Gupta, C., Podkopaev, A., and Ramdas, A. Distribution-free binary classification: prediction sets, confidence intervals and calibration. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 3711-3723. Curran Associates, Inc., 2020.
[14] Hafez-Kolahi H., Moniri, B., Kasaei, S., and Baghshah, M. S. Rate-distortion analysis of minimum excess risk Bayesian learning. International Conference on Machine Learning. pp. 3998-4007, 2021.

---

[15] Harutyunyan, H., Raginsky, M., Ver Steeg, G. and Galstyan. A. Information -eeemation-thhortiic general- ization bounds for black-box learning algorithms. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 24670-24688 Curran Associates, Inc., 2021.
[16] Haussler, D. and Opper, M. Mutual information, metric entropy and cumulative relative en- tropy risk. The Annals of Statistics,, 25(6):2451-244) 1997.
[17] Hellström, F. and Durisi, G. A new family of generalization bounds using samplewise evalu- ated cmi. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 10108-10121. Curran Associates, Inc., 2022.
[18] Jiang, X., Osl, M., Kim, J., and Ohno-Machado, L. Calibrating predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19 (2:263-274, 2012.
[19] Kozachenko, L. F. and Leonenko, N. N. Sample estimate of the entropy of random vector. Problemy Peredachi Informatsii, 23:9-16, 1987.
[20] Kraskov, A., Stögbauer, H., and Grassberger, P. Estimating mutual information. Physical Review E, 69:066 138, 2004.
[21] Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Uni- versity of Toronto, 2009.
[22] Kulynych, B., Yang, Y.-Y., Yu, Y., Bt asiok, J. and Nakkiran, P. What you see is what you get: Principled deep learning via distributional generalization. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho. K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 2 2168-2183 2183. Curran Associates, Inc., 2022.
[23] Kumar, A., Sarawagi, S., and Jain, U. Trainable calibration measures for neural networks from kernel mean embeddings. In Dy. J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2805-2814. PMLR, 10-15 Jul 2018.
[24] Kumar, A., Liang, P. S., and Ma. T. Verified uncertainty calibration. In Wallach, H., Larochelle, H. Beygelzimer. A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[25] LeCun, Y., Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W., and Jackel, L.. D. Backpropagation applied to handwritten zip code recognition. Neural Computation, (4):541-551, 1989.
[26] Li, M., Neykov, M., and Balakrishnan, S. Minimax optimal conditional density estimation under total variation smoothness. Electronic Journal of Statistics, 16(2):3937-397) 2022.
[27] Loftsgaarden, D. O. and Quesenberry, C. P. A Nonparametric Estimate of a Multivariate Den- sity Function. The Annals of Mathematical Statistics, 3693):0049-1051, 1965.
[28] Mou, W. Wang, L., Zhai, X., and Zheng, K. Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints. In Proceedings of the 31st Conference on Learning Theory, volume 75. pp. 605-638. 2018.
[29] Popordanoska, T., Sayer, R., and Blaschko, M. A consistent and differentiable Ip canonical calibration error estimator. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 7933-7946. Curran Associates, Inc., 2022.
[30] Rissanen, J. Universal coding, information, prediction, and estimation. IEEE Trans. Inf. Theor, 30(4):629 636, sep 2006. ISSN 0018- 8944.4
[31] Roelofs, R., Cain, N., Shlens, J., and Mozer, M. C. Mitigating bias in calibration error es- timation. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pp. 6036-4054 2022.
12

---

[32] Ross, B. C. Mutual information between discrete and continuous data sets. PLOS ONE, 9(2): 1-101. 02 2014.
[33] Russo, D. and Zou, J. Controlling bias adaptive data analysis using information theory. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pp. 1232-1240, 2016.
[34] Steinke, T. and Zakynthinou, L. Reasoning About Generalization via Conditional Mutual Information. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 Proceedings of Machine Learning Research, pp. 3437-
3452. PMLR, 09 12 Jul 2020.
[35] Sun, Z., Song, D., and Hero, A. Minimum-risk recalibration of classifiers. In Oh, A., Nau- mann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 69505-69531. Curran Associates, Inc., 2023.
[36] Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
[37] Wainwright, M. J. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[38] Wang, D.-B., Feng, L., and Zhang, M.-L. Rethinking calibration of deep neural networks: Do not be afraid of overconfidence. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan,
(eds.), Advances in Neural Information Processing Systems, volume 34, pp- 11809-1 11099-1820. 820. Curran Associates, Inc., 2021.
[39] Wang, H., Gao, R., and Calmon, F. P. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. Journal of Machine Learning Research, 24(26): 43, 2023.
[40] Wang, Z. and Mao, Y. Tighter information-theoretie generalization bounds from supersam- ples. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pp. 361 10011133617. PMLR, 23-29 Jul 2023.
[41] Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning, pp. 681-688, 2011.
[42] Widmann, D., Lindsten, F., and Zachariah, D. Calibration tests beyond classification. In International Conference on Learning Representations, 2021. URL URI.attps::/ooeeeeewee.. net/forum? id= bxf89v33...
[43] Xu, A. and Raginsky, M. Information-theoreee analysis of generalization capability of learning algorithms. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[44] Xu, A. and Raginsky, M. Minimum excess risk in Bayesian learning. IEEE Transactions Information Theory, 68 68(12):7935-795, 2022.
[45] Yang, Y. Minimax nomparametric classification. i. rates of convergence. IEEE Transactions on Information Theory, 45(7))2271 1999.
[46] Yang, Y. and Barron, A. Information-thherreii determination of minimax rates of conver- gence. The Annals of Statistics, 27(5):1564 - 1599, 1999. doi: 112214//0//011999 142. URL https: //tp///////////// org/ 10. 100...12/////0/01799919111
[47] Yatracos, Y. G. Lower Bound on the Error in Nonparametrie Regression Type Problems. The Annals of Statistics, 16(3):1180 1187, 1988.
[48] Zadrozny, B. and Elkan, C. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. Proceedings of the Fighteenth International Conference on Machine Learning, pp. 609-616, 2001.
13

---

[49] Zadrozny, B. and Elkan, C. Transforming classifier scores into accurate multiclass probability estimates. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 694 699, 2002.
[50] Zhang, J., Kailkhura, B., and Han, T. Y.-J Mix-n-match Ensemble and compositional meth- ods for uncertainty calibration in deep learning. In Proceedings of the 37th International Conference Machine Learning, volume 119, pp. 11117-11128, 2020.
14

---

A Remarks about the order expressions
Let f.g: R + R. We say f(x) g(x) when there exist positive constants a, b and no such that Vn > Yoo, we have ag(n) - f() S bg(x)) holds. Moreover f(n) & g()) means that there exists positive constant and no such that Vn no. we have [f(n) og(n) holds. This is equivalent to f(n) = O(g(n))
B
The detailed explanation of how the data is split and used in our bounds
Here we remark how the data is prepared and used in our analysis.
B.1
The binning ECE and its evaluation
In the standard supervised learning settings assume that Nall data is obtained i.i.d from data gener- ating distribution D. We express this as Sall = (( Mi) Nail Then the dataset is divided to
Sall = Ser U Ste,
Str n Ste =.
where Str is the training data which is data points and See is the test data points which is the data points. Thus Nau = n + The-
B.1.1 Evaluation of the ECE under the test dataset in Section 3
Here we discuss the evaluation of ECE(Su; Sta), which uses Ste to calculate the ECE in Section 3. This is the most common common approach in practice. We remark that as for the UWB, since we do not use Ste when preparing bins, those Sie are i.i.d. inside each bin.
As for UMB, the situation is bit complicated. Since we use Ste construct bins, it seems that Ste are no more i.i.d inside each bin. Surprisingly. Gupta & Ramdas [12] have shown that the samples allocated in each bin are i.i.d. under UMB method. So using the same Ste for constructing bins and evaluation of the binning ECE does not result in a large bias.
In these ways, only used to learn the parameter W.
calculate ECE(fw, wes Ste). We also remark that the training samples Sur
B.1.2 Evaluation of the ECE under the training dataset in Section 4
discuss the evaluation of ECE(fw. Su), which uses Sur to calculate the ECE in Section 3. Thus, we use the training dataset St for learning W and calculating ECE.
We need to carefully consider how the data is used when considering the result of the UMB in The- orem 4. This theorem provides us the generalization guarantee of the ECE between ECF( Sir) and ECE(Sw, Ste). As for ECF(Sw, S.,) using UMB, we first train fw with St, and construct bins with St, and calculate the empirical mean of each bin with Su. On the other hand, when calculating ECE(fw, Ste). calculate the empirical mean of each bin with Ste and we use the same bins with ECE(fu, S,r,, so bins are constructed using Str in Theorem us with the generalization gap, where we regard that the bins constructed with the training dataset are regarded as part of our trained model in our theoretical analysis.
this sense, Theorem provides
B.2 The recalibration in Section 4.3
When the recalibration is performed, we further split the test data into
San S, U S.e U any common part sets are empty,
where Sur is the training datasets used for learning W, and S,e is the dataset used for the recali- bration. The most widely used approach is the HMMB-ased recalibration. First, we construct bins following the UMB approach using Sre- Then let us express S.e {(z,, ((1,,:)) function
H.g. The recalibrated
hr.s., (x)= (x)==Anss Pn.s.. 1 (a)ET f...... Emre Vm 1 [L(EmE), Eme 1 (alt)E)
B
(22)
im1
15

---

Then Sie is used for evaluating the ECE or test accuracy.
However, since preparing both Ste and Sre is sample inefficient, our idea is reusing training sample Sir with size n even for the recalibration. In our setting, we split the data
Sall Sir U Ste:
S Φ.
and we construct bins following UMB approach using Sur and calculate recalibration function by using Srr
2m Um 1 (am)er Em=1 [ame)l
hI.S..
E Sr.. (x)e
Pr...
(23)
We then finally evaluate the ECE using Ste. So our approach is more sample-efficient.
C Auxiliary lemma and facts
Here introduce auxiliary lemma and facts, which we will use repeatedly in proofs. In this section, we express fw as f to simplify the notation.
C.1 Binning and bias
First, from the definition of ECE in Eq. (2), we can immediately reformulate
FCC((S,S.) Σ TE SX (x)en
(24)
where S. is the empirical distribution of S..
Next we introduce the binned function of f as fz, which is the conditional expectation given bins:
B fz(x) = Σ f1( L(zen Σ E((()))((X) 4.] f())t
B
(25)
==1
f1,(2) ([ e T.).
(26)
The following relation holds:
Lemma 1, We define the test-binned risk as
B
ECE Bin (f) = Σ EX - f(x)) Lxxeu
(27)
then we have
ECE Bin = =
(28)
where TCE(Sz) means the TCE of the function JT-
Proof. By definition, we have
B
ECE (f) =
Σ DY -f())) s(xee]]
Σ
P(f(X) L e 41 (((()))((X) e 4.).
(29)
16

---

where we used the definition of the conditional expectation. On the other hand, We have
TCE(/>)
B - [z(x)|
B
Σ
E [|[[T|/Z(()] - /z(x)) [x())))
Σ P(fz(a) E E E. (=))( e 4.
Σ L) - =[(() E 4Mll
(30)
where we used the tower property. This concludes the proof.
Thus, transform the loss and ECEs by Eqs. (24) and (27)
C.2
Usefuul inequalities
Here we introduce lemmas, which we will use repeatedly in our proofs.
Lemma 2 (Corollary 3.2 in Boucheron et al. [3]). We say that function f X + R has the bounded differences property for some nonnegative constants Cl...., Cu.
(I - F(11,...,,--11 Ti I. ..... kn)) S Ci 1sisn. (31)
sup
Se EX
If Xx,..., Xn are independent random variables taking values in X, we define the real-valued random variable as
Z = f(X
(32)
If f has the bounded difference property with constants C1y...n Cas then we have
Var / -
(33)
1=1
Combining this lemma with Holder inequality, have the following relation,
1
Z
E 7
S
(34)
We often consider the case where -1 < f < 1. This implies that e; 2 for all Then
E | 1
(35)
Another situation is that given function +E (xx)). where f corresponds to the empirical mean of some function g. This implies that c = 2/n for all i. Then
X + [-,, consider
=
E
B[A]|
(36)
Lemma 3 (Used in the proof of McDiarmid's inequality). Given bounded difference function f. for any t IR, we have
E (0((M Xa) - N Xwll]] S Ses Ei c
(37)
17

---

D Proofs of Section 3
D.1 Proofs of Theorem
Proof. Here we express the samples in Ste as 1it m (Xx, mi }.
As for the first inequality, it is the consequence of the Jensen inequality. as follows;
TCE(fz)
Bz'=(xi,))) [(X' - -fw(X') fw
B
The
Σ
E 1n = (m v m) mmi The
Σ
Exr, fw (X (xw)et
B
Ren
E [ (X) Ym me
Σ (Y, fw(( (x()E)
nee
m=1
Es. ECE(fW..W..... Ste):
(38)
where we used the Jensen inequality. As for the second inequality, we separately prove UWB and UMB.
D.1.1 Proof for the UWB
We start from UWB. Conditioned on W, using the relation between the loss and ECEs by Eqs. (24)
and (27), we have
(TCE(f)) ECE(SW, Sto)l
The
1d (x=(X"' [(Y" - fw((X))) I (xm)ee]))
Σ
Σ (Y fwx(X.)) 1w (XLeEL
The
m=1
1 Nen
2"=(X",X") (Y") -f (XX")) (x")en
(Y fw fx(xX)) fw
The
B
nen
(z")
4(Zzm)
(39)
The m==1
where we used the triangle inequality ||a] - |b/| < |a bl for the first inequality and set 4(2)
(y fx)) 1 fw (a)eT,
We use the following relation: for the one-dimensional real random variable X, by Jensen inequality. have
AB| [X] log 1(e
(40)
Then combining with the above, we have
1 Ess. e D. 1 Dm 4(%())
Es.. TCE(f2) ECE(fw, <
age
(41)
18

---

By setting ((e = Egu1;(Z")
1
Em= 4(Z,m) we have
Es e 'Ein 10(K,5e())
-Esu II
i=1
Bse II
(gg(t.Sw)) + (1991155)))
Bg Σ
DB (' (-1)
(42)
Σ
Es
e'
VimoMB=0011
Σ
Es
nen Eme, 4((4)) -i (1
(43)
Pipo,B==0,1
where Em.... Em..... -0- all the combinations that will be generated by expanding II,- in Eq. (42) and it has 2 combinations.
We would like upper bound Es,.e" E (Bgul(2")- (- Tiee Em (.22))) using Lemma 3. For that purpose, here we evaluate cs of Lemma 3. By focusing on exponent, we can estimate 6;8 by
B Σ t(
sup Rig in
1(-1))
E2"l,(Z")
(e(mm)
(#)m
EZ
i=1
The m=1
-t(-1)4. B2"4(Z")
4(<'m))
1((me)
mymmmm
B t(-1)) (11b(=m)) + 1/ (2(m))))
sup
2/m E EZ 1=1
t( t(-1)0t
(- ((ymm Sw (I'me)) 11 sw (e,, +( -w (w(e)))) Sw (w (eI,)
sup
= E2
(( ((-1)aR
(-(wmm (W
Sw (x're)) )) (w ((im - Sw (āmn)) 1 (tm))))ll))
7te
(44)
(45)
Thee
where the last inequality is derived as follows; Here by definition of the binning, each data point is allocated to single bin. This means that for the input r'me> one of {1 fw (af (e,, ) is not zero. 0 holds. A
We refer such index b. Then 1 (w(x" * O the b-th bin and f= similar argument holds for the input H and we refer to the index that the indicator function not zero as which implies 1 (at, * 0 and 1l f ( = 0. Note that such and can be equal and can be different. Thus, although there are 2B indicator functions in Eq. (44), at most only two indicator functions are not zero.
Combined with the fact that V/m.. - (x'mrr) S 1, we obtain Eq. (45). Note that by Assumption 1, (f (fm)) Pse in Fm Ste takes the distinct values almost surely and in the above discussion, do not consider the case when b/ = fnr (x,, for some b holds, which means that the predicted probability is just the value of the boundary of bins.
When we do not assume that Assumption 1, there may be a possibility that b/ B= (H:)) ) for some b holds, which means that the predicted probability is just the value of the boundary of bins. Then,
19

---

at most only four indicator functions are not zero. This results in a worse bound
B _1--1)
sup
Ez)1((2)
(e(zm)
(#m ) Iim &m EZ
i=1
mmm
- -
Ezil((z))
Σ
(x(mm)
l:((me)
mytmm
4t
(46)
Thse
Combined with Lemma 3, we have that
Esy c Ees lo() <
Σ
II
Ez C
EE (- (-m))t(Bmml(("))
mio Dm (.
D1 Pn 0,1 m=1
Σ
II
Ez C Eimi(-1)" (R)r((()))))("")
mae Em 1:(2(n)
U 0.11= m=1
Σ
(11 (
91 Up=01
2 e 6.0.
212
(47)
Combining this with Eq. (41), we have
1 Es.. TCE(/Z) - ECE(/w, Stoll
log E.s. e. '' (2x))((")) Emhe 4(Z
log 2 tmen
Trenn
log
t
+
2nn
B log 2
V
(48)
1tte
D.1.2 Proofs for the UMB
The proof goes similarly as in the case UWB up to Eq.(4 Then we need special care bound the exponential moment since in the UMB, bins are constructed using Ste, and thus the samples are no longer i.i.d. Recall the definitions that f(m) is the m-th order statistics of (f....., and the boundaries of bins are defined by such order statistics u₁ = f([ma//B])>
We define the set B(B), which is the of test data points used for defining the boundaries of bins. We then define Sie as Ste - S(m and thus Sie is the set of test data points, which not used for the boundaries. We express (S (f)(a)) E S(B)
We define k //ab/BB BB,, which is used for defining the b-th bin. Let fix b E [B] and denote u = hb and Ab-1- Then Gupta Ramdas [12] showed that fi41))... 1) are independent and identically distributed given boundary points b/((m.BBBB)) BB-1
BB1 in Lemma [12]. Moreover,
Lemma 2 Gupta & Ramdas [12] showed that let p be the density induced by the distribution P(f((X)) then
() for every i E 1, 11, < < fww),
(49)
where each 7 is independent random variables 8, ((]n(())) This implies that given the bound- ary points defining bins, the data points inside the boundary are i.i.d.
20

---

In order to use this result, we need to eliminate f(n) from the empirical mean of UMB. This is evaluated as follows; using this from the result of UWB, we have
(TC ECE(fw. Ste)l
B
$
Ezul((Z")
4(
Rie m==
B Σ 1=1
18tel
Stel
$ Egul;
( m
+
((
(50)
S5ee
m=1
m=1
m=1
This partition eliminates the boundary point from the empirical estimation. We can upper bound the second term
| ((
2B
4(Z',) m=1
(51)
|Scel m=1
B
which follows directly by definition (see also Corollary in Gupta & Ramdas [12].). Then we have S. TCE(fI) :
Ess, e 2 (2ubl
nse Dmiee ((())))
$ (s( Es,, e E 3xnl((")) To Emerr 4((22)) +.2LB
(52)
Given the boundary point, the above exponential moment satisfies the condition of Lemma 3, since the 4 (Z,,) are Li.d, given in each bin by Lemma 2 in Gupta & Ramdas [12]. This can also be confirmed that for random variables f()). f(me)). given f(). (f()).... f(-1)) and f(+1)...... f(m))) are conditionally independent (this is proved in Gupta & Ramdas [12], especially the proof of Lemma 2). Combined with Eq. (49), given the boundary points, Sue are i.i.d and the size of which is Tite B. Then only need upper bound
1 EEsm
t E. e
1ibal Emer, 4(7%)
Es.
(53)
We can upper bound this similar way as in the case of UWB, replacing nhe with nie B under Assumption 1. Thus, we have
ss (CE(S2) (CE(Jw,S S Bs. e ' -E / [gul:("")
Em=i (((2)))
B loog 2
2B
(54)
The B
Nte
This concludes the proof.
D.2 Comparison with the trivial bound
We remark that for UWB, also upper bound in the following way;
nre
Es.. (f)(
ECE(fw, Ste) < Es..
Σ
Ez"I(Z"")
(Z
The
B
1
Es...
Var
(((m)
The
1=1
m=1
B
B
< EsS
(55)
Vise
1=1
where we used the triangle inequality ||a| |b|| < la b) for the first inequality and set (,2)
(y- -w)()) 1 fw(e)),, Note that since 1 S 4(2) S 1, we can use Eq. (36). However, since we did not use the property of the indicator function, this suffers from the slow convergence of B.
21

---

D.3 High probability bound
the main paper, we present the expectation bound. On the other hand, as shown in the above proof, we evaluated the exponential moment. Thus, we can obtain the high probability bound directly,
Corollary 2. Under the same assumptions in Theorem 2, for any å (0, 1), we have
B log + log !
Prrea
(TCE(f)) ECE(fw,Su) &
2 1
(56)
Thee
This means the statistical bias is Op( B/mr))
Proof. Using the proof Theorem 2, and chernoff-bounding technique, for any O, we have
Ps,. ((TCE(fz) ECE(fw, 2 E) S tEE,,,, ' 1 3xnli
D (((2))))
mie
[(-ne) 201e
I 2 e
(57)
By setting t = ne then
Ps.. ([TCE(fz) -ECE(f,, Sto)1 2 5
Peg 2 201e
(58)
and setting 5 23e 20
we have that
B log + log
Ps.e
[CC((f)) - ECE(fw.Su. 2 /2
S 8.
(59)
Tle
D.4 Proofs of Theorem
Proof. We use the following lemma to study the binning bias.
Lemma 4.
TCE(fz) & TCE(F.) < + BBC fz(X).
(60)
This implies that
(CE(ft)) TCC((=)) EY
- E|Y [x(]]] + El) fx(X)).
(61)
Proof. The first incquality has been proved in Proposition 3.3 in Kumar et al. [24].
22

---

The second inequality is proved as follows;
TCE(fw) = E [| [x(Xi]]
Σ El (x)en, Eu fx((I
I.]
B
P ( -1 E
4,]
B
(X) E -0 E AJ]l
e (x) 41 (X)6 E 4J
Σ P (1)EE) E 1J - E 1.).
(62)
In the above, the second term corresponds to (CE(fz).
As for UWB, from Lemma 4, we have
(CF(f)) - TCF(J=) BY - -XY] E)) - fz(X)) S
B + B
(63)
where we used the fact that with UWB, we split the function with equal width 1/B and used the Lipschitz continuity the function.
Next, we focus on UMB. To analyze the binning bias of this, we focus on Eq. (50). We replace the loss 4m (2) in that equation with
1 (w)etm
4m (2)
(64)
Then, the first line and second line of Eq. (50) can be rewritten
The
Σ (())(x)) E Im)) P(T)) Σ
E Ezul,
(77%)
(65)
where P(T,) the empirical estimate of the binning probability P(Tm). The right-hand side can be bounded in the same way as Appendix. D.1.2, which requires evaluating the exponential moment. The proof goes the same way, that is, we utilize the results of Gupta & Ramdas [12] and the upper bound of the exponential moment. The procedure is exactly the same. Thus, we have
B
2B 1ogg2
2B
(z) 1m)) - P(L)) s
(66)
[The
B) The B
By definition, we put equal mass in any bin, thus,
1+
P(L)
Thn
B
from the proof of Theorem 3 in Gupta & Ramdas [12].
23

---

Thus, by the Jensen inequality, we have for any E [B],
1
/
2B log 2
2B nite
P(fu(x) E Im)) s
V (ne B)
(67)
B
Combining these results, the binning bias is upper bounded by
(X) fz())
B
Σ P(fo(X) E (X) E ET] (x) i=1
2B log? 2 (Nte B)
2B The
E 41 (X]
fw (x)]lflw(X E 41)
*
(68)
We use the fact that (X) (X) S f(L/BD) -f holds by the definition of the UMB, which is the largest difference of the bins. Then
[X)] (X) E 4. fw((X)lfw(X) 1.) -
fLni/BB) ((((()-)//B) S
(69)
Combining the above, Then we have
2B log 2 (Tre
2B The
(x) - fz(X)) s +
(70)
B)
As for the (X)
by the assumption the Lipschitz continuity, we simply
multiply I. to the above and obtain
1
2B log 2
2B Nie
E - BYY)+(()]]]]I (EIS fx(X) S
B
V
nNe
B)
(71)
This concludes the proof.
D.5 Hölder continuity does not improve the total bias
In the nonparametric estimation, imposing the higher order smoothness improves the bias order. According to Tsybakov [36], the lower bound is O DFT) if we assume 3-Hölder continuity.
In our total bias analysis. the statistical bias not improved by this assumption. As for the binning bias, if we assume that E fur satisfies 3-Hölder continuity with constant M for all the order, then obtain that for UWB,
M
1
(CE(()) - TCE(A2) < EE fo (X) EY (12 + fz(X)
<
+
B
B
(72)
Combined with the statistical bias we have that
M
2B log 2
Biastot (Fw, Ste) S
+
+
(73)
B
B
Thee
and the optimal bin size again O 1/3, and resulting bias Biassot (Sor, Sio) Om 1/33 which
does not improve the bias. This is because of the error term of (X) (X) (x((X) This term cannot be improved by 1/B, B, thus we cannot leverage the underlying smoothness of the data. A similar discussion holds for the UMB setting.
24

---

D.6 Additional comparison with existing work
In Gupta & Ramdas [12], the error bound of ECE is derived through the following three steps: (i) Firstly, showing that the samples assigned to each bin are ii.d., (ii) using Hoeffding inequal- ity, deriveving [z - fz(x) = Oply Op(yB/ng B/nee) for each bin, and (iii) finally, summing up these error bounds for all bins, resulting in O,( B log B/nre) (in expectation O(B/veta)) This slow convergence is attributed to the separated analysis for each bin, which necessitates multiple applications of concentration inequalities.
In addition to the slow convergence, it is difficult to derive the error bound for UWB using this approach. The difficulty lies in demonstrating convergence for specific bins. For instance, in existing UMB studies Gupta & Ramdas [12], becomes inevitable to address the allocation of samples to each bin when attempting discuss the convergence of sample means for each bin. In UMB, equal number of samples, /ee/ B, are allocated to each bin to achieve equal mass across all bins. In UWB, however, there is guarantee about the number of samples entering each bin (in the worst case, all samples might be assigned to a single bin) because the widths of all bins are set equally. This necessitates discussions about the number of samples allocated intervals under strong assumptions regarding [[)]f(())] requiring stronger assumptions compared to both this study and existing research.
E Proofs of Section 4
First, we introduce notations, which are used the I'T-based analysis. We express the super-samples
(a, y):
(74)
(ã, D).
(75)
Sm (ām 9m))
(76)
ău (Tu: ;ú),
(77)
Um (2m,Um Um,
(78)
0m (Tmm mm,0m
(79)
We also define the total bias when using Ser as
Biastor (fw: Suz) = [TCE(fw) EC Sw)l.
(80)
We then decompose this bias into two biases as follows:
Biastot (Jey Ser) < Biassin (S fI) + Biasstal (Surs Str);
(81)
where
Biaspia (fwr fI) = [TCE(f)) TCE((f))
(82)
Biasstat (fwr S.)) = [TCE(2)) ECE(Sw, Su))-
(83)
We remark that the bins used in Jz of UMB constructed using S.r and thus, TCE(fz) also depends on Str.
E.1 Proof of Theorem 4 (The statistical bias when reusing the training dataset)
Proof. We start with the case of UWB. The proofs goes almost similar way as the standard information--heereti generalization error bounds.
Using the relation between the loss and ECEs by Eqs. (24) and (27), first we reformulate the ECEs as follows;
ECE(f 20) Σ
(Ym.Cm FA(ZZ. I (X
(84)
i=1 m=1
ECE(fAL2 A(2..))))))) .R), -uo) = Σ
(Ym.Um (82 [
(85)
m=1
25

---

To simplify the notation, we also introduce the loss as
I(A(Zu, R); 7, ((Y -A(Ze, 1 LAcE n) (X)EL
(86)
where Z -X,,): Then we obtain
A(2y (1): AU, 2, A( Bu, R)) = |ECE(J (CCE/A(22.))
kx0
ECB(J (CE(JA(22..))) (1) 2v)1
n
1
I(A(Zu R), 0mm.0.:)) i))
Σ
(A(Zu, R), 7 Um.
71
n2
B
Σ
Σ
[(A(Z,, R), Dm 1)
Σ
((Ai2,, R), Zmm
(87)
11 mm1
where W in the second line should be W A((7. R), but make the presentation simpler, we used W. We also used the triangle inequality ||a] 16|1 < la 6.
With this notation, by using the Donsker-Varadhan lemma, we have
E R,2.0 AUU Z. A(Zv, R))
(U, 2, A(Z, R));UIZ) + E2 log En,v' clA(U" (lA(U",2.A22.RR) (22.
< inf
t>0
t
[(A 2, A(Zu, R)):U1Z)
< inf
t>0
b
((A(Zu,)) R).2 m,,'' - 2 (LA(u,,)) .0),2 2t .
Eg loggogERA ER
+
t
[A Ž, AlZu, R)) + Eg log ER, Ei e La.
= inf
(88)
where we introduced
1 n Σ ((A(zu r), 3mm, ,(,,u,r,U,,))
n Σ ((A(zu) E,,U%
(89)
Our first observation is that conditioned on 7 = 2, R and U = u, the expectation of the exponent is
B
E B
u. Ur, 8))
(90)
by definition. Then similarly to Appendix D.I, we upper bound the exponential moment as follows;
Eyre ER Iu(E,,.,UU .0l Eg
II
e (l((E...
i=1
Ev
II
e (a((,,,,
+e - tgg(,,aa,)
i=1
E (-)""("()"
Eg
(91)
U1..,,
Σ
Egue (-1"
D. E. (-1)% (( (1 [0]
Ege
Σ
n
Eg e ( [[( a0..,,8m000 3) M( ((,,Fmmuu :0] (92)
-(
m=1
26

---

where =0000 is all the combinations that will be generated by expanding I in Eq. (91) and it has 2 combinations.
We would like to upper bound Ly; e (-=1(= (m. -)) .)] using Lemma 3 condi-
tioned on all other random variables. For that purpose, here we evaluate e; of Lemma To estimate it let us focus on UH and it takes value U (0. 1). So let us consider how the exponent changes by changing U
U O. Then the difference of the exponent is written as
[1w,, 2, - Uww, 2m,0, 2)] t(-1)"; B 1)
[Uw, 2m,0, I(w, Em,1,
n
t( 1-11) 2
(1ym.1 fw (Tm,)))) (u(mm)))) (1ym,0 fw (Tm. (slomm))nn)
t( t(-1) 1) +
((vm. - fro (mm,1))) f ([ym, (Zm, f (m.tm)))te))))
n
(93)
To evaluate the indicator function, we repeat the same discussion in Eqs. 44 and (45). On the basis of that discussion, by the definition of binning, for the input Zn,0, exactly of the indica- tors (L) J is non-zero, denoted as b. Consequently, all other indicators are zero, i.e., (u O. Similarly, for input In,1, the corresponding non-zero bin index denoted as b, so 1 (E))).)) is nonzero and others are zero. It should be noted that and b may be the same or different.
Thus, although there 2B indicator functions in Eq. (93), most only indicator functions not zero. Combined with the fact that [8m,1 Sw (Tm, 1] < and [ym.0 - (Tm,o) ]= S 1, Eq. (93) upper bounded by 4t
Note that by Assumption 1, (fm m== takes the distinct values almost surely and in the above discussion, we do not consider the case when b/B = [ for some b holds, which means that the predicted probability is just the value of the boundary of bins. In conclusion, we obtain the upper bound of Eq. (93) as
1)
[[[,, i, 1(w, om,o i)] ((-1)):
[[[ Em, U(w, 2,, e)] S 41
(94)
Then by Lemma 3, we have that
Σ [I
Eug e (-11
(1 [Iw,,mm Fm 1)
Σ
II
222
2 21
"
P0=0,1 m=1
BB=01 m=1
(95)
Thus
B
Eg Ele, 10(3,,,; Eg II
< 2n
(96)
and combining with Eq. (88), we have
E ER,2,U
Σ
n
I(A(Zu, R), mm.mm.
0m 1)
Σ
B
1
Σ
n
I(A Zu, R), Zm.um:1)
72
n
i=1
[AA Ž. A(Zu, R)); UZ) B Bog 2
2
inf
150
8(T(A(U, A,u,Z U)); + B 2)
(97)
27

---

This concludes the proof of UWB.
We prove the case of UMB. The key difference lies in the fact that the bins are dependent the training samples.
A AU A(Zu, R)) = [ECE([W, 20) F.F(/SW, Au)l
B
Σ m=11
Cm. - JA(Zy, my (m., Su
B
(ym, 10 1
where expressed the dependency of bins the training samples (Zy)). However, this dependency does not change the proof in the above; we use the consker-Varadhan lemma. We upper bound of the exponential moment. When upper bounding the exponential moment, conditioned on U, which means we conditioned on the bins. So we can exactly use the same derivation. So we can proceed with the proof exactly in the same way UWB.
Finally, we bound the statistical bias using the Jensen inequality follows: First following the proof of Theorem 2, using Eqs. (24) and (27), we have
E (TCE(S2) ECE(Sw,SS.. Sw)l R,8t
E
E [(>" (fw"-(((X")) (1 (x())e)
Σ 7m--fee (Xmm)) 1 (X 7
8,8t
2" (X",
E
E -ww"-wwx") (xm)enl
(Ym fw (Xm)) 1 I (Xm)e4
R,8tr
(X' yo)
i=1
m=1
B
[(Y (x(() tw (xggen.
Σ (Ym Sw [w((m))) sw (Xm)En
R,St
(2 m
i=1
m=1
m=l
B Σ
[( Jw (x"))) (xggeel
Σ fwr(Xm)) (w
(Xm)
T6
i=1
mm1
ml1
Se, St [ECE(Sw. SOCCEffw,,,,. S..) ECE(fw,SH)
(98)
where the first inequality is the triangle inequality and the second inequality is the Jensen inequality. Note that the above reformulation possible for both UWB and UMB. Although the case of
UMB, bins of the TCE still depend on St., it makes no difference in the above inequalities. We then use Theorem 4.
Remark 1. In the above proof of UWB, instead of Eq. (88), it is possible to consider the following type Donsker-Vartt Varadhan inequality
B
ER.2.
Σ
Σ
I(A(Zu, R), Zm, ;m. 1)
Σ
1
I(A(Zu. R),
Um))) Um,
n
m=1
(((AAZu. R), E, B); U12)
< inf 82-0
Eg log ERUUe 1B Mm [A(ZZ,)) R),2 mm
8) Dm ((A(Z2, R2, m,
T(U(AZZe R), 2, B): U12) + E, log ER, be E. I (.UU,
inf ES0
(99)
which results a looser bound than the above proof, which can be confirmed by the data processing inequality.
28

---

E.2 Proof of Theorem 5 (The total bias)
Before presenting the proof of the total bias, we first provide the following binning bias analysis for the UMB.
Theorem 8. For UMB, Under the CMI setting and under Assumptions I and 2, we have
1
2
ER... (TC(s))C((w))/TTTC 51++
+
(ogMI+Blog2)
(100)
B
where fCMI is defined in Eq. (17).
Proof of Theorem 8. The proof is similar in Appendix D.4. The difference is that the current setting, reuse the training dataset, so we need to evaluate the bias for that. First, in the same way as in Appendix D.4, we have that
ER,S, (X) - fz(X)]
B Σ
ER..S.
J E fw (X))))] e I.]
t=1
IP(fw(X) e 4a)) ( E [[][[[( e fw 4illoo)
R.Sa
ntSu
(101)
where we used Hölder inequality in the second line and E] loc the maximum of the integrand.
We want to estimate P(T+) = P((()) E T,). For this purpose, we use Eqs. (87) and (86). We re-define the loss of Eq. (86)
La (x)EE,
(102)
and substitute it into Eq. (87), then we have that
n La(2 (8m El
B
LAi2 Ry &m D
E R,Z.U
P(L) -(4)))(1)))))
E R.Z.U
1=1
1=1
(103)
where P(4) is the empirical estimate of the binning probability using supersample Xm, and P(T.) is that of obtained by X Xn. Then, to obtain the upper bound of the right-hand side of the above, repeat the proof of Theorem 4 in Appendix E. Let define
C...
B
AU 2.U...(2o.. R)) = Σ
Σ m=1
(1
Aily my (8 (8m. 1 11 (8 (8m.W.We))
(104)
29

---

With this notation, by using the Konsker-Varadhan lemma, we have
B
E
P(L.)
P(I.)
i=1
Em=
Em=1 1 SAcRy (y(..um)))mmm)
R
11
i=1
Eg R. 2,0 A (U, Z, A(Zu, R))
IAAU, Z, A(Z. R)): Eg log ER, u e CAA AZ2,,
inf
120
[fA(2u. (X);U12)
inf
Em
Ail Ry m, 1E4 Em=i "
Al(2 R) (8m,0% 3E4
Eg log BR,U" e Eis
I(f (x); + 2 log BRU (111012,
inf
(105)
120
t
where we introduced
n Σ m=1
g(ž, u, U 1)
I(A(Zu, 2m, ; n2 m=1
Σ
I(A(zu r). Em,Un, (106)
I IffA(2o .z) UX): and I(A(U, A(Z U)) < fCMI by the data processing inequality since the indicator functions depend on fw-
Here we use the fCMI =
Then, estimate this using Lemma 3 in similar way. The difference is the estimation of the upper-bound in Eq. (94), which is used for the evaluation of the exponential moment. Since we use the indicator function as loss, the coefficient c, for Lemma 3 is upper-bounded by 2t /,, not 4t/n. n. Then we repeat the proof strategy replacing the exponential moment evaluation by 2t n, not 4t n.
With this difference,
Eyee' Ee (o(E...
Ev II
All (0) <2Bef 22
(107)
and Eq. (97) can be rewritten in the following way
E ER R,Z.U Z. Σ P(1) P ((1))-(())) P(L)) P())
2(MCM B Bog 2)
SV
(108)
n
and clearly, by fixing some i, we have that
B Σ -
2(ICM + B Blog2)
2n P(L.) P(T.)) s E22
S
(109)
n
Since we put an equal mass for each bin for the training dataset with UMB, we have
- u-1+1 < B
P(I))
Combined with Jensen inequality, we have
2(FCMI + log 2)
ER.S., P(I) <
(110)
B
30

---

Then we have
ER,S., E| (X) - (x)]
B
2 B log 2)
E R,S.r
E 4,]l0
B
1
+ B log 2)
Σ
[[] L1 (X) E 4.]bo R.
E
B
72
(111)
Finally, we use the fact that (X) - {| S {LLi/BB - ((L(((-1/BB)) holds by the definition of the UMB, which is the largest difference of the bins. Then
B
E
[[E[[ E L.] (x))))) E Ti]lx
R,S
Σ J(LB/BB) J((x((-1)/BB) S
(112)
where EJ 1mo is the maximum of the integrand.
Combining the above, Then we have
E fX) fx(X
R,,te
2(1CM + B Bog 2) B
B
+
E
(X) E I. (x)(x)l. E Lillx
n
R.S
2(1CMI + 1 log 2)
+
(113)
Y2
This concludes the proof.
Using this we provide the proof of the total bias as follows;
Proof of Theorem 5. We use the triangle inequality,
ER,sL [TCE(ww ECE(/w, S.r)
ER,S., [CE(fw) - TCE(f) TCE(fT) - ECE(fw, ER,S.. [CC(Jw) - TCE(SZ) + RR,s, (TCF((Z) F.CF(J,, Su)]- The first term is the binning bias and the second term is the statistical bias.
(114)
We start from the UMB; we can bound the binning bias in the first term by Theorem 8 and the statistical bias the second term by Theorem 4 of the UMB.
As for the UWB, the binning bias is simply (1 + L)/B. B, which can be derived similarly as in Ap- pendix D.4. As for the second term, can bound it by Theorem 4 of the UWB.
This concludes the proof of Eq. (16).
Provided in the proof of Theorem 8 (especially in Eq. (105)), we can obtain the tighter version of the binning bias bound as follows; Corollary 3. For UMB, Under the CMI setting and under Assumptions I and 2, we have
ER,S., ICE(wW)TTEE(H) (1+
[(A(U, R)) + + log
B
(115)
where
AUU, A(U,2,A(Zo,1) R))
(1
f fxco Ry (8 Om.0 Sacer Ay (8 (8mwweee))
(116)
31

---

In the proof of Theorem 8, we used the fact that [(A Z, 2.) fCMI by the data processing inequality. Thus, fCMI appearing Theorem can be replaced with T[ Z, A(Z. R)); which results tighter bound.
E.3 Proof of Theorem (metric entropy)
Proof. Recall the setting, where we assume that fw E F has the metric entropy, log log.W(F, 11F,111-lso. loo 0), with parameter ò (> 0). That is, there exists set of functions F8 == {fi...., (AI that consists 8-cover of F. We will consider replace fo with the functions from the d-cover.
Using the 8-cover, want to construct set of functions F that satisfies the following property; there exists function
F such that for any imput and that is allocated to i-th bin, that is, fw (x) E I, then f satisfies fx) E I and [ ll <
The original cover F may not satisfy this property follows; If we simply consider that h = arg min fl fl then there a possibility that h((x) & I, for x: E such that fz) E I. This fEF,
will cause a problem when approximating the ECE using h. If h()) & Je it significantly changes the estimation of the conditional expectation in each bin, leading larger change of the ECE. To avoid this, we consider a set functions such that for each I...., B, for any f E Fs. we define
f(x) == max min (f(O), 20: i-1 B): B +g.
(117)
where 0 < c < 1/26. We refer to this set of clipped functions as F; for 1,..., B. The parameter is introduced that the clipped value does not take the boundary value between the i-th bin and - 1)-th bin. Since we set 0 < e < 1/26, the parameter does not affect the bias analysis below. Then, define the function
B
f(x) = Σ f
(118)
where fi = arg min suprex, (f) f(x) and X = fx X(f((() E 4J. (if X, o. fEF,
do not need consider fi and any function in F; be used.) Note that under this definition, supzex; (x) fa(x)] < holds for each = 1,..., This can be confirmed as follows; given any Swo assume that there exists point xx X' (the following discussion still holds when there are multiple such x² and we refer to them as 2²*) that achieves sup, [sn h/ If f (x=) E
4, by the definition of F,, [fa(=*) - fa (x*) I max [min (I(x*), [ i-1 +e fw((")) S
[h(x*)-1 ff fm.(")) S 8. For æ. which does not achieves sup,, (n)( -(xx))lo (that is, x $ X²) and satisfies (z) E 4,, then we have lf(())
fw)) S max min (h(x), $), 1-1
B + fz S
[M(x) (a)) 5. So for any x E X, f (x) f((x)] < 8 holds. Thus the function f defined in
Eq. (117) satisfies that for any x. if fn (x) E 1,, then f satisfies f(x) E 4 and |lf fallox < 6.
With these settings, consider replacing the functions in the total bias defined by above. Here in after, we set < 1/B. Then the error the TCE by replacing fw with f is given as
E B [f]] - ful - EEY All 5 (1+ L)o.
(119)
which is obtained by the Lipschitz assumption.
32

---

Next, we consider the enror in the ECE by replacing fw with f is given as follows; [ECE(Jw: Sur) Stt)
B
B(. -Y-
[o(()) fx()))
Σ
E (x, (Y-
sxjennl
>
() (Y fio( 1x(())
IB (X.Y) (X (xxeel Σ
(X (f(X) - fio(X)) (x)eell
B
1
1 (r.. eet f(m)
Th.
[4
m==
m=1
B
[TA]
8|7,1
44
(120)
where [4 = 2mm1 1 fm.((=)) and we used the fact that E, 14| and fn)ee L(()) for any x by definition.
Then the total bias is upper bounded by using f as follows;
ER.S, (TCE(Sw) ECE(Sw, Str)
En,s, [TCE(fw) TCE(F) + TCE(J) - ECE(fW;
< (1 + 1.5 + ER,s., (CE(J) FCF(J,, + (FCE(J,, - FCF(/W, Ser)
S (2 + L)6 + ER.S.. (TE(()) ECE(f, S..)).
(121)
Since the second term in the above represents the total bias of f, using Theorem 5
(cCMT()) + B log
ER.S,, (TCE(f) ECE(S, 1 +
+
(122)
B
n
where replace f. appearing in the bound appearing Theorem 5 with defined above.
From the data processing inequality, we can upper bound the eCMI(i) by the [CMI of f. Then such [CMI is bounded by the entropy of f as follows
eCMI( < ICMI(f) = ((f(X); Ž) & (( H(f( 2 S H[ (123) where we used the definition of mutual information and the conditional entropy of f given U (H Z) is larger than because f(X) is the discrete random variable and the entropy of the discrete random variable is always larger than O. We can confirm that f(X) is a discrete random variable since f belongs to the function which is defined by the covering and the input X is 2n.
Then we upper bound (ff Z] by the log of the number of distinct values that are represented by Eq. (118) given 2n inputs of supersamples Ż. We refer to as N. Define (2. g) = max If(x)) - g(x:)] for f.g F. The d-covering number of JF with respect d2n is denoted N(F den, 5), and define N(F 6, 2n) = sup M(F, d2n, 6). It is known that A(F, 6, 2n) < N(F, I|. ()) in general [37]. We focus on the fact that f defined in Eq. (118) is the element of + F2 +.... .... +F where Fi + F2 implies the set of functions that is [ʃ + glʃ E Fi,g I E F2). Note that the covering number of sum two functions are upper bounded by the multiplication of each covering number, that is
W(F 0, 2n) < (F5,
(124)
and thus, we have
W(Fi + F2 +
+ FB, 2m) < I N(F.. (/
(125)
33

---

Thus we have
B N & II ( & (M(F,) 1llo. 8/B))
(126)
1=1
In conclusion, we have that
cCM((I S log N I (log 1loo 6/B).
(127)
Combining these we have ER,S, Biastot (Sw, Str) <
1
8 ( BBllog (F,, || 1l,o. 8/B) + B Blgg 2)
(2 + L)8+
B
+ L
8B log 2N 1oo, 5/B)
B (2 L)8 +
(128)
n
Finally, as for the order discussion, for example, we can obtain (NF, I| ll,,, 8) x ( (L)) when f a d-dimensional parametric function that is Lo-Lipschitz continuous (Lo > 0) [37]. leading to the following upper bound:
3
dB log B2 B2
HRS,, Bias (fw, S.,) 2
(129)
n
where we set = OL)/B). This bound minimized when B = On3 resulting in a bias of Olognn/n211
Here we provide additional discussion about the metric entropy. The bound based the metric entropy depends on the model's dimensionality, making them unsuitable for large models such as neural networks. Some existing studies [15, 17] present the upper bound of the eCMI and fCMI by the dimension-indeeender complexities, such as the VC dimension for binary classification and connecting IT theory UC theory.
Inspired by these results, here we provide the upper bound eCMI and fCMI using such dimension- independent complexities. As provided in the lower bound analysis above, since TCE estimation is similar to the nonparametric regression, we use the fat-shattering dimension [1] to upper bound the eCMI. Specifically, from Lemma 3.5 in Alon al. [1] in if our model class (-) satisfies 8/4-fat dimension with dø/4 for 5 E [0, 1), we have
eCMI S (CMI = O(ds/1
d5/4 log
log dz/1ō
(130)
which results in the dimension-independenn upper bound. To evaluate the fat-shattering dimension for specific models, see Bartlett & Maass [2] for the details.
E.4 Proof of Theorem 7 (recalibration)
Proof. Recall the definition of the recalibration. Here we show the expression when we use the training dataset S.:
B
1r (x)
Σ Ar. 1 fm.xeel
(131)
1=1
En Um (a Em (emm))l
(132)
The proof similar to the proof of Theorem We use Eqs. (87) and (86), let S.r then we have
{m 12 D
34

---

RR ,
E
NT,, (x)] hI (x)]
R.....
E2"= [XY" - pis.sw) someeelll
i=1
= LR.
22
[K Dis.sa) (xixeeen 1m Σ
i=1
m=1
E 12 1m mmm
mm
m
1=1
(Y 1 (xw))) - (w te,. Iw Pe,s (x
R. (Zm) mamm n
[C
Ym -ww..://mmmmmm........... (xx( (1 [mwoxee))
(x()e)
n
B
E
Σ
[Y 1 (x()e) Ym [x(X))e))]]]]]
R2 (2 mmm
4
m
+
E R. (Z. Pizi: 7
[L ([x)))))) - [wix)ee))
(133)
m=1
where we used the Jensen inequality first and the used the triangle inequality and used the fact that | s by the definition of UMB in the next inequality.
We then rewrote the above in the CMI setting, have
ER,S., E hr, (+)) hI,su (+)
B Σ
E R,2U0
mm,.m. 1, 18 Ym,um 10 El
1=1
E n,2,v
SACRo my (8mm
om ee,
1 ee
2(T(A) 7, A Zv. R)); 2) + Blog2)
2(1(A2(U, 7, AlZu, R)):
B Blgg 2)
n
(134)
where
B
1
A(2,
=
( Um -
(8 -Yn,um Lacky nn (8m. )Ei,)
1=1
m=1
(135)
B Σ 1=1
A2 2. A(Z,, R)) =
Σ
(8 (8m...
(136)
where the last line is we repeat the proof of Theorem The proof of Theorem has discussed the loss composed of the indicator function, we can use exactly the same proof procedure. The only difference the CMI: here we consider the eCMI which uses above A and A₂ as the random variables, and their CMIs are the conditional mutual information between A and A2.
35

---

From Eq. (134), we can further simplify the upper bound using the data processing inequality,
[(,, U1) R, Z); U1Z) eCMI
(137)
eCMI [((,A(Zo R), [ I(A(Zu, 2), = 2) (x)) 1, Aizo .o (2)E1g)
(138)
(139)
We then have
ER, Eyy hT.SO (x)] s 2/ 2(eCMI + B Blgg S $21
2(1MI B log 2)
(140)
In the numerical experiments, we use the tighter version, which appears in the proof above; Corollary 4. Under the same setting and assumptions as Theorem we have
ER,s., E h (x:) ht (2:)
(U, Zu. R));; + B Blog2)
2(T(A2(U, R)): + B log 2)
n
(141)
where
AUU, R))
Σ
② mm .1 L0 Om om. -mmum 11 (8m. JEL.
(8m,
(142)
A2 R))
Σ
1 1x (mm.0 1 S 2y ( (8..
(143)
In the main paper, we further upper bound eCMIs by fCMI, which is followed by the data processing inequality.
E.5
Recalibration when using test data
Here we show the bias of the recalibration when the test (recalibration data) is used.
Corollary 5. Conditioned on W = w, under the same assumption as Theorem 2, we have
Es., BIIEEY (X)] hz hz.s.. (X)) logBog2//nn - 2B) 2B/eneee B)
log
(144)
Proof. The recalibration bias corresponds the statistical bias because from Theorem 2, we have Es., Biasstat (h, Ste) Es.. TCE((Z) - ECE(hw: Ste)
$ /2B log 2/ (nre B) + 2B/ B).
(145)
where hr the conditional expectation of h hr.s,, given bins I. Note that by the definition of
hi,,, from the tower property hz(Ø) = lr,s (x) holds since we take the expectation in each bin. Thus, by definition Es," TCE(hz) Es._ [|[EEY|b.. (x..s...)) (X)] holds. Moreover Es., ECE(E,, S.e) 0 by definition, since this is the definition of the recalibrated function. Thus, we obtain the result.
Further discussion
We have presented the results of our analyses of (i) the total bias in estimating the TCE and (ii) the generalization error analysis for the ECE and the TCE thus far. this section, we explain the difference between our study and the existing work in the calibration context.
36

---

E1 Discussion about the assumption
Here we discuss the necessity of Assumption 1. The reasons of using this assumption are two-fold: i) : The first purpose is that we want to use the results in Gupta & Ramdas [12], which analyzes the statistical bias of the UMB. Their proofs use the existence of the density of (2), so Assumption cannot be eliminated. ii) The other purpose is that by Assumption 1, we want to use the fact that {Sn (mm))
Z'm E Ste takes the distinct values almost surely (same for (fro (I.) (mmm))== m= in
I' E S).
Regarding i), we used results in Gupta & Ramdas [12] to prove the result of UMB in Eq. (9) of Theorem 2 and the result of UMB of Theorem 3. Thus, the results using these theorems require Assumption 1. They correspond to the results related the bias of UMB, So the results of UWB essentially do not require this assumption.
The situation becomes complicated when considering the generalization error analysis. Our analysis uses the ITT-based approach and does not use the results in Gupta & Ramdas [12], so we do not need Assumption I regarding i). However, if all (Jm()) }=== in Im S takes the same value, we cannot construct the bins in UMB. So when considering the training data reuse, we need Assump- tion I to construct the bins of UMB. However, we remark that we can replace Assumption I with the assumption that "we assume that (fm()) in Im E S takes distinct values almost surely".
When considering the UWB, we do not suffer from such troubles since we simply split the interval [0, 1] with equal width as the b-th interval is given as ((b - 1)/B b/ B). However, there might be chance that all the (fm(mm) m= in I' E Ste takes b/ then the coefficients of the bound changes. Recall that our proof uses the bounded difference property when upper bounding the exponential moment, for example, in Eq. (93) and Eq. (94). That estimation is based on the fact that (Su (xm))) upper bound of the bounded difference will change, which results in the different coefficients in our bound, although we can proceed with the proof in the same way.
in Iim E Ser takes different values. So if all the f takes the same value, the
For these reasons, we decided to impose Assumption I for all the statements. As we discussed above, if we focused on the specific setting, such as UWB and UMB, then there is room to eliminate or replace the assumption.
Next, we discuss the necessity of Assumption 2. Estimating TCE involves nonparametrie regres- sion of [XY) = v). For finite samples, smoothness assumptions like I Lipschitz continuity are required; without them, small changes in could cause large variations in label outcomes, making estimation impossible [26]. Such smoothness assumptions are standard in nonparametric regres- sion, including kernel-based ECE. Therefore, without these assumptions, increasing the sample size would not ensure that training (or test) ECE converges to TCE. As noted in our minimax lower bound discussion, the absence of smoothness (3 + 0) leads to increasing bias.
In practice, Assumption 2 is reasonably mild. For example, if label distributions follow a Bernoulli distribution with the mean depending on the input xr Assumption 2 satisfied [47]. This rel- atively weak assumption in binary classification. Moreover, existing studies have shown that many common benchmark datasets are consistent with this assumption (e.g.. [49]). Additionally, our nu- merical experiments with the data used in this study confirmed that the conditions for smoothness, such as non-diverging first derivatives, are indeed satisfied (see Figure 6 in Appendix H.4). This supports the robustness of our assumptions and the applicability of our methods in real-world sce- narios.
Finally, regarding the assumption ne 2 2B, it is crucial for UMB, as it guarantees the proper construction of bins. In UMB, we first use B samples to build the bins. We then partition the remaining Re- B samples evenly across these bins. If n. 2 2B, we have n. - B 2 B, preventing equal distribution of samples. thereby rendering UMB inapplicable. Conversely, UWB does not require this assumption since it divides the [0, 1] interval into equal-width bins.
F.2 Discussion about our proof techniques
Here we discuss our proof techniques. In our proof for UWB, our proof technique does not heavily depend on the binning construction method, so we can apply our technique to other than UWB and UMB. The important ingredients are the boundedness of y and (a) and the property of the indicator function. However, our proof builds on the reformulation of Eqs. (24) and (27) this can be
37

---

restriction for some settings. For example, when we consider higher-order ECEs defined as
B
ECE Se) = Σ pilfi.s. -t..s.
(146)
with p > 1, which can not be reformulated like Eqs. (24) and (27), and thus our proof technique cannot be applicable.
On the other hand, as we introduce in the above, the technique of Gupta & Ramdas [12] can apply to ECEs with p > 1. However, the drawback is that their technique can only apply to UWB without training data reuse.
Next, we discuss our results with Wang et al. [39]. The eCMI appearing in Theorem 4 closely aligns with the AL bound (loss difference) of Theorem I of reference Wang et al. [39]. Specifically, the eCMI term in Theorem 4 is not based on the value of ECE itself. Instead, it is derived from the difference between the test data ECE and the training data ECE. This approach aligns with the AL (loss difference) as shown in Theorem of reference Wang et al. [39].
However, extending bounds using the techniques of Wang al. [39] presents significant chal- lenges. The A T. bound in Wang et al. [39] defines the loss gap for a single data index i as AL; and utilizes the symmetry of each individual index derive fast rate bounds, as demonstrated in Theo- rem 4.3. In contrast, our bound requires treating all n indices simultaneously. This necessity arises because ECE is nonparametric estimator that uses all n indices, unlike usual losses such the 0-1 loss, where an estimator can be constructed using a single index. Consequently, the techniques from Wang et al. [39] that utilize the symmetry of single index are not applicable our context, making it difficult to employ the methods from Wang et al. [39].
F33
Comparison of our bound with existing and trivial bounds
Here discuss the order of our generalization error bias in more depth. Recall that our Theorem
ER.s.. S... (CCE(w,, Ste) -e.ee-ECCE ECE(fw: Sw) S 8(eCMI + B log 2)
(147)
and the important property is that the bound is of order O(v B/n) if we neglect the order of eCMI.
Here we see that when we use existing Theorem directly, the resulting bound is O(B/ Vn). Recall that
B
ECE(f,
Σ (x,) (Y -fu(() (x))
(x)ee)
TCE(fz) - Ex
-fx()) -x(() (x)ee)
where Sur is the empirical distribution of the training dataset. Thus
B
Es., Stn.R R
Σ
DY -w 1 (w Σ (x (Y (w)(w(X)) 1 (x)en,
ES.. R
(x -wv(X)) 1w(Xjer (x (Y fw(()) (xjenl
St.
Σ
(Y - Sw(X)) (1))))-1wwx000 1 - F. (x.Y (Y (w((x) -1 1
B
(cCMI(i,) log 2)
2
B
(FCMI + log 2),
(148)
38

---

where we used the triangle inequality in the second line and from the third line to the fourth line, we applied Eq. (5) in Theorem by fixing the binning index i and eCMI is where eCM [[:s; U1)
İ,U,, R2 2)
n Σ
1
(Y mm ( Sacey (.m.
(Ymum F) m=1
20 Jen
(149)
Thus, this proof is simple compared our proof of Theorem 4, but results in worse dependency on B. In our proof, we used the property of the binning and indicator function of the loss function explicitly, which results in better dependency. On the other hand, when deriving Eq. (148), we do not use such properties, and thus results in worse dependency on B.
F.4 Discussion about the order of eCMI and fCMI
Here we discuss when eCMI and fCMI can be controlled theoretically.
As discussed in Section 4, from data processing inequality [6], have that eCMI < ICMT s S). Since (CMT does not depend on B, and the dependency on B of ICMT, eCMI is not a problem.
Here, we cite the classical result about I(W;;) S). Clarke & Barron [5] (see also Rissanen [30], Haussler & Opper [16]) clarified that the growth rate of MI can be controlled as follows: if w takes a value dddiimnniioal compact subset of IRd and p(y]æ; w) smooth in w, then as n + oc, we have
n
I(W;5) = log
+ h(W) + E Eog det.J + o(1),
2xe
where ((W) is the differential entropy of W, and J is the Fisher information matrix of p(Y W).
Moreover, Steinke & Zakynthinou [34] introduced the CMI that satisfies fCMI < CMT discussed the CMI is upper bounded by the various notions of stability. For example, the training algorithm satisfies v /2ediiffernntillyy private (DP) algorithm, then CMI is upper-bounded by en. So this controlled by the DP algorithm, then our eCMI can also be controlled appropriately. For example, Xu & Raginsky [43] discussed that the Gibbs algorithm satisfies ( /n)-DP when the loss takes value [0, 1j. Thus, such Gibbs algorithms can control our eCMI moderately.
Steinke & Zakynthinou [34] also clarified that if the algorithm d stable in total variation distance, then CMI is upper bounded by ōn. From the stability perspective, Mou et al. [28] showed that the Hellinger distance and T is the iteration number of the SGLD algorithm. Thus, this implies that when T is small, the eCMI of SGLD can be very small. Recently, Farghly& Rebeschini [8] and Futami Fujisawa [9] showed that under the certain non-convexity assumption, SGLD satisfies the Wasserstein and KL stability of the order of ((1nn), which also result the eCMI of SGLD.
SGLD satisfies O( ( stability
F55 Relation the existing study of calibration
Here we discuss other existing work, which is not shown in the main paper mainly due to the space limitation. First, we compare our result and existing analysis by Gupta & Ramdas [12] in Appendix F.2 in detail.
We discuss in Appendix D.2 how our proof technique improves the trivial dependency of O(B) our O(VB) for the ECE with the test dataset. We show similar discussion for the ECE with training dataset reuse.
Kulynych et al. [22] also discussed the relation between generalization and calibration. However, there are two distinct differences from theirs; One that they only discuss the statistical bias not consider the binning bias. The other is that their statistical bias is of O(B) while ours is O(VB), which is significant improvement.
39

---

Carrell et al. [4] numerically evaluated the generalization gap of the calibration, which is close to the statistical bias in our training reuse setting. They focused on the numerical aspects and statistical bias, while ours focused on the theoretical analysis and focuses on both the binning and statistical biases.
Gruber & Buettner [10] studied the various statistics related to calibration error. While our study rig- orously analyzes both the binning and statistical bias, their work focuses on the asymptotic settings and has not derived the dependency of B and n.
There is an additional comparison of our analysis with Gupta & Ramdas [12] in Appendix D.6
F.6 Discussion about the lower bound
Here, we discuss the lower bound of the bias when estimating the TCE from the following two viewpoints; the TCE estimation can be seen as (i) estimating a parameter in each bin, and (ii) estimating a one-dimensional function a pointwise. To understand this, we start deriving the following lower bound by using Jensen inequality:
TC 2 ff
(150)
This bound suggests that estimating B[Y] = (a) achieves the small TCE. From the classical the- ory, for any distribution D, the lower bound of a parameter estimation bias 1/ [37]. Eq. (150) corresponds to the setting of B = 1 bin to estimate the conditional expectation in the ECE. With these observations, we discuss the statistical bias of UMB. UMB, we estimate the conditional expectation using = n/ B samples in each bin and this is parameter estimation problem. Thus this leads to O(1/ /m) bias from the classical theory. On the other hand, we derived the statistical bias ( (V/Bn) for UMB, thus it is optimal when viewed as the parameter estimation.
However, using a constant function (z) = EYY, which achieves the small TCE, is useless in practice. Our original motivation is to measure the perfect calibration, which requires estimating the conditional expectation Y (z) p] for the interval p E [0, 1] in pointwise, and this is function estimation problem. Thus, the bins used in the ECE adjust that whether estimating ECE is
close to the parameter estimation or the function estimation. Then this trade-off is captured by the binning bias in our analysis. So the total bias represents such trade-off whether the problem the parameter function estimation.
From the classical theory of Fano's method [37]. when we estimate the Lipschitz function with a closed interval, it achieves lower bound (11ndd+2), with d as the input dimension of the function. In the calibration, the input is the probability p and thus = 1. Since we derived that the bias of the ECE is O(1/n2/3), it achieves the minimax rate if the underground conditional expectation E|Y p] satisfies Lipsthitz continuity.
Moreover, when the d-dimensional target function satisfies stronger smoothness assumption, 3- Hölder continuity, we suffer the bias of 0 [36]. So if E|Y p] satisfies such condi- tions, the lower bound of the bias should be O (1//n=iiT, however as discussed in Appendix D.5, the binning method cannot achieve this rate and thus cannot utilize the smoothness of the data dis- tribution.
E.7 Additional discussion about the lower bound
Here we discuss additional points regarding the TCE bias estimation. Conditioned on W = let fwr (z)) and the distribution induced by p(x) by (x) over as p(v). We express the support of
p(v) as V C [0, 1]. Let g(v)= = E[y = 1[ (x) ) = e] Pr[Y = 1/u]. Let G be a class of candidate conditional probability functions over V and every candidate g g satisfies S g(v) S for all
E V. Let us write the L2 minimax error as
R(G: n) = inf sup BVg(V) 3 á geg
(151)
where ý is over all valid estimators for y using n samples (Xm, Yn) and the expectation taken with respect to true y. The 1.2 and higher order minimax rate has been shown in [45] by using the
Yang-Barron method [46], which the mutual information-based approach stemming from Fano's method. To cite this result, we need additional assumptions that control the mutual information [45];
40

---

Assumption 3. Assume that G has at least one member g" that is bounded away from 0 and 1, i.e,
there exist constants 0 < C1 S C2 such that 0i S 9 S cz.
Here we assume that 9 is a set of functions that satisfies the 3-Lipschitzness: for any g E 9, there exists positive constant C that satisfies (g(e) g(0')l E Cl v' l for any v, v' e V.
According to Lemma [45], B-Lipschitzness and we have
R(G;n) ž n -222222))))
(152)
Thus, we consider the histogram-based estimator for
9bin (v) E St.s.. lvel.
(153)
which is used in the definition of the binning ECE, then
sup
-28(2201)) El ((i0i(()) - 2 2 inf sup Blg(V) 2 9Eg
=
(154)
9Eg
Thus we can obtain the lower bound the recalibrated function from true conditional expectation.
Here we discuss how this lower bound related to the total bias of the ECE. Let us define the semi-metric
pla.g' (V vI| Ellg'()) VI]I.
(155)
We can easily confirm that satisfies the positivity and triangle inequality, so this is the semi-metric. We show the following relation for the total bias and this p as follows; recall that we can express the TCE as
TCE(fw) [V[g(V) vil
(156)
and
Es.. (CE(Sfu; Swe) = ([l(iiinV)) v(V)+ -V VI]
(157)
where
((v)= Σ U.S. LuEI, U,S,, 1
Pic
Lun Em,
m=
where Um = (. Thus, the total bias is given as the total bias
Es, Bias (Sw: -,, Sto) = Es.. TCE(fw) - ECE(fws Sta)l
2 (TCE(fw) Es,, ECE(ffe, Sto)l
|Ev [[g)) - V1] - Ev [1 (V) VVVV+ V) p(g. (158)
where ğ Gbin (V) V (VV) V. Thus, by studying the risk under p. we study the total bias.
On the other hand, this is smaller than the Ll distance
E ((V) g(V) Z Bl(((V) vI] - EIlV 9(V)] p(g.
(159)
by the triangle incquality. Note that LI distance is smaller than L2 distance, the above minimax result for Ò and in Eq. (154) is insufficient to understand the bias of TCE and ECE from the lower bound. Instead, introduce different lower bound given as follows. Conditioned W w, under the B-Lipschitzness for | (x) = u] and Assumption 3, we have
sup Eil (ll V
1 (V) V(V) 28/(28+1),
(160)
9Eg
And We can further obtain
sup
B Bll - V 1i (V) -V(VV 8/(28+11
(161)
DEG
where E loo is the maximum of the integrand. These lower bounds imply the pointwise lower bound of the difference of the conditional expectation and Using these lower bounds, we study the difficulty of estimating the TCE at each V (x).
41

---

Table 2: Model architecture of CNN on the MNIST experiments.
Model architecture CNN (same as Harutyunyan ct al. [15])
(1st layer) Convolutional
32 filters.
kernels, stride padding batch normalization, ReLU
(2nd layer) Convolutional
32 lilters, 4 x 4 kernels, stride 2. padding 1, batch normalization, ReLU
(3rd layer) Convolutional
64 filters, 3 x 3 kernels, stride 2. padding 0, batch normalization, ReLU
(4th layer) Convolutional
256 filters,
kernels, stride 1, padding 0, batch normalization, ReLU
Fully connected
128 umits, ReLU
Fully connected
units, Lincar activation
Proof. First, we focus on the relation
sup Elllg() -1 (V) V(V) inf sup [V]l - v(V)) (162) .EG
g sEG
We then estimate the minimax L.2 estimation error under the semimetric P(g.9') = EVl - The proof the same as that of Lemma [45], which uses Yang Barron method. The difference is to derive the packing number under the semimetric not the L2 distance. However p is nothing but the shifted version of the L2 distance. Thus the order the packing number is
the same that of L2 distance. Note that since G is the set of positive functions thus, taking the absolute of (VV - V does not change the order. Then by using Fano's method, we obtain the result for L2 lower bound. The version of |loe can be proved in the same way.
We finally remark that the above pointwise gap is larger than the total bias
B (VV) VI lr V) V(O)
(163)
s. [ly(V - V1 E Elii (V) - (V) Es, Biastot (Sa Sto)
(164)
where we used the relation of that 1.2 larger than L1 and used the Jensen inequality.
F88 Relation the multiclass settings
Although our study focuses on binary classification, we can extend it to multi-class settings. In existing work [24, 10), the top-label calibration error (top ECE) has been proposed as a measure for multi-class calibration. For instance, in K-class classification problem, of each label by the final softmax layer neural networks. We assume that (w) E IR predicts the label by C' == argmax, (X)), where (X)x represents the model's confidence of the label E [K]. Then top ECE is defined using the highest prediction probability output by fw: PYY compute the ECE in similar way as binary classification. In this case, since we focus only on the top label, we can treat top-binning ECE in the same way binary classification, leading the same generalization and total bias bounds. Our results, therefore, offer flexibility to analyze the widely used top-label calibration emrrr in multi-class settings.
obtain predictions
(X)cc fw (X)cl- By considering binning only for the top score,
G Experimental settings
In this section, we summarize the details of our experiments conduced in Sections and 6.
G.1 Experiments the synthetic dataset
For the experiments on the synthetic dataset, we follow Zhang et al. [50] and assume that the distri- butions of the label Y and the input data X are as follows:
P(Y = P(Y = 0) = 2'
(165)
and
P(X = = -1,1,
P(X x/Y = 0) -xx
(166)
42

---

Table 3: Experimental settings on MNIST [25].
Experimental selup for MNIST experiments
Tack
classfhcation
Model
CNN with four layers
Adam with learning
Optimizer
SGLD with 0.004 learning rate (docaying by a factor 0.9 after cach 100 itorations) SGLD)
Num. of traming samples
[75, 250, T0IX, 4[i]]
epochs
Num. of samples for CMI estimation
Num. of samplings
Num. of recalibration dataset (existing methods)
100
where (xx; m, .)) the Gaussian distribution with mean m and standard deviation σ. Then, the probability of Y = given r can be expressed as
P(Y = 1 1 exp(2x)
We also define the prediction models as follows:
1
exp(- 80 - -312)
2 == fw = (=1, 22) exp(- 30 B1x) 1 exp(- 1xp(-30 B1
where [B0, }1} are parameters.
Under these settings, we can calculate the closed-form of the canonical calibration function TT2) (T1(2), x2(2)) where
Tı (z) = (1+ cxp 200 + log(1/21 ")>
(2(2) (2).
31
Due to this closed-form calibration function, we can estimate the TCE based on Monte Carlo inte- gration. In this paper, use 10t random samples generated from Eqs. (165) and (166) and evaluate the sample average value of [ - म (z)l as the estimator of TCE. Furthermore, we estimated the Lipschitz constant L by taking the maximum values of the gradient of (T, (2)..
G.2 MNIST and CIFAR experiments
Model architectures, datasets, model training process, and implementation: We summarize the details of model architectures for CNN, datasets, and model training process in Tables 2-4. Our experiments were conducted by adapting the code from Harutyunyan et al. [15] to suit our exper- imental configurations. Consequently, the datasets utilized in this study were normalized in accor- dance with the implementation provided the referenced repository. We used NVIDIA GPUs with 32GB memory (NVIDIA DGX-1 with Tesla V100 and DGX-2) for MNIST (SGLD) and CIFAR-10 -00 experiments. We also used CPU (Apple MI) with 16GB memory for the other experiments.
Table 4: Experimental settings on CIFAR-10 [21].
Experimental setup for CIFAR experiments
Task
dog-or-not classifiatiion
Model
ResNet-50 pectrained ImageNet
SGD with 0.01 learning rale and U.9 momentum
Optimizer
SGLD 0.01 learning (docaying by factor after iterations)
Batch size
64
training samples
5000, 20000
Num. of epochs
40
Num. samples for CMI estimation
Num. samplings for
Num. recalibration dataset (existing methods) 100
Mutual information estimation: We cannot estimate the mutual information
[[[(A(Zs, 2s, R), 2, S1) in our bounds using the approach of Harutyunyan et al. [15] and
https://githu: com com/brrayrhar/t-OM
43

---

Hellström & Durisi [17]. This is because our loss function I(A(Zs. R), Z. B) assumes con- tinuous values, while these works specifically focus on discrete random variables, such as the output values of 0-1 loss or the predicted labels of classifiers. Hence, we developed a plug-in estimator for [[s, R), Z, S|2) [19, 20, 32], which is computed using estimators for the probability density of 1(A(2s. R)) and Str, as well as their joint probability density, employing s--eaaret-neiighoor-beedd density estimation [27]. The estimation strategy is incorporated into mutual-info.classi. function (we refer to the follow- ing link: https://scckktt-eearr org/stable httplleeemmdles////eee aaaaab/eeeedulleeeeeeeeeeeeeeedd sanerrttddskleaaee feature. selection liruaal_iffoo inteallsss____siiiff html). We set k 3 following the default setting of this function and Kraskov et al. [20], Ross [32].
the Feleamm.featureeselecccii
Standard deviation evaluation of our bounds: The standard deviation in Table and Figures 2- 5, which is almost unrecognizable due to its small value, are attributed to the randomness inherent in various experimental settings during model training, i.e., randomness of the training dataset and the initial model parameters. For example, in the MNIST experiments in Table 3, the standard deviation of our bound was evaluated under the x 10 models.
H Additional experimental results
In this section, we show the additional results obtained from our experiments.
H.1 Bound plot on UWB
We show the results of our bound in (14) using UWB, as shown in Figure3, which was omitted from the main paper due to page limitations. As we discussed in Section 6, we can see the importance of the choice of to obtain nonvacuous bound values. We also observed that our optimal choice, B In 1/3 is effective in obtaining nonvacuous bounds.
MNIST (Adam)
MNIST (SGLD)
CIFAR, (SGD)
CIFAR (SGLD)
UA2 0-2
UA2 0-22
DAN We
Figure 3: Behavior of the upper bound in Eq. (14) for various B as n increases (mean = std.). For clarity, only the results using UWB are shown. The ECE gap is evaluated by estimating ER,S,, S.o [[CC(f , change B did not result in significant differences.
Ste) ECF(sw, S.,]]. The ECE gap is shown for B = [n3/3] since the
H.2 Bound plot on recalibration reusing training dataset
We further show the plots of our bound for the recalibration scenario in Figure 4. The relationship between n, B, and bound values is similar to that observed in the non-recalibration case. Inter- estingly, the choice of optimal B is crucial for obtaining a small bound value when we conduct recalibration.
(Adam)
MNIST (BGLD)
CIFAR-10 (SGD)
CIFAR- 10 (SGLD)
635 (017-)57)
Figure 4: Behavior of the upper bound in Eq. (141) as n increases for different number of bins (mean + std.) when using UMB after recalibration.
44

---

MNIST [Adam)
MNIST (SGLD)
CIFAR-10 (SGD)
CIFAR11 (SBLD)
505
Figure 5: Behavior of the upper bound in Eq. (14) for various B increases (mean + std.; log- scale) when UMB used. The ECE gap is evaluated by estimating S.. [ECE(fw. Sto) ECE(fw, Ste)l-- These results show that the variance of the ECE gap obtained in non-optimal B settings is large, while the ECE gap in settings based on the optimal B is stable.
H.3 Bound plot for the various number of bins
We examined the ECE gap for various bin sizes using the same setup as Figure 2, and these results presented in Figure 5. We plotted them on a log scale to illustrate how the ECE gap and upper bound behave with different bin sizes. We found that sometimes bins other than the optimal can yield better generalization gap. However, the optimal bin size minimizes the total bias stated in Theorem 5, not necessarily the generalization gap as Theorem 4. On the other hand, the optimal was found to be numerically stable, although, in certain models, high variance observed for certain bin sizes, with the ECE gap occasionally not decreasing as increases.
H.4 Empirical verification of Lipschitz continuous for E{
As discussed in Appendix F, Assumption2 is generally mild in practice. To assess the empirical plausibility of the Lipschitz continuity assumption in Assumption 2, we performed numerical evaluation using ResNet experiments. Specifically, checked whether the value of E[ estimated via bimning, cxhibits relatively smooth variations. These results are presented in Figure 6. The findings indicate that the estimated values fluctuate smoothly to significant degree, provid- ing empirical support for the Lipschitz. continuity assumption. This strengthens the validity of our assumptions and confirms the applicability of our methods in practical, real-world scenarios.
CIFAR1O (RasNal50: SGD, 8- 50)
CIFARIO (ResNat5O SGLD; 8 50)
E7 mitrate
0.8
0.8
0.4
Figure 6: Behavior of the estimator of E|Y [XX) in the ResNet experiments. The red line is the (third-order) Polynomial function fitted to the estimated values of [f)).
45

---

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

---

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

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes].
Justification: We only used the popular benchmark datasets (MNIST and CIFAR-10) that be easily obtained. As for the source code, denoted that our experiments are imple- mented by adapting the source codes of Harutyunyan et al. [15] pettps://githar com/ hrayrhar/f-CMI)
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
conooicy)))))ooooooollmmmmmmmlpp for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. cttcc//ppb........ wccppullcc/aeecc hambllccguidess.. Maaees//ooeeubiiii sssisssssoooosoo onPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]].
Justification: We explained all details of our experimental settings in Section 6 and Ap- pendix G.
Guidelines:
The answer means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [es]_
Justification: We reported the mean = std. of bound values for all experiments in Section and Appendix H. The reason why we cannot see the range of std. in the plot is that its values very small (less than 1 4; see Table for example.).
Guidelines:
The answer NA means that the paper does not include experiments.
48

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification: We used NVIDIA GPUs with 32GB memory (NVIDIA DGX-1 with Tesla V V100 and DGX-2) for MNIST (SGLD) and CIFAR-10 experiments. We also used CPU (Apple M1) with 16GB memory for the other experiments (see Appendix G).
Guidelines:
The answer means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrrppeeeeee httpppuiii//ttiiciiiiieeeeeaaaae
Answer: [Yes].
Justification: We confirmed that our paper does not have issues concerning the NeurIPS Code of Ethics, although the primary emphasis of this paper is on theoretical analysis.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes].
49

---

Justification: Although the primary focus of this paper is theoretical analysis, discussions on the potential impacts of our research are presented in Sections and 7.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The primary focus of this paper is theoretical analysis, and although it in- cludes experiments, their purpose is to numerically validate the theory. Therefore, the concerns raised in the question do not apply.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes].
Justification: We provide citations reference URLs for all of the code, data, and models used in our experiments (see Appendix G). We also declared the name the licence is CC-BY 4.0 in our submission page of OpenReview.
Guidelines:
50

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA].
Justification: The primary focus of this paper theoretical analysis, and although it in- cludes experiments, their purpose is to numerically validate the theory. Therefore, the concerns raised in the question do not apply.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]-
Justification: We do not utilize such services, so the concerns raised in the question are not applicable us.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
51

---

Answer: [NA]
Justification: The primary focus of this paper is theoretical analysis, and has been con- firmed that the concerns raised in the question are not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as institution conducting the review.
52


Reviews:
[{"review_id": "kqZ1EtNadg", "reviewer": "Reviewer_9r8F", "summary": "This paper presents a comprehensive analysis of the estimation bias for expected calibration error (ECE), focusing on two common binning strategies: uniform mass and uniform width binning. The analysis establishes upper bounds on the bias, resulting in an improved convergence rate. Furthermore, these bounds reveal the optimal number of bins needed to minimize the estimation bias. The study also extends the bias analysis to generalization error analysis using an information-theoretic approach, deriving upper bounds that facilitate numerical evaluation for recalibration methods based on training data. Experiments with deep learning models demonstrate that the bounds are nonvacuous, due to the information-theoretic generalization analysis approach.", "questions": "1.\tClarification: what is the ECE gap plotted in Figure 1 and Table 1? Estimated ECE? To my understanding, all the bounds in Figure 1 are quite loose. Shouldn't we plot the left-hand side of Equation 14 for a more accurate comparison?\n\n2.\tHow should the error bars for the bound values in Table 1 be interpreted? What is the source of the randomness?\n\n3.\tIt is not accurate to say that I(S;W)=O(log n) in Line 258, as such Barron’s result assume that samples Z are conditional i.i.d. given model parameter w. However, in the learning context, we always assume that training samples are i.i.d.", "limitations": "The Limitations are well addressed in section 7.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As the author pointed out, the existing literature lacks a theoretical analysis of the estimated ECE and a more principled approach to estimation. This paper addresses and closes this gap.", "weaknesses": "1.\tTightness issue of the upper bound in Corollary 1. It is commendable that the authors included a discussion on the tightness of Equation 12. However, it would be more rigorous to formally establish a minimax lower bound for the estimation bias that applies to all types of estimators. The authors could either use existing results from Tsybakov [33] or construct a worst-case analysis using Le Cam’s method to establish the lower bound. While it is acceptable if the constant does not match the upper bound, it is crucial to demonstrate the rate.\n\n2.\tA drawback of information-theoretic (IT) bounds is the implicit dependency on the algorithm. For example, Theorem 7 appears very similar to Theorem 4, as the recalibration-induced dependence is encapsulated in the CMI term. The authors should provide more commentary on this aspect and clarify the connection between Theorems 6 and 5, as well as which bound is more practical for use.\n\n3.\tIn the caption of Figure 1, It is said that the ECE gap does not change significantly in B. How can we justify that the selection of $B = n^{1/3}$ is better? Figure 1 primarily plots the bound in (14), but as I mentioned earlier, such a bound can be very loose, and more empirical justification should be provided for the selection of optimal B.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.\n\n### Q.1: Derive a minimax lower bound for the total bias.\n**A.** Please see our global response for a minimax lower bound.\n\n### Q.2: Regarding the drawback of IT bounds.\n**A.** \nThe objectives of IT-based generalization bounds and UC bounds differ significantly. The former aims to derive upper bounds that are algorithm-dependent to gain a detailed understanding of how a training algorithm behaves to achieve generalization performance. This also involves analyzing these bounds to quantitatively examine the specific algorithms. In contrast, UC bounds are primarily derived to determine the sample size needed to achieve sufficient generalization performance from a convergence rate perspective, regardless of the algorithms.\n\nNext, we explain the explicit relationship between Theorems 5 (IT bound) and 6 (UC bound). \nIn the proof of Theorem 6, we derive the upper bound of eCMI (fCMI) using the metric entropy of the specific $\\delta$-cover (Eq. 124). Therefore, the metric entropy-based UC bound serves as a further upper bound to the IT bounds. In addition to this, as shown in the global response, we show the new connection between IT and UC bounds using the fat-shattering dimension, which is independent of the model’s dimension. These insights will be included in the revised manuscript.\n\n### Q.3: Regarding the ECE gap in Figure 1 and Table 1.\n**A.** \nFirst, the ECE gap shown in Fig. 1 corresponds to the empirical estimate of the middle expression in Eq. (14). We added the formal definition in Fig. 5 of our additional pdf. \n\nThe ECE gap reported in Tab. 1 is evaluated through the empirical estimator of the statistical bias: $E_{R,S_{re}} E [|E[Y|h_{\\mathcal{I},S_{{re}}}(X)] - h_{\\mathcal{I},S_{{re}}}(X)|] =  E_{R, S_{{re}},S_{te}}ECE(h_{\\mathcal{I}, S_{\\mathrm{re}}},S_{te})$ for existing recalibration methods due to the definition of recalibration. \nFor our proposed method, which uses all training data as recalibration data, it is evaluated as $E_{R,S_{tr}} E [|E[Y|h_{\\mathcal{I},S_{tr}}(X)] - h_{\\mathcal{I},S_{tr}}(X)|] = E_{R,S_{tr},S_{te}}ECE(h_{\\mathcal{I}, S_{tr}},S_{te})$. \n\nThanks to your suggestion, we realized that this explanation is too brief and would like to add a detailed explanation of how we numerically measured the ECE gap in Appendix G.\n\nAlso, we believe that visualizing the estimate of the left-hand term in our theoretical framework is crucial for verifying whether the right-hand side is effectively upper bounded numerically and for analyzing the relationship between these two behaviors (refer to our answer to Reviewer 8W41, Q.4).\n\n### Q.4: Regarding empirical justification of our optimal $B$.\n**A.** \nRegarding the optimal $B$ and the ECE gap, we initially showed only the ECE gap with this optimal $B$ in Fig. 1 for clarity. Motivated by your review, we examined the ECE gap for various bin sizes using the same setup as Fig. 1, and these results are presented in Fig. 5 of the additional PDF. We plotted them on a log scale to illustrate how the ECE gap and upper bound behave with different bin sizes. We found that sometimes bins other than the optimal $B$ can yield a better generalization gap. However, the optimal bin size minimizes the total bias as stated in Theorem 5, not necessarily the generalization gap (Theorem 4). On the other hand, the optimal $B$ was found to be numerically stable, although, in certain models, high variance was observed for certain bin sizes, with the ECE gap occasionally not decreasing as $n$ increases. Finally, to our knowledge, no existing work has evaluated model performance based on ECE from a generalization perspective. Our contribution is the first bound that allows for this numerical evaluation.\n\nTo further assess the optimality of $B$, we need to evaluate the total bias. However, evaluating the upper bound for TCE with benchmark datasets and experiments using CNN and ResNet proved challenging. Therefore, we performed additional experiments using Toy data to more easily evaluate the tightness of the bound and the optimality of $B$. Specifically, we created Toy data following the settings in existing studies and numerically evaluated both sides of Corollary 1. Since Corollary 1 does not involve eCMI, this approach allows for a more accurate assessment of the bound's tightness and optimality. The results are shown in Fig. 4 of the PDF. The first two figures from the right display the total bias and upper bound of Corollary 1 under the optimal bin size, showing that the bound effectively captures the behavior of the total bias. The last two figures plot the TCE gap with different bin sizes compared to the theoretically optimal number of bins. Despite some fluctuations due to a small sample size $n$, the actual behavior closely aligns with theoretical predictions, validating the optimal bin size.\nThese facts will be added in Appendix H.\n\n### Q.5: Regarding the interpretation of the error bars for the bound values in Table 1\n**A.** The error bars in Tab. 1 (and the standard deviation in Fig. 1, which is almost unrecognizable due to its small value) are attributed to the randomness inherent in various experimental settings during model training, i.e., randomness of the training dataset and the initial model parameters. We acknowledge that we have not explained this point clearly enough, so we will include this explanation in Appendix G.\n\n### Q.6: The issue with the statement on Line 258 about $I(S;W) = O(\\log n)$\n**A.** \nYour point is correct, and the cited results consider a setting similar to Bayesian inference, involving conditionally i.i.d. samples. We cited the result as an example illustrating a scenario where mutual information is theoretically controlled. To make the meaning of the citation clearer, we plan to explicitly state that the cited paper addresses conditionally i.i.d. settings.", "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": "sKy1NnYBYB", "reviewer": "Reviewer_Ckaf", "summary": "The paper studies  the expected calibration error  using information-theoretical tools. They derive different tight fCMI and eCMI bounds in this setting. Empirical results show that the results are nonvacuous.", "questions": "Besides fCMI and eCMI based bounds, is it possible to extend the analysis and derive $\\Delta$-L based bounds [37]? These bounds are typically tighter compared to fCMI and eCMI.", "limitations": "The limitations are adequately addressed in the conclusion.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1/ The paper is in general well written. Adequate discussions are given in the main body of the paper and the appendices.\n\n2/ The paper provides the first information-theoretic comprehensive analysis of the bias associated with the ECE when using the test and training datasets.\n\n3/ The theoretical results seem sound. I skimmed through most of the proofs (I did not go through all of them in detail)  but the proofs are well-structured and easy to follow. \n\n3/ Empirical results show that the bound is tight for deep learning models.", "weaknesses": "The only weakness, if any, is perhaps that the paper uses conventional machinery for deriving information-theoretic generalization bounds and that it has not developed novel proof techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.\n\n### Q.1: Regarding the novelty of proof techniques\n### A. \nFirst, it is important to clarify that our techniques are fundamentally different from those used in previous studies, as referenced in [11, 10, 22]. In these studies, the error bound for the ECE is derived through the following three steps: (i) Initially, it is shown that the samples assigned to each bin are i.i.d.; (ii) the Hoeffding's inequality is then applied to derive that $|\\mathbb{E}[Y|f_{\\mathcal{I}}(x)] - f_{\\mathcal{I}}(x)| = O(\\sqrt{n_{te}/B})$ for each bin; and (iii) these error bounds are summed up across all bins to yield $O(B/\\sqrt{n_{te}})$. This approach leads to a slow convergence, which can be attributed to the separate analysis conducted for each bin, requiring multiple applications of concentration inequalities.\n\nIn our approach, we leverage a reformulation of the ECE and TCE as outlined in lines 151 and 152. These equations frame both the ECE and TCE in terms of the relationship between the empirical expectation and its population expectation. This framework allows us to apply concentration inequalities to the errors in all bins combined, specifically to the ECE and TCE themselves. Unlike traditional methods, we employ McDiarmid's inequality—notably, leveraging the technique within its proof—to derive an upper bound without the need to decompose the error into individual bins. This strategy eliminates the necessity to compute the cumulative sum of statistical biases across bins, achieving a more efficient convergence rate of $O(\\sqrt{B/n})$ in expectation.\n\nWhile McDiarmid’s inequality is widely used, our application of it within the binning context is technically novel because it requires meticulous handling of data replacement, as detailed in Appendix D.1.1. This approach in treating the data and applying the inequality offers a marked improvement in the convergence order compared to existing studies.\n\nWe would also like to highlight the novelty of Theorem 6. Our work extends beyond the standard construction of a $\\delta$-cover for Lipschitz functions. As outlined in Appendix E.3, our approach involves a careful design of the $\\delta$-cover to ensure that both the output of the original function $f_w$ and that of the $\\delta$-cover function are categorized into the same bin. This careful alignment is significant to control the discretization error associated with the binning ECE when employing $\\delta$-cover functions. This strategy, which we introduce for the first time, is crucial for enhancing the accuracy and effectiveness of our theoretical framework, providing a novel contribution to the field.\n\n### Q.2: Relation to the result in [37]\n### A. \nThe eCMI appearing in Theorem 4 (Eq. (15)) closely aligns with the $\\Delta L$ bound (loss difference) of Theorem 1 of reference [37].\nSpecifically, the eCMI term in Eq. (15) is not based on the value of ECE itself. Instead, it is derived from the difference between the test data ECE and the training data ECE. This approach aligns with the $\\Delta L$ (loss difference) as shown in Theorem 1 of reference [37].\n\nHowever, extending our bounds using the techniques of [37] presents significant challenges. The $\\Delta L$ bound in [37] defines the loss gap for a single data index $i$ as $\\Delta L_i$ and utilizes the symmetry of each individual index to derive fast rate bounds, as demonstrated in Theorem 4.3. In contrast, our bound requires treating all $n$ indices simultaneously. This necessity arises because ECE is a nonparametric estimator that uses all $n$ indices, unlike usual losses such as the 0-1 loss, where an estimator can be constructed using a single index. Consequently, the techniques from [37] that utilize the symmetry of a single index are not applicable to our context, making it difficult to employ the methods from [37].\n\nFurthermore, as previously discussed, we have derived a minimax lower bound for total bias, amounting to $\\mathcal{o}(1/n^{1/3})$ under Lipschitz conditions. This implies that the problem of estimating ECE is as fundamentally challenging as estimating conditional probabilities in the context of nonparametric regression. Therefore, deriving a fast rate of $\\mathcal{O}(1/n)$ under a parametric learning setting, as seen in [37], is not feasible for the ECE estimation problem.\n\nWe will add these discussions in the revised version of our paper.", "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": "iFB55rwdoJ", "reviewer": "Reviewer_8W41", "summary": "This paper investigates the estimation bias in expected calibration error (ECE) for binary classification models, focusing on uniform mass binning (UMB) and uniform width binning (UWB). The authors present a comprehensive theoretical analysis, establishing upper bounds for the bias and the generalization error. Based on the convergence rates of binning and statistical bias, they identify the optimal number of bins to minimize the total estimation bias.", "questions": "Recent information-theoretic bounds have shown improved rates of O(1/n) under the interpolating regime, and also direct computational tractability with loss CMI or entropy metrics. It may be worth some discussions on whether these techniques can be adopted to acquire tighter bounds.\n\nTighter Information-Theoretic Generalization Bounds from Supersamples. ICML 2023.\n\nRethinking Information-theoretic Generalization: Loss Entropy Induced PAC Bounds. ICLR 2024.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides a comprehensive analysis of the estimation bias in ECE, providing upper bounds and optimal bin size choices for both UWB and UMB.\n* The authors further derive upper bounds for the generalization error between ECE and TCE using an information-theoretic approach.\n* Numerical experiments on deep learning tasks confirm that the derived bounds are non-vacuous.", "weaknesses": "* The provided results only apply to binary classification, and require Lipschitz continuity which may not be necessarily satisfied in deep learning models. Also, these bounds are analyzing the ECE using test data but not training data, making them less applicable since test data are not always available in practice.\n* The convergence rates of the information-theoretic generalization bounds heavily depend on the actual rate of eCMI and fCMI measures, which are not directly clear in analysis. In theorem 6, the authors show that eCMI scales as O(log n) based on metric entropy, but this bound involves the dimensionality d, and is thus hardly applicable to deep learning models.\n* For experimental results, only the statistical bias is evaluated but not the total generalization error. It is also hard to see to what extent these bounds are tight in the current results. These bounds are also hard to estimate due to the existence of eCMI or fCMI measures. I would suggest the authors additionally consider some synthetic settings where TCE, eCMI, and fCMI are analytically tractable to show the tightness of the bounds. (maybe Gaussian data points?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.\n\n### Q.1: Regarding the setting of binary classification and the Lipschitz continuity.\n**A.** \nAlthough our study focuses on binary classification, we can readily extend it to multi-class settings. In existing studies [22, 8], the top-label calibration error (top CE, TCE) has been proposed as a measure for multi-class calibration. For instance, in a $K$-class classification problem, we obtain predictions for each label by the final softmax layer in neural networks. We assume that $f_w(x)\\in \\mathbb{R}^K$ predicts the label by $C:=\\mathrm{argmax}_k f_w(X)_k$, where $f_w(X)_k$ represents the model’s confidence of the label $k \\in K$. The top CE (TCE) is then defined using the highest prediction probability output by $f_w: TCE:=\\mathbb{E}|P(Y=C| f_w(X)_C)-f_w(X)_C|$. By considering binning only for the top score, we can compute the ECE (top-binning ECE) in a manner similar to binary classification. In this case, since we focus only on the top label, we can treat top-binning ECE in the same way as binary classification, which results in the same generalization and total bias bounds. Our results, therefore, offer flexibility to analyze the widely used top-label calibration error in multi-class settings. We will add this discussion to the paper.\n\nRegarding Assumption 2, this does not imply the Lipschitz continuity of the function $f_w(\\cdot)$ itself, but the Lipschitz continuity of the conditional expectation $\\mathbb{E}[Y|f_w(x)=v]$, which is a kind of characteristic of the data itself. For a more comprehensive discussion on the Lipschitz continuity assumption, please refer to the global response provided above and the response to Reviewer kktU (Q1).\n\n### Q.2: Regarding the necessity of test dataset in the ECE evaluation.\n**A.** \nIf your question concerns the difference between IT-based bounds and generalization error upper bounds like PAC-Bayes, which can be evaluated using only training data, model distribution, and prior distribution, note that the IT-based upper bound can still be evaluated even if only training data is available in practice. As discussed in Line 257, $\\mathrm{eCMI} \\leq \\mathrm{fCMI}\\leq  I(W;S_\\mathrm{tr})$ [13,15] holds, and $I(W;S_\\mathrm{tr})$ only depends on the training dataset. Thus, by replacing eCMI and fCMI in Theorem 4 and 5 with this mutual information, we get the bound that is independent of the test dataset. On the other hand, the inclusion of test data dependence in eCMI and fCMI through the index \\tilde{U} provides the benefit of tighter bounds.\n\nIf our explanation does not align with your concern, please provide further questions during the discussion phase.\n\n### Q.3: Regarding the convergence behavior of our bounds and the vacuousness of the metric-entropy-based bound\n**A.** Your points are accurate. The primary distinction between IT bounds and UC bounds lies in their objectives:\n- IT Bounds: These are algorithm-specific and aim to provide detailed insights into how a particular algorithm performs in terms of generalization. They focus on analyzing these bounds to understand the performance of specific algorithms. By further assuming specific algorithm classes, such as stable algorithms or stochastic convex optimization, we can derive the theoretical behaviors of the mutual information.\n- UC Bounds: These are derived to determine the necessary sample size for achieving generalization performance based on convergence rates, independent of the algorithm used. Typically, UC bounds employ metric entropy to derive results. In response to your suggestion, we provide UC bounds that use the fat-shattering dimension, which is independent of the model’s dimension as detailed in the global response above.\n\n### Q.4: Regarding the statistical bias evaluation, and the TCE evaluation experiment on the synthetic experimental settings.\n**A.** \nEvaluating the upper bound for TCE proved challenging with benchmark datasets and experiments using CNN and ResNet. However, we were able to conduct TCE evaluation experiments using a synthesized dataset based on the settings in [Z]. The results are shown in Fig. 4 of our additional PDF. \n\nWe numerically evaluated both sides of Corollary 1. Since Corollary 1 does not involve eCMI, this approach allows for a more accurate assessment of the bound’s tightness and optimality. The first two rightmost figures display the total bias and upper bound of Corollary 1 under the optimal bin size, demonstrating that the bound effectively captures the behavior of the total bias. The last two figures show the TCE gap plotted against different bin sizes compared to the theoretically optimal number of bins. Despite some fluctuations due to a small sample size $n$, the actual behavior closely aligns with theoretical predictions, validating the optimal bin size.\n\n[Z]: J. Zhang et al. Mix-n-Match: Ensemble and Compositional Methods for Uncertainty\nCalibration in Deep Learning. ICML2020.\n\n### Q.5: Regarding the improvement of the convergence rate\n**A.** \nAs discussed in the reply to Reviewer Ckaf (Q.2), we cannot use the technique proposed in [37] directly. Moreover, we have derived a minimax lower bound for total bias, which is $\\mathcal{o}(1/n^{1/3})$, implying that the problem of estimating TCE is as inherently challenging as estimating conditional probabilities in the context of nonparametric regression. Therefore, deriving a fast rate of $\\mathcal{O}(1/n)$ under a parametric learning setting is not feasible for the ECE estimation problem. However, discussing whether the techniques adopted in the papers you suggested can be used to improve the constants of the bounds constitutes important future work. We would like to specify this in the conclusion section.", "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": "8FGV8j9ZaL", "reviewer": "Reviewer_kktU", "summary": "This paper analyzes the estimation bias and generalization error of the expected calibration error (ECE). Specifically, in a binary classification setting, the authors provide an upper bound for the total bias with an improved convergence rate, applicable to both uniform mass and uniform width binning strategies. They also determine the optimal number of bins to minimize the total bias. Furthermore, the authors utilize the information-theoretic generalization framework, particularly the Conditional Mutual Information (CMI) framework, to characterize the generalization of ECE.", "questions": "1. Does Assumption 2 hold true in practice? Is there a way to verify it? Additionally, what is the motivation behind assuming $n_e\\geq 2B$? How is this assumption utilized? If $n_{te}\\leq 2B$, will Theorems 2 and 3 still be valid?\n\n2. In the proof sketch of Theorem 2, you mention that $\\mathrm{ECE}$ and $\\mathrm{TCE}$ could be re-written. While they seem correct to me, could you elaborate on how $\\mathrm{TCE}(f_\\mathcal{I})$ is obtained in the form shown in Line 152? I did not find the details in the complete proof.\n\n3. According to Theorem 5, do the upper bounds indicate that UWB is a better binning strategy than UMB, given that UMB has an additional $\\mathrm{fCMI}$ bias term? It seems that only UMB's expected binning bias is sensitive to the training data, which might be seen as a disadvantage in terms of the upper bound.\n\n4. The writing can be significantly improved. For example, in Line 244, you mention \"Our theory might guarantee the ECE under test dataset for them.\" Do you mean your theory might guarantee low ECE under the test dataset? Additionally, in Lines 251-252, \"This implies that if the model generalizes well, evaluating the ECE using the training dataset may better reduce the total bias than that using test dataset.\" Why does evaluating ECE reduce total bias? What we really care about is ECE on unseen/test data. How does evaluating ECE on training data affect this purpose?\n\n5. Why is the metric entropy method only used for UWB? It seems that you upper bound $\\mathrm{eCMI}$ by the $\\mathrm{fCMI}$ term first in your proof. What prevents you from giving a similar result for UMB?\n\n6. In Line 339-340, you mention that \"a notable trend towards acquiring relatively stable nonvacuous bounds can be observed when adopting $B =\\lfloor n^{1/3} \\rfloor$\", but according to Figure 1, it seems $B=52$ is tighter than $B=B =\\lfloor n^{1/3} \\rfloor$ in most cases. Could you clarify this?\n\n7. Since $\\mathrm{eCMI}$ and $\\mathrm{fCMI}$ terms are key components in both standard generalization error and expected total bias of calibration error, do you have any new insights into the relationship between calibration and generalization from this perspective?", "limitations": "The authors have thoroughly discussed some limitations of this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper achieves a tighter bound for total bias compared to previous works.\n\n2. The optimal number of bins is determined using the upper bound of the total bias.", "weaknesses": "1. As the authors themselves note, a significant limitation is that the analysis in this work is only applicable to binary classification.\n\n2. Some assumptions (e.g., Assumption 2) are not well justified.\n\n3. The writing has significant room for improvement; several arguments are unclear or misleading.\n\nPlease find more details in the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.\n\n### Q.1: Regarding the strictness of Assumption 2 and the assumption of $n_e\\geq 2B$\n**A.** \nFirst, please refer to the global response for the discussion on the necessity of Assumption 2. In practice, Assumption 2 is reasonably mild. For example, if label distributions follow a Bernoulli distribution with the mean depending on the input $x$, Assumption 2 is met [E]. This is a relatively weak assumption in binary classification. Moreover, existing studies have shown that many common benchmark datasets are consistent with this assumption (e.g., [F]). \nTo ascertain whether the assumption of Lipschitz continuity is empirically plausible, we conducted a numerical evaluation based on ResNet experiments. This involved checking if the value of $E[Y|f(X)=v]$, estimated through binning, exhibits relatively smooth variations. These findings are depicted in Fig. 6 of the attached PDF. The results demonstrate that the estimated quantity $E[Y|f(X)=v]$ fluctuates smoothly to a considerable extent, thereby supporting the validity of the Lipschitz continuity assumption. This supports the robustness of our assumptions and the applicability of our methods in real-world scenarios. We will incorporate these results into our paper.\n\nRegarding the assumption $n_e\\geq 2B$, it is crucial for UMB, as it guarantees the proper construction of bins. In UMB, we first use $B$ samples to build the bins. We then partition the remaining $n_e−B$ samples evenly across these bins. If $n_e < 2B$, we have $n_e−B< B$, preventing equal distribution of samples, thereby rendering UMB inapplicable. Conversely, UWB does not require this assumption since it divides the $[0,1]$ interval into equal-width bins. We will clearly outline this distinction in the revised paper.\n\n[E] Y. G. Yatracos. A Lower Bound on the Error in Nonparametric Regression Type Problems. Ann. Stat., 1988.\n[F] B. Zadrozny et al. Transforming Classier Scores into Accurate Multiclass Probability Estimates. KDD '02.\n\n###  Q.2: How to obtain TCE and ECE reformulations.\n**A.** \nThe proofs of those reformulations are provided in Appendix C, specifically in Lemma 1. In the revised version, we will explicitly reference this lemma to avoid any confusion.\n\n###  Q.3: Reason why UMB has an additional term compared to UWB in Theorem 5,\n**A.** \nThe additional term (fCMI) arises because UMB uses training data to construct bins. This means we must consider overfitting not only during learning for $f_w$ but also in the bin construction process. This leads to extra fCMI terms in UMB compared to UWB, which is a potential disadvantage. Practically, UMB is designed to prevent issues with bins having no samples when $n_e$ is small. When sufficient data is available, we can partition the entire dataset into training data for learning $f_w$ and another dataset for bin construction. This approach avoids the extra fCMI term and has been explored in previous work [22].\n\n### Q.4: The meaning of Line 244 and Lines 251-252\n**A.** \nIntent of Line 244: Our goal is to show that, similar to how ERM bounds test loss by training loss plus a generalization gap, our Theorem 4 bounds test ECE by training ECE plus a generalization gap. Some studies [21, 26, 36] use regularization to minimize training ECE in their algorithms, so if a small eCMI or fCMI ensures a small generalization gap, the upper bound of test ECE will also be minimized, thus providing theoretical assurance akin to ERM’s generalization theory.\n\nLines 251-252: In ERM, the expected loss can be estimated with a validation dataset, with an error rate of $O(1/n_{te}^{1/2})$. However, ECE converges to TCE at a much slower rate of $O(1/n_{te}^{1/3})$. Increasing validation data does not significantly improve this rate. Since training dataset size is often much larger than the test data size, if the generalization error (eCMI or fCMI) is small, using training data to estimate ECE could result in a smaller bias of $O(1/n_{tr}^{1/3})$. Thus, using training data for estimating TCE could be a promising approach. We will clarify these points in the revised paper.\n\n### Q.5: The difficulty of deriving the metric entropy bound for for UMB\n**A.** \nDeriving the metric entropy bound for UMB is challenging due to the difficulty of constructing the appropriate $\\delta$-cover of functions. As highlighted in Eq. 117 and Eq. 120, we need to set $\\delta$ smaller than the width of the bins. In the case of UWB, the bin width is $1/B$; however, in UMB, the bin width is not fixed and varies according to the data. This dependency adds complexity to preparing the appropriate $\\delta$-cover.\n\n### Q.６: Clarification in Line 339-340\n**A.** \nBased on the additional experiments, we will revise the explanation as follows:\n- The optimal $B$ is determined based on the upper bound of the total bias (Thoerem 5) and does not necessarily minimize the generalization error bound (Theorem 4). However, setting $B$ in this way ensures that we avoid vacuous values, numerical instabilities and even increase of the ECE gap as we increase $n$.\n\nFor the details, please see Fig. 5 in the PDF and response to Reviewers 9r8F (Q.4) (and to Reviewer 8W41; Q.4 for TCE and the total bias evaluation on toy data experiments.).\n\n### Q.7: New insights into the relationship between calibration and generalization\n**A.** As stated in the global response, the total bias of the TCE and ECE matches the rate achieved in nonparametric regression, conclusively showing that estimating TCE is as challenging as estimating conditional probabilities using nonparametric regression. Thus, compared to usual generalization problems such as classification error, evaluating TCE requires more samples, and achieving a fast learning rate of $O(1/n)$ under parametric learning settings seems to be not possible, highlighting a distinct difference.", "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:
We would like to express our sincere appreciation for your insightful reviews and suggestions. First, we will address the common concerns raised by the reviewers. Following that, we will address each individual question.

## Discussion about the lower bound of the total bias
As pointed out by Reviewer 9r8F, here we show the lower bound of the total bias by using the result of the nonparametric binary classification in [A]. The method in [A] is the extension of Fano's method focusing on evaluating mutual information (MI) with the Yang-Barron method [B].

Conditioned on $W=w$ we express $v=f_w(x)$. Let $p(v)$ be the probability density of $v$ induced by $p(x)$ using $f_w(x)$ and $\mathcal{V}\subset [0,1]$ be its support. Define $g(v)=\mathbb{E}[Y|f_w(x)=v]=\mathrm{Pr}[Y=1|v]$. Let $\mathcal{G}$ be a class of candidate conditional probability functions over $\mathcal{V}$ and every candidate $g\in\mathcal{G}$ satisfies $0\leq g(v)\leq 1$ for all $v\in\mathcal{V}$. 

We need the following assumption to control MI [A]; Assume that $\mathcal{G}$ has at least one member $g^*$ that is bounded away from 0 and 1, i.e., there exist constants $0<c_1\leq c_2<1$ such that $c_1\leq g^*\leq c_2$. Instead of Assumption 2 in our paper, assume that for any $g\in\mathcal{G}$ and for any $v,v'\in\mathcal{V}$, $|g(v)-g(v')|\leq C|v-v'|^\beta$ with $C>0$. When $\beta=1$, this becomes Assumption 2.

Under the above two assumptions, the following relation holds; 
$$
    \sup_{g\in\mathcal{G}}\mathbb{E}|\mathrm{TCE}(f_w)- \mathrm{ECE}(f_w,S_{te})|\geq \inf_{\hat{g}}\sup_{g\in\mathcal{G}}|\mathbb{E}[|g(V)-V|]-\mathbb{E}[|\hat{g}(V)-V|]|\succeq  n^{-\beta/(2\beta+1)},
$$ where $\hat{g}$ is over all valid estimators for $g$ using $n$ samples $(X_m,Y_m)_{m=1}^n$ and the expectation is taken with respect to true $g$. Note that the left-hand side of the above corresponds to the total bias in our paper. Note that the term $\mathbb{E}[|g(V)-V|]$ is the TCE. If we consider $\hat{g}$ as the kernel density estimation, the above result can be used as the lower bound of the kernel ECE, which is also a popular method to estimate the TCE. 
  
From this, when $\beta=1$, the upper bound of our total bias (e.g., Eq.(13)) achieves the same rate as the lower bound thus the binning achieves the optimal rate. However, when $\beta>1$, the upper bounds do not reach the lower bound. As discussed in lines 191-204, this limitation arises because binning cannot exploit the underlying smoothness of the distribution.
 
In [A], the L1 minimax rate of conditional probability is given as 
$$
    \inf_{\hat{g}}\sup_{g\in\mathcal{G}}\mathbb{E}|\hat{g}(V)-g(V)|\succeq  n^{-\beta/(2\beta+1)}.
$$
Combining this with our results, we can see that the rate of the total bias matches the rate of nonparametric regression, conclusively showing that **estimating TCE is as challenging as estimating conditional probabilities.**  We will incorporate these results and proof into our revised paper.

[A] Minimax nonparametric classification rates of convergence, Y. Yang. IEEE Transactions on Information Theory, 1999

[B] Information-theoretic determination of minimax rates of convergence, Y. Yang and A. Barron. The Annals of Statistics, 1999.

## Connection between IT-bound and UC theory (fat-shattering dimension)
s pointed out by Reviewer 8W41, the bound by metric entropy depends on the model's dimensionality, making them unsuitable for large models such as neural networks. Some existing studies [13,15] present the upper bound of the eCMI and fCMI by the dimension-independent complexities, such as the VC dimension for binary classification and connecting IT theory to UC theory. 

Inspired by these results, here we provide the upper bound of eCMI and fCMI using such dimension-independent complexities. As provided in the lower bound analysis above, since TCE estimation is similar to the nonparametric regression, we use **fat-shattering dimension** [C] to upper bound the eCMI. Specifically, if our model class $f_w(\cdot)$ satisfies $\delta/4$-fat dimension with $d_{\delta/4}$ for $\delta\in[0,1]$, we have
$$
eCMI(Eq.15)\leq fCMI(Eq.(17))= O\Big(d_{\delta/4}\log \frac{n}{d_{\delta/4}\delta} \log \Big(\frac{n}{\delta^2}\Big)\Big) 
$$
which results in the dimension-independent upper bound. To evaluate the fat-shattering dimension for specific models, see [D] for the details. We will incorporate these results into our paper.

[C] Scale-sensitive dimensions, uniform convergence, and learnability. N. Alon, et.al., Journal of the ACM, 1997

[D] Vapnik-Chervonenkis Dimension of Neural Nets. Peter L. Bartlett

## Discussion about Assumption 2
Here, we discuss the necessity of Assumption 2. Estimating TCE involves nonparametric regression of $E[Y∣f(X)=v]$. For finite samples, smoothness assumptions like Lipschitz continuity are required; without them, small changes in $v$ could cause large variations in label outcomes, making estimation impossible [E]. Such smoothness assumptions are standard in nonparametric regression, including kernel-based ECE. Without these assumptions, increasing the sample size would not ensure that training (or test) ECE converges to TCE. As noted in our minimax lower bound discussion, the absence of smoothness ($\beta\to 0$) leads to increasing bias. 

[E] Minimax optimal conditional density estimation under total variation smoothness, M. Li, et. al., Electron. J. Statist, 2022.

## Additional numerical validation
We add numerical experiments addressing the concerns raised by the reviewers in PDF:
- Toy data experiments to evaluate the total bias and optimality of $B$ (Fig. 4). For the detailed explanation, see the reply to Q.4 of Reviewer 8W41.
- A logarithmic plot of the ECE gap in Figure 1 to clarify the behavior of the bounds (Fig. 5). For the detailed explanation, see the reply to Q.4 of Reviewer 9r8F.
- Experiments validating the Lipschitz continuity in Assumption 2 (Fig. 6). For the detailed explanation, see the reply to Q.1 of Reviewer kktU.

Meta-review: This work provides a theoretical analysis into the estimation bias for expected calibration error in the binary classification setting, including upper bounds on the bias and discussion of optimal binning strategies. Most reviewers responded positively, highlighting the quality of the writing, the empirical study on the tightness of the obtained bounds, and how the work closes an important gap in the literature. While there was some concern about the restriction to the binary classification setting, the authors claim that the study can be extended to multi-class settings. Including this discussion will greatly improve the applicability of this work. Provided these inclusions are incorporated into the camera-ready submission, I recommend acceptance.
Decision: Accept (poster)