Information-theoretic Generalization Analysis for Expected Calibration Error

We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.

Q.1: Regarding the strictness of Assumption 2 and the assumption of $n_e\geq 2B$

A. First, please refer to the global response for the discussion on the necessity of Assumption 2. In practice, Assumption 2 is reasonably mild. For example, if label distributions follow a Bernoulli distribution with the mean depending on the input $x$, Assumption 2 is met [E]. This is a relatively weak assumption in binary classification. Moreover, existing studies have shown that many common benchmark datasets are consistent with this assumption (e.g., [F]). To ascertain whether the assumption of Lipschitz continuity is empirically plausible, we conducted a numerical evaluation based on ResNet experiments. This involved checking if the value of $E[Y|f(X)=v]$, estimated through binning, exhibits relatively smooth variations. These findings are depicted in Fig. 6 of the attached PDF. The results demonstrate that the estimated quantity $E[Y|f(X)=v]$ fluctuates smoothly to a considerable extent, thereby supporting the validity of the Lipschitz continuity assumption. This supports the robustness of our assumptions and the applicability of our methods in real-world scenarios. We will incorporate these results into our paper.

Regarding the assumption $n_e\geq 2B$, it is crucial for UMB, as it guarantees the proper construction of bins. In UMB, we first use $B$ samples to build the bins. We then partition the remaining $n_e−B$ samples evenly across these bins. If $n_e < 2B$, we have $n_e−B< B$, preventing equal distribution of samples, thereby rendering UMB inapplicable. Conversely, UWB does not require this assumption since it divides the $[0,1]$ interval into equal-width bins. We will clearly outline this distinction in the revised paper.

[E] Y. G. Yatracos. A Lower Bound on the Error in Nonparametric Regression Type Problems. Ann. Stat., 1988. [F] B. Zadrozny et al. Transforming Classier Scores into Accurate Multiclass Probability Estimates. KDD '02.

Q.2: How to obtain TCE and ECE reformulations.

A. The proofs of those reformulations are provided in Appendix C, specifically in Lemma 1. In the revised version, we will explicitly reference this lemma to avoid any confusion.

Q.3: Reason why UMB has an additional term compared to UWB in Theorem 5,

A. The additional term (fCMI) arises because UMB uses training data to construct bins. This means we must consider overfitting not only during learning for $f_w$ but also in the bin construction process. This leads to extra fCMI terms in UMB compared to UWB, which is a potential disadvantage. Practically, UMB is designed to prevent issues with bins having no samples when $n_e$ is small. When sufficient data is available, we can partition the entire dataset into training data for learning $f_w$ and another dataset for bin construction. This approach avoids the extra fCMI term and has been explored in previous work [22].

Q.4: The meaning of Line 244 and Lines 251-252

A. Intent of Line 244: Our goal is to show that, similar to how ERM bounds test loss by training loss plus a generalization gap, our Theorem 4 bounds test ECE by training ECE plus a generalization gap. Some studies [21, 26, 36] use regularization to minimize training ECE in their algorithms, so if a small eCMI or fCMI ensures a small generalization gap, the upper bound of test ECE will also be minimized, thus providing theoretical assurance akin to ERM’s generalization theory.

Lines 251-252: In ERM, the expected loss can be estimated with a validation dataset, with an error rate of $O(1/n_{te}^{1/2})$. However, ECE converges to TCE at a much slower rate of $O(1/n_{te}^{1/3})$. Increasing validation data does not significantly improve this rate. Since training dataset size is often much larger than the test data size, if the generalization error (eCMI or fCMI) is small, using training data to estimate ECE could result in a smaller bias of $O(1/n_{tr}^{1/3})$. Thus, using training data for estimating TCE could be a promising approach. We will clarify these points in the revised paper.

Q.5: The difficulty of deriving the metric entropy bound for for UMB

A. Deriving the metric entropy bound for UMB is challenging due to the difficulty of constructing the appropriate $\delta$-cover of functions. As highlighted in Eq. 117 and Eq. 120, we need to set $\delta$ smaller than the width of the bins. In the case of UWB, the bin width is $1/B$; however, in UMB, the bin width is not fixed and varies according to the data. This dependency adds complexity to preparing the appropriate $\delta$-cover.

Q.６: Clarification in Line 339-340

A. Based on the additional experiments, we will revise the explanation as follows:

• The optimal $B$ is determined based on the upper bound of the total bias (Thoerem 5) and does not necessarily minimize the generalization error bound (Theorem 4). However, setting $B$ in this way ensures that we avoid vacuous values, numerical instabilities and even increase of the ECE gap as we increase $n$.

For the details, please see Fig. 5 in the PDF and response to Reviewers 9r8F (Q.4) (and to Reviewer 8W41; Q.4 for TCE and the total bias evaluation on toy data experiments.).

