PAC Prediction Sets Under Covariate Shift
Authors: Sangdon Park
Edgar Dobriban
Insup Lee
Osbert Bastani
Venue: ICLR 2022 Poster (2022)
Keywords: probably approximately correct
prediction set
covariate shift
importance weight
calibration
Clopper-Pearson binomial interval
rejection sampling

Abstract: An important challenge facing modern machine learning is how to rigorously quantify the uncertainty of model predictions. Conveying uncertainty is especially important when there are changes to the underlying data distribution that might invalidate the predictive model. Yet, most existing uncertainty quantification algorithms break down in the presence of such shifts. We propose a novel approach that addresses this challenge by constructing \emph{probably approximately correct (PAC)} prediction sets in the presence of covariate shift. Our approach focuses on the setting where there is a covariate shift from the source distribution (where we have labeled training examples) to the target distribution (for which we want to quantify uncertainty). Our algorithm assumes given importance weights that encode how the probabilities of the training examples change under the covariate shift. In practice, importance weights typically need to be estimated; thus, we extend our algorithm to the setting where we are given confidence intervals for the importance weights. We demonstrate the effectiveness of our approach on covariate shifts based on DomainNet and ImageNet. Our algorithm satisfies the PAC constraint, and gives prediction sets with the smallest average normalized size among approaches that always satisfy the PAC constraint.

Published as a conference paper at ICLR 2022
PAC PREDICTION SETS UNDER COVARIATE SHIFT
Sangdon Park
Edgar Dobriban
Dept. of Computer & Info. Science
Dept. of Statistics & Data Science
PRECISE Center
The Wharton School
University of Pennsylvania
University of Pennsylvania
Sangdonpeseas.. upenn edu
Nobriban@whartenn upenn edu
Insup Lee
Osbert Bastani
Dept. of Computer & Info. Science PRECISE Center
Dept. of Computer & Info. Science
PRECISE Center
University of Pennsylvania lee0cis upenn.
University of Pennsylvania
obastani @seas upenn.
ABSTRACT
An important challenge facing modern machine learning how to rigorously quantify the uncertainty of model predictions. Conveying uncertainty is espe- cially important when there are changes to the underlying data distribution that might invalidate the predictive model. Yet, most existing uncertainty quantifica- tion algorithms break down in the presence of such shifts. We propose a novel approach that addresses this challenge by constructing probably approximately correct (PAC) prediction sets the presence of covariate shift. Our approach fo- the setting where there is covariate shift from the source distribution (where we have labeled training examples) to the target distribution (for which we want quantify uncertainty). Our algorithm assumes given importance weights that encode how the probabilities of the training examples change under the co- variate shift. In practice, importance weights typically need to be estimated; thus, we extend our algorithm to the setting where we are given confidence intervals for the importance weights. We demonstrate the effectiveness of our approach on covariate shifts based on DomainNet and ImageNet. Our algorithm satisfies the PAC constraint, and gives prediction sets with the smallest average normalized size among approaches that always satisfy the PAC constraint.
INTRODUCTION
key challenge in machine learning is quantifying prediction uncertainty. A promising approach is via prediction sets, where the model predicts set of labels instead of single label. For example, prediction sets can be used by robot to navigate to avoid regions where the prediction set includes an obstacle, or in healthcare to notify doctor if the prediction set includes a problematic diagnosis.
Various methods based on these approaches can provide probabilistic correctness guarantees (i.e.. that the predicted set contains the true label with high probability) when the training and test dis- tributions are equal formally, assuming the observations are exchangeable (Vovk et al.. 2005) Pa- Lei
padopoulos et al. 2002, Lei et al. 2015) or i.i.d. (Vovk 2013 Park et al., 2020a] Bates al. 2021 However, this assumption often fails hold in practice due to covariate shift-i.e. where the in- put distribution changes but the conditional label distribution remains the same (Sugiyama et al. 2007 Sorthonnro-Canndee et al.) 2009). These shifts can both natural (c.g.. changes in color and lighting) (Hendrycks & Dietterich 2019 adversarial (e.g., foo attacks) (Szegedy al. 2014).
We consider unsupervised domain adaptation (Ben-David et al. 2007). where we are given labeled examples from the source domain, but only unlabeled examples from the target (covariate shifted) domain. We propose an algorithm that constructs probably approximately correct (PAC) prediction sets under bounded covariate shifts (Wilks 1941
Valiant 1984 iie., with high probability

---

Published as a conference paper at ICLR 2022
1.22
C= 0.300
Ops
brain
029
WFSC1
brain,
Üps.w
Boo,
lallipp-- nurtle
600
(a) prediction set example
(b) size and error tradcoff
results across many shifts
Figure 1: (a) An example of a covariate shifted image where existing approach, PS (Park al, 2020a), constructs prediction sets that do not contain the true label (i.e., "sea turtle"); in contrast, our proposed approach PS-W does. (b) The red curve shows the tradeoff between size and error achieved by different choices of т on single shift; the goal is to be as far to the left as possible without crossing the desired error bound
0.1 shown the black dashed line. The existing approaches PS and WSCI (Tibshirani et al. 2019) fail to satisfy the desired error bound due to covariate shift, whereas our approach satisfies it. (c) Our approach satisfies the error bound over nine covariate shifts on DomainNet and ImageNet, whereas existing approaches do not.
the training data ("probably"), the prediction set contains the true label for test instances ("approxi- mately correct").
Our algorithm uses importance weights to capture the likelihood of source example under the target domain. When the importance weights are known, it uses rejection sampling (von Neumann 1951) to construct the prediction sets. Often, the importance weights must be estimated, in which case need to account for estimation error. When only given confidence intervals around the importance weights, our algorithm constructs prediction sets that robust to this uncertainty.
We evaluate our approach in two settings. First, we consider rate shift, where the model is trained on broad domain, but deployed on narrow domain-e.gg e.g., autonomous daytime and nighttime images but operate at night. Even if the model continues to perform well, this covariate shift may invalidate the prediction sets. We show that our approach constructs valid prediction sets under rate shifts constructed from DomainNet (Peng et al., 2019). whereas several existing approaches do not. Second, we consider support shift, where the model trained on one domain, but evaluated on another domain with shifted support. We train ResNet101 (He et al. 2016) using unsupervised domain adaptation (Ganin et al. 2016) on both ImageNet-C synthetic perturba- tions (Hendrycks & Dietterich 2019) and PGD adversarial perturbations (Madry et al.) 2017) to ImageNet (Russakovsky et al. 2015). Our PS-W W algorithm satisfies the PAC constraint, and gives prediction sets with the smallest average normalized size among approaches that always satisfy the PAC constraint. See Figure] for a summary of our approach and results.
may be trained both
Related work. Our work is related to conformal prediction (Vovk al. 2005 Balasubramanian ct al. 2014) without a shift, where the goal is to construct models that predict sets of labels designed to include the true label with high probability (instead of predicting individual labels) under the assumption that the source and target distributions are the same. In particular, our setting is related al. | 2015). where the training set is split into proper training set used to train a traditional predictive model, and calibration set used to construct the prediction sets. The general approach is to train model f X x y > IR that outputs conformity scores, and then to choose threshold E R that satisfies correctness guarantee, where the corresponding prediction sets are C(x) {y E y f(x, v) 2 7}
inductive (or split) conformal prediction (Papadopoulos al., 2002 Vovk 20133 Lei
PPar et al. 2020al Gupta al. 2021): this notation is defined in Section 2
Several kinds of correctness guarantees under no shift have been considered. One possibility is input conditional validity (Vovk) 2013] Barber et al., (020), which ensures correctness for all future co- variates x, with high probability only over the conditional label distribution p(y x)). This guarantee is very strong, and hard to ensure in practice. A weaker notion is approximate (Lei & Wasserman, 2014 Barber et al., (020) or group (Romano et al. 2019) conditional validity. which ensures cor- rectness with high probability over p(y x) as well Finally, unconditional validity ensures only correctness over the joint distribution p(z, y). We focus on unconditional validity, though our approach extends readily to group conditional validity.
distribution p(x) over subgroup.
2

---

Published as a conference paper at ICLR 2022
A separate issue, arising in the shift setting, is how to condition the calibration set Z. A conventional goal is unconditional validity, over the distribution p(z. y, 2). We refer to this strategy as fully unconditional validity. However, the guarantee consider uses separate confidence level for the training data, which is called a training conditional guarantee (Vovk) 2013); this correctness PAC correctness guarantee (Park et al. 2020a), and is also equivalent to the standard "content" guarantee with certain confidence level for tolerance regions (Wilks) [941] Fraser 1956). We build Park al. (2020a), which formulates the problem of choosing as learning a binary classifier where the input and parameter spaces are both one meeddimnsioonal: thus, the correctness guarantee corresponds to PAC generalization bound. This approach is widely applicable since it can work with variety of objectives (Bates et al. (021).
notion is equivalent
Recent work has extended inductive conformal prediction to setting with covariate shift (Tibshirani et al., 2019; Lei & Candès 2020); similarly, Podkopaev & Ramdas] (2021) considers conformal prediction under label shift (Lipton al. 2018). i.e., assuming the conditional probabilities p(x y) do not change. These approaches start from the assumption that the true importance weights (IWs) are known (Tibshirani et al., 2019 Podkopaev & Ramdas] 202T). or assume some properties of the estimated IWs (Lei & Candès 2020), whereas approach considers a special form of "ambiguity" in the estimated IWs. Furthermore, they are focused on fully unconditional validity, whereas we obtain PAC prediction sets. In addition, Cauchois et al. (2020) designs confidence sets that are robust to all distribution shifts with bounded /-divergence; in contrast, we consider the unsupervised learning setting where we have unlabeled examples from the target distribution. We provide additional related work in Appendix A
BACKGROUND ON PAC PREDICTION SETS 2
We give background PAC prediction sets (Park al. 2020a): we also re-interpret this approach using Clopper-Pearson confidence intervals (Clopper & Pearson 1934), which aids our analysis.
2.1 PAC PREDICTION SETS ALGORITHM
Let x E X' be covariates and y y be labels. We consider a source distribution P over X x ) with probability density function (PDF) p(z,, y) [ prediction set a set-valued function C: X + 2²
Inputs. We are given held-out calibration set Sm of i.i.d. samples (I,, ~ P for i E [m] = {1...., m], written as S, pm and a score function f: X' y + Rzo. For example, f(r., y) can be prediction for the probability that y is the label for z. The score function can be arbitrary, but score functions assigning higher scores to likely labels yield smaller prediction sets.
PAC prediction set. A PAC prediction sei is set-valued function C X + 2 satisfying the following two conditions. First, C approximately correct in the sense that its expected error (failing to contain the true label) is bounded by given 1).
Lp(C)= E(E.))~ [1 C(x))] (a.))~~ll & C(x) Se.
Second, noting that Csm, is constructed based on calibration set Sm pm the condition that Cs approximately correct must be satisfied with high probability- i.e., for given 5 E (0, 1), we have
IP Ps.., pm (Cp.Cs...) S c) 21 d
Our goal is to devise an algorithm for constructing a PAC prediction set C. Letting C(x) = y for all E X' always satisfies both conditions above, but this extreme case would be uninformative if used as a prediction set. Therefore, we additionally want to minimize the expected size EES(C(())) of the prediction sets C(x)), where S: : 2 + R>o size measure, which is application specific (e.g., the cardinality of a set in classification); however, we only rely on the monotonicity of the size measure with respect to the prediction set parameterization in construction.
All quantities that define measurable with respect fixed olagebrra on X V: for instance, p the density induced by fixed --ninte measure. To be precise, we consider probability measure P defined with
with respect to the hase measure M on X x V; then, p = dP/dM is the Radon-Nykodym derivative respect to M. For classification, . is the product of a Lehesgue measure on X' and counting measure on V. We use the term "prediction set" to denote hoth the set-valued function and set output by this function.
3

---

