PAC-Bayes Analysis for Recalibration in Classification
Authors: Masahiro Fujisawa
Futoshi Futami
Venue: ICML 2025 poster (2025)
Keywords: Calibration
ECE
expected calibration error
PAC-Bayes
Primary area: theory->probabilistic_methods
TL;DR: We present a PAC-Bayes analysis for calibration error and propose a new generalization-aware recalibration algorithm.

Abstract: Nonparametric estimation using uniform-width binning is a standard approach for evaluating the calibration performance of machine learning models.
However, existing theoretical analyses of the bias induced by binning are limited to binary classification, creating a significant gap with practical applications such as multiclass classification. Additionally, many parametric recalibration algorithms lack theoretical guarantees for their generalization performance.
To address these issues, we conduct a generalization analysis of calibration error using the probably approximately correct Bayes framework. 
This approach enables us to derive the first optimizable upper bound for generalization error in the calibration context. 
On the basis of our theory, we propose a generalization-aware recalibration algorithm. 
Numerical experiments show that our algorithm enhances the performance of Gaussian process-based recalibration across various benchmark datasets and models.

PAC-Bayes Analysis for Recalibration in Classification
Masahiro Fujisawa" 12
Futoshi Futami 12
Abstract
evaluates the disparity between the predicted probability of a model and the conditional probability of the label frequency given by the model prediction. Analytically computing the TCE is, however, challenging because the conditional probabilities of the labels are intractable. Among various methods proposed to address this issue, constructing its es- timator called the expected calibration error (ECE) using uniform-width binning (UWB) (Zadrozny and Elkan, 2001; Naeini al., 2015) is one of the most widely adopted. This study centers on this approach.
Nonparametric estimation using uniform-width binning standard approach for evaluating the calibration performance of machine learning mod- els. However, existing theoretical analyses of the bias induced by binning are limited to binary clas- sification, creating a significant gap with practi- cal applications such as multiclass classification. Additionally, many parametric recalibration algo- rithms lack theoretical guarantees for their gen- eralization performance. To address these issues, we conduct generalization analysis of calibra- tion error using the probably approximately cor- recf Bayes framework. This approach enables us to derive the first optimizable upper bound for gen- cralization error in the calibration context. On the basis of our theory, we propose a generalization- aware recalibration algorithm. Numerical experi- ments show that our algorithm enhances the per- formance of Gaussian process- process-based recalibration across various benchmark datasets and models.
If the ECE is small, we consider the model well well-calibrated and its predictions highly reliable. Unfortunately, as has already been made evident in recent studies, models such as neural networks are not necessarily well-calibrated (Guo et al., 2017). If a model shows poor calibration performance, it is common to apply post-processing technique known as recalibration (Guo et al., 2017; Zadrozny and Elkan, 2001). This technique adjusts predicted probabilities using recali- bration function a parametric function trained separately from the original model on a dataset independent of both training and test data. Recalibration aims to train separate function that, when composed with the original predictor, yields a low ECE. Numerous methodologies have been pro- posed recently, including temperature scaling (Guo et al., 2017) and recalibration based on variational inference (VI) with a Gaussian process (GP) (Wenger et al., 2020).
1. Introduction
Increasing the reliability of machine learning models is cru- cial in risk-sensitive applications such as autonomous driv- ing (Chen et al., 2015). Recently, the concept of calibration has become significant measure of reliability, especially in classification tasks. In this context, the calibration per- formance is evaluated by how well predictive probabilities provided by our model align with the actual frequency of true labels. close correspondence between them indicates that the model is well-calibrated (Dawid, 1982; Widmann et al., 2021). To evaluate the calibration performance, a calibration error (Gupta and Ramdas, 2021; Roelofs al., 2022) such as the top-label calibration error (TCE) (Kumar et al., 2019; Gruber and Buettner, 2022) is often used. This
Given that the ECE is an estimator of the TCE, it is im- portant for reliable uncertainty evaluation to understand the extent of bias introduced between them before and after recalibration. Nevertheless, the theoretical understanding of this remains limited. In the context of bias analysis be- fore recalibration, many studies have focused exclusively on binary classification and have shown that the number of bins used in binning significantly affects both the estimated ECE and the bias (Gupta and Ramdas, 2021; Sun al., 2023; Futami and Fujisawa, 2024). Such insights remain unclear in the multiclass classification context. Moreover, regularization techniques have been proposed to reduce the ECE on training data (Kumar et al., 2018; Popordanoska et al., 2022; Wang et al., 2021a). However, a low ECE on training data does not guarantee a similar low TCE. Verify- ing this requires a theoretical analysis of the gap between these, which, to our knowledge. has not yet been explored.
'Equal contribution 'The University of Osaka, Osaka, Japan "RIKEN Center for Advanced Intelligence Project, Tokyo, Japan. Correspondence to: Masahiro Fujisawa <fujisawa boist.osake upac.jps, Futoshi Futami ffutami.futoshi.coo osaka-u.ac u.ac.pp
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

PAC-Bayes Analysis for Recalibration in Classification
This situation remains the same even after recalibration. Moreover, in many recalibration methods, postprocessing is performed to achieve low ECE only the recalibra- tion data. However, in practice, it is desirable to perform recalibration such that the ECE evaluated on test data is reduced-that is, to enhance the model's generalization per- formance from the ECE perspective through recalibration. Although existing studies have confirmed this point only through numerical experiments (Platt, 1999; Zadrozny and Elkan, 2002; Kull et al., 2017; Naeini et al., 2015; Guo et al., 2017; Wenger et al., 2020), recalibration methods with theo- retical guarantees for improving generalization performance in terms of ECE have not been explored thus far.
view of how our contributions relate existing literature.
2. Preliminaries
In this section, we summarize the basic notations, problem setup (Section I),, calibration metric (Section 2.2), and postprocessing by recalibration (Section 2.3).
2.1. Notations and Problem Setting
For a random variable denoted in capital letters, we ex- press its realization with corresponding lowercase letters. Let P(X) denote a probability distribution of X, and let P(Y|X) represent the conditional probability distribution of Y given X. We express the expectation of random variable X as Ex Let (L(PIIQ) be the KL divergence of P from Q, where Q is a probability distribution and P is absolutely continuous with respect to Q.
Given this background, we conduct a comprehensive anal- ysis of the bias of the ECE in multiclass classification. To achieve this, cusing on the ECE before and after recalibration by ap- plying the probably approximately correct (PAC) Bayes theory (McAllester, 2003; Alquier et al., 2016), a general method for deriving generalization bounds across various models. Since PAC-Bayes theory allows for the algorithm- dependent analysis of generalization performance, the ob- tained upper bounds are often optimizable and useful for deriving new generalization-wwar algorithms. In apply- ing PAC-Bayes analysis to the ECE, we face the following two challenges: (i) Owing to the nonparametric estima- tion of conditional probabilities, the ECE computed on the test dataset is not a sum of independently and identically distributed (i.i.d.) random variables and thus cannot be applied using the existing PAC-Bayes bounds derived under the i..d. assumption, and (ii) some bins may not contain samples because UWB divides the probability interval [0, 1] into equal widths, making it difficult to apply the concentra- tion inequality used in the PAC-Bayes bound derivation.
develop statistical learning theory fo-
Let 2 = X' y be the domain of data, where X' and y are the input and label spaces, respectively. Let the label space be D' = {0. ..... K 1), where K E N is the number of classes. For the label Y E Y. we define the one-hot encod- ing of the label Y as ey E R Suppose 'D represents an unknown data distribution, and let S.. == {(Xm. Ym)) } denote the training dataset consisting of nur samples drawn i.i.d. from D. We also define the test dataset comprising The samples drawn i.i.d. from D. Let fw : X - A K be probabilistic classifier, where A represents the K- dimensional simplex. This classifier is parameterized by w E W C Rd. For example, such a simplex is obtained by the final softmax layer in neural networks. Under these settings, fw predicts the label from C == argmax, (X)x. where (x) ) is the k-th dimension of f (z), which rep- resents the model's 's confidence of the label h: E K.
We evaluate the performance characteristics of the trained predictor fw, such its accuracy using the classification loss function lace ) x A K + R. where lace (x)) denotes the loss incurred by the prediction (x) for the target y. We define the training loss as L(w, The E(XY)ES, lace lYc fan (X)) and the expected loss as L(w, D) = Lacc (Y, (X)). Under this setting, one of the major purposes of the learning algorithms is to achieve the small generalization gap for loss function laccs which is defined as [L D) L(w, S-
Our main contribution a novel analysis of ECE in multi- class classification, which addresses the abovementioned limitations. We begin by presenting decomposition of the bias into binning bias and finite-sample estimation bias. We then derive a novel concentration inequality that enables theoretical analysis in the foming-bbssed ECE setting with UWB. This framework reveals that the bias in ECE estima- tion converges at a notably slow rate. Furthermore, by deriv- ing the PAC-Bayes bound, we have successfully formulated new generalization-awan recalibration algorithm, which is expected to improve the generalization performance of cali- bration and reduce the estimation bias in TCE. Numerical experiments confirm a correlation between the Kullback- Leibler (KL) regularization terms in our bounds and the generalization performance, show that our method can im- prove GP-based recalibration, and reveal the instability of ECE-based calibration performance evaluation due to the slow convergence rate. Finally, we discuss related work in light of our theoretical findings in Section 5, providing
=
2.2. Calibration Metries for Multiclass Classification
In the context of calibration, it is expected that not only fw has high accuracy but also its predictive probability aligns well in the actual label frequency P(Y k) f)f((()) (x)) for k O,..., K 1. Hereinafter, given (w, x), we treat (()) as the K dimmennsioaal vector by regarding its k-th element as P(Y = k) (x)). Then, a model is well-
2

---

PAC-Bayes Analysis for Recalibration in Classification
calibrated (Widmann et al., 2021; Gupta al., 2020) when P(Y]s((X) (X) holds. However, it is difficult to confirm this in practice. Instead, frequently used measure is the top-label calibration error (TCE) (Kumar et al., 2019; Gruber and Buettner, 2022), which uses the highest prediction probability in fw:
ization perspective, it is important to theoretically inves- tigate conditions under which y fi also achieves low ECE(7% fw, Ste). To this end, we define the following enror term, resembling the standard generalization error typ- ically defined via a loss function.
gen(me o sw, Ste, ECE.)
TCE(fw) EI
fu
: -I,s,, [E, ECE( o fws Sto) ECE(( o fw: Ste)
Unfortunately, evaluating the TCE is still infeasible because P(Y (X)cc is intractable. To resolve this issue, we evaluate the calibration performance by constructing the estimator of the TCE, The widely used estimator is the expected calibration error (ECE), where binning is used to estimate P(Y- = (X))c (Guo al., 2017: Zadrozny and Elkan, 2001; 2002). The ECE is often computed us- ing UWB, which partitions the predictive probability range [0, 1] into B equal-width intervals I = {4:)-1 (called bins) and averaging within each bin using an evaluation dataset E =h, For simplicity, we refer to UWB simply as binning. Accordingly, we define the ECE based on binning as follows:
We refer to this quantity as the generalization error of the ECE under Sre. In addition, the total bias for the recalibration, defined below, is required be small:
Bias (Ne swy Ste, TCF) = |TC fw) ECE(1 sus S-o)
Another goal of our study is to provide theoretical under- standing of these errors and biases by deriving their upper bounds using PAC-Bayes theory.
S. = {2m]m
3. Analysis of ECE for Multiclass Classification
ECE(fw, Se)= Σ pil..s. Pt.s.l:
(1)
Here, we present a comprehensive analysis of the ECE before applying recalibration.
where |4g = Emi=1 fulamde Pi
3.1. Total Bias Analysis for the ECE
and pt,s. 1 Em=1 (x)())) =m= Here, bins are set by divid- ing the interval [0, 1] into B bins of the same width: I 1/ (1/B,2/3 2/BB
fu.s. == [..
[.T2 Em=1
In this section, we present our main analysis for the total bias. Under the smoothness assumptions commonly used in nonparametric estimation (Tsybakov, 2008), we show the following theorem:
T..1
IB= ((B - 1)/B.B}
Since the ECE is an estimator of TCE, it is important to understand the bias defined as
Assumption 1. Conditioned on W = w, the L-Lipschitz continuity holds for P(Y C ())(()))))) (x)c).
Bias(f Se, TCE) == [TCE(f=) ECE(fw. Se)l.
Theorem Given W w. for any positive constant (0, 1) and X >> O, with probability E with respect to Sie. we have
and we refer to this as the total bias. As discussed in Sec- tion 1, one of our goals is to evaluate this bias theoretically in the multiclass classification setting.
+ B log 2 + log + 22a
1 +
Bias( Ste, TCF) S
mic
B
X
2.3. Postprocessing by Recalibration
The trained predictor (x)) can be poorly calibrated (Guo et al., 2017; Kumar et al., 2019). One common approach to address this problem involves recalibrating (xr) by post- processing using the parametric function fγV : A -> AK where E V C Rd is the parameter learned by the recali- bration dataset S,e ~ D at fixed w and S,e is independent of St.- In this procedure, the overall dataset is split into the training data S., for learning W, the recalibration data Sre for learning V, and the test data S.e for the evaluation of the ECE. We define the recalibrated model as no fw.
The complete proof is shown in Appendix B.5. The first term on the right-hand side is referred as the binning bias, whereas the second term is called the estimation bias (Fu- tami and Fujisawa, 2024). According to this theorem, the number of bins shows a trade-off off relationship as follows. As we increase B, the binning bias decreases because we esti- mate the label frequency more precisely. On the other hand, the statistical bias increases since the number of samples al- located to each bin decreases. From this observation, we de- rive the optimal number of bins that minimize the total bias. By setting X / /Bnee we can minimize the upper bound of Eq. (3) with respect to B. This yields B = (ml) 1/3), and
The output after recalibration, n/ fw. is expected to yield sufficiently small ECE(1) o Sw, S.o). From a general-
3

---

PAC-Bayes Analysis for Recalibration in Classification
under this bin size, the order of the estimation bias becomes
Comparison with existing work: The most closely related analysis is that performed by Futami and Fujisawa (2024); they evaluated a similar bias using information-theorele generalization error analysis (IT analysis) (Xu and Ragin- sky, 2017). Their obtained bound and ours achieved the same order with respect to n, which improves previous re- sults, such as those obtained by Gupta and Ramdas (2021), 1), However, our result has two advantages over that obtained by Futami and Fujisawa (2024). The first advantage is that ours can treat the multiclass setting and the second advan- tage is that our theory builds on the PAC-Bayesian theory and the upper bound is optimizable, which leads to our novel recalibration algorithm, as shown in Section 4. On the other hand, Futami and Fujisawa (2024) used the supersam- ple setting of the IT analysis, with which the optimizable upper-bound is difficult to obtain.
(Sas Ste, TCE) - O(1/nee)) 1.3).
(2)
This optimal order matches the result of the binary clas- sification provided by Futami and Fujisawa (2024). This is natural, given that the binning ECE divides the top-1 predicted probabilities equally into B bins in both cases.
The order of the total bias in Eq. (2) is tight from the non- parametric regression viewpoint. As discussed by Futami and Fujisawa (2024), the TCE measures the error between two functions, namely, P(Y = Cl and (w)),, and estimate P(Y fl)( by binning, which is nonparametric method. Thus, this is problem of non- parametric regression on [0, 1] under Lipschitz continuity. According to Tsybakov (2008), the error in nonparametric regression cannot be smaller than O11/nl Achieving an order smaller than this requires additional assumptions about the data distribution. Thus, the order of our bound is convincing under the current assumptions. We note that assuming Hölder continuity instead of Assumption does not improve the order of the estimation bias owing to the bias caused by binning (see Appendix B.7 for details).
We also note that it seems difficult to use the approach of deriving tighter PAC-Bayes bounds on the basis of the KL divergence of the Bernoulli random variable kl (Maurer, 2004; Foong et al., 2021). This is because the ECE is no longer a sum of i..dd random variables as it is in test loss.
3.3. Analysis for the Top-K Calibration Metric
3.2. Total Bias Under the Training Dataset
In applications such as medical diagnosis (Jiang et al., 2012), it often important to calibrate the prediction probabilities for any & E [K], not simply focusing on the top-1. In this case, the alternative metric
Some recent algorithms (Kumar et al., 2018; Popordanoska et al., 2022; Wang et al., 2021a) focus on minimizing ECE(fa,; Sw) without guaranteeing that the gap between TCF(S=) and (CFF(Ju; will remain small. Therefore, in this section, we theoretically investigate the conditions that an algorithm must satisfy to minimize this gap and to achieve a well-calibrated model. To this end, we conduct a theoretical analysis focusing on the following bias:
CE (fw) = ElIP(Y - fw (X)1l,,
has been explored instead of TCE (Gruber and Buettner, 2022), where Ilp is the L distance in R The CEg met- ric measures the calibration performance of models across all classes. Here, we show that the direct estimation of CE& by binning results in slow convergence due to the curse of dimensionality.
Bias(sw, Str, TCE) == [TCF(fw) - -CCE(fe, S.)))
The following theorem presents the first PAC-Bayes bound for the generalization error of the ECE.
Let us consider the following binning scheme to estimate CEK. Since we want to estimate the K K-dimensional con- ditional probability in [0, 1] by binning, we split each dimension [0, 1] into B' bins of the same width. After doing so, there are B- = (B')* bins, and [0, 1j is split into B small regions. We refer to these regions as I = [1) In this case, the ECE of CEK can be defined as
Theorem 2. Under Assumption 1, for any fixed prior n,
which is independent of Sue and posterior distribution P
over W, and for any positive constant E [0, 1] and X >>000 0, with probability 1 - e with respect to Stn. we have
Bip fw, Ser, TCE)
(L(pI[T) + B Blog 2 + log ! + 2A
1+1.
L B +
ner
ECFK = Σ pill PillSr.s. Pr.sall,, (4)
A
The complete proof is shown in Appendix B.3. Assum- ing that (L(p][>) is sufficiently smaller than Ru. e.g., Olog nu)) and independent of B, and setting X = - BB we can minimize the upper bound of Eq. (3) with re- 1/3 spect to B. This yields B- = Onn and we have Bias(f fw, Suc, TCE)= = Olog ner /ar/n 1/3)
where [7s] == Em (u(a))ed Ds = 1T//ne. ft.s. = 1 Em fu and Pa,s. = [T.]
Σm fm )ei,)),,e Sym. The definition of Eq. (4) is sim- ilar to that of Eq. (1). The difference is that Eq. (1) only focuses on the top label. Under these settings, the upper bound of the total bias in ECE is given as follows.
4