Q.7: New insights into the relationship between calibration and generalization

A. As stated in the global response, the total bias of the TCE and ECE matches the rate achieved in nonparametric regression, conclusively showing that estimating TCE is as challenging as estimating conditional probabilities using nonparametric regression. Thus, compared to usual generalization problems such as classification error, evaluating TCE requires more samples, and achieving a fast learning rate of $O(1/n)$ under parametric learning settings seems to be not possible, highlighting a distinct difference.

We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.

Q.1: Regarding the setting of binary classification and the Lipschitz continuity.

A. Although our study focuses on binary classification, we can readily extend it to multi-class settings. In existing studies [22, 8], the top-label calibration error (top CE, TCE) has been proposed as a measure for multi-class calibration. For instance, in a $K$-class classification problem, we obtain predictions for each label by the final softmax layer in neural networks. We assume that $f_w(x)\in \mathbb{R}^K$ predicts the label by $C:=\mathrm{argmax}_k f_w(X)_k$, where $f_w(X)_k$ represents the model’s confidence of the label $k \in K$. The top CE (TCE) is then defined using the highest prediction probability output by $f_w: TCE:=\mathbb{E}|P(Y=C| f_w(X)_C)-f_w(X)_C|$. By considering binning only for the top score, we can compute the ECE (top-binning ECE) in a manner similar to binary classification. In this case, since we focus only on the top label, we can treat top-binning ECE in the same way as binary classification, which results in the same generalization and total bias bounds. Our results, therefore, offer flexibility to analyze the widely used top-label calibration error in multi-class settings. We will add this discussion to the paper.

Regarding Assumption 2, this does not imply the Lipschitz continuity of the function $f_w(\cdot)$ itself, but the Lipschitz continuity of the conditional expectation $\mathbb{E}[Y|f_w(x)=v]$, which is a kind of characteristic of the data itself. For a more comprehensive discussion on the Lipschitz continuity assumption, please refer to the global response provided above and the response to Reviewer kktU (Q1).

Q.2: Regarding the necessity of test dataset in the ECE evaluation.

A. If your question concerns the difference between IT-based bounds and generalization error upper bounds like PAC-Bayes, which can be evaluated using only training data, model distribution, and prior distribution, note that the IT-based upper bound can still be evaluated even if only training data is available in practice. As discussed in Line 257, $\mathrm{eCMI} \leq \mathrm{fCMI}\leq I(W;S_\mathrm{tr})$ [13,15] holds, and $I(W;S_\mathrm{tr})$ only depends on the training dataset. Thus, by replacing eCMI and fCMI in Theorem 4 and 5 with this mutual information, we get the bound that is independent of the test dataset. On the other hand, the inclusion of test data dependence in eCMI and fCMI through the index \tilde{U} provides the benefit of tighter bounds.

If our explanation does not align with your concern, please provide further questions during the discussion phase.

Q.3: Regarding the convergence behavior of our bounds and the vacuousness of the metric-entropy-based bound

A. Your points are accurate. The primary distinction between IT bounds and UC bounds lies in their objectives:

• IT Bounds: These are algorithm-specific and aim to provide detailed insights into how a particular algorithm performs in terms of generalization. They focus on analyzing these bounds to understand the performance of specific algorithms. By further assuming specific algorithm classes, such as stable algorithms or stochastic convex optimization, we can derive the theoretical behaviors of the mutual information.
• UC Bounds: These are derived to determine the necessary sample size for achieving generalization performance based on convergence rates, independent of the algorithm used. Typically, UC bounds employ metric entropy to derive results. In response to your suggestion, we provide UC bounds that use the fat-shattering dimension, which is independent of the model’s dimension as detailed in the global response above.

Q.4: Regarding the statistical bias evaluation, and the TCE evaluation experiment on the synthetic experimental settings.

A. Evaluating the upper bound for TCE proved challenging with benchmark datasets and experiments using CNN and ResNet. However, we were able to conduct TCE evaluation experiments using a synthesized dataset based on the settings in [Z]. The results are shown in Fig. 4 of our additional PDF.

We numerically evaluated both sides of Corollary 1. Since Corollary 1 does not involve eCMI, this approach allows for a more accurate assessment of the bound’s tightness and optimality. The first two rightmost figures display the total bias and upper bound of Corollary 1 under the optimal bin size, demonstrating that the bound effectively captures the behavior of the total bias. The last two figures show the TCE gap plotted against different bin sizes compared to the theoretically optimal number of bins. Despite some fluctuations due to a small sample size $n$, the actual behavior closely aligns with theoretical predictions, validating the optimal bin size.

[Z]: J. Zhang et al. Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning. ICML2020.

Q.5: Regarding the improvement of the convergence rate