Published as a conference paper at ICLR 2022
Algorithm. To construct C, we first define the search space of possible prediction sets along with the size measure S. We parameterize C by a scalar 7 E T = Rz0 as
[(x; (v
7}
i.e., T is the threshold on f((z,)) v) above which we include in C(r).. Importantl, T controls the tradeoff between size and expected error. The reason that TI S T2. then Cr. (2) C Cr (x)
for all x X. Thus, size is monotonically decreasing in T r-c.., S(Cr, (x)) < S(C (z)) for all
I E X. and error is monotonically increasing in T r-ic., (C,,,) S (p( See Figure lb for an illustration, and Park et al. (2020a) and Gupta et al. (2021) for details.
As a consequence, a typical goal is to construct C, that provably contains the true label with high probability, while empirically minimizing size (Vovk et al., 2005 Gupta al. (021). In our set- ting, we want to maximize T (equivalently, minimize expected size) subject to the constraint that C. is PAC. Let L.s,, (C+) = (x.g)) (y C+(1)) be the empirical error count Sm. and
F(k; m. Eizo (1-))(=)" be the cumulative distribution function (CDF) of the binomial distribution Binom(m, with trials and success probability In prior work, Park al. (2020a) constructs C₁ by solving the following problem:
max T subj. Ls (C+) S k(m, TET
where k(m, e, 6) maK A: subj. to F(k; m, s) S 6. Intuitively, the PAC guarantee via this construction is related to the Binomial distribution; Ls., (C) has distribution Binom m. (C))) (given a fixed C). since (y & C(z)) has a BernoulliLpp(")) distribution when (z, y) P. Thus, k(m,e, E, defines "confidence interval" such that if T.s... (C) < k(m,e, 6)6, then CC( < Below, we formalize this intuition by drawing a connection to the Clopper-Peand Peapse- confidence interval.
with probability least
2.2 CLOPPER-PEARSON INTERPRETATION
We interpret using the Hloper-Pearson (CP) upper bound 0(k m),) E [0, (Clopper & Pearson 1934 Park et al., 2021), This is an upper bound on the true success probability 1t, constructed from sample k Binom(m, /)), which holds with probability least 6, i.e.,
P Pk--Binom(m..)) [4 $ 0(k: m, 6)] 1 - where
0(k; m, 8) = inf (0 E [0,1] F(): m, 0) S S0J
(2)
Intuitively, for a fixed C, Ls_ (C) ~ Binom(m, LP())), so the true error LP(C) is contained in the CP upper bound B[Ls.,. (C); m; 5) with probability at least - 8. Intuitively, we can therefore choose 7 so that this upper bound is E. However. we need account for generalization error of our estimator. To this end, we have the following (see Appendix (.addixx.xip for proof and Algorithm 2 in Appendix for implementation details on the corresponding algorithm):
Theorem Let Ucr(C C, Sm. 8) = -(L (O); m; 8), where 0 is defined in 2 Let & be the solution of the following problem
+ == max T
subj. to Ucp(Cr, Sm: Se.
(3)
TET
Then, have PP Pmn-Pa (Tp(Ct) s e) for any T S
PAC PREDICTION SETS UNDER COVARIATE SHIFT
We extend the PAC prediction set algorithm described in Section 2 to the covariate shift setting. Our novel approach combines rejection sampling (von Neumann [951 with Theorem
We consider trivial solution when 3 is not feasible, but omitting here avoid clutter.
4

---

Published as a conference paper at ICLR 2022
3.1 PROBLEM FORMULATION
We assume labeled training examples from the source distribution P are given, but want to construct prediction that satisfy the PAC property with respect a (possibly) shifted largel distribution Q- Both of these are distributions over X' x V/ denote their PDFs by p(æ; y) and q(z, y), respectively. The challenge that we are only given unlabeled examples from Q.
Preliminaries and assumptions. We denote the likelihood ratio of covariate distributions by w" (2) q(z)/p<z), also called the importance weight (IW) of x. Our main assumption is the covariate shift condition, which says the label distributions are equal (i.e., plu 2)) = g x)), while the covariate distributions may differ (i.e., we can have p(r) * q(z)).
Inputs. We assume a labeled calibration set Sm consisting of i..d. samples (z4, yt) ~ P (for i (m]) is given, and a score function f X x y - R20- For now, we also assume we have the true importance weights " == w² (x:;) for each (xi, V/ ~ P. as well as an upper bound 2 x w" (x) on the IWs. In Sections 3.3 and Appendix we describe how to estimate these
quantities in way that provides guarantees under smoothness assumptions on the distributions
Problem. Our goal is to construct Cs.,. that is a PAC prediction set under Q-i.e..
P sm.. pm (Cs(Cs...) S $] 2 1-6,
where LQ(C) == (xa))ool & (z)) is the error of on Q, while empirically controlling its size.
3.2
REJECTION SAMPLING STRATEGY
Our strategy is to use rejection sampling to convert Sm consisting of i.i.d. samples from P into labeled calibration set consisting of i.i.d. samples from Q.
Rejection sampling. Rejection sampling (von Neumann 1951 Owen 2013 Rubinstein & Kroese 2016) is a technique for generating samples from a target distribution (ax) based on samples from proposal distribution p(z). Given importance weights (IWs) w" (x) and an upper bound b > max w" (z), it constructs set of ii.d. samples from g(z). Typically, rejection sampling is used when the proposal distribution is easy to sample compared to the target distribution. In contrast, use to convert samples from the source distribution into samples from the target distribution.
In particular, and the target distribution to be our target covariate distribution Qx Let V2- ~ U = Uniform([o, 1)) be i.i.d., V = (V1,... Vn), and v² (wi, ...., w with wt w" (a:;) defined before. Then, given Sm, it uses rejection sampling to construct randomly chosen set of N samples
algorithm takes the proposal distribution to be the source covariate distribution Px,
(S V, ",,"",b) = ( y:) E Sm V S w//bb
(4)
from Qx The expected number of samples is E[N] = m//; thus, rejection sampling is more effective when the proposal distribution is similar the target.
Rejection sampling Clopper-Pearson (RSCP) bound. Given TN. our algorithm uses the CP bound to construct PAC prediction set C. for Q. Let a. 1(, < w /b) indicate whether example (Ii, 31) E Sm is accepted-i.e. (Sm, V, u .)) {(I,,, v1) E Sm a, = wJ.hhere (T'n(S., V, w² b)l -i=1 oi. Then, follows that URSCP bounds the error on Q, where
URSCP (C, Sm. V, 8) = UC,
V, oF" "r"",b)). 8),
(5)
Thus, have the following (see Appendix D33 for the proof, and Algorithm 4 in Appendix E for detailed deseription of the PS-R algorithm that leverages this bound):
Theorem Define URSCP as ( Let + be the solution of the following problem:
max T subj. URSCP(Cr, Sm, V, 1", ,, 0) S
(6)
TET
Then, we have Ps Pum (Lo(C,) < - for any F.
Note that V is sampled only once for Algorithm 4 so the randomness in V can contribute to the failure of the correctness guarantee; however, the failure rate is controlled by 6.
'In practice we improve stability of importance weights by considering source and target distributions induced by feature mapping, e.g., learned using unsupervised admainnad (Park al. 2020b).
5

---

Published as a conference paper at ICLR 2022
3.3 APPROXIMATE IMPORTANCE WEIGHTS
So far, we have assumed that the true importance weight w (a)) is known. Since in practice, it needs to be estimated, relax this assumption only needing an uncertainty set of possible importance weights. This allows us to handle estimation error in the weights.
Problem. Let S be unlabeled calibration examples from the source distribution (i.c., the covariates in Sm). T. be unlabeled calibration examples from the target distribution (denoted by T ~ ²%),, and w (wi,.., w ! be the vector of true importance weights w =" (xz), . for (Ia, Vi) E Sm. Then, we assume an uncertainty set W S I that has 27 with high probability, ie..
Psx P PT.TT
117" E W] 2 8m
where & E 10, We assume W has the form
W e Vi [m]
10 mz S we}
for some W, and W. See the discussion on our choice of W in Appendix C.1
Robust Clopper-Pearson bound. To construct a PAC prediction C' for Q, suffices to bound the worst-case error over E W, i.e., we have the following (see Appendix D.4 for the proof):
Theorem Suppose W satisfies 7. Define URSCP as in 5 Let be the solution of the following:
max TT
subj.
max URSCP Sm, V, w. d,)) Se.
wEW
Then, we have IPg
S.. Pm V~ QQ [Q)
8c dw for any T S.
key challenge applying Theorem 3 is solving the maximum over w W. We propose a simple
greedy algorithm that achieves the maximum.
Greedy algorithm for robust URSCP- The RSCP bound URSCP satisfies certain monotonicity prop- erties that enable us to efficiently compute an upper bound to the maximum in (8). In particular, C' makes an error on (Ii, y1) (i.c., Y4 & C(r,)), then URSCP is monotonically non-decreasing in w. w" (I,); intuitively, this holds since larger Wº increases the probability that (I;, Vs) is included in Ty (Sm: V, w", b), which in turn increases the empirical error (Tx V.u (C)) Con- versely, if C does not make an error (Ii, yi) (i.e., Y1 C(z;)), URSCP is non-increasing in w/. More formally, we have the following result (see Appendix D.5 for a proof):
Lemma For any i [m], URSCP (C, Sm, V,w" w", b, 8) is monotonically non-decreasing in w if y: & C(ri), and monotonically non-increusing in w if ye E C(x.).
Our greedy algorithm leverages the monotonicity of URSCP. In particular, given W and C, the choice
à = (wi,,... wm).
where
w
Wa
if & C(a.) if E C(x;)
(Vi (Vi E [m])
(9)
is the maximum value over W of the constraint URSCP (Cr, Sm, V, w. b, dc) in 8 i.e.
max URSCe C,, Sm, V, w. b, 6) = URSCP (C, Sm. V, úù b)
(10)
wEW
Thus, we have the following, which follows by 10 and the same argument as the Theorem 3
Theorem Suppose W satisfies 77. Define 0r.8% as in P making the dependency on t, SX
and TXX explicis, and URsCP as in 5y. Let 7 be the solution of the following problem:
max TET
T
subj. to URSCP (Cr, Sm. V, 1,,,s,88 8x.88XT b, dc) S E.
(1I)
Then, we have P Sm.PPm.Vaae V~ TX Qx [L((C+) < < &c 8m for any T S
Importance weight estimation. In general, to estimate the importance weights (IWs), some as-
sumptions on their structure required (Kanamori et al. 2009 Cortes et al. 2008 Nguyen al.)
We assume b is given for simplicity, but our approach estimates it; see Appendix C.2 for details.

---

Published as a conference paper at ICLR 2022
Algorithm PS-W: an algorithm using the robust RSCP bound in (20)
I: procedure PS-W T. f,9, T, Sw: dc, K, E)
W ESTIMATEIW T 9, ow: K, E)
(b) Compute an uncertainty set W
3: 4- [a W.
(b) Compute the maximum IW (see in Appendix C.2
4: return PS- (S-ROBUST((Sm.
W d,0)
5: procedure ESTIMATEIWS(SA.) T 9. Sw, K, E)
6: Construct bins B1, ......, Bx using described in Appendix B.2
Construct W using ....... Bx. S T I, dw and, E described in Appendix B.1
8: return W
9: procedure PS- PS-ROBUST(S f,g, T, W,b,e,o))
10:
V ~ Uniform((0, 1))
11:
for 7 E do do
(D) Grid search in ascending order
13:
Construct vp using given T, Sm. and W if URsCr(Cr, Sm, W, 6, dc) & then
14:
15:
max(f;7) 7)
16:
else break
17:
return
2010
Lipton al., 2018). We use cluster-based approach (Cortes al. 2008). In particular, heuristically partition the feature space of the score function f into bins by using a probabilistic classifier that separates source and target examples, and then estimate the source and target covari- ate distributions p(x) and g(x) based on the smoothness assumption over the distributions, where the degree of the smoothness is parameterized by E. Then, we construct the uncertainty set W that satisfies the specified guarantee in 7). See Appendix B for details.
Algorithm. Our algorithm, called PS-W, is detailed in Algorithm I it solves (0) and also performs importance weight estimation according to (17) in Appendix B In particular, [ constructs a prediction set that satisfies the PAC guarantee Theorem parameters (e.g., K, E, and grid search parameters).
See Section 4.1 for our choice of
EXPERIMENTS
We show the efficacy of our approach rate and support shifts DomainNet and ImageNet.
4.1 EXPERIMENTAL SETUP
Models. For each source-target distribution pair, we split each the labeled source data and unlabeled target data into train and calibration sets. We use a separate labeled test set from the target for evaluation. For each shift from source to target, based on ResNet101 (He et al., 2016), trained using unsupervised domain adaptation based on the source and target training sets. See Appendix F for details, including data split.
use deep neural network score function
Prediction set construction. To construct our prediction sets, we first estimate IWs by training probabilistic classifier g using the source and target training sets. Next,
g to construct heuristic IWs w(x) 1/g(s = 1 x) - 11, where & = 1 x is from source. Then, we estimate the lower and upper bound of the true IWs using Theorem 5 with F 0.001 and K 10 bins (chosen to contain equal numbers of heuristic IWs), where we compute the lower and upper Clopper-Pearson interval using the source and target calibration sets. Furthermore, given confidence level we use 8c 8 8/2. For the grid search in line 12 of Algorithm we increase by 10-7 until the bound URSCP exceeds 1.5c. Finally, we evaluate the prediction set error on the labeled target test set.
Baselines. We compare the proposed method in Algorithm I (PS-W) with the following:
PS: The prediction using Algorithm that satisfies the PAC guarantee from Theorem based on Park et al. (2020a), which makes the I.i.d. assumption.
PS-C: Clopper-Peare method addressing covariate shift by a conservative upper bound on the empirical loss (see Appendix for for details), resulting in Algorithm 3 that solves the following:
arg max TET
subj. to UCp(Cr, Sm, 8) S s/b.
WSCI: Weighted split conformal inference, proposed in (Tibshirani et al. 2019). Under the ex- changeability assumption (which is somewhat weaker than our i.i.d. assumption), this approach

---

Published as a conference paper at ICLR 2022
error
orror
0.10
1000
602
600
predletton
400
4.00
200
602
200
P5 W501
PS-C
PS-W
75
WSCC1
PS-C
15-W
002
PS-R
PS-M
PS-W
P5-R
PS-M
PSAW
(a) Comparison
(b) Ablation study
Figure 2: The prediction set error and size over 100 random trials under synthetic shift from Ima- geNet ImageNet-CI3. Parameters are m 20, 000, 0.1, and ò 10 (a) and (b) shows the box plots for comparison and ablation study, respectively.
provides correctness guarantees only for a single future test instance, i.e., it includes an con- fidence level (denoted in their paper) but not 8. Also, assumes the true IWs are known; following their experiments, we use the heuristic IWs constructed using g.
PS-R: The prediction set using A Algorithm that satisfies the PAC guarantee from Theorem 2 with the heuristic IWs constructed using probabilistic classifier g.
PS-M: The prediction set using Algorithm 5
which is identical to PS-R except that PS-M esti- mates IWs heuristically using histogram density estimation and a calibration set. In particular, partition the IW values into bins, project source and target calibration examples into bins based the value of the probabilistic classifier g, and estimate the source density PB and target density (n for each bin. The estimated importance weight is v(x) = (x)) ( pp (2)), where Pa and (B are
defined in 44 and (15). respectively.
Metrics. We measure performance via the prediction set error and size on a held-out test set-i.e., error the fraction of (x, y) such that y & C(xx) and size is the average of [C(x)] over z.
Rate shifts on DomainNet. We consider settings where the model is trained on data from a variety of domains, but then deployed on specific domain; we call such a shift rate shift. For instance, a self-driving car may be trained on both day and night images, but tested during the night time. While the model should still perform well since the target is a subset of the source, the covariate shift can nevertheless invalidate prediction set guarantees. We consider rate shifts DomainNet (Peng) al. 2019), which consists of images of 345 classes from six domains (sketch, clipart, painting, quickdraw, real, and infograph); we use all domains as the source and each domain as target.
Support shifts on ImageNet. Next, we consider support shifts, where the support of the target is different from the support of the source, but unsupervised domain adaptation is used to learn fea- ture representations that align the two distributions (Ganin et al., (0066;; then, the score function is trained on this representation. First, consider Image.NetCC (Hendrycks & Dietterich 2019), which modifies the original ImageNet dataset (Russakovsky et al.) 2013) using 15 synthetic pertur- bations with 5 severity levels. We 13 perturbations, omitting "snow" and "glass blur", which are computationally expensive to run. We consider the original ImageNet dataset as the source, and the all synthetic perturbations on all of ImageNet (denoted ImageNet-C13) as the target. See Appendix F.3 for data split. Second, we consider ad adversarial shifts, where we generate adversarial examples for ImageNet using the PGD attack (Madry et al.) (2017) with 0.01 tor -norm perturbations with respect to pretrained ResNet101. We consider the original ImageNet as the source and the adversarially perturbed ImageNet as the target.
4.2 EXPERIMENTAL RESULTS
We summarize our results in Table [ and provide more details in Figure in Appendix G.2 Our PS-W algorithm satisfies the PAC constraint, and gives prediction sets with the smallest average normalized size among approaches that always satisfy the PAC constraint.
Rate shifts on DomainNet. We use ε 0.1 and = 10-5. As can be seen in Table 1 the prediction set error of our approach (PS-W) does not violate the error constraint E 0.1, while all other comparing approaches (except for PS-C) violate it for at least one of the shifts. While PS-C satisfies the desired bound, is overly conservative; its prediction sets are significantly larger than necessary, making it less useful for uncertainty quantification. For the shift to Infograph in Table I PS- W achieves relatively larger average prediction set size compared to other shifts; this is because the classification error of the score function f over Infograph is large-71 28%, whereas
8

---

Published as a conference paper at ICLR 2022
Table 1: Average prediction set error and sizes over 100 random trials under rate shifts on Do- mainNet (first six shifts) and support shifts on ImageNet (last two shifts). We denote an approach satisfying the & error constraint by v, and otherwise. The "normalized size" is the size divided by the total number of classes (i.e., 345 for DomainNet and 1000 for ImageNet). Parameters are m = 50, 000 for DomainNet, m = 20, 000 for ImageNet, E 0.1, and å = 10-5 Our approach PS-W satisfies the e constraint, while producing prediction sets with the smallest average normalized size among approaches that always satisfy the error constraint. See Appendix G.2 for box plots.
Baselines
Ablations
Ours
Shift
PS
WSCI
PS-C
PS-R
PS-M
PS-W
error
size
error
size
error
size
error
size
eтror
size
error size
All
10.5
9.5
10.7
10.6
10.8
17.0
(0.944)
(0,099)
(0.093)
(0.044)
(0.04)
(0.030)
Sketch
X
13.1
X
18.6
141.7
28.2
26.1
40.3
(0.142)
(0.116)
(0.020)
(0.097)
(0.105)
(0,078)
Painting
X
15.4
X
30.0
125.4
37.7
34.5
52.8
(0.159)
(0.112)
(0.025)
(0.096)
(0.103)
(0.076)
Quickdraw
3.8
23.8
4.3
4.2
6.1
(0.069)
(0.097)
(0.021)
(0.088)
(0.087)
(0.067)
Real
8.7
7.2
47.8
8.7
7.1
11.8
(0.079)
(0,057)
(0.032)
(0.000)
(0.068)
Clipart
X
10.2
X
10.9
345.0
19.4
14.8
25.7
(0.105)
(0.101)
(0,000)
<0.060)
Infograph
X 36.4
X
165.1
345.0
202.6
177.4
216.4
(0.363)
(0.114)
(0.000)
(0.085)
(0.107)
(0.078)
ImageNet-PGD
5.5
4.7
1000.0
1000.0
7.8
13.9
(0,090)
(0.066)
(0.04))
(0.049)
ImageNet-C13
X
9.3
X
67.0
1000.0
1000.0
15.9
35.8
(0.127)
(0.111)
(0,000)
10.000)
(0.0613
mean normalized size
0.0338
0.0257
0.0047
that over Sketch is 37.16%. Even with the poor score function, our proposed approach still satisfies the 0.1 error constraint. Finally, while our approach PS-W generally performs best subject to satisfying the error constraint, we note that our ablations PS-R and PS-M also perform well, providing different tradeoffs. First, the performance of PS-W is significantly more reliable than PS-R, but in some cases PS-R performs better (e.g., it produces slightly smaller prediction sets on rate shifts but significantly larger sets on support shifts). Alternatively, PS-M consistently produces smaller prediction sets, though it sometimes violates the eπror constraints.
Support shifts on ImageNet. We show results for synthetic and adversarial shifts in Table | (and Figure 4 in Appendix G.2) As can be seen, the error of our approach (PS-W) is below the desired level. PS-R performs poorly, likely due to the uncalibrated point IW estimation-we find that cal- ibrated importance weights mitigate these issues, though accounting for uncertainty in the IWs is necessary for achieving the desired error rate; see Appendix G.3 for details.
For adversarial shifts, the target classification error of the cource-trained ResNet101 and the domain- adapted ResNet101 is 99.97% and 28.05%, respectively. Domain adaptation can significantly de- crease average error rate, but label predictions still do not have guarantees. However, our prediction set controls the prediction set error rate as specified by s. As shown in Figure 4 our prediction set function outputs a prediction set for given example that includes the true label least 90% of the time. Thus, downstream modules can rely on this guarantee for further decision-
Ablation and sensitivity study. We conduct an ablation study on the effect of IW calibration and the smoothness parameter E for PS-W. We observe that the IW calibration considering uncertainty intervals around calibrated IWs required for the PAC guarantee (e-g.. Figure 2b). Also, we find
that a broad range of E-s can be used to satisfy the PAC guarantee; we believe this result is due to the use of domain adapted score function. See Appendices G.3 & G.5 for details.
5 CONCLUSION
We propose a novel algorithm for building PAC prediction sets under covariate shift; it leverages jection sampling and the Poopeer-Pearson interval, and accounts for uncertain IWs. We demonstrate the efficacy of our approach on natural, synthetic, and adversarial covariate shifts on DomainNet and ImageNet. Future work includes providing optimality guarantees on the prediction set size, rigorous estimation of the hyperparameter F,, and incorporating probabilistic IW uncertainty estimates.

---

Published as a conference paper at ICLR 2022
Ethics statement. We do not foresee any significant ethical issues with our work. One possible issue is that end-users may overly trust the prediction sets they do not understand the limitations of our approach-e.go e.g.. it is only a high probability guarantec.
Reproducibility statement. Algorithms used for evaluation, including ours, are stated in Algorithm Algorithm 2 Algorithm 3] Algorithm 4 and Algorithm | along with hyperparameters for algo- rithms in Section 4.1 and Appendix Related code released The proof of our theorems are
stated in Appendix
D the required assumption is stated in Assumption
ACKNOWLEDDGMENTS
This work supported in part by ARO W91 INF-20-1--000- AFRL and DARPA FA8750- 18-C 18-C-0090, NSF award CCF 1910769, and NSF award 2031895 on the Mathematical and Scientific Foundations of Deep Learn- ing (MoDL). Any opinions, findings and conclusions recommendations expressed in this material those of the authors and do not necessarily refiect the views of the Air Force Research I. Laboratory (AFRI.), the Army Research Office (ARO), the Defense Advanced Research Projects Ageney (DARPA), the Department of Defense, the United States Government. The authors are grateful to Art Owen for helpful comments.
REFERENCES
Anastasios N Angelopoulos, Stephen Bates, Emmanuel Candès, Michael Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms achieve risk control. arXiv preprint 1rXi:22110.01052, 2021.
Vineeth Balasubramanian, ShennShyang Ho, and Vladimir Vovk. Conformal prediction for reliable machine learning: theory, adaptations and applications. Newnes, 2014.
Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-free conditional predictive inference, 2020.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei. Jitendra Malik, and Michael I Jordan. Distribution-free, risk-controlling prediction sets. arXiv preprint arXiv:2101.02703, 2021.
Shai Ben Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137- 2007.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning for differing training and test distributions. In Proceedings the 24th international conference Machine learning, pp. 81-88. ACM, 2007.
Glenn Brier. Verification forecasts expressed in terms of probability. Monthly weather review, 78(1):1-33 1950.
Emmanuel J. Candès, Lihua Lei, and Zhimei Ren. Conformalized survival analysis, 2021.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift, 2020.
Victor Chernozhukov, Kaspar Wüthrich, and Zhu Yinchu. Exact and robust conformal inference methods for predictive machine learning with dependent data. In Conference On Learning Theory, pp. 732-749. PMLR, 2018
Charles Clopper and Egon Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404 413, 1934.
Corinna Cortes, Mehryar Mohri, Michael Riley, and Afshin Rostamizadeh. Sample selection bias correction theory. In International conference on algorithmic leurning theory, pp. 38-53. Springer, 2008.
David R Cox. Two further applications of model for binary regression. Biometrika, 45(3/4): 562-565, 1958.
https:// thub. com/ http://hhhh...mmmmmgo//////aaaap
10

---

Published as a conference paper at ICLR 2022
Morris H DeGroot and Stephen E Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Sociery: Series D (The Statistician), 32(1-2):12-22 1983.
Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Few-shot conformal prediction with auxiliary tasks, 2021.
Donald Alexander Stuart Fraser. Nonparametric methods in statistics, John Wiley & Sons Inc, 1956.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversane training of neural net- works. Journal of Machine Learning Research, 17(59) 2016. URL ptr..orr//rrrr///////////..
papers/v17/15- html
Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift, 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv:100..05999 2017.
Chirag Gupta, Arun K. Kuchibhotla, and Aaditya K. Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Dan Hendryeks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. Proceedings of the International Conference on Learning Represen- tations, 2019.
Ying Jin, Zhimei Ren, and Emmanuel Candès. Sensitivity analysis of individual treatment effects: A robust conformal inference approach. arXiv preprint arXiv:2111.12161, 2021.
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach direct im- portance estimation. Journal of Machine Learning Research, 10(1u):1391-1445, 2009.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 4346 4356. PMLR, 2020.
Volodymyr Kuleshov and Percy S Liang. Calibrated structured prediction. In Advances in Neural Information Processing Systems, pp. 3474-3482, 2015.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon, Accurate uncertainties for deep learning using calibrated regression. arXiv preprint arXiv:1807.0026. 2018.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, pp. 3792-3803, 2019.
Donghwan Lee, Xinmeng Huang, Hamed Hassani, and Edgar Dobriban. T-cal: An optimal for the calibration of predictive models. arXiv preprint 2xXi::2033001800 2022.
Jing Lei and Larry Wasserman. Distribution-fre prediction bands for non non-mmraetriic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):71-96, 2014.
Jing Lei, Alessandro Rinaldo, and Larry Wasserman. conformal prediction approach explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1):29-43, 2015.
Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment effects. arXiv preprint arXiv:2006.06138 2020.
state of the art. Decision making and change in human affairs, pp. 275-324, 1977. Sarah Lichtenstein, Baruch Fischhoff, and Lawrence D Phillips. Calibration of probabilities: The
11

