PAC Prediction Sets Under Label Shift
Authors: Wenwen Si
Sangdon Park
Insup Lee
Edgar Dobriban
Osbert Bastani
Venue: ICLR 2024 poster (2024)
Keywords: prediction set
label shift
distribution-free uncertainty quantification
probably approximately correct
Clopper-Pearson binomial interval
rejection sampling
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: Prediction sets capture uncertainty by predicting sets of labels rather than individual labels, enabling downstream decisions to conservatively account for all plausible outcomes. Conformal inference algorithms construct prediction sets guaranteed to contain the true label with high probability. These guarantees fail to hold in the face of distribution shift, which is precisely when reliable uncertainty quantification can be most useful. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting, where the probabilities of labels can differ between the source and target distributions. Our algorithm relies on constructing confidence intervals for importance weights by propagating uncertainty through a Gaussian elimination algorithm. We evaluate our approach on four datasets: the CIFAR-10 and ChestX-Ray image datasets, the tabular CDC Heart Dataset, and the AGNews text dataset. Our algorithm satisfies the PAC guarantee while producing smaller prediction set sizes compared to several baselines.

Published as a conference paper at ICLR 2024
PAC PREDICTION SETS UNDER LABEL SHIFT
Wenwen Si', Sangdon Park?, Insup Lee', Edgar Dobriban', Osbert Bastani
'Department of Computer & Information Science, University of Pennsylvania "Graduate School of AI and Computer Science & Engineering, POSTECH 'Department of Statistics and Data Science, University of Pennsylvania (wenwens, lee, obastani saaasannj@seees sess upenn edu, sangdon@postech..c.k dobriban@wharte upenn. edu
ABSTRACT
Prediction sets capture uncertainty by predicting sets of labels rather than individual labels, enabling downstream decisions to conservatively account for all plausible outcomes. Conformal inference algorithms construct prediction sets guaranteed to contain the true label with high probability. These guarantees fail to hold in the face of distribution shift, which is precisely when reliable uncertainty quantification most useful. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting, where the probabilities of labels can differ between the source and target distributions. Our algorithm relies on constructing confidence intervals for importance weights by propagating uncertainty through Gaussian climination algorithm. We evaluate our approach on four datasets: the CIFAR-I0 and ChestX-Ray image datasets, the tabular CDC Heart Dataset, and the AGNews text dataset. Our algorithm satisfies the PAC guarantee while producing smaller prediction set sizes compared several baselines.
INTRODUCTION
Uncertainty quantification can be a critical tool for building reliable systems from machine learning components. For example, medical decision support system can convey uncertainty to a doctor, or a robot can act conservatively with respect to uncertainty. These approaches are particularly important when the data distribution shifts the predictive system is deployed, since they enable the decision-maker to react to degraded performance.
Conformal prediction (Vovk et al. 2005 Angelopoulos & Bates, 2021 is promising approach to uncertainty quantification, aiming to outputs sets of labels instead single label. Under standard assumptions (i.i.d. or exchangeable data), it guarantees that the prediction set contains the true label with high probability. We consider probably approximately correct (PAC) (or calibration-sel- conditional) guarantees (Vovk) 2012, Park et al.) 2019), which ensure high probability coverage over calibration datasets used to construct the prediction sets.
In this paper, we propose a novel prediction algorithm that provides PAC guarantees under the label shift setting, where the distribution of the labels may shift, but the distribution of covariates conditioned on the labels remains fixed. For instance, during a pandemic, disease may spread to much larger fraction of the population, but the manifestations of the disease may remain the same. As another example, real-world data may have imbalanced classes, unlike the balanced classes typical of curated training datasets. We consider the unsupervised domain adaptation setting (Ben-David et al. 2006), where we are given labeled examples from a source domain, but only unlabeled examples from the target domain, and care about performance in the target domain.
standard way to adapt conformal inference to handle distribution shift is by using importance weighting to "convert" data from the source distribution into data from the target distribution (Tibshi- the label shift setting, one possible way to express the importance weights is Cp q' where Cp is the confusion matrix and q" is the distribution of predicted labels (Lipton ct al. 2018); see details below. However, the estimation error for the unknown Cp and 9a breaks the PAC guarantee.
rani et al. 2019).
2

---

Published as a conference paper at ICLR 2024
label probability
sample
predict
Cps(x)
effusion
infilrration
no shift
(x)
effusion
label probabiity
infiltration
sample
prodict
effusion
Cpsw (x)
infiltration
nodule
effasion infiltrtion
nodule
label shift
Figure I: An example of our approach on the ChestX-ray dataset. the unshifted setting, standard PAC prediction sets guarantee sigh-probbbility coverage, but this guarantee fails under label shift. Our approach addresses this challenge and continues to work in the shifted environment.
Instead, we construct confidence intervals around Cp and q², and then devise a novel algorithm to propagate these intervals through the Gaussian elimination algorithm used to compute w". Finally, we leverage an existing strategy for constructing PAC prediction sets when given confidence intervals for the importance weights (Park et al., (021).
We empirically evaluate our approach on four datasets across three application domains: CIFAR- 10 (Krizhevsky al., 2009) the computer vision domain, the CDC Heart Dataset (Centers for Disease Control and Prevention (CDC), 1984) and ChestX-ray (National Institutes of Health and medical domain, and AGNews (Zhang et al. 2015) in the language domain.
others 2022)
Contributions. We propose novel algorithm for constructing PAC prediction sets in the presence of label shift, which computes provably valid intervals around the true importance weights. Our algorithm is based climination, which to our knowledge is novel approach to uncertainty propagation in a prediction construction setting. Finally, empirically demonstrate that approach satisfies the PAC guarantee while constructing smaller prediction sets than several baselines.
technique for propagating confidence intervals through the updates of Gaussian
of our technique the ChestX-ray -ray dataset. In medical settings, prediction sets (denoted PS) provide rigorous way to quantify uncertainty for making downstream decisions. In particular, they can guarantee that the prediction set contains the true label (in this case, a diagnosis) with high probability. However, label shift happens commonly in medical settings, for instance, many illnesses have varying rates of incidence over time even when the patient population remains the same. Unfortunately, label shift breaks the PAC coverage guarantee. Our approach (denoted PSW) corrects for the label shift via importance weighting; does so a provably correct way. The resulting prediction sets satisfy the PAC guarantee.
Example. Figure iillustrates
Related work. There has been recent interest in conformal inference under distribution shift, much of it focusing on covariate shift (Tibshirani et al. 2019 Lei & Candès 2021; Qiu et al. (022). (Podkopaev Ramdas 202T) develop methods for marginal coverage under label shift, whereas we interested in training conditional-ov that the true importance weights are known exactly, which is rarely the case. In the label shift setting, the importance weights can be estimated (Lipton al., 2018), but we show in our experiments, uncertainty in these estimates must be handled for the PAC guarantee to hold.
M.CC-guraattes. Furthermore, they formally assume
We leverage the method of (Park et al. 2021 handle estimation error in the importance weights. That work studies covariate shift, and uses a heuristic to obtain intervals around the importance weights. For the label shift setting, can in fact obtain stronger guarantees: modify Gaussian
2

---

Published as a conference paper at ICLR 2024
elimination to propagate uncertainty through the computation of the weights w' Cp' q" We give a more comprehensive discussion of related work in Appendix
PROBLEM FORMULATION
2.1 BACKGROUND ON LABEL SHIFT
Consider the goal of training classifier 9 X' - V/ where X' S RR is the covariate space, and (1.... K} is the set labels. We consider the setting where we train on one distribution = [K]
Pover X' x - called the soure-wwith a probability density function (PIF) p (ar, y) p(1,, y), and evaluate on a potentially different test distribution Q-called the warget-withh PDF (I, y) + g). We focus on the unsupervised domain adaptation setting (Ben-David et al. 2007). where we are given an i.i.d. sample Sn ~ Pm of m labeled datapoints. and an i.i.d. sample of n unlabeled datapoints T Q*- The label shift setting (Lipton al.) 2018)) assumes that only the label distribution Qy may be change from Py, and the conditional covariate distributions remain the same:
Assumption 2.1. (Label shift) We have p(a y) = q( y) for all æ E X, y E V
We denote ply) = (Y y) for y E y and analogously for Q. (Litoon et 2018 consider two additional mild assumptions:
Assumption 2.2. For all y E Y' such that ((v) > O, we have p(v) > 0.
Next, given the trained classifier g : X - y let Cp RRk denote its expected confusion matrix-i.e. Caj = (Cp);j = Pxxx)>(((())== = =
Assumption 2.3. The confusion matrix Cp is invertible.
This last assumption requires that the per-class expected predictor outputs be linearly independent; for instance, it is satisfied when g is reasonably accurate across all labels. In addition, one may test whether this assumption holds (Lipton et al. 2018).
Denoting the importance weights w' == (a(v)/p()) vey E RKK and == g(a),, we will write p(ily)= = P(x.r))p(((X) = y Y = y). and define p(ù, y) Py as well as the corresponding expres- sions for 9 analogously. Since ý depends only on x, we have q(δ v) = p(O y). Thus, see e.g..
Lipton et al. (2018).
{v) ply)
9g = Σ ql v)((v) = Σ p(D v)g(v) = Σ p(D. v)
DEY
DEY
DEY
or in a matrix form, q-' Cpw", where q² (gg)DEy RK As we assume Cp is invertible,
w² = CP'
(1)
Our algorithm uses this equation to approximate w", and then use its approximation construct PAC prediction sets that remain valid under label shift.
2.2 PAC PREDICTION SETS UNDER LABEL SHIFT
We are interested in constructing a prediction set C X 2 which outputs a set of labels C(r) C y for each given input x E X' rather than a single label. The benefit of outputting set of labels is that we can obtain correctness guarantees such as:
P(x,))<p\ E C(X)) 2-1))21-8
where (0, 1) is user-provided confidence level. Then, downstream decisions can be made in way that accounts for all labels y E C(x) rather than for a single label. Thus, prediction sets quantify uncertainty. Intuitively, equation can be achieved if we output C(x) = y for all X, but this is not informative. Instead, the typical goal is to output prediction sets that are as small as possible.
The typical strategy for constructing prediction sets is to leverage fixed existing model. In particular, we assume given a scoring function f X' x y + I; most deep learning algorithms provide such scores in the form of predicted probabilities, with the corresponding classifier being g(x)
3

