Information-theoretic Generalization Analysis for Expected Calibration Error

Authors: futoshi  futami
masahiro  fujisawa
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:21:52

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.

Main paper: 
 introduction: 
 Ensuring reliable predictions from machine learning models holds paramount importance in risksensitive applications such as medical diagnosis [18] . To achieve this, it is essential not only to evaluate the accuracy of the point predictions of 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 probabilities of a model align with the actual frequency of true labels, and a 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 on their calibration performance both theoretically and numerically. In this paper, we assume a 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 is 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 [0, 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 te . 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, to confirm the accuracy of calibration evaluation using the ECE. Furthermore, it is vital to identify the conditions under which our training algorithm achieves a low ECE or TCE for unknown test datasets. This can be paraphrased as the importance of conducting generalization error analysis under the ECE and TCE. Nevertheless, research on these aspects remains 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-mass binning (UMB) [13, 12] . Consequently, there remains a significant gap in the comprehensive theoretical 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 scenarios utilizing UMB, there has been no corresponding analysis for uniform-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 is successfully derived from these results. With this optimal bin size, the total bias of the ECE exhibits a rate of O(1/n 1/3 te ) for both UWB and UMB, where n te is 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 information-theoretic (IT) analysis [43, 15, 17] . Directly applying the existing IT analysis is, however, challenging because the ECE on the training dataset is no 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. 
preliminaries: 
 For a random variable denoted in capital letters, we express its realization with corresponding lowercase letters. Let P X denote the distribution of X, and let P Y |X represent the conditional distribution of Y given X. We express the expectation of a random variable X as E X . The symbol I(X; Y ) represents the mutual information (MI) between X and Y , while I(X; Y |Z) is the conditional MI (CMI) between X and Y given Z. We further define [n] = {1, . . . , n} for n ∈ N.We consider binary classification in this paper. Let Z = X × Y 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 S tr := {Z m } n m=1 denote the training dataset consisting of n samples drawn i.i.d. from D. We also define the test dataset comprising n te samples as S te ∼ D nte . Let f w : X → [0, 1] be a parametric probabilistic classifier that outputs a prediction of the probability Y = 1, and we denote its parameters as w ∈ W ⊂ R d . We consider a randomized algorithm A : Z n × R → W, where R ∈ R is the randomness of an algorithm, independent of all other random variables. For fixed R = r and S tr = s, A(s, r) is a deterministic function and f A(s,r) (x) is the prediction at point x given s and r. We evaluate the accuracy of the trained predictor f w using the loss function l : W × Z → [0, 1], where l(A(s, r), z) denotes the loss incurred by the prediction f w (x) for label y. For example, the zero-one loss is commonly used to evaluate the accuracy. Then, the training loss is given by LStr := 1 n n m=1 l(A(S tr , R), Z m ) and the test loss is given as L Z := l(A(S tr , R), Z) where Z ∼ D. We also define the expected version of them as L S := E Str,R LStr and L D := E Str,Z,R L Z .In this section, we introduce a calibration metric and its corresponding estimator. The most widely known metric is the true calibration error (TCE) [31, 10, 12] defined asEQUATIONconditioned on W = w. Unfortunately, evaluating the TCE directly is challenging due to the intractable calculation of E[Y |f w (X)]. To avoid this issue, we often use the binning method [11, 48, 49] . This method estimates the TCE by partitioning the prediction probability range [0, 1] into B intervals I = {I i } B i=1 (called bins) and averaging within each bin using the evaluation dataset S e := {Z m } ne m=1 ∈ Z ne , where we assume n e ≥ 2B. For instance, we have S e = S te when the test dataset is used for evaluation. The TCE estimator on the basis of I, with S e , is defined asEQUATIONwhere |I i | := ne m=1 1 fw(xm)∈Ii , p i := |Ii| ne , fi,Se := 1 |Ii| ne m=1 1 fw(xm)∈Ii f w (x m ), and ȳi,Se := 1 |Ii| ne m=1 1 fw(xm)∈Ii y m . This estimator is called the expected calibration error (ECE) 3 .There are two common methods to construct I. One is uniform width binning (UWB) [11] , which divides the [0, 1] interval into equal widths as follows: I i = ((i -1)/B, i/B] for i in [B] . The other approach is 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 f m = f w (x m ) for x m ∈ S e , let f (m) be the m-th order statistics of (f 1 , . . . , f ne ), and then set I 1 = (0, u 1 ], I 2 = (u 1 , u 2 ], . . . , I B = (u B-1 , u B ] for b ∈ [B-1] and u b := f (⌊neb/B⌋) with u B = 1. Here, ⌊x⌋ := max{m ∈ Z : m ≤ x}.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 w ) -ECE(f w , S e )|. We call this bias as the total bias. To facilitate the total bias analysis, we adopt the following definition of the binned function of f w [24] :EQUATIONwhich represents the conditional expectation within each bin. When we evaluate the ECE on S e = S te , we expect that ECE(f w , S te ) will converge to TCE(f I ) = E|E[Y |f I (x)] -f I (x)| with increasing n te . However, TCE(f I ) underestimates TCE(f w ) [24, 10] , that is,EQUATIONwhich implies that ECE(f w ) is a biased estimator of TCE(f w ). Therefore, comprehending the extent of this bias is crucial to an accurate calibration performance evaluation. Nevertheless, previous studies [24, 13, 12] have exclusively focused on the statistical bias in UMB, defined as |TCE(f I ) -ECE(f w , S te )| as discussed in Section 1. This brings us to an analysis of the total bias for both UWB and UMB.We now briefly outline the IT analysis using the evaluated CMI (eCMI) [34] that we utilize in our study. Consider Z ∈ Z n×2 as an n × 2 matrix, where each entry is drawn i.i.d. from D. We refer to this matrix as a supersample. Each column of Z has indexes {0, 1} associated withU = (U 1 , . . . , U n ) ∼ Uniform({0, 1} n ) independent of Z.We denote the m-th row as Zm with entries ( Zm,0 , Zm,1 ). In this setting, we consider ZU := ( Zm,Um ) n m=1 as the training dataset and Z Ū := ( Zm, Ūm ) n m=1 as the test dataset with n te = n, where Ūm = 1-U m . With these notations, we can see thatL Z := 1 n n m=1 l(A( ZU , R), Zm,Um ) corresponds to the training error since L S = E Z,R,U L Z . Also, L Z := 1 n n m=1 l(A( ZU , R), Zm, Ūm ) corresponds to the test error, L D = E Z,R,U L Z .The described settings, called the CMI setting [17] , lead to the following theorem. Theorem 1 (Theorem 6.7 in Steinke & Zakynthinou [34] ). Under the CMI setting, we haveEQUATION3 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 a clear distinction from the estimator obtained through binning.where eCMI(l) := I(l(A( ZU , R), Z); U | Z) and l(A( ZU , R), Z) is an n × 2 loss matrix obtained by applying l(A( ZU , R), •) elementwise to Z.The reason we focus on IT analysis is that it enables algorithm-dependent analysis. The conventional uniform convergence theory [37] focuses solely on function classes to derive bounds. However, recent findings suggest that models trained by some algorithms are not well calibrated but show high accuracy [11, 24] . Therefore, it 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.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 a function f : X → R has the bounded differences property if for some nonnegative constants c 1 , . . . , c n ,EQUATIONIf X 1 , . . . , X n are independent random variables taking values in X , we define the real-valued random variable asEQUATION)If f has the bounded difference property with constants c 1 , . . . , c n , then we haveEQUATIONCombining this lemma with Holder inequality, we have the following relation,EQUATION)We often consider the case where -1 ≤ f ≤ 1. This implies that c i = 2 for all i. ThenEQUATION)Another situation is that given a function g :X → [-1, 1], consider f (x 1 , . . . , x n ) := 1 n n i=1 f (x i )., where f corresponds to the empirical mean of some function g. This implies that c i = 2/n for all i. ThenEQUATION)Lemma 3 (Used in the proof of McDiarmid's inequality). Given a bounded difference function f , for any t ∈ R, we have E e t(f (X1,...,Xn)-E[f (X1,...,Xn)]) ≤ e Proof. Here we express the samples in S te as{Z ′ m } nte m=1 = {(X ′ m , Y ′ m )}.As for the first inequality, it is the consequence of the Jensen inequality, as follows;EQUATIONwhere we used the Jensen inequality.As for the second inequality, we separately prove UWB and UMB. 
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 as follows:EQUATIONWe can derive the following upper bound of Eq. ( 6) by using the triangle inequality,EQUATIONwhere Bias bin (f w , fI ) := |TCE(f w ) -TCE(f I )| and Bias stat (f w , S te ) := |TCE(f I ) - ECE(f w , S te )|.We call the former as the binning bias, which arises from nonparametric estimation via binning, and the latter as the statistical bias caused by estimation on 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 = w, f w (x) is absolutely continuous w.r.t. the Lebesgue measure.This assumption means that f w (x) has a probability density, and it is satisfied without loss of generality 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 2 (Statistical bias analysis). Given W = w, under Assumption 1, we haveEQUATIONEQUATIONProof sketch. First, we reformulate the ECE asECE(f w , S te ) = B i=1 |E (X,Y )∼ Ŝte (Y -f w (X)) • 1 fw(X)∈Ii | and the TCE as TCE(f I ) = B i=1 |E (X,Y )∼D (Y -f w (X)) • 1 fw(X)∈Ii |,where Ŝte is the empirical distribution of S te . The proof of this reformulation is shown in Appendix C.1. Thanks to these transformations, our analysis does not have the problem that the UWB method can lead to bins without any samples. By evaluating the exponential moment for UWB using McDiarmid's inequality under these reformulation, we have, for any λ ≥ 0,EQUATIONUsing this, we can derive both the bias and the high probability bound. We can derive a similar bound for UMB. The complete proof is provided in Appendix D.1.Eq. (8) shows that ECE(f w , S te ) overestimates TCE(f I ) in expectation. Combined with Eq. ( 4), we can see that ECE(f W , S te ) cannot be the upper or lower bound of TCE(f w ) in expectation. This emphasizes the importance of the rigorous bias analysis of |TCE(f w ) -ECE(f w , S te )|.Comparison with existing work: Eq. ( 9) provides better generality and a tighter bound than prior results. Our bound exhibits O( B/n te ) in expectation (and O p ( B/n te ) in high probability w.r.t. S te proved in Appendix D.3.). In contrast, the existing analysis [13, 12, 24] provided a similar bound focused on UMB scale as O(B/ √ n te ) in expectation (and O p ( B log B/n te ) in high probability). In terms of generality, our derivation techniques can be applied to both UMB and UWB, whereas existing bounds are limited to UMB.The proof procedure in existing work [13, 12, 24] involves (i) showing that the samples assigned to each bin are i.i.d., (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 to 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 a more detailed explanation of this in Appendix D.6.Next, we show the results of our binning bias analysis under the following common assumption in the nonparametric estimation context [36] .Assumption 2. Given W = w, E[Y |f w (x)] satisfies L-Lipschitz continuity.Theorem 3 (Binning bias analysis). Given W = w, under Assumptions 1 and 2, we haveE Ste Bias bin (f w , f I ) ≤ 1+L B(for UWB),EQUATIONProof sketch. In Appendix D.4, we show thatBias bin (f w , f I ) ≤ E|E[Y |f w (X)] -E[Y |f I (X)]| + E|f w (X) -f I (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 O(1/B) because UWB divides the interval into equal widths. For UMB, we 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 = w, under Assumptions 1 and 2, we haveEQUATIONThe above result evidently implies a trade-off concerning B. Intuitively, this indicates that while a larger number of bins, B, improves the precision of f w estimation, accurately estimating the conditional expectation requires a 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 = O(n 1/3 te ) and givesEQUATIONSince 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 E[Y |f w (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 O(1/n 1/3 te ) under Assumption 2. 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.We finally remark that the total bias of binning using UWB and UMB cannot be improved even assuming the Hölder continuity for E[Y |f w (x)] instead of Assumption 2. This is because the binning bias includes the error term E|f w (X) -f I (X)| = O(1/B) even under the Hölder continuity. Thus, we suffer from the slow converge E Ste Bias tot (f w , S te ) = O(1/n 1/3 te ) under the optimal bin size B = O(n 1/3 te ) (see Appendix D.5 for this proof). According to Tsybakov [36] , the lower bound of the nonparametric estimation is O(1/n β/(2β+1) te) under β-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 of 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 a 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.The expected generalization error between the ECE and TCE can be defined through the total bias notion, that is, E R,Str Bias tot (f W , S tr ) := E R,Str |TCE(f W ) -ECE(f W , S tr )|. In this section, we derive the upper bound of E R,Str Bias tot (f W , S tr ) 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, Bias stat (f w , S tr ) := |TCE(f I ) -ECE(f w , S tr )|, using a similar proof technique as in Theorem 2. Theorem 4 (Generalization error bound of the ECE). Under the CMI setting and under Assumption 1, for both UWB and UMB, we haveEQUATIONwhere eCMI( lEQUATIONProof 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/ √ n). Therefore, we derive the extended version of Eq. ( 5) by correlating B bins according to Eq. (10) and combining this with the Donsker-Varadhan lemma. The complete proof can be found in Appendix E.1.Comparing Eq. ( 14) with Eq. ( 9) in Theorem 2, we find that eCMI measures the additional bias that arises when evaluating the ECE using training data that are dependent on the trained model f w instead of test data, which are independent of it. In other words, the term E R,Str,Ste |ECE(f W , S te )-ECE(f W , S tr )| 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 in the setting of recalibration in Section 4.3.In Appendix E, we derive the binning bias under the training data similar to Theorem 3. By combining 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 Assumptions 1 and 2, we haveEQUATIONIn the above, eCMI( l) is defined as Eq. (15) andEQUATIONwhere x denotes the n × 2 matrix obtained by projecting each element of z, and f A( ZU ,R) ( X) is the n × 2 matrix calculated by the elementwise application of f A( ZU ,R) (•) to x.When comparing Eq. ( 12) with the above results, it is observed that an additional bias, eCMI (including 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 a 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, 38] . 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 minimize the upper bound in Theorem 5. If eCMI( l) and fCMI are sufficiently small compared with n, for example, O(log n) (we discuss this in Section 4.2), then, the optimal bin size can be derived as B = O(n 1/3 ) by minimizing Eq. ( 16) w.r.t. B. Such an optimal B leads toEQUATION) According to Eq. ( 13) and the above result, we can anticipate that E R,Str Bias tot (f w , S tr ) is much smaller than E Ste Bias tot (f W , S te ) because the number of training data is often much larger than that of test data (n ≫ n te ). 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.In this section, we analyze how additional biases, i.e., eCMI( l) and fCMI, behave. The initial observation is that the following relation holds [17] : eCMI( l) ≤ fCMI ≤ I(W ; S). Furthermore, we can see that I(W ; S) = O(log n) under certain constrained conditions, such as the conditionally i.i.d. setting when f w (x) is the underlying probability model for p(y|x; w) with W being compact 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 f w belongs to. Suppose that F with the metric ∥ • ∥ ∞ has the metric entropy, log N (F, ∥ • ∥ ∞ , δ), with the parameter δ (> 0). That is, there exists a set of functions F δ := {f 1 , . . . , f N (F ,∥•∥∞,δ) } that consists of δ-cover of F. Then, under the CMI setting and under Assumptions 1 and 2, for any δ ∈ (0, 1/B] and for UWB, we haveEQUATIONSee 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 models. For example, we can obtain [37] , leading to the following upper bound:N (F, ∥ • ∥ ∞ , δ) ≍ L0 δ d when f w is a d-dimensional parametric function that is L 0 -Lipschitz continuous (L 0 > 0)EQUATIONwhere we set δ = O(1/B). This bound is minimized when B = O(n 1/3 ), resulting in a bias of O(log n/n 1/3 ), 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.As an application of our generalization error bound, we analyze recalibration using a post-hoc recalibration function, which is used when the trained model is not well calibrated. We focus on the 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 B for details of this splitting strategy). After training f w using the training dataset, we construct the recalibrated function h using the recalibration dataset S re asEQUATIONwhere ȳi,Sre is the empirical mean of {y m } nre m=1 ∈ S re in the i-th bin defined as in Eq. ( 2) and n re is the number of the recalibration dataset. In short, Eq. ( 21) provides an estimator of the conditional expectation of Y given f w (x) by setting S e = S re . Gupta & Ramdas [12] clarified that the statistical bias of Eq. ( 21) is given by E Sre TCE(hI,Sre ) = E[|E[Y |h I,Sre (X)] -h I,Sre (X)]| = O p ( B log B/|S re |).Since we need to split the overall data into three datasets, this approach could be sample-inefficient and could result in a very loose bound. Although reusing the training dataset may solve this problem to some extent, it has been suggested that this method may cause performance degradation due to overfitting [24, 12] .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 7 (Recalibration reusing the training dataset). Replacing S re with S tr in Eq. (21) , under the CMI setting and under Assumptions 1 and 2, we haveE R,Str TCE(h I,Str ) = E R,Str E[|E[Y |h I,Str (X)] -h I,Str (X)] ≤ 2 2(fCMI + B log 2) n ,where fCMI is defined in Eq. ( 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 tr . This indicates that reusing S tr does not negatively affect the order of the bias if fCMI is smaller than other terms, as discussed in Sections 4.1 and 4.2.Since the size of S tr is much larger than that of S re , the recalibration function h I,Str may exhibit a much smaller bias compared to h I,Sre . 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 is 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 generalization performance in terms of prediction accuracy, to 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 in 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 an extension of this approach to the ECE and recalibration. Bound & Gap (less calibrate) 12) as n increases when UWB is used. The following two terms: less calibrate and better calibrate refer to β = (0.5, -1.5) and β = (0.2, -1.9), respectively, where the former setting produces a worse value of the TCE estimator. UWB; B = ⌊(2n(1 + L) 2 /(log 2)) 1/3 ⌋ n^{-1/3} TCE gap; B = ⌊(2n(1 + L) 2 /(log 2)) 
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).In this section, we empirically validate our theoretical findings in Eq. ( 12), the nonvacuous nature of our bounds in Eq. ( 14), and confirm the efficiency of the optimal number of bins as discussed in Section 4.1.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) = 1 2 , and we adoptf w (x) = P (Y = 1|X = x) = 1/(1 + exp(-β 0 -β 1 x)) as the prediction model, where w = {β 0 , β 1 } are parameters. Under these settings, we can calculate the closed-form of E[Y |f w (X)] 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 Ste Bias tot (f w , S te ), 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) isB = ⌊2n(1 + L) 2 /(log 2) 1/3 ⌋, where L is estimated to be the maximum value of the gradient of the closed-form of E[Y |f w (X)].We provide the details of the experimental settings in Appendix G.1.Figure 1 shows the results. The two leftmost figures show that the TCE gap is O(n -1/3 ) 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 B are set as {n -1/2 , n -1/3 , n -1/4 , 2n -1/2 , 2n -1/3 , 2n -1/4 , 3n -1/2 , 3n -1/3 , 3n -1/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 are 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 = ⌊n 1/3 ⌋.The bound values for the existing recalibration method originate from Corollary 4 in Appendix E.5. Here, we report the ECE gap as 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 the ECE gap, which is the estimator ofTCE because E R,Sre E[|E[Y |h I,Sre (X)]-h I,Sre (X)] = E R,Sre,Ste ECE(h I,Sre , S te ) (existing recalibration meth- ods) E R,Str E[|E[Y |h I,Str (X)] -h I,Str (X)] = E R,E R,Str,Ste [|ECE(f W , S te ) -ECE(f W , S tr )|].We show the results obtained when using UMB in Figure 2 . These results show that our bound value becomes less than 1 with an appropriate setting of B. We also observed that the bound values decrease with n, whereas these values sometimes become vacuous for small n when B is large. Adjusting B could pose challenges; however, a notable trend towards acquiring relatively stable nonvacuous bounds can be observed when adopting B = ⌊n 1/3 ⌋, even though this is the optimal choice only at the upper bound of TCE, as discussed in Theorems 5 and 6 in Sections 4.1 and 4.2. Similar results are obtained when using UWB (see Figure 3 in Appendix H).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 independently created recalibration datasets (n re = 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, our bound values are lower than those for the existing 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. 
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 is 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.[49] Zadrozny, B. and Elkan, C. Transforming classifier scores into accurate multiclass probability estimates. In 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 methods for uncertainty calibration in deep learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 11117-11128, 2020. 
 
 Appendix: Let f, g : R → R. We say f (x) ≍ g(x) when there exist positive constants a, b and n 0 such that ∀n > n 0 , we have ag(n) ≤ f (x) ≤ bg(x) holds. Moreover f (n) ≲ g(n) means that there exists a positive constant c and n 0 such that ∀n > n 0 , we have |f(n)| ≤ cg(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 boundsHere we remark how the data is prepared and used in our analysis.In the standard supervised learning settings assume that N all data is obtained i.i.d from data generating distribution D. We express this as S all = {(x i , y i )} N all i=1 . Then the dataset is divided to S all = S tr ∪ S te , S tr ∩ S te = ϕ, where S tr is the training data which is n data points and S te is the test data points which is n te data points. Thus N all = n + n te .Here we discuss the evaluation of ECE(f w , S te ), which uses S te 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 S te when preparing bins, those S te are i.i.d. inside each bin.As for UMB, the situation is a bit complicated. Since we use S te to construct bins, it seems that S te 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 S te for constructing bins and evaluation of the binning ECE does not result in a large bias.In these ways, we can calculate ECE(f w , S te ). We also remark that the training samples S tr are only used to learn the parameter W .ere we discuss the evaluation of ECE(f w , S tr ), which uses S tr to calculate the ECE in Section 3. Thus, we use the training dataset S tr for learning W and calculating ECE.We need to carefully consider how the data is used when considering the result of the UMB in Theorem 4. This theorem provides us the generalization guarantee of the ECE between ECE(f w , S tr ) and ECE(f w , S te ). As for ECE(f w , S tr ) using UMB, we first train f W with S tr and construct bins with S tr and calculate the empirical mean of each bin with S tr . On the other hand, when calculating ECE(f w , S te ), we calculate the empirical mean of each bin with S te and we use the same bins with ECE(f w , S tr ), so bins are constructed using S tr in Theorem 4. In this sense, Theorem 4 provides 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.When the recalibration is performed, we further split the test data into S all = S tr ∪ S re ∪ S te , any common part sets are empty, where S tr is the training datasets used for learning W , and S re is the dataset used for the recalibration. The most widely used approach is the UMB-based recalibration. First, we construct bins following the UMB approach using S re . Then let us express S re = {(x i , y i )} nre i=1 . The recalibrated functionEQUATION)Then S te is used for evaluating the ECE or test accuracy.However, since preparing both S te and S re is sample inefficient, our idea is reusing training sample S tr with size n even for the recalibration. In our setting, we split the data S all = S tr ∪ S te , S ∩ S te = ϕ, and we construct bins following UMB approach using S tr and calculate recalibration function by using S trEQUATION)We then finally evaluate the ECE using S te . So our approach is more sample-efficient.Here we introduce auxiliary lemma and facts, which we will use repeatedly in our proofs. In this section, we express f w as f to simplify the notation.First, from the definition of ECE in Eq. ( 2), we can immediately reformulate it asEQUATIONwhere Ŝe is the empirical distribution of S e .Next we introduce the binned function of f as f I , which is the conditional expectation given bins:EQUATIONEQUATIONThe following relation holds:Lemma 1. We define the test-binned risk asEQUATIONthen we haveEQUATIONwhere TCE(f I ) means the TCE of the function f I .Proof. By definition, we haveEQUATIONwhere we used the definition of the conditional expectation. On the other hand, We haveEQUATIONwhere we used the tower property. This concludes the proof.Thus, we can transform the loss and ECEs by Eqs. ( 24) and ( 27)C.We start from UWB. Conditioned on W , using the relation between the loss and ECEs by Eqs. ( 24) and ( 27), we haveEQUATIONwhere we used the triangle inequality ||a| -|b|| ≤ |a -b| for the first inequality and setl i (z) = (y -f W (x)) • 1 f W (x)∈Ii .We use the following relation: for the one-dimensional real random variable X, by Jensen inequality, we haveEQUATIONThen combining with the above, we haveEQUATIONBy setting g(i, S te) := E Z ′′ l i (Z ′′ ) -1 nte nte m=1 l i (Z ′ m ), we have E Ste e t B i=1 |g(i,Ste)| = E Ste B i=1 e t|g(i,Ste)| ≤ E Ste B i=1e tg(i,Ste) + e -tg(i,Ste)EQUATIONEQUATIONwhere v1,...,v B =0,1 is all the combinations that will be generated by expanding B i=1 in Eq. ( 42) and it has 2 B combinations.We would like to upper boundE Ste e t B i=1 (-1) v i [E Z ′′ li(Z ′′ )-1 n te n te m=1 li(Z ′m )] using Lemma 3. For that purpose, here we evaluate c i s of Lemma 3. By focusing on the exponent, we can estimate c i s byEQUATIONEQUATIONwhere the last inequality is derived as follows; Here by definition of the binning, each data point is allocated to a single bin. This means that for the inputx ′ m ′ , one of {1 f W (x ′ m ′ )∈Ii } B i=1 is not zero.We refer to such index as b. Then 1 f W (x ′ m ′ )∈I b ̸ = 0 at′ m ′ -f w (x ′ m ′ )| ≤ 1, we obtain Eq. (45) . Note that by Assumption 1, {f w (x m )} nte m=1 in x m ∈ S te takes the distinct values almost surely and in the above discussion, we do not consider the case when b/B = f w (x m ) 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 = f w (x m ) for some b holds, which means that the predicted probability is just the value of the boundary of bins. Then, at most only four indicator functions are not zero. This results in a worse boundEQUATION)Combined with Lemma 3, we have thatEQUATIONCombining this with Eq. ( 41), we haveEQUATIONThe proof goes similarly as in the case of UWB up to Eq.( 41). Then we need special care to bound the exponential moment since in the UMB, bins are constructed using S te , and thus the samples are no longer i.i.d. Recall the definitions that f (m) is the m-th order statistics of (f 1 , . . . , f nte ) and the boundaries of bins are defined by such order statistics u b := f (⌊nteb/B⌋) .We define the set S (B) , which is the set of test data points used for defining the boundaries of bins.We then define Ste as S te -S (B) , and thus Ste is the set of test data points, which is not used for the boundaries. We expressf w (S (B) ) = {f w (x)|x ∈ S (B) }.We define k b := ⌊n te b/B⌋, which is used for defining the b-th bin. Let fix b ∈ [B] and denote u = k b and l = k b-1 . Then Gupta & Ramdas [12] showed that f (l+1) , . . . , f (u-1) are independent and identically distributed given boundary points {f (⌊nteb/B⌋) } B-1 b=0 in Lemma 1 [12] . Moreover, Lemma 2 in Gupta & Ramdas [12] showed that let p be the density induced by the distribution P (f w (X)), thenEQUATIONwhere each fi is independent random variables fi ∼ P (f w (X)). This implies that given the boundary points defining bins, the data points inside the boundary are i.i.d.In order to use this result, we need to eliminate f (u) from the empirical mean of UMB. This is evaluated as follows; using this from the result of UWB, we haveEQUATION)This partition eliminates the boundary point from the empirical estimation. We can upper bound the second term asEQUATIONwhich follows directly by definition (see also Corollary 1 in Gupta & Ramdas [12] .). Then we haveEQUATION)Given the boundary point, the above exponential moment satisfies the condition of Lemma 3, since the l i (Z ′ m ) are i.i.d, given in each bin by Lemma 2 in Gupta & Ramdas [12] . This can also be confirmed that for random variables (f (1) , . . . , f (i) , . . . , f (nte) ), given f (i) , (f (1) , . . . , f (i-1) ) and f (i+1) , . . . , f (nte) ) are conditionally independent (this is proved in Gupta & Ramdas [12] , especially the proof of Lemma 2). Combined with Eq. ( 49), given the boundary points, Ste are i.i.d and the size of which is n te -B. Then we only need to upper boundEQUATIONWe can upper bound this in a similar way as in the case of UWB, replacing n te with n te -B under Assumption 1. Thus, we haveEQUATIONThis concludes the proof.We remark that for UWB, we can also upper bound in the following way;EQUATIONwhere we used the triangle inequality ||a| -|b|| ≤ |a -b| for the first inequality and setl i (z) = (y -f W (x)) • 1 f W (x)∈Ii . Note that since -1 ≤ l i (z) ≤ 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.In 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 haveEQUATION)This means the statistical bias is O p ( B/n te ).Proof. Using the proof of Theorem 2, and Chernoff-bounding technique, for any t > 0, we haveEQUATION)By setting t = nε thenEQUATIONand setting δ := 2 B e -nε 2 2n te , we have thatEQUATIONProof. We use the following lemma to study the binning bias.Lemma 4.EQUATION)This implies thatEQUATIONProof. The first inequality has been proved in Proposition 3.3 in Kumar et al. [24] .The second inequality is proved as follows;EQUATIONIn the above, the second term corresponds to TCE(f I ).As for UWB, from Lemma 4, we haveEQUATION)where we used the fact that with UWB, we split the function with equal width 1/B and used the Lipschitz continuity of the function.Next, we focus on UMB. To analyze the binning bias of this, we focus on Eq. (50). We replace the loss l m (z) in that equation withEQUATIONThen, the first line and second line of Eq. ( 50) can be rewritten asEQUATIONwhere P (I i ) is the empirical estimate of the binning probability P (I m ). 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 haveEQUATION)By definition, we put equal mass in any bin, thus,P (I i ) = u -l + 1 n te ≤ 1 B .from the proof of Theorem 3 in Gupta & Ramdas [12] .Thus, by the Jensen inequality, we have for any m ∈ [B],EQUATIONCombining these results, the binning bias is upper bounded byE|f w (X) -f I (X)| = B i=1 P (f w (X) ∈ I i )E[|E[f w (X)|f w (X) ∈ I i ] -f w (X)||f w (X) ∈ I i ] ≤ 1 B + 2B log 2 (n te -B) + 2B n te -B B i=1 E[|E[f W (X)|f W (X) ∈ I i ] -f W (X)||f W (X) ∈ I i ] (68) We use the fact that E[|f w (X)-E[f w (X)|I i ]||I i ] ≤ f (⌊ni/B⌋) -f (⌊n(i-1)/B⌋)holds by the definition of the UMB, which is the largest difference of the bins. ThenB i=1 E[|E[f W (X)|f W (X) ∈ I i ] -f W (X)||f W (X) ∈ I i ] ≤ B i=1 f (⌊ni/B⌋) -f (⌊n(i-1)/B⌋) ≤ 1. (69)Combining the above, Then we haveEQUATIONAs for theE||E[Y |f w (X)] -E[Y |f I (X)]|, by the assumption of the Lipschitz continuity, we simply multiply L to the above and obtainEQUATIONThis concludes the proof.In the nonparametric estimation, imposing the higher order smoothness improves the bias order.According to Tsybakov [36] , the lower bound is O(n-β β+1 te) if we assume β-Hölder continuity.In our total bias analysis, the statistical bias is not improved by this assumption. As for the binning bias, if we assume that E[Y |f w (X)] satisfies β-Hölder continuity with constant M for all the order, then we obtain that for UWB,EQUATIONCombined with the statistical bias we have thatEQUATIONand the optimal bin size is again O(n 1/3 te ) and resulting bias is Bias tot (f w , S te ) = O(n-1/3 te), which does not improve the bias. This is because of the error term of E|f w (X) -f I (X)|. This term cannot be improved by 1/B, thus we cannot leverage the underlying smoothness of the data. A similar discussion holds for the UMB setting.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 i.i.d., (ii) using Hoeffding inequality, deriveving |E[Y |f I (x)] -f I (x)| = O p ( B/n te ) for each bin, and (iii) finally, summing up these error bounds for all bins, resulting in O p ( B log B/n te ) (in expectation O(B/ √ n te ). 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] , it becomes inevitable to address the allocation of samples to each bin when attempting to discuss the convergence of sample means for each bin. In UMB, an equal number of samples, n te /B, are allocated to each bin to achieve equal mass across all bins.In UWB, however, there is no 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 to intervals under strong assumptions regarding E[Y |f w (x)], requiring stronger assumptions compared to both this study and existing research.To simplify the notation, we also introduce the loss asEQUATIONwhere Z = (X, Y ). Then we obtainEQUATIONwhere W in the second line should be W = A( ZU , R), but to make the presentation simpler, we used W . We also used the triangle inequality ||a| -|b|| < |a -b|.With this notation, by using the Donsker-Varadhan lemma, we haveEQUATIONwhere we introducedEQUATION)Our first observation is that conditioned on Z = z, R = r, and U = u, the expectation of the exponent isEQUATIONby definition. Then similarly to Appendix D.1, we upper bound the exponential moment as follows;E U ′ e t B i=1 |g(z,u,r,U ′ ,i)| = E U ′ B i=1 e t|g(z,u,r,U ′ ,i)| ≤ E U ′ B i=1e tg(z,u,r,U ′ ,i) + e -tg(z,u,r,U ′ ,i)EQUATIONwhere v1,...,v B =0,1 is all the combinations that will be generated by expanding B i=1 in Eq. ( 91) and it has 2 B combinations.U ′ m e t n n i=1 (-1) v i l(w,z m, Ū ′ m ,i)-l(w,z m,U ′ m,i) using Lemma 3 conditioned on all other random variables. For that purpose, here we evaluate c i of Lemma 3. To estimate it let us focus on U ′ m and it takes value U ′ m = {0, 1}. So let us consider how the exponent changes by changing U ′ m = 1 to U ′ m = 0. Then the difference of the exponent is written asEQUATIONTo 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 x n,0 , exactly one of the indicators {1 fw(xn,0)∈Ii } B i=1 is non-zero, denoted as b. Consequently, all other indicators are zero, i.e., 93) is upper bounded by 4t n . Note that by Assumption 1, {f w (x m,Um )} n m=1 takes the distinct values almost surely and in the above discussion, we do not consider the case when b/B = f w (x m,Um ) 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) asEQUATIONThen by Lemma 3, we have thatEQUATION)ThusEQUATIONand combining with Eq. (88), we haveEQUATION)This concludes the proof of UWB.We next prove the case of UMB. The key difference lies in the fact that the bins are dependent on the training samples.∆(U, Z, A( ZU , R)) := |ECE(f W , Z Ū ) -ECE(f W , ZU )| = B i=1 1 n n m=1 (ỹ m, Ūm -f A( ZU ,R) (x m, Ūm )) • 1 fw(x m, Ūm )∈Ii( ZU ) - B i=1 1 n n m=1 (y m, Ūm -f A( ZU ,R) (x m, Ūm )) • 1 fw(x m, Ūm )∈Ii( ZU ) ,where we expressed the dependency of bins on the training samples as I i ( ZU ). However, this dependency does not change the proof in the above; we use the Donsker-Varadhan lemma. We upper bound of the exponential moment. When upper bounding the exponential moment, we 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 as UWB.Finally, we can bound the statistical bias using the Jensen inequality as follows: First following the proof of Theorem 2, using Eqs. ( 24) and ( 27), we haveEQUATIONwhere the first inequality is the triangle inequality and the second inequality is the Jensen inequality. Note that the above reformulation is possible for both UWB and UMB. Although in the case of UMB, bins of the TCE still depend on S tr , 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-Varadhan inequalityEQUATIONwhich results in a looser bound than the above proof, which can be confirmed by the data processing inequality.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 1 and 2, we haveEQUATION)where fCMI is defined in Eq. (17) .Proof of Theorem 8. The proof is similar in Appendix D.4. The difference is that in the current setting, we 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 thatEQUATIONwhere we used Hölder inequality in the second line and E| • | ∞ is the maximum of the integrand.We want to estimate P (I i ) := P (f (X) ∈ I i ). For this purpose, we use Eqs. ( 87) and (86). We re-define the loss of Eq. ( 86)EQUATIONand substitute it into Eq. ( 87), then we have thatEQUATIONwhere P (I i ) is the empirical estimate of the binning probability using supersample Xm,Um and P (I i ) is that of obtained by Xm, Ūm . Then, to obtain the upper bound of the right-hand side of the above, we repeat the proof of Theorem 4 in Appendix E.1. Let us defineEQUATIONWith this notation, by using the Donsker-Varadhan we haveEQUATIONwhere we introducedEQUATION)Here we use the fCMI := I(f A( ZU ,R) ( X); U | Z) and I(∆(U, Z, A( ZU , R)); U | Z) ≤ fCMI by the data processing inequality since the indicator functions depend on f w .Then, we can estimate this using Lemma 3 in a 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 a loss, the coefficient c i s for Lemma 3 is upper-bounded by 2t/n, not 4t/n. Then we repeat the proof strategy replacing the exponential moment evaluation by 2t/n, not 4t/n.With this difference,EQUATIONand Eq. ( 97) can be rewritten in the following wayEQUATIONand clearly, by fixing some i, we have thatEQUATION)Since we put an equal mass for each bin for the training dataset with UMB, we haveP (I i ) = u -l + 1 n ≤ 1 B .Combined with Jensen inequality, we haveEQUATION)Then we haveEQUATIONFinally, we use the fact thatE[|f (X) -E[f (X)|I i ]||I i ] ≤ f (⌊ni/B⌋) -f (⌊n(i-1)/B⌋)holds by the definition of the UMB, which is the largest difference of the bins. ThenEQUATION)where E| • | ∞ is the maximum of the integrand.Combining the above, Then we haveEQUATIONThis concludes the proof.Using this we provide the proof of the total bias as follows;Proof of Theorem 5. We use the triangle inequality,E R,Str |TCE(f W ) -ECE(f W , S tr )| = E R,Str |TCE(f W ) -TCE(f I ) + TCE(f I ) -ECE(f W , S tr )| ≤ E R,Str |TCE(f W ) -TCE(f I )| + E R,Str |TCE(f I ) -ECE(f W , S tr )|.(114) The first term is the binning bias and the second term is the statistical bias.We start from the UMB; we can bound the binning bias in the first term by Theorem 8 and the statistical bias in the second term by Theorem 4 of the UMB.As for the UWB, the binning bias is simply (1 + L)/B, which can be derived similarly as in Appendix D.4. As for the second term, we 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 1 and 2, we haveEQUATION∆(U, Z, A( ZU , R)) := B i=1 1 n n m=1 (1 f A( ZU ,R) ( Xm, Ūm )∈Ii -1 f A( ZU ,R) ( Xm,Um )∈Ii ) . (116)In the proof of Theorem 8, we used the fact that I(∆(U, Z, A( ZU R)); U | Z) ≤ fCMI by the data processing inequality. Thus, fCMI appearing in Theorem 5 can be replaced with I(∆(U, Z, A( ZU , R)); U | Z), which results in a tighter bound.Proof. Recall the setting, where we assume that f w ∈ F has the metric entropy, log N (F, ∥•∥ ∞ , δ), with parameter δ (> 0). That is, there exists a set of functions F δ := {f 1 , . . . , f N (F ,∥•∥∞,δ) } that consists δ-cover of F. We will consider to replace f w with the functions from the δ-cover.Using the δ-cover, we want to construct a set of functions F that satisfies the following property; there exists a function f ∈ F such that for any input x and that x is allocated to i-th bin, that is,f w (x) ∈ I i , then f satisfies f (x) ∈ I i and ∥f -f w ∥ ∞ < δ.The original δ cover F may not satisfy this property as follows; If we simply consider that h = arg minf ∈F δ ∥f w -f ∥ ∞ ,then there is a possibility that h(x) / ∈ I i for x ∈ X such that f w (x) ∈ I. This will cause a problem when approximating the ECE using h. If h(x) / ∈ I i , it significantly changes the estimation of the conditional expectation in each bin, leading to a larger change of the ECE. To avoid this, we consider a set of functions such that for each i = 1, . . . , B, for any f ∈ F δ , we defineEQUATIONwhere 0 < ϵ < 1/2δ. We refer to this set of clipped functions as F i for i = 1, . . . , B. The parameter ϵ is introduced so that the clipped value does not take the boundary value between the i-th bin and (i -1)-th bin. Since we set 0 < ϵ < 1/2δ, the parameter ϵ does not affect the bias analysis below. Then, we define the functionEQUATIONwheref i := arg min f ∈Fi sup x∈Xi |f w (x) -f (x)| and X i := {x ∈ X |f w (x) ∈ I i }. (if X i = ϕ, wedo not need to consider f i and any function in F i can be used.) Note that under this definition,sup x∈Xi |f w (x) -f i (x)| < δ holds for each i = 1, . . . , B.This can be confirmed as follows;given any f w , we assume that there exists a point x * ∈ X (the following discussion still holds when there are multiple such x * and we refer to them as X * ) that achievessup x |f w -h| ∞ . If f w (x * ) ∈ I i , by the definition of F i , |f i (x * ) -f w (x * )| ≤ max min h(x * ), i B , i-1 B + ϵ -f w (x * )| ≤ |h(x * ) -f w (x * )| ≤ δ. For x, which does not achieves sup x |f w (x) -h(x)∥ ∞ (that is, x / ∈ X * ) and satisfies f w (x) ∈ I i , then we have |f i (x) -f w (x)| ≤ max min h(x), i B , i-1 B + ϵ -f w (x)| ≤ |h(x) -f w (x)| ≤ δ. So for any x ∈ X i , |f w (x) -f i (x)| < δ holds. Thus the function f defined in Eq. (117) satisfies that for any x, if f w (x) ∈ I i , then f satisfies f (x) ∈ I i and ∥f -f w ∥ ∞ < δ.With these settings, we consider replacing the functions in the total bias defined by above. Here in after, we set δ < 1/B. Then the error in the TCE by replacing f w with f is given asEQUATIONwhich is obtained by the Lipschitz assumption.Next, we consider the error in the ECE by replacing f w with f is given as follows;EQUATION)where |I i | := n m=1 1 fw(xm)∈Ii and we used the fact that i |I i | = n and 1 fw(X)∈Ii = 1 f (X)∈Ii for any x by definition.Then the total bias is upper bounded by using f as follows;EQUATIONSince the second term in the above represents the total bias of f , using Theorem 5EQUATIONwhere we replace f w appearing in the bound appearing Theorem 5 with f defined above.From the data processing inequality, we can upper bound the eCMI( l) by the fCMI of f . Then such fCMI is bounded by the entropy of f as followsEQUATIONwhere we used the definition of mutual information and the conditional entropy of f given U (H[f ( X)|U, Z]) is larger than 0 because f ( X) is the discrete random variable and the entropy of the discrete random variable is always larger than 0. 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 H[f ( X)| Z] by the log of the number of distinct values that are represented by Eq. ( 118) given 2n inputs of supersamples Z. We refer to it as N . Defined 2n (f, g) := max i∈[2n] |f (x i ) -g(x i )| for f, g ∈ F.The δ-covering number of F with respect to d 2n is denoted as N (F, d 2n , δ), and we define N (F, δ, 2n) := sup [37] . We focus on the fact that f defined in Eq. ( 118) is the element of F 1 + F 2 + . . . , +F B , wherex n ∈X n N (F, d 2n , δ). It is known that N (F, δ, 2n) ≤ N (F, ∥ • ∥ ∞ , δ) in generalF 1 + F 2 implies the set of functions that is {f + g|f ∈ F 1 , g ∈ F 2 }.Note that the covering number of sum of two functions are upper bounded by the multiplication of each covering number, that isEQUATIONand thus, we haveEQUATIONThus we haveEQUATIONIn conclusion, we have thatEQUATIONCombining these we haveEQUATIONFinally, as for the order discussion, for example, we can obtain [37] , leading to the following upper bound:N (F, ∥ • ∥ ∞ , δ) ≍ L0 δ d when f w is a d-dimensional parametric function that is L 0 -Lipschitz continuous (L 0 > 0)EQUATIONwhere we set δ = O(1/B). This bound is minimized when B = O(n 1/3 ), resulting in a bias of O(log n/n 1/3 ).Here we provide additional discussion about the metric entropy. The bound based on 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-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 dimensionindependent 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 et al. [1] in if our model class f w (•) satisfies δ/4-fat dimension with d δ/4 for δ ∈ [0, 1], we haveEQUATIONwhich results in the dimension-independent upper bound. To evaluate the fat-shattering dimension for specific models, see Bartlett & Maass [2] for the details.Proof. Recall the definition of the recalibration. Here we show the expression when we use the training dataset S tr :EQUATIONEQUATION)The proof is similar to the proof of Theorem 8. We use Eqs. ( 87) and (86), let S tr = {Z m } n m=1 , then we haveEQUATIONwhere we used the Jensen inequality first and the used the triangle inequality and used the fact that |μ i,Str | ≤ 1 by the definition of UMB in the next inequality.We then rewrote the above in the CMI setting, we haveEQUATIONwhereEQUATIONwhere the last line is we repeat the proof of Theorem 8. The proof of Theorem 8 has discussed the loss composed of the indicator function, we can use exactly the same proof procedure. The only difference is the CMI; here we consider the eCMI which uses above ∆ 1 and ∆ 2 as the random variables, and their CMIs are the conditional mutual information between ∆ 1 and ∆ 2 .From Eq. (134), we can further simplify the upper bound using the data processing inequality,EQUATIONl(A( ZU , R), z, B) := (1 f A( ZU ,R) (x)∈I1 , . . . , 1 f A( ZU ,R) (x)∈I B ).(139)We then haveEQUATIONIn the numerical experiments, we use the tighter version, which appears in the proof above; Corollary 4. Under the same setting and assumptions as Theorem 7, we haveEQUATIONwhereEQUATIONEQUATIONIn the main paper, we further upper bound eCMIs by fCMI, which is followed by the data processing inequality.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 haveEQUATIONProof. The recalibration bias corresponds to the statistical bias because from Theorem 2, we haveEQUATION)where h I is the conditional expectation of h I,Sre given bins I. Note that by the definition of h I,Sre , from the tower property h I (x) = h I,Sre (x) holds since we take the expectation in each bin. Thus, by definition E Sre TCE(h EQUATIONWe 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. In this section, we explain the difference between our study and the existing work in the calibration context.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 f w (x), so Assumption 1 cannot be eliminated. ii) : The other purpose is that by Assumption 1, we want to use the fact that {f w (x m )} nte m=1 in x m ∈ S te takes the distinct values almost surely (same for {f w (x m )} n m=1 in x m ∈ 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 to 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 IT-based approach and does not use the results in Gupta & Ramdas [12] , so we do not need Assumption 1 regarding i). However, if all {f w (x m )} n m=1 in x m ∈ S takes the same value, we cannot construct the bins in UMB. So when considering the training data reuse, we need Assumption 1 to construct the bins of UMB. However, we remark that we can replace Assumption 1 with the assumption that "we assume that {f w (x m )} n m=1 in x m ∈ 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 a chance that all the {f w (x m )} nte m=1 in x m ∈ S te takes b/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 {f w (x m )} n m=1 in x m ∈ S tr takes different values. So if all the f takes the same value, the 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.For these reasons, we decided to impose Assumption 1 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 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 [26] . Such smoothness assumptions are standard in nonparametric regression, 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 (β → 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 x, Assumption 2 is satisfied [47] . 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., [49] ). Additionally, our numerical 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 scenarios.Finally, regarding the assumption n e ≥ 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.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 f (x) and the property of the indicator function. However, our proof builds on the reformulation of Eqs. (24) and (27) this can be a restriction for some settings. For example, when we consider higher-order ECEs defined asEQUATIONwith 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 ∆L bound (loss difference) of Theorem 1 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 ∆L (loss difference) as shown in Theorem 1 of reference Wang et al. [39] .However, extending our bounds using the techniques of Wang et al. [39] presents significant challenges. The ∆L bound in Wang et al. [39] defines the loss gap for a single data index i as ∆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 Wang et al. [39] that utilize the symmetry of a single index are not applicable to our context, making it difficult to employ the methods from Wang et al. [39] .Here we discuss the order of our generalization error bias in more depth. Recall that our Theorem 4 isEQUATIONand the important property is that the bound is of order O( B/n) if we neglect the order of eCMI.Here we see that when we use existing Theorem 1 directly, the resulting bound is O(B/ √ n). Recall thatECE(f, S tr ) = B i=1 |E (X,Y )∼ Ŝtr (Y -f w (X)) • 1 fw(X)∈Ii |, TCE(f I ) = B i=1 |E (X,Y )∼D (Y -f w (X)) • 1 fw(X)∈Ii |.where Ŝtr is the empirical distribution of the training dataset. ThusEQUATIONCarrell et al. [4] numerically evaluated the generalization 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 rigorously 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.6F.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 in a pointwise. To understand this, we start deriving the following lower bound by using Jensen inequality:EQUATIONThis bound suggests that estimating E[Y ] = f w (x) achieves the small TCE. From the classical theory, for any distribution D, the lower bound of a parameter estimation bias is 1/ √ n [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. In UMB, we estimate the conditional expectation using m = n/B samples in each bin and this is a parameter estimation problem. Thus this leads to O(1/ √ m) bias from the classical theory. On the other hand, we derived the statistical bias O( B/n) for UMB, thus it is optimal when viewed as the parameter estimation.However, using a constant function f w (x) = E[Y ], which achieves the small TCE, is useless in practice. Our original motivation is to measure the perfect calibration, which requires estimating the conditional expectation E[Y |f w (x) = p] for the interval p ∈ [0, 1] in a pointwise, and this is a 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 a trade-off whether the problem is the parameter or function estimation.From the classical theory of Fano's method [37] , when we estimate the Lipschitz function with a closed interval, it achieves a lower bound O(1/n d+2 ), with d as the input dimension of the function. In the calibration, the input is the probability p and thus d = 1. Since we derived that the bias of the ECE is O(1/n ), however as discussed in Appendix D.5, the binning method cannot achieve this rate and thus cannot utilize the smoothness of the data distribution.Here we discuss additional points regarding the TCE bias estimation. Conditioned on W = w, let v = f w (x) and the distribution induced by p(x) by f w (x) over v as p(v). We express the support of p(v) as V ⊂ [0, 1]. Let g(v) = E[Y = 1|f w (x) = v] = Pr[Y = 1|v].Let G be a class of candidate conditional probability functions over V and every candidate g ∈ G satisfies 0 ≤ g(v) ≤ 1 for all v ∈ V. Let us write the L2 minimax error asEQUATION)where ĝ is over all valid estimators for g using n samples (X m , Y m ) n m=1 and the expectation is taken with respect to true g. The L2 and higher order minimax rate has been shown in [45] by using the Yang-Barron method [46] , which is the mutual information-based approach stemming from Fano's method. To cite this result, we need additional assumptions that control the mutual information [45] ; Assumption 3. Assume that G has at least one member g * that is away from 0 and 1, i.e., there exist constants 0< c 1 ≤ c 2 < 1 such that c 1 ≤ g * ≤ c 2 .Here we assume that G is a set of functions that satisfies the β-Lipschitzness; for any g ∈ G, there exists positive constant C that satisfies |g(v) -g(v ′ )| ≤ C|v -v ′ | β for any v, v ′ ∈ V.According to Lemma 1 in [45] , if β-Lipschitzness and we haveEQUATIONThus, if we consider the histogram-based estimator for ĝ ĝbin (v) :EQUATIONwhich is used in the definition of the binning ECE, thenEQUATIONThus we can obtain the lower bound of the recalibrated function from true conditional expectation.Here we discuss how this lower bound is related to the total bias of the ECE. Let us define the semi-metricEQUATIONWe can easily confirm that ρ satisfies the positivity and triangle inequality, so this is the semi-metric. We can show the following relation for the total bias and this ρ as follows; recall that we can express the TCE asEQUATIONandEQUATIONwhereV (v) = B i=1 vi,Ste • 1 v∈Ii , vi,Ste := 1 |I i | nte m=1 1 vm∈Ii v mwhere v m = f w (x m ). Thus, the total bias is given as the total biasEQUATIONwhere g := ĝbin (V ) -V (V ) + V . Thus, by studying the risk under ρ, we can study the total bias.On the other hand, this ρ is smaller than the L1 distanceEQUATIONby the triangle inequality. Note that L1 distance is smaller than L2 distance, the above minimax result for ĝ and g in Eq. ( 154) is insufficient to understand the bias of TCE and ECE from the lower bound. Instead, we introduce different lower bound given as follows. Conditioned on W = w, under the β-Lipschitzness for E[Y |f w (x) = v] and Assumption 3, we haveEQUATIONAnd We can further obtainEQUATIONwhere E| • | ∞ is the maximum of the integrand. These lower bounds imply the pointwise lower bound of the difference of the conditional expectation and V . Using these lower bounds, we study the difficulty of estimating the TCE at each V = v = f w (x). Proof. First, we focus on the relationEQUATION)We then estimate the minimax L2 estimation error under the semimetric ρ(g, g ′ ) := E||g(V) -V | - |g ′ (V ) -V || 2 .The proof is the same as that of Lemma 1 in [45] , which uses Yang Barron method.The difference is to derive the packing number under the semimetric ρ not the L2 distance. However ρ is nothing but the shifted version of the L2 distance. Thus the order of the packing number is the same as that of L2 distance. Note that since G is the set of positive functions thus, taking the absolute of g(V ) -V does not change the order. Then by using Fano's method, we obtain the result for L2 lower bound. The version of ∥ • ∥ ∞ can be proved in the same way.We finally remark that the above pointwise gap is larger than the total biasEQUATIONEQUATIONwhere we used the relation of that L2 is larger than L1 and used the Jensen inequality.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 a K-class classification problem, we obtain predictions of each label by the final softmax layer in neural networks. We assume that f w (x) ∈ R K predicts the label by C := argmax k f w (X) k , where f w (X) k represents the model's confidence of the label k ∈ [K]. Then top ECE is defined using the highest prediction probability output by f w : 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 in a 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 as binary classification, leading to 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.In this section, we summarize the details of our experiments conduced in Sections 3 and 6.For the experiments on the synthetic dataset, we follow Zhang et al.[50] and assume that the distributions of the label Y and the input data X are as follows: EQUATIONHellström & Durisi [17] . This is because our loss function l(A( ZS , R), Z, B) assumes continuous values, while these 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 I(l(A( ZS , R), Z, B); S| Z) [19, 20, 32] , which is computed using estimators for the probability density of l(A( ZS , R)) and S tr , as well as their joint probability density, employing k-nearest-neighbor-based density estimation [27] . The estimation strategy is incorporated into the sklearn.feature selection.mutual info classif function (we refer to the following link: https://scikit-learn.org/stable/modules/generated/sklearn.feature_ selection.mutual_info_classif.html). We set k = 3 following the default setting of this function and Kraskov et al. [20] , Ross [32] .Standard deviation evaluation of our bounds: The standard deviation in Table 1 and Figures 2 3 4 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 5 × 10 models.In this section, we show the additional results obtained from our experiments.We show the results of our bound in Eq.( 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 B to obtain nonvacuous bound values. We also observed that our optimal choice, B = ⌊n 1/3 ⌋, is effective in obtaining nonvacuous bounds. 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. Interestingly, the choice of optimal B is crucial for obtaining a small bound value when we conduct recalibration. 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.We examined the ECE gap for various bin sizes using the same setup as Figure 2 , and these results are 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 a better generalization gap. However, the optimal bin size minimizes the total bias as stated in Theorem 5, not necessarily the generalization gap as in Theorem 4. On the other hand, the optimal 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 increases.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 a numerical evaluation using ResNet experiments. Specifically, we checked whether the value of E[Y |f (X)], estimated via binning, exhibits relatively smooth variations. These results are presented in Figure 6 .The findings indicate that the estimated values fluctuate smoothly to a significant degree, providing 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. https://github.com/hrayrhar/f-CMI 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	Tightness 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.