---

Published as a conference paper at ICLR 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. 122--133. PMLR, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0600 2017.
Ali Malik, Volodymyr Kuleshov, Jiaming Song, Danny Nemer, Harlan Seymour, and Stefano Er- mon. Calibrated model-based deep reinforcement learning. In International Conference on Ma- chine Learning, pp. 4314 4323, 2019.
Robert G Miller. Statistical prediction by discriminant analysis. In Statistical Prediction by Dis- criminant Analysis, pp. 1 1-54. Springer, 1962.
Allan H Murphy. Scalar and vector partitions of the probability score: Part i. two-state situation. Journal of Applied Meteorology, 122):273-282, 1972.
XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory,
56(11):5847-5861, Nov 2010. ISSN 1557-9654, doi: 10.1 10.11099i..20102266888 URL http:
7/dx. doi. org / 10. 1109/TIT 2010. 2068870
Art B. Owen. Monte Carlo theory, methods and examples. 2013.
Artidoro Pagnoni, Stefan Gramatovici, and Samuel Liu. Pac learning guarantees under covariate shift. arXiv preprint arXiv: 1xXiv:8//200639) 2018.
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. In International Conference on Learning Representations, 2020a. /
Sangdon Park, Osbert Bastani, James Weimer, and Insup Lee. Calibrated prediction with covariate shift via unsupervised domain adaptation. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020b.
Sangdon Park, Shuo Li, Insup Lee, and Osbert Bastani. PAC confidence predictions for deep ral network classifiers. In International Conference on Learning Representations, 2021. URL htttps://pperreye
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1406-1415, 2019.
John Platr. Probabilistic outputs for support vector machines and comparisons regularized likeli- hood methods. Advances in large margin classifiers, 1999.
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fre uncertainty quantification for classi- fication under label shift. arXiv preprint arXiv:2103.03323, 2021.
Dimitris N Politis.
Model-free prediction in regression. In Model-Free Prediction and Regression, pp. 57-80. Springer, 2015.
Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Distribution- prediction sets adaptive unknown covariate shift. arXiv preprint arXiv:2203.06116. 2022.
Joaquin Hulñooneo-Candell Masashi Sugiyama, Neil D Lawrence, and Anton Schwaighofer. Dataset shift in machine learning. Mit Press, 2009.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel J. Candès. With malice towards none: Assessing uncertainty via equalized coverage, 2019.
12