---

Published as a conference paper at ICLR 2024
arg max f(x,)) y). The scores do not need to be reliable in any way; if they unreliable, the PAC prediction set algorithm will output larger sets. Then, we consider prediction sets parameterized by real-valued threshold R:
[y f(, 2) 2T).
In other words, we include all labels with score at least т. First, we focus on correctness for P. in which case only need Sm. usually referred to as the calibration set. Then, a prediction set algorithm constructs threshold F(S..
and returns C*(Sm.))
Finally, we want i to satisfy 2 one caveat is that it may fail to do so due to randomness in Sm. Thus, we allow an additional probability å E IR of failure, resulting in the following desired guarantee:
P Sm Pm
[ Pxxy))-PY E C+(s..)(X)) 2 1 - c]
6.
Vovk 2012) Park et al. 2019) propose an algorithm f that satisfies e see Appendix
Finally, we interested in constructing PAC prediction sets in the label shift setting, using both the labeled calibration dataset Sm. ~ pm from the source domain, and the unlabeled calibration dataset TX Q" from the target distribution. Our goal is construct (SSms Tx) based on both S., and T'X which satisfies the coverage guarantee over Q instead of P:
n
PS QQ
(xxxY)>~ll C=(sm.Ty) 2 1 s)
Importantly, the inner probability is over the shifted distribution Q instead of P.
ALGORITHM
To construct prediction sets valid under label shift, we first notice that it is enough find element- wise confidence intervals for the importance weights w". Suppose that we can construct W kEY [y Wt]] C R such that w W. Then, when adapted our setting, the results of Park et al. 2021 originally for the covariate shift popllem-rrovide an algorithm that returns threshold
7(Sm V, W,6), where Uniform 1])* a vector of random variables, such that
Pss. Pm, PPxYY~ Y E C+(Sm.. 2 s) 2 1
(5)
This is similar to equation but it accounts for the randomness used by our algorithm -iia V-in the outer probability. We give the details in Appendix C
The key challenge is to construct W TTkeyLus, Wx] such that w E W with high probability. The approach from Park et al. 202I) for the covariate shift problem relies on training a source-target discriminator, which not possible in case since do not have class labels from the target domain. Furthermore, Park et al. (2021)'s approach is does not provide conditions under which one can provide valid confidence interval for the importance weights in their setting.
Our algorithm uses a novel approach, where we propagate intervals through the computation of importance weights. The weights w" are determined by the system of linear equations Cpw" = q² Since Cp and q" are unknown, we start by constructing element-wise confidence intervals
Cp < Cp < Cr
and "
(6)
with probability least 1 over calibration datasets Sm and TX We then propagate these confidence intervals through each step of Gaussian elimination, such that at the end of the algorithm, obtain confidence intervals for its output-i.e.,
w
w
< w
with probability at least - ō.
Finally, we can use 7 with the algorithm from Park et al. 2021) to construct PAC prediction sets under label shift. We describe our approach below.
3.1 ELEMENTWISE CONFIDENCE INTERVALS FOR Cp AND y"
Recall that Cp = (cr)ijey and q-' = (qk)key) Note that Gij = P(g(() = i,Y = 5] is the mean of the Bernoulli random variable (g(X)= = j) over the randomness in (X, P.
4

---