A. As discussed in the reply to Reviewer Ckaf (Q.2), we cannot use the technique proposed in [37] directly. Moreover, we have derived a minimax lower bound for total bias, which is $\mathcal{o}(1/n^{1/3})$, implying that the problem of estimating TCE is as inherently challenging as estimating conditional probabilities in the context of nonparametric regression. Therefore, deriving a fast rate of $\mathcal{O}(1/n)$ under a parametric learning setting is not feasible for the ECE estimation problem. However, discussing whether the techniques adopted in the papers you suggested can be used to improve the constants of the bounds constitutes important future work. We would like to specify this in the conclusion section.

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.

We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.

Q.1: Regarding the novelty of proof techniques

A.

First, it is important to clarify that our techniques are fundamentally different from those used in previous studies, as referenced in [11, 10, 22]. In these studies, the error bound for the ECE is derived through the following three steps: (i) Initially, it is shown that the samples assigned to each bin are i.i.d.; (ii) the Hoeffding's inequality is then applied to derive that $|\mathbb{E}[Y|f_{\mathcal{I}}(x)] - f_{\mathcal{I}}(x)| = O(\sqrt{n_{te}/B})$ for each bin; and (iii) these error bounds are summed up across all bins to yield $O(B/\sqrt{n_{te}})$. This approach leads to a slow convergence, which can be attributed to the separate analysis conducted for each bin, requiring multiple applications of concentration inequalities.

In our approach, we leverage a reformulation of the ECE and TCE as outlined in lines 151 and 152. These equations frame both the ECE and TCE in terms of the relationship between the empirical expectation and its population expectation. This framework allows us to apply concentration inequalities to the errors in all bins combined, specifically to the ECE and TCE themselves. Unlike traditional methods, we employ McDiarmid's inequality—notably, leveraging the technique within its proof—to derive an upper bound without the need to decompose the error into individual bins. This strategy eliminates the necessity to compute the cumulative sum of statistical biases across bins, achieving a more efficient convergence rate of $O(\sqrt{B/n})$ in expectation.

While McDiarmid’s inequality is widely used, our application of it within the binning context is technically novel because it requires meticulous handling of data replacement, as detailed in Appendix D.1.1. This approach in treating the data and applying the inequality offers a marked improvement in the convergence order compared to existing studies.

We would also like to highlight the novelty of Theorem 6. Our work extends beyond the standard construction of a $\delta$-cover for Lipschitz functions. As outlined in Appendix E.3, our approach involves a careful design of the $\delta$-cover to ensure that both the output of the original function $f_w$ and that of the $\delta$-cover function are categorized into the same bin. This careful alignment is significant to control the discretization error associated with the binning ECE when employing $\delta$-cover functions. This strategy, which we introduce for the first time, is crucial for enhancing the accuracy and effectiveness of our theoretical framework, providing a novel contribution to the field.

Q.2: Relation to the result in [37]

A.

The eCMI appearing in Theorem 4 (Eq. (15)) closely aligns with the $\Delta L$ bound (loss difference) of Theorem 1 of reference [37]. Specifically, the eCMI term in Eq. (15) is not based on the value of ECE itself. Instead, it is derived from the difference between the test data ECE and the training data ECE. This approach aligns with the $\Delta L$ (loss difference) as shown in Theorem 1 of reference [37].

However, extending our bounds using the techniques of [37] presents significant challenges. The $\Delta L$ bound in [37] defines the loss gap for a single data index $i$ as $\Delta L_i$ and utilizes the symmetry of each individual index to derive fast rate bounds, as demonstrated in Theorem 4.3. In contrast, our bound requires treating all $n$ indices simultaneously. This necessity arises because ECE is a nonparametric estimator that uses all $n$ indices, unlike usual losses such as the 0-1 loss, where an estimator can be constructed using a single index. Consequently, the techniques from [37] that utilize the symmetry of a single index are not applicable to our context, making it difficult to employ the methods from [37].

Furthermore, as previously discussed, we have derived a minimax lower bound for total bias, amounting to $\mathcal{o}(1/n^{1/3})$ under Lipschitz conditions. This implies that the problem of estimating ECE is as fundamentally challenging as estimating conditional probabilities in the context of nonparametric regression. Therefore, deriving a fast rate of $\mathcal{O}(1/n)$ under a parametric learning setting, as seen in [37], is not feasible for the ECE estimation problem.

We will add these discussions in the revised version of our paper.

We would like to express our deepest appreciation for your insightful reviews and suggestions. We sincerely summarize our responses to you as follows.

Q.1: Derive a minimax lower bound for the total bias.

A. Please see our global response for a minimax lower bound.

Q.2: Regarding the drawback of IT bounds.

A. The objectives of IT-based generalization bounds and UC bounds differ significantly. The former aims to derive upper bounds that are algorithm-dependent to gain a detailed understanding of how a training algorithm behaves to achieve generalization performance. This also involves analyzing these bounds to quantitatively examine the specific algorithms. In contrast, UC bounds are primarily derived to determine the sample size needed to achieve sufficient generalization performance from a convergence rate perspective, regardless of the algorithms.

