PAC-Bayes Analysis for Recalibration in Classification

We sincerely thank you for your feedback.

Experimental Designs Or Analyses

Q.1: Regarding the Gibbs error

Step 5 of Algorithm 1 shows that we take the average over $J$ posterior samples. In contrast, the theory defines bias as the expectation over the hypothesis distribution outside the absolute value, while the algorithm takes it inside. By Jensen’s inequality, the inside expectation is smaller, so the theoretical bound—specifically, Corollary 5—still holds for the algorithm.

Relation To Broader Scientific Literature

Q.2: Regarding the relationship between this study and Futami and Fujisawa (2024)

Please refer to our response to Reviewer mK1Q’s Q.1. In short, our main technical contribution is the decomposition of bias into approximation and estimation errors, and the development of a bounded-difference concentration inequality enabling finite-sample ECE bias analysis in multi-class settings. This extends the analytical framework of Futami and Fujisawa (2024) beyond binary classification.

Other Comments and Suggestions

Q.3: Regarding the notation of expectation

We apologize for the inconsistent use of $\mathbb{E}\_X$ and $\mathbb{E}\_{p(X)}$. This reflects common conventions in different contexts: PAC-Bayes often uses $p(X)$, while bias analysis refers to $X$. We will revise the notation for better consistency and clarity.

Q.4: Regarding our explanation around line 152

We revised the explanation as follows:

• “The output after recalibration, $\eta_v\circ f_w$, is expected to yield a sufficiently small $\mathrm{ECE}(\eta_v\circ f_w, S_{\mathrm{re}})$. From a generalization perspective, it is important to theoretically investigate conditions under which $\eta_v\circ f_w$ also achieves low $\mathrm{ECE}(\eta_v\circ f_w,S_{\mathrm{te}})$. To this end, we define the following error term, resembling the standard generalization error typically defined via a loss function.”

Q.5 and 6: Regarding $\lambda$ in Theorem 1, Eq. (6)

We added the assumption $\lambda > 0$ to Theorem 1 and corrected it to $\eta_{V}$.

Q.7: Regarding our explanation around line 227

We apologize for the overstatement and have revised the text as follows:

• “This result highlights the importance of KL regularization in the parameter space—similar to the standard PAC-Bayes bound over $S_{\mathrm{tr}}$ (McAllester, 2003; Alquier et al., 2016)—in preventing overfitting and improving generalization.”

Q.8: Regarding our explanation around line 309

We revised the explanation as follows:

• “Since this objective function is derived from the PAC-Bayes bound for $l_{\textrm{acc}}$ (Theorem 4 in Appendix B) and Corollary 2 via a union bound, it remains within the generalization error bound (see Corollary 5 in Appendix C.3 for details).”

Q.9: Regarding our explanation around line 294

This has been corrected. We apologize for any confusion.

Questions

Q.10: Regarding the difference from Futami and Fujisawa (2024)

Please see our responses under Relation to Broader Scientific Literature and Weaknesses, and Reviewer mK1Q’s Q.1 for clarification.

Q.11: Regarding the limitation of our PBR

We added the following to the fifth paragraph of Section 6.2: GP-based recalibration methods, including PBR, construct the GP prior using outputs of the trained model $f_w$ as inducing points. If $f_w$ misclassifies training data, the prior may be misaligned with the true distribution, and the posterior will be regularized toward this inappropriate prior, degrading performance.

Q.12: Regarding clarification on class identification

We apologize for the lack of clarity. Our intention was to consider the Top-$K'$ classes—those with the highest predicted probabilities—as a natural extension of TCE. Your comment prompted us to reconsider pre-specifying a particular set of $K'$ classes. We found this also theoretically valid and practically relevant when focusing on calibration for specific target classes. This discussion was added to the final paragraph of Section 3.3.

References

• Futami & Fujisawa, 2024
• Alquier et al., 2016
• McAllester, 2003

Thank you very much for your valuable suggestions. All proposed changes have been incorporated into the main text. Due to the word limit, we cannot provide all revision details here. Please feel free to contact us during the discussion period if you'd like more information.

Theoretical Claims and Weaknesses

Q.1: Proof Sketch of Theorems 1 and 2

We added a proof sketch to clarify our theoretical contributions. The bias is decomposed into binning approximation error and finite-sample estimation bias:

• We define $f_{\mathcal{I}}(x) = \sum_{i=1}^B \mathbb{E}[f_w(X) \mid f_w(X) \in I_i] \cdot 1_{f_w(x) \in I_i}$, representing the expected label frequency in each bin.
• The bias is bounded as: $\mathrm{Bias}(f_w, S_{\text{te}}, \mathrm{CE}) \leq |\mathrm{CE}(f_w) - \mathrm{CE}(f_{\mathcal{I}})| + |\mathrm{CE}(f_{\mathcal{I}}) - \mathrm{ECE}(f_w, S_{\text{te}})|$
• The first term uses the Lipschitz assumption; the second is bounded via McDiarmid’s inequality with binwise conditioning.
• In Theorem 2, only the second term remains and is bounded via PAC-Bayes using the Donsker–Varadhan inequality.