---

Published as a conference paper at ICLR 2022
Reuven Y Rubinstein and Dirk P Kroese. Simulation and the Monte Carlo method, volume 10. John Wiley & Sons, 2016.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 11(3))211-252, 2015.
Masashi Sugiyama, Matthias Krauledat, and Klaus- Roburt Muller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(May) 2007.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal predic- tion under covariate shift. Advances in Neural Information Processing Systems, 32:2530-2540, 2019.
Leslie G Valiant. A theory of the learnable. Communications of the ACM,
1984.
John von Neumann. Various techniques used connection with random digits. In A. House- holder, G. E. Forsythe, and H. H. Germond (eds.), Monte Carlo Method, volume 12 of National Bureau of Standards Applied Mathematics Series, chapter 13, pp. 36-38. US Government Printing Office, Washington, DC, 1951.
Vladimir Vovk. Conditional validity of inductive conformal predictors. Machine learning. 92(2-3): 349-376, 2013.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science Business Media, 2005.
Ximei Wang, Mingsheng Long, Jianmin Wang, and Michael Jordan. Transferable calibration with lower bias and variance in domain adaptation. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. neurips. pdf
19212-19223. Curran Associates, Inc., 2020. URL cc
Samuel S Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathe- matical Statistics, 12(1):91-96, 1941.
Chen Xu and Yao Xic. Conformal prediction interval for dynamic time-series. In International Conference Machine Learning, pp. 11559- 1569. PMLR, 2021.
Yachong Yang, Arun Kumar Kuchibhotla, and Eric Tchetgen Tchetgen. Doubly robust calibration of prediction sets under covariate shift. arXiv preprint arXiv:2203.01761, 2022.
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. Citeseer, 2001.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. Proceedings of the eighth ACM SIGKDD international conference on Knowl- edge discovery and data mining, pp. 694-699, ACM, 2002.
13

---

Published as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORK
Prediction sets under i.i.d. assumption. We built our proposed approach on the known PAC prediction set approach (Wilks) [941] Park et al. (020a) due to its simplicity and sample efficcinny.. As other candidates, nested conformal prediction (Vovk et al. 2005 Gupta et al. (022]) reinterprets multiple known conformal prediction approaches using a scalar parameteriztion of prediction sets; but different from Wilks
(1941) Park et al. (2020a), it is not known to provide PAC guarantees. Kivaranovic et al. 2020 provides a PAC style guarantee, but their approach is limited to regression and is sample-inefficient, i.e., it requires sample of size O(1/E"), while Park et al. (2020a) has a better sample complexity, as demonstrated in their paper.
Prediction sets under various settings. Prior prediction set algorithms have been considered in several settings. First, traditional conformal prediction (Vovk al. 2005) often considers the setting where labeled examples arrive sequentially from the same distribution; there has also been work extending conformal prediction the setting where the distribution time-varying (Politis) 2015] Chernozhukov et al.] [0188] Xu & Xiel [021] Gibbs & Candès [021). ). Alternatively, there has been
work on constructing cisk-controlling prediction sets for supervised learning setting (Vovk) 2013 Park et al. 2020a] Bates et al.) 2021 Angelopoulos et al. 2001). Finally, there has been recent work on conformal prediction in the meta- veta-learning setting (Fisch et al. (02T);; in particular, given a few labeled examples drawn from the new task, their approach leverages labeled examples from previous tasks to construct a conformal predictor for the new task, assuming the tasks are exchangeable.
Developments after our work. After work was made publicly available, Din et al. (202I) has developed a different, robust conformal inference approach to constructing prediction sets with estimated weights under covariate shift. Their algorithm assumes given upper and lower bounds on the importance weights, and uses the worst-case quantile over all weights that satisfy the constraint to set the critical values. Further, Yang al. (2022) have developed doubly robust approach to construct prediction sets satisfying approximate marginal coverage under covariate shift (which can be robust to estimating the weights and per-covariate prediction error). leveraging semiparametric efficiency theory. Qiu et al. (2022) have developed a parallel approach for the PAC case.
Calibration. An alternative way to quantify uncertainty is calibrated prediction (e.g., Brier 1950 Cox 1958 Miller, 1962] Murphy 1972. Lichtenstein et al.] 1977] DeGroot & Fienberg 1983 Guo lt al., 2017 etc), which aims to ensure that among instances with a predicted confidence p, the model is correct a fraction p of the time. Techniques have been proposed to re-scale predicted
confidences to improve calibration (Plati 1999. Guo et al., 2017, Zadrozny & Elkan 2000] 2002 Kuleshov & Liang] 2015:
Kuleshov et al. 2018 Malik et al. 2019); including ones with theoretical
guarantees (Kumar et al.
2019 Park et al. (021) and ones that handle covariate shift (Park et al.
2020b Wang al. (2020). There are also methods to rigorously test calibration, dating back to Cox
1958): Miller ( 1962). see e.g., Lee et al. (2022) for a recent approach. These approaches provide a qualitatively different form of uncertainty quantification compared to the one we consider.
e.g.,LLee
Rejection sampling, Rejection sampling (sometimes accept-reject sampling) is a well-known tech- nique (Owen) 2013 |Rubinstein & Kroese, (2066) dating back at least to von Neumann (1951). We highlight that most work on covariate shift relies on importance weighting; our rejection sampling approach relatively less common and more novel. In fact, the best of our knowledge, only Pagnoni et al. (2018) has used rejection sampling for a different problem in this area.
IW estimation. There has been long line of work studying the problem of estimating impor- tance weights (IWs), also called likelihood ratios, in way that provides theoretical guarantees. For instance, (Nguyen al. 2010) provides a convergence rate analysis of IW estimators- smoothness assumptions, they provide finite sample bound on the Hellinger distance between the true IW and estimated IW. Next, (Kanamori et al. 2009) shows a similar finite sample guarantee, assuming the true IW can be represented linear combination of kernels. Finally, (Cortes et al.) 2008) proposes non-parametric IW estimators, modeling the source and target distribution by his- tograms over clusters in sample space.
The IW estimation approaches can be used in conjuction with prediction set construction. Compared to Candes et al. (202I), which only guarantees asymptotic validity under certain assumptions the estimated IWs, Theorem 4 provides a snite-sample correctness guarantee. Furthermore, we explicitly describe algorithm for approximate IWs, required by Theorem 4 in Appendix B
14

---

