Minimum-Risk Recalibration of Classifiers
Authors: Zeyu Sun
Dogyoon Song
Alfred Hero
Venue: NeurIPS 2023 spotlight (2023)
Keywords: probability calibration
optimal number of bins
label shift adaptation
TL;DR: This paper proposes a framework for evaluating and analyzing the risks for histogram binning recalibration.

Abstract: Recalibrating probabilistic classifiers is vital for enhancing the reliability and accuracy of predictive models. Despite the development of numerous recalibration algorithms, there is still a lack of a comprehensive theory that integrates calibration and sharpness (which is essential for maintaining predictive power). In this paper, we introduce the concept of minimum-risk recalibration within the framework of mean-squared-error (MSE) decomposition, offering a principled approach for evaluating and recalibrating probabilistic classifiers. Using this framework, we analyze the uniform-mass binning (UMB) recalibration method and establish a finite-sample risk upper bound of order $\tilde{O}(B/n + 1/B^2)$ where $B$ is the number of bins and $n$ is the sample size. By balancing calibration and sharpness, we further determine that the optimal number of bins for UMB scales with $n^{1/3}$, resulting in a risk bound of approximately $O(n^{-2/3})$. Additionally, we tackle the challenge of label shift by proposing a two-stage approach that adjusts the recalibration function using limited labeled data from the target domain. Our results show that transferring a calibrated classifier requires significantly fewer target samples compared to recalibrating from scratch. We validate our theoretical findings through numerical simulations, which confirm the tightness of the proposed bounds, the optimal number of bins, and the effectiveness of label shift adaptation.