These techniques generalize the binary setting Futami & Fujisawa, 2024 to the multiclass case and form a core novelty of our work.

Q.2: Clarifying Contributions in the Introduction

We revised the sixth paragraph of the Introduction to concisely state our contributions, including the decomposition and concentration inequality enabling analysis of binning-based ECE with UWB.

Experimental Design or Analyses

Q.3: Empirical Validation of Theoretical Results

We extended the bound verification experiment from Zhang et al., 2020 and (Futami & Fujisawa, 2024) to the multiclass case. Using synthetic data with analytically computable TCE, we confirmed:

• The TCE–ECE gap decreases as $\mathcal{O}(1/n^{1/3})$ at the theoretical bin size.
• The empirically optimal bin size also follows $\mathcal{O}(n^{1/3})$.

Results are shown here. This discrepancy arises because the theoretical bin size minimizes the upper bound, not necessarily the actual TCE gap. We added this discussion to Section 6.

Other Comments and Suggestions

S.1-1: Clarifying Use of UWB

We clarified early in the Introduction that our analysis focuses on ECE estimated using UWB. In Section 7, we also note that extending the theory to estimators like uniform-mass binning is an important future direction.

S.1-2: Justifying TCE and ECE Focus

We chose TCE and ECE because (1) TCE is theoretically well-founded, (2) ECE is its standard estimator in practice, and (3) their bias and generalization in multiclass settings remain underexplored.

S.2: Clarifying Eqs. (8) and (9)

We added definitions for key terms (e.g., total bias, generalization error, top-$K$ CE) and clarified the distinction between Eqs. (8) and (9).

S.3: Related Work Positioning

To improve clarity, we placed Related Work after introducing the main definitions. A pointer to Section 5 was added at the end of the Introduction.

S.4: Correlation Analysis

Following prior work (e.g., Jiang et al., 2019; Kawaguchi et al., 2023), we confirmed a positive correlation between the KL term in Eq. (6) and the ECE gap through PBR-based experiments. This supports the validity of the bound. We made this clearer in Section 6.1.

S.5: Parametric vs. Nonparametric Clarification

We revised the abstract and Section 1 to clarify the use of nonparametric methods (e.g., binning for ECE estimation) and parametric ones (e.g., recalibration via GP). We also clearly stated the two main objectives.

Questions

Q.4: Class Size and Prior Choices

Theorems 1 and 2 focus on Top-1 accuracy and are unaffected by class size $K$, but Theorem 3 is. Our bound decreases slower than $\mathcal{O}(\sqrt{K/n})$ (Morvant et al., 2013), which is an important direction for future work.
Our bin size is minimax-optimal and aligns with asymptotic trends. $\lambda$ and the prior are tunable; we used a GP prior, but tighter (non-optimizable) bounds from marginal or IT-based priors (e.g., Futami & Fujisawa, 2024) are also possible.

Q.5: Fast Rates under Low-Noise Conditions

Under Bernstein or Tsybakov noise (Alquier et al., 2016), PAC-Bayes can achieve fast rates. Our setting differs structurally, but exploring whether fast-rate bounds can be incorporated into ECE analysis is an interesting future direction.

Thank you very much for your valuable suggestions. All proposed changes have been incorporated into the main text. Due to the word limit, we cannot provide all revision details here. Please feel free to contact us during the discussion period if you'd like more information.

Claim and Evidence

Q.1: Motivation for Eq. (9)

As you noted, the Brier score is a proper scoring rule and can improve accuracy (e.g., Kull et al., 2015; Perez-Lebel et al., 2018). However, our setting involves recalibration, where $f_w$ is trained with cross-entropy loss. Using a Brier-based recalibration may lead to inconsistent per-sample losses, particularly since squared loss can behave erratically for noise in the dataset. To mitigate this, we evaluated both Eq. (8) (Brier) and Eq. (9) (Brier + cross-entropy). Empirically, Eq. (9) tended to perform better.

Methods and Evaluation Criteria

Q.2: Motivation for using UWB and method comparison

• (a) We focus on ECE via uniform-width binning (UWB), a widely used estimator in prior work. As noted in Section 7, alternatives like Kernel CE or Smoothed CE may improve stability, but our work is the first to theoretically analyze the instability of binning-based ECE in the multiclass case.
• (b) Binary methods (e.g., Beta calibration, isotonic regression) can be extended via one-vs-all but calibrate only the top class. Hence, we compare only methods designed for multiclass outputs. We revised Section 6.2 to clarify this, and Appendix E contains full comparisons.

Experimental Designs or Analyses

Q.3: GP-based methods and overfitting

GP-based methods may face instability with limited recalibration data. However, their kernel-based smoothness prior acts as a natural regularizer based on the principle of Occam’s razor (e.g., Rasmussen & Williams, 2006; Bishop, 2006; MacKay, 1998), making them more robust to overfitting than parametric methods like temperature scaling. We added this to Section 6.2.

Q.4: GP computational complexity

We revised Section 4.2 to clarify:

• We use the outputs of $f_w$ on $S_{\mathrm{re}}$ as $M$ inducing points for a data-dependent GP prior $\tilde{\pi}$, which maintains independence from $S_{\mathrm{tr}}$.
• Following (Wenger et al. , 2020), we reduce the cost from $\mathcal{O}(N^3)$ to $\mathcal{O}(N^2M)$ (here, $N$ corresponds to the number of $S_{\mathrm{re}}$), which is feasible as the sample size of $S_{\mathrm{re}}$ is often smaller than that of $S_{\mathrm{tr}}$.

Relation to Broader Scientific Literature

Q.5: Novelty and context

Prior work on ECE bias (e.g., Gupta & Ramdas, 2021; Sun et al., 2023; Futami & Fujisawa, 2024) mostly focuses on binary settings and does not address generalization (except for Futami & Fujisawa, 2024). Our work extends this to multiclass classification, with an optimizable PAC-Bayes bound and a novel recalibration algorithm.
While some findings (e.g., optimal bin size) are consistent with binary results, this cross-setting agreement itself shows a novel knowledge obtained via our study. Multiclass calibration metrics have been discussed (e.g., Zhang et al., 2020; Gruber & Buettner, 2022), but without generalization or recalibration—key aspects of our study.

We revised Section 5 accordingly:

• Discussed how our PAC-Bayes analysis differs from conventional i.i.d.-based approaches.
• Clarified that our bound is optimizable, enabling practical algorithm design.
• Highlighted how our Theorem 3 formally explains the curse of dimensionality in $\mathrm{CE}\_K$, unlike prior work.

Other Strengths and Weaknesses

Q.6: Writing improvements

Thank you for your comment. To enhance clarity, especially for readers less familiar with PAC-Bayes theory, we added proof sketches after Theorems 1 and 2 (see our response to Reviewer FaKB Q.1). We also removed a potentially confusing explanation around lines 191–192. Due to the word limit, we were unable to list all specific revision details here. If you are interested, we would be happy to provide them during the discussion period—please feel free to reach out.

References

• Kull et al., 2015
• Perez-Lebel et al., 2018
• Rasmussen & Williams, 2006
• Bishop, 2006
• MacKay, 1998
• Wenger et al. , 2020
• Gupta & Ramdas, 2021
• Sun et al., 2023
• Futami & Fujisawa, 2024
• Zhang et al., 2020
• Gruber & Buettner, 2022

We sincerely thank you for your feedback.

Q.1: Regarding the key technical innovations of this paper relative to Futami and Fujisawa (2024)

The key difference from Futami and Fujisawa (2024) lies in extending the analysis from binary to multi-class classification. In the binary setting, the change in ECE when replacing a single sample can be easily bounded, enabling a straightforward application of McDiarmid’s inequality via bounded differences. In contrast, our multi-class setting requires bounding the difference over simplex-structured binning, which is significantly more complex. Establishing a proof technique to handle this is a core technical contribution of our work. The effectiveness of extending the proof techniques to the multiclass setting is most clearly shown in the analysis of the Top-$K$ calibration metric in Theorem 3 and the corresponding optimal bin size. Our analysis suggests that the derived optimal bin size is closely related to the nonparametric estimation of conditional probabilities in $K$-dimensional spaces. This insight generalizes the findings of Futami and Fujisawa (2024), which focused on the binary classification case, essentially a one-dimensional problem involving the predicted probability of a single label. Moreover, while their information-theoretic analysis yields non-vacuous bounds via mutual information, it does not lead to optimizable objectives, making it unsuitable for deriving generalization-aware recalibration algorithms. In contrast, our PAC-Bayes-based analysis provides a KL-divergence upper bound that is optimizable, naturally leading to a variational Bayes-style recalibration method.

Q.2: Regarding the justification of the Lipschitz continuity assumption

We guess this question concerns Assumption 1, so we first clarify its meaning. Assumption 1 states that, for a neural network $f_w(x)$ with a final layer mapping into the probability simplex (e.g., via softmax), the conditional probability $\mathbb{E}[Y \mid f(x)]$ of the top predicted class is Lipschitz continuous with respect to the input $x$, under fixed parameters $w$. Notably, the Lipschitz condition is imposed only on the input space, not on the computation of the top class index $C = \arg\max_{k} f_{w}(x)_k$. That is, the assumption only requires that there exists a constant $L$ such that $\left|\mathbb{E}[Y \mid f(x)] - \mathbb{E}[Y \mid f(x')]\right| \leq L \|x - x'\|$, where the output components are fixed. Thus, the argmax operation does not influence this assumption. Moreover, this Lipschitz continuity is a mild and standard assumption in nonparametric estimation, including binning and kernel-based ECE estimation. Since ECE estimates a conditional expectation, some form of smoothness—such as Lipschitz or Hölder continuity—is required. Without it, even a small change in input could cause drastic label changes, making estimation from finite samples infeasible. It has been shown that such smoothness is necessary for consistency in conditional expectation estimation (see Li et al., (2021)). This assumption is directly related to estimation bias: without it, ECE does not converge to TCE, even as the number of samples increases.

References

• Futami & Fujisawa, 2024
• Li et al., 2021