Published as a conference paper at ICLR 2022
B IMPORTANCE WEIGHT ESTIMATION
In general, to estimate the importance weights (lWs), some assumptions on their structure are re- quired. A number of approaches have been proposed, with varying guarantees under different as- sumptions (Kanamori et al., 2009; CCortes et al. 2008 Nguyen et al. 2010; Lipton et al. 2018). We use cluster-based approach (Cortes et al. 2008); our approach compatible with any of these strategies if they can be modified to provide uncertainty estimates of the IWs.
In our approach, given a partition X' - By into bins, we can estimate the IWs based on the fractions of source and target samples in each bin. If the partition is sufficiently fine, then we can obtain confidence intervals around the estimated IWs with finite-sample guarantees. However, this strategy requires the number of bins in the partition to be exponential in the dimension of X'. Thus, in practice, we use a heuristic to construct the partition. We describe the cluster-based approach and our partition construction heuristic below.
B.1 CLUSTER-BASER APPROACH
We assume given unlabeled calibration sets S and T:X, where S consists of ii.d samples I; ~ p(x:) for [m]] and TX consists of i.i.d. samples x; q(x) for E [n]] respectively"i Roughly speaking, the cluster- based strategy estimates the average IW in each bin By; assuming p and q are roughly constant in each bin, these accurately estimate the true IWs. Let j(x) be the bin containing (i.e., (x)) and let
/ p(x') dx' and qn(x) == (f(x) s.t. Fj J q(x') da' B,
pn(x) = Pf(w) s.t. Pj
B3
be the (unnormalized) approximations of the densities p and q. respectively, that are constant on each bin. We assume that pæ and (B are accurate approximations:
Assumption Given E E R20, the partition satisfies
f [p(x) p()')((d de' s E' and f [a(x) q( SE (E] (12) Bj
Thus, p and 9 are roughly constant on the partitions. In general, 12 can hold for any E E R p and g are Lipschitz continuous and each B, is sufficiently small (see Appendix Bor for discussion). Then, under Assumption [ it can be verified that
(o(x) - p(x) - Ps (x) < E and
(e(x) .0)))()))> gb(x)) E (Vr E X))
(13)
where v(x) = Uj(m), and SB, dr' is the volume of bin B, (see the proof of Theorem 5 for the validity of 13 Next, we have the following empirical estimates of pg and q8, respectively:
pв(x) = P)(x) s.t. po
1
Σ
1 1 E B,) and
(14)
m
z'ESX
1
(B(x) = (i()) s.t. 4
Σ Z'ETX
1 (a' E Bj).
(15)
Now, 1(x' E Bj) has distribution Bernoullipp)) when x P, thus m P3 has distribution Binom(m.,)) P,). and p; is contained ity: in particular, let é be the Clopper-Peante Hopper-Pearson lower bound corresponding to the Clopper-Pearson Q(k; m, 6)]
Clopper- Clopper-Pearson interval around ÓS with high probabil-
upper bound defined in Section 2.2 i.e., IP (P==-Bimm(mm.a))
Then, we have
(m 29. m, 8') < P3 S 0mm m; 8')
(16)
with probability at least 1- 8' with respect to the samples S.X Combining the following result (and see Appendix D.6 for proof):
13 and 16). we have
We can use the same calibration set to construct IW's and prediction sets due to the union bound in Theo-
15

---

Published as a conference paper at ICLR 2022
Theorem Letting 8' (2K) and [u] + max{0, o) for all u E R. have
(n (n()): El
(n (n(
w(x) = 0 (m mm + E
I w (x) w(x)=
@ (m fB(x), m, -J+ (Vx E)
(17)
with probability at least 1 5w over S and T.X
We use these upper and lower bounds the IWs as the inputs and w to our algorithm-
W {w X I Ve E X, wxxx) S w((x) s wxx)),
and use max ((x) ma w as the maximum IW. If b is known, we need importance weights associated with source calibration samples S thus
simpler form of W as follows:
W = fw E RM Vi E [m], I we S <m
where w; == w(x;)) and w; w(x) 3 for o; E S.
Theorem Junder Assumption one way to construct uncertainty set W that contains the true IWs.
Corollary Given K E N, E R20. and dm E (0, 1), suppose Assumption is satisfied and W is Then, have
constructed using Theorem 5
Psy P TT TH Q fwo W] 2 21-6. 1
B.2 PARTITION CONSTRUCTION HEURISTIC
In general, exponentially many bins are needed to guarantee Assumption [ Instead, we consider an intuitive heuristic for constructing these bins, so that the importance weights w(z)-rrahhe than density functions p(x)) and g(x:) individually-arr roughly constant on each bin, inspired by (Park et al. [22T]] 2020b); standard heuristic for estimating IWs is to train probabilistic classifier g(s x) to distinguish source and target training examples, and then use these probabilitics to construct the IWs. In particular, define the distribution
1 (p()) 1(s 1)+ 2 (a(x)) 1(s 0).
g (a, y)
Then, letting g" (y x)) be the conditional distribution, have w (x) (s (= 1 ct al. 2007). Thus, we train g(s x) s gs x) and construct bins according to w(r) = 1/g(s
1|2) x) -1 Bickel
1, Le..
By fr X ((x) E [wz, w)+1)),
where 0 = wi S W2 S S WK++ = co. Finally, we describe how to train g. Let S.X and TX be unlabeled training examples from source and target, respectively; then, the set
R ((x, x S U ((x, 0) T.
consists of i..dd. samples (x,y) v) s* 5*xx,)) v). Thus, we can train R an using supervised learning. In practice, the corresponding IW estimates w(xx) can be inaccurate partly since w is likely overfit to R par which why re-estimating the IWs in each bin according to Theorem remains necessary.
B.3 DENSITY ESTIMATION SATISPYING ASSUMPTION 1
We consider the following binning strategy that satisfies Assumption D for Lipschitz continuous PDFs. In particular, assume the PDFs p(z) and q(x) are L-Lipschitz continuous for some norm ||- Then, for any given E, construct each bin B, such that
E
|| x'll 5 L L.
Va, E B₁,
16

---

Published as a conference paper at ICLR 2022
where by is the volume of bin By. Then, we know that
(p(x) p(a')l - L1|x - x'1l Dj
so
J,, (p(x)) =((x')(dxx"" E.
Similarly, have
[ B,
1a(x) - g(x')ldx' s E.
Thus, the bins satisfy Assumption I Finally, assuming || is the Loo norm, we describe one way to construct bins. In particular, construct bins by taking an E-net with (E/L) where the dimension of X. Then, we have
d+1
E
| x'11s 5
ed
L Uj
as desired.
C
ADDITIONAL DISCUSSION ON IMPORTANCE WEIGHTS
C.I APPROXIMATE IMPORTANCE WEIGHTS
In Section 33
assume W has the following form:
W = (w E R
S w s.)
However, considering the fact that the expected importance weight is one, i.e., [a>p[w"(x)) 1, the uncertainty set W that contains the true importance weights with high probability can be further constrained follows:
W = (w ERR Vi E [m] w w S w. S E w/ c
for some e and In particular, using the Hoeffding's inequality for example, and č such that W1, ... Wmm. can be the part of the true importance weight w" that satisfies the mass constraint En- lw" (x)) 1.
estimate
Recall that we have to find a maximizer in the uncertainty set W as in 8 however, due to the additional constraint on > i= wi in W", is challenging to solve the maximization problem exactly.
C.2 MAXIMUM IMPORTANCE WEIGHT ESTIMATION
To generalize our approach to estimate the maximum importance weight b, we redefine the uncer- tainty set W over importance weights as follows:
W == {w X
R Vz E X, w(x) S w(x) w(x)
some w : X' ++ and w - IR such that it contains the true importance weight w" with high probability-i.e..
sxx Px-rrTr Tx ~Qx
(w- E W 2 8m
(18)
Given this, the maximum importance weight is obtained as follows:
i max wr (xx)..
x
Considering that W can be estimated using binning as Appendix B the maximum importance weight is rewritten as follows:
max (T) max Wy x
(19)
]E[K]
17

---

Published as a conference paper at ICLR 2022
where
(n nj,n, 8') F Wj == [0 (m Py. m. 8') E]
Here, G. 8, m, 2,,8''E,, E.E,p, and 93 are defined in Theorem and Appendix
The guarantee (18) implies the guarantee (7). Thus, for the maximization over the uncertainty set in (8. we use the original definition W and the greedy algorithm for v in (9). Then, Theorem 4 with the estimated b using (19) still holds as follows:
Theorem Suppose Assumption is satisfied and W is estimated using Theorem Define wr S.X TN as in (9 and bsx b5x.TZ as 199. making the dependency on т, SX and TX explicit, and URSCP as in Let f be the solution of the following problem:
max 7 subj. Unscr(Ct, V, W,W, TN bexTT , dc) S 6. TET
(20)
Then, we have P sm V-tm
V T& (Ll sd) bc - for any T S f.
C.3 CHOOSING HYPERPARAMETERS
In general, there is no systematic way to choose the smoothness parameter E and the number of bins K; we briefly discuss strategies for doing
Number of bins K. The bins are defined in one dimensional space as described in Appendix [B.2] so follow the standard practice in the calibration literature for binning (Guo et al. 2017; Park al.) 2021) where K is between 10 and 20. As we are using equal-mass binning, we choose the number of bins that each bin contains sufficiently many source examples (in our case, 5000 examples) for the length of the Clopper- Pearson interval over IWs of each bin to be below some threshold (in our case, 10-3), which leads us to 10. We provide sensitivity analysis Appendix G.6
Smoothness parameter E. Estimating E (i.e., computing the integral of the difference of source and target probabilities) is intractable general as it requires that we perform density estimation in nigh-dimensional space (i.c.. 2048 in our case), and then integrate this density over each bin. To avoid this hyperparameter selection, we choose E equal to zero or close to zero (in our case, 0.001). Intuitively, we find that binning based on the surce-discriminatoo scores is an effective way to group examples with similar IWs; thus, the main contribution to the uncertainty is the error of the point estimate. We provide a sensitivity analysis on E in Appendix G.5) Importantly, note that PS-W even with = 0 satisfies PAC criterion. One direction for future work is devising better strategies for choosing E.
C.4 COMPARISON WITH WSCI
Guarantee. The main difference between WSCI and PS-W lies in the guarantee provided (rather than prediction size); PS-W provides a stronger guarantee than WSCI. In particular, WSCI does not provide PAC guarantee. Instead, to satisfy the coverage probability guarantee, it requires practice, we usually have a single
new calibration set for every new test example. However, held-out calibration set. Thus, our approach PS-W provides guarantee that holds conditioned on this set. This difference is illustrated Figure 3a which compares WSCI and PS- given the true importance weight. PS-W produces larger size than WSCI, but strictly satisfies the error constraint. The shortcoming of WSCI can also be observed in Figure in Tibshirani et al. (2019). which empirically shows that the guarantee only holds on average over examples.
Usage of IWs. WSCI requires the true IWs, whereas our method can use approximate IWs. Also, IW's are used differently. Given the true importance weights, WSCI uses the importance weights to reweight examples the calibration set, and PS- W uses the importance weights to generate a target labeled calibration set using rejection sampling.
18

---

Published as a conference paper at ICLR 2022
D PROOFS
D.1 PROOF OF THEOREM 1
First, note that the constraint in implies F(Ls,, m, I d: conversely, any value of satisfying F(Ls,,. (C+); m. I ó also satisfies Ls... (C+) I k(m, E, 8). Thus, we can rewrite (1) as
arg max T subj. to F(Ls,. (C+): m, 5.
TET
On the other hand, if satisfies
3. then by definition of (Cr Sm 8) [kk: m. we have inf E [0 F(Ls.. (C,); 0) = 8) U [1) s,
which implies that F(Ls,, (C₂); m, S 6 (since the infimum is obtained within the set since the binomial CDF F' is continuous in s). Conversely, any value of T satisfying F(Ls.. (C+): m, S
also satisfies Ucr(Cr, Sm, 5) S c. Thus, we can rewrite (3) as
arg TET
subj. F(Ls. (C+); 8,
implying ( and 3 equal. Thus, the claim follows from Theorem 1 of (Park et al. 2020a and the fact that the error Lp(C,) is monotonically increasing in т.
D.2 MONOTONICITY OF THE CLOPPER-PEARSON BOUND
The CP bound UCT enjoys certain monotonicity properties that we will need. Intuitively, the CDF decreases as the number of observations m increases while holding the number of successes & fixed, increases if both m and i are increased by the same amount (i.e., holding the number of failures k fixed). In particular, we have the following:
Lemma 2 We have (k;; m 1, 2 (k: 6) and 0(k 1;m 1,8) (kk m,
Proof. Recall that F(k; m. 0) is the cumulative distribution function of a binomial distribution Binom (m, 0), or equivalently of the random variable Σ X;, where X₃ Bernoulli()) are i.i.d.
Decreasing case. If k & m - 1, then we have
m-
X
Kisk
Σ
X Sisk
i=1
hence
m
P
X; k
CP
Σ
X; < k
i=1
so (k;; m. 0) S F(k; 1,
Then, we have
0(k;m,8) = inf (0 00, 00 F(k; m. ()
< inf (0 E [0. F(km 1,8) = (k; m 1,
thus 0 is monotonically non- non-increasing m.
Increasing case. We have
m-1
Σ X₁ 1 Σ Sk
1=1
hence
P
X; < -
C
Σ x
1=1
19

---

Published as a conference paper at ICLR 2022
so F(k 1:m 1,8) Flkm
Then, we have
0(k; = inf (0 [0, F(kmm, 0) s (1) 2 inf (0 E [0, 1] F(k 11mm-mm--- - 1,0) - 6) {1)
0(k 1;m 6):
thus P is monotonically jointly non non-decreasing in (m, k).
D.3 PROOF OF THEOREM 2
The rejection sampling prediction set consists of two steps: (i) generate target samples, using source samples Sm. importance weights w, and upper bound on their maximum value b, and (ii) construct the Clopper-Pearson prediction set using the generated target samples.
From rejection sampling, we choose Σ o samples from Sm, denoting them by Ty; here, N ~ Binom (m, 1/b), and 1/b is the acceptance probability (von Neumann 1951 1951) i.c.
(x b
b
where V Uniform (00 1]). The samples in Tn are independent and identically distributed, con- ditionally on the random number N of samples being equal to any fixed value n. The reason is that one can view the rejection sampling algorithm proceeding one by one. The first stage starts at the very beginning. and then each stage ends when a datapoint accepted, followed by starting a new stage at the next datapoint. The last stage ends at the last datapoint.
stages, iterating through the samples
Based only on the source samples observed in one stage, rejection sampling produces a sample from the target distribution. Thus, within each stage, produce one sample from the target distribu- tion, and because each stage is independent of all the other ones, conditionally on any number of stages reached, our produced target samples are iid. Thus, conditionally on each = n..
use the Clopper-Pearson bound
To this end, let (S,,, V) / explicitly denote the dependence on S., and V, and let
i F(Tw) arg max subj. to URSCr(C,, 8) S E.
TET
Note that conditioned on obtaining samples using rejection sampling (i.e., (S V,w, b)l = n)), we have F(Sm, V) - (TT,,, where _ denotes equality in distribution. Then, we have
P PmmmPmm / mm
[LQ(C=(s...)) v)) s
P sm pm v~um (L P SEIN =n] P[N n)
PT, ~m [Le S PPN =n]
n=0
m
(1 8) PPN =n
8,
where the inequality follows by Theorem
The claim follows.
D.4 PROOF OF THEOREM 3
First,
7 = arg max subj. to URSCP Smo $ S TET
(21)
20

---

Published as a conference paper at ICLR 2022
which satisfies P Pm. Voltim [L) S 1- dc by Theorem 2 Now, with probability least 1 Swn we have w² E W. Under this event, we have
URSCP(CT. Sm, V, w", b, 8c) I max URSCP(Cr, Sm, V, b, wEW
so & satisfies the constraint in (2 Thus, must have 9 S F. By monotonicity of LQ(C,) in T, we have (C+ I LQ(C,), which implics that
I' sm Pmm V-m .NW ~Q (C+) S < Sm..,P [C+) S òc, where the last step follows by Theorem 2 probability least 1 8w.
The claim follows by a union bound, since ii* E W with
D.5 PROOF OF LEMMA
Let t and e be IWs where w(x;) 2 v(x;) and w(xx) = v(x;) for j + i. Additionally, we use the following shorthands:
m
w(x;)
1hw =
Σ1
Vi S
b
i=1
{ E Sm
V w(x:)
Tau =
km
Σ
( $ C(x)),
Vi u(di))
n2 = Σ
b
1=1
Tn. = { Sm
v(x;)
V
and
b
kg =
E
1 & C(z)).
(T.
Here, The 2 The since wxxx;) 2 u(x;). Finally, recall that F(k; m. 0) be the cumulative distribution function of a binomial random variable Σm X,, where X; ~ Bern(f).
Non-decreasing case. If y4 & C(x:), there
cases to consider:
1. If vize) < V, < w(xe), bb b then can verify that nh n. + and kw K. + 1.
2. Otherwise, we can verify that new = n. and A = kig-
In both cases, kwr 2 ny and New 2 ny. Since 0 is monotonically jointly non-decreasing in (m, k) as in Lemma 2 we have
URSCP(C, Sm, V, we b,
Ucr( UCr(TTr... (C),8)
i (kiw Rew: 8)
2 0 (kp no, 5)
Ver(Ler,, (C),
URSCP Sm, V, 6,,
thus URSCP is monotonically non non-decreasing in w(z.).
Non-increasing case. If y; E C(Ix;), then kw = kg. Since 0 is monotonically non-increasing in m as in Lemma 2 we have URSCP (C, Sm, V, w. 6) = Ucr(TTT.. (C),5)
= Okkwi Tew 8)
Okkui Bey 8)
UCP(LT,, (C),6)
URSCP (C, Sm. V, b,
21

---

Published as a conference paper at ICLR 2022
thus URSCP is monotonically non-increasing in w(x)).
D.6 PROOF OF THEOREM 5
Recall that
pn(x)= = Σ
1 (x E Bj)
Σ
1 E BB)
j=1
2'ESX
K
(z(x)= = Σ
1 (z (x Bj)
Σ T'ET
1 (xx E B₁)
jml
/ p(x') dæ',
PB( Σ
1 (x B,)
B,
j=1
K
1 (I B,) / B,
(B(x)= = Σ
q(x') dæ', and
1=1
v(x) Uj(z) S dæ'.
BB(a))
Due to the assumption of 12 lu(x) pp(x)= - -xx((x) is bounded for any E B, as follows:
I p(z) di' - / B, p(z') dæ
1 B,
[u(x) p(x)= - p2(2)) =
p(x) -p(x)dd" )dx'
Bg
(p(x) - p(('') da
B3
E.
(22)
Similarly,
(m(x)) . g(x) - gg(x))] E.
(23)
Observe that mp(x)) ~ Binom m, Jw, p(x') p(x')da)) for any x E By; thus px is bounded with proba- bility at least 8' as follows due to the Clopper-Pearson interval (0. 0):
((mp());m,8') px(x) 0(,
(24)
Similarly,
((ng(x); 8') < gx(x)) 0(n((r);;n
(25)
From
23
24 and 25 the following holds:
0mpp(z); 6') E v(x) p(x) < ((mp(z): m,) + E and
((ng(=); E v(z) g(x) < ((n((z)) + E.
Therefore, for any By. wt (I)) is bounded as follows:
((ng(=):n, 8') < wx)
((x) (nq((x); n. 8')
mmp(()):, 8¹) + E
p(z) e(mp(x); 8') E'
Since we apply the Clopper-Pearson interval for K partitions for both source and target, the claim holds due to the union bound.
22

---

Published as a conference paper at ICLR 2022
E ADDITIONAL ALGORITHMS
E.1 PS ALGORITHM
Algorithm 2 PS: an algorithm using the CP bound in (3)
procedure PS(S.. J,T,e,
- for r E PETdo do UCP(CCr, 8) S then f + ma)
(D) Grid search in ascending order
else break
return 7
E.2 PS-C ALGORITHM
Algorithm PS-C: an algorithm using the CP bound in (3) with e/b
procedure P.-C(Sm. 6, return PS(Sm, eT
We describe the PS-C algorithm, which uses a conservative upper bound on the CP interval. Let
Lp(C)= = IE
(1 C(x))
(u,y)
LQ(C)= = I ((x)(()))
(a,4)~
w² (z) = g(z)
p(z)
b = max w (x). #EX
Then, have
LQ(C) = E
[1 (1 $ C(+))
(a.y)~
E
(z) C()))
(a.y)~
E
1b-1 C(+))
b F. (.u)>
( E C(+))
= bb(C
Thus, Lc(C) (C( E. Equivalently, (C S e Lp S e/b. As consequence,
we can choose C' based on the CP bound for the i.i.d. case (i.e., Algorithm 2b. except using the desired error of e/b (instead of e). The algorithm described in Algorithm
23

---

Published as a conference paper at ICLR 2022
E.3 PS-R ALGORITHM
Algorithm 4 PS-R: an algorithm using the RSCP bound in 66)
procedure PS-R(Sm: f.7 T, w, 6,
V Uniform( 1)
5- 0
for T E T do
(D) Grid search in ascending order
if URSCP((Tr, Sm, V,w, (,,,,,) b, S then f max(f,
else break
return f
E.4 PS-M ALGORITHM
Algorithm PS-M: an algorithm using the RSCP bound in (6) along with IWs rescaling
procedure PS-M(Sm: m. T.X. [ T, w. 6)
(a(z) for æ E X, where PB and iB are defined (4) and 15 respectively ((x) < )n(a))
return PS-R(Sm- m. J, T, v0, b,8,
F EXPERIMENT DETAILS
F.1 DOMAIN ADAPTATION
We use a fully-connected network (with two hidden layers, where each layers has neurons followed by ReLU activations and 0.5-dropout layer) as the domain classifier (recall that the input of this domain classifier the last hidden layer of ResNet101). We use the last hidden layer of the model example space X, where its dimension is 2048. For neural network training, stochastic gradient descent (SGD) for 100 epochs with an initial learning rate of 0.1, decaying by half once every 20 epochs. The domain adaptation regularizer is gradually increased in (Ganin)
et al. 2016 We use the same hyperparameters for all experiments.
F.2 DOMAINNET
We split the dataset into 409,832 training, 88,371 calibration, and 88,372 test images.
F.3
IMAGENETC-13
We split ImageNet into 1.2M training, 25K calibration, and 25K test images, and ImageNet-C13 into 83M training, 1.6M calibration, and 1.6M test images.
To train model using domain adaptation, due to the large size of the target training set, we sub- sample the target training be the same size as the source training set on for each random trials.
G ADDITIONAL RESULTS
G. SYNTHETIC RATE SHIFT BY TWO GAUSSIANS
We demonstrate the efficacy of the proposed approaches (i.e., PS-R with the known IWs and PS-W with the estimated IWs) using synthetic dataset consisting of samples from two Gaussian distribu- tions.
Dataset. We consider two Gaussian distributions W(, Σ) and N(,, E') over 2048 dimensional covariate space X. Here, / 0; E and E' are diagonal where Σ1,1 52. Σ, 10-1, E 1,
24

---

Published as a conference paper at ICLR 2022
size
error
Size
2.00
2.00
0.04
prediction sel e17O2
0.01
1.55
0.22
91..50
1.25
1.25
prediction
0.02
0.02
0.75
0.75
0.22
0.50
0.01
0.50
0.25
0.00
0.00
With the known true IW
(h) With estimated IW
Figure 3: Error under the rate shift by Two Gaussians (over 100 random trials). Parameters are m 50, 000, 0.01, and 5 10-5
and E 10 for ( 2048). We consider the "flat" Gaussian N(,, Σ) the source and the "tall" Gaussian NH,, E") the target. Intuitively, there is rate shift from the source the target-i.e.. the target examples are subset of the source, but occur with higher frequencies. We use the following labeling function: ply x) (5xx1), where the sigmoid function. Finally, we generate 50,000 labeled examples for each training, calibration, and test.
Results. We consider different setups: the true IW is known, and 2) the IW is unknown. In Figure 3al we demonstrate the prediction set errors given the true IW. As expected PS-R satisfies the PAC guarantee- iie., the eттоr is below E. However, as shown in Figure [3b when we need to estimate IWs, using just the point-estimate of the IW results in PS-R performing poorly in terms of prediction set error; still satisfies the constraint, but the error close to zero, indicating that the prediction set size is too large to be useful for an uncertainty quantifier. In contrast, PS-W (i.e., rejection sampling based on interval estimates of IWs) produces a larger, more reasonable error rate while still satisfying the PAC condition. These experiments demonstrate that PS-R works well when given the true IW, but accounting for IW uncertainty is important when using estimated IWs.
25

---

Published as a conference paper at ICLR 2022
G.2
PREDICTION SET SIZE AND ERROR
size
6920
0.34
f- 0.10
prediction 5e2 00000
0.08
prediction set size
prediction SCt 0770
0.00
250
0.06
0.08
200
150
0.02
0.10
PS WSCI PS-C PS-W
WSCI PS-C PS-R PS-W
P5
WSCI
PS-C
PS-W
WSCI
PS-C
PS-W
(a) All
(b) Sketch
orfor
350
emror
350
0.00
300
0.10
300
0.00
250
250
0.66
200
3.130
150
0.04
100
2,00
100
3.00
50
3.00
(c) Clipart
(d) Painting
error
size
error
0.00
175
0.30
g 1550
prediction set arrer
0.00
g
150
175
prediction st
125
5 125
0.06
prediction
0.44
50
25
0.00
P5
WSCI
PS-C PS-W
WSCI
PS-C
PS-W
0.00
P5
WSC1
PS-C
PS-W
WSCI
PS-C
PS-W
(e) Quickdraw
(f) Real
size
emrrr
size
orsdlction 6ntor
0.25
- 0.10
300
350
predittion esror
0.12
prodiction set size
1000
0.25
250
200
150
0.06
400
100
0.04
200
0.10
WSCI PS-C PS-W
PS
WSCI
PS-C
PSWW
WSCI
PS.C PS-W
P5
WSCI
PS-C
PS-W
(g) Infograph
(h) ImageNet-C13
size
predi ctlnn set size
2.03
800
5.6
600
prediction
2.04
400
3.00
200
3.0
P5
WSCI
PSC
PS-W
PSC PSWW
(i) ImageNet + PGD
Figure 4: Prediction set error and size under rate shifts on DomainNet (a-g) and under support shifts on ImageNet (h, i) (over 100 random trials for error and over held-out for size). Parameters are = 50, 000 for DomainNet and m 20, 000 for ImageNet, = 0.1, and = 10
26

---

Published as a conference paper at ICLR 2022
G.3
ABLATION STUDY ON CALIBRATION
5ize
0.20
300
200
pradictio 0010E
prediction set error
250
0.28
150
200
0.29
150
100
75
2-
0.10
50
0.22
0.10
25
50
PS-R
PS-M
PS-W
PS-R
PS-M
PS-W
PS-R
PS-M
PS-W
PS-R
PS-M
PS-W
(a) DomainNet-Skeenn Sketch
(b) DomainNet et-Clipart
error
size
error
0.10
250
40
prediction 617Or
prediction set eirer
35
0.00
200
0.28
150
25
20
100
0.04
15
F-0.10
0.00
PS-R
PS.M
FS-W
PS-R
PS-M
PS-W
0.00
PS-R
PS.M
PS-W
PSIR
PS.M
PS-W
(c) DomainNet-Paintion
(d) DemainNet -eiikkrrrw
error
ertor
80
0.00
70
orediction Eet arro
0.20
0.28
pedicton
0.00
0.00
5 200
0.04
30
150
100
0.0.22
8 0.10
50
PS-W
0.00
Domain
(f) Domain
0.10
error
size
0.20
error
1000
size
prediction 6TTOr
crediction set crerr
0.00
800
0.06
400
0.04
200
200
x=10.11
0.00
PS-R
PS-M
PS-W
PS-R
PS-W
0.00
PS-R
PS.M
PS-W
PS-R PS-M
(g) ImageNet-C13
(h) ImageNet-PGD
Figure 5: Ablation study on calibration (over 100 random trial for error and over a held-out test set for size). PS-R does not rescaled IWs, PS-M uses point estimates of rescaled IWs, and PS-W uses intervals around rescaled IWs. Parameters are m = 50, 000 for DomainNet shifts, m = 20, 000 for ImageNet shifts, 0.1, and 8 10-5 In particular, ignores the worst-case IWs as in Theorem 3 instead, rescales the importance weights in each bin via a point estimate, i.e., Theorem 5 without the Clopper-Pearson interval (i.e., with E = 0. As can be seen in the results on the shift to various domains, our approach satisfies the PAC guarantee but this version does not-in fact, its error is even worse than PS-R, which uses the non-rescaled importance weights from the probabilistic classifier s.
consider variant PS-M of PS-W that
oc) and
27

---

Published as a conference paper at ICLR 2022
G.4
COMPARISON WITH VARIOUS TOP-K K PREDICTION SETS
5ize
5ize
2m 0.10
100
2.35
0.10
300
0.30
250
orodiction 20t
200
prediction
60
orediction
prediction
150
40
2.30
100
(a) All
(b) Sketch
200
prediction set eror
e- 0.10
250
177
200
prediction
0.13
0.20
125
75
prediction
150
100
25
Topto
(c) Clipart
(d) Painting
error
error
80
0.35
prediction set eitor
3.23
40
prediction S2t
0.20
50
prodiction
3.15
0.55
30
10
20
6:05
Tust2
Tect0
Topo2
PSW
3.01
Tepl
Test0 Tapt0 15:47
Tept
16630 lop50
(c) Quickdraw
(f) Real
350
credictio set 2700
300
prediction set error
prediction on Set size
250
200
0.3
150
100
50
0.0
Typl
Topt Teplo Tepto PSW
0
Teat Toos
Teato Tepio HEW
0.0
Tept
Tips
Topio Toplo PMW
1451
TA0
Topon Thois P0
(g) Infograph
(h) ImageNet-C13
error
0.25
0.10
prediction size
0.20
200
130
0.30
100
0.05
50
Tepl Tap3 Top2o
Ta250
Top3
Top3o
FS-W
(i) ImageNet PGD
Figure 6: Prediction set error size size under rate shifts on DomainNet (a-g) and under support shifts on ImageNet (h, i) (over 100 random trial). Default parameters are 50, 000 for DomainNet and m = 20, 000 for ImageNet, = 0. and ò = 10 5 A Top-K prediction set is prediction set that contains top labels based on a domain-adapted score function; thus the set size always K. As can be seen in the prediction set error plots, Top- prediction sets do not consistently satisfy the desired guarantee. Moreover, the prediction the Top-50 prediction set error rate almost achieves the desired error rate, e.g., (6d), the mean and medial the corresponding prediction set size larger than PS-W.
size worse than PS-W. W. For example, when
28

---

Published as a conference paper at ICLR 2022
G.5 VARYING SMOOTHNESS PARAMETER
0.100
predittoo set error
grediction S2t e/10n
0.00
0.00
150
0.04
75
50
(a) All
(b) Sketch
predictin set err0r
0.08
prediction set error
0,00
250
200
150
6.04
50
0.001
0.005
(c) Clipart
(d) Painting
prediction set eroo
0.10
prediction set eerer
0.10
250
2.00
70
0.00
60
3.00
40
30
100
5.00
3,00
50
0
0.001
0.005
0.01
0.001 0.005
(e) Quickdraw
(1) Real
== 0.10
2.3
prediction set ertor
6.08
predicton set error
400
3.09
200
0.02
100
3,02
50
100
0.001
0.005
0.01
0.001 0.005
0.01
gg) Infograph
(h) ImageNet-C13
1... a= 0.10
200
prodictin pet arror
175
125
100
50
6.31
2.605
0.001
(i) ImageNeet PGD
Figure 7: Prediction set error size size under rate shifts on DomainNet (a-g) and under support shifts on ImageNet (h, i) (over 100 random trial) for varying E. Parameters DomainNet and m = 20, 000 for ImageNet, E in Assumption bounds the quality our estimates of p(x) and q(x); since these errors cannot be conveniently measured, we have chosen it heuristically as hyperparameter. In this figure, we show the error of PS-W W as function of F. As F. becomes smaller, the prediction sets become more optimistic while still satisfying the PAC guarantee. Note that the optimal case is F. = O, since PS-W still satisties the PAC guarantee; this result suggests that our IW estimates are reasonably accurate.
50, 000 for 0.1, and 5 10 5 In particular, the parameter
29

---

Published as a conference paper at ICLR 2022
G.6 VARYING NUMBER BINS
E=0.10
E 0.10
prediction S8t 6110r
prediction set enT0r
175
0.00
150
6..6
8
100
75
100
0.92
25
23
15
20
10
15
20
(a) All
(b) Sketch
5- 0.10
6- 0.10
prediction 32t e110N
prediction set estor
250
250
8.68
200
100
100
3.02
50
50
10
15
20
10
20
(c) Clipart
(d) Painting
6.15
0.13
== 0.10
== 0.10
predictionee sertonneeee orrer
Dredcctionse error
200
8.06
2.08
30
0.04
20
0.04
100
50
5.00
3.00
10
15
20
5
10
20
(c) Quickdraw
Real
predction error
350
prediction set enror
0.10
0.22
300
3.00
400
250
3.00
8.06
300
0.04
200
3.00
100
6.00
13
15
23
2.00
15
23
15
20
(g) Infograph
(h) ImageNet-C13
400
predictin set arer
350
200
200
6:04
150
100
50
K
10
15
20
(i) ImageNet + PGD
Figure 8: Prediction set error size size under rate shifts on DomainNet (a-g) and under support shifts on ImageNet (h, i) (over 100 random trial) for varying K. Parameters are 50, 000 for DomainNet and m = 20, 000 for ImageNet, = 0.1, and 8 = 10-5 In general, must be chosen to be small enough so each bin contains sufficiently many source examples to achieve small Clopper-Perasee interval size (e.g.. 10-3), though also needs to be sufficiently large to satisfy the smoothness assumption.
30

---

Published as a conference paper at ICLR 2022
G.7
PREDICTION SET VISUALIZATION
Example
Crs(z)
(())
Example a
Crs(x)
wrs)
angel, cello, harp, microphome, piano, violin
raccoon
owl, raccoon
angel, harp
dolphin,
bread, grapes,
shark, snorkel, submarine, whale
wine bottle
shark, snorkel
wine glass
coffee cup, cup, mug. teapot
campfire, ocean, star, tent
coffee cup, cup
campfire
hurricane, occan, square, tornado
brain, fish, lion, lollipop, turtle
ocean
brain
hod, beit, birthdlay cake, guitar, had,
fire hydrant, foot, penguin, telephone
hat, hot tub
penguin
tiny paint can, pillow.
tqjanggss, basket, bread, carror, harp, lobsters bootibroshh
base baseball but. bread, light bulb. union, potato
[asparagus] { }
baseball, onion
Figure 9: Prediction of the DomainNet shift from All Paint. Parameters & = 0.1, and = 10-5, The green label is the true label and the label with the hat is the predicted label. We choose examples where the two approaches differ; in particular, if PS-W is incorrect, then PS is incorrect as well since the prediction set sizes are monotone in T.
50, 000,
31

---

Published as a conference paper at ICLR 2022
Example x
Cps(2)
(())
Example x
Ces(a)
Cps w
photocopier)
printer, photocopier
limber wolf, red wolf, dingo
limber wolf, white walr, walf, enyose, dinngo
aireraft carrier, sirliner, nirship. container ship, stopwstchs, pancchute tank, warplani, wing
forklin, gokart, golfeart, hurvesier, lawi pickup. snow plowplow, thressher, tracktor
airliner,
focklidh, golicaat, harvester, lawn mowerr snowplow. tracktor
airship, warplane
leopard, leagand, cheetah
Icopard, loopard, jaguar, cheetah
diancudback, sidewinder
hognose snake, dismondbuck, inder
ent. center, monitor, screen, television
analog clock, buromeser. odometier stogwatch. wall clock
aealog clack, bas mmmmmeeter, diginal watch, mag. compuss, odometer, stopwatch, clock
television
burbell, barometer, car wheel. dumbielll,
chamelcon, green lizard
chameloon, lizard, green wallng stick, mantis
barbell, dumbbell, lens cap, puck
lens power puck,
stethascope
Pembroke, Cardigan }
Pembroke, Cardigan
faee powder,, lipstick, paintbrush
bailpocine face powde, lipetick, painthmish, perfome, sunscreen
Figure 10: Prediction sets of the shift from ImageNet ImageNet-C13. Parameters are m 20, 000, = 0.1, and = 10-5, The green label is the true label and the label with the hat is the predicted label. We choose examples where the two approaches differ; in particular, if PS-W is incorrect, then PS is incorrect as well since the prediction set sizes are monotone in т.
32

---

Published as a conference paper at ICLR 2022
Example
Crs(
(ar)
Example x
Crs(a)
Öps Cys-w(ar)
brain coral, starfish, urchin
coral, chitos,
box turtle
terrapin, box turtle
seu unchin, cucumber, coral reef, stinkhorn
while terrier, kuvasz, komondor
Maltese dog. white serrier, komonder, Samayya
red fox, kit fox
kit fox
leaf beetle, ladybug
ladybug
tusker
tusker, elephan!
beaker, beer bottle, perfume, pop bottle, water bottle, wine bottle
beaker, pop bottle, water bottle, wine bottle
banjo, elec guitar, stage
acou guitar, banjo, elec. guitar, stage
car wheel, convertible, sports car
breastplate, cuirass
convertible, sports car
cuirass
crash helmet
bunnet, creec holmet, foutball helmes
confectionary
confectrairry
Figure 11: Prediction sets of the shift from ImageNet ImageNet-PGD. Parameters are m 20, 000, = 0.1, and ò = 1 The green label is the true label and the label with the hat is the predicted label. We choose examples where the two approaches differ; in particular, if PS-W is incorrect, then PS is incorrect as well since the prediction set sizes are monotone in т.
33


Reviews:
[{"review_id": "a59X5VkfaU-", "reviewer": "Reviewer_qXST", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths: \n\nI think the paper studies an interesting approach to a relevant problem. It is cleanly written, and the method is developed slowly and clearly, at least up to the final piece of estimating the $\\mathcal{W}$, but this final opacity is fine since this part largely uses established methods. In particular I think the idea of using the sample-wise bounds on $w_i$ to come up with worst-case type bounds is quite clever. The presented method shows meaningful gains over both prior proposals (WSCI), and the study is ablated well to illustrate the effects of each of the pieces of the main scheme.\n\nWeaknesses:\n\nTo me there are two main weaknesses:\n\n- Firstly, no real justification for the choice of $E = 0.01$ and $K = 10$ is presented. How were these numbers arrived at? Is it reasonable that such crude chunking of the data yields such regular marginals? For that matter, no contextualisation of these numbers is given either - how optimistic or not is assuming $E = 0.01$? Finally, sensitivity with respect to these hyperparameters is not discussed. I think understanding these aspects is critical to the practical usage of a method like this.\n\n- Secondly, I don't think the conclusion is as clear as is suggested by the \"mean-normalised-size-of-reliable-methods\" metric. This mean normalised size itself is not too meaningful as a metric to me (these are fairly different tasks with fairly different scales of difficulty as evinced by the mean sizes themselves). More importantly, I find it a much more natural statement to say that PS-R as a method makes sense when the shift is non-adversarial, and PS-M as a method that is slightly too optimistic, but otherwise effective. I think the paper undersells these a bit, needlessly, in favour of a bit too pessimistic a method, which at face value I only see as being relevant when no information about the shift is available. On the whole, I would prefer a more nuanced exposition of the experiments than the one given.\n\nBesides the above, I only have minor quibbles to do with clarity of notation:\n\n- The expression $U_{CP}(C_\\tau, S_m, V, w,b, \\delta_C)$ is hard to parse, especially since its actual definition as $U_{CP}( C_\\tau, T_N(S_m, V, w,b), \\delta_C)$ is hidden away in a statement. For instance, one thing I was missing because of this was that for each possible $w_\\tau,$ the set $T_N$ must be resampled. I think this notation should be clarified, perhaps by separating out the definition to draw enough attention to it.\n\n- The expression $s(y|x)$ is unfortunate since $y$ is already used for classes. Perhaps a different letter should be used here.", "summary_of_the_paper": "This paper is concerned with learning prediction sets (in a PAC sense) under the covariate shift assumption, given a model $f(x,y)$. The form of the sets is restricted to $C_\\tau(x) := \\{y : f(x,y) \\ge \\tau\\},$ and the problem is set up as learning a $\\tau$, using a  labelled source dataset $S_m \\sim P^{\\otimes n}$ and an unlabelled target dataset $T_n \\sim Q^{\\otimes n}$ such that with high probability over $S_m, T_n,$ $Q(Y \\in C_\\tau(X)) \\ge 1-\\varepsilon,$ where $\\varepsilon$ is a given target coverage level. It is desired that $\\tau$ is as large as possible to minimise the size of the prediction sets learned.\n\nThe main scheme is presented modularly. The paper first describes how finding the maximum $\\tau$ whilst ensuring that the number of points in $S_m$ it captures is large enough (as specified by using a Binomial tail inverse) gives valid sets when $Q = P$. Next, it is argued that when $Q$ is absolutely continuous with respect to $P$, and the derivative $w(x) = \\frac{\\mathrm{d}Q}{\\mathrm{d}P}(x)$ is upper bounded and known, then one can importance sample the set $S_m$ to generate a sample from $Q$, which can then plug into the previous procedure. This step fundamentally uses the covariate shift assumption, and, to my understanding, is folklore. The following, then, constitute the main technical contributions.\n\nNext, the assumption of exact knowledge of $w$ is relaxed, and it is argued that if instead for each $x_i \\in S_m,$ bounds $\\underline{w}_i \\le w(x_i) \\le \\overline{w}_i$ are available, then one can produce a worst-case estimate of the coverage of $C_\\tau$ for any $\\tau$ (by taking points that were missed to have high weights, and points covered to have low weights), and if this pessimistic coverage also satisfies the constraint. So, for each $\\tau$, the worst $w_\\tau$ can be produced, which can then feed into the importance sampling procedure above.\n\nThen, it is pointed out that such a confidence bound on the $w_i$s can be learned using a probabilistic classifier $s(\\cdot|x)$ to separate data from $S_m$ and $T_n$, which leads to the main proposed algorithm. While it is roughly justified in the appendix that an accurate estimate can be obtained under smoothness assumptions with an appropriately fine gridding of the space (and a consequently huge sample complexity), the concrete proposal is to replace this step with a heuristic method for fitting bounds on the weights, and then plugging these into the above strategy. Note that this is not implemented as a direct optimisation over $\\tau$ - instead a set $\\mathcal{T}$ of possible values is pre-selected, and the procedure is executed for each $\\tau$ (the algorithm recommends an increasing order on the same).\n\nFinally, the paper presents experiments in the DomainNet dataset, and in the ImageNet dataset, where the shift in the latter corresponds to adversarial perturbations. The principal baselines are the weighted split conformal inference (WSCI) method, which in my opinion is an appropriate choice, and the \"PS-C\" method, which simply uses a prediction set that has $1-\\varepsilon/b$ coverage on the source data, where $b$ is an estimated upper bound on $w$. The proposed method is ablatively presented, and it is seen that on just the DomainNet data, the method PS-R (which simply takes $(1-s)/s$ as an estimate of $w$) is both reliable and performs well, while the PS-M method, which further integrates samples in bins tends to be slightly optimistic on this dataset. Conversely, in the adversarially perturbed dataset, PS-R produces trivial prediction sets (since presumably this shift goes entirely outside the source domain's support), while PS-M performs well. The proposed method, PS-W, which further uses upper and lower bounds on $w$s after integrating them over bins, tends to be pessimistic (error-rates of $0.06-0.07$ are observed when only $0.1$ is demanded), but is not too much worse than either of these methods, and is effective in both types of shifts.", "summary_of_the_review": "I think this is a good paper, which makes an interesting methodological contribution to an increasingly relevant subfield. While it would benefit from better contextualisation of the hyperparameters of the method, and from a softer touch in interpreting experiments, I feel confident in recommending it for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Xdx2ty9ahFI", "reviewer": "Reviewer_ZLVy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n1.\tThe paper proposes a nice solution to a popular and important problem—uncertainty quantification for machine learning models in the presence of covariate shifts;\n2.\tThe proposed method and PAC theory are general to quantify uncertainty for any black-box machine learning models;\n3.\tThe datasets used to evaluate the algorithm are well connected with applications.\n4.\tThe paper is well organized and easy to follow.\n\nWeaknesses and Suggestions:\n\nAs shown in Algorithm 1, the random variable V is sampled once. The algorithm is essentially a randomized algorithm. If the upper bound for importance weight b is large, the acceptance rate in rejection sampling can be small, i.e., the random set $T_N$ in Equation (4) can be small. I concern this will lead to some instability issue of the algorithm. In Theorem 2, the high-confidence bound is marginal overall all possible V. This means that conditional on some value of V, the prediction sets given by the algorithm can possibly fail to achieve the target coverage rate. \n\nSection 3.3 needs to clarify the assumptions in Appendices. \n\n1. The proof of Theorem 5 in Appendix D.6 uses Equation (11) in Assumption 1. The authors need to explain how to construct a partition that satisfies the Assumption 1 on page 14. Like the authors said in Appendix B.2, In general, we need exponentially many bins to guarantee Assumption 1. I encourage the authors to add a formal proposition for the uncertainty set which states clearly the assumption needed to achieve the high-probability bound in Equation (6). It is okay if this assumption can only deal with by some heuristic approach. But it is important to explain what you did in practice, e.g., Why it is a good choice to estimate the lower and upper bound of the true IWs with $E=0.01$ and $K=10$ bins in Section 4.1?\n\n2. Appendix C.1 states that the uncertainty set defined below Equation (6) does not consider the fact that the expected importance weight is one; the optimization problem with additional constraint is challenging to solve exactly. The authors provide a good intuition of the greed algorithm using the monotonicity of $U_{RSCP}$. However, if the lower and upper bound of the true IWs are estimated, the constraint in Equation (10) is not the same as the constraint in Equation (7), so I don’t see why Theorem 4 holds by Equation (9) and using the same argument as the proof of Theorem 3. Also, in footnote 5, the authors mention “we assume b is given for simplicity, but our approach estimates it;” This also leads to some difficulty for moving from Theorem 3 to 4 as well. At the end of Appendix A, the authors mentioned “Compared to Candes et al. (2021), which only guarantees asymptotic validity under certain assumptions on the estimated IWs, Theorem 4 provides a significantly stronger finite-sample correctness guarantee (in addition to providing PAC-style guarantees).” However, I am concerned if Theorem 4 is only true if we can find a partition that achieves Assumption 1 and we know the true maximum importance weight $b$.\n\nIn experiments, the benchmark WSCI (Tibshirani et al., 2019) approximately achieves the target error rate $0.1$ and often have smaller prediction sets than PS-W (Figure 2). The experiments on real-world datasets are truly interesting. However, it may be better to compare WSCI and PS-W on a simpler synthetic dataset assuming the true importance weights are given.\n\n1. I wonder if your method based on PAC theory can provide smaller prediction intervals than the conformal prediction approach WSCI. Theoretically, could we have a comparison between WSCI and PS-W assuming the true importance weights are known?\n\n2. WSCI estimates the importance weights. Your method does rejection sampling using the importance weights, it would be great if the authors can add a discussion comparing both approaches. \n\n3. WSCI only assumes the weighted exchangeability of the data. Your method assumes the data are i.i.d, which is a stronger assumption and need to be mentioned clearly in the paper.\n\n", "summary_of_the_paper": "This paper proposes a new method to construct approximately correct (PAC) prediction sets for uncertainty quantification in the presence of covariate shift. It is a natural and interesting extension of the previous works [Park et al. 2020a, 2021] on PAC prediction sets. The building blocks this paper took from these previous works are the optimization problem in Equation (1) and the Clopper-Pearson confidence intervals for the Binomial distribution in Section 2.2. The extension is based on a rejection sampling Clopper-Pearson bound given in Section 3.2. \nThe authors propose an algorithm with and without access to the true important weights. The algorithm is evaluated in the settings of “rate shift” and “support shift” on the DomainNet and ImageNet datasets. The experiments show that the algorithm gives the smallest prediction sets among approaches that always satisfy the PAC constraint.\n", "summary_of_the_review": "The method proposed by the paper is interesting and new. However, I found some claims of the theories in the paper need to be clarified or made more formally. I hope the authors can address my concerns in their feedback.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "O-UqBycPHLS", "reviewer": "Reviewer_vZMq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Studying prediction sets under covariate shift in the PAC setting is a well-motivated problem given the ubiquitous presence of probabilistic classifiers in machine learning practice. Overall this work is well-written, and does a good job motivating and placing itself within the prior literature.\n\nOn the theoretical side, the work is incremental. It relies mostly on previous ideas from the literature in combination with classical techniques like rejection sampling. Further, the authors provide no theoretical guarantee on the optimality of the output set size. This is the main parameter of interesting the prediction set model, since it is easy to get standard PAC guarantees simply by outputting the entire label space. On the other hand, the authors do provide ample empirical evidence that their algorithm returns small prediction sets compared to other baseline models with similar accuracy guarantees.\n\nTypos: \"assume given\" (bottom of page 4/5).", "summary_of_the_paper": "Let $X$ be an instance space, $Y$ a set of labels, $D$ some underlying (hidden) distribution over $X \\times Y$. This work studies a new method for converting the output of a probabilistic predictor (e.g. a deep net) to a good prediction set: that is a mapping from $C: X \\to 2^Y$, such that for most samples $(x,y) \\sim D$, $C(x)$ contains $y$. Formally, the authors study this problem in the PAC setting with covariate shift. The learner is given access to the score function, a labeled sample from the source distribution $P$ over $X \\times Y$, and unlabeled samples from a target distribution $Q$ over $X \\times Y$ whose marginal over $X$ may be shifted from the source. The goal is to output a prediction set which is as small as possible while still retaining PAC guarantees with respect to the shifted target distribution. This is a well-motivated model in practice. Probabilistic outputs of modern neural nets can be difficult to interpret, and small prediction sets may be useful in settings where one wishes to avoid or check more carefully a few marked outputs (e.g. a problematic medical diagnosis).\n\nAssuming known, bounded importance weights, the authors provide an algorithm satisfying the PAC guarantee by maximizing a cutoff value for the score function that performs well over an empirical sample. They ensure their guarantee holds over the target rather than source distribution by rejection sampling to simulate the target distribution. The authors also extend this to settings where the importance weights are unknown but can be estimated from unlabeled samples. Finally, the authors provide experimental evidence over a couple common settings of covariate shift. They show that their algorithm outperforms baseline methods in the literature in the sense that it maintains PAC guarantees while outputting a smaller prediction set  in expectation.\n", "summary_of_the_review": "Overall, the submission is borderline. The proposed algorithm is mostly based on prior work and has few non-trivial theoretical guarantees, but it does perform well against other baselines in interesting practical settings such as rate shift.\n\n\nEDIT: I have read the author response and my review remains largely unchanged, though I would raise the score to 7 if this were possible within the ICLR format. Rejection sampling is a well-known strategy within the domain adaptation community for dealing with bounded covariate shift. The modification to approximate importance weights is more novel, but not of great theoretical interest since it is basically an immediate application of monotonicity. Finally, while the authors do provide a theoretical guarantee on the threshold cutoff parameter $\\tau$, this is only meaningful with respect to a very narrow set of algorithms (namely those w/ one fixed cutoff parameter that satisfy PAC-guarantees). There is no obvious way to actually connect this to a guarantee on the optimal prediction set sizes, even in the PAC setting (nor is this ever discussed). However, the empirical results do a good job of making up for these weaknesses, so I would give the paper a 7 if I could. Unfortunately ICLR does not give provide this option.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9WG8kYSO5dm", "reviewer": "Reviewer_vXNT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n1. Technical details/proofs have been adequately presented\n\nCritical Comments:\n1. It would be helpful to include reason why probabilistic classification models that can handle covariate shift not be used for PAC prediction sets. For eg. why not include labels with top-k posterior likelihoods to create the prediction set? etc. In the same spirit, it seems necessary to atleast empirically compare against such baselines.\n2. While robust variant in sec3.3 is ok, because the goal is to optimize (guard against) the worst-case scenario, one would expect that the variant would turn out to be more conservative/pessimistic. However, the simulations show that the size of predictions is small than it's non-robust (vanilla) counterpart. Am I missing something?\n3. Since the work is about PAC guarantees etc., it seems to be more efficient if the probabilities (uncertainties) in the confidence interval of the importance weights are taken into account and propagated through. However, currently the Confidence intervals are merely approximated as an interval. Can this be improved?\n4. Simulations seem to be a bit weak without comparison to top-k methods etc. \n\n\nMinor Comment:\n1. Near footnote 1, \"p(x,y) is pdf\" ... if y is dicrete like in classification, there is no such pdf.", "summary_of_the_paper": "The paper presents algorithms for PAC prediction sets under the assumption of covariate shift. Using estimated/known importance weights that encode the shift, the method optimizes for the smallest subset of labels such that with high probability the error of this prediction set is low. A rejection sampling based strategy is then shown to satisfy the PAC constraints. The methodology is extended to the case where the importance weights are uncertain (due to estimation error). It is shown that the robust variant can be solved using the extreme case weights and the rejection sampling based algorithm. Simulations show the efficacy of the method.", "summary_of_the_review": "While the work seems technically sound, there are some loose ends like those mentioned above. Empirical comparisons with some baselines also seem to be missing. So I recommend only a marginal accept in it's current state.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers were clear in their opinion that the paper deserves to be accepted. One reviewer also indicated a wish to increase the score from 6 to 7 but was not able to do that, so it isn't reflected in the final score. The reviewers appreciated the methodological contribution made by the paper.
Decision: Accept (Poster)