Published as a conference paper at ICLR 2024
Similarly, 9k is the mean of (X) k) over the randomness in X Qx Thus, the Clopper-Pearson Pearson (CP) intervals (Clopper & Pearson 1934) for a Binomial success parameter to construct intervals around Gúj and 9r- Given confidence level 8 (0, 1) and the sample mean Gy m E (a.y)s.. 1 [g((x) i = 5) distribuut as scaled Binomial random variable-thi this is an interval CP(cg m. 8) [cij. Cayl such that
Is P (ci CP(Cis, m, 6)] 2
Similarly, for Ok- we can construct CP intervals based on Q%: ; for confidence levels dig and 6% chosen later, we obtain for all i,j, E [K],
EmETx (g(x) = k). Together,
Psm. pm (G3 Cij S Eny 1 5
P Prx~Q2
9 qh
qk
- Oz.
(8)
Then, the following result holds by union bound: Given any dag, d2 E (0, 20). for all i, & E [K], letting (sys Cig] = CP(C m, 6iz) and EnE[K] Oe. we have
[g 7xl = CP( n, 0g), and letting å = Σije(K) dij
P S. Pm Pm TT Tx
Si S cy S Cay. A
9x qh T kE[K]
21-8.
[JE[K]
3.2 GAUSSIAN ELIMINATION WITH INTERVALS
We also need to set up notation for Gaussian elimination, which requires to briefly recall the algorithm. To solve Cpw" = q" Gaussian elimination (see e.g., Golub & Van Loan 2013) proceeds
in two phases. Starting with e Cp and d q², iteration t 1, Gaussian elimination uses row k = t to eliminate the kthh column of rows E {kk + }} (we introduce a separate variable k for clarity). In particular, if cha # O, we denote
c
ifi K
qi
ifi
Ckk
ch
Vi.j E [K].
Cij
otherwise;
otherwise.
If ct = O, but there is an element j > k in the kth column such that t/ * O, the kth and the jth rows are swapped and the above steps are executed. If no such element exists, the algorithm proceeds to the next step. At the end of the first phase, the matrix K-1 has all elements below the diagonal equal to zero-i.e., K- solves for W backwards from i K to i = introducing the following notation. For each if
0 if j < In the second phase, the Gaussian elimination algorithm
K # 0, we denote i (a. s
where 8, = Σソ=
K %j Aw:.
In our setting, we do not know c and qO: instead, we assume given entrywise confidence intervals as in equation 6 which amount to c S c² < 2d and qd S 9 S <. We now work on the event that these bounds hold, and prove that our algorithm works on this event; later, we combine this result with Equation to obtain high-probabilltty guarantee. Then, our goal is to compute z", c g', q such that for all iterations E {0, 1..., K 11. we have elementwise confidence intervals specified by e², é., g² and टी for the outputs c², of the Gaussian elimination algorithm:
d' d 5
and s'
(10)
The base case / = 0 holds by the assumption. Next, to propagate the uncertainty through the Gaussian elimination updates for each iteration / [K -1], our algorithm sets
if > k k
[+1 Sj
if k.
Vi,j E [K]
(11)
otherwise
'The algorithm requires further discussion if K 0 Goolub & Van Loan 2013 this does not commonly happen in motivating application so will not consider this case. See Appendix D for details.
c
5

---

Published as a conference paper at ICLR 2024
for the lower bound, and computes
ifi k. J
Sacky Ckk
if if >k k,
Vi,j [K]
(12)
otherwise
for the upper bound. The first case handles the fact that Gaussian elimination is guaranteed to zero out entries below the diagonal, and thus these entries have no uncertainty remaining. The second rule constructs confidence intervals based the previous intervals and the algebraic update formulas used in Gaussian elimination for the entries for which i, > k. For instance, the above confidence intervals use that on the event 52, and by induction on f, if Sij 2 and s > 0 for all i, E [K] and
for all i, the Gaussian elimination update 1g
c+1
= ci - c ///t//t can be upper bounded as
C.dy
S d
(13)
cu
d
The assumptions that cty 2 0 and ci > 0 for all i E [K] and for all t may appear little stringent, but the former can be removed at the cost of slightly larger intervals propagated to the next step, see Section D The latter condition is satisfied by any classifier that obtains sufficient accuracy all labels. We further discuss these conditions in Section[D] The third rule in equation| 11 and equation [2 handles the remaining entries, which do not change; and thus the confidence intervals from the previous step can be used. The rules for are similar, and have a similar justification:
Su
ifisk. k.
ifi> k.
7
7+11=
Vi E [K]. (14)
Skk
Ck
otherwise;
g
otherwise.
For these rules, our algorithm assumes g. 2 O for all E [K] and all I, and raises error if this fails. As with the first condition above, this one can be straightforwardyy relaxed; see Appendix D
In the second phase, we compute wt starting from K and iterating assume we have the confidence intervals w I w < w for j > i. Then, we compute confidence intervals for the sum 8,, with a similar justification based on the Gaussian elimination updates:
1. On iteration we
Σ 1=++1
and
8
(15)
J=
and show that they satisfy 8; S 8 S 3, on the event Q. Finally, we compute confidence intervals for wf, assuming K Sai >
3
m
and
(16)
K-1
for which we can show that they satisfy w S w S w based on the Gaussian elimination updates.
Letting W = =(w | w= S w S T"), we have the following (see Appendix E proof). Lemma 3.1 (Elementwise Confidence Interval for Importance Weights). If (6) holds, and for all i E [K] St 2 O, ck > 0, and q. 2 0, then w" Cp 5 9-' W.
We mention here that the idea of algorithmic uncertainty propagation may be of independent interest. In future work, it may further be developed to other methods for solving linear systems (e.g.. the LU decomposition, Golub & Van Loan (2013), and other linear algebraic and numerical computations.
3.3 OVERALL ALGORITIM
Algorithm I summarizes our approach. As can be seen, the coverage levels for the individual Clopper- Pearson intervals are chosen to satisfy the overall coverage guarantee. particular, the PAC guarantee equation follows from equation 5 equation
Lemma 3.1 and union bound; we provide
a more detailed explanation in Appendix F
Theorem 3.2 (PAC Prediction Sets under Label Shift), For any given e, 6 E (0, 1), under A Assumptions
2.1 2.2 and 2.3 j. E [K], we have ctyy 2 ch > and of 2 O, then Algorithm satisfies
P P9 PT..P"TTT---- CQ",
[Pxx.))~olY E CF (X)
8] 2 8.
As discussed in Appendix
D we can remove the requirement that ct 2 0 and o. 2 0 for

---

return C. Q. Published as a conference paper at ICLR 2024
Algorithm 1 PS-W: PAC prediction sets in the label shift setting.
1: procedure PABELSSHIPPRIDDDTTONSSTSS.S Te f,,,6)
2: G. CPINTERVAIL(S.: Tx arg mrrgmax,c>. Pey f(z, v),
KIK-1)
(2(X+1)+1))
3: W 4- INTERVAL. C.g.
4: if WV Ø then return @
return PEEEDICTIONST,,TS
W. 6/ ( +1)
procedure CPINTERVAL(Sm. T .9.6)
7: for i,j E [K] do
8:
Compute [g) Gg] CP (m " (awess 1((x)) = i,y 5). m).. +1))
9: for & [K] do
Compute 22. Tx. CP (n (n-' Exery 1(((x) = k), (
10:
11:
12: procedure INTERVAL
13:
for E [l.....
do
14:
for i,j E [K]dd do
15:
Compute ciy, dg using 11 & 12 and g, of using [4
16:
if dg for some
c 0 for some
for some i, then return
17:
for E [K,.... 1] do
18:
Compute s 5. using 15 and w,, W. using 16
19:
return W = I [u, w.
20:
procedure IWPREDICTIONSET(S.. f, W II W,,, 6,
21:
V Uniform( 11)m
22:
return F(Sm, V. W. maxke[k] E, as in
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Predictive models. We analyze four datasets: the CDC Heart dataset, CIFAR-10, Chest X-ray, and the AG News dataset; details are provided in Section 4.2 We use a two-layer MLP for the CDC Heart data with SGD optimizer having a learning rate of 0.03 and momentum of 0.9, using a batch size of 64 for 30 epochs. For CIFAR-10, we finetune pretrained ResNet50 He et al. (2016). with learning rate of 0.01 for 56 epochs. For the ChestX-ray -ray dataset, we use a pre- traited CheXNet (Rajpurkar& et al. 2017) with a DenseNet121 (Huang et al. 2017) backbone with learning rate of 0.0003 for two epochs. For AGNews, we fine-tune pre-trained Electra sequence classifier for one epoch with an AdamW optimizer using learning rate of (1.00011
Hyperparameter choices. There are two user- user-speeifeed hyperparameters that control the guarantees, namely 5 and e. In our experiments, we choose 8 = 5 x 10 to ensure that, over 100 independent datasets Sm, there is 95% probability that the error rate is not exceeded. Specifically, this ensures that IP (x,x))=P YY- E C=(Sm)) (X)] 1- holds for all 100 trials, with probability approximately 1 1/00 x x 10-4, We select for each dataset in a way that the resulting average prediction set size is greater than one. This ensures that the coverage guarantee is non-trivial, as a single-valued classifier should not achieve the desired coverage rate (as small).
Dataset construction. We follow the label shift simulation strategies from previous work (Lipton al. 2018). First, we split the full dataset into training data, and "base" source and target datasets. We use the training dataset to fit score function. Given label distributions Py and Qy, we generate the source dataset Sn,, target dataset x.X and a labeled, size o target test dataset (sampled from Q) by sampling with replacement from the corresponding base datasets. We consider two choices of Py and Qy: (i) a tweak-one shift, where change the probability of one label, and keep the relative proportions of the other labels equally likely, and (ii) general shift, where we shift each probability as described later.
Baselines. We compare our approach (PS-W) with several baselines (see Appendix G
7

---

Published as a conference paper at ICLR 2024
PS: PAC prediction sets that do not account for label shift (Vovk 2012 Park al. 2019). This
does not come with PAC guarantees under label shift.
WCP: Weighted conformal prediction under label shift, which targets marginal coverage Pod
kopaey & Ramdas] 2021). This does not come with PAC guarantees under label shift either.
PS-R: PAC prediction sets that account for label shift but ignore uncertainty in the importance
weights; again without guarantees.
PS-C: This addresses label shift via a conservative upper bound on the empirical loss (see Appendix G for details). This is the only baseline with PAC guarantee under label shift.
We compare to other baselines in Appendix [.5] and to an oracle with the true weights in Appendix H Results for other hyperparameters are in Appendix
Metrics. We measure performance via the prediction set error, i... the fraction of (zz ~ Q such that $ C=(x); and the average prediction set size, i.e., the mean of |C₂ (C)(, evaluated on the held-out test set. We report the results over 100 independent repetitions, randomizing both dataset generation and our algorithm.
4.2 RESULTS & DISCUSSION
CDC Heart. We use the CDC Heart dataset, a binary classification problem (Centers for Disease
Control and Prevention (CDC) 1984). The goal is to predict the risk of heart attack given features such level of exercise or weight. We use 0.1 and 6 5 10-4 We consider both large and small shifts. For the large shift, the label distributions denoted (pos%, neg%) (94%, 6%) for
predecion set arror
0.15
1.5
0.22
1.75
2.00
1.2
0.00
1.50
2.0
1.0
set
1.25
0.8
0.06
0.75
0.4
0.50
0.10
0.2
0.25
6.01
PS-U PSR PS-W WCP
0.0
P5 PS-C PS-R PS-W WCP
0.00
PS PS-C PS-R PSW WCP
0.00
PS-C PS-R PS-W WCP
(a) Prediction set error and size under small shifts on
(b) Prediction set emror and size under large shifts on
the CDC Heart dataset. Parameters x 10-4 42000, 42000, and o 9750.
0.1. d
the CDC Heart dataset. Parameters E 0.1, 8
10
42000, 42000, and o 9750.
Figure 2: Prediction set results on the CDC Heart dataset.
source, and (63.6%, 36)4%) for target; results are Figure We also consider a small shift with label distributions (94%, 6%) for source, and (91.3%, 8.7%) for target; results in Figure 2a| As can be seen, our PS- W algorithm satisfies the PAC guarantee while achieving smaller prediction set size than PS-C, the only baseline to satisfy the PAC guarantee. The PS and PS-R algorithms violate the PAC guarantee.
CIFAR-10. Next, we consider CIFAR-10 Krizhevsky al. 2009). which has 10 labels. We use 8 = 0.1 and 5 x 10-4, We consider a large and a small tweak-one shift. For the large shift, the label probability
10% for all labels in the source, 40.0% for the tweaked label, and 6.7% for other labels in the target; results are in Figure 3al For small shifts, we use 10% for all labels for the source, 11.76% for the tweaked label, and 9.8% for other labels for the target; results are Figure 3b) Under large shiftts, our PS-W algorithm satisfies the PAC guarantee while outperforming PS-C by large margin. When the shift very small, PS-W W still satisfies the PAC guarantee, but generates more conservative prediction sets similar in size to those of PS-C (e.g., Figure (3b) given the limited data. Results for a non-uniform source distribution and general shifts are shown in Appendix [.8]
AGNews. AG News is subset of AG's corpus of news articles (Zhang et al. 2015). It is text classification dataset with four labels: World, Sports, Business, and Sei/Tech. contains 31,900 unique examples for each class. We use shifts. We consider a large shift and a medium sized calibration dataset, with label distributions equalling (30.8%, 30.8%, 7.7%, 17%%%%8%% 30.8%) for the source, and (12.5%, 12.5%, 62.5%, 12.5%) for the target; results are Figure 4a As before, our PS-W approach satisfies the PAC guarantee while achieving smaller set sizes than PS-C.
0.05 and = 5 x 10 14- We use tweak-one label
ChestX-ray. ChestX-ray 14 (Wang et al., 2017) is a medical imaging dataset containing about 112K frontal-view X-ray images of 30K unique patients with fourteen disease labels. This dataset contains
8

---

Published as a conference paper at ICLR 2024
4.0
prediclon Sat amoo
1.75
gredie Eeiieiion selt arror
3.5
1.25
2.5
cm 0.10
0.01
1.5
0.50
22.00
0.5
PS PS-C PS-R PS-W WEP
0.00
P5 PS-C PS-R PS-W WCP
PS PS-C PS-R PS-W WCP
0.0
PS PSC PS-R PS-W WCP
(a) Prediction error and size with larger shift on CIFAR-10. Parameters are & = 0.1, = 5 x 10T m 27000, n = 19997, and = 19997.
small shift on CIFAR- 10. Parameters are & = 0.1, = 5 x 10 m 27000, n = 16500, and = 16500.
Prediction set erro and size
Figure 3; Prediction set results on the CIFAR-10 10 dataset.
Em 0.05
2.00
0.12
1.75
2
1:25
prediction
0.30
5000
0.00
0.75
0.
0.25
0.00
(a) Prediction and size the AGNews 10
(b) Prediction emror and size the ChestX-ray dataset. Parameters
Datasct. Parameters are 0.05, m = 26000, n = 12800, and = 12800.
0.3, m = 67200, n 35200, and o 3520.
10
Figure 4: Prediction set results on the ChestX-ray dataset.
instances with multiple labels, which omit. We also omit classes with few positively labeled datapoints, leaving six classes: Atelectasis, Effusion, Infiltration, Mass, Nodule, Pneumothorax. We consider general label shift. We consider large tweak-one shift, with label distributions of (19.1%, 19. 19, 4.5%, 19.1 1%) for the source, and (11.1%, 11.1 %, 44.5%, 11.1%) for the target. Results for E 0.3 in Figure 4b As before, our PS-W approach satisfies the PAC guarantee while outperforming PS-C. The PS-R and WCP methods violate the constraint.
Discussion. all our experiments, our approach satisfies the PAC guarantee; furthermore, produces smaller prediction set sizes than PS-C- the only baseline to consistently satisfy the PAC guarantee except when the label shift small and the calibration dataset is limited. In contrast, the PS baseline does not account for label shift, and the PS-R baseline does not account for uncertainty in the importance weights, so they do not satisfy the PAC guarantee. The WCP baseline is designed to target a different guarantee, and it does not satisfy the PAC guarantee. Thus, these results demonstrate the efficacy our approach.
Limitations. Our approach is focused on problem settings where the label shift is not too small and sufficient calibration data available; and may produce conservative prediction sets otherwise. This reflects the intrinsic difficulty of the problem in these settings. Importantly, our PAC coverage guarantees still hold.
CONCLUSION
We have proposed a PAC prediction set algorithm for label shift setting, and illustrated its effectiveness in experiments. Directions for future work include improving performance when the calibration dataset or the label shift small.
Reproducibility statement. Our code available at pac-ps-labe -ate0---aall--s-f-- for reproducing experiments.
ACKNOWLEDGEMENT
This work was supported in part by ARO W911NF-20-1-0080 ARO W911NF-23-1-02% NSF 2031895, NSF 2046874, ONR N00014-21-1-2843,, the Sloan Foundation, and Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea govermment Artificial Intelligence Graduate School Program (POSTECH)). Any opinions, findings and conclusions recommendations expressed in this material those of the authors and do not necessarily reflect the views the Army Research Office (ARO), or the Department of Defense, the United States Government.
(MSIT)

---

Published as a conference paper at ICLR 2024
REFERENCES
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-fres uncertainty quantification. arXiv preprint arXiv:2107.075// 2021.
Kamyar Azizzadenesheli. Anqi Liu, Fanny Yang, and Animashree Anandkumar, Regularized learning for domain adaptation under label shifts. arXiv preprint arXiv:1903.097334 2019.
Vineeth Balasubramanian, Shen-Shyang Ho, and Vladimir Vovk. Conformal prediction for reliable machine learning: theory, adaptations and applications. Newnes, 2014.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137-144, 2007.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint htti:2000804266.7 2020.
Centers for Disease Control and Prevention (CDC). Behavioral risk factor surveillance system, 1984. URL https: //wp:::::/wwwwweee cdc. httpp//ppp...s//aouaaaalaaccaela satppuaaaaaaaaaaannanaa catteaaaaaaaa_aaeeeea htm
Yee Seng Chan and Hwee Tou Ng. Word sense disambiguation with distribution estimation. IJCAI, volume 5, pp. 1010-5, 2005.
Charles Clopper and Egon S Pearson. The use of confidence fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413, 1934.
Edgar Dobriban and Mengxin Yu. Symmpi: Predictive inference for data with group symmetries. arXiv preprint arXiv:2312.16160, 2023.
Robin Dunn, Larry Wasserman, and Aaditya Ramdas. Distribution- free prediction sets for two-layer hierarchical models. Journal of the American Statistical Association, 0(0):1-12, 2022.
Donald Alexander Stuart Fraser. Nonparametric methods statistics. John Wiley & Sons Inc, 1956.
Saurabh Garg, Yifan Wu, Sivaraman Balakrishnan, and Zachary Lipton. A unified view of label shift estimation. Advances Neural Information Processing Systems, 33:3290-33000 2020.
Saurabh Garg, Sivaraman Balakrishnan, and Zachary C Lipton. Domain adaptation under open set label shift. arXiv preprint arXiv:2207.13044, 2022.
Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine learning. 3(4):5, 2009.
I. Guttman. Statistical Tolerance Regions: Classical and Bayesian. Griffin's 's statistical monographs & courses. Hafner Publishing Company, 1970. URL htt.h:tp///// /bwok/s.ooss//////ooo
: google. wwt.eeecoooooooooooeeoeeooo boon/
Td=300vAAAAMAAJ
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and puttern recognition, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. Advances in neural information processing systems, 19, 2006.
10

---

Published as a conference paper at ICLR 2024
Ramneet Kaur, Susmit Jha, Anirban Roy, Sangdon Park, Edgar Dobriban, Oleg Sokolsky, and Insup Lee. idecode: In-distribution equivariance for conformal of-istribiuttinn detection. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Jing Lei, Alessandro Rinaldo, and Larry Wasserman. A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1):29 (3))):299444222 2015.
Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2021.
Shuo Li, Xiayan Ji, Edgar Dobriban, Oleg Sokolsky, and Insup Lee. Pac-wrap: Semi-supervised pac anomaly detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
Zachary Lipton, Yu-Xiang Wang. and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pp. 3122-3130. PMLR, 2018.
National Institutes of Health and others. Nih clinical center provides one of the largest publicly available chest x-ray datasets to scientific community, 2022.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pp. 345-356. Springer, 2002.
Sangdon Park. Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. arXiv preprint arXiv:2001.00100 2019.
Sangdon Park, Shuo Li, Insup Lee, and Osbert Bastani. Pac confidence predictions for deep neural network classifiers. arXiv preprint arXiv:2011.00716 2020.
Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. Pac prediction sets under covariate shift. arXiv preprint arXiv:2106.00 09848, 2021.
Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. Pac prediction sets for meta-learning. arXiv preprint arXiv:2207.024440 2022.
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-free uncertainty quantification for classifi- cation under label shift. In Uncertainty in Artificial Intelligence, pp. 844-853. PMLR, 2021.
Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Prediction sets adaptive to unknown covariate shift. arXiv preprint arXiv:2203.06/200 2022.
Hongxiang Qiu, Eric Tchetgen Tchetgen, and Edgar Dobriban. Efficient and multiply robust risk estimation under general forms of dataset shift. arXiv preprint arXiv:2306. 16406, 2023.
Pranav Rajpurkar, Jeremy Irvin, Kaylie Zhu, Brandon Yang, Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, Katie Shpanskaya, et al. Chexnet: Radiologist-level pneumonia detection on chest x-rays with deep learning. arXiv preprint a7Xiv:1711.05225. 2017.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
Reuven Y Rubinstein and Dirk P Kroese. Simulation and the Monte Carlo method. John Wiley & Sons, 2016.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 11(555))2233-233 2019.
Marco Sacrens, Patrice Latinne, and Christine Decaestecker. Adjusting the outputs of a classifier to priori probabilities: simple procedure. Neural computation, 14(1):21-44 2002.
11

---

Published as a conference paper at ICLR 2024
Alexander Shapiro. Monte carlo sampling methods. Handbooks in operations research and manage- ment science, 10:353-444 425, 2003.
Amos Storkey et al. When training and test sets are different: characterizing learning transfer. Dataset shift in machine learning, 30:3-28, 2009.
Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. Advances in neural information processing systems, 20, 2007.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
John Von Neumann. Various techniques used in connection with random digits. Appl. Math Ser, 12 (36-38):3, 1951.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pp. 475-490, PMLR, 2012.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer Science & Business Media, 2005.
Xiaosong Wang. Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers. Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakll-supervised classi- fication and localization of common thorax diseases. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2097-2106, 2017.
Samuel S Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathemat- ical Statistics, 12(1):91-96, 1941.
Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In Proceedings of the twenty-first international conference Machine learning, pp. 114, 2004.
Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In International conference on machine learning, pp. 819-827. PMLR, 2013.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL RELATED WORK
Conformal Prediction. Our work falls into the broad areas of distribution-Free uncertainty quantifi- cation, conformal prediction and tolerance regions (e.g., Guttman 1970 Vovk et al. 2005 Balasub. ramanian et al., 20144] Angelopoulos & Bates 202 Kaur et al. 2022 Li et al. 2022 Dobriban &
Yu 2023] ctc), which aim to construct prediction sets with finite sample coverage guarantees. The
prediction sets often realized by setting threshold on the values of traditional single-laeel
predictor (i.e. conformityynon-co confoormity score function) and predict all labels with scores above this
threshold. Our setting is related to inductive conformal prediction (Papadopoulos al.) [2002] [ovk
2012 Lei et al. 2015), where the dataset is split into training set for fitting the scoring function and calibration set for constructing the prediction sets.
PAC Prediction Sets. A standard coverage guarantee for conformal prediction methods is marginal coverage over the training, calibration and test data. For inductive conformal prediction, training-de conditional correctness (Vovk] 2012 Park et al. (019) aims to achieve an (s, -coveraee guarantee, where coverage over test points exceeds the desired error rate level E with probability at most 8. Sets satisfying this guarantee have been termed PAC prediction sets (Park et al., 2019). This guarantee is also equivalent to the classical coverage properties of tolerance regions (Wilks 1941 Fraser 1956). PAC coverage may be desired when a slight excess of the desired error rate cab cause significant safety concern.
Covariate shift
Label shift
Importance weights, as a function of x. y
(x))/p())
((v)/p()
Shared conditional distribution, for all x. y ply x) gly x))
p(x
v) g(2r
v)
Table 1: Comparison of covariate shift and label shift.
Huang et al. 2006 Sugiyama et al. 2007 Gretton et al.) 2009) supposes that the conditional covariate distribution is fixed but the label distribution may change from a source to target distribution; see Table T In more detail, let p and g denote the probability density functions of the source and target domains with respect to common dominating measure, respectively. Label shift assumes that for all labels y, (3) may differ from p(y), but for all features v and labels y, we have p(æ; y) q(x: | y). Label shift can arise when the representations of the classes changes, for instance in scenarios like medical diagnosis and object recognition (Storkey
Label shift. Label shift (Zadrozny 2004;
ct al. 2009 Sacrens et al. 2002 Lipton et al. (2018).
Early solutions required the estimation of q and p. which may scale poorly with the dimension (Chan & Ng 2005) Storkey et al. 2009; Zhang et al. 2013). More recently, two approaches achieved
scalability by assuming an approximate relationship between ground truth labels y and the outputs ğ of classifier (Lipton al.] | Azizzadenesheli al.) | Saerens al. (002): Black Box Shift
Estimation (BBSE) (Lipton et al. 2018) and RLLS (Azizzadenesheli et al. 201 provided consistency results and finite-sample guarantees assuming the confusion matrix is invertible. Subsequent work developed unified framework that decomposes the error in computing importance weights into miscalibration error and estimation error, with BBSE as a special case (Garg et al., 2020); this approach was extended to open set label shift domain adaptation (Garg et al. 2022). We also mention that label shift a special case of more general class of distribution shifts that allow the source and target distributions to be related by sharing sequential conditional distributions (Qiu et al. 2023).
Conformal methods and distribution shift. Conformal prediction has been adapted to distribu- tion shifts such as covariate shift (Tibshirani et al., 2019, Lei & Candès] 2021: Qiu et al. 2022). (Podkopaev & Ramdas| 2021) considers label shift when the true importance weights are exactly known. Importance weights are typically estimated with uncertainty. We address this by developing an algorithm to find confidence intervals for the importance weights. More broadly. prediction sets have been studied in the meta-learning setting (Dunn et al. 2022 Park et al. 2022).. as well as the setting of robustness to all distribution shifts with bounded -iierrgence (Cauchois et al. 2020).
Class-conditional prediction sets. Although not designed specifically for solving the label shift problem, methods for class condiiioniiioaal coverage (Sadinle et al. (019)) and adaptive prediction sets (APS) (Romano et al. 2020) can improve robustness label shifts. However, class-conditional
13