2.	A 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.

3.	In 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.
questions: questions: 1.	Clarification: 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?

2.	How should the error bars for the bound values in Table 1 be interpreted? What is the source of the randomness?

3.	It 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: limitations: The Limitations are well addressed in section 7.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The limitations are adequately addressed in the conclusion.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* 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?)
questions: 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.

Tighter Information-Theoretic Generalization Bounds from Supersamples. ICML 2023.

Rethinking Information-theoretic Generalization: Loss Entropy Induced PAC Bounds. ICLR 2024.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. As the authors themselves note, a significant limitation is that the analysis in this work is only applicable to binary classification.

2. Some assumptions (e.g., Assumption 2) are not well justified.

3. The writing has significant room for improvement; several arguments are unclear or misleading.

Please find more details in the questions below.
questions: 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?

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

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

4. 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?

5. 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?

6. 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?

7. 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: limitations: The authors have thoroughly discussed some limitations of this work.

Comments: title: Acknowledgement and clarification of the limitation of the binary classification
Thank you for the responses
Acknowledgement
Thank you for the comment.
Thank your for the reply
comment: We sincerely appreciate your thorough review of our responses to the reviewers’ comments.
And, we are delighted that you have decided to increase your score.

Concerning the limitations inherent in binary classification, we addressed similar points in our response to Reviewer 8W41 (Q.1). Please refer to that section for details. In summary, our analysis can extend to multiclass scenarios involving top-calibration error, such as when using softmax for classification. In these cases, evaluating the calibration of the highest softmax score is standard practice, and these metrics can be reduced to a formulation similar to binary classification, enabling our analysis. 