---

PAC-Bayes Analysis for Recalibration in Classification
Theorem 3. Assume that J (x) has a probability density over [0, 1|K and [w)))] satisfies the T.-Lipschitz con- tinuity. Then, for any fixed prior x, which is independent of St. and the posterior distribution p over W. and for any positive constant & E [0, 1] and x > O, with probability 1- E with respect to Stc. we have
any fixed prior n. which is independent of Sye, and posterior
i over V, for any & E (0, 1) and X > 0, with probability E with respect to Sye, we have
Eggen(ny o f.. See. ECE)
(6)
KL(PI + Bogg 2 + log 1 + 422
E, - F.CK Stt))
(5) K²X²
K(1 (1++1) L)_ KL(p||=) + BK log 2 + log 1 +
20trr
B
A
This result highlights the importance of KL regularization in the parameter space-similas to the standard PAC-Bayes bound over Str (McAllester, 2003; Alquier et al., 2016) preventing overfitting and improving generalization. Since the recalibration data is available and we have fixed w. we only consider the posterior ò over V. Instead of fixing W w. we can also obtain the PAC-Bayes bound by taking expectation over W (see Appendix C.2).
By minimizing the upper bound of Eq. (5), we obtain the optimal bin size as B = (n x472, leading to an estimation bias of O log nee/ Mee//ner* We can similarly show the result of the total bias as
x+²)
Bias( Ste, CEx) =
- ECE Sto) = =11/m/ (((K2))).
Discussion about the assumption of Tht Rue nz Al- though single data point can be used to evaluate loss in a standard generalization error analysis, multiple data points are required to evaluate the ECE, as it is a nonparametric es- timator. Therefore, for a fair comparison, the same number of data points should be used in the analysis of the ECEs based on Sre and Suc. We also remark that this assumption is not very restrictive since we split all the available data into training, recalibration, and test datasets, and most data are allocated to the training dataset in practice.
The proof' are provided in Appendix B.8. This order aligns with the lower bound of K K-dimensional nonparametric re- gression with Lipschitz continuity (Tsybakov, 2008), and it is much larger than that of the TCE (Ollgg ut. /n/////))) owing to the curse of dimensionality. Thus, this result clar- ifies the pros and cons of the TCE; the TCE successfully circumvents the curse of dimensionality as described in Theorem 2 by focusing only on the top-1 predicted label, although does not necessarily guarantee good calibration performance for all classes (Gruber and Buettner, 2022).
Next, we present our MAC-Bayes bound on the estimation bias of the ECE and TCE in the recalibration context after in- troducing the necessary assumption similar to Assumption 1.
We note that our proof technique can be extended to cases where we focus on the calibration of any K" E [1, K] classes, resulting in a total bias of O11/nte 2/11/2/(K' 1/(K'+3) +2)) (see Appendix B. for the details). This finding suggests that in scenarios with large number of classes, it is crucial to selectively choose which classes to evaluate for calibra- tion, especially when additional classes beyond the top label require calibration evaluation, rather than evaluating all classes. This approach is essential for achieving sample- efficient calibration evaluations.
Assumption 2. Conditioned on W = w and V = v, the L-Lipschitz continuity holds for P(Y = Cluv o (x))) in the multiclass classification.
Corollary 2. Under Assumption 2, conditioned on W = w. for any fixed prior tt, which is independent of Stc. and pos- for terior distribution p over V, and for any positive constant [0, 1] and X > with probability E with respect to Seer we have
4. PAC-Bayes bounds under Recalibration
E,Bias(w fw, Sre, TCE)
In this section, we analyze the recalibration using PAC- Bayesian theory. leading to our novel recalibration algorithm in Section 4.2. All the proofs are provided in Appendix C.
1 KT(PI(*) + B log 2 + log ! + 2x²
(7)
4.1. Generalization and Total Bias under Recalibration
Similarly to Eq. (3), there is a trade-off relationship with respect to B in the above bound. By minimizing this upper bound with respect to B, we obtain the optimal bin size as
The following result shows the PAC-Bayes bound of the ECE under the recalibration context.
B = O 1/3) For practical purposes, it is possible to set
Corollary 1. Assume that The = Nue = n. For both binary and multiclass classifications, conditioned on W = w. for
B |nre J. where [x] == max E Z : m S xx).
1/3
5

---