---

Published as a conference paper at ICLR 2024
coverage is stronger guarantee that leads to prediction sets larger than for our algorithm, while APS does not satisfy a PAC guarantee; we compare empirically to these approaches Appendix [.5]
B BACKGROUND ON PAC PREDICTION SETS
Finding the maximum 7 that satisfies 3 is equivalent to choosing the largest such that the empirical emror
Lsm (C+) = Σ
1y & (x))
(2.
on the calibration set Sm is bounded Vovk et al. (2005); Park et al. 2019). Let F(k;; m, =
Eizo (*)) =) be the cumulative distribution function (CDF) of the binomial distribution
Binom(m, 8) with m trials and success probability & evaluated at kt Then, Park et al. (2019) constructs C+ via
f
subj. to (c+ S E,m,
(17)
TET
where k(m, E, = max subj. F(k;; m, 8.. KENL(0)
Their approach is equivalent the method from Vovk (0122), but formulated in the language of learning theory. By viewing the prediction set as a binary classifier, the PAC guarantee via this construction can be connected to the Binomial distribution. Indeed, for fixed C, Ls (C) has distribution Bionm(m, LC()), since I(y & C(z)) has a Bernoull(Lpp(C) distribution when (a. y) ~ P. Thus, k(m, e, 5) defines a bound such that (C(C) S E, then (s,,(C)) S k(m, E, with probability at least 8.
C BACKGROUND ON PREDICTION SETS UNDER DISTRIBUTION SHIFT
Here we demonstrate how to obtain prediction sets given intervals w- S ~ Th around the true importance weights. This approach is based closely the strategy in (Park et al. 2021 for constructing prediction sets under covariate shift, but adapts it to the label shift setting (indeed, our setting is simpler since there finitely many importance weights). The key challenge is computing the importance weight intervals, which we describe in detail below.
Given the true importance weights w", strategy would be rejection sampling (Von Neumann 1951; Shapiro 2003 Rubinstein & Kroese, (016) to subsample S.,. to obtain a dataset that effectively consists of N S m i.i.d. samples from Q (here, N random variable, but this turns out not be an issue). Essentially, for each (I,, V1. E Sm. we sample a random variable V ~ Uniform((O, 1]), and then accept samples where V; S / where b is an upper bound on wg-
T (S,, V. ,),",,)= = (I's vi E Sm
V1
S
W. b
In our setting, we can take b = maX wg. Then, we return F(IN (Sm: V,w",b) b)). Since (S V, wn, b) consists of an i.i.d. sample from Q, we obtain the desired PAC guarantee (4)
In practice, do not know the true importance weights w². Instead, suppose we can obtain intervals Wy -wy Wy such that wy E W, with high probability. We let W = TI W,, and assume w" E W with probability at least 1 - ó. The algorithm proposed in (Park et al., [02I]) adjusts the above algorithm to conservatively account for this uncertainty-i.ee. it chooses so the PAC guarantee 4 holds for any importance weights w E W:
+(Sm, V, b) = min ((T b)w.
(18)
wEW
We minimize over since choosing smaller leads to larger prediction sets, which is more conserva-
tive. (Park et al. 202T) show how to compute (T8) efficiently. We have the following guarantee:
Theorem C.1 (Theorem 4 in (Park et al. 2021)) ) Assume that w² E W. Letting U = Uniform([O, 1)),
IP sss,. Pm VV-t/m
((x,Y)) CP(S...V...o)) 2 - s] > -
In other words, the PAC guarantee holds, with the modification that the outer probability includes the randomness over the samples
T used by our algorithm.
14

---

Published as a conference paper at ICLR 2024
D ENSURING THE CONFIDENCE BOUNDS AT EACH STEP
The diagonal elements Cisk of the confusion matrix of an accurate classifier, are typically much larger than the other elements. Indeed, for an accurate classifier, the probabilities of correct predictions ((g(x)
A. = k) are higher than those of incorrect predictions GA := P(g(x) = i, i + k. On the other hand, the Clopper-Peant related Wald interval has length or order 1/ym, where m is the sample size). Thus, we expect that
interval is expected be short (for instance, the
< 2 < CkR. k -...... K k.
(19)
Without loss of generality, we consider equation 11 as example. In the Gaussian elimination process, recall that the update step
if k.
(20)
Skk
Combining with equation 19 the factor by which the k-th row is multiplied is small, i.c., E/eckkk < 1. Thus the resulting i-th diagonal elements
S
Skk
change little after each elimination step, and are expected to remain positive. Next we discuss intervals for off-diagonal elements.
Balanced classifier. For a balanced classifier, when Gu and Cjk are close for all i such that o k j * k since the factor / is small, the lower bound in equation 20 is expected be positive.
Imbalanced classifier. For the more general case of a possibly imbalanced classifier, Gij and Cıÿ may not be close. This could cause non-positive bounds at certain steps, so the confidence interval may not be valid at the next steps; e.g., equation 13 may fail. However, note that since
cx E [cke, ckul,
cky
E [ckj ckyl:
we have
ch I max{I F max c 1. [2ky))
and hence
max
le max { (lckyl |4y1)
Sht
In fact, one can derive the even tighter bound
cu
Euchss
The
Ehetyy
chscts
max
che
che
che
che
che
che
che
This can be checked by carefully going through all possible cases of positive and negative values of the bounds. Similar changes can be made to computing the upper bounds.
possible for our final interval W to contain negative lower bounds due to loose element-wise intervals or other factors. Since importance weights are non-negative, negative importance weight bounds act the same way as zero lower bounds rejection sampling, and preserve our guarantees.
Finally, the requirement of an accurate classifier is already imposed by methods such BBSE to ensure the invertibility of the confusion matrix. Therefore, our Gaussian climination approach does not impose significantly stronger assumptions.
E PROOF OF LEMMA
For the first phase, we prove by induction f that (10) holds for all t. The base case = 0 holds by
assumption. For the induction step, we focus on Gj the remaining bounds Sj 9% follow similarly. There are three sub-cases each corresponding to one of the update rules in (TT).
d+1 [++ and 7/
For the first update rule 2+1 0. equation 10 follows since the Gaussian elimination algorithm
15

---

Published as a conference paper at ICLR 2024
guarantees that dj O. For the second and third update rules, equation 10 follows by direct algebra and the induction hypothesis. For instance, for i, > t, equation 13 holds, and similarly 25
For the second phase, the fact that & S S and w= S w² S w" follows by similar induction argument. Since Gaussian elimination guarantees that w" Cp 57- and we have shown that
w" W I [w,, W.), the claim follows.
F PROOF SKETCH OF THEOREM 3.2
First, Theorem 3.2 follows from equation 5, assuming the given confidence intervals W; [ w for cach importance weight wy is valid-ic.. w, E W, Equation 5 follows by Theorem in Park ct al. (02I). Roughly speaking, if w is known, then we can use a standard rejection sampling procedure based on W convert S., into set of i.i.d. samples from Q. Then, the PAC guarantee would follow by standard conformal prediction results, e.g., Park et al. (2020). When wi is not known, then intuitively, Park al.] (202T) takes the worst reparameterization trick to do so in computationally efficient way. Finally, by Lemma 3.1 we have w, W; for all E [n] with high probability, Theorem 3.2 follows by a union bound.
all te E W, They
G CONSERVATIVE BASELINE
We describe PS-C, the conservative baseline summarized in Algorithm 2 upper bound b 2 w² on the importance weight, we use the upper bound
particular, given an
(xxx))=(((((XX). Y) w < b Exx,r)) Y)].
As a consequence, we can run the original prediction set algorithm from Vovk 2012); Park et al. (019)) with a more conservative choice of that accounts for this upper bound.
Algorithm 2 PS-C: an algorithm using the CP bound in equation 21
procedure PS-C(Sm. TXX J,T,&,,,,, E, Sw: &c)
2:
C. T, 7 CPINTERVAL m. TX x ++ arg yax (,,w),
3:
< INTERNALGAUSSIINELLIICC, 2, g.
4: b b+ ma Wh
5:
return PS(Sm, J, ST, e//b,
Lemma G.1. Algorithm 2 satisfies the PAC guarantee under label shift equation 4
Proof. Having constructed the importance weight intervals w", can b maxke[K] Wa find conservative upper bound on the risk as follows:
EXx $ (x)( = 4(1 ((x,))((y & (x)))addy
=/ - p(c,)) & C+(x))drdy (
bE(x,r Cx)]..
(21)
Hence, using the PS prediction set algorithm with parameters (s/b, 8), the output is (E,8)-PAC.
H ORACLE IMPORTANCE WEIGHT RESULTS
Here, we show comparisons to oracle that is given the ground truth importance weights (which are unknown and must be estimated most practical applications). uses rejection sampling according to these weights rather than conservatively accounting for uncertainty in the weights. In contrast to our baselines (which need to estimate w), this oracle represents a "gold (yet not achievable) standard" to compare with. It enables to quantify the increase in average prediction set size due uncertainty in our estimates of w. stemming from (i) finite sample error, accounted for by Clopper-Pearre Pearson intervals, and (ii) label shift, accounted for by our interval Gaussian elimination algorithm.
16

---

Published as a conference paper at ICLR 2024
2,00
poidecton s4t emnur
1.75
5.12
2.00
1.75
1.25
1.50
g g.225
1.00
prediction
x 1.00
0.00
0.75
504
0.50
0.25
0.00
PS.CPS.R Ora Ora WWWP
0.00
P5 PS-CPS-R PS-WWCP
141
P5 PS-CPS-R PraPS-WWCC
0.00
P5 O.cPP--.OrrPS---e
(a) Prediction set emrrr and size on the CDC dataset.
(b) Prediction set error and size on the CIFARIO. Pa- rameters are 0.1, 6 = x 10 10-4, 27000,
Parameters 0.1, 6 = x 10 m 42000,
42000, 0 9750.
n 19997, and 19997.
Figure 5: Prediction set results with comparison to the oracle importance weight (Ora).
First, for the CDC heart dataset, we consider the following label distributions: source (94%, 6%). target: (63.6%, 36.4%); see Tigure[5a the results. Second, for the CIFAR-10 10 dataset, we consider the following label distributions: source (10% 10%, 10%, 10%, 10% 10%. 10%, 10%. 10%, 10%). target: (6.7%, 6.7%, 6.7%, 40.0%, 6.7%, 7%, 6. 7%, 6. 6.7%, 6. 6.7%, 6.7% 6.7%); see Figure 5b for results.
I ADDITIONAL RESULTS
1.1 CDC HEART
prodction sat artor
1.75
1.25
6.34
1.25
1.00
srediction
0:33
1.00
0.75
0:22
0.50
0.00.0
0.05
0.25
PS-C PSR PSW
PS-C
PS-R
PSW
PS PS-C
PS-R
PSWW
PS-C PSH PSW
(a) Prediction set error and size under small shifts on
(b) Prediction set error size under large shifts on
the CDC Heart dataset. Parameters are 0.05,
the CDC Heart datasct, Parameters are E 0.05, 5
5 x 10 m 42000, n = 42000, and = 9750.
5 x 10
= 42000,
42000, and o = 9750.
2.00
2.00
Evedction eero
1.75
3005
1.75
1.50
w.20
0.05
1.00
1.25
3.000
005
g 1.00
1.25
0.10
0.50
0.03
0.25
005
0.03
0.25
PS-C
PS-R
PS-W
PS-C PS-R PS-W
PS-C PS-R PS-W
P5 PSIC
PS-R PSWW
(c) Prediction set error and size under small shifts on
(d) Prediction set error size under large shifts on
the CDC Heart dataset. Parameters are = 0.03, =
the CDC Heart dataset, Parameters are è 0.03, 8 42000, and 9750.
5 x 10 42000. 42000, and = 9750.
5 x 10
42000,
Figure More Prediction set results with different hyperparameters on the CDC Heart dataset.
17

---

Published as a conference paper at ICLR 2024
1.6
16-
1.4
1.2
0.64
1.2
breeiston
0.8
gredict titt
0.0
0.8
010
0.4
0.05
0.05
0.2
0.0
(a) Prediction and size under reversed small shifts (91.3%% 8.7%) - (91%, 6%)) ) on the CDC Heart dataset. Parameters are 0.05, 5 = 5 10 42000, 42000, and 9750.
(b) Prediction and size under reversed large shifts (663.6% 36.1%) - (94%, 6%)) on the CDC Heart dataset, Parameters are : = 0.05, 6 = 5 10
42000, 42000, and 9750.
Figure 7: More Prediction set results with different hyperparameters on the CDC Heart dataset.
I.2
CIFAR-10
3.5
Devdccion set ernor
-- 0.05
2.5
0.35
0.030
0.03
3.0
2.0
0.255
2.5
0.020
1.0
0.15
1,5
0.10
0.5
PS-C PSR
PSW
PS-C PS-
PSW
P5
PS-C
PS-8
PSW
PS-C PS
PSW
(a) Prediction set error and size with larger shift on CIFAR-10. Parameters are = 0.05, 6 = x 10-4, 27000, 19997, and 19997.
(b) Prediction set error and size with larger shift
CIFAR-10. Parameters are 0.03, 5 = x 10-1
27000, 19997, and f 19997.
Figure 8: More Prediction set results with different hyperparameters on the CIFAR-I0 dataset.
1.3
AGNEWS
2:25
1.6
t=0.03
c= 0.10
predictio set aree
2.5
1.2
1.0
5 15
prediction
0.8
6:04
+
1:10
0.6
0.
0.2
P5
PS-C
PS-R
PS-W
0.0
PS
PS-C
PSR
PSW
PS-C
PS-R
PSW
PS
PS-C
PS-R
PSW
(a) Prediction set error and size on the AGNews Dataset. Parameters are E = 0.03, = 5 x 10-1
(b) Prediction set error and size on the AGNews Dataset. Parameters are = 0.1, 5 = 5 10 26000, 1 12800, and 12800.
m 26000, n 12800, and 12800.
Figure 9: More Prediction set results with different hyperparameters on the AGNews dataset.
1.4 CHESTX-RAY
0.30
0112
coddcctinn set eetor
0.30
0.5
redictionn. 995
2.03
r=0
2.04
0.0
4.5
P5 P5 P5R WWCP
P5 PS-C PS P5WW WCP
P5
PS
PS
PSW
PS
PSC PSR PSW
(a) Prediction set error and size on the ChestX-ray dataset. Parameters are 0.3, 5 5 x 10
(b) Prediction set error and size on the ChestX-ray dataset. Parameters
0.1, = 5 x 10
33600, 17600, and 3520.
67200.
35200, and ( 3520.
Figure 10: More Prediction set results with different hyperparameters on the ChestX-ray dataset.
18

---

Published as a conference paper at ICLR 2024
1.5 ADDITIONAL BASELINES
Class-conditional conformal predictors fit separate thresholds for each label and demonstrate robust- ness to label shift. In Figure II we show the conasicondiii results for both conformal prediction tuned for average coverage and PAC prediction set, the CDC and CIFAR-10 dataset. Here, LWCP is a baseline from the label-conditional setting from Sadinle et al. (2019), which does not satisfy PAC guarantee. PS-LW adapts the standard PAC prediction set algorithm (Vovk) 2012 Park et al. 2020) to the label-conditional setting; our approach is PS-W. Most relevantly, while PS-LW more conservative than our approach (PS-W) and produces prediction sets that are larger on average. Intuitively, it satisfies stronger guarantee than necessary for our setting, leading it to be overly conservative.
approximately satisfies the desired error guarantee,
prediction set error
0.10
1.2
0.08
1.0
0.8
0.06
size
0.6
0.04
0.4
0.02
0.2
E 0.10
0.00
0.0
PS-W PS-LW WCP LWCP
PS-W PS-LW WCP LWCP
Figure 11: Prediction set error and size the CDC dataset under small shifts. Parameters 0.1, 5 5 x 10-A, m = 42000,, n = 42000, and o = 9750.
Empirically, find that while APS improves coverage in the label shift setting, it does not satisfy our desired PAC guarantee. In particular, we show results for the APS scoring function with vanilla prediction in Figure as can be seen, it does satisfy the desired coverage guarantee. Due its unusual structure, it is not clear how APS can be adapted to the PAC setting, which is our focus.
1.2
0.10
prediction set error
1.0
0.08
0.8
size
0.6
0.04
0.4
0.02
0.2
E
0.10
0.00
0.0
PS PS-W APAC WCP APS
PS
WCP APS
Figure 12: Prediction set error and size on the CDC dataset. Parameters are e = 0-1, 5 10-1 42000, 42000, and 9750. Label distribution (94%, 6%) with small shift (91.3%,8.7%) in the target.
I.6 CIFAR-100 100
We show results on CIFAR-100 in Figure The scores are the logits of a pretrained ViT model. The results show that both PS-C and PS-W attain the desired coverage guarantee, while the remaining approaches not do so. Furthermore, PS-W W outperforms PS-C in terms of average prediction set size.
19

---

Published as a conference paper at ICLR 2024
In this case, both PS-C and PS-W are quite conservative, due to two main reasons. First, the Clopper- Pearson intervals can be conservative when is very small, and we need to divide 8 by K K(K + (1)+1)=a +1, since need to take union bound over (KK + 1) + 1 events in equation 8 Second, although our Gaussian "interval" elimination algorithm does uncertainty propagation in time O ),**) the resulting confidence intervals (w, )H) may be conservative, thereby amplifying the first issue. With more calibration data, our approach would be less conservative.
30
0.10
prediction set error
25
0.08
20
0.06
size
15
0.04
10
0.02
5
0.10
0.00
0
PS PS-C PS-R PS-W WCP
PS PS-C PS-R PS-W WCP
Figure 13: Prediction set error and size on the CIFAR-100 dataset. Parameters are & = 0.1. 8= 5 10 270k, 180k, and 5950. Label distribution ([1001) + [0.3%]) for source, and ([0.84%) x 99 + [16.8%] for target.
1.7 LARGE E
We provide results on larger choices of in Figures 14 15
1.6
prediction set error
0.30
1.4
0.25
1.2
1.0
0.20
size
0.8
0.15
0.6
0.4
0.05
0.30
0.2
0.00
0.0
PS PS-C PS-R PS-W WCP
PS PS-C PS-R PS-W WCP
Figure 14: Prediction set error and size on the CDC dataset. Parameters are 0.3, 5 42000, 42000, and 9750. Label distribution is (94%, 64) for source, and (63.6%, 4%) target.
10
I.8 NON-UNIFORM SOURCE DISTRIBUTIONS
We provide results with non-uniform source distribution in Figure 16
20

---

Published as a conference paper at ICLR 2024
0.25
1.6
+
E 0.20
prediction set error
1.4
0.20
1.2
0.15
1.0
size
0.8
0.10
0.6
0.4
0.05
0.2
0.00
0.0
PS PS-C PS-R PS-W WCP
PS
PS-C PS-R PS-W WCP
Figure 15: Prediction set error and size with large shifts on the CIFAR-10 dataset. Parameters are
0.2, 8 5 x 10 m 27000, 19997, and 19997.
2.5
prediction set error
0.10
2.0
0.08
size
1.5
0.06
1.0
0.04
0.02
0.5
0.10
0.0
PS
PS-C PS-R PS-W WCP
PS PS-C PS-R PS-W WCP
Figure 16:
Prediction set error and size on the CIFAR-10 dataset. x 10-4
Parameters are
34k, n 45k, and (10.53%, 5.26%, 15.79%,5526%9. 5.26%, 10.53%, 15.79%, 10.53%, 5.26%, 15.79%) for source, and (3.57%,7.14%, 10.71%, 35.71%. 3.57%,7.14% 10.71%, 3.57%, 7.14%, 10.71%) for target.
0.1,
45k.
Label distribution is
21


Reviews:
[{"review_id": "FYIT0zx8RT", "reviewer": "Reviewer_y3Aa", "summary": "The paper studies the problem of producing calibrated prediction sets under label shift. The authors propose a method with formal PAC guarantees that is based on propagating uncertainty via a Gaussian elimination algorithm.", "questions": "- Can performance be summarized by a single metric and what happens to performance relative to baselines in that case?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and very clear\n- It studies an important practical problem: calibrated uncertainty estimation\n- It introduces a novel approach with formal guarantees", "weaknesses": "- I am not entirely convinced by the empirical results. In many tables, certain models get better prediction set error, but the prediction set size can be worse, and vice-versa. It would be better to compare the performance of all methods using one metric. A proper scoring rule is a standard method to evaluate the quality of predictive forecasts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4pe8ItD8rN", "reviewer": "Reviewer_mNQN", "summary": "This paper proposes a new conformalized procedure to construct prediction sets with PAC guarantees in the presence of label shifts. The issue of prediction sets without PAC guarantees is an interesting one, which the paper does well to highlight. The proposed method essentially tunes the parameter of the conformity score function by importance weights. The authors also provide a theory to show that the prediction sets generated by the proposed method satisfy the PAC guarantee. Empirical experiments corroborate the merits of the proposed method.", "questions": "1. By the definition of $T_N(S_m,V,w^*,b)$ , the rejection sampling accept samples with a $1-m_{y_i}/b$ probability. But, a common operation in the rejection sampling [R1, R2 ] is to accept samples with a $m_{y_i}/b$ probability, i.e., $V_i\\leq m_{y_i}/b$. This confuses me, so could you elaborate more about the reason for this difference?\n\n2. In Figure 3, I have seen the mean error rates of PS-C and PS-W are smaller than other methods that consider label shift, such as WCP. Thus, can we directly reduce the value of $\\epsilon$ to get the PAC guarantee on WCP, as shown in Corollary 1 of [R3]? And, what is the difference between Corollary 1 of [R3] and the optimization problem in Eq 16? (I think they have the same mathematical meaning.)\n\n[R1] Park, Sangdon, et al., PAC Prediction Sets Under Covariate Shift, ICLR 2022\n\n[R2] Pagnoni, Artidoro, Stefan Gramatovici, and Samuel Liu. \"Pac learning guarantees under covariate shift.\" arXiv preprint arXiv:1812.06393 (2018).\n\n[R3] Vovk, Vladimir. \"Conditional validity of inductive conformal predictors.\" Asian conference on machine learning. PMLR, 2012.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper studies an interesting problem, i.e., uncertainty sets under label shift. \n\n2. This work is well organized, and the proposed method is well-described. I believe readers can easily get the core idea.\n\n3. The datasets used to evaluate the algorithm are well-connected with applications, and the corresponding results demonstrate the PAC guarantee of the proposed method.", "weaknesses": "1. Theorem 3.2 lacks a detailed proof procedure, although the authors provide an interesting discussion on the confusion matrix in section 3.3. Please let me know where the proof is if I missed.\n\n2. All experiments are conducted on small-scale datasets where the number of classes is small, but it is always desired to include large-scale experiments. Can you share any experimental results (e.g., on CIFAR100) compared with other methods?\n\n3. The proposed method primarily builds upon a combination of existing methods (i.e., Clopper-Pearson intervals [1], Gaussian elimination [2]) and it doesn't present significant theoretical novelty.\n\nI am willing to improve my score, if the authors can well address these concerns.\n\n[1] Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934.\n\n[2] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5hGzxecNpI", "reviewer": "Reviewer_onAF", "summary": "The authors consider the conformal prediction (CP) interval for the classification problem under the label shift setting, where the distribution of the labels may shift, but the distribution of covariates conditioned on the labels remains fixed. Following the estimation of the framework from previous work, the authors take into account the uncertainty in estimating the confusion matrix and distribution of predicted labels when constructing the prediction interval.", "questions": "1. When comparing the work of Sadinle (LWCP), the coverage is not guaranteed. However, in my perspective, it seems to be more proper comparing the proposed method to the class-specific construction which allows different cut-off for different classes and guarantees the coverage under arbitrary shift.\n2. Do you mean WCP instead of CP in Figure 2?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-explained and easy to follow.", "weaknesses": "see below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DgzT43XuOf", "reviewer": "Reviewer_2Pyj", "summary": "The paper introduces a novel algorithm for constructing prediction sets with PAC (probably approximately correct) guarantees under the label shift setting. The proposed method leverages the concept of importance weighting, drawing upon the confusion matrix and the distribution of predicted labels. The authors construct confidence intervals for these elements and develop an algorithm to propagate these intervals using Gaussian elimination. Through a rejection sampling-based approach (Park et al. 2022), they attain prediction sets with PAC guarantees.", "questions": "- On Page 3: $p(\\hat{y}|y) = P_{(X,Y)\\sim P_X} \\[g(X) = \\hat{y}| Y = y \\]$. Should it be $P_{(X,Y)\\sim P}$, since $g$ is trained on $X$ and $Y$.\n\nIn empirical studies:\n- On Page 7: \"We select $\\epsilon$ for each dataset in a way that the resulting average prediction set size is greater than one.\" This approach seems to deviate from the typical use of conformal prediction where any desired coverage level can be achieved. \n- According to (Guan and Tibshirani, 2022), a prediction $C(x) = \\emptyset$ would suggest that x is likely distant from the training data. This implies that we cannot assign it to any class and should consider it an outlier. I'm curious if the proposed method can serve a similar purpose in outlier detection.\n- On Pages 8-9: Why are the sample sizes for the CIFAR-10 and AGNews experiments different between the \"large shift\" and \"small shift\" scenarios?\n- How did you determine the number of iterations, $t$? In section 3, it seems $t$ should be $\\[K-1\\]$. However, in the empirical studies, \n$t$ appears to range from 10,000 to 20,000, even for binary classification problems. Also, does this imply a significant computational cost?\n- In Figure 5, you've replaced \"PS-W\" (the proposed method) with \"Ora\". I'm curious, did you use the oracle weight for the other methods as well?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper offers a method for uncertainty quantification in machine learning under label shift assumption. \n- The paper mostly relies mostly on previous work, the innovation is propagating confidence intervals through Gaussian elimination to quantify the uncertainty of weights.\n- The paper is overall well-written and organized.", "weaknesses": "- While a theoretical guarantee is provided, it is dependent on $\\tau$, which seems less meaningful.\n- The assumption that the confusion matrix is invertible might be too strong for real-world applications. The element-wise confidence intervals approach for importance weights can be computationally intensive, especially given the large number of iterations required.\n- The simulations could potentially be strengthened (see questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4vCcVJ1prZ", "reviewer": "Reviewer_tiZb", "summary": "The paper introduces an innovative algorithm for the construction of prediction sets that promises probably approximately correct (PAC) guarantees in scenarios with label shift. Such prediction sets provide a mechanism to capture uncertainties by predicting sets of labels instead of individual ones. The approach seeks to address the challenges posed by distribution shifts and applies importance weighting techniques to overcome these challenges, coupled with the novel introduction of Gaussian elimination for uncertainty propagation. The approach is validated empirically across a mix of datasets spanning multiple domains.", "questions": "How robust is the algorithm to extreme label shifts or when the shift is non-uniform across classes?\nHow sensitive is the approach to the estimation errors in the importance weights, and are there any mechanisms to mitigate potential inaccuracies?\nAre there computational overheads introduced by the Gaussian elimination procedure, especially when applied to large datasets?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Label shift is an inherent challenge in real-world datasets, especially in settings like healthcare where outcomes can dynamically change. Addressing uncertainty under such scenarios is a meaningful contribution.\n\nThe paper presents a fresh take on dealing with label shift by estimating importance weights and subsequently leveraging Gaussian elimination. The use of Gaussian elimination to propagate uncertainties in the domain of prediction set construction is notable and potentially groundbreaking.\n\nThe empirical evaluation covers a variety of datasets from distinct domains, lending more weight and general applicability to the findings.\n\nThe example provided for the ChestX-ray dataset effectively illustrates the applicability and significance of the approach in practical scenarios.", "weaknesses": "While the methodology is fundamentally sound, it might benefit from a more in-depth discussion or a visual representation to aid clarity, especially around the estimation and application of importance weights.\n\nIt would be helpful to know the performance of the proposed method in relation to existing approaches in more detail, especially to understand the trade-offs or advantages.\n\nIt's unclear how the method would perform under extreme label shifts or in scenarios with limited data availability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)