Minimum-Risk Recalibration of Classifiers
Zeyu Sun"
Dogyoon Song*
University of Michigan zeyusundumich.c edu
University of Michigan
dogyoons@umich.co edu
Alfred Hero
University of Michigan hero@eecs umich. edu
Abstract
Recalibrating probabilistic classifiers is vital for enhancing the reliability and accuracy of predictive models. Despite the development of numerous recalibration algorithms, there is still lack of a comprehensive theory that integrates calibration and sharpness (which is essential for maintaining predictive power). In this paper, we introduce the concept of minimum-risk recalibration within the framework of meea-ssuaree-erron (MSE) decomposition, offering principled approach for evaluating and recalibrating probabilistic classifiers. Using this framework, we analyze the uniform maaoorm-mass binning (UMB) recalibration method and establish a finite-sample risk upper bound of order Ö(B/n + 1/B²) where B is the number bins and n the sample size. By balancing calibration and sharpness, we further determine that the optimal number of bins for UMB scales with n resulting risk bound of approximately On 2/3). Additionally, we tackle the challenge of label shift by proposing a two-stage approach that adjusts the recalibration function using limited labeled data from the target domain. Our results show that transferring calibrated classifier requires significantly fewer target samples compared recalibrating from scratch. We validate our theoretical findings through numerical simulations, which confirm the tightness of the proposed bounds, the optimal number of bins, and the effectiveness of label shift adaptation.
1 Introduction
Generating reliable probability estimates alongside accurate class labels is crucial in classification tasks. A probabilistic classifier is considered "well calibrated" when its predicted probabilities
closely align with the empirical frequencies of the corresponding labels [9. Calibration is highly
desirable, partieularly in high-stakes applications such as meteorological forecasting R32
10.
econometrics [16), personalized medicine [25] 24], and natural language processing 37
53
Unfortunately, many machine learning algorithms lack inherent calibration [18].
To tackle this challenge, various methods have been proposed for designing post hoc recalibration
functions. These functions are used assess calibration error 52
42
17
detect miscalibration
21 Despite the rapid development of recalibration algorithms, there is still lack of a comprehensive theory that encompasses both calibration and sharpness (retaining predictive power) from a principled standpoint. Furthermore, existing methods often rely on diverse calibration metrics 17 and the selection hyperparameters is often based on heuristic approaches [4 20 without rigorous justifications. This highlights the
30). and provide post-hoc recalibration [50 51 18 48 29
Equual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

need for identifying an optimal metric to evaluate calibration, which can facilitate the development of a unified theory and design principles for recalibration functions.
In addition, the deployment of machine learning models to data distributions that differ from the training phase is increasingly common. These distribution shifts can occur naturally due factors such as seasonality or other variations, or they can be induced artificially through data manipulation methods such as subsampling or data augmentation. Distribution shifts pose challenges to the generalization of machine learning models. Therefore, it becomes necessary to adapt the trained model to these new settings. One significant category of distribution shifts is label shift, where the marginal probabilities of the classes differ between the training and test sets while the class conditional feature distributions remain the same. With calibrated probabilistic predictions, label shift can be adjusted assuming access to class marginal probabilities [12. However, miscalibration combined with label shift is common and remains a challenging problem 2
In this paper, we aim to address these issues in a twofold manner. Firstly, we develop a unified framework for recalibration that incorporates both calibration and sharpness in a principled manner. Secondly, we propose a composite estimator for recalibration in the presence of label shift that converges the optimal recalibration. Our framework enables the adaptation of a classifier to the label-shifted domain in a sample-efficient manner.
1.1 Related work
Recalibration algorithms. Recalibration methods can be broadly categorized into parametric and nonparametric approaches. Parametric methods model the recalibration function in a parametric form and estimate the parameters using calibration data. Examples of parametric methods include Platt scaling [40], temperature scaling [1]. Beta calibration [28). and Dirichlet calibration [27]. However, it has been reported that scaling methods are often less calibrated than supposed, and quantifying the degree of miscalibration can be challenging [2).. In contrast, nonparametric recalibration methods do
assume a specific parametric form for the recalibration function. These methods include histogram
binning [50] isotonic regression [51) kernel density estimation [52] 42 splines 23], Gaussian
processes [49] among others. Hybrid approaches, integrating both parametric and nonparametric
techniques, have also been proposed. For instance, Kumar et al. [29] combine nonparametric histogram binning with parametric scaling to reduce variance and improve recalibration performance. Nevertheless, this hybrid approach is biased when its parametric assumptions fail. In this work, we consider a nonparametric histogram binning method called uniform- -mss binning (UMB), which is asymptotically unbiased.
Histogram binning method. Histogram binning methods are widely used for recalibration due to their simplicity and adaptability. The binning schemes can be pre-specified (e.g., uniform- width binning I8], data-dependent (e.g., uniform-mass binning (50). or algorithm-inducer [51]. When selecting binning scheme, it is crucial to consider the trade-off between approximation and estimation. Coarser binning reduces estimation error (variance), leading to improved calibration, but at the expense of increased approximation error (bias), which diminishes sharpness. Thus, determining the optimal binning scheme and hyperparameters, such as the number of bins (B), remains an active area of research. (36] proposes a Bayesian bimning method, but verifying the priors 44 suggests choosing the largest B that preserves monotonicity, which is heuristic and computationally inefficient. (2) offers a heuristic for choosing the largest B subject to a calibration constraint, lacking a quantitative characterization of sharpness. Our work builds upon the existing upper bounds for calibration risks of binning methods [29 (0) and derived upper bounds for complementary risk component known as the sharpness risk. We quantitatively characterize the -itrrationssaapnessss tradeoff, which yields an optimal choice for the number of bins that achieves the minimum risk.
is often challenging.
Adaptation to label shift. Label shift presents a challenge in generalizing models trained on one distribution (source) to different distribution (target). As such, adapting to label shift has received considerable attention in the literature 122 45 31 3 2 14] In practical scenarios, it is common to encounter model miscalibration and label shift simultaneously [47 Empirical observations have highlighted the crucial role of probability calibration in label shift adaptation 12 [3), which justified by subsequent theories [1]. However, to the best of our knowledge, there has been no prior work that specifically addresses the recalibration with limited amount of labeled data from the target distribution. Our theoretical analysis points out that using only target labels achieves risk
bounds of the same order as the methods using only target features [1 3 14].

---

1.2 Contributions
This paper contributes to the theory of recalibration across three key dimensions.
Firstly, we develop comprehensive theory for recalibration in binary classification by adopting the meea--squree-errror (MSE) decomposition framework commonly used in meteorology and space weather forecasting [
33 46). Our approach formulates the probability recalibration problem as the minimization a specific risk function, which can be orthogonally decomposed into calibration and sharpness components.
Secondly, utilizing the aforementioned framework, derive a rigorous upper bound on the finite- sample risk for uniform mass binning (UMB) (Theorem []. Furthermore, we minimize this risk bound and demonstrate that the optimal number of bins for UMB, balancing calibration and sharpness, scales the order of n/133, yielding the risk bound of order n 2233 where denotes the sample size.
Lastly, we address the challenge recalibrating classifiers for label shift when only a limited labeled sample from the target distribution is available, challenging situation for direct recalibration approach. We propose a two-stage approach: first recalibrating the classfier on the abundant source- domain data, and then transfering it to the label-shifted target domain. We provide umite-sample guarantee for the risk of this composite procedure (Theorem[2) (2). Notably, to control the risk under approach requires much smaller sample size from the target distribution than direct recalibration on the target sample (12(==)) vs. S2 (/2)), cf. Remark
1.3 Organization
This paper is organized as follows. In Section we introduce notation and provide an overview of calibration and sharpness. D the notion of minimum-risk recalibration by defining the recalibration risk that takes into account both calibration and sharpness. In Section we describe the uniform-mass histogram binning method for recalibration and provide risk upper bound with rate analysis. extend our approach to handle label shift in Section To validate our theory and framework, present numerical experiments in Section 6 Finally, in Section 7 we conclude the paper with a discussion and propose future research directions.
2 Preliminaries
2.1 Notation
Let N and R denote the set of positive integers and the set of real numbers, respectively. For n E N, let [n] := [1....,n}} For æ E R. let [x] = max(m E Z m S x}. For any finite set S (&s : [n]] and any i E [n]. we let S(L) denote the k-th order statistic, which the k-th smallest element in
Let (2, P) denote generic probability space. For event A E, the indicator function 1 : Ω - {0, 1} is defined such that (z) = if and only if E We write happens P-almost surely if P(A) = 1. For probability measure P. define Ep the expectation, with subscript P omitted when the underlying probability measure is clear. For a probability measure P and a random be the probability measure induced by X.
variable X Ω + Rd. let Px- == P x-1
Letting f.g + R. we write fxx) Ogg(z) as x oo if there exist M > 0 and my > such that [xx] < Mg(²) for all 2 zg- Likewise, we write f(x) = ((g(x)) if g(x) = (x)))) We write f(x) g(x) ) if f(x)= (g((z) and g(x) 0(f(z)). We write f(x) ((((z)) if there is k such that f=) (g((z) (x) log (g(z))).
2.2 Calibration and sharpness
Consider the binary classification problem; let E X and Y E y= {0, 1} denote the feature and label random variables. Letting P denote probability measure, want to construct function f: X + z [o, 1] that estimates the conditional probability, i.e.
f(X) P|Y X].
(I)
3

---

Since estimating the probability conditioned on the high dimensional X is difficult, the notion of calibration captures the intuition ① in a weaker sense [3 9
Definition 1. A function f X + Z is (perfectly) calibrated with respect to probability measure P, if
((x) P = 1 (X)) P-almosi surely.
Calibration itself does not guarantee useful predictor. For instance, constant predictor f(X) EY is perfectly calibrated, but it does not change with the features. Such predictor lacks sharpness [26]. also known resolution [35], another desired property which measures the variance in the target Y explained by the probabilistic prediction f(X)-
Definition 2. The sharpness of a function f X with respect probability measure P refers to the quantity
Var ( | f(x)))
E ((X))
The following decomposition of the mean squared error (MSE) suggests why is desirable for a classifier / to be calibrated and have high sharpness; note that Var [Y] is quantity intrinsic the problem, unrelated to /.
MSE(F) == E - f(x))
Var[Y] Var [ Y f(X)) + (((x)- - B|Y f(x)))
squared error
sharpmess
calibration
3 Optimal recalibration
For an arbitrary predictor f : 2' + 2, the aim of recalibration is to identify a post-processing function h : Z such that h f is perfectly calibrated while maintaining the sharpness of f as much as possible. The calibration and sharpness can be evaluated using the following two notions of risks. We suppress the dependency of risks on and P when it leads to no confusion.
Definition 3. Let f: f:A X + 2 and h 2 + Z. The calibration risk of h over f under P is defined as Real Rea((h) R& (h; f) = Ep [1 f(X) Er Y h f(x)))²
(3)
Definition 4. Let X and h Z Z. The sharpness risk of h over f under defined as Roha (h) = Rrp (h; f) == Ep (Ep [Y ho f(X)] Ep [Y [(x)))
(4)
Note that the calibration risk (1: f) = 0 if and only if h o is perfectly calibrated, cf. Definition The sharpness risk Ru (h; f) quantifies the decrement in sharpness of incurred by applying the recalibration map h, and (hha((; f) = O when h is injective (29].
Next we define comprehensive notion of risk that we will use to evaluate recalibration functions. Definition 5. Let f X + Z and h
Z. The recalibration risk of h over f under P is defined
as
R(h) = (h f) = Ep (hh o f(X) - Ep(Y [
(5)
The following proposition shows that the recalibration risk can be decomposed into calibration risk and sharpness risk. The proof deferred to Appendix A Proposition 1 (Decomposition of recalibration risk). For any f X + Z and any h - Z.
(b: Rp (h; + Rehh (h: f))
(6)
Note that (p(h) = 0 if and only if R.pl (h) = 0 and R (h) = 0. This happens if and only if o f is calibrated, and the recalibration h preserves the sharpness of f in predicting Y.
R(h) = then we call h an optimal recalibration function (or minimun-rise recalibration function) of f under P. Let h;; 2 + 2 be the function
EE(YY f(() 2], if supp Pς(X): if & supp Pf(X)-
h h+)
0,

---

Then R(h p) = O. Indeed, h is minimum-riss recalibration function of f if and only if h hj,p Pz Pa-ootsst surely.
Problem 1 (Recalibration). Suppose that have measurable function f X + Z and dataset D ( Vi) [n]} that is an independent and identically distributed (IID) sample drawn from
P. The goal of recalibration is estimate recalibration function z h using f and DD
Problem 1 can be viewed as a regression problem, where we estimate the function form of E Z [n]]
from data {(22, 9s) [n]], where 2; =x;)) vi
4 Recalibration via uniform-mass binning
4.1 Uniform-mass binning algorithm for recalibration
Given a dataset of prediction-label pairs {(2,, v1) E x [n]]. the histogram binning calibration method partitions Z [0, 1] into set of smaller bins, and estimate E[Y Z] by taking
the average in each bin. We consider the uniform mass binning, constructed using quantiles of predicted probabilities.
Definition 6 (Uniform mass binning). Let S {z+ E [0,1] : [n]]. binning scheme = {41 12, IB} is the uniform-mase binning (UMB) scheme induced by $ if
1 = =uu, wi], and In (4,-1, 1, up] vb [B] (1},
(8)
where 0, ug = 1, and [[[bb/B]) for E [B - 1]. For our subsequent discussions, we make the following assumptions on the distribution of Y and Z:
(A1) The cumulative distribution function of Z, denoted by Fz, is absolutely continuous.
(A2) hr defined in is monotonically non-decreasing on supp Pz.
(A3) There exists K > 0 such that if S 22, then (2)) h(, s K (F2((2)-F2(2)) (FF(())))
Assumption (A1) is made for the sake of analytical convenience without loss of generality; see
discussions in (20, Appendix CJ. An important implication of Assumption (A1) is that all intervals
in B are non-empty P'z-almost surely if S {2, i E [n]] are IID under Pz. Assumption (A2)
makes sure Z is informative to preserve the rankings of P|Y Z] [5I]. Lastly, Assumption (A3)
posits that Z is sufficiently informative that P interval I where (2) is small. This assumption is mild but not trivial; see Appendix B.2
2] does not change too rapidly any
Now we describe how to construct recalibration function using UMB.
Algorithm.
1. Given ((2,, y/) i E [n]]. and B E let (4,44 Ta} be the UMB scheme of size induced by {2, : i [m]].
2. Let h = hg Z 2 be function such that
h(()) Σ pr Ir(z) where ùr Σi= Vs 1r(2) El 1,(2))
VI E
IEB
4.2 Theoretical guarantees
Here we establish high-probabiility upper bound on the recalibration risk R(h) for the UMB estimator, h defined in ( which converges to 0 as the sample size n increases to co.
Theorem 1. Let P be probability measure and f X + Z be a measurable function. Suppose that (A1) & (A2) hold. Let B be the UMB scheme induced by an IID sample of f(X), and let h = hg be the recalibration function based on cf. (9). Then there exists a universal constant > 0 such that 8,
for any E (0, if 2 c. |B] log 2 then with probability at least 1
Real (h) < (1
log (4(8)/8)
+ [n/1B]]
and
Raha (h) <
[
2((n/ BI] 1)
8K*
(A3) holds.
5

---

Remark 1. We note that the upper bound on Real (f) in Theorem 1 coincides with the result presented in 120) up to a constant factor in the failure probability, However, Theorem pproviees an additional upper bound on R (h), thereby effectively managing the overall recalibration risk R(h).
Optimal choice of the number of bins [B]. Based on Theorem 1 for any fixed sample size as the number of bins B = [8] increases, the calibration risk bound increases, while the sharpness risk bound decreases. This trade-off suggests may get an optimal number of bins B by minimizing the upper bound for the overall risk, R(h) Re (h) + [aaba (h).
For the simplicity of our analysis, we assume n is divisible by B, and Assumption (A3) holds. Firstly, observe that n/B 2 2, and thus, n/
(2B). Also, since B 2 1 and 6 < I, log( 1B 2 1,
B/B $ V 2n/BBII log (15 2 V n/B log 12) Thus, we obtain a simplified risk it follows that 1
bound R(h) < ((B;n, 5) where ((B;n, == 4B log 4 +
sk² AT. With log B terms ignored, minimizing ((B; 8) over B yields optimal B and resulting risk bounds, respectively:
B x n 1/3 log 1/3 (13()
(10)
R(h) = R. (f) = (h) = - (0 .log/ (1/06)-
(11)
Furthermore, the asymptotic risk bound in 11 implies that R(h), (h), and Reha(() are all bounded by e with high probability if the sample size
22 3/2).
(12)
Comparison with the hybrid method 29 Kumar et al. 29 proposed hybrid recalibration approach that involves fitting a recalibration function in a parametric family H. which is then discretized using UMB. Note that the hypothesis class H may may not include the optimal recalibration function h3.pP p. If hj.p E H. using a similar analysis as above, we derive their high probability risk bound O ( log @ + ) under Assumption (A3) which achieves Ó(n when B" x vn, exhibiting faster decay than our R(h) O(n-2/3). While the faster rate is anticipated from employing parametric methods, we note that when h & H. their method exhibits inherent bias (approximation error) induced by parametric function fitting, whereas our method is asymptotically unbiased. This distinction is corroborated by numerical simulations in Appendix E.2
Proof sketch of Theorem I First, we demonstrate that the uniform-mass binning scheme B = {1) 16 satisfies two regularity conditions with high probability, when the sample size is not too small. Specifically, we show that (i) B is welln-balanced [29] with respect to fX), resulting in B bins having comparable probabilities (Lemma] 3); and that (ii) the empirical mean in each bin of B uniformly concentrates to the population conditional mean of Y conditioned on f(X) being contained within the bin (Lemma 4 Thereafter, we prove that if B satisfies these properties, then the calibration risk Real and the sharpness risk Raha can be upper bounded as stated in Theorem [ see Lemmas 5 and [nd (or Lemma ( (oldss, The detailed proof is in Appendix B
Recalibration under label shift
This section extends the results from Section to address label shift. In Section 5.1 we introduce the label shift assumption (Definition 7) and reframe the recalibration problem accordingly. We show that composition of the optimal
the optimal recalibration function in this context recalibration function (cf. Section 3 and a shift correction function. Building on this observation, we propose a two-stage estimator in Section 5.2 where each stage estimates one of the component functions. The composite estimator's 's overall performance is supported by theoretical guarantees.
be expressed
5.1 Revisiting the problem formulation
Let P and Q denote the probability measures of the source and the target domains, respectively. We assume P and Q satisfy the label shift assumption defined below.

---

Definition 7 (Label shift), Probability measures P and Q are said to satisfy the label shift assumption the following two conditions are satisfied:
(B1) P[X E B = = B for all ls E {0,1) and all B E B(x).
Y
(B2) P|V=1| = 1] (0, (an QY = = E (0,
According Condition (B1) the class conditional distributions remain the same, while the marginal distribution of the classes may change. Condition (B2) requires all classes to be present in the source population, which is a standard regularity assumption in the discussion of label shift [3 14] it also
posits the presence of every class in the target population.
Optimal recalibration under label shift. Under the label shift assumption between P and Q, we define the label shift correction function g" Z + such that
w z
Q|Y = k] P[Y k]]
(2) w 2 + w
where
wx
4k E {0, 1}.
(13)
The conditional probabilities under P and Q can be related 45 as follows:
Q = x E B) 9" (PlY = B)
AB E ((x).
(14)
Recall that the optimal recalibration function for predictor ʃ X' - 2 under probability measure P is defined as hi, (=) = Ply = 1 s(X) = =|: see (7). In the presence of a label shift between P and Q, we may write the optimal recalibration function for f under Q as
h =9" hj.p
(15)
(b) g" (PLY = f(x) = 2]) (d) (g* ((ohj,p) (z),
because (=))(=) QI = 1 ((x) - =]
where (a) and (c) follows from the definition of h and (b) is due 14
Recalling the definition of the risk Rp( from (5) we observe that Ro (hh J) 0, which is consistent with the risk characterization of the optimal recalibration. Our goal is to estimate the optimal recalibration function , = g" o hi, from data.
Problem 2 (Recalibration under label shift). Suppose that we have measurable function x Z and two IID datasets Dp = (z,, 34 M) P and DQ = (24, no ~ ~Q. The goal of recalibration under label shift is to estimate h = h11q using f, Dp and Dq.
The source (training) dataset Dp may not be accessible due to privacy protections, proprietary data, practical constraints, as is often the case when recalibrating a pre-trained black box classifier to new data. In these cases, it suffices to have estimates of the recalibration function hy.p and the marginal probabilities PLY k), k {0, 1) under P. for our method and analysis.
Remark 2.
5.2 Two-stage recalibration under label shift
Method. We propose a composite estimator of hij. g" o hijpp which comprises two estimators g g" and hp se hj,PP. Here we describe a procedure produce this composite estimator.
1. Use Dp to construct hp Z - E, the estimated recalibration function 9 (for f under P).
2. Use Dp and De construct ğ Z such that
QIY k]
((2)
where
ih PLy k]]
4k E {0,1],
(16)
و z + 1i( 1 - 2)
where P|y = k) : pr
1Prl
[ly = k] and QJY = k] := Doo ΣBe
|Pol
1|p = k) are the
empirical estimates of the class marginal probabilities.
3. Let
ha 9 hp.
(17)
Note that the recalibration estimator hp (Step 1) remains the same with that in Section 4.1 Fur-
thermore, the shift correction estimator ğ (Step 2) is a plug-in estimator of the label shift correction function g" in 14) based on the estimated weights, w; and wp.
7

---

Theory. We present a recalibration risk upper bound for the proposed two-stage estimator. We let Pk == P|Y = k). 9b == Q1 xi), and w 2h for E {0, 1). Moreover, let pmin = ming Pk. Amin = ming Pk. Wiin- == ming wa and wmxx == max; wi..
Ph
Theorem 2 (Convergence of hq)). Let P.Q be probability measures and let f x:X E be measurable function. Let Dp be an HID sample of size up and Da ~ Q be an HID sample of size no. Suppose that Assumptions (B1) & (B2) hold. Let B be the UMB scheme induced by Dp.
Let hp h be the recalibration function (9) based on B, and let 9 denote the shift correction function as defined in (16). Then
R2 (g o hp) 2
Po P1
+ P1
+
w RR (hp::p
min
2
where
Pk: :=
Wk E
k
{0,
1].
(18)
Furthermore, suppose that (AI) such that for any 8 (0, 1).
(A2) & (A3)
hold. Then there exists universal constant c
27
4|B]| [B] log
27
16
T&P Z max
and
no 2
log
Punin
8
Umin
8
then with probability at least 1 - 6,
2
Rø o hp) S 2 max min
3
8||3|
1
8K2
log
+
2
2([np/1
1)
5
npp/
[B]
|
(19)
1
16 (
+ 54 max
log
Pmiin n2 qmin nQ
Remark 3. Note that Pk -> 1 np, iq oc, and thus, the upper bound (8) reduces to
2 Wiuaa Rp Rp(hp;)), Moreover, when P Q, we have whin =wim 1, and this further simplifies to the recalibration risk without label shift, up to multiplicative constant 2.
Remark 4 (Target sample complexity). Assume that np 2 nQ and the number of bins satisfies -2/3 + na²)). This result indicates that [B] x ppp 1/3 Then (19) implies R2(g a hp:f) = Omp D(p2/3
the proposed recalibration method using (17) requires significantly smaller larget sample size no ((a-1) to control the risk, as compared no Q(e-3/2 in (12).
Remark 5 (Comparison with label shift using unlabeled target data). When the source sample size mp is sufficiently large, achieve a risk of RQ(9 hp) Onn'') with high probability. It is important note that in this scenario, only utilize the labels from the target sample to address label shift. Remarkably, the same rate applies when employing the algorithms proposed (37 14). which solely rely features from the larget sample, For proof sketch, please refer to Appendix
6 Numerical experiments
In this section, we present the results of our numerical simulations conducted to validate and reinforce the theoretical findings discussed earlier. The simulations based family of recalibration functions called beta calibration [28]: Hoeu = (hoca (2; a, b, c) a 2 0, b 2 0, c E R), where
hheaa ( b) 1] - [0, 1] is defined
N (2; a, b.
(20)
1 1+1/ c
In addition, consider the joint distributions D(r)) of X and Y, where Y ~ Bermoull( X Y N 1). and X Y N22 1). and a pre-trained probabilistic classifier fz) (xx)
1/(1 + e -²)). To accommodate the limitations of space, we summarize the results in Figure 1 3
providing a concise overview. Detailed information about the simulation settings, implementation details, and further experimental results and discussions can be found in Appendix
and Table I
Our simulation code is available at lhttts://// thub. http://hhhhc.ccc/eeee//////aaaaa label
shift
8

---

10-1
Calbration Rikk
10-1
10
Calbration
1.0"
10"4
Shappesss
10
10-1
10
B-34
8-
4.6-09
Re
10"4
n-1,0cm
6,00+03
B::04
10"
22e+05
10a
2
10
107
104
10a
(a) Roal vs. n
(b) Roal (h) vs.
(c) R (h) vs.
(d) R(h)
Figure I: Medians (solid lines) and 10-90 percentile ranges (shaded areas) of quadrature estimates of
population risks over 10 realizations and theoretical risk upper bounds (ó 0.1) (dashed lines) for
various and B. (a)-(c) The empirical rates, R On 0.39 po.95) and R (DB--1833))) align
with theoretically predicted rates, O(B/n) /n) and O(B-²), in Thm. (d) The empirically observed R and our upper bound exhibit similar trends as a function of B.
10-2
2000
Opiimal
1500
Optmall
1.0
2.2e-06
experiment theary
500
4.6e400
10a
nt2
105
10a
10a
10
Figure 2: The optimal number of bins B for different sample sizes n plotted linear scale (left) and log scale (middle), and the population risk for various combinations of and B, with the optimal B marked by black dots (right). Note that the risk surface relatively smooth around its minimum, suggesting the robustmess of the optimal B.
Table 1: 90% -0%-quanile of the risks of Platt scaling [40] the hybrid method 29 uniform-wizd binning (UWB) (18), and uniform-mass binning (UMB) over 100 random calibration datasets drawn from ~ Uniform(0. 1], and (a) Y 2 ~ Beemouull(/nenn (2; (2;4, 4, 0)), or (b) Y Z ~ Bernoulli (Avee (z; 0.1, 4, 0)). While Platt scaling and the hybrid method achieve lower R under the correct parametric assumption, UWB and UMB may outperform when the parametric assumption fails.
(a) Correct parametric assumption
(b) Misspecified parametric assumption
Metric (x (x10-3)
Real
Reha
R
MSE
Metric
Real
g
MSE
(x10-3)
Platt
0.122
0.000
0.122
10.338
Platt
3.682
0.000
3.682
21.994
Hybrid
0.119
0.212
0.315
10.532
Hybrid
3.117
0.251
3.360
21.672
UWB
0.661
0.194
0.855
11.071
UWB
0.572
0.238
0.810
19.122
UMB
0.647
0.212
0.839
11.055
UMB
0.560
0.251
0.797
19.109
Table 2: Risks under label shift from D(0.5) to D(0.1), with 103 and no 102. Standard deviations are computed from 10 random realizations. LABEL-SHIFT, only applying an injective 9.
achieves Rsha = 0 but incurs high Real, SOURCE, recalibrated with B np on Dp, incurs high 1/3 Real TARGET, recalibrated with = ni on Do. incurs low Real Our proposed COMPOSITE
achieves the lowest nonzero Reha and lowest Real
Method
Estimator
Real
Aphha
R
MSE
SOURCE
hr
0.016:10.005
0.0032+10.0014
0.01910.006
0.029=000006
TARGET
uugett
0.0020=#0.0025
0.049:40.000
0.05110.000
0.060-10.006
LABEL-SHIFT
0.026:10.006
0
0.026-10.006
0.035
COMPOSITE
hg
0.00019=0.00017
0.0032+00.014
0.003410.0013
0.0127+000013

---

1.0
1.0
Empirical Frequency
Empirical Frequency
0.8
0.8
0.6
0.6
h
0.4
Platt
0.4
Platt
Hybrid
Hybrid
0.2
UWB
0.2
UWB
UMB
UMB
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
Predicted Probability
Predicted Probability
(a) Correct parametric assumption
(b) Misspecified parametric assumption
Figure 3: Optimal recalibration function ht and recalibration function estimates by Platt Scaling
40 the hybrid method (29]. UWB, and UMB when the parametric assumption is (a) correct and (b) misspecified. UMB traces the he in both cases, whereas the hybrid method traces Platt scaling, exhibiting an intrinsic bias from h" in (b).
7 Discussion
This paper presents a comprehensive theory for recalibration, considering both calibration and sharpness within the nean-squared-error (MSE) decomposition framework. We use this framework to quantify the optimal calibration-sharpees balance and establish rigorous upper bound on the finite-sample risk for uniform-mass binning (UMB). Additionally, recalibration under label shift with limited access to labeled target data. Our proposed two-stage approach effectively estimates the recalibration function using ample data from the source domain and adjusts for the label shift using target domain data. Importantly, our findings suggest that transferring a calibrated classifier requires a significantly smaller target sample than recalibrating from scratch on the new domain. Numerical simulations confirm the tightness of the finite sample bounds, validate the optimal number of bins, and demonstrate the effectiveness the label shift adaptation.
address the challenge of
In concluding this paper, we identify several promising directions for future research.
Relaxation of the assumptions would be worthwhile to explore whether or not the assumptions made in our analysis could be relaxed. For instance, the widely adopted monotonicity assumption (A2) and its variants
[5] 52 43 44 may not hold in real-world settings. Thus, exploring potential relaxations of this assumption is valuable. In addition, a mild but non-trivial smoothness assumption
(A3) (c.f. Remark and 8 introduced obtain tight sharpness risk upper bound (c.f. Remark 9); investigating its practical implications and exploring potential relaxations could be interesting future work.
Calibration-sharpees framework analysis Applying framework analyze recalibration methods beyond UMB, such as isotonic regression (5T) and kernel density estimation [52), can offer further insights into their performance and properties, providing guidance practitioners in selecting suitable algorithms based on specific conditions and requirements.
Multiclass probability recalibration The concept of calibration considered in this work extends to multi-class classification settings, known canonical calibration [48). Weaker, but more tractable notions of multi-class calibration have also been explored in the literature [48] 21). While partition- based methods, multi-class extensions of binning methods, known to have consistency [48] and vanishing calibration error [41], establishing upper bounds for their sharpness risk remains difficult. Additionally, designing partition scheme in multidimensional space is challenging task [21]; the interplay between calibration and sharpness could potentially guide the development of partition strategies that balance both aspects in multi-class classification.
Applications to real-world data Investigating the calibration interaation-saapnness tradeoff in real-world applications, which often involve multiple classes, presents an interesting challenge. is crucial to develop effective estimators for both calibration risk and sharpness risk in such scenarios. While
estimators for calibration risk exist (e.g., binning-based and KDE-bbased [6] 29 52 42 and lower
bound for sharpness risk has been established [39], direct estimator of sharpness risk is still lacking.
10

---

Acknowledgments and Disclosure of Funding
The research this paper was partially supported by ARO grants W911NF-23-1-0543 and W91 INF. 19-1-0269 and by DOE grant DE-NA0003921.
References
[1] John Aitchison and Sheng M Shen. Logistic-norne normal distributions: Some properties and uses. Biometrika, 67(2):261-272, 1980.
[2] Amr Alexandari, Anshul Kundaje, and Avanti Shrikumar. Maximum likelihood with bias- corrected calibration is hard-to-beat at label shift adaptation. In International Conference Machine Learning, pages 222-232. PMLR, 2020.
[3] Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang. and Animashree Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations, 2018.
[4] Jarostaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pages 1727-1740, 2023.
[5] Glenn W Brier et al. Verification of forecasts expressed terms probability. Monthly Weather Review, 18(1):1-3, 1950.
[6] Jochen Brücker. Estimating reliability and resolution of probability forecasts through decompo- sition of the empirical score. Climate dynamics, 39:655-667, 2012.
[7] Dallas Card and Noah Smith. The importance of calibration for estimating proportions from annotations. In Proceedings of the 2018 Conference the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pages 1636-1646, 2018
[8] Misty Crown. Validation of the NOAA Space Weather Prediction Center's solar flare forecasting look-up table and forecaster-issued probabilities. Space Weather, 10(6), 2012.
[9] A Philip Dawid. The well-calibrated Bayesian. Journal of the American Statistical Association, 776379):00--610, 1982.
[10] Morris H DeGroot and Stephen E Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series (The Statistician). 32(1-2):12 1983.
[11] Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 295-302, 2020.
[12] Charles Elkan. The foundations of cost-sensitive learning. International Joint Conference on Artificial Intelligence, volume 17, pages 973-978. 2001.
[13] Andrea Esuli, Alessio Molinari, and Fabrizio Sebastiani. A critical reassessment of the Saerens- Lateste- algorithm for posterior probability adjustment. ACM Transactions on Information Systems (TOIS), 39(2):1-34, 2020.
[14] Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. unified view of label shift estimation. Advances in Neural Information Processing Systems, 33:3290-3300, 2020.
[15] Tilmann Gneiting and Adrian E Raftery. Weather forecasting with ensemble methods. Science,
3 310(5746):248 249, 2005.
[16] Tilmann Gneiting and Adrian E Raftery. Strietly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):39--77, 2007.

---

[17] Sebastian Gruber and Florian Buettner. Better uncertainty calibration via proper scores for classification and beyond. Advances in Neural Information Processing Systems, 35:8618-8632. 2022.
[18] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[19] Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-fre free binary classifi- cation: Prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems,
2020.
[20] Chirag Gupta and Aaditya Ramdas. Distribution-free calibration guarantees for histogram binning without sample splitting. In International Conference on Machine Learning, pages 3942-3952. PMLR, 2021.
[21] Chirag Gupta and Aaditya Ramdas. Top-label calibration and multiclass-to- binbary reductions. In International Conference on Learning Representations, 2022.
[22] Chirag Gupta and Aaditya Ramdas. Online Platt scaling with calibeating. In International Conference Machine Learning, 2023.
[23] Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchis- escu, and Richard Hartley. Calibration of neural networks using splines. In International Conference on Learning Representations, 2020.
[24] Yingxiang Huang, Wentao Li, Fima Macheret, Rodney A Gabriel, and Lucila Ohno-Machado. tutorial on calibration measurements and calibration models for clinical prediction models. Journal of the American Medical Informatics Association, 27(4):621 2020.
[25] Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila Ohno-Machado. Calibrating predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263-274, 2012.
[26] Volodymyr Kuleshov and Percy S Liang. Calibrated structured prediction. Advances in Neural Information Processing Systems, 28, 2015.
[27] Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with Dirichlet calibration. Advances in Neural Information Processing Systems, 32, 2019.
[28] Meelis Kull, Telmo M Silva Filho, and Peter Flach. Beyond sigmoids: How to obtain well- calibrated probabilities from binary classifiers with beta calibration. Electronic Journal of Statistics, 11:5052-5000 5080, 2017.
[29] Ananya Kumar, Percy Liang, and Tengyu Ma. Verified uncertainty calibration. Advances in Neural Information Processing Systems, 32, 2019.
[30] Donghwan Lee, Ximmeng Huang, Hamed Hassani, and Edgar Dobriban. T-Cal: An optimal test for the calibration of predictive models. arXiv preprint arXiv:2203.01850 2022.
[31] Zachary I. Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. International Conference on Machine Learning, pages 3122-3130. PMLR, 2018
[32] Allan H Murphy, new vector partition of the probability score. Journal of Applied Meteorology and Climatology, 12(4):595-600, 1973.
[33] Allan H Murphy and Edward S Epstein. Verification of probabilistic predictions: A brief review. Journal of Applied Meteorology and Climatology, 6(5):748-755 1967.
[34] Allan H Murphy and Robert I. Winkler. Reliability of subjective probability forecasts of precipitation and temperature. Journal of the Royal Statistical Society Series C: Applied Statistics, 26(1):41-47, 1977.
12

---

[35] Allan H Murphy and Robert L Winkler. A general framework for forecast verification. Monthly weather review. 115(7):130-1338, 1987.
[36] Mahdi Pakdaman Nacini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using Bayesian binning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[37] Khanh Nguyen and Brendan O'Connor. Posterior calibration and exploratory analysis for natural language processing models. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1587-1598, 2015.
[38] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
[39] Alexandre Perez-Lebel, Marine Le Morvan, and Gaël Varoquaux. Beyond calibration: Estimat- ing the grouping loss of modern neural networks. In The Eleventh International Conference on Learning Representations, 2023.
[40] John Platt. Probabilistic outputs for support vector machines and comparisons regularized likelihood methods. Advances in Large Margin Classifiers, 10(3):61-74, 1999.
[41] Aleksandr Podkopaev and Aaditya Ramdas. Distribution free uncertainty quantification for classification under label shift. In Uncertainty in Artificial Intelligence, pages 844- 853. PMLR, 2021.
[42] Teodora Popordanoska, Raphael Sayer, and Matthew Blaschko. A consistent and differentiable lp canonical calibration error estimator. Advances in Neural Information Processing Systems, 35:7933-79483 2022.
[43] Amir Rahimi, Amirreza Shaban, Ching-An Cheng, Richard Hartley, and Byron Boots. Intra order-preserving functions for calibration of multi-class neural networks. Advances in Neural Information Processing Systems, 33: 13:13666-3347, 2020.
[44] Rebecca Roelofs, Nicholas Cain, Jonathon Shlens, and Michael C Mozer. Mitigating bias in calibration error estimation. In International Conference on Artificial Intelligence and Statistics, pages 4036-4054. PMLR, 2022.
[45] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of classifier to new a priori probabilities: A simple procedure. Neural Computation, 14(1):21-41, 2002.
[46] Zeyu Sun, Monica G Bobra, Xiantong Wang. Yu Wang, Hu Sun, Tamas Gombosi, Yang Chen, and Alfred Hero. Predicting solar flares using CNN and LSTM on two solar cycles of active region data. The Astrophysical Journal, (31 2022.
[47] Junjiao Tian, Yen-Cheng Liu, Nathaniel Glaser, Yen-Chang Hsu, and 7solt Kira. Posterior re-calibration for imbalanced datasets. Advances in Neural Information Processing Systems, 33:8101-8113, 2020.
[48] Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration in classification. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3459-3467. PMLR, 2019.
[49] Jonathan Wenger, Hedvig Kjellström, and Rudolph Triebel. Non-parament calibration for classification. In International Conference on Artificial Intelligence and Statistics, pages 178-190. PMLR, 2020.
[50] Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 609-616, 2001.
[51] Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 694-699, 2002.
13

---

[52] Jize Zhang, Bhavya Kailkhura, and T Yong-Jin Jin Han. Mix-n-match: Ensemble and compositional methods for uncertainty calibration in deep learning. International Conference on Machine Learning, pages 11117-11128. PMIR, 2020.
[53] Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh, Calibrate before use: Improving few-shot performance language models. In International Conference on Machine Learning, pages 12697-12706. PMLR, 2021.
14

---

A Proof of Proposition 1
Proof of Proposition First of all, recall the definition of the risks from 3 and (4
Real (h; [) IE [S(X) - EY [(X)))
R (h: f) E [E h f(x) EY f(x)))
To keep our notation concise, we use fX) as a shorthand notation, and also let Yz := -== and Yx2))
EE[Y I()] throughout this proof. We can decompose the recalibration risk from
Definition
3
R(h) E[(h(Z) Y2)²1
B[(h(Z) YM(2) + VR(Z) - 12)
E[(M(Z) Yx(2)) + =[(((())
- (x(2)((M22) - V2)
E[(h(Z) \) B[(Yn()) 12) (B(B((((() (((2))((((2) Y2) h(Z)]]
=E(((Z) - (1 B[(((()) 12) 2B((h(Z)) (x(2))( 1[|22 (())]]]
-E[(N(Z) )2 + B(((())) 12) 22E(((Z) (((2)) Yx(2))
-E((NZ) ) ([(()()) - 12)1
((O((A)
(N)
B Proof of Theorem 1
In this section, we present proof of Theorem Let (Y, J x be random variables that admits a joint distribution Py.z, which we assume to be fixed throughout this section. Let S= {(), 23) E y x Z : [n]} and let (cf. Definition 6 of size B induced by (2, s in) S. Note that if S is random sample from Py.2: 2, then the binning scheme B induced by is also a random variable following a derived distribution. To facilitate our analysis, we introduce the notion of well- bell-balanced binning.
I2....... IB] be the uniform-no mass binning scheme
ballneal binning; (2 Let B E N. let Z be a random variable that takes value in [0, 1), and let E IR such that a 2 1. A binning scheme B of size B is a-well-baat balanced with respect to Z if
Definition
oB < PIZE
a B' bbe
In addition, we define two (parameterized families of) Boolean- valued functions balance and & upproox as follows: for any binning scheme B,
Va R
Phalance (B; =
1
S
PIZEE
S B
VI B].
(21)
[3|
Ve E R, T Pppprox (B:s) == max 10r μ - {
(22)
IEB
where 1(A) = 1 if and only the predicate A is true, and for each interval E B,
pu Σi Vi (21) and
B(y,)) Y 1Z)).
(23)
Σ (z))
Note that if Pbllace (B:a)
for > 1, then B is a-well-balanced with respect to Z (cf. Definition (oopproxx::B] (B:e) = 1 for e 2 O, then the conditional empirical mean Y in each bin / B approximates the conditional expectation with error at most e, uniformly for all bins.
8). Also, appprux
The rest of this section organized as follows. In Section B.
we ensure that for an appropriate choice of a E IR, it holds with high probability (with respect to the randomness in B) that @balance [: a) = & Papprox (B;e) = 1. Section B.2 we establish upper bounds on the reliability
risk Real and the sharpness risk Reha under the premise that &halance (B; a)) = $ aapprox (B:e)
Finally, in Section B.3 we conclude the proof of Theorem by combining these results together.
15

---

B.1 Highh-probbbility certification of the conditions
Well-balanced binning scheme. First of all, we observe that the uniform-bas binning scheme induced by an IID random sample from Py.z is
with high probability, if the sample
size is sufficiently large. Here we paraphrase result from (29 our language.
Lemma (129) Lemma 4.3]). Let S = {Z:: E } be an IID sample drawn.rrmm Pz and let B be the uniform-mass binning scheme size B induced by S. There exists a universal constant é'
such that for any 6 E (0, 1), if 2 e. log(B//g then Pbalanco (B, 2) = 1 with probability at least 1 6.
Lemma B states that
B ②
n 2 c B log
P [ is 2- 2-well- well-balanced with respect to Pz] 2 1
While the value of the universal constant that one may set, for example, c' 2420, which can be verified by following their proof with c' kept explicit.
specified in the original reference 29 we remark
The proof of Lemma in (29 relies on a discretization argument that considers a fine-grained cover of z = [0, 1] consisting of disjoint intervals-namely, {1) j E [10B]] such that PiZ E 1 InF for all j [10B]-and then approximates each Io by subset of the cover. As the authors of [29) remarked, this argument provides a tighter sample complexity upper bound than naïvely applying Chernoff bounds or standard VC dimension argument, which would yield an upper bound of order
0 ( log ().. We omit the proof of Lemma and refer interested readers to the referenced paper 29 for more details.
Uniform concentration of bin-wise means. Next, we argue that for the uniform-man mass binning scheme B induced by an IID sample, the conditional empirical means of each bin concentrates to the population conditional expectation, uniformly for all bins in B. Here we restate a result from (2)
Lemma 4 (20) Corollary IJ). Let Pz be an absolutely continuous probability measure on Z = [0, 11. and S {Z, : E [m]} be an IID sample drawn from Pz. Let N such that I u and B be the
mass binning scheme of size B induced by S. Then for any 8 E (0,1),
1
2B
1
P Papproxx (B) 1] 2 1-5
where
2[LnBB] log
(24)
[n/B]'
Lemma states that under the mild regularity condition of Pz being absolutely continuous, the uniform-mass binning accurately approximates all bin-wise conditional means as long as there are at least two samples per bin in the sense that
2B
2B
P
sup bEIB)
uol S
2[[nBB] - 1) log
2 1 5.
n/ B
B.2 Conditional upper bounds reliability risk and sharpness risk
In this section, we establish upper bounds on the reliability risk Real and the sharpness risk Reha for l under the premise that F (B: (B) = 1 and $ approx (B; é) = for appropriate parameters 0,& R.
To avoid clutter in the lemma statements to follow, here we recall our prob- lem setting and set several notation that will be used throughout this section. Recall that P = Px,y is a joint distribution on X x y and let f X' + Z a measurable function. In addition, we let Š = { y:) E X x y : E [n]]} be an IID sample drawn from P, and let = ((. Z x y: (I, v) and 2 = f(x) Let be the uniform-man mass binning scheme induced by (z's in) S, and let h B -
Preparation.
+ Z be the recalibration function derived from B as described in Section 4.1 ( The dependence among P, f, S, B, and h are summarized by diagram in Figure
Furthermore, we define the index function for binning scheme to facilitate our analysis.
16

---

P
S
B h
Figure 4: Stochastic dependence among P.f, and h.
Definition Let be a binning scheme. The index function for B the function B: [[]]] such that
B(2) Σ (0 (z).
(25)
IEB
Remark 6. Note that B is measurable function and defines an index function that identifies which
bin of B the argument 2 E [o, 1] belongs to. Specifically, suppose that B = {II...., .....,.Ip IB 1B} for some B E N and there exists up, U1..... ............ ug [0, such that (i) ug < U1
< uu and (ii) 1b (46-1, uo] for all b [B] {1} and 1 [ua, u1). Then 3(z) = if and only if 1--
B.2.1 Calibration risk upper bound
We observe that if binning scheme B produces empirical means ju, that approximate the true means 14, with error at most e, then the calibration risk is upper bounded by e².
Lemma (Calibration risk bound). For any 2 if t approx (B; e) then Real (h; f, P) S?
To begin with, we recall the definition of the calibration risk (Definition 3). and let Z = f(X). Then may write
Proof of Lemma 5
(h(2) - EEI h(22)) |
1e0al (h; P) IE
[(b(2)) B|Y h(2))) 3(2)
E
1. the law of total expectation
E (Aigc2) - (1Dr1)) )²1
max (ir - -m1)² TEB
Note that if + approx ( = 1, then maxtes (βr - (fz-11) s c
We remark that the proof of Lemma iss simple application of applying Hölder's inequality. Also, we note that a similar argument was considered in (20, Proposition 1] to establish the inequalities between the T. cP-oottterparts of the calibration risk, which they call the ex-exeected calibration error (ECE). In this work, we focus on the case 2.
B.2.2 Sharpness risk upper bound
Next, present an upper bound for the sharpness risk that diminishes as the binning scheme B becomes more balanced.
Lemma (Sharpness risk bound). Suppose that the optimal post-hoc recalibration funciionn h cf. monotonically non-decreasing. Let such that a 2 If balancee a) = 1, then
Rsba (he f.P) <
B
Proof of Lemma 0 Letting 2 = =((X,, we can write the sharpness risk of h over o with repsect to
P as
Raha (h; P) = (E M(z) E 2))²
17

---

We recall the definition of the index function 3 for B (Definition 9
and observe that
{(2)
E Y ) Y
S E
E
i( E Y ]
E Y [()
Y
Z 1
Σ
- Z 1,(2))
JEB
Σ TEB
E
E
E|Y
h(2)) - E Y 1 12) B(Z)]
v. the law of total expectation
Σ E
PiZ
E
E |B| M(z) E Z
Z E |
Remark 6
TEB
Σ JEB
P(z El
(spph),p(3) - inf m()p(z))
by definition of hipp; cf.
=El
=EI
<
Σ
a
(suphi
- -inf h f()(()))
Phalance (balance(B..)) =
[
sEl
IEB
IA
[
The inequality in the last line follows from the facts that (i) I are mutually exclusive and (ii)
hG kt)p(2)) E [0, 1] and hÿ,r p is monotone non-decreasing.
Our proof of Lemma However, note that we obtain an improved constant - 1 as opposed to 2 in 22 Lemma D.6]
6 relies on similar techniques that are used in [29 Lemmas D.5 and D.6].
with a more refined analysis.
An improved rate with additional assumptions. It is possible to improve the rate of the sharpness risk upper bound from 0(BB -) to O( with an additional regularity assumption on hj.p-
Recall that we assumed in (A3) that there exists K > 0 such that if 21 S 22, then hj. p),p(2))
h*) < K (F2 - Fz (z) that is, hÿ.p p is K-smooth with respect to Fz. This posits that the conditional probability P|Y = 1 = 2] of the target variable Y given forecast variable Z cannot vary too much in regions where the density of Z is low, where the forecast is rarely issued. This is a reasonable assumption because if PIy = 1|Z] changes too rapidly with respect to Z, then suggests that we need additional information about Y beyond what Z can provide in order to improve the quality of forecasts. We remark that (A3) is indeed a fairly mild assumption to impose on, however, is not trivial one.
Remark (Mildness of (A3) p. Suppose that Z = (X) has a density pz that is uniformly lower bounded by on the support of Z. hf is L-Lipschitz, then h is (L/e)-smooth with respect to Fz. This also provides sufficient condition to verify (A3) in practice.
Remark 8 (Non-triviality of (A3). Notice that even if Fz is absolutely continuous and hÿ,p con- tinuous, the smoothness constant K could become large if the prediction Z is heavily miscalibrated. For instance, in Figure 6 h (2) is changing fast in the interval [0.5, 0.75] where (2) is small, which results in a larger value of K that can even diverge if pz()) + 0.
Here we define the notion of gi-smoothness to formalize Assumption improved upper bound for the sharpness risk.
(A3) and then present an
Definition 10 (bl-smoothness). Let E R2 and db [0, 1] - [0. 1] be a monotone non-deceeasing function. A function Φ [0, 1] + [0. 1] is K K-smooth with respect to v for any 21, 22 E [0, 1] such
that 21 S z2.
(x(22) - db21) < K (1(2)) 1 v²(=)).
(26)
Lemma 7 (Improved sharpness risk bound). Suppose that the function h;,p(2 defined in 7 is
monotonically non-decreasing and K-smooth with respect Fz for some K 2 O. where Fz is the
cumulative distribution function of Z = fX).. If Phatance (B, a) = 1, then
K²a²
Roha -
B²
18

---

Proof of Lemma 7 Let Z = f(X) and B = [B]. For each b E [B], we let 2b.max == -sup Io and
2b,min = inf 1.. Then we have
R fr; P)
( h(2)) - EY =
= E
-E
E EE Y h[z)] - E YY z [(Z)]
Σ
PIZ Tb] IE ( [(2)) F 2))² ((Z) =b]
PIZ E 1ol. (2j,p(20.max) - (2
: hj.p non-decreasing
PIZ E In] (K. (Fz((,2))))x)) - Fz F2((2,mmn))
hj.p is K-smooth w.r.t Fz
1=1
Σ
K². .Ilz E ln)
$ K2
Σ
a
$ balance CaailanceeBB,0 a) =
B
b=1
K203
= B²
Remark 9 (Tightness of the rate OB-2)). The asymptotic rate Reha 2 is tight and cannot be further improved without additional assumptions. For instance, let 's consider uniform-mass binning of size B on Uniform(O,) 1). the population limit, each bin has width 1 and within- bin variance 1/(12B3). Thus, the sharpness risk, obtained by taking expectation of the conditional variance (per each bin), 1/(12B²), attaining the rate B-2.
B.3
Completing the proof of Theorem 1
Proof of Theorem 4
For given 8 (0, 1), let 81 = 82 8/2. Then we observe that
B
2 c | log 81
(.aaaanccBB.11 = 1] 2 61
by Lemma
n 2|
approxx (B, Es2) = 1] 2 82
by Lemma
where d' 0 is the universal constant that appears in Lemma and
1 log
2 [
EB2 - 2( [B] -
82
n/ [
Observe that 6, = < and B 2 1, and thus, log
[8]
log 2. Letting maxtd', logz) and
applying the union bound, we have
2||B|
c- [ log
P Palaace (B,2) and 4 Papprox (B, = =1] 2
Next, we observe that if Pbalance (B, 2) and & ( 1, then
Real (h; f: P) < (Eá,)²
by Lemma
2
Roha (h; P) <
by Lemma 6
B
19

---

Additionally, if the Assumption (A3) also holds, then we obtain stronger upper bound on Rehs (h; f, P) by Lemma
8K
Reha P. <
C Proof of Theorem 2
This section contains proof of Theorem 2 Prior to the proof, Section C.1 we provide several lemmas that will be useful in our proof. Thereafter, we present proof of Theorem in its entirety in Section
C.1
Useful lemmas
C.1.1
Concentration of wh to w
First of all, we recall the binomial Chernoff bound, which is a classical result about the concentration of measures that can be found in standard textbooks on probability theory.
Lemma (Binomial Chernoff bound). Let X, be IID Bernoulli random variables with parameters
E (0, 1), and let S, = E 11=1 X, Then for any ó E IR such that 0 < E < 1,
2²
Pls, 2 (1 + t)pl S exp
11
3
P(., $ (1 - e)pl & exp
2 11
follows from Lemma
8 that for any s, E (0, 1),
2
Sn pl
n 2 =2p
log
=
I 6.
(27)
Let P, Q be two distributions on y [0, 1}, and let Dp P. DQ ~ Q denote IID samples of size
n,, nQ. respectively. Recall from
13 and (16) that for each k {0, 1}, we define
Pol Y
PD. IY = k]
w
and
wk
Pp = k}
Ppp Y ki
Then, let
W w
W1 w
Po
and
P1 ==
(28)
Now we define another parameterized family of Boolean-valued functions Pratio Pratio(Dp, Do; 3) as follows. Given Dp P. P. Q, and 3 E R such that 1 < < 2,
{ [ mh 8, Wk E (0.
Pratio (D,, PQ: 3)
(29)
Corollary 9. Let P. two distributions on y {0. 1}, and let Dp P. DQ ~ Q denote IID
samples of size nQ, respectively. For each le E 1), let Ps == Pp k and := Pq
k). Likewise, we let Pk = ap EyED, 1 = k} and dR = 1 Σ Ey 1 k}. For any
aq
8 E (0, 1) and any 3 E (1,2), if
27
8 8
27
np 2 (3 2)2 min Po. Pid
log
and nn 2 (B - 1)2 min go. 91
log
then
P ( (DD, (Dp, 1) 8 8.
20

---

Proof of Corollary 9 Let = 8-1 Since 1+z I 1 + 3z for all x' E [0.1/3], we have
3
I-x
3
148
1
<
1+E
2 3. Then it follows from
(27) that for each k E {0,1}, 1}.
I-
3
8 8
Pk
Pk
Rp 2
log
P
8
5
4
3
8
1ák
qk
nQ 2
log
8
q
Applying the union bound, we obtain the following implication:
3
8
3
8
np 2² (po.pp p1}
log
and no
log
8
E² "mii
q0. q1
8
P&
PM
[K-
P
max
max kE(0,1}
88
(E(0,11)
Pk
9k
1 +
1 -
P
max Pk
min Pk <
S 8
kE(0,11
1-E
(E(1,1)
1 E
1
P
max Pk (0(1)1)
min Pk < kE(0.1)
3 S..
C.1.2 Regularity of the Shift Correction Function
Lemma 10. Let w (wo, W1) E R² such that Wo: W1 > 0 and we + = 1.
The function
w1z Iw : [0, 1] + [0, 1] such that (z) #o0=- is L-Lipschitz where L = max
Proof of Lemma 10 First of all, consider the first-order derivative of gwi
d dz
W1 [wi2 + wo(1 - 2)] W (wi wo)
W w0
-w(2)
[ + wo - =)]² d
[wiz + wo - =)]
We observe that Iw is monotone increasing as J. (2) > 0 for all E [0, 1]. Next, we consider the second-order derivative of gw:
0, Va [0, 1]
if wo > w1.
2wowi: (wo w1)
d=2 Iw (z) (z)
0, Vz [0,
if wo W1. wo < wi
wiz wp(1 - =]]
< O, Va E [0,
Therefore,
d #e (0.1) dz (m)
d Iw (z)
if wo W1.
sup
==1
w1
if wo < W1.
1==
Lemma 11. Let P.O. Q be joint distributions of (X E X {0, 1), and let we
Y for
Y
e f 13, P.Q sutisfy the label shift assumption (Definition) 7. i.e., if Asssupptions (B1) and
(B2) hold, then for any measurable function f X + R, the following two-sided inequality holds:
[f) [x(]]
min (E
WEk
max Wk- kE (0(01))
(30)
Proof of Lemma 11 First of all, we observe that EQ [xx)]
EQ [[x][()]
by the law of total expectation
PolY k] [e()
k=0
Σ (wk- Pp = k)) Ep (X) YJ. by definition of wg the label shift assumption
Thus, it follows that min wa Er(f(X)] < [x] I max; we Ep(f(X)).
21

---

C.2 Completing the proof of Theorem 2
Proof of Theorem 2 This proof is presented in four steps. In Step 1, we establish simple upper bound for the risk Rg Rg(hq: f' that consists of two error terms: the first term quantifies the error introduced by the estimated label shift correction, å. while the second term quantifies the error due to the estimated recalibration function, hp. In Steps 2 and 3, we derive separate upper bounds for these two error terms. Finally, in Step 4, we combine the results from Steps 1-3 to obtain a comprehensive upper bound for RQ, which concludes the proof.
Step 1. Decomposition of RQ- Recalling the definition of the risk RQ. cf. ( we obtain the following inequality:
R2 Ra(h:: f) EQ
(h2o -x21)))))
ho f(x) 9" e hp o f(X) + g" o h f(X) E00
= Eq
(a)
(go f(x)) - 9" hp f(x))
$ 2
EQ
(31)
- Bo (0 o -
E 2 }}}
+ Eq
(32)
=/
where (a) follows from the simple inequality (a + 6)2 < 2(a² + 12) for all a, b E R. In Step 2 and Step of this proof, we establish separate upper bounds for the two terms, T2, T2.
Step 2. An upper bound for T1.
Recall from 13) and
16 that
wi=
Q k]
g" (z)
where
W
Ak {0,
w = wT(1 2)
P k]
Φ1 ((=) w1z v0
Q = k]
where
vk E 10.1}.
P k]
Let
w
11 Pi
Po
and
(33)
w
wi
Then we observe that for any 2 E (0, 1).
i1 wv( (1 2)
w
l0(z) g²(2
w1 z
w + w (1 2)
(wr w - wi wo) x(11 - =)
[10 + v0 - =)]
[wiz 2 + w/( (1 2)]
(w w (h)) . 2(1 - 2)
(w0 wō + w mho)
2( 2)
w wō w d0
wi wg + w voo
|Po p1l
+
Moreover, ((0) = (0) = 0 and 0(1) = 96 (1) 1. Letting -; hp o f(X), we obtain
2 Po P Po P1
Ti liq (B(2h) 9 99
(34)
remains to establish probabilistic tail bounds for po: Pl, which we will accomplish Step 4 of this proof.
22

---

Step 3. An upper bound for Tz. We observe that
g o hp f(X) - -EQl s(x1))
|
T- = Eq
g hp f(X) - g" (Eplly ((Xx)))
=
EQ
Label shift assumption, cf. (14)
max
EQQ (hip Eply s(X)))
is " Lipschitz, cf. Lemma 10 W min
wiin
Winax Wiin
(hx) Bply s(x))) 27
"inax Ep
by Lemma
w Waxx
Rp (pphpif))
2
min
Step 4. Concluding the proof. that
For given E 1), = 82 = 6/4 and 63 = 6/2. We observe
B
up 2 c' | log
p balance (B,2) - 1| 81
by Lemma 3
81
nP 2 2|3]
approx Ex,)
1] 2 82
by Leema
where d' > 0 is the universal constant that appears in Lemma and
1 log
[8] 82
Eb,
V 2( [l] 1)
+
n [|]
Furthermore, assuming
27 log
8
27
8
TPP min (po: PI
and
no
min
91
log
5g
we may define 36g as a function of n.p, ne and óg such that
1
}
63) (5). (35)
8
О8, (np, == max
27 log
np- min no min qo. 90.91]]
Then follows from Corollary that
P ( ratio Dr: Bn)
1-88 63.
Observe that 81 = 8 and
B 2 4, and thus, log
18 b,
2
log 16 2 2. Let c = d. Since e' 2
and log
log (20) log
notice that
%g
27
B
np 2 max
[
log
mint po. Po.
[
27
8
np max
[B] log
2|
log
82
min (Po. P1]
8g
In summary, obtain that for any given 8 (0, 1),
27 | log
4| 8
27
16
np 2 max {at min (po, p1]
and nn min ( go, 91
log
P T ballance (B, 2) 1 & T
approx B, Ea/4) = & T ratio (Dr: Dos B8/2)
1]
> - 8.
(36)
We remark that our decomposition of á into ò, 82, dg is arbitrary, and is intended to simplify the subsequent analysis.
23

---

Conditioned on the event Pbllance (B, = 1 & 4 (approx(B,E///) = 1 & Pratio (Dp, (D: B8/2) =
T1 v
Po P1
2
Ba/2
88/2
1
S (56/2 1)²
34
also, see
29
Po + P1
B6/2 + B8/2
T2 x
Rr (hp:f)
2
min
Wmax min
2
<
2
6//4
+
[B]
proof of Theorem T
Lemmas 5
Note that if Assumption (A3) holds, then we additionally have
W 3 T2
SK²
max w min
68/4
2
[
Inserting these upper bounds for Ti and T2 into complete the proof.
31.
32
and recalling the expression for (35
D Proof sketch of the argument in Remark 5
Recall our composite recalibration function,
he a hp,
(37)
does not use the features in Do- Specifically, 9 parameterized by d (10 i) which can be
estimated using only labels in Dp and DQ. cf. (66). According to Theorem 2 Ro(ho) = O
with high probability for sufficiently large np.
Now suppose we are given an unlabeled target sample with unknown label shift. We can estimate using the target features via maximum likelihood label shift estimation approach [14), yielding ML (uill, m and the calibrated classifier h f This results different composite
recalibration function than Equation (37).
ML. IQQ
MML hp,
(38)
where gML. [0, 1] + [0, 1] is defined as (z) 2/ (L + wi (1 2)). We claim in Remark 5 that, for sufficiently large np, the composite recalibration function in Equation (38)
achieves R (h
O with high probability, enjoying the same convergence rate as ho (Equation 37 Here we give proof sketch.
the maximum likelihood approach in [14 to estimate w. We want show ( On with high probability for sufficiently large np. Recall RQ(hq) s 2(T; T2) according to Equation (3T) and (32), and label shift estimation error only affects Tı, so sufficient show Ti ( ) with high probability.
Proof sketch. Suppose
For sufficiently large np, hp f is sufficient calibrated, so || 3 = O(n²') by Theorem 3 in [4] Since
Σ (pk 1)2 wiinn 2
Σ (px 1)2 wiin 2 max (px: - -1)2, (39) kE
kE(0,1)
kE
we have PI [1-a,1+ed aa] for & E {0, 1), where we can control a 0.5, which bounds T, in (34):
||0
O. For sufficiently small ||0 w
wr
Po P1
2a
11 wlle O(no))
Ti
<
< 2a
2
(40)
On + p1
2a
min
The rest of the proof are the same with Appendix
C.2

---

E Details on the experiments
In Section 1 and E.3 we consider family of joint distributions ((T)) of X and Y. where
Y ~ Bernoulli TT
Y = 0 ~ (-2,1) 1), and X Y = (2,, 1). Suppose we are given f()) (x)) 1/(1 + =) for E IR, as a probabilistic classifier. The optimal recalibration
function can be derived as
(=) PlY = 1 f(x) = = =
(41)
In Section E.2 we consider parametric family of recalibration functions called beta calibration 28
Hheta ( (,), 2 0, 2 0, c E RJ, where Whema (:3 a, b,c) [0, + [0. 1] is defined as
Nee (z) a, b,
(42)
1+ 1/ e (1-2)5
In addition, consider a subfamily Heggi normal C Haea defined as Hlogit-noma (Mogi normal (+; 0, c) = hreaa (-; a, a. c) aaaa (()aa-(()++c) : a 2 0, E R Apparently, the optimal recalibration function in
Equation 41 J E noogil-
E.1 Verifying results for UMB
First, we recalibrate f on data distributed as D(0.5) using UMB.
Verifying the risk convergence in Theorem 1
We vary n E [10? 107] and B E [6, 10 in the log scale. For each combination of (n, we use UMB to recalibrate f fnn data generated from D(0.5), and compute quadrature estimates of population (ea)(h), R (h), Rsha(h), and R(h). as well as The constant K in Assumption (A3) is selected
their high probability bounds based on Theorem [ by numerical maximization as
h" (²22)) hz)
K max US S PIz E [21,
Figure [sows the bounds follow the same trends as their associated population quantities, providing valid upper bounds in all cases.
Verifying the optimal choice of the number of bins. We find empirically optimal B*exprrmment that achieves the minimal risk for each choice of n. We compute the theoretically optimal choice of the number of bins, Betheory by minimizing the fimite-sample upper bounds. Figure 2 shows #eexprriment follows the same trend with Bethoory, both scales in O(n!/3).
E.2 Comparing recalibration methods
To highlight the benefits and drawbacks of UMB's nonparametric nature, compare UMB with (semi-pparametric recalibration methods in scenarios where the parametric assumption is correct and where it misspecified. We compare the method under study, uniform- mass binning (UMB), with other recalibration methods: uniform-widhe binning (UWB) [18), Platt scaling [40 and hybrid grrametric-binning method (29]. Note that Platt scaling and the hybrid method adopt the parametric assumption h" E Huugi
-Hugittnormal- normal-
For the first setting, we construct optimal recalibration function h² E Haugit so that the parametric assumption of Platt scaling and the hybrid method holds. In particular, we consider the distribution Z Uniform 00, 1] and Y Z Bernoulli (/oogit (Z; a, c)) with = and c 0. For the second setting, we construct ht" E Hreea but ht & Hingit-normal so that the parametric assumption fails. In particular, consider the distribution Z ~ Uniform(0, 1] and Y Z Bernoulli //beaa (2;a. b, c)) with = 0.1. b = 4, and c 0. For each setting, we fix calibration sample size to be n 5000.
*We say adopt the name "logit-normal calibration" after a simple example: Y = Bernoulli(0.5). Z gegit-Normal(pa,, +²") for i E {0, 1). then the optimal recalibration function E|Y Z 24 u4's and 7:'s. 's.
Logit-Normal(uug) Normal(u,, if (Z) ~ (², M. Similar to beta calibration 28 we
Aaggtttcormal (2; a2;
for some a, depending
"The original Platt scaling operates on outputs of real-valued SVM outputs [40). For probabilistic classifiers,
we follow [38 29 22] and implement Platt scaling by first transforming probabilities onto the real line via the
logit transform
25

---

Platt
Hybrid
Platt
Hybrid
UWB
UMB
UWB
UMB
0.1
0.01
0.01
Real
0.00
0.001
100g
100g
0.001
100μ
100
Raha
Ríha
10p
14
10
0.01
0.01
<c 0.001
0.001
100g
1000
5 100
1000
B
(a) Correct parametric assumption
(b) Misspecified parametric assumption
Figure 5: Risks number of bins B.
Risks as functions of the number of bins We traverse the number of bins E [10, 2000] the log scale and compare how each method behaves B changes. When the parametric assumption is correct, the hybrid method achives significantly lower Real and overall R than UMB and UWB for sufficiently large number of bins (Figure Sa). advantage highlighted in [29]. In contrast, when the parametric assumption fails, the binning methods UMB and UWB has better performance with the optimal number of bins (Figure 5b). This is because Platt scaling and hybrid methods are intrinsicly
biased when h² f Huggi narmall as noted in Section 4.2
Quantitative results of risks under optimal B For each setting, we fix B that achieves low recalibration risk for UWB and UMB in Figure 5 Specifically, choose B = 2 1/3 34 for the correct parametric assumption setting, and 1/3 17 for the misspecified parametric assumption setting. Then, for each setting, we compare the 90% quantiles of risks of each recalibration method fitted on 100 random replicates of calibration datasets of size n 5000.
Table 1 quantititively verifies that Platt and the Hybrid method achieves lower Real and overall the parametric assumption correct, and UWB and UMB achieves lower Real and overall R when the parametric assumption fails.
Visualization of calibration curves We fix the calibration dataset and visualize the calibration curves for all methods under the two settings. Figure 3 shows that the binning methods (UWB and UMB) closely track the optimal recalibration function h" in both settings. contrast, the hybrid approach follows the Platt scaling estimates, leading to an inherent bias from h" when the parametric assumption is invalid (Figure 3b
E.3 Comparing recalibration schemes under label shift
We consider the label shift with source distribution D(0.5) and target distribution D(mq), where TQ varies in {0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5). The results where TQ > 0.5 can be inferred by symmetry and hence not experimented. We vary np in {10, 10 10a 10" and n in {10, 10 10%).
26

---

1.0
Pglz)
Empirical Frequency
Aurget
Density
hl
0.0
0.6 Predicted Probability
Predicted Probability
Figure 6: Left: calibration curves of for COMPOSITE ha, SOURCE hp, TARGET he target and LABEL-
SHIFT 9. Right: the marginal density of Z = f(X) under Q
Aside from our proposed recalibration function ho = 9 o hp (7). referred to as COMPOSITE, we consider three other calibration approaches baselines: (1) SOURCE, denoted hp, which is only calibrated on the source data, (2) LABEL- -IIF,, denoted as 9. which performs label shift correction without calibration, and (3) TARGET, denoted as 92 which is only calibrated on the target data.
1/3 for TARGET. The number of bins B are chosen be n for COMPOSITE and SOURCE, and "Q
Table shows the risks for different approaches with лo = 0.1, np 103, and no = 102. In terms of Real COMPOSITE performs the best, as calibrated to the target distribution by taking advantage of the abundant source data. In terms of Rsha LABEL-SHIFT achieves Rsha 0 due to the strictly increasing g. but it suffers from high Real, COMPOSITE and SOURCE achieve smaller result of using more bins a larger sample. Considering the combined impact of calibration and sharpness, our approach COMPOSITE attains the lowest overall recalibration risk R as well MSE.
pasha than TARGET,
Figure 6 shows the optimal recalibration function h and the recalibration functions for the four approaches. It can be seen that COMPOSITE best estimates h" with the highest resolution.
27


Reviews:
[{"review_id": "AJaCW5SVUf", "reviewer": "Reviewer_a48G", "summary": "This work looks at methods for calibrating probabilistic classifiers for Mean Squared Error by decomposing it into calibration error and sharpness errors. It gives finite sample error guarantees on both of these for the Uniform Mass Binning method. By balancing sharpness and calibration error, they also propose the optimal number of bins to use. Additionally, they look at the problem of calibrating classifiers in the case of label distribution shift between train and test. Their results show that transferring a calibrated classifier requires significantly fewer target samples compared to recalibrating from scratch. They validate our theoretical findings through numerical simulations.", "questions": "- Why did the authors choose to analyze only Uniform Mass Binning and not other methods like Uniform width binning?\n- For the label distribution shift problem, is the proposed method equivalent to just scaling all the predicted probablities according to the target distribution and then using the uniform binning technique?\n- In definition 4, the sharpness risk of h over f, is this the sharpness risk of h.f - sharpness risk of f?\n- Why is Assumption 3 needed for the label distribution case?\n- Just to confirm, is this the first sharpness risk bound?\n- In figure 2a, why is the gap increasing between the theoretical and empirical bound as n increases?\n- In table 1, the different methods compared are not clear to me. Can the authors please explain?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Existing works have looked at finite sample bounds for the calibration error but not the sharpness (as mentioned in this paper). This is the first method to look at both sharpness and calibration together which is an important criterion. \n- The paper is generally well written.", "weaknesses": "- The main contribution is to give risk bounds for sharpness along with the calibration error. In my opinion, this is not a significant contribution. There is not any particular strategy proposed using this analysis but only choosing the number of bins.\n- The second problem of using this method for label distribution shift also seems straightforward and I have also asked a related question below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe appreciate the valuable comments and feedback. Our response is structured to address the highlighted weaknesses first, followed by detailed point-by-point responses to specific questions.\n\n### **Weaknesses**\n\n1\\. Not a significant contribution:\n\nWe appreciate the reviewer's recognition of our paper's unique contribution in jointly addressing sharpness and calibration, introducing a new recalibration perspective. Yet, we respectfully disagree that our contributions lack significance. We elaborate on our work's importance as follows:\n1. **Holistic approach:**\nPost hoc recalibration is a crucial issue with a long history. Our paper advances the recalibration field by addressing sharpness and calibration together, bridging a gap in prior research. Sharpness, though often overlooked, plays a crucial role in recalibration. Relying solely on the calibration criterion may lead to suboptimal recalibration. By considering both aspects, we provide a comprehensive and principled framework to effectively tackle the problem, a notable advancement.\n2. **Foundational understanding:**\nAlthough not novel, histogram binning presents a functional approach that lays a foundational step in illuminating the recalibration perspective. Our aim is not to propose a complex or competitive strategy, but to establish a solid theoretical basis for recalibration. This foundational understanding holds intrinsic value, complementing practical strategies. Moreover, the simplicity of our method is not a drawback, but rather a blessing, as it extends practical applicability.\n3. **Bin selection significance:**\nWe acknowledge the importance of bin selection in histogram binning literature, a well-recognized topic in calibration research. Our approach aligns with recent efforts, such as [26] and [37], which emphasize the need for improved binning strategies. Our paper contributes by proposing a theoretically-backed approach for selecting the optimal number of bins, bolstering recalibration reliability.\n\nWe believe these contributions significantly enhance recalibration and pave the way for future advancements.\n\n2\\. Perceived simplicity of the method:\n\nThe reviewer described scaling predicted probabilities via the label shift formula followed by recalibration through uniform mass binning (UMB) in Question-2. We stress a key distinction: the operation order is reversed compared to Eq. (15) or (17) in the original submission. Thus, the reviewer's method may not necessarily estimate the optimal recalibration function under label shift. Recall that our recalibration function's optimality is substantiated by Theorem 2's risk bounds.\n\nWe appreciate the reviewer's engagement and hope this response clarifies our method's nuances and strengths. Also, we reiterate that the method's simplicity underscores its broad applicability and foundational significance, rather than being a drawback.\n\n### **Questions**\n1\\. Rationale for UMB:\n\nOur choice of UMB over UWB was driven by analytical considerations. UMB's well-balanced binning property (Lemma 3 in Appendix B.1), ensuring nearly equal sample sizes per bin, aids analysis. In contrast, UWB can yield varied per-bin sample sizes depending on distributions. Consequently, UWB's calibration risk bounds conservatively rely on the smallest sample sizes among bins [17, Corollary 3], whereas UMB provides distribution-free calibration risk bounds. Moreover, UMB's well-balanced binning ($\\Phi_{balance}(B,\\alpha)=1$ in Lemmas 6 and 7) ensures robust sharpness risk bounds across diverse distributions.\n\n2\\. Clarification of the method:\n\nPlease see the response to Weakness-2.\n\n3\\. Definition 4:\n\nWe presume that the reviewer inquires if the sharpness risk of $h$ equals the reduction in sharpness of $f$ resulting from the application of $h$, i.e., sharpness of $f$ minus sharpness of $h\\circ f$, which an accurate interpretation (see Line 146-147).\n\n4\\. Assumption 3:\n\nAssumption (A3) is optional, and its inclusion enhances the sharpness risk bound from $O(1/B)$ to $O(1/B^2)$ (Theorem 1). For the label shift case (Theorem 2), omitting Assumption (A3) relaxes the sharpness risk bound term from $\\frac{8K^2}{B^2}$ to $O(1/B)$. We opt for (A3) whenever feasible to showcase the tightest upper bound within a context reasonably common in practical scenarios.\n\n5\\. First sharpness risk bound:\n\nTo our knowledge, this indeed represents the first formulation of a sharpness risk bound. It's worth mentioning that a related study by [26] found that MSE only increases by O(1/B) by discretization (Proposition D.4, [26]), which bounds sharpness risk by O(1/B) for recalibration functions with 0 calibration risk. In our work, we integrate this insight into Theorem 1, asserting $GRP(\\hat{h})\\leq\\frac{2}{B}$ in the absence of Assumption (A3).\n\nIt's important to underscore that [26] didn't explicitly label their excess MSE bound as a sharpness risk bound, nor did they emphasize the independent existence of such a bound beyond discretization. In fact, the bound of sharpness risk strictly implies their results as a special case. Furthermore, we enhance the sharpness risk bound to $O(1/B^2)$ by introducing Assumption (A3).\n\n6\\. Figure 2a:\n\nOur focus is mainly on the order of the risk bound, which holds significance in asymptotic contexts. As such, the expanding gap in Figure 2-a and the uniform gap in Figure 2-b could potentially be attributed to a constant multiplicative factor. Remarkably, the theoretical and empirical optimal values for $B$ closely align in order, evident from their near-parallel trends in Figure 2(b).\n\n7\\. Table 1:\n\nDue to page limit, we moved the detailed method explanation to Appendix E.2. We're aware of possible clarity concerns in Table 1's caption and understand the value of summarizing these details in the Experiments section. In the forthcoming camera-ready version upon acceptance, we aim to improve clarity by incorporating these explanations into Table 1's caption or integrating them into the main text."}, {"review_id": "4sL8T4E3eX", "reviewer": "Reviewer_kAN5", "summary": "This work proposes a calibration method for probabilistic classifiers. It is known that most machine learning models produce predictions with high confidence that yield a distribution different than the underlying true label distribution. The proposed method focuses on calibration without a loss on the prediction performance and is claimed to adjust for label shift.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper is written clearly with good and easy-to-follow notations. The different definitions are well-placed and help the reader to follow the flow of the paper. Overall good structure of the paper. \n- The equal focus during the calibration on both calibration and sharpness goals is well-motivated and importantly this setting. The theory is developed rigorously and the different choices and assumptions are justified.\n- This paper extends the proposed work to label-shfit setting and provides a good discussion on \"recalibration under label shift\" .\n- This paper provides experimental results that show the validity of the theoretical work proposed.", "weaknesses": "I think this paper lacks the following two points:\n\n- A discussion in section 1.1 highlighting to the reader how this paper approaches the recalibration problem differently than existing work. Only the work in [26] has been addressed.\n- Section 6 does not include a discussion about the empirical results of previous works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable feedback on our work. With gratitude for the positive evaluation, we are dedicated to clarifying and enhancing our contributions by addressing the raised concerns.\n\n### **Weaknesses**\n#### 1\\. Insufficient discussion on distinction from existing work:\nThe reviewer's observation is valid, and we appreciate the opportunity to address this concern. While we have selected [26] for the main comparison, it's important to note that our engagement with existing work extends beyond this comparison. In Section 4, alongside the comparison with [26], we underscore in Remark 1 that our calibration risk bound aligns with [18] up to a constant factor in the failure probability. In Section 5, we compared target sample complexity with [28,2,12] in Remark 5, pointing out that our method, which only uses target labels, achieves the same order of risk bounds as the methods using only target features.\n\nWe would like to provide further insight into our rationale for selecting [26,18] as the basis of comparison in Section 4. Our objective is to holistically and quantitatively address both calibration and sharpness preservation. A main contribution of our work is to develop risk bounds for both calibration and sharpness risks, which subsequently inform the optimal choice of bin number in uniform mass binning -- a recalibration method extensively studied theoretically and applied in practice. To the best of our knowledge, [26,18] represent the most competitive theoretical works that are relevant to our goal, as they provide state-of-the-art calibration error bounds under their specified assumptions. In contrast, [32,37] lack theoretical underpinning and primarily focus on empirical assessment.\n\nWe value the reviewer's perspective feedback and appreciate the opportunity to clarify our choices of baseline works. Should there be additional works that are better suited for comparison with our theoretical framework, we would appreciate the reviewer's further input, which would improve the robustness and comprehensiveness of our work.\n\n#### 2\\. Lack of empirical results comparison and discussion with prior works:\nWe greatly appreciate the reviewer's observation, which makes us realize the importance of including empirical comparisons between the proposed methods and previous works.\nIn addition to our original experiments which validated our theoretical claims, we have conducted additional numerical experiments to compare the performance of the UMB method with three other approaches—UWB [16], Platt scaling [34], and hybrid method [26]. The results and discussion of these comparisons have been incorporated into the Author Rebuttal report. This inclusion enhances the comprehensive evaluation of our work and strengthens its practical implications.\n"}, {"review_id": "RxuuKTeGwX", "reviewer": "Reviewer_USpM", "summary": "This paper introduces the concept of minimum risk recalibration, utilizing Mean Squared Error (MSE) decomposition. The authors provide justification for their approach by demonstrating that minimizing the proposed risk yields simultaneous minimization of the calibration risk while preserving the sharpness of the probability forecaster. Furthermore, the authors employ the MSE decomposition to analyze the recalibration method known as UMB. Theoretical analysis reveals that selecting an appropriate number of bins allows for achieving a balance between the calibration risk and sharpness. Expanding on their findings, the authors apply their methodology to address the problem of recalibration in label shift. They provide theoretical and experimental validation for their approach in the context of label shift, further supporting the effectiveness of their proposed method.", "questions": "Please refer to the Weakness part.", "limitations": "The authors have analyzed the limitation of the used method in the appendix.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The authors provide a rigorous introduction to key statistical measures essential for the recalibration task, such as recalibration/calibration risk and sharpness risk. They demonstrate that minimizing these measures can result in a well-calibrated forecaster.\n\n2. Building upon the introduced statistics and their properties, the authors enhance the analysis of UMB. They unveil a tradeoff between calibration risk and the preservation of sharpness by establishing a high-probability error bound. Furthermore, they leverage this upper bound to guide the selection of the number of bins in the UMB method, highlighting the practical significance of the proposed bound and decomposition.\n\n3. The authors extend the application of their proposed method to address the challenge of label shift, showcasing the validity of their work in practical downstream tasks.\n\n4. The paper thoroughly discusses the mildness of the assumptions made and experimentally validates the non-trivial nature of the proposed bounds and schemes.", "weaknesses": "While the outcome of this study is fruitful, it is encouraged that the authors delve into a further discussion regarding the potential extension of their framework to the multi-class scenario. This extension would provide additional intuitive information and enhance the applicability of their proposed methodology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are overwhelmingly grateful for the reviewer's in-depth understanding and unreserved recognition of our work, encompassing nontrivial concepts, rigorous analysis, practical significance of the tradeoff, applications to downstream tasks, assessment of assumptions, and experiment design for theory verification.\nWe indeed agree with the reviewer that one of the most promising directions forward is to extend our framework to the multiclass scenario.\nWe are delighted to provide further discussion in this paper to enhance intuitive understanding and practical applicability of our methodology.\n\nIn the context of multi-class classification, the concept of calibration takes on various forms [19].\nAn intriguing avenue for extension involves canonical calibration [41], which directly extends our methodology.\nA major challenge of the extension lies in designing the binning scheme in a multidimensional space, a complexity that has been explored in [19].\nWhile calibration guarantees have been explored in [35], establishing sharpness risk bounds within this multi-class context remains an engaging pursuit.\nThe interplay between calibration and sharpness could potentially guide the development of a binning strategy that balances these aspects in multi-class classification.\n\nWe extend our appreciation to the reviewer once more for this invaluable suggestion of including additional discussion on the multi-class scenario.\nFurthermore, we would appreciate the reviewer's further input that could enrich this discussion and enhance the value of our work."}, {"review_id": "cP6szVpjtr", "reviewer": "Reviewer_yKq4", "summary": "The paper studies a very relevant problem of post-hoc calibration in probabilistic classifiers. There is a great body of work on calibrating probabilistic classifiers so that the predicted probabilities match the empirical label frequencies in the popular machine learning literature. However, calibrating probabilistic classifiers so that they retain their sharpness / refinement is not studied much. The paper focuses on the post-hoc calibration with retained sharpness properties from first principles. Its entry point is the classical decomposition of mean squared error of the classifier into sharpness and (mis)calibration. Traditionally, both the measures were important, but the works in machine learning literature has mostly focussed on (mis)calibration only. There are important contributions in this paper: a) proposing recalibration risk measure which attains its minimum value only when both sharpness and the calibration requirements are met. b) uniform mass binning algorithm to approximate the optimal recalibration map. c) Theoretical results on the binning scheme and binning scheme to bound both the calibration risk and the sharpness risk. d) Formal result on the trade-off between calibration and sharpness. e) recalibration studies in a simple (but important) distribution shift with label shift. All of these results are for binary classification setting.", "questions": "1. The optimal recalibration function is same as the canonical calibration map defined in [2] (Section 3.1). While it is clearly interesting to see that a canonical calibration map is the optimal recalibration map, could authors comment on this connection? The optimal recalibration map is certainly a calibrated function (as the Proposition 1 in [2] states), I am curious about some insights on why it would also be a map to minimise the sharpness risk.\n\n2. Additionally, [2] also propose a sort of general methodology to estimate this canonical calibration map (Section 4.1). While they do not comment on the partitioning scheme, it would be interesting to draw insights on general partitioning schemes and the bound on the recalibration risk. \n\n3. While the authors mention that extending the results presented in the paper to multi-class setting is a future research direction, could authors see that the estimator provided in [2] could be useful for multi class case (as [2] do not restrict itself to binary classification)?  \n\n\n[2]  Juozas Vaicenavicius et al. Evaluating model calibration in classification. (2019)", "limitations": "Obviously, there are limitations to this work, as there are with any works. However, the authors have been very clear in stating them. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. It is clear that the paper makes theoretical contributions to an important problem. It has been observed that major recalibration algorithms in machine learning literature not just ignore the sharpness measure, but they degrade it [1]. There is a trade-off between these quantities, and this paper formally state this with some actionable insights to balance this trade-off.\n2.  Theorem 1 generalises a previous result in the literature with an additional insight on the sharpness risk. Generalisations and connections to previous results is a sign of great work. \n3. While the results on label shift are easy consequences of the general recalibration results presented earlier in the paper, it is still great to see this extension. \n4. In my opinion, the paper is significant and relevant to the machine learning community. I believe the paper will spur more work on post-hoc calibration methods. \n5. The paper is excellently written, easy to read and understand.\n\n\n\n\n\n[1] Aditya Singh et al. On The Dark Side Of Calibration For Modern Neural Networks. (2021) (http://www.gatsby.ucl.ac.uk/~balaji/udl2021/accepted-papers/UDL2021-paper-074.pdf)", "weaknesses": "I do not have major concerns with this paper. I have some questions though (please see below):", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for the comprehensive understanding and the positive evaluation from the reviewer, especially in acknowledging our theoretical contribution to an important field while providing actionable insights, and recognizing the impact of this work on the community.\nWe also appreciate the invaluable questions and suggestions from the reviewer, which has led us to think deeper in terms of extending our theory to the multi-class scenario while drawing connections from a previous paper [41] (we use the reference number in the paper to avoid confusion).\nWe present our perspectives as follows and hope these will address the reviewer's questions and lead to insightful discussions.\n\n### **Questions**\n#### 1\\. Connection with the canonical calibration map in [41]:\nThe reviewer's observation is accurate; the optimal recalibration function in our work is the same as the canonical calibration function defined in Eq. (4) of [41] in the binary classification setting. Below, we elaborate on this connection in three aspects.\n\n1. **Equivalence:**\nIn the framework of [41], a classifier $f: \\cal{X} \\to \\cal{Y}$ is considered *reliable* if and only if $P[Y\\in\\cdot|f(X)]=f(X)$, that is, the conditional distribution of the target class, given any prediction made by $f$, precisely matches that prediction. This aligns directly with the notion of a *(perfectly) calibrated* classifier, as defined in our paper through Definition 1.\n\n2. **Calibration:**\nAs pointed out by the reviewer, the optimal recalibration function is calibrated as it follows the form in Proposition 1 in [41].\n\n3. **Sharpness:**\nIn our work, we define the optimal recalibration function through the minimum risk criterion, requiring the achievement of zero recalibration risk. Remarkably, this implies the optimal recalibration function has 0 calibration risk and 0 sharpness risk according to Proposition 1. Alternatively, we can also examine the definition of the sharpness risk (Definition 4) for the optimal recalibration function $h^*(z)=\\mathbb{E}\\left[ Y \\mid f(X) = z\\right]$. Observing $h^*(f(X))$ as a function of $f(X)$ and applying towering property, we have\n\\begin{align}\n    \\newcommand{\\EP}{\\mathbb{E}}\n    \\EP \\left[ Y \\mid h^*(f(X)) \\right]\n    = \\EP \\left[ Y \\mid \\EP \\left[Y \\mid f(X) \\right] \\right]\n    = \\EP \\left[ \\EP \\left[Y \\mid f(X) \\right] \\mid \\EP \\left[Y \\mid f(X) \\right] \\right]\n    = \\EP \\left[Y \\mid f(X) \\right],\n\\end{align}\nwhich establishes that $R^{sha}(h^*) = 0$.\n\n    Intuitively, $h^*$ takes the form of expectation of $Y$ conditioned on the full prediction $f(X)$, in a sense carrying all the \"information\" within $f(X)$ about $Y$. Therefore, using $h^* \\circ f$ will not reduce the explained variance by $f$, thus achieving 0 sharpness risk.\n\n\n\n#### 2\\. Exploring insights from partitioning schemes in [41]:\n\nThe reviewer has identified a major challenge for recalibration using a general partitioning scheme.\nIn particular, the consistency results presented in Theorem 1 of [41] lay a foundation for estimating calibration error, prompting the question of deriving convergence rates for calibration risks. However, effectively controlling the sharpness risk can be intricate when an explicit description of a partitioning scheme is absent.\nOne insight we draw from [41] is that the maximum diameter of sets in the partition can be used to effectively measure the granularity of the partition, which may be useful in developing sharpness risk bounds.\nConsidering these aspects, we recognize that bounding the recalibration risk for overall recalibration risk for general partitioning schemes is a promising, albeit challenging, trajectory for future research endeavors.\nWe appreciate the reviewer's thought-provoking comment, as it has motivated us to delve into the intricacies of general partitioning schemes and derive these valuable perspectives.\n\n\n#### 3\\. Potential usefulness of partitioning method for multi-class settings:\n\nWe perceive the partition-based estimator in [41] as a promising candidate for extending our framework to multi-class scenarios, representing a natural multi-dimensional progression from the histogram-binning estimator. Beyond the specific estimator outlined in that work, we also recognize an additional potential application of [41] stemming from its introduction of a calibration lens. This lens accommodates diverse facets of partial calibration, a concept of particular interest within the realm of multi-class classification [16, 19]. \n    \nFurthermore, the work by [41] establishes the almost sure consistency of a binned (=partitioned) estimator for expected miscalibration through Theorem 1. This achievement could potentially serve as a foundational step in establishing the convergence of the binned estimator's calibration risk towards zero, offering a promising initial stride in this direction."}, {"review_id": "sNsyxFCqA0", "reviewer": "Reviewer_GPZN", "summary": "Background:\nGenerating reliable probability estimates alongside accurate class labels is crucial in classification tasks. Calibration, which refers to the alignment between predicted probabilities and empirical frequencies of labels, is highly desirable in various applications. However, many machine learning algorithms lack inherent calibration.\n\nThis paper aims to address these issues in two ways:\n1. Development of a unified framework for recalibration that incorporates both calibration and sharpness in a principled manner.\n2. Proposal of a composite estimator for recalibration under label shift, which converges to the optimal recalibration and enables sample-efficient adaptation of classifiers to label-shifted domains.", "questions": "1. In Eq. (9), I understand that the function $\\hat{h}(z)$ calculates the expected label within the bin that $z$ belongs to. So, why is $\\hat{h}$ a monotonically increasing function of $z$ and its growth pattern similar to the cumulative distribution function (CDF) of $z$? Although you have made Assumption 2, can I understand that this assumption implies that $y$ must follow a specific distribution form in order to satisfy the monotonicity of $\\hat{h}$?\n2. In the experimental section, the author only presents a very simple toy scenario, and I am quite curious about the performance of the author's algorithm in more complex scenarios. For instance, in real-world classification datasets like cifar-10-long-tail or cifar-100-long-tail, how does the recalibration effect of more complex models, such as neural networks or decision trees?\n3. In Fig. 1 (a), as the value of $n$ increases, regardless of the magnitude of $B$, $R^{cal}(\\hat{h})$ exhibits a noticeable decrease. Does this imply that when the dataset size $n$ becomes sufficiently large, $R^{cal}(\\hat{h})$ has already reached a level where recalibration is unnecessary?\n\nIf the author can answer my question, I will change my score.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. This paper is exceptionally well-written, with a clear and logical structure, making it easily understandable to a wide audience.\n2. The theoretical foundation of this paper is solid, the proof process is very detailed, making it easy for people to follow.\n3. The algorithm proposed by the author is simple and efficient, making it easy to implement.", "weaknesses": "1. Although the author provides solid theoretical analysis, this paper lacks enough experiments to demonstrate the effectiveness of their method.\n2. The author employs three assumptions, and in my view, assumption 2 is a rather strong one, which is difficult to guarantee in practical applications.\n3. The experiments in this paper were conducted primarily on toy datasets, and the author do not provide any experiments on how to apply Recalibration in real-world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable feedback on our work. With gratitude for the positive evaluation, we are committed to further clarifying our contributions by addressing the concerns and questions raised. To streamline this endeavor, our response is organized to initially address the highlighted weaknesses, followed by detailed point-by-point responses to the specific questions.\n\n### **Weaknesses**\n#### 1\\. Insufficient experiments:\nWe believe that the numerical evidences presented in our original submission effectively validate both the theoretical claims and the efficacy of our method. Specifically, we validate the main results outlined in Section 4, including the risk upper bounds in Theorem 1 (Figure 1) and the optimal choice of the number of bins $B$ (Figure 2). Additionally, the significant contributions of Section 5, such as the explicit form of optimal recalibration under label shift and a two-step recalibration estimator with theoretical guarantees, are substantiated by Table 1.\n\nWhile we maintain confidence in the sufficiency of our original numerical experiments to validate our theoretical findings, we also acknowledge the value of extending numerical studies, e.g., by including comparisons to other methods. To address this, we have conducted additional numerical experiments that compare the performance of our proposed UMB method against three other approaches: UWB [16], Platt scaling [34], and the hybrid method [26]. The results of these supplementary comparisons are included in the Author Rebuttal report.\n\n#### 2\\. Validity of Assumption 2:\nWe appreciate the reviewer's recognition of the potential stringency and practical challenges related to ensuring Assumption 2. However, it's important to highlight that while this assumption might appear stringent, it remains sensible for a reasonably well-performing classifier $f$, for which the underlying trend is expected to persist even if predicted probabilities $f(x)$ are imprecise. Specifically, we should expect $f(x_1)\\leq f(x_2)$ when $P[Y=1|x_1]\\leq P[Y=1|x_2]$ for a reasonable classifier.\n    \nAdditionally, it's worth noting that similar monotonicity assumptions are prevalent in related literature. For instance, such assumptions are utilized in recalibration through isotonic regression [44], maintaining accuracy via order-preserving maps [45], and selecting bin numbers for monotonicity preservation [37].\n\n#### 3\\. Lack of experiments with real-world datasets:\nOur main emphasis in this paper lies in presenting a fresh recalibration perspective alongside a thorough analysis of a working method, making it primarily theoretical in nature. Although the application of our framework to real-world contexts holds potential interest, we believe its incorporation is not essential within the scope of the present paper. As such, we regard this as a captivating and promising avenue for future endeavors—to extend our comprehensive framework, encompassing both calibration and sharpness risks, to real-world applications. \n\n### **Questions**\n#### 1\\. Monotonicity of $\\hat{h}$?\nFirst of all, we want to clarify that Assumption (A2) enforces the monotonicity of $h^*$, NOT imposing the monotonicity of $\\hat{h}$. As the reviewer observed, $\\hat{h}$ is an estimate of $h^*$ computed as the expected label within the bin that $z$ belongs to, and may NOT be monotone due to the finite sampling effect. However, we anticipate concentration of $\\hat{h}$ to $h^*$, especially with narrow bins and ample per-bin data, leading to monotone increasing $\\hat{h}$ with high probability. \n\nFurthermore, the reviewer accurately notes that Assumption (A2) concerns the distribution of $Y$. Specifically, the monotonicity of $h^*$ imposes a monotonicity requirement on the conditional distribution of $Y$ given $Z=f(X)$; recall $h^*(z)=E[Y|Z=z]$ from Eq. (7).\n\n#### 2\\. Applications to more complex scenarios:\n1. **Real-world data:**\nWe agree with the reviewer that applications of our framework to real-world classification tasks would be interesting. Nevertheless, it's important to highlight that many real-world tasks involve **multi-class** classification. While it is conceivable to address this, e.g., by transforming it into multiple pairwise binary classification tasks, multi-class classification scenarios lie beyond the scope of the current paper. Thus, we regard it as an intriguing direction for future exploration.\n\n2. **Complex models:**\nPost-hoc recalibration treats probabilistic classifiers as black-box entities, only utilizing their predicted probabilities as inputs. Therefore, our recalibration framework applies to **any** probabilistic classifiers, including neural networks and decision trees. As far as we understand, the performance of the model and recalibration are not directly linked. Although different models might yield distinct joint distributions of probabilistic predictions $f(X)$ and labels $Y$, indirectly influencing the fitted recalibration function $\\hat{h}$, its performance will remain consistent if it holds distribution-free calibration guarantees [18].\n\n#### 3\\. (Un-) necessity of recalibration for large $n$?\nWe appreciate the reviewer's keen observation regarding the decreasing trend of $R^{cal}(\\hat{h})$ as $n$ increases in Fig. 1(a). This behavior signifies that $\\hat{h}$ effectively calibrates $f$, resulting in a well-calibrated composition $\\hat{h}\\circ f$ for large $n$; it's important to clarify that this doesn't necessarily imply $f$ is inherently well-calibrated. Hence, if the initial classifier $f$ lacks calibration, it remains relevant to estimate a post-hoc recalibration function $\\hat{h}$. Additionally, we'd like to emphasize that the aspect of sharpness is entirely overlooked in this context; when $B=1$, the composition $\\hat{h}\\circ f(x)\\to EY$ (for all $x$) as $n\\to\\infty$, leading to a constant classifier that's calibrated but devoid of information."}]

Author rebuttal:
We appreciate the reviewers' valuable feedback. Our Author Rebuttal addresses recurring themes, offering clarification on methodological contributions and presenting supplementary numerical evidence. Comprehensive point-by-point responses are available in individual rebuttals.

### **Summary of contributions**
**Key highlights.**
Allow us to succinctly underscore the key contributions in this paper.
1. We introduce a novel quantitative framework that interlaces both sharpness and calibration, thereby yielding further insights for the recalibration problem.
2. Applying this framework to histogram binning method, we obtain finite-sample error bounds for the calibration risk and the sharpness risk.
3. Our analysis illuminates a principle guiding the selection of an optimal number of bins, notably identifying $B = O(n^{1/3})$ where $n$ is the calibration dataset size.
4. Considering the label shift, an exemplar of distributional shift, we identify the optimal recalibration function while proposing a pragmatic two-step estimator, fortified with a convergence guarantee.

We appreciate the recognition of our work's theoretical significance by Reviewers 2, 3, 4, and 5. Reviewer 1 also partially acknowledged this contribution, with specific inquiries that we addressed comprehensively in our individual response.

**Significance of contributions.**
We further elaborate on the importance of our work as follows.
1. **Holistic approach:** 
Our paper makes a distinct contribution by addressing both sharpness and calibration concurrently, bridging a gap that has persisted within recalibration research. The interplay between these elements, often overlooked, profoundly influences recalibration outcomes. By holistically integrating these aspects, we introduce a comprehensive and principled solution, marking a substantial advancement.
2. **Foundational insight:**
Our proposed method based on histogram binning -- a pragmatic solution among potential alternatives -- and its analysis illuminate a novel recalibration perspective. We underscore that this paper is primarily aimed at establishing a conceptual framework underpinned by strong theoretical foundations. This foundational comprehension carries intrinsic value, effectively complementing practical strategies. Additionally, the simplicity of our approach extends its applicability rather than serving as a limitation.
3. **Significance of optimal bin selection:**
We acknowledge the significance of bin selection, in line with recent work in histogram binning literature such as [26] and [37], emphasizing the need for improved strategies and metrics. Our contribution offers a theoretically-supported approach for optimal bin number selection, bolstering the reliability of recalibration outcomes.

### **Additional experiments**
In response to the reviewers' requests, we conducted additional experiments to compare our proposed method with prominent approaches from the literature. The results of these experiments are detailed in the attached report. Specifically, we assess the performance of four methods: our method (UMB), uniform width binning [16], Platt scaling [34], and Platt-binning [26]. These methods represent two alternative binning approaches, a parametric method, and a hybrid parametric-binning approach, respectively. Additionally, we examine two distinct data distributions that were studied in [25]: Logistic calibration and Beta calibration. The outcomes of these supplementary experiments provide further support for the assertions we made in Section 4.2 of our original submission, where we theoretically compared risk bounds.

Table R.1 presents quadrature estimates of population risks for the four methods under (a) Logistic calibration and (b) Beta calibration. Notably, Table R.1a demonstrates that Platt-binning outperforms scaling and binning methods in terms of $R^{cal}$ when the underlying model assumption is correct (Logistic model). This performance superiority can be attributed to the accurate parametric model assumption, resulting in lower sample complexity compared to nonparametric methods. This finding validates a key claim made in [26]. However, as depicted in Table R.1b, this advantage of Platt-binning diminishes when the true recalibration function deviates from the parametric family. In such cases, the nonparametric binning methods (UMB \& UWB) emerge as the top performers among the four methods.

Figure R.1 provides a visual representation of the recalibration curves for the optimal recalibration function $h^*$ and its estimates under the two distributions. Remarkably, in both Logistic calibration and Beta calibration, histogram binning methods (UWB and UMB) closely track the $h^*$ curve. Conversely, the scaling-binning approach follows the Platt scaling estimates, leading to an inherent bias from $h^*$ in Beta calibration. This visualization provides insightful evidence of the efficacy of our proposed methods.

### **Promising future research: extension to multi-class classification**
As mentioned in the original Discussion, extending our framework to multiclass classification will be an exciting and logical progression. We notice that many reviewers share this view and express interest in its application to multiclass scenarios.

However, a major challenge of the extension lies in designing the binning scheme in a multidimensional space, a complexity that has been explored in [19]. Reviewer 4 (yKq4) highlighted potential insights from partition-based results in [41] for this extension. We acknowledge that while some calibration guarantees have been explored in [35], establishing sharpness risk bounds within this multi-class context remains an engaging pursuit. We believe the interplay between calibration and sharpness could potentially guide the development of a binning strategy that balances these aspects in multi-class classification. 

In conclusion, we recognize the multiclass extension as a promising direction for future research.

Meta-review: This paper presents a principled approach for recalibrating probabilistic classifiers, with guarantees on both calibration and sharpness. This is in contrast to the existing literature, which mainly focuses on calibration, often at the expense of degradation in sharpness. The authors apply their results the classical histogram binning based calibration, and provide a theoretically sound approach for bin selection, and also discuss an application to recalibration under label shift. Supporting experiments on synthetic data are provided.

The reviewers agree that the paper very well-written and makes solid theoretical contributions. Despite concerns about the paper not providing experiments on real-world data, the general consensus is to accept the paper.

The authors are strongly encouraged to include the following in the camera-ready version:
- detailed discussion of how the paper differs from prior work (Reviewer kAN5)
- a discussion on extension to multi-class problems (Reviewer USpM)
- additional experiments presented as a part of the rebuttal (Reviewer GPZN)
Decision: Accept (spotlight)