PAC-Bayes Analysis for Recalibration in Classification
4.2. Proposed Recalibration Algorithm Based on PAC-Bayes Bounds
Algorithm PAC-Bayes recalibration (PBR)
1: INPUT: All dataset Sanl model fw. recalibration model
Tu. variational posterior p(u; 0)
From Corollary 2,
see that as long a) is
Splitring all dataset Sall to Str. S
regularized and the ECE under the recalibration data is small, the recalibrated function could exhibit small TCE. This
3: Training fw using Su--
4: Updating 0 by minimizing Eq. (8) or (10) using Sre at fixed w.
leads us to propose a generalization-wwarr recalibration method by minimizing our bound.
5: Obtaining V by taking the mean of J samples
However, minimizing this function is difficult since the ECE neither smooth nor differentiable. To avoid this issue, we focus on the following relation:
(V))²= Lid. ((u;0)
(Option) Calculate the test ECE: ECE(M, fwo See) by 1/3
setting B = [ttre
7: RETURN: t/o a sw. (ECE(M) o sw: Ste))
EC su Sre) E(xYsss ler -I (x)
in the multiclass classification, where - denotes the expectation by the empirical distribution of Sie, see Appendix C.3 for its derivation. This upper bound is the Brier score (Gruber and Buettner, 2022), which is a con- tinuous and differentiable calibration metric. Therefore, under the posterior p(u) ç(uu ()) parametrized by 6, we minimize the following BAC--Byys-bbar based objective by based optimization:
to yield a small KL value. This is because w is trained using Str, and since Sur and Sre are independent, this does not violate the independence of Sre from as assumed in Corollary 1.
A GP-based recalibration method was also proposed by Wenger al. (2020), and, as far know, it is one of the methods that achieve ofate-of-the-arl performance. Their recalibration was conducted via variational inference (VI), i.e., minimizing the following objective function derived from the evidence lower bound (ELBO):
E E (x.S) ley ny Su (x)1 +o
(8)
((v:0)
Tre
(L(
Brier score
(x.r)s,, fac (Y, ny o fx))
Thee
We expect the recalibrated models to achieve not only low TCE or CE but also high accuracy in practice. We thus consider minimizing the following objective with the classification loss lacei
where lace is defined as the softmax loss. Eq. (10) corre- sponds to this ELBO objective when a and the Brier score is removed. This fact indicates that our PBR extends the GP-based recalibration to have flexible KI. regulariza- tion and Brier score loss to control calibration performance the basis of the PAC-Bayes notion. In this paper, we adopt in PBR the same computational strategy for GP-based recalibration as proposed by Wenger et al. (2020), in order to reduce the computational cost from ((N*) to O M). While this cost is not negligible, remains justifiable in practice, as the size of S,e is significantly smaller than that of Su. In Section 6.2, we compare PBR and Ga-based recalibration using the same recalibration model settings.
Ep Ep(n:) B Jace (Y, nv o (X))
(9)
Expected classilication
(pl)
+ E Exx,y)ss,,,le lley - Ty o fa (X) +a
fdee
score
(10)
Since this objective function is derived from the PAC-Bayes bound for lu (Theorem 4 in Appendix B) and Corollary 2 via union bound, it remains within the generalization error bound (See Corollary 5 in Appendix C.3 for details).
5. Related work
Several studies have applied PAC-Bayes theory to classi- fication metrics beyond accuracy. Ridgway et al. (2014) addressed AUC, Morvant et al. (2012) studied the confu- sion matrix in multiclass settings, and Sharma et al. (2024) examined conformal prediction quantification. In this work, we extend the PAC-Bayesian framework to the calibration metric.
We refer to the recalibration achieved by minimizing Eqs. (8) and (10) as PAC-Bayes recalibration (PBR) and summarize these procedures in Algorithm 1. As an example of re- calibration model in PBR, we use the Gaussian process (GP) (Rasmussen and Williams, 2005). In this case, p(v; f) is set as the multivariate Gaussian distribution, N(v;; Jr, E),
tool for uncertainty
where μ and Σ are the mean and covariance matrix, respec- tively. Furthermore, we can construct a data-dependent GP prior से using the M outputs {f (2, M (x E S.e) ob- tained during training as inducing points, which is expected
Gupta and Ramdas (2021) and Kumar et al. (2019) examined the ECE in binary classification, focusing on uniform mass hinning (UMB), which partitions the probability space into
6

---

PAC-Bayes Analysis for Recalibration in Classification
Dataset
Model 1-layer
Dataset CIRAR10D Model resnext: -1xxxt
Datas CIFARIOD densenet L190 k40
0.20
ECE gap (Blas)
0.032
0.0
0.010-
9.20
0.01
2.25
0.25
0.006
0.024
5.2
3.05
0.75
0.032
Kendall's t- 0.29
Kendall's T- 0
20
Kendall's T- 0.33
0.030
9.00
500
1003
1530
2530
50dco
130500
15:0000
200000
23530
403co
00003
302000
KL
KL
KL
Figure 1. KL vs ECE gap on MNIST (Multiclass; 1-layer NN) and CIFAR- 100 (Multiclass; ResNeXt-29 (Xic et al., 2017) and DenseNet- BC-190 (Huang et al., 2017)) dataset for cach of various regularize parameters (a:).
Table 1. Results of multiclass classification experiments on MNIST and CIFAR-100 100. The symbols (L) and (f) refer to lower and higher values indicating higher performance, respectively. We Rue
1000.
Dala
Modd
Uncalibrate
GP (Wezger et al. 20230
PER (Ours; Exy (8))
PER (Ours; Bq. (101)
Temp. Scaling
ECE (1)
Accurscy (?)
ECR
Accuracy (T)
(.)
Accursccy (7)
ECR(())
Accuracy (7)
ECE (1)
Accurscy (?)
XCBresl
.006
.0003
.975
.006
9786 0007
9775 0007
20011
9785
0006
.0055 .0117
.9755
.1425
19003 18/13
0315
00128
5620
Hayer NN
.0164 .00044
00020
(9740 0000
.0187 0014
0309
.0112
2019
8016
.0002
0000
alennet
.25-8 (8117
457-4 00935
25.88
1008
4575 H 0000
.258 10:7
AS72 0.00
2358
0017
1373 0009
0216
00037
45744 0003
WRN 25 10 drop
.0368 = (8000)
.333 3. 0011
.3367
50030
8129 1. .001]
.0004
00644
8120 2. 0011
.0340
0003
A129 4: n001
J0374
/0125
.5331 2. 0011
CIFARIOO
.0401 = -0110
5229 +: 0015
.0100
0000
8229 + .001
10520
= 0000
8228 + 0014
.0510
0082
5230 +: 0014
.0401
2019
8229 +: 0015
resnect tictiid
(1000 6: (0112
2231 4: MM13
3410
0003
8:10
3. 0014
03315 0006
8821 0013
A032
00771
8200 4. 0014
(1220
(412)
2531 d: 0015
densmett-hsl 190-4-00
0639
00088
8230
00090
0008
8229
02007
06500 1045
8218
0.00
.0188
0051
8239 0007
0222
0013
8230
0007
intervals of equal mass. They also analyzed a recalibration method based on UMB. Sun al. (2023) further analyzed binning-based recalibration for binary classification under similar Lipschitz assumption. Futami and Fujisawa (2024) investigated the generalization of the ECE using IT analysis under a comparable setting, and derived a total bias of order (L/n2//)) In contrast, our work provides an analysis of the binning ECE in the multiclass setting-a direction that has not yet been explored. Furthermore, our bound is op- timizable, which allows us to derive novel recalibration algorithm for the ECE criterion that explicitly considers gen- eralization. A natural direction for future work is to extend our analysis to settings that employ UMB.
6. Experiments
In Section 6.1, we verify the correlation between our bounds in Corollary and the generalization performance of recal- ibration. We then evaluate the effectiveness of our PBR described in Section 4.2. Due page limitations, we pri- marily report results from multiclass classification exper- iments the MNIST (LeCun et al., 1989) and CIFAR- 100 (Krizhevsky, 2009) datasets. Additional experimen- tal results are provided in Appendix E, and details of our experimental settings, including model specifications, are summarized in Appendix D. For ECE evaluation, we set B = [rre
1/3 based on our findings.
The analysis of multiclass calibration remains limited com- pared to that of binary classification. For instance, Zhang al. (2020) investigated the kernel-based CÊR; however, their analysis does not address generalization recali- bration, which fundamentally distinguishes our approach. Moreover, while they noted that the binning-based CFx suf- fers from the curse of dimensionality, no formal justification was provided. In contrast, our Theorem 3 formally validates this phenomenon. Gruber and Buettner (2022) discussed various calibration metries and clarified that the TCE weaker calibration metric than CEx- Theorem 3 further demonstrates that the naive estimator of CEœ suffers more severely from the curse of dimensionality than the TCE.
6.1. Verification of Our Bounds
In this section, we empirically investigate the correlation between the KL divergence term in Eq. (6) and the ECE gap, which we define as the absolute difference between the ECEs of the test and training datasets. Our goal here is to as- sess whether the KL divergence in our bound can adequately explain the observed generalization performance. To investi- gate this, we first conducted recalibration experiments using PBR (Eq. (8)) with various KL constraints (a). We then measured the KL values and the ECE gap after recalibra- tion using 10-fold cross-validation, setting fhe = 1000. As evaluation metrics, we adopted Pearson's 's and Kendall's rank-correlation coefficients, which are widely used to as- sess the consistency between generalization metries and actual generalization performance (Jiang al., 2020; Wang et al., 202 lb; Kawaguchi et al., 2023).
7

---

PAC-Bayes Analysis for Recalibration in Classification
alexnet
WAN-28-10-dog
re5next-8664g
re5next-16x644
densenet-Be wttettthh--99000 L190-k40
200
PCR total lours
PBR tous!
Temperature
014
0.15
1.0
0.01
2.00
0.7
0.02
1
4 6p
4
42
4
Figure 2. The vs ECE on the test dataset on the experiments with CIFAR-100 dataset. PBR (ours) and PBR total (ours) correspond to the results obtained by optimizing Eqs. (8) and (10), respectively.
A portion of the results is presented in Figure 1. These results confirm the positive correlation between the KL di- vergence and the ECE generalization gap. This confirms that our bounds are valid in explaining the generalization performance. It is also evident that the ECE gap is noisy. This is due to the slow convergence rate of the binning ECE estimator, which scales as O (11/n even under the optimal B. With The 1000, the estimation bias can con- tribute noise on the order of (1/110), meaning that when models achieve an ECE below 0.1, the correlation could be obscured by noise. A straightforward approach to reduc- ing noise is increasing the size of the recalibration dataset. However, due to the (1//nee) (3) convergence rate, this is impractical, highlighting the inherent difficulty of precise ECE evaluation.
One possible reason for this discrepancy is that Wenger et al. (2020) reported the ECE values with B 100. Accord- ing to our analysis. this setting minimizes estimation bias when 7ie = O However, since the actual The used in their experiments is significantly smaller (see Section 4.1 of Wenger et al. (2020)), their reported results may have been affected by severe bias. This finding underscores the fundamental importance of selecting an appropriate number of bins based on a well- well-grounded theoretical framework for conducting reliable empirical evaluations.
These findings also indicate that the GP recalibration some- times yield results that are not significantly different from the uncalibrated setting. In contrast, our PBR shows sub- stantial improvements over both uncalibrated and GP-based methods. It is worth mentioning that our additional ex- periments in Appendix E confirm that GP-based methods, including PBR, do not consistently outperform standard re- calibration techniques such as temperature scaling. These observations suggest that the use of GP for recalibration methods does not guarantee superior performance and em- phasize the importance of carefully selecting a recalibration strategy that aligns with the characteristics of the dataset and model.
6.2. Empirical Comparison of Recalibration Methods
In this section, we compare our proposed PBR and existing standard or state-of-the-art recalibration meth- ods, temperature scaling (Guo et al., 2017) and GP cal- ibration (Wenger et al., 2020). The optimizable pa- rameter in PBR is selected via grid search from {0., 0.01, 0, 0.25, 0.5, 0.75, 0.9, 1.0). Wenger et al. (2020) also reported results for recalibration methods origi- nally developed for binary classification, such as Platt seal- ing (Platt, 1999), isotonic regression (Zadrozny and Elkan, 2002), Beta calibration (Kull et al., 2017), and Bayesian binning into quantiles (BBQ) (Naeini et al., 2015), by adapt- ing these methods to the multiclass setting via one-vs-all conversion. To ensure a fair comparison, however, we in- cluded only methods that are directly compatible with mul- ticlass classification as baselines. A comparison of these methods in the binary classification setting can be found in Appendix E.
We also conducted additional experiments using f'ee {10, 50, 100, 250, 500, 1000, 30000 5000) to further exam- ine how the performance of each recalibration method varies with different values of Thre The parameter a in PBR was selected following the same procedure as described earlier.
We show the results in Figure 2. From these results, we can see that our PBR achieves relatively good performance under various settings of Tire, consistently improving the performance of GP-based recalibration methods. However, in experiments with AlexNet, GP-based recalibration includ- ing PBR fails except when The is small. Given AlexNet's lower accuracy (see the Uncalibrated column in Table 1), the following explanation may be plausible. All of our re- calibration methods construct the GP prior using the outputs of the pretrained model f.r as inducing points. If f.r fails to classify the training data accurately, the resulting GP prior will be misaligned with the true data distribution. Con- sequently, the recalibrated posterior is regularized toward
We summarize the results in Table 1. The results show that our method consistently improves calibration performance over existing approaches, particularly outperforming the GP-based recalibration method. Additionally, we found that, contrary to the findings of Wenger et al. (2020), tem- perature scaling sometimes performs better than GP-based recalibration in terms of ECE when using the optimal B.
8

---

PAC-Bayes Analysis for Recalibration in Classification
this inappropriate prior, which degrade overall perfor- mance. The temperature scaling appears to perform stable and effective recalibration The increases, regardless of ac- curacy, and it even achieves a higher performance than PBR in some experimental settings; however, it is considered to cause overlitting when Tye is small because the temperature scaling lacks regularization terms such as the KL divergence used in PBR. This underscores the importance of carefully selecting recalibration methods based the characteris- tics of the model and dataset denoted previously. Sum- marizing these results, in practical applications- at least for multiclass classification-ii it would be advisable to try both temperature scaling and our PBR, verify their perfor- mance using validation data, and choose the method that contributes more to improving calibration performance.
7. Conclusion and Limitations
In this paper, we analyzed the generalization error and esti- mation bias of the ECE in multiclass classification for the first time, resulting in several non-asymptotic bounds and the practical optimal bin size. Moreover, we developed a new generalization-awaal recalibration algorithm based PAC-Bayes bound. Our analysis also revealed the slow convergence of the ECE through binning, which is funda- mental limitation. As discussed in Section 3.2, the binning method cannot leverage the underlying smoothness of the data distribution. Our numerical results suggest that the limited number of test data points makes the numerical eval- uation of the ECE unstable in practice. We believe that other nonparametric methods for estimating the CE TCE may address the limitations identified in this study. Investigating the effectiveness of such methods constitutes an important direction for future work. Another key avenue for future research is to extend the theoretical analysis to cases where alternative methods for estimating the TCE, such as UMB, employed.

---

PAC-Bayes Analysis for Recalibration in Classification
Acknowledgments
S. Gruber and F. Buettner. Better uncertainty calibration via proper scores for classification and beyond. Advances in Neural Information Processing Systems, 55:8618-8632, 2022.
MF was previously supported by the RIKEN Special Post- doctoral Researcher Program and JST ACT-X Grant Num-
ber JPMIAX210K, Japan. MF is currently supported by KAKENHI Grant Number 25K21280 1866. FF was supported by JSPS KAKENHI Grant Number JP23K16948 FF was supported by JST, PRESTO Grant Number JPMJPR22C8, Japan.
C. Guo, G. Pleiss, Y. Sun, and K. Q Weinberger. On cal- ibration of modern neural networks. In International conference on machine learning, pages 1321-1330, 2017.
C. &uppta and A. Ramdas. Distribution-ffee calibration guar- antees for histogram binning without sample splitting, In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pages 3942-3952 PMLR, 18-24 Jul 2021.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
C. Gupta, A. Podkopaev, and A. Ramdas. Distribution-free binary classification: prediction sets, confidence inter- vals and calibration. Advances in Neural Information Processing Systems, 33:3711 2020.
References
P. Alquier, J. Ridgway, and N. Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 17(23)):--41, 2016.
G. Huang, 7. Liu, I.. van der Maaten, and K. Q Weinberger. Densely connected convolutional networks. In Proceed- ings of the IEEE Conference Computer Vision and Pattern Recognition, pages 2261-2261 2017.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013.
X. Jiang, M. Osl, J. Kim, and L. Ohno-Machado. Calibrat- ing predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263-277 2012.
L. Breiman. Random forests. Machine Learning, 45(1): 5-32, 2001.
C. Chen, A. Seff, A. Kornhauser, and J. Xiao. Deepdriving: Learning affordance for direct perception in autonomous driving. In Proceedings of the IEEE international confer- ence on computer vision, pages 2722-2730, 2015.
Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Ben- gio. Fantastic generalization measures and where find them. In The Tenth International Conference Learning Representations, 2020.
T. Chen and C. Guestrin. XGBoost: scalable tree boost- ing system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794, 2016.
Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottleneck help deep learning? In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 16049-16096. PMLR, 23-29 29-2 Jul 2023.
A. P. Dawid. The well-calibrated Bayesian. Journal of the American Statistical Association, 77(379):605-610, 1982. doi: 00010000016224591198222 10477855.
A. Foong, W. Bruinsma, D. Burt, and R. Turner. How tight can PAC-Bayes be in the small data regime? Advances in Neural Information Processing Systems, 34:4093-4105, 2021.
A. Krizhevsky, Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25, pages 1097-1105, 2012.
Futoshi Futami and Masahiro Fujisawa. Information- theoretic generalization analysis for expected calibration error. arXiv preprint arXiv:2405.15700 2024.
A. Geiger. Are we ready for autonomous driving? The KITTI vision benchmark suite. In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3354-3361. IEEE Computer Society, 2012.
M. Kull, T. S. Filho, and P. Flach. Beta calibration: A well- founded and easily implemented improvement on logistic calibration for binary classifiers. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pages 623-631, 2017.
10

---

PAC-Bayes Analysis for Recalibration in Classification
A. Kumar, P. S Liang, and T. Ma. Verified uncertainty calibration. Advances in Neural Information Processing Systems, 32:3792-3803, 2019.
A. Sharma, S. Veer, A. Hancock, H. Yang, M. Pavone, and A. Majumdar. PAC-Bayes generalization certificates for learned inductive conformal prediction. Advances in Neu- ral Information Processing Systems, 36, 2024.
Aviral Kumar, Sunita Sarawagi, and Ujjwal Jain. Trainable calibration measures for neural networks from kernel mean embeddings. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Confer- ence on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2805-2814, PMLR, 10-15 Jul 2018.
Z. Sun, D. Song, and A. Hero. Minimum-risk recalibration of classifiers. In Thirty-sevntth Conference on Neural Information Processing Systems, 2023.
A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008. ISBN 0387790519.
Y. LeCun, B. Boser, S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropaga- tion applied to handwritten zip code recognition. Neural Computatioo, 1(4):541-551 1989.
B. S. Veeling, J. Linmans, J. Winkens, T. Cohen, and M. Welling. Rotation equivariant CNNs for digital pathol- ogy. In Medical Image Computing and Computer Assisted Intervention MICCAI 2018: 21st International Confer- ence, Granada, Spain, September 16-20, 2018, Proceed- ings, Part 11, pages 210-218 2018
A. Maurer. A note on the PAC Bayesian theorem. arXiv preprint cs/0411099, 2004.
Deng-Bat Bao Wang, Lei Feng, and Min-Ling Zhang. Rethink- ing calibration of deep neural networks: Do not be afraid of overconfidence. Advances in Neural Information Pro- cessing Systems, 34: 34:1184:::1: 1809-118200 2021a.
D. A. McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21, 2003.
E. Morvant, S. Koço, and L. Ralaivola. PAC-Bayesian gener- alization bound on confusion matrix for multi-class clas- sification. In Proceedings of the 29th International Cofer- ence on International Conference on Machine Learning, pages 1211-1218, 2012.
H. Wang, Y. Huang, R. Gao, and F. Calmon. Analyzing the generalization capability of SGLD using properties of Gaussian channels. In Advances in Neural Informa- tion Processing Systems, volume 34, pages 24222-24234, 2021b.
M. P. Nacini, G. F. Cooper, and M. Hauskrecht. Obtaining well calibrated probabilities using Bayesian binning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 2901-2907, 2015.
J. Wenger, H. Kjellström, and R. Triebel. Non-parametric calibration for classification. In Proceedings ohe the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pages 178-190, 2020.
J. Platt. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods. In Ad- vances Large Margin Classifiers, pages 61-74, 1999.
D. Widmann, F. Lindsten, and D. Zachariah. Calibration tests beyond classification. In International Conference on Learning Representations, 2021.
Teodora Popordanoska, Raphael Sayer, and Matthew Blaschko. A consistent and differentiable Ip canonical cal- ibration error estimator. Advances in Neural Information Processing Systems, (177933-7946. 2022.
S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. In 2017 IEFE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5987-5995, 2017.
A. Xu and M. Raginsky. of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, vol- ume 30, pages 2524-2533, 2017.
cetemattion-theoreffe analysis
C. F. Rasmussen and C. K. I. Williams. Gaussian Pro- cesses for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
J. Ridgway, P. Alquier, N. Chopin, and F. Liang. PAC- Bayesian AUC classification and scoring. Advances in neural information processing systems, 27:658-666, 2014.
B. Zadrozny and C. Elkan. Obtaining calibrated proba- bility estimates from decision trees and naive Bayesian classifiers. In Icml, volume 1, pages 609-616, 2001.
B. Zadrozny and C. Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694-699. 2002.
R. Roclofs, N. Cain, J. Shlens, and M. Mozer. Mitigat- ing bias in calibration error estimation. In International Conference on Artificial Intelligence and Statistics, pages 4036 4054, 2022.

---

PAC-Bayes Analysis for Recalibration in Classification
S. Zagoruyko and N. Komodakis. Wide residual networks. In Proceedings of the British Machine Vision Conference (BMVC), 2016.
Zhang, Kailkhura, and Y.-J. Han. Mix-n-match: Ensemble and compositional methods for uncertainty cal- ibration in deep learning. In International conference machine learning, pages 11117-11128, PMLR, 2020.
12

---

PAC-Bayes Analysis for Recalibration in Classification
A. Remark about the binary setting
Here we introduce the calibration for binary classification. Although, the primary goal our study the multiclass setting, our theory can handle for both the binary and multicalss settings.
Let (0. 1) and let fw= X' > [0, be model, where the output corresponds the model's confidence that the label is 1. In the context of calibration, it is expected that not only fw has high accuracy, but also its predictive probability aligns well in the actual label frequency
A model is well-calibrated (Widmann et al., 2021; Gupta et al., 2020) when P(Y (X)) = (X) holds; however, it is difficult to confirm this. Therefore, an alternative metric called as the calibration error (CE) (Widmann et al., 2021; Gupta et al., 2020) typically used. Given W w, the CE is defined as
CE(fw) = E\ = 1l. - (x)) = E ff fan (X)I.
Unfortunately, evaluating the CE is still infeasible because E (X) is intractable. To resolve this issue, we evaluate the calibration performance by constructing the estimator of the CE. The widely used estimator is the expected calibration error (ECE), where binning is used to estimate fu (XX) (Guo et al., 2017; Zadrozny and Elkan, 2001; 2002). The ECE calculated by partitioning the range of the predictive probability [o, 1] into B intervals I = { (called bins) and averaging within each bin using an evaluation dataset S. = { 2m 1e ECE defined as
E nnr, where we assume ne 2 2B. That is, the
ECE(fw; Sc) Σ Pilfi,s. Vs,sol.
where [ Em 1 (l( P: [dl fr.s. [h Em=1 1 fm and Tr,s. Te
TI Emm 1 (Im))) In the above, bins are set by dividing the interval [0, 1] into B bins of the same width: 21/B,/B)).... .I,
1 = 1/B,/B]
B). Setting Se Ste. for instance, corresponds evaluat-
ing the ECE the test dataset.
Similarly to the multiclass setting, we define the total bias of CE as (f)), CE) |CE(n,(fw) (CE( for binary classification.
B. Proofs and discussion of Section 3
For the latter purpose, we define [n]] {L....,o n} for n e N and [x] max(m e E m S x}.
B.1. Additional preliminary
We use the following lemma repeatedly in our proofs.
Lemma (Used in the proof of McDiammid's 's inequality). (Boucheron et al., 2013) We say that a function f : X + R has the bounded difference property if for some nonnegative constants C...
sup
In) - f(z1. Ti-1, T
In) Sc, 1sisn.
of EX
If X,,..., Nu are independent random variables taking values in X and f has the bounded difference property with constants Ciy...y On, then for any E E, we have
E ((0X -1)
See En df
The following theorem is the most basic form of the PAC-Bayes generalization bounds (Alquier et al., 2016).
Theorem 4. For any fixed prior which is independent of St.. and posterior distribution over W and for any E (0,1)
and X > O, with probability e, we have
Sigen <l(p + log Ex,s, -L log
(11)
13

---

PAC-Bayes Analysis for Recalibration in Classification
B.2. Reformulations of the ECE to loss functions
Here, we introduce the reformulations of the ECE, which the essential technique in our proof. Note that when focusing on the TCE of the multiclass setting, its properties are almost the same as those of the binary classification. This is because TCE only considers the top label and by regarding the top label corresponding to label in the binary classification and other labels as O in the binary classification, then it is clear that the ECE of the multiclass and binary setting are almost identical.
BINARY CLASSIHICATION
We first focus on the binary setting. The training ECE can be reformulated as the empirical mean of - fx) in each bin as follows
B ECE( Se) =
Σ (Y fw(()) ( (x)ee)
(12)
which follows immediately from the definitions. Here Es, the empirical expectation by the evaluation dataset.
Recall that the conditional expectation of J given bins is defined as
B fz = Σ Bl (X) [.) - (x)ee
The following relation holds
CE(fz) Σ DX -Y fx()) 1 (x)en,
(13)
where CE(fz) means the CE of the function fz. We can derive this follows; By definition, we have
B
(X - fu(())) (x)en.
B Σ - fu (x)enll
Σ (X) ()EY))))))))) I.] - (X) A.l.
==
where we used the definition of the conditional expectation. On the other hand, We have
CE(ft) E/E[Y[fz(z)] - fx(x))
E [ - fx(x)) I sxxxee
Σ e - E
P(f((X) e ( E EX) 4Mb
where we used the tower property. This concludes the proof.
Thus, we can transform the loss and ECEs by Eqs. (12) and (13).
14

---

PAC-Bayes Analysis for Recalibration in Classification
MULTICLASS CLASSIFICATION
Next, we consider the ECE for the multiclass setting. Let C fw Then by definition of ECE, have
4 Pt.s.l
ECE(fw, Se)
Σ
fis.
Σ
(X)cet)
(14)
The
where [4g]
Em=1 fu(()))EE
fi..
1 fem and Pi..
[4|
I
Em=1 L (em))ol Aum==C =C. As for the conditional function, we define
Tol
B f = Σ (X) e 4,] s
Then by repeating the exactly same proof for Eq. (13), we obtain
B
TCE(F?())
Σ -ux -.. (x0oeee
(15)
We can that the ECE of the binary and multiclass classification essentially represents the same quantity; in the multiclass setting, by re-labeling C' as 1 and others 0, they represent the same quantity.
B.3. Proof of Theorem (Bias under the training dataset)
Here present generalized version of Theorem 2 that includes the binary classification. After that, show the proof of Theorem 1, which can be directly obtained from Theorem 2.
To simplify the notation, we express The
Theorem 5. Under Assumption for any fixed prior which is independent of Su., and posterior distribution p over W and any positive constant [0, and > O, with probability 1 with respect Sus we have
(T((p]()) B log 2 + loog 2xa n (Binary classification).
Biass Str. CE)
S
+
B
X
+ L B
1 c <L(p)() + log + log
+ 2x² n (Multiclass classification).
B. Bi.isssww, St.. TCE) <
A
Proof. BINARY SETTING
We start from the binary classification setting. To analyze the bias caused by binning, following Futami and Fujisawa (2024), we define the conditional expectation of fur given bins as fz(x) ΣB EXf AJ] ( With this definition, decompose the estimation bias follows:
Bias(fu, Str. CE) = (CE(fw) -CC Ste)l & ICE(f.) - CE(fz)) (CE(fz) ECE(Sw, Sto)l-
where the first term is called 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. We then evaluate these terms separately.
As for the first term, show that
- - - +E fx())
(16)
holds. Note that P(Y 1xfw(x)) = ff) holds for the binary classification. First, we can show that
CE(ft) CE(Fw),
15

---

PAC-Bayes Analysis for Recalibration in Classification
by Jensen inequality with respect to the conditional expectation. This has been proved in Proposition 3.3 in Kumar et al. (2019). Next, upper bound (w) as follows
CE(fw) E || fw (X)] fa
(. -x)
Σ - 4
Σ
+ - E II
(X) 1J ( E 1ill
( E E 4 (X) E I.]
(X) (X E 4. fx)(l)l E 4.),
=1
where the second term is CE(fz), we finished the proof of Eq. (16).
Then we can show that
L.
(C((f) CE(fI) & EE (Y - -
(17)
B B'
Liptiuiizzcomiinuittyy of the function and the fact that we split the function with equal width 1/B. Now, where we used the Lipschitz continuity we have
E,((E().) ECE(S S,,) S E, CE())) CE( E, CE((f)) ECE(S Str)
L 1 E,/CE(/Z)) ECE(Sw;; S.:)),
B
B
We will bound the second term. For this purpose, we use Theorem in Appendix B.4, this concludes the proof for the binary setting.
Proof. MULTICLASS SETTING
Next, for the multiclass setting, similarly to the binary case, Similarly to the binary setting, we define the conditional expectation of fu given bins as f (x) = -E (Xf((X) E (.)))e.( With this definition, we decompose the estimation bias as follows:
Bias(fa, Su. TCE) = [TCE(fw) ECE(f Swe)l & (TCE(f)) T(E()))((((+))))() (TCE()) - ECE(f Ste)l.
As for the multiclass setting, similarly the binary case, we have
[CCEff)) ECE(S St)) (TC((f)) TCE(A2) ( (CCC((/))-ECC((...... Str)l-
(18)
Then similarly to Eq. (16) in the binary classification, we can show that
[TCE(Fw) S Clf, P(Y -1
16

---

PAC-Bayes Analysis for Recalibration in Classification
by the almost identical proof. We then upper-bound them
L B
(CE(S") - & C)sx(X))) - P(Y BXxX
using the Lipschitz continuttt and the property of the binning. We substitute this into Eq. (18), we have
(C ECE(fM;
- Ep (CE(()) - TCE(S=) + (C/TCE(/T) ECE(Sw, Str)
L 1
$ B -E/TCCE(f) ECE(F S..)
Then using Theorem 6 in Appendix B.4 for the second term, this concludes the proof.
B.4. Auxiliary result about the statistical bias
Here present the auxiliary result, which is used in Appendix B.3.
First, we introduce the assumption, which is used in existing analysis Gupta and Ramdas (2021) and not necessarily in our proof:
Assumption 3. Given W (x)e is absolutely continuous with respect the Lebesgue measure.
As for the binary setting, we assume that (ar) absolutely continuous with respect to the Lebesgue measure. This assumption means that fw has probability density, is satisfied without loss of generality elaborated in Appendix in Gupta and Ramdas (2021). Although this assumption is not required for main results, if we assume this, improve the coefficient of the upper bound. Thus in the below, provide the proof with and without this assumption simultaneously.
Thanks to this assumption, (X) takes distinct values almost surely, so for example, the situation when all training samples take the same predicted probability will be circumvented. When considering the multiclass setting with CEx, this property plays an important role eliminating the curse of dimensionality, see Appendix B.9.
Theorem 6. Assume that n. For both binary and multiclass settings, for any fixed prior which is independent of Str, and posterior distribution over W and any positive constant e E (0, 1) and > 0, with probability 1 - with respect to Stz. we have
E, CEE(f) ECE(fW, Sw.) KL(pI(>) + log 2 log _ + 2xa
(Binary classification),
X
E, TCE((Z) (CE(Jw,Su)) (L(p]T)) + B log 2 + log + 2x
(Multiclass classification)
Furthermore, addition the above assumption, when Assumption holds, we have
CE((E) St)) [L(p]|T) + B Blog + log 1 +
2n
(Binary classification),
X
(L(p) m) + B log 2 + log L
A² 2m
Ep TCE(fz) (CE(fw,Su]1
(Multiclass classifccation)
A
Proof. To simplify the notation, we express S.r as S in this proof.
17

---

PAC-Bayes Analysis for Recalibration in Classification
BINARY SETTING
To derive the PAC Bayes bound, we transform the loss using Eq. (12) and (13), we have
CE( - ECE(SW,S))
B
Σ
Ez (xi-(x)))) (fw(') (x)en. - Σ
Σ
(Ym fw((m)) Is
1m1
m==
<
Σ
Bz: Bx-=(X,09) [0'- - fw((')) [w
Σ (Ym fw(Xmm) (w((E)E
i=1
S
Σ
(z) Σ (m
(19)
72
m=1
where we used the triangle inequality ||a] [b|| < la - b) for the first inequality and set 1,(2) = (v - (-w((x)) (x)cel
We then evaluate the exponential moment as
E (CE EgRge' E
( (2/4((2)) En 4((m))
(20)
By setting S) = Ez(((Z²) - 1 have
B
Es II Ese E Io(i.S)
e Ass(.,S)
i=1
< Es II
e (ali.S)
+e -t((19))
i=1
< Es
Σ
E' (-1)"
(21)
Ub--,,
Σ
Ege E (-1)"
Ug=01
Σ
Ese B ( (E)()() (B2)l(())- Em ((Zm))
Up
where Eop is all the combinations that will be generated by expanding 11. in Eq. (21) and it has 2 combina- tions.
We would like to upper bound Ege' (E:) En... 4(2m)] using Lemma For that purpose, here we evaluate
18

---

PAC-Bayes Analysis for Recalibration in Classification
Gg of Lemma By focusing the exponent, we can estimate c;S
B Σt(-7
sup
11-1)
Ez.4(Z²)
4((2
fro Fr 3. E22
1=1
m=1
- - Ez:l((Z)) - Σ
4(((m)) (2(mm))
n
m3mm
B t( t(-1) 1-(((((e)) + 11 (1m(mm)
sup
am mm EZ i=1
t( 1) ( ((e'n' - I sw (e.))e))) +("m' - fw -fw((mm)) sw (hrt)))e)))
sup
#mm mm EZ
1-1)enn ( (Wi'n Sw (x'm)) (w(or))ess) + ((ām² (w((mm)) (((())))ls)
+
(22)
n
2t
1A
(23)
n
The last inequality is derived as follows: By definition the binning, each data point is assigned to exactly one bin. Consequently, for the input "'m., one indicator from the set {1 fw (ro("..))) e,, ) is non-zero, we denoted the corresponding index 6. Thus, L fmn('",, Jets + 0, and JE 0. A similar discussion applies to the input T,,' with the non-zero index denoted b, indicating 1 fw different. Therefore, although Eq. (22) contains 2B indicator functions, most only two non-zero.
0 and fm,(= (aaee,"))E JE 0. Note that b and can be either identical or
Combined with the fact that Iy'n fo (x'm:)) ) S 1, we obtain Eq. (23). Note that by Assumption 3, {f (Fmm } } in Im E S takes the distinct values almost surely and in the above discussion, we do not consider the case when b/ B fw (xm) for some holds, which means that the predicted probability is just the value the boundary of bins.
Combined with Lemma 1, we have that
Ese ER 1901,
Σ
Il
Ez e¹ 1E [Bgrl((")) - Em., 4(22)) [
VinnMB=0, m=l
Σ
(8)))))(2)
M1..,9=0,11
2
When we do not assume that Assumption 3, there may be possibility that b/B = (2m) for some holds, which means that the predicted probability just the value of the boundary of bins. Then Eq. (22), most only four indicator functions zero. This results in worse bound
1((-1)"
(z)
Σ k(()))
sup
-
[zm F. EZ 1=1
m=1
+(-1))
Ezz((Z')
Σ mom
(((m))))) 1
((mm.)
4t <
n
and results in
Eset Σe lo(,
Σ
II
Ez c En ((Z)))
2 23820 222
<
ug 0,1 m=1
19

---

PAC-Bayes Analysis for Recalibration in Classification
We define the upper bound of the exponential moment
f(t = log 2n 21a n log 2 e
without Assumption 3, with Assumption 3.
(24)
From Eq. (20), for any have
(25)
Then we take the expectation with respect to the prior
E, BC <
Using the Fubini theorem, we change the order of expectations,
EsEx [ S
and use the Donsker-Varadiee lemma, have
Es pe F,((CR())) (CC s 1.
where P(W) be the set of all probability distributions on W.
By using the Markov inequality with Chernoff-bounding technique, we have
sup E,((E(())) - ECE(/w, (L(p]T PEP(W)
- s(t,n) > log Se.
By rearranging the inequality
(T((p]m) + [(,, n) log
3p P(W), CE())) ECE(fw,S)
S E.
(26)
By substituting Eq. (24) when without Assumption 3, we have
KL(pI(T) log 2 + 2xa + log 1
P 3p e P(W). B..,),EF EECE(fw,
S E.
MULTICLASS SETTING
As for the ECE of the multiclass setting, from Eq. (14) and Eq. (15), we can proceed the proof exactly the same way the binary setting, By using the triangular inequality similarly to Eq. (19) and setting (()) = (LY=C - (X))c) (X)ce..
we have
B
(CE(f))) ECE(Se, S
Σ Ez-D4(Z) - EEzss ((Z))
By using McDiarmid's inequality to evaluate the exponential moment, we obtain
Es e (CB S3) < EE E (2m00 1(12) 2B 222
Then by using the Fubini theorem and Donsker- Valadhan inequality as in the case of the binary classification, we get the bound.
20

---

PAC-Bayes Analysis for Recalibration in Classification
B.5. Proof of Theorem (Total bias analysis)
Now we present the proof of Theorem 1. The proof almost identical to that of Theorem shown in Appendix B.3.
To analyze the bias caused by binning, following Futami and Fujisawa (2024), define the conditional expectation of fw given bins as f (a:) == Ei= (X)x(()) e 7:) fu())oEE, With this definition, we decompose the estimation bias as follows:
wf) ECE( S.o)1 S (TCE(FW) TCE(SE) (C)( -CC(( Ste)l-
where the first term is called 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. We then evaluate these terms separately.
As for the binning bias, using Assumption 1, it can be bounded by (1 L)BB because prepared bins divide the interval [0, into equal widths.
Next, we evaluate the statistical bias. We first derive the following reformulation:
BCE(fa,, - Σ (4= fw())c) (x)ceel
where Es.. the empirical expectation Ste. This reformulation derived Eq. (14). As for the TCE, we get a similar relation from Eq. (15).
By using the triangular inequality similarly to Eq. (19) and setting 4(Z) c 1 (x have
B
TCE(f.) ECE(S,, Str) S
Σ Ezzpli - 4z~5,,((2)
(27)
By using McDiarmid's inequality evaluate the exponential moment of Eq. (27), obtain
Es, e
< 2 "
22
for any (see Eq. (24)). Combining this result with the Markov inequality, we can upper bound the statistical bias.
B.6. Generalization of the ECE under the training dataset
Here we show the generalization error bound for the ECE, which is useful when analyzing the recalibration algorithm. Theorem 7. Assume that Tiee Thr n. For both binary and multiclass settings, for any fixed prior n, which independent of Se., and posterior distribution over W and any positive constant (0, and X >> O, with probability 1 with respect to St, we have
KL(p]T) + B log 2 + log + 422
E, Es. ECE(fw. Sic) ECE(fw,Su))
When Assumption 3 holds, we have
(T(pl(T) + B log log 1 + X² n
Es ECE(Sw, ECE(Sw, S..) S
Proof. To derive the PAC Bayes bound, we transform the loss
Es,. ECE(JW, Sie) - ECE(JW, Sax)
B
B
Es..
1
[(Y - (X))) (x)cn))
Σ
Σ (X.Y)
-Y (w-(w(X)) (
1=1
(X.
B
Es...
Σ 4(Z) Σ (())
1=1
ZES
ZES
21

---

PAC-Bayes Analysis for Recalibration in Classification
where used the triangle inequality ||a] - |b|l < b) for the first inequality and set 442) (yv-w(a)) (u(e)e
We then evaluate the exponential moment
E S e B (OBBS.....)-BB((/w....
- E, BB Eisil 2 Eses, 4(2)- EzEs, 1122)
S Br Es e Ehsi Ees,, 4(2) IZEs, 1.(2)
By setting g(i, Suc, Ste) = >1 - n - Zes, 4(Z), we have
Si e E' (1( S Ste Il
e ((.
B
II
(eo(i.Sun: + -to(iSSenne))
i=1
S Es 11m0,0=0011
Σ
c (-)"
(28)
Σ
Es
(-1"
Σ
Es..
Eis (-1" Ezes, Ezze,,,, 4(2) Exes, 4(21]
U100,12=0,1
where E Em is all the combinations that will be generated by expanding I in Eq. (28) and it has 2 combina- tions.
E (-)" Ezes, 1122) Eze,, ((()) using Lemma For that purpose, here we evaluate 6; Lemma 1. We can upper bound it completely in the same way as Eq. (23). For that purpose, we [ Ezes,, 4(2) x Ezes,, 4(2)]. Note that S consists of 2n random
We would like to upper bound Es,, e
define Ste U Su. (()) == E variables. We remark that Es [S() 0 conditioned w, thus, it satisfies the condition of Lemma 1. Then We define S' in which we replace single S with 2m E Z. Then with Assumption 3, we have
sup ((S) 3(S") = 21 8 E2
(29)
which is followed by discussion in Eq. (23). Differently from Eq. (23), there exist 4B bins, but since only replace single data point Sm, as discussed in Eq. (23), only two indicator function is not zero. This results in the above upper bound.
Combined with Lemma 1, we have that
Ess En la(1.
Σ
BS.. Suo esS))
Σ
(8))))))))
=2e 2²
21 01.001
00
We can derive the upper bound without Assumption 3 in the same way Eqs. (24) and (29),
4
sup ū(S) 8(S") S,
Combined with Lemma 1, we have that
Es,, e Di 2..1 <
Σ
Es,, S.. ((S)
Σ
( (1)))(2n)()) = =2 422
Pi WB 0.1
21 P1 U2 0,1
In conclusion, we have
log 1og2 BBe 4t2 e
without Assumption 3,
f(t,n) =
(30)
log B 22
with Assumption 3.
22

---

PAC-Bayes Analysis for Recalibration in Classification
Then we can proceed the proof of PAC Bayesian bound in the same way Eq. (25) and repeat the same derivation. This concludes the proof.
As for the ECE of the multiclass setting, from Eq. (14) and Eq. (15), we can proceed the proof exactly the same way as the binary setting, which results in the same upper bound.
B.7. Limitation under the Hölder continuity
Here we discuss the assumption of Lipschitz continuity. It is known that by assuming the higher order smoothness, such as the H-Hölder continuity, the bias of the nonparametric estimation decreases (Tsybakov, 2008), particularly, the lower bound (
However, in the binning scheme, we cannot improve the optimal order from O(n-1/3) due to the binning bias. This is because that in Eq. (17), which is appearing the proof of the estimation bias, there is the error term fl (X) (X)) This term is upper bounded by 1/B since we consider that the bins are allocated with equal width. Thus, we cannot improve the estimation bias order owing to this error term, which remains 1/ B even under the Hölder continuity assumption. Thus, the binning method cannot utilize the smoothness the underlying data distribution.
B.8. Proof of Theorem (Bias for the multiclass setting)
The upper bound can be derived similarly to the binary classification setting in Appendix B.3; 1) we first transform the EC and CEK. 2) decompose the estimation bias to the generalization and binning bias, 3) bound those two terms using the generalization error analysis and the binning definitions.
In this section, we express the distance ||
||2 of R as simplify the notation.
ECE TRANSFORMATION
Recall the definition
B
ECEx (Jws Sc) = Σ PillJi.ss Di.s.ll
where 41
Em (r.m)e P
/1//ner fr.s.
H Em 1 (ru and Pts.
1
E'e L fo (1m)) Sym-
T.
Using this definition, we first derive the ECE transformation; for the ECEx under the training dataset, we have
B [
B (x. - far (X)) 1 (m..)
ECEx (fw, S1)
Σ
If..s..
-r..s
Σ
(31)
im1
Next, we define the conditional expectation as
fz(z)
Σ (z
[x)ee,
Σ Elfa (X)lff() - (x)(e)
Then by repeating the exactly same proof for Eq. (13), the following relation holds
B
CEx(Fz) = Σ | - (x)) f..eellll---
(32)
Again, we consider the following decomposition for the estimation bias
ICEx ECEx (fw, Su)l JCEx (fw) CE (fx)) ICEx (fz) ECEx
(33)
We then separately upper bound the above two terms.
23

---

PAC-Bayes Analysis for Recalibration in Classification
GENERALIZATION OF ECE
First we focus on the second term, |CEx ECE& (Sw, St)) and we upper bound by the PAC Bayes bound:
Theorem Assume that (x) has the probability density over [0, 1] Then for any fixed prior a, which is independent of St. and posterior distribution over W and any positive constant [0, 1] and X > with probability with respect Sto have
<L(p] + BK log + log 1 + K2 2n
Bp (Fz FCCE St)l
X
Proof. The proof strategy almost identical to the TCE.
First, transform the generalization gap by using Eqs. (31) and (32). First note that
CFx(SI) = Σ
(onp)oooy--u(X (xyen,
and
ECEx Str)= Σ
(xxx)))3,, (m 1 I (xm)Ez
Thus, we have
ICE ECEx (F Stx)
B
B - Sw(()) f [R (x.) -
Σ
- (Bxx.))D(ey-Suul
so)ee Σ
B
Σ
(xxx))))((()- - 4(2)
ZEStr
where used the triangle inequality ||a||-I|b|| s a-blll for the first incquality and set (1z) (ew-f((x))) (X)er We then evaluate the exponential moment follows;
ES E (CCB (sw.S)) E, Es. e EE (xx)) Exesy 4(2)/|
Es, Es E ER (oxx)) Ezer, 4(%)a
where ((())& the k-th dimension of 12)2.
By setting g(i, k S.r) = E24(()xx - Ezes, 1<(Z),, have
Es, e. Ei. ΣK 1o(1,k,uu) Es..
i= 1=1
Es..
En EX
Es.
Σ
Es Ee K (-
0.1
Σ
Es (- - 4(2).)
24

---

PAC-Bayes Analysis for Recalibration in Classification
BK in Eq. (28) and it has 2 where Σ 00=00 is all the combinations that will be generated by expanding [
combinations.
We would like to upper bound the exponential moment using Lemma 1. For that purpose, here we evaluate 6; of Lemma 1. We can upper-bound it completely in the same way as the binary case. Then with Assumption that (x) is absolutely continuous, Ja (a: takes the distinct values almost surely. Thus, we have
B K
1 T2
sup {am mm B.
ΣΣt(T))
Ezi4(Z')
Σ
4(
)R
1 ((mm)) 7
1(-1))
(2 n
1 (=
B
K
t( ((-1))
[-1(((me)) )2 + (e(2m)al
sup
zmn mm! E2
n
i=1
Am1
K
( (((ex)('n - f (m)))))) fwie twid DeN) + ((ier Sw (Fm)))))) s ( (wr ((-1)0:
sup
z/ Fmm E2
k=1
f(-1)En
(
(-(((e))nn You. Sw (x) 1 (w (e( + (fmr, fk (Tm)m)) (w(e
(34)
K
21
2KL
n
which is followed by discussion in Eq. (23). Combined with Lemma 1, we have that
Ess e El EKs lo().S)))
Σ PLI..WBK=0.1
(8)8)() = 2 E =m
(35)
Thus, the exponential moment is upper-bounded and define
[(I,n) = 2K x²,2
We then repeat the Chernoff-bounding technique of the proof of the PAC-Bayes bound derivation, and substitute [tt, n) into Eq. (26), we have the following PAC-Bayes bound; for any prior and posterior distribution P over W and any positive constant [0, 1] and A > 0, with probability 1 with respect to Str. we have
E,ICEx(fz) -CCEE Sw)l KL(pI(T) BK log 2 + log
K
2m
(36)
BIAS ANALYSIS OF THE BINNING METHOD
Next, we upper bound (CEx(fw) - CEx((Z)) which is the first term of Eq. (33). By repeating exactly the same procedure in Eq. (16), we can show that
ICE CE (fz) < Bley (X)] Eley Ifz [f
(X)]II
El]fu +
(x))
We can bound them using the definition of the binning construction; recall that in the current binning construction, we split each dimension of [o, 1) with B' bins with equal width. Thus [., fz(X)&| S 1/B' for all & e [K]. This implies that
La (X)x {x()xN) < K
EII - fx(XI < E
B
1=1
25

---

PAC-Bayes Analysis for Recalibration in Classification
Then the fact that B (B*)K, have that
K
B
B
Using the Lipschitz continuity for the first, we have
(CEx(fu) - (Ex(fz)) - E|jEeey [X)] - Eley BIL - fx(X)
KL K
K(1+1) L)
(37)
B'
B
B
CONCLUSION
Finally, taking the expectation by p in Eq. (33), we upper bound the first and second term using Eq. (37) and Eq. (36), we obtain the theorem.
As for the total bias
Bias([ws Ste, CEx) = |CEx (Sro) ECEx (Jws Sto)
We can derive this using the above generalization bound for E, (Jz)) ECEx Ser) similarly to the derivation in Appendix B.5. The result is simply dropping the KL term in Eq. (36) and obtain the order Bias(fw> Ste CEx)
(1//ne (1// +2) under = O(nie
B.9. Discussion about the assumption of Theorem 3
In Theorem 3, we assumed that fm (z) has the probability density in [o, 1]K In the binary classification and TCE analysis, this assumption is not required, and we assume this, our bound results in the improvement of the coefficient, not affect the order of the bound.
On the other hand, when considering the generalization of ECEx, this assumption is inevitable circumvent the curse of dimensionality especially in the generalization error analysis. Here discuss how Theorem 3 changes when eliminating this assumption. If we do not assume this assumption, in the proof of Theorem 3, the exponential moment is replaced to
Es, c Eis EK (0().S.))
Σ
(1/8)(n)
2k(2
= 2BK A x2,
which is the surprisingly worse upper bound compared with the upper bound of the exponential moment shown in Eq. (35) with the assumption. Then the obtained PAC Bayesian bound becomes
E Cx - ECCE (fw, S.)) KL(pI<>) + BK log 2 log 1 4k x²²
2n
X
which has the new coefficient 4 and is significantly larger than that Theorem 3.
This is caused by the evaluation of the coefficient of the Lemma 1. the derivation of Eq. (34), if we do assume that f.r has the probability density, then there is possibility that the training data is allocated to the point the exact grid points of the hypercube constructed by the bins. The grid point is the intersection of 2 small regions, and thus, the c,s of Lemma I becomes exponentially large. Owing to this, the coefficient of Eq. (34) is significantly larger compared with the setting when we assume that fw has the probability density, where we do not need to consider such a worst case. In this way, the order of the bias significantly improves by assuming that fio has the probability density.
1. Discussion about the selected labels for the ECE
Here we consider the setting that we only focuses on K' E [1, K] classes. Without loss of generality, we focus on the set of labels defined as (0. (O...., K' - 1}. We then define (x) = (f.( (x))) We also regard P(Y = 0 0l (lf((() (X))..... PP.............................. = K' (X)) as the K' dimensional vector given w and æ. We also define the one-hot vector oy = ((ey),,-. (e:) where (ey ) is the k-the element of ey.
26

---

PAC-Bayes Analysis for Recalibration in Classification
Under these notations, we can define
CE (
where 11p is the L distance in RRK The CEg' metric measures the calibration performance of models for only K" classes.
Let us consider the following binning scheme to estimate CEg'. Since we want to estimate the K" -'-dimensio conditional probability in [0, 1] by binning, we split each dimension [0, 1] into B' bins of the same width. After doing so, there are B K bins, and [o, 1|K is split into B small regions. We refer these regions I = (T)) In this case, the ECE of CEx can be defined as
ECE (fu, Se) = Dillfi.s P1
where [/| = Em= 1 (LL) Pr = [il//ne P....
[ Em= 1 (e and Pis. =
T. Em= 1 1 (em)))) v...
For these definitions, we can derive the following bias
Bias( Ste, CF (fw) RCE (Swe (fw; Stc)l
and this can be analyzed exactly in the same way as Appendix B.8. Then we have Bias(sw Sea, CEK:) = O(1/nee ((1/12/(x(+2) We can obtain the similar generalization bound.
under B = Ore x7
C. Proofs and discussion of Section 4
We remark that recalibration takes fл : A - K and this clear for the multiclass setting since fw : X A In the case of the binary setting, fn X' - [0, 1]. So, consider that the input n) is (f) fm( E A Then treat the recalibration in unified way.
C.1. Proofs for Corollary and
When we recalibrate the model, fix w. Thus under the swr the given recalibration data S.c {(Xm, Fre) is transformed into S.e (X Vn))i and samples in S.e are i.i.d by definition. Then apply our developed PAC-Bayes bounds in Appendix B for this new dataset.
As for Corollary 1, we can prove it exactly in the same way as shown in Appendix B.6. Simply replacing Sur with Sie in Appendix B.6 and apply to the standard derivation of PAC-B MAC-Byaeisan bound shown in Eq. (25). This concludes the proof.
As for Corollary 2, we first provide the complete statement;
Corollary 3. Assume that The Nue n. Under Assumption conditioned on W w. for any fixed prior which independent of Sre, and posterior distribution over V and any positive constant E [0, 1] and X > 0, with probability 1 with respect to Sre, have
KL(P + B Bogg 2 + log + 22²
1+ L
E. BiBissnn Swo Stc, CF.) S
KT(()) + B log 2 + log + 2x²
1 1 L
Eg Bias(n Swo Ste, TCE)
B
We can prove this exactly in the same way as shown in Appendix B.3. Simply replacing S., with Sie in Appendix B.3. This concludes the proof.
C.2. Discussion about the conditional KL divergence
In Corollary and 2, we fixed w. If we take the expectation with respect to W, then the bound of Corollary become as follows;
27

---

PAC-Bayes Analysis for Recalibration in Classification
Corollary 4. Assume that nhe nhe nt, Under Assumption conditioned Sir Ser, for any fixed prior which independent of Ste, and posterior distribution ( over V and any positive constant e E [0, 1] and X >> 0, with probability 1 with respect to Sye, have
(s)) ) Bagen(n. o fws Ste. ECE) Bp(l)as)) [L(p]T) + log 2 log 4A
À
where EE ((tt))..)) ( [KL( represents the conditional KL divergence.
Proof. The proof is almost the same Appendix B.6. The difference is how utilize the Chernoffboundding technique. Here we only show the different parts, After obtaining the upper bound of the exponential moment ft, Azee) as in Eq. (30), we substitute this into Eq. (25), which can be written as follows; for any to and we have
Es (ECE(n Sto) F f(t.m.)) S 1.
Then we take the expectation with respect to the prior ग and p(w)su),
pp(l)) Ex Es.
Using the Fubini theorem, we change the order of expectations,
) Ea
S1.
and p(w]ssr) and Sre are independent thus
Es EE p( Ea
S1.
Then, use the Donsker- Varadhan lemma, we have
Es, Bp(wlee))
[| f(t S1.
By taking the Jensen inequality, we have
Es.-
swp
< Es., (p(
s(t,nz))) $ 1.
By taking the swap about E. B((w)).) and sup, we have
Ss.. e (uPper Sar
f(t,m
S..) -CC((, Es.. ( S"PAE Bs (L(()))) - s(trrre) -
After this, we simply follow the derivation of the standard PAC-Bayes derivation in Appendix B.3.
C.3. Discussion for Section 4.2
First, the upper bound of the ECE is obtained by
Phe
1
The
ECE(1 fwo S,e)
(er)c- - TV fm
ley TV fx)]1
Thre
The
(X,Y)S,,
(X,Y)ES,.
where (cy )c the C-th dimension of the one-hot encoding of the label Y and the first inequality is followed by Hölder inequality and the Jensen inequality. As for the binary classification, by Hölder inequality and Jensen inequality, we have
Pre
ECE(1o o fwo Soo) < Thre (X,
Y my (X)1
28

---

PAC-Bayes Analysis for Recalibration in Classification
since the recalibrated function "y Iw (X) A² and its 1st dimension represents the predicted probability of the label is Then from the estimation bias bound in Eq. (7), we have
B2 TCE( fw)
s RR SwoSeo + 1+ L
KL(PI()
+ B log 2 + log _
1AA
+
B
A
1+ L
(T(p)=)
B Blgg log 1
41 Pre
$ E Tue (X,,)
|er - fo (
+
(38)
B
A
holds for any À > O. Thus, the objective function of Eq. (8) is the upper bound of the TCE the PAC-Bayes bound. Clearly, similar statement holds for CE in the binary setting.
Next, we discuss the objective function of Eq. (10). This objective function can guarantee the performance of test accuracy and TCE simultaneously follows; Assume that lace y x [0, 1] and define the training loss Lace(V (V,Su) Su) = The (X.Y)SS. lace (Y, Ny (X)) and the (expected) test loss as (uc D) == Ezlace(Y, (Y, nV fxo())) Under this
setting, we have
Corollary 5. Assume that The The n and Under Assumption 2, conditioned on W = for any fixed prior ã, which is independent of Ste, and posterior distribution p over and any positive constant e E [0. 1] and X >> O, with probability
1 with respect to Sre, we have
1
Thro
PE (V,D) TCE(1 Sw) S Rp
Σ
(Jaze (aaceY,, (Y, m/ Sw(()) + lley By o fuo (x)
Thre
(X,Y)ES,e
1 T.
2KL(P + B logg + 332²
Site + 22
+
B
Proof. From Eq. (11), which the standard PAC-Bayes bound for [0, 1] bounded loss function, we have
La (V, < L.L. Lac (V,S + KL(ĀI(F log 1 +
A
Smie.
(39)
By considering the union bound with Eq. (39) and Eq. (38), setting as E/2 in each high probability bound, we obtain the result.
Clearly, a similar statement holds for CE in the binary setting.
Thus, the objective function Eq. (10) optimizes the upper bound Corollary 5, and thus, it naturally guarantees the test accuracy and TCE simultaneously.
29

---

PAC-Bayes Analysis for Recalibration in Classification
Table 2. Datasets used in experiments
Dataset
Classes
Train data (ntz
Recalibration data (Nue)
Test data (nue)
KITTI (Geiger, 2012)
16000
1000
8000
PCam (Veeling et al., 2018)
22768
1000
9000
MNIST (LeCun al., 1989)
10
60000
1000
9000
CIFAR-100 (Krizhevsky, 2009)
100
50000
1000
9000
D. Details of experimental settings
In this section, summarize the detail information of our numerical experiments in Section 6. Our CIFAR-100 experiments were conducted on NVIDIA GPUs with 32GB memory (NVIDIA DGX-1 with Tesla V100 and DGX-2). For the other experiments, we used CPU (Apple M1) with 16GB memory.
Datasets and models: We show the details of the datasets and the numbers of training, recalibration, and test data in Table 2. For the models, we used XGBoost (Chen and Guestrin, 2016), Random Forests (Breiman, 2001), and a 1-layer neural network (NN) for the KITTI, PCam, and MNIST experiments. For the CIFAR-I00 experiments, we used AlexNet (Krizhevsky et al., 2012), WideResNet (Zagoruyko and Komodakis, 2016), DenseNet-BC-190 (Huang et al., 2017), and ResNeXt--9 (Xie al., 2017). XGBoost, Random Forests, and the 1-layer NN were trained by adapting the code from Wenger et al. (2020) !. Models used in the CIFAR-100 100 experiments were obtained from the GitHub project page: (https: //ggtttthbbb//g/////.////gg.bbbt com http://aaaawptttrreaeee class insiifiiitoooo
Recalibration algorithms: In the multiclass classification experiments, the standard method of temperature scaling (Guo et al., 2017) and the recently developed GP calibration (Wenger et al., 2020) that has shown good performance were used as baselines. As baseline method for binary classification, we additionally adopted Platt scaling (Platt, 1999), isotonic regression (Zadrozny and Elkan, 2002), Beta calibration (Kull et al., 2017), and Bayesian binning into quantiles (BBQ) (Naeini et al., 2015). We also adopted the GP calibration with mean approximation (Wenger al., 2020) in the additional experiments in Appendix E.
Wenger et al. (2020) reported results for Platt scaling (Platt, 1999), isotonic regression (Zadrozny and Elkan, 2002), Beta calibration (Kull et al., 2017), and Bayesian binning into quantiles (BBQ) (Naeini et al., 2015), which were originally developed for binary classification tasks and adapted to the multiclass setting via a one-vs-all approach. However, for fair comparison, our multiclass classification experiments employed temperature scaling and GP-based recalibration as baseline methods, these approaches be directly applied the multiclass setting.
For our PBR method, we set the Gaussian distribution as both the posterior and prior, as in Wenger et al. (2020). We also followed the settings for training strategy, hyperparameters, and optimizers in Wenger et al. (2020) to ensure fair comparison. PBR has an optimizable parameter 1/A in addition to the posterior parameter; thus, we selected it using grid search from the following candidates: {0., 0.01, 0.1, 0.25, 0.5, 0.75, 0.9, 1.0]. The mean approximation strategy in Wenger al. (2020) can be applied for PBR. Thus, we reported the results of PBR with mean approximation (denoted as PBR app.) in Appendix E.
1/3 Performance evaluation: We measured the predictive accuracy and the ECE estimated by binning, with = [ following our theoretical findings Corollary 2. We conducted 10-fold cross volssvvaio for recalibration function training and reported the mean and standard deviation of these two performance metries. We also used J 100 Monte Carlo samples from posterior f to obtain V.
E. Additional experimental results
Here are additional experimental results that could not be included in the main part of this paper.
We first show all the experimental results regarding the correlation between the KI--divergence and our bound in Figures and 4. We observed that the KL-divergence and generalization gap are well correlated in terms of Pearson's 's and Kendall's
hhttps://gt thub. com
30

---

PAC-Bayes Analysis for Recalibration in Classification
rank-correlation coefficients, especially in the multiclass classification tasks (MNIST and CIFAR-100). However, for the binary classification experiments, strong correlation was observed. We conjecture that this is caused by the estimation bias of ECE through binning, which has a very slow convergence rate of O(nre under our optimal B. Since we use Nye = 1000, the noise due to the estimation bias can be (11/10), which is larger than the ECE gap values in the binary classification experiments. Therefore, it seems that the correlation is buried in the noise.
We also show the results of comparisons with all baseline methods in Tables 3-6. These results confirm that our method almost consistently improves GP-hased recalibration methods.
Finally, we evaluate the effect of using Brier and cross-entropy losses in our recalibration approach defined in Eq. (9). Specifically, we reran the experiments under the same setup described in Appendix D, and re-evaluated our two methods from Eqs. (8) and (9) in terms of ECE, classification accuracy, and cross-entropy loss.
The results summarized in Tables 7-10. Our first key observation is that both of our methods-PPR and PBR total- consistently improve ECE when minimizing the Brier score. This is expected, the Brier score upper-bounds ECE. We also observe improvements in accuracy and cross-entropy in some settings, particularly for binary classification tasks on relatively simple datasets such as KITTI and PCam.
However, when recalibration is performed using only the Brier score (with KL regularization), PBR can lead to degradation in both cross-entropy and accuracy, especially for more complex datasets and multi-class tasks. This trend is evident in Table 9 (excluding the XGBoost and Random Forest settings) and Table 10 (excluding AlexNet), and particularly pronounced in experiments involving deep neural networks.
One possible explanation is as follows: in all experiments, the base models fw were trained using the cross-entropy loss. When recalibration is subsequently performed using only the Brier score, the optimization objective diverges from the training objective. This mismatch can propagate through the GP-based recalibration process, introducing inconsistencies that ultimately degrade performance in terms of accuracy and cross-entropy. Notably, this degradation alleviated by incorporating the cross-entropy loss into the recalibration objective, as done in PBR total. This suggests that including cross-entropy helps reduce the misalignment between training and recalibration losses.
In summary, minimizing the Brier score alone does not necessarily improve cross-entropy accuracy and may in fact worsen them. However, incorporating cross-entropy into the recalibration objective offers more balanced trade-off, improving calibration while preserving predictive performance.
31

---

PAC-Bayes Analysis for Recalibration in Classification
Dataset- KITTI Modd-XXBBost
Detaset-KOTTI
Dataset-KITTI Mlyee=
0.012
0.030
9.032
0.028
0.008
+
ECE. gap
0.026
0,300
0,000
0.032
9.002
0.030
Kefdallls 0.0000 Pearson's
-0.00
Kendall's == Pearson's
0.20
0.000
Kendallls 0.03
son's
20
60
60
69
30
10
6o
70
10
20
25
PCaa Model=XGBoost
PCaam Modill random forest
Dataset=PCam Modal- 1layer NN
0.020
ECE Gap
0.01
0.0022
0.1
0.010
0.5
0.75
0.025
1.0
0.020
Pearson's r= 0.00
Pearson's rm 0.03
-6.03
Pearson's r 0.09
200
250
2002
5900:
Dataset= MNIST Model=
Ustaset=NNIS) Modelcrandom forest
Dataset=MMisi Model layerrNN
0.012
0.0200
0.020
ECE gap
0.0125
0.510
0.044
0.0015
0.0050
0.004
0.0025
Kihddal's T
0.08
Kendall's T= 0:30
Kendall's ==
0.29
1258
1500
1503
1800
2500
KL
KL
KL
Figure ECE gap on KITTI (binary), PCam (binary), and MNIST (Multiclass) dataset per various regularize parameters (a).
001
435
0.0
3/2
1m-022
040:00 311
Figure 4. KL vs ECE gap on CIFAR- 100 (Multiclass) dataset per various regularize parameters (a). For the AlexNet experiments, the x-axis range has been limited the figure better illustrate the data due the observation of very large KT. values for the case where 0.
0.300
XGBoost
2.54
randem forest
0.02
1layer NN
PBR (oun)
tours)
0.155
ape. (ours)
0.300
PBR app. total (ours)
Temperature scaling
scaling
Isotonic regression
3.52
0.00
Beta caibration
allbratioo
0.00
5.00
0.00
callbration (app.)
Dre
Die
nue
Figure 5, thn vs. ECE on the test dataset for experiments with the KITTI dataset. For details methods, we refer to Appendix D.
32

---

PAC-Bayes Analysis for Recalibration in Classification
Table KITTI (binary)
Model
Method
ECE (mean + sid)
Accuracy (mean + std)
Uncalibration
0.0113 = 0.0004
0.9627 = 0.0011
GP calibration (Wenger et al., 2020)
0.0063 + 0.0020
0,9633 + 0.0007
GP calibration (app.) (Wenger al., 2020)
0.0079 = 0.0033
0,9640 = 0.0013
PBR (ours)
0.0076 + 0.0030
0.9641 = 0.0014
PBR total (ours)
0.0063 = 0.0014
0.9636 + 0.0013
PBR app. (ours)
0.0079 + 0.0033
0.9640 + 0.0013
XGBoost
PBR app. total (ours)
0.0063 + 0.0012
0.9637 + 0.0013
Temperature scaling (Guo et al., 2017)
0.0060 +: 0.0009
0.9627 1 0.0011
Platt scaling (Platt, 1999)
0.0076 + 0.0014
0.9621 1 0.0011
Isotonic regression (Zadrozny and Elkan, 2002)
0.0093 + 0.0030
0.9624 + 0.0022
Beta calibration (Kull et al., 2017)
0.0052 + 0.0015
0.9627 + 0.0008
BBQ (Naeini et al., 2015)
0.0341 + 0.0745
0.9611 + 0.0021
Uncalibration
0.0736 + 0.0014
0.9638 + 0.0015
GP calibration (Wenger et al., 2020)
0.0070 + 0.0032
0.9628 + 0.0018
GP calibration (app.) (Wenger et al., 2020)
0.0074 + 0.0029
0.9626 = 0.0018
PBR (ours)
0.0076 = 0.0031
0.9626 = 0.0019
PBR total (ours)
0.0068 = 0.0033
0.9628 = 0.0018
PBR app. (ours)
0.0074 = 0.0029
0.9626 = 0.0018
Random Forest
PBR app. total (ours)
0.0068 + 0.0087
0.9628 = 0.0017
Temperature scaling (Guo et al., 2017)
0.0063 = 0.0029
0.9638 = 0.0015
Platt scaling (Platt, 1999)
0.0060 + 0.0031
0.9631 + 0.0017
Isotonic regression (Zadrozny and Elkan, 2002)
0.0097 + 0.0033
0.9612 + 0.0024
Beta calihration (Kull et al., 2017)
0.0063 + 0.0023
0.9627 + 0.0015
BBQ (Naeini et al., 2015)
0.1148 + 0.0538
0.8948 + 0.0026
Uncalibration
0.0049 + 0.0008
0.9619 + 0.0014
GP calibration (Wenger et al., 2020)
0.0047 + 0.0008
0.9619 + 0.0014
GP calibration (app.) (Wenger et al., 2020)
0.0047 + 0.000S
0.9620 + 0
PBR (ours)
0.0017 + 0.000S
0.9619 + 0.0013
PBR total (ours)
0.0046 + 0.0007
0.9621 + 0.0014
PBR app. (ours)
0.0047 + 0.0008
0.9619 + 0.0014
I-Layer NN
PBR app. total (ours)
0.0045 1 0.0008
0.9620 + 0.0014
Temperature scaling (Guo et al., 2017)
0.0104 + 0.0050
0.9618 1: 0.0014
Platt scaling (Platt, 1999)
0.0103 + 0.0049
0.9642 + 0.0016
Isotonic regression (Zadrozny and Elkan, 2002)
0.0085 + 0.0049
0.9672 + 0.0024
Beta calibration (Kull et al., 2017)
0.0073 + 0.0047
0.9672 + 0.0013
BBQ (Nacini et al., 2015)
0.0324 + 0.0760
0.9648 + 0.0051
XGBoost
3.00
random forest
1layer NN
PBR (ours)
PBR total tours)
0.23
3.05
0.20
app. (ours)
6.6
3.8
0.38
app. (ours)
Temperature staling
0:3
3.0
0.16
Platt staling
regression
Beta ca calbration
GP calibration
0.50
calibration lapp.)
Fre
Figure 6. The vs. ECE on the test dataset for experiments with the PCam dataset. For details on our methods, we refer to Appendix D.
33

---

PAC-Bayes Analysis for Recalibration in Classification
Table 4. PCam (binary)
Model
Method
ECE (mean std)
Accuracy (mean std)
Uncalibration
0.0519 + 0.0015
0.8445 = 0.0015
GP calibration (Wenger et al., 2020)
0.0122 = 0.0053
0,8466 + 0.0018
GP calibration (app.) (Wenger al., 2020)
0.0133 + 0.0057
0.8168 + 0.0021
PBR (ours)
0.0139 + 0.0043
0.8145 + 0.0030
PBR total (ours)
0.0113 + 0.0043
0.8161 +: 0.0024
PBR app. (ours)
0.0140 + 0.0042
0.8441 + 0.0028
XGBoost
PBR app. total (ours)
0.0116 + 0.0055
0.8449 1 0.0028
Temperature scaling (Guo et al., 2017)
0.0605 1 0.0048
0.8445 + 0.0015
Platt scaling (Platt, 1999)
0.0492 + 0.0057
0.8474 1: 0.0011
Isotonic regression (Zadrozny and Elkan, 2002)
0.0170 + 0.0053
0,8442 + 0.0031
Beta calibration (Kull et al., 2017)
0.0183 + 0.0019
0,8475 + 0.0012
BBQ (Nacini et al., 2015)
0.0143 + 0.0098
0.8412 + 0.0065
Uncalibration
0.0816 = 0.0014
0,8495 = 0.0018
GP calibration (Wenger et al., 2020)
0.0124 + 0.0027
0,8492 = 0.0019
GP calibration (app.) (Wenger al., 2020)
0.0115 = 0.0041
0.8491 = 0.0019
PBR (ours)
0.0109 + 0.0040
0.8490 = 0.0020
PBR total (ours)
0.0116 = 0.0068
0.8490 = 0.0019
PBR app. (ours)
0.0104 + 0.0038
0.8491 = 0.0020
Random Forest
PBR app. total (ours)
0.0116 + 0.0063
0.8489 + 0.0019
Temperature scaling (Guo ct al., 2017)
0.0092 + 0.0056
0.8495 + 0.0018
Platt scaling (Platt, 1999)
0.0096 1 0.0054
0.8496 +: 0.0014
Isotonic regression (Zadrozny and Elkan, 2002)
0.0202 1 0.0085
0.8464 + 0.0038
Beta calibration (Kull et al., 2017)
0.0122 + 0.0036
0.8488 + 0.0024
BBQ (Naeini et al., 2015)
0.0529 + 0.0079
0.8063 = 0.0082
Uncalibration
0.2060 + 0.0014
0.5928 + 0.0016
GP calibration (Wenger et al., 2020)
0.0385 + 0.0073
0.6510 + 0.0021
GP calibration (app.) (Wenger al., 2020)
0.0389 + 0.0057
0.6507 + 0.0023
PBR (ours)
0.0385 + 0.0073
0.6507 + 0.0020
PBR total (ours)
0.0384 +:2 0.0060
0.6497 1: 0.0034
PBR app. (ours)
0.0885 = 0.0073
0.6507 = 0.0021
L-Layer NN
PBR app. total (ours)
0.0389 = 0.0057
0.6507 + 0.0023
Temperature scaling (Guo et al., 2017)
0.0812 + 0.0169
0.5928 + 0.0016
Platt scaling (Platt, 1999)
0.0484 + 0.0105
0.6224 + 0.0068
Isotonic regression (Zadrozny and Elkan, 2002)
0.0214 + 0.0055
0.6483 + 0.0026
Beta calibration (Kull et al., 2017)
0.0256 + 0.0044
0.6478 + 0.0026
BBQ (Nacini et al., 2015)
0.0179 + 0.0029
0.6467 + 0.0039
XGBoost
random forest
1layer NN
0.008
0.04
0.020
PBR (ours)
0.06
0.3
0.015
PBR total (ours)
PBR app. (ours)
ECE
0.004
0.02
0.010
PBR app. total (ours)
Temperature scaling
0.002
0.01
0.005
GP calibration
GP calibration (app.)
0.000
1000
0.00
150
0.000
Tree
fie
fiee
Figure The vs. ECE on the dataset for experiments with the MNIST dataset. For details our methods, refer Appendix D.
34

---

PAC-Bayes Analysis for Recalibration in Classification
Table 5. MNIST (Multiclass)
Model
Method
ECE (mean + std)
Accuracy (mean + std)
Uncalibration
0.0036 + 0.0003
0.9785 = 0.0005
GP calibration (Wenger et al., 2020)
0.0038 + 0.0006
0.9786 = 0.0007
GP calibration (app.) (Wenger al., 2020)
0.0040 + 0.0004
0.9785 = 0.0007
PBR (ours)
0.0035 + 0.0004
0.9785 = 0.0007
XGBoost
PBR total (ours)
0.0037 1: 0.0004
0.9785 0.0006
PBR app. (ours)
0.0036 +: 0.0003
0.9785 1 0.0005
PBR app. total (ours)
0.0036 + 0.0004
0.9785 0.0005
Temperature scaling (Guo et al., 2017)
0.0055 +: 0.0017
0.9785 +: 0.0005
Uncalibration
0.1428 + 0.0007
0.9659 + 0.0005
GP calihration (Wenger et al., 2020)
0.0313 + 0.0056
0.9663 + 0.0011
calibration (app.) (Wenger al., 2020)
0.0091 + 0.0046
0.9641 + 0.0016
PBR (ours)
0.0065 + 0.0017
0.9639 + 0.0018
Random Forest
PBR total (ours)
0.0057 +: 0.0028
0.9656 0.0017
PBR app. (ours)
0.0091 + 0.0046
0.9641 = 0.0016
PBR app. total (ours)
0.0045 + 0.0020
0.9662 0.0016
Temperature scaling (Guo et al., 2017)
0.0062 + 0.0009
0.9659 = 0.0005
Uncalibration
0.0164 1: 0.0004
0.9760 0.0005
GP calibration (Wenger et al., 2020)
0.0101 1: 0.0023
0.9740 + 0.0008
calibration (app.) (Wenger al., 2020)
0.0159 + 0.0007
0.9760 0.0006
PBR (ours)
0.0137 + 0.0014
0.9751 + 0.0009
1-Layer NN
PBR total (ours)
0.0112 + 0.0019
0.9740 0.0016
PBR app. (ours)
0,0159 + 0.0007
0.9760 + 0.0006
PBR app. total (ours)
0.0148 + 0.0017
0.9742 + 0.0015
Temperature scaling (Guo et al., 2017)
0.0062 + 0.0026
0.9760 + 0.0005
alexnet
WAN-28-10-drop
resnext-Bx61d
0.6
resnext-16x544
densenet-bc-1190400
0.25
(ouns
6.35
PBR total toursi
0.55
6.34
PBR tours)
apo: (ours)
0.00
Temperature scaling
0.22
0.5
GP ca calibration
calibrationn lapp.)
6:00
631
642
Pre
Figure 8,
ECE the test dataset for experiments with the CIFAR- 100 dataset. For details methods, refer Appendix D.
35

---

PAC-Bayes Analysis for Recalibration in Classification
Table 6. CIFARIO0 (Multiclass)
Model
Method
ECE (mean std)
Accuracy (mean std)
Uncalibration
0.2548 0.0007
0.4374 0.0008
GP calibration (Wenger et al., 2020)
0.2548 + 0.0008
0.4373 0.0009
GP calibration (app.) (Wenger et al., 2020)
0.2548 + 0.0007
0.4374 0.0008
PBR (ours)
0.2545 + 0.0007
0.4374 + 0.0008
alexnet
PBR total (ours)
0.2548 0.0008
0.4373 0.0009
PBR app. (ours)
0.2548 1: 0.0007
0.4374 +: 0.0008
PBR app. total (ours)
0.2548 0.0008
0.4374 0.0008
Temperature scaling (Guo et al.. 2017)
0.0216 +: 0.0037
0.4374 + 0.0008
Uncalibration
0.0568 0.0009
0.8131 0.0011
GP calibration (Wenger et al., 2020)
0.0567 + 0.0010
0.8129 + 0.0011
GP calihration (app.) (Wenger et al., 2020)
0.0568 0.0009
0.8130 0.0011
PBR (ours)
0.0501 + 0.0054
0.7878 0.0049
WRN-28- WRN-28-10-droo 10-drop
PBR total (ours)
0.0349 0.0093
0.7965 0.0064
PBR app. (ours)
0.0568 + 0.0009
0.8130 = 0.0012
PBR app. total (ours)
0.0568 0.0009
0.8130 0.0011
Temperature scaling (Guo et al., 2017)
0.0374 + 0.0028
0.8131 = 0.0011
Uncalibration
0.0401 0.0010
0.8229 0.0013
GP calibration (Wenger et al., 2020)
0.0400 +: 0.0010
0.8229 + 0.0014
GP calibration (app.) (Wenger et al., 2020)
0.0400 0.0009
0.8229 0.0013
PBR (ours)
0.0320 +: 0.0050
0.8023 + 0.0084
resnext-8x64d
PBR total (ours)
0.0310 0.0082
0.8123 0.0080
PBR app. (ours)
0.0399 + 0.0024
0.8167 01.047
PBR app. total (ours)
0.0401 + 0.0010
0.8229 0.0014 4
Temperature scaling (Guo et al., 2017)
0.0401 + 0.0019
0.8229 0.0013
Uncalibration
0.0405 0.0012
0.8231 0.0013
GP calibration (Wenger et al., 2020)
0.0403 + 0.0013
0.8230 = 0.0014
GP calibration (app.) (Wenger al., 2020)
0.0405 0.0014
0.8230 0.0014
PBR (ours)
0.0305 + 0. 0.0056
0.8014 + 0.0065
16x64
PBR total (ours)
0.0321 0.0071
0.8123 0.0065
PBR app. (ours)
0.0384 + 0.0032
0.8118 + 010068
PBR app. total (ours)
0.0321 +: 0.0071
0.8123 0.0065
Temperature scaling (Guo et al., 2017)
0.0420 +: 0.0025
0.8231 = 0.0013
Uncalibration
0.0639 + 0.0008
0.8230 0.0007
GP calihration (Wenger et al., 2020)
0.0639 + 0.0008
0.8229 01.007
GP calihration (app.) (Wenger al., 2020)
0.0639 + 0.0008
0.8230 0.0007
PBR (ours)
0.0630 + 0.0045
0.8041 0.0143
densenet-hc-L1190-440
PBR total (ours)
0.0618 0.0054
0.8195 0.0078
PBR app. (ours)
0.0639 +: 0.0008
0.8230 + 0.0007
PBR app. total (ours)
0.0639 +: 0.0008
0.8230 0.0007
Temperature scaling (Guo et al., 2017)
0.0222 + 0.0013
0.8230 = 0.0007
36

---

PAC-Bayes Analysis for Recalibration in Classification
Table ECE, accuracy, and entropy under PBR (Fq. (8)) and PBR total (Eq. (10)) on KITTI. Bold font indicates the hest result among PBR and PBR total for each metric. If the best values are numerically identical, no bolding is applied. In case of a tie in the mean. the result smaller standard deviation is considered better.
Model
Method
ECE (1)
Accuracy (t)
Cross entropy (L)
Uncalibration
0.011 + 0.000
0.963 - 0.001
0.110 + 0.002
XGBoost
PBR (ours)
0.008 + 0.003
0.964 0.001
0.104 + 0.002
PBR total (ours)
0.006 + 0.001
0.964 + 0.001
0.104 + 0.001
Uncalibration
+ +004:00000
0.964 + 0.001
0.160 + 0.003
Random Forest
PBR (ours)
0.008 = 0.003
0
0.114 0.004
PBR total (ours)
0.007
0.963 0.002
0.113 + 0.005
Uncalibration
0.005 +
0.962 - 0.001
0.122 + 0.004
L-Layer NN
PBR (ours)
0.005 + 0.001
0.962 + 0.001
0.122 + 0.004
PBR total (ours)
0.005 + 0.001
0.962 + 0.001
0.122 + 0.004
Table ECE, accuracy, and cross entropy under our PBR (Bq. (8) and PBR total (Eq. (10)) on PCam. Bold font indicates the best result among PBR and PBR total for each metric. If the best values numerically identical, no bolding is applied. case of tie in the the result with smaller standard deviation is considered better.
Model
Method
ECE (L)
Accuracy (1)
Cross entropy (4)
Uncalibration
0.052 + 0.002
0.845 + 0.002
0.356 + 0.004
XGBoost
PBR (ours)
0.014 0.004
0.844 0.003
0.338 + 0.004
PBR total (ours)
0.011 + 0.004
0.846 + 0.002
0.336 + 0.003
Uncalibration
0.082 + 0.001
0.850 + 0.002
0.382 + 0.004
Random Forest
PBR (ours)
0.011 + 0.004
0.849 + 0.002
0.339 0.003
PBR total (ours)
0.012 = 0.007
0.339 + 0.003
Uncalibration
0.206 + 0.001
0.593 + 0.002
0.866 + 0.004
1 L-Layer NN
PBR (ours)
0.038 + 0.007
0.651 + 0.002
0.663 0.008
PBR total (ours)
0.038 0.006
0.650 + 0.003
0.661 + 0.004
37

---

PAC-Bayes Analysis for Recalibration in Classification
Table ECE, accuracy, and cross entropy under our PBR (Eq. (8) and PBR total (Eq. (10) MNIST. Bold font indicates the best result among PBR and PBR total for each metric. If the best values are numerically identical, no bolding is applied. In case of a tie in the mean.
result smaller standard deviation is considered better.
Model
Method
ECE (L)
Accuracy (t)
Cross entropy (1)
Uncalibration
0.004 0.000
0.979 + 0.000
0.073 0.002
XGBoost
PBR (ours)
0.004 = 0.000
0.978 # 0.001
0.073 = 0.002
PBR total (ours)
0.004 + 0.000
0.979 + 0.001
0.073 + 0.002
Uncalibration
0.143 = 0.001
0.966 + 0.001
0.254 0.001
Random Forest
PBR (ours)
0.007 = 0.002
0.964 = 0.002
0.134 = 0.009
PBR total (ours)
0.006 + 0.003
0.966 + 0.002
0.120 + 0.004
Uncalibration
0.016 =
0.976 + 0.001
0.124 + 0.005
L-Layer NN
PBR (ours)
0.014 = 0.001
0.975 + 0.001
0.107 = 0.005
PBR total (ours)
0.011 + 0.002
0.974 0.002
0.100 + 0.006
Table 10, ECE, accuracy, and cross entropy under our PBR (Eq. (8)) and PBR total (Eq. (10) on CIFAR100. Bold font indicates the best result among PBR and PBR total for each metric. If the best values numerically identical. bolding is applied. In case of a tie in the mean, the result with a smaller standard deviation is considered better.
Model
Method
ECE (L)
Accuracy (t)
Cross entropy (L)
Uncalibration
0.255 + 0.001
0.437 = 0.001
2.952 + 0.009
alexnet
PBR (ours)
0.255 + 0.001
0.437 = 0.001
2.952 + 0.008
PBR total (ours)
0.255 = 0.001
0.437 = 0.001
2.952 + 0.009
Uncalibration
0.057 + 0.001
0.813 + 0.001
0.772 + 0.005
WRN-28-10-drop
PBR (ours)
0.050 + 0.005
0.788 + 0.005
0.897 0.030
PBR total (ours)
0.035 0.009
0.796 + 0.006
0.818 = 0.023
Uncalibration
0.040 = 0.001
0.823 = 0.001
0.704 0.006
resnext-8x64d
PBR (ours)
0.032 + 0.005
0.802 - 0.008
0.037
PBR total (ours)
0.031 0.008
0.812 + 0.008
0.739 + 0.023
Uncalibration
0.040 + 0.001
0.823 + 0.001
0.709 0.005
resnext-16x64d
PBR (ours)
0.030 + 0.006
0.801 - 0.006
0.804 0.024
PBR total (ours)
0.032 + 0.007
0.812 + 0.007
0.741 0.018
Uncalibration
0.064 0.001
0.823 + 0.001
0.708 + 0.007
densemet-bc-LL190-k4)
PBR (ours)
0.063 + 0.005
0.804 0.014
0.799 + 0.074
PBR total (ours)
0.062 + 0.005
0.820 + 0.008
0.721 1 0.028
38


Reviews:
[{"review_id": "j27N9Yke6S", "reviewer": "Reviewer_mK1Q", "summary": "Existing recalibration methods either lack theoretical analysis or are limited to binary classification. To address this, the authors first analyze the generalization error and estimation bias of the ECE in multiclass classification, deriving non-asymptotic bounds and identifying the practical optimal bin size. They then conduct a PAC-Bayes analysis for recalibration and propose a new generalization-aware recalibration algorithm based on the PAC-Bayes bound. Numerical experiments demonstrate that the proposed algorithm outperforms the performance of Gaussian process-based recalibration across various benchmark datasets and models", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your feedback.\n\n### Q.1: Regarding the key technical innovations of this paper relative to Futami and Fujisawa (2024)\n\nThe 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.\nThe 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.\nMoreover, 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.\n\n\n### Q.2: Regarding the justification of the Lipschitz continuity assumption\n\nWe 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.\nMoreover, 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.\n\n### References \n- [Futami & Fujisawa, 2024](https://proceedings.neurips.cc/paper_files/paper/2024/file/9961e42624a6c083279303767c73269d-Paper-Conference.pdf)  \n- [Li et al., 2021](https://arxiv.org/pdf/2103.07095)", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The definition of generalization error is standard, and the datasets are appropriate.", "theoretical_claims": "I didn't verify the proofs in the appendix in detail but reviewed the proof outline, which appears to be correct, but I could be wrong because I am not very familiar with the PAC-Beyas theory.", "experimental_designs_or_analyses": "Yes, the experiments seem convincing and discussion is detailed", "relation_to_broader_scientific_literature": "Conceptually, this paper primarily extends the results of Futami and Fujisawa (2024) from binary classification to the multiclass setting. However, it employs different mathematical techniques, which contribute to its originality and innovation.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The writing is clear, with well-stated theorems and a strong takeaway message.\n2. The theoretical results appear robust, tight, and technically innovative.\n3. Practical algorithms are derived from the theoretical analysis, demonstrating applicability.\n\nWeaknesses:\n1. Some results may not be particularly surprising, given the results of Futami and Fujisawa (2024).\n2. The assumption of Lipschitz continuity may be too strong, as the argmax function itself is not Lipschitz. A small perturbation in x could lead to significant changes in the conditional probability.", "other_comments_or_suggestions": "See weaknesses.", "questions_for_authors": "1. Could you elaborate on the technical innovations of this paper compared to Futami and Fujisawa (2024)?\n2. The assumption of Lipschitz continuity appears somewhat strong, given that the argmax function itself is not Lipschitz. A small perturbation in x can potentially cause a large change in the conditional probability. Could you clarify why this assumption is still reasonable in this context?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qcU40uZ3fO", "reviewer": "Reviewer_FaKB", "summary": "This paper provides a PAC-Bayesian analysis of recalibration in multiclass classification, particularly focusing on evaluating and controlling the bias and generalization error of the expected calibration error (ECE) viewed as an estimator of the top-label calibration error (TCE; infeasible to evaluate); see Section 3. The authors introduce a general theoretical framework using PAC-Bayes analysis to derive optimizable upper bounds for the generalization error and bias of the ECE, which are subsequently used to propose a novel recalibration algorithm (PAC-Bayes Recalibration, or PBR; see Section 4.2). Theoretical results include optimal bin-size choices and associated convergence rates. Empirical evaluations demonstrate the effectiveness of the proposed method, showing consistent performance improvements in recalibration compared to other existing methods (e.g., Gaussian process recalibration, temperature scaling).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## Theoretical Claims and Weaknesses\n\n### Q.1: Proof Sketch of Theorems 1 and 2  \nWe added a proof sketch to clarify our theoretical contributions. The bias is decomposed into binning approximation error and finite-sample estimation bias:\n- 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.\n- 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}})|$\n- The first term uses the Lipschitz assumption; the second is bounded via McDiarmid’s inequality with binwise conditioning.\n- In Theorem 2, only the second term remains and is bounded via PAC-Bayes using the Donsker–Varadhan inequality.\n\nThese techniques generalize the binary setting [Futami & Fujisawa, 2024](https://proceedings.neurips.cc/paper_files/paper/2024/file/9961e42624a6c083279303767c73269d-Paper-Conference.pdf) to the multiclass case and form a core novelty of our work.\n\n### Q.2: Clarifying Contributions in the Introduction  \nWe 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.\n\n## Experimental Design or Analyses\n\n### Q.3: Empirical Validation of Theoretical Results  \nWe extended the bound verification experiment from [Zhang et al., 2020](https://arxiv.org/pdf/2003.07329) and (Futami & Fujisawa, 2024) to the multiclass case. Using synthetic data with analytically computable TCE, we confirmed:\n- The TCE–ECE gap decreases as $\\mathcal{O}(1/n^{1/3})$ at the theoretical bin size.\n- The empirically optimal bin size also follows $\\mathcal{O}(n^{1/3})$.\n\nResults are shown [here](https://drive.google.com/file/d/1YBM1El-FtxYh1sRg0OjA0tw7CItwOnuQ/view?usp=sharing).\nThis discrepancy arises because the theoretical bin size minimizes the **upper bound**, not necessarily the actual TCE gap. We added this discussion to Section 6.  \n\n## Other Comments and Suggestions\n\n### S.1-1: Clarifying Use of UWB  \nWe 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.\n\n### S.1-2: Justifying TCE and ECE Focus  \nWe 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.\n\n### S.2: Clarifying Eqs. (8) and (9)  \nWe added definitions for key terms (e.g., total bias, generalization error, top-$K$ CE) and clarified the distinction between Eqs. (8) and (9).\n\n### S.3: Related Work Positioning  \nTo improve clarity, we placed Related Work after introducing the main definitions. A pointer to Section 5 was added at the end of the Introduction.\n\n### S.4: Correlation Analysis  \nFollowing prior work (e.g., [Jiang et al., 2019](https://arxiv.org/abs/1912.02178); [Kawaguchi et al., 2023](https://arxiv.org/pdf/2305.18887)), 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.\n\n### S.5: Parametric vs. Nonparametric Clarification  \nWe 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.\n\n## Questions\n\n### Q.4: Class Size and Prior Choices  \nTheorems 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](https://arxiv.org/pdf/1202.6228)), which is an important direction for future work.  \nOur 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.\n\n### Q.5: Fast Rates under Low-Noise Conditions  \nUnder Bernstein or Tsybakov noise ([Alquier et al., 2016](https://jmlr.org/papers/v17/15-290.html)), 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.", "claims_and_evidence": "The main claims that PAC-Bayes bounds can effectively quantify generalization and estimation biases in multiclass recalibration scenarios are generally well-supported by solid theoretical analyses (Theorems 1, 2, and 3) and comprehensive numerical experiments (Section 6).", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria—particularly the use of standard benchmarks (MNIST, CIFAR-100) and established baselines (temperature scaling, GP recalibration)—are relevant and appropriate for this problem.The choice of calibration metrics (TCE, ECE) aligns well with existing literature.", "theoretical_claims": "I briefly checked the main theoretical results (Theorems 1, 2, and 3) and their proofs provided in the appendix. They appear technically sound and are based on standard PAC-Bayes and concentration inequality arguments. However, the main text could greatly benefit from including clearly summarized high-level intuitions and sketches of key proofs (particularly for Theorem 1). I believe presenting the theoretical insights more explicitly and earlier could improve readability and comprehension.", "experimental_designs_or_analyses": "The experimental setups and analyses appear generally sound, utilizing standard benchmarks such as MNIST and CIFAR-100 datasets, and appropriate baseline methods (temperature scaling, GP-based recalibration). However, clearer connections between empirical experiments and the theoretical results (e.g., verifying optimal bin-size choices empirically) could help readers better appreciate the results in this paper as well as further enhance the paper’s contribution.", "relation_to_broader_scientific_literature": "The authors effectively position their contributions within existing literature on calibration methods, PAC-Bayes theory, and binning-based calibration error estimation. Their work clearly distinguishes itself from recent recalibration literature by providing a PAC-Bayes theoretical framework for recalibration, particularly emphasizing the multiclass setting compared to previous binary-focused works.", "essential_references_not_discussed": "The discussion of related works seems generally adequate.", "other_strengths_and_weaknesses": "Strengths:\n* Solid theoretical contributions that provide novel guarantees for ECE using PAC-Bayes bounds, enhancing methodological rigor.\n\n* Broad relevance, particularly with practical applications in multiclass recalibration scenarios.\n\n* Extensive empirical validation that convincingly demonstrates the effectiveness of the proposed recalibration method.\n\nWeaknesses:\n* Presentation can be significantly improved by clarifying key ideas earlier in the text and summarizing the theoretical contributions more explicitly and concisely, enhancing readability and accessibility.", "other_comments_or_suggestions": "This paper offers noteworthy contributions, yet it could be significantly strengthened by improving clarity and organization. In particular, introducing key concepts and theoretical motivations earlier—and in a more structured manner—would help preempt many reader questions and confusions. Below, I elaborate on specific suggestions:\n\n**1. Manuscript organization and clarification:** \nIt would be beneficial to address anticipated reader questions more directly and to summarize theoretical insights earlier. For example, in the introduction (lines 76–86), the authors raise the concern that some bins may remain empty when applying PAC-Bayes analysis to ECE. However, they do not specify that either they will use equal-width binning or this challenge applies primarily to equal-width binning---prompting the reader to wonder about \"what if we use uniform-mass binning instead?\" Another instance arises from the presentation of TCE as the central recalibration metric in early sections (e.g., Section 1 and Section 2.2), along with the implication that ECE is crucial for analyzing TCE. This leads to questions about why TCE is the only focus and whether analyzing ECE is indeed the best way to manage TCE. Although these issues are addressed in later sections, introducing the rationale and framing them clearly from the outset would greatly enhance readability.\n\n**2. Explicit definitions and explanations:** \nClearly defining core ideas---such as total bias (pre- and post-calibration) and the generalization error of ECE---would help readers follow the arguments more easily. Placing these definitions in a dedicated “Definition” environment could make them more prominent and accessible. Additionally, when comparing Equations (8) and (9), it should be highlighted more explicitly that the only change is the added classification loss term $l_{\\mathrm{acc}}$, instead of merely presenting two expressions. A more explicit mention of this difference, possibly alongside visual cues or parentheses to clarify the scope of the expectation in Equation (9), would be helpful.\n\n**3. Positioning of the “Related Work” section:**\nIt might be advantageous to move Section 5 (“Related Work”) closer to the introduction. While I understand that the section also serves to discuss the results presented later, having this material earlier could frame the research questions and contributions more clearly. Doing so would likely address some of the aforementioned reader concerns about TCE, ECE, and binning choices right from the start.\n\n\nI have some additional minor comments below:\n\n**4.** In Section 6, the authors write \"... we observe a correlation between the KL divergence and the ECE generalization gap, as confirmed by Pearson’s and Kendall’s rank-correlation coefficients, supporting the validity of our bound.\"  However, I don't clearly see (1) if the correlation is sufficiently significant, and (2) how the observed trend supports theoretical findings.  It may be worth adding a few more sentences for a more detailed and systematic assessment.\n\n**5.** In Section 2.3, the authors define the recalibration map as a *parametric* function $\\eta_V: \\Delta^K \\to \\Delta^K$ with parameter $V \\in \\mathbb{R}^{d'}$. Meanwhile, the abstract and other parts of the paper emphasize nonparametric binning. Either revising the definition of the recalibration map or clarifying how a parametric approach to recalibration aligns with the stated focus on nonparametric binning would help avoid confusion and strengthen the paper’s coherence.", "questions_for_authors": "Could you clarify or comment on the practical tightness of the upper bounds presented in Theorems 1, 2, and 3? While I appreciate the arguments regarding the asymptotic minimax rate with respect to sample size, I am curious about two additional aspects:\n\n**1. Dependence on other factors.** How tight is the dependence on parameters such as $K, B, \\lambda$, and the KL divergence? It would be informative to see either a theoretical discussion or numerical experiments (e.g., with synthetic toy datasets) that illustrate how these factors affect the bounds.\n\n**2. Potentially favorable properties in practical datasets.** Are there particular properties in real-world datasets (or their underlying distributions) that might lead to faster rates, even if the general minimax rates are pessimistic? Demonstrating such scenarios would further highlight the practical significance and relevance of your results.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FvqCPsdif1", "reviewer": "Reviewer_ZBrY", "summary": "The paper presents the PAC-Bayes based analysis of generalisation in recalibration of predictors. Recalibration of predictors to minimise calibration errors is a common task, however to the best of my knowledge, I haven't seen formal PAC-Bayes results on the generalisation aspect of it. Some arguments that I have seen are based on the usual concentration results. In that sense, the paper makes useful contribution. The paper also studies the bias in estimating top-label calibration with an estimator of the form of expected calibration error---a popular metric for measuring calibration. The paper also presents a recalibration based approach that is directly informed by the PAC-Bayes analysis. Experiments support the generation gap dependence on the PAC-Bayes terms, and further experiments on recalibration approaches suggest mixed insights.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## Claim and Evidence\n\n### Q.1: Motivation for Eq. (9)\nAs 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.\nTo mitigate this, we evaluated both Eq. (8) (Brier) and Eq. (9) (Brier + cross-entropy). Empirically, Eq. (9) tended to perform better.\n\n## Methods and Evaluation Criteria\n\n### Q.2: Motivation for using UWB and method comparison\n- (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.  \n- (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.\n\n## Experimental Designs or Analyses\n\n### Q.3: GP-based methods and overfitting\nGP-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.\n\n### Q.4: GP computational complexity\nWe revised Section 4.2 to clarify:  \n- 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}}$.  \n- 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}}$.\n\n## Relation to Broader Scientific Literature\n\n### Q.5: Novelty and context\nPrior 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.  \nWhile 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.\nMulticlass calibration metrics have been discussed (e.g., Zhang et al., 2020; Gruber & Buettner, 2022), but without generalization or recalibration—key aspects of our study.\n\nWe revised Section 5 accordingly:\n- Discussed how our PAC-Bayes analysis differs from conventional i.i.d.-based approaches.\n- Clarified that our bound is optimizable, enabling practical algorithm design.\n- Highlighted how our Theorem 3 formally explains the curse of dimensionality in $\\mathrm{CE}\\_K$, unlike prior work.\n\n## Other Strengths and Weaknesses\n\n### Q.6: Writing improvements\nThank 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](https://openreview.net/forum?id=eJzZryJfri&noteId=UqauLyR5uq)). We also removed a potentially confusing explanation around lines 191–192.\nDue 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.\n\n### References\n- [Kull et al., 2015](https://link.springer.com/content/pdf/10.1007/978-3-319-23528-8_5.pdf)  \n- [Perez-Lebel et al., 2018](https://arxiv.org/pdf/2210.16315)  \n- [Rasmussen & Williams, 2006](https://gaussianprocess.org/gpml/chapters/RW.pdf)  \n- [Bishop, 2006](https://link.springer.com/book/9780387310732)  \n- [MacKay, 1998](https://core.ac.uk/download/pdf/216127203.pdf)  \n- [Wenger et al. , 2020](https://proceedings.mlr.press/v108/wenger20a.html)\n- [Gupta & Ramdas, 2021](https://arxiv.org/abs/2105.04656)\n- [Sun et al., 2023](https://arxiv.org/abs/2305.10886)\n- [Futami & Fujisawa, 2024](https://proceedings.neurips.cc/paper_files/paper/2024/file/9961e42624a6c083279303767c73269d-Paper-Conference.pdf)  \n- [Zhang et al., 2020](https://arxiv.org/pdf/2003.07329)  \n- [Gruber & Buettner, 2022](https://arxiv.org/abs/2203.07835)", "claims_and_evidence": "1. The goals of the paper are clearly stated, and the paper also accomplishes it convincingly.\n2. There are connections also mentioned to similar reported results in the literature (results from Tsybakov in Section 3.1, GP-based recalibration by Wenger et al. in Section 4.2).\n\n3. One clarity that I can get is in Equation 8 and Equation 9: Equation 8 suggests to minimise a regularised form of Brier score, and it is known (check Chapter 3 here: https://www.cis.upenn.edu/~aaroth/uncertainty-notes.pdf#page=25.58) that minimising it should also fix the accuracy, or if we fix the calibration error, the predictor's performance improve. So is there some additional motivation for directly adding a loss function in Equation 9?", "methods_and_evaluation_criteria": "The methods and evaluation are justified to a certain extent. However, the paper needs to explore alternate approaches to estimating TCE / ECE, like the kernel based methods or the smooth calibration error. Experimentally, alternative recalibration methods like beta calibration, isotonic regression can also be investigated. This could help inform more exhaustive insights.", "theoretical_claims": "I haven't verified the proofs of the presented theoretical claims in details, but they follow the similar machinery as the typical PAC-Bayes results, and in that sense, I do agree with the presented claims.", "experimental_designs_or_analyses": "The paper suggests that temperature scaling can cause overfitting when recalibration data is small. However, I'm assume GP based inference can also suffer from that. Furthermore, when the dataset is large, then GP based inference can be computationally expensive. I'm aware there are methods to deal with these issues in the GP literature, but I'd appreciate if this can be highlighted.", "relation_to_broader_scientific_literature": "The paper's result informs the generalisation of recalibration approaches and the trade-offs therein. While the results could be useful, they don't seem very revealing in terms of what one should expect. The literature on ECE is familiar with the trade-off between the number of bins and estimation bias. PAC-Bayes generalisation bounds also are intuitive, and are expected in terms of what is known in the standard PAC-Bayes bounds. I'd appreciate if authors can further help me understanding the implications of the presented results.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The paper can also be improved in terms of writing. The paper currently presents theoretical results one after the other with little intuition or motivation over the significance of the results. The paper also assumes significant familiarity with the PAC-Bayes machinery, and could be made more accessible by a gentle introduction. For example, lines 191-192 state that $f_w$ and $S_{tr}$ are dependent, however for someone who is not familiar with the PAC-Bayes would not get the importance of such statements.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "Check above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6VTafd7yak", "reviewer": "Reviewer_pWL9", "summary": "In this paper, the PAC-Bayesian framework is used to analyze recalibration in a multiclass classification setting. Specifically, the bias of estimators of the calibration error is bounded, taking both binning and statistical effects into account. The resulting bounds are used as the basis for new recalibration algorithms, which yield improved performance over state-of-the-art approaches for certain settings.\n\n## update after rebuttal\n\nI thank the authors for their responses. I have updated my evaluation upward accordingly, but the contributions still seem somewhat incremental relative to utami and Fujisawa (2024).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your feedback.\n\n## Experimental Designs Or Analyses\n\n### Q.1: Regarding the Gibbs error\n\nStep 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.\n\n## Relation To Broader Scientific Literature\n\n### Q.2: Regarding the relationship between this study and Futami and Fujisawa (2024)\n\nPlease refer to our response to [Reviewer mK1Q’s Q.1](https://openreview.net/forum?id=eJzZryJfri&noteId=4CcGzbpkT0). 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.\n\n## Other Comments and Suggestions\n\n### Q.3: Regarding the notation of expectation\n\nWe 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.\n\n### Q.4: Regarding our explanation around line 152\n\nWe revised the explanation as follows:\n  - “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.”\n\n### Q.5 and 6: Regarding $\\lambda$ in Theorem 1, Eq. (6)\n\nWe added the assumption $\\lambda > 0$ to Theorem 1 and corrected it to $\\eta_{V}$.\n\n### Q.7: Regarding our explanation around line 227\n\nWe apologize for the overstatement and have revised the text as follows:\n  - “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.”\n\n### Q.8: Regarding our explanation around line 309\n\nWe revised the explanation as follows:\n  - “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).”\n\n### Q.9: Regarding our explanation around line 294\n\nThis has been corrected. We apologize for any confusion.\n\n## Questions\n\n### Q.10: Regarding the difference from Futami and Fujisawa (2024)\n\nPlease see our responses under Relation to Broader Scientific Literature and Weaknesses, and [Reviewer mK1Q’s Q.1](https://openreview.net/forum?id=eJzZryJfri&noteId=4CcGzbpkT0) for clarification.\n\n### Q.11: Regarding the limitation of our PBR\n\nWe 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.\n\n### Q.12: Regarding clarification on class identification\n\nWe 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.\n\n### References  \n- [Futami & Fujisawa, 2024](https://proceedings.neurips.cc/paper_files/paper/2024/file/9961e42624a6c083279303767c73269d-Paper-Conference.pdf)  \n- [Alquier et al., 2016](https://jmlr.org/papers/v17/15-290.html)\n- [McAllester, 2003](https://link.springer.com/chapter/10.1007/978-3-540-45167-9_16)", "claims_and_evidence": "Yes — the theoretical derivations appear sound, and the claimed performance improvements (mixed depending on setting) are not beyond what is actually demonstrated", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I skimmed all proofs and did not notice any issues, but did not go through details beyond App. B.4.", "experimental_designs_or_analyses": "I did not study the experimental results beyond the main paper. A minor point that does not seem fully supported is that the theorems involve a “Gibbs error” (i.e. parameters are drawn randomly from posterior for each use) while the practical algorithm deploys an averaged parameter.", "relation_to_broader_scientific_literature": "The contributions of this paper give a foundation for many approaches to recalibration, for which theoretical analyses may be lacking. The most closely related work to this is Futami and Fujisawa (2004), for which similar bounds on recalibration error are derived. The key difference appears to be that the present paper derives high-probability PAC-Bayesian bounds, while the work of Futami and Fujisawa obtains CMI-based bounds in expectation. However, the proof techniques are very similar, and obtaining the results of this paper seems to essentially rely on using a different change of measure in Donsker-Varadhan. The concentration inequalities that are used are essentially identical, based on a bounded differences argument [1]. The attractiveness of the PAC-Bayesian approach, as highlighted in this paper, is that it enables explicit optimization, potentially leading to improved algorithms. While the present paper also discusses multi-class classification, this analysis appears very similar to the binary case, as noted in the paper.\n\n[1]: e.g., lines 878-908 are identical with the argument on p. 15 of Futami and Fujisawa without explicit reference. This casts some doubt on the \"main contribution [being] the derivation of new concentration inequalities\"", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "It appears to me that the key strength of the paper is the proposed algorithm, and the fact that this leads to improvements in certain settings, while a key weakness is the similarity of the theoretical analysis compared to Futami and Fujisawa (2004).", "other_comments_or_suggestions": "1. “the expectation of a random variable $X$ as $E_X$”: this notation seems to be actually used with distributions in subscript rather than random variables\n2. Line 152: “We expect…” should be with $S_{re}$ rather than $S_{te}$?\n3. Theorem 1: $\\lambda$ is not defined in theorem statement\n4. Eq. (6): Should be $\\eta_V$?\n5. Line 227, right column: “required” — as the obtained result is only an upper bound, it cannot be used to argue that regularization is required for preventing overfitting\n6. Line 309: “Eq. (10)” from appendix is referred to without context\n7. Line 294, right column: “Equation. (9)”", "questions_for_authors": "1. Can you clarify how the theoretical analysis differs from that of Futami and Fujisawa (2004)? If there are key aspects that I have missed, this may affect my evaluation.\n2. It is noted in the paper that the proposed algorithm PBR performs worse than temperature-based approaches for, e.g., settings where the underlying classifier has low accuracy. What may this depend on? As the key contribution of the paper appears to be a potential algorithmic advance, clarifying why and how it is useful may affect evaluation.\n3. In line 249 and onwards, the use of focusing on $K’$ classes is discussed. Do these classes need to be identified in advance or is, e.g., top-$K’$ classes okay? (Just curious)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review."}}]

Author rebuttal:

Meta-review: The reviewers agreed that the paper offers one of the rare theoretically grounded contributions to classifier recalibration. This is also an original contribution to the PAC-Bayes framework, as the studied metric differs from the ones classically studied when bounding the generalization error. The PAC-Bayesian treatment allows the conception of an efficient recalibration algorithm based on bound optimization.

Importantly, the reviewers diligently suggested clarification improvements during the discussion. I strongly encourage the authors to integrate them into the revised version of their paper conscientiously.
Decision: Accept (poster)