Concerning the minimax theorem, additional assumptions are necessary because the theorem deals with worst-case distributions. Worst-case scenarios may occasionally involve settings that are unrealistic or unlikely. However, for establishing upper bounds, as in Theorem 5, Assumption 2 is generally sufficient, making it more practical and likely to be met in real-world scenarios.
We hope these answers will further clarify your understanding.
I would like to thank the authors for their responses and apologize for not engaging in the discussion earlier. I have read all the reviews and the corresponding author responses.

My concern regarding Assumption 2 has been adequately addressed, and further clarifications have been provided for other questions. I will increase my score to 5 accordingly. However, I am not assigning a higher score because the analysis in this paper is limited to binary classification, with no clear path to extending it to a multi-classification setting. While I also appreciate the minimax results, I am concerned that the analysis (and potentially the assumptions) might require significant refinement in more general or practical settings.
We greatly appreciate your acknowledgment of our responses. We will incorporate the theoretical facts and insights, along with their proofs, discussed during the rebuttal period into the revised version. Additionally, we will improve the clarity of the existing experiments and include the additional experiments in the revised version as well.

We are delighted that you have decided to increase your score.
Thank you again for your insightful feedback.
I appreciate the authors' effort in preparing the response. It thoroughly addresses all my comments, and I am pleased to see the matched lower-bound results and additional empirical evidence supporting the claim. I will raise my score to 7—this is a solid paper.

Please ensure that the new results are incorporated into the final revision, and make sure the figures in the main body are clear and easy to follow.
Thank you for confirming our response. If there are any further issues or concerns that need to be addressed to improve the score, please let us know. We are happy to discuss them further.
Thank you for confirming our response. We believe that the additional experiments address your concerns. If there are any further issues or concerns that need to be addressed to improve the score, please let us know. We are happy to discuss them further.
Thank you for the response. I'll maintain my positive score.
Thank you for the response and additional experiments. I'll maintain my positive rating.