Next, we explain the explicit relationship between Theorems 5 (IT bound) and 6 (UC bound). In the proof of Theorem 6, we derive the upper bound of eCMI (fCMI) using the metric entropy of the specific $\delta$-cover (Eq. 124). Therefore, the metric entropy-based UC bound serves as a further upper bound to the IT bounds. In addition to this, as shown in the global response, we show the new connection between IT and UC bounds using the fat-shattering dimension, which is independent of the model’s dimension. These insights will be included in the revised manuscript.

Q.3: Regarding the ECE gap in Figure 1 and Table 1.

A. First, the ECE gap shown in Fig. 1 corresponds to the empirical estimate of the middle expression in Eq. (14). We added the formal definition in Fig. 5 of our additional pdf.

The ECE gap reported in Tab. 1 is evaluated through the empirical estimator of the statistical bias: $E_{R,S_{re}} E [|E[Y|h_{\mathcal{I},S_{{re}}}(X)] - h_{\mathcal{I},S_{{re}}}(X)|] = E_{R, S_{{re}},S_{te}}ECE(h_{\mathcal{I}, S_{\mathrm{re}}},S_{te})$ for existing recalibration methods due to the definition of recalibration. For our proposed method, which uses all training data as recalibration data, it is evaluated as $E_{R,S_{tr}} E [|E[Y|h_{\mathcal{I},S_{tr}}(X)] - h_{\mathcal{I},S_{tr}}(X)|] = E_{R,S_{tr},S_{te}}ECE(h_{\mathcal{I}, S_{tr}},S_{te})$.

Thanks to your suggestion, we realized that this explanation is too brief and would like to add a detailed explanation of how we numerically measured the ECE gap in Appendix G.

Also, we believe that visualizing the estimate of the left-hand term in our theoretical framework is crucial for verifying whether the right-hand side is effectively upper bounded numerically and for analyzing the relationship between these two behaviors (refer to our answer to Reviewer 8W41, Q.4).

Q.4: Regarding empirical justification of our optimal $B$.

A. Regarding the optimal $B$ and the ECE gap, we initially showed only the ECE gap with this optimal $B$ in Fig. 1 for clarity. Motivated by your review, we examined the ECE gap for various bin sizes using the same setup as Fig. 1, and these results are presented in Fig. 5 of the additional PDF. We plotted them on a log scale to illustrate how the ECE gap and upper bound behave with different bin sizes. We found that sometimes bins other than the optimal $B$ can yield a better generalization gap. However, the optimal bin size minimizes the total bias as stated in Theorem 5, not necessarily the generalization gap (Theorem 4). On the other hand, the optimal $B$ was found to be numerically stable, although, in certain models, high variance was observed for certain bin sizes, with the ECE gap occasionally not decreasing as $n$ increases. Finally, to our knowledge, no existing work has evaluated model performance based on ECE from a generalization perspective. Our contribution is the first bound that allows for this numerical evaluation.

To further assess the optimality of $B$, we need to evaluate the total bias. However, evaluating the upper bound for TCE with benchmark datasets and experiments using CNN and ResNet proved challenging. Therefore, we performed additional experiments using Toy data to more easily evaluate the tightness of the bound and the optimality of $B$. Specifically, we created Toy data following the settings in existing studies and numerically evaluated both sides of Corollary 1. Since Corollary 1 does not involve eCMI, this approach allows for a more accurate assessment of the bound's tightness and optimality. The results are shown in Fig. 4 of the PDF. The first two figures from the right display the total bias and upper bound of Corollary 1 under the optimal bin size, showing that the bound effectively captures the behavior of the total bias. The last two figures plot the TCE gap with different bin sizes compared to the theoretically optimal number of bins. Despite some fluctuations due to a small sample size $n$, the actual behavior closely aligns with theoretical predictions, validating the optimal bin size. These facts will be added in Appendix H.

Q.5: Regarding the interpretation of the error bars for the bound values in Table 1

A. The error bars in Tab. 1 (and the standard deviation in Fig. 1, which is almost unrecognizable due to its small value) are attributed to the randomness inherent in various experimental settings during model training, i.e., randomness of the training dataset and the initial model parameters. We acknowledge that we have not explained this point clearly enough, so we will include this explanation in Appendix G.

Q.6: The issue with the statement on Line 258 about $I(S;W) = O(\log n)$

A. Your point is correct, and the cited results consider a setting similar to Bayesian inference, involving conditionally i.i.d. samples. We cited the result as an example illustrating a scenario where mutual information is theoretically controlled. To make the meaning of the citation clearer, we plan to explicitly state that the cited paper addresses conditionally i.i.d. settings.