Test-time recalibration of conformal predictors under distribution shift based on unlabeled examples
Authors: Fatih Furkan Yilmaz
Reinhard Heckel
Venue: Submitted to ICLR 2023 (2023)
Keywords: classification
uncertainty estimation
conformal prediction

Abstract: Modern image classifiers achieve high predictive accuracy, but the predictions typically come without reliable uncertainty estimates. Conformal prediction algorithms provide uncertainty estimates by predicting a set of classes based on the probability estimates of the classifier (for example, the softmax scores). To provide such sets, conformal prediction algorithms often rely on estimating a cutoff threshold for the probability estimates, and this threshold is chosen based on a calibration set. Conformal prediction methods guarantee reliability only when the calibration set is from the same distribution as the test set. Therefore, the methods need to be recalibrated for new distributions. However, in practice, labeled data from new distributions is rarely available, making calibration infeasible. In this work, we consider the problem of predicting the cutoff threshold for a new distribution only based on unlabeled examples. While it is impossible in general to guarantee reliability when calibrating based on unlabeled examples, we show that our method provides excellent uncertainty estimates under natural distribution shifts.

Under review as a conference paper at ICLR 2023
TEST-TIME RECALIBRATION OF CONFORMAL PREDIC- TORS UNDER DISTRIBUTION SHIFT BASED ON UNLA- BELED EXAMPLES
Anonymous authors Paper under double-blind review
ABSTRACT
Modern image classifiers achieve high predictive accuracy. but the predictions typically come without reliable uncertainty estimates. Conformal prediction al- gorithms provide uncertainty estimates by predicting set of classes based on the probability estimates of the classifier (for example, the softmax scores). To provide such sets, conformal prediction algorithms often rely on estimating a cutoff threshold for the probability estimates, and this threshold is chosen based calibration set. Conformal prediction methods guarantee reliability only when the calibration set is from the same distribution methods need to be recalibrated for new distributions. However, in practice, labeled data from new distributions is rarely available, making calibration infeasible. In this work, we consider the problem of predicting the cutoff threshold for a new distribution based on unlabeled examples only. While it is impossible in general to guarantee reliability when calibrating based on unlabeled examples, we show that our method provides excellent uncertainty estimates under natural distribution shifts, and provably works for a specific model of distribution shift.
the test set. Therefore, the
INTRODUCTION
Consider (black-box) image classifier that is trained on a dataset to output probability estimates for I. classes given an input feature vector x E IRd. This classifier is typically a deep neural network with a softmax layer the end. Conformal prediction algorithms are wrapped around such a black-box classifier to generate a set of classes that contain the correct label with user-specified desired probability based on the output probability estimates.
Let E Rd be feature vector with associated label {1....,L}, L}. We say that set-valued function C generates valid prediction sets for the distribution
P(xa)~P [y E C(x)) 2 1
(1)
where 1 - a is the desired coverage level. Conformal prediction methods generate valid set generating
functions by utilizing a calibration set consisting of labeled examples [(x1, y1 .1),..., (X,; Dn)] drawn from the distribution P. An important caveat of conformal prediction methods is that they assume that the examples from the calibration set and the test set are exchangeable, i.e., samples are identically distributed, or more broadly, are invariant to permutations across the two sets.
The exchangeability assumption is difficult to satisfy and verify in applications and potentially limits the applicability of conformal prediction methods in practice. In fact, in practice one usually expects a distribution shift between the calibration set and the examples inference (or the test set), in which case the coverage guarantees provided by conformal prediction methods new CIFAR-IO1 10. and ImageNetV2 test sets were created the same way as the original CIFAR- 10 and ImageNet test sets, yet Recht et al. 2019 found notable drop in classification accuracy for all classifiers considered.
void. For example, the
Ideally, conformal predictor is recalibrated age guarantces are not valid (Cauchois et al., 2020). However, in real-world applications, while distribution shifts are ubiquitous, labeled data from new distributions is scarce non-existent.
distribution before testing, otherwise the cover-

---

Under review as a conference paper at ICLR 2023
We therefore consider the problem of recalibrating conformal predictor only based unlabeled data from the new domain. This is an ill-posed problem: it is in general impossible to calibrate a conformal predictor based on unlabeled data. Yet, propose simple calibration method that gives excellent performance for a variety of natural distribution shifts.
Organization and contributions. We start with concrete examples how conformal predictors yield miscalibrated uncertainty estimates under natural distribution shifts. We next propose a simple recalibration method that only uses unlabeled examples from the target distribution. We show that our method correctly recalibrates a popular conformal predictor (Sadinle et al. 2019) on a theoretical toy model. We provide empirical results for various natural distribution shifts of ImageNet showing that recalibrating conformal predictors using our proposed method significantly reduces the performance gap. In certain cases, it even achieves near oracle-level coverage.
Related work. Several works have considered robustness of conformal prediction to distribution shift. Tibshirani al. (2019) considers covariate shifts and proposes calibrating conformal predictors by estimating the amount of covariate shift from unlabeled target data. Similarly, Park et al. (2022) considers the problem of estimating the covariate shift from unlabeled target data, and aims at constructing PAC prediction sets instead of the standard unconditionally valid prediction sets. In contrast, we focus on complex image datasets for which covariate shift is not well defined. In Appendix
B we provide comparison of our method to the above covariate shift based methods for setting where we have access to labeled examples from multiple domains during mrining/allibratinn, one of which correspond the target distribution.
We are not aware of other works studying calibration of conformal predictors under distribution shift based on unlabeled examples. However, prior works propose to make conformal predictors robust to various distribution shifts from the source distribution of the calibration set (Cauchois et al., 2020 Gendler et al., 2022), via calibrating the conformal predictor achieve desired coverage in the worse case scenario of the considered distribution shifts. Cauchois et al. (2220) considers covariate shifts and calibrates the conformal predictor to achieve coverage for the worst-case distribution within the f f-divergence ball of the source distribution. Gendler et al. (2022) considers adversarial perturbations as distribution shifts and calibrates a conformal predictor to achieve coverage for the worst-case distribution obtained through f2-norm bounded adversarial noise.
While making the conformal predictor robust to a range of worst-case distributions at calibration time allows maintaining coverage worst-case distributions, this approaches has two shortcomings: 1. Natural distribution shifts are difficult to capture mathematically, and models like covariate-shifts or adversarial perturbations do not seem model natural distribution shifts (such that from ImageNet to ImageNetV2) accurately. 2. Calibrating for a worst-case scenario results in an overly conservative conformal predictor that tends yield much higher coverage than desired for test distributions that correspond to less severe shift from the source, which comes at the cost of reduced efficiency (i.e., larger set size, or larger confidence interval length).
In contrast, our method does not compromise the efficiency of the conformal predictor on easier distributions we recalibrate the conformal predictor separately for any new dataset.
A related problem is to predict the accuracy of a classifier on new distributions from unlabeled data
sampled from the new distribution (Deng & Zheng 202T Chen al. 2021 Tiang et al. 202T Deng
et al. 2021 Guillory et al. 2021 Garg et [0.2)) In particular, Garg et al. (2022 proposed
simple method that achieves state-of-the-an performance in predicting classifier accuracy across a
range of distributions. However, the calibration problem we consider is fundamentally different than estimating the accuracy of classifier. While predicting the accuracy of the classifier would allow making informed decisions on whether to use the classifier for new distribution, it doesn't 't provide solution to recalibrate.
CONFORMAL PREDICTION AND PROBLEM STATEMENT
We start by introducing conformal prediction and our problem setup.
Conformal prediction. Consider a black-box classifier with input feature vector x E Rd that outputs probability estimate xx(x) [0, 1] for each class = 1,..., L.. Typically, the classifier is
2

---

Under review as a conference paper at ICLR 2023
neural network trained some distribution, and the probability estimates the softmax outputs. We denote the order statistics of the probability estimates by (x)) 2 ((2) (x) _... 2 ((I)) (x).
Many conformal predictors are based on calibrating on calibration set D [x,, y/ 12 to find a cutoff threshold (Sadinle al., 2019; Romano et al. 2020 Angelopoulos et al.) (020) that
achieves the desired empirical coverage on this set. Here, the superscript P denotes the distribution from which the examples in the calibration set are sampled from. Specifically, conformal calibration computes the threshold parameter as
T" = inf (T : Ki : E C(x, Us T)H 2 (1 - an 1)}.
Here, C(x, u, T) is the set-valued function associated with the conformal predictor that outputs confidence set which is a subset of the classes {l....,L] L). and u, is added randomization to ensure the smoothness of the cardinality term, chosen independently and uniformly from the interval [o, 1]. See Vovk et al. 20055 on smoothed conformal predictors. Finally, the '+1' term in the (n + 1) term a bias correction for the finite size of the calibration set.
This conformal calibration procedure achieves distributional coverage as defined in the expression for any valued function C(x, u, 7) satisfying the nesting property, i.e., C(x, u, 71) C C(x, u, T2) for 7i < 72, see /Angelopoulos et al. 2020 Thm. 1).
In this paper, we primarily focus on the popular conformal predictors Thresholded Prediction Sets (TPS) (Sadinle et al.] (2019) and Adaptive Prediction Sets (APS) Romano et al. (2020). The set generating functions of the two conformal predictors are
CTPS (x, 7) = {e E (I,...;I.) 21
2 21-1)
(3)
and
CAPS(X (x, u,
lE f1, ..... L}: Σ (x) (()()))) S
(4)
with (O, 1) for smoothing. The set generating function of TPS doesn't 'tt require smoothing since each softmax score is independently thresholded and therefore there are no discrete jumps.
We emphasize that the threshold 7 depends on the distribution P and a labeled calibration set from P
is needed to compute the threshold through conformal calibration given in the expression 2) We
therefore add a superscript to the threshold to make clear which distribution was used to sample the
calibration set, for example 7P indicates that the calibration set was sampled from the distribution P.
The prediction set function CTPS for TPS and CAPS for APS both satisfy the nesting property. There-
fore, TPS/APS calibrated on a calibration set D by computing the threshold in the expression (2) is guaranteed to achieve coverage the distribution P. However, coverage is only guaranteed if the test distribution Q is the same as the calibration distribution P.
Coverage failures under distributions shifts. Often we're most interested in quantifying uncer- tainty with conformal predictions when we apply a classifier to new data that might come from a slightly different distribution than the distribution provide coverage guarantees for data coming from the same distribution as the calibration set, and the coverage guarantees often fail even under slight distribution shifts.
calibrated on. Yet, conformal predictors only
For example, APS calibrated to yield 1 - a = 0.9 coverage on the standard ImageNet-Val dataset only achieves coverage of 0.64 on the ImageNet-Sketee dataset, which consists of sketches of the ImageNet- Val images and hence constitutes distribution shift (Wang et al. 2019)).
Different conformal predictors typically have different coverage gaps under the same distribution shift. More efficient conformal predictors (i.e., those that produce smaller prediction sets) tend to have a larger coverage gap under distribution shift. For example, both TPS and RAPS (a generalization of APS proposed by Angelopoulos et al. (2020)) yield smaller confidence sets, but only achieve coverage of 0.38 vs. 0.64 for APS on the ImageNet-Sketee distribution shift discussed above.
Even under more subtle distribution shifts such subpopulation shifts (Santurkar et al. 2021) the
achieved coverage can drop significantly. For example, APS calibrated to yield 1 - a = 0.9 coverage
on the source distribution of the Living-17 17 BREEDS dataset only achieves coverage of 0.68 on the target distribution. The source and target distributions contain images of exclusively different breeds of animals while the animals' species is shared as the label (Santurkar al. 2021).
3

---

Under review as a conference paper at ICLR 2023
Step 1
Step 2
Step
å = 0.00743
0.90991
0.14
0.12871
emp coverago
0
0.95
0.12
0.1
0.9
0.1
[[ cel
[[KED afatttccll
0.9
0.95
[D0]
[PP]
Figure 1: Illustration of recalibration of conformal predictor with QTC: ImageNet- Val was used as the source distribution P and ImageNet-Shee Skeechh-SShhhhhtt as the target distribution @. Step 1: QTC is used the target to find the threshold q such that fraction of the target samples have a lower score than q as measured by [XXDR; <(((x))<q)
[D0
az
Step At test time, QTC estimates the value of [XED"; +
[DP]
Step 3: The estimate of 3 is used recalibrate the conformal predictor, yielding TQTe 0.99991.
Problem statement. Our goal is to recalibrate conformal predictor on new distribution Q based on only unlabeled data. Specifically, our goal to predict the threshold T as an estimate 7 for target distribution Q as well possible that the conformal predictor with the set function C(x, u, f2) achieves coverage close to the desired coverage Towards this goal, we only have access to an unlabeled dataset D uulabeled = fxi...., X,, sampled from the target distribution Q. We use Dunlabeled to denote unlabeled (label-stripped) dataset.
a on the new distribution Q.
In general, is impossible to guarantee coverage since conformal prediction relies on strict exchange- ability assumptions which not be controlled in practice for datasets (Vovk et al., [0055]
Romano et al. 2020 Angelopoulos et al., 2020 Cauchois et al.) 2020). However, we will see that we consistently estimate the threshold for variety of natural distribution shifts.
We refer to the difference between the target coverage - a and the actual coverage achieved on given distribution without any recalibration efforts as the coverage gap. We assess how effective recalibration method is based on the reduction of the coverage gap after recalibration under a variety of settings (e.g., choice conformal predictor, target level a) and distribution shifts.
METHODS
In this section we introduce our calibration method, that term Quantile Thresholded Confidence (QTC), along with baseline methods we consider our experiments.
3.1 QUANTILE THRESHOLDED CONFIDENCE
Consider conformal predictor calibrated on the source distribution P to yield coverage of 1 which yields the threshold 7.6 The conformal predictor guarantees coverage of a on the source distribution P, but different distribution Q the coverage off. But there is value 3 such that, we calibrate the conformal predictor on the source distribution using the value instead of a, it achieves 1 coverage on the target distribution, i.e., the corresponding thresholds obey 7 =
Our method estimates the value 3 based unlabeled examples. From this estimate 3, we compute the corresponding threshold 73 by calibrating the conformal predictor on the source calibration set
using 3. which yields threshold close to the desired one, i.e., 78 ~ -0.
4

---

Under review as a conference paper at ICLR 2023
We are given labeled source dataset P and an unlabeled target dataset D unlabeled Our estimate of 3 relies on the following quantile function
(D, inf p:
(0000))))) 2 20). XED
(5)
D
which depends on the scores of the classifier through score function s(T(()) max, (x), which we take as the largest softmax score of the classifier's prediction. Here, 'D is a set of unlabeled examples and с [0, 1] scalar. Our method first identifies threshold based on the unlabeled target dataset unlabeled for desired coverage level or in expression D
(5) by computing q(D unlabeled at). Since this process is identical to finding the (a)th quantile of the scores on the dataset, we dub the method Quantile Thresholded Confidence (QTC), QTC estimates 33 as
(Q
unlabeled) (DTrelDalabbleel
ID'P
(s(#(x))< anlaheeed .a)
(6)
XED
We the value Bqrc found in (6) to calibrate the conformal predictor the dataset D with the goal of achieving - a coverage on the target distribution Q. QTC is illustrated in Figure I
We also study two variants of QTC that find the threshold q the source dataset used for conformal calibration instead of the target as ablation methods: QTC-SC and QTC-ST, where SC stands for Source Coverage and ST for Source Threshold. Similarly QTC, QTC-SC aims to estimate the value 3. On the other hand, QTC-ST aims to directly estimate the threshold 7 by using the threshold 7" found by calibrating the conformal predictor the source as equation (2) QTC-SC and QTC-ST estimate 33 and 7 as
BQrc-sc(D) =
1 (olr())
D
XED
TQTC-ST(D)
Σ XED
(s(T()))
(8)
[D]
where D2
unlabeled is substituted for 'D in the above expressions for target distribution Q.
QTC is inspired by method for predicting the accuracy of a classifier from Garg et al. (2022). Garg al. 2022\'s method finds a threshold on the scores that matches the accuracy of a classifier on the dataset and predicts the accuracy on other datasets analogous to the expression (8). Contrary, we predict a threshold of conformal predictor, and our method is based on predicting the parameter instead of threshold directly.
3.2 BASELINE METHIODS
We consider several regression based methods as baselines. Regression-bard based methods have been used for predicting classification accuracy, assuming a correlation between the classification accuracy and a feature (e.g., average confidence) across different distributions (Deng et al., 2021 Deng & Zheng 202 Guillory et al. (02T). Those regression-bast a prediction on a new distribution Q based on the set of unlabeled examples D uulabeled The function fe is learned based synthetically generated distributions P1, P2.... and datasets D DPP.... ... sampled from those distributions. Such synthetic datasets can be produced by applying corruptions to the natural images of the source distribution, e.g., ImageNet-C (Hendrycks & Dietterich, 2019).
methods learn function Jo that makes
We expand the existing range of regression-basee -ased methods by considering a variety of setups for the feature space that extract different levels of detail from the classifier's statisties on the dataset. We use ob (D): R&_ - RRd to denote the feature extractor that maps the softmax scores of the classifier to the features for a given dataset D, A simple example is the one-dimensional feature (d 1) extracted by computing the average confidence of given classifier across the examples of a given dataset.
We fit regression function fe parameterized by the feature extractor o. by minimizing the mean squared error between the output and the calibrated threshold 5 across the distributions as
arg min ((fo((r())) P.).
(9)
We consider the following choices for the feature extractor Φz:
5

---

Under review as a conference paper at ICLR 2023
ImageNetV2
ImageNct Sketch
ImageNet-R
achieved coverage
0.88
0.85
0.877
0,00
0.44
0.04
0,50
54
0.54
0.54
0.38
0.34
30
Nox
cm
Dey
Qrc
oresse
one-sy-
ACR
C70
PCB
Grc
mrese
ome-3
Gmc
arese
Entity-13
Entity-30
1iivigg
achieved coverage
0.9
0.9
89
0
0
0.
70
0.77
TV
0.77
0.77
0.75
74
0.74
0,77
012
0.61
0.57
0.55
018
PER
erc
Qreae
arc.sy
CT2
DCR
PCR
cTC
Orcac
arcss
ACR
C3R
cm
arcac
Qressy
Figure Coverage obtained by TPS for a desired coverage
a 0.9 on the target distribution
Q after recalibration using the unlabeled samples from Q for various recalibration methods. The dotted line the coverage without recalibration, and the dashed line is the target coverage 1 - = 0.9. The figure shows that QTC and its variants almost fully close the coverage gap across ImageNet and BREEDS test distribution shifts, corresponding to varying severities.
Average confidence regression (ACR): The average confidence of the classifier across the entire dataset which is dx (D) D ΣxED max; (x).).
Difference of confidence regression (DCR) (Guillory al. 2021): The average confidence of the classifier across the entire dataset offset by the average confidence on the source dataset, which is Φ (D) [D) ExED max, me(x) |2D2| ΣxED" max, (x(x), where D'P
is the source dataset. Prediction is also for the offset target
We consider DCR addition to ACR, because DCR performs better for predicting the classifier accuracy (Guillory et al., 202I). Since the threshold т found by conformal calibration depends on the distribution of the confidences beyond the average, we propose the below techniques for extracting more detailed information from the dataset.
Confidence histogram-densinn regression (CHR): Variable dimensional (d = p) features
extracted as Φn (D) = {11b) ExED 1 maxx (=("))(p?" ;-;,..,(((....)) This corresponds to
the normalized histogram density of the classifier confidence across the dataset, where is a hyperparameter that determines the number of histogram bins in the probability range [0, 1J. Neural networks tend to be overconfident in their prediction which heavily skews the histogram densities to the last bin. We also therefore consider a variant of CHR, dubbed CHR-, where have {1,.... .I.....P 1} and hence d p 1, equivalent to dropping the last bin the histogram as a feature.
Predicted class-wise average confidence regression (PCR): Features with dimen-
sionality equal to the number of classes (d L) extracted (x
Exer (x)) (Lmarg max, Te(x]]
This corresponds to the average confidence of the classifier across the samples for each predicted class.
Exen (i-arx many ne(x))
j=(1...b)
EXPERIMENTAL RESULTS
For most experiments, we use ResNet-50 and DenseNet-122 121 21 as the backbone classifiers. We use the following choices for the source distribution P and associated natural distribution shifts:

---

Under review as a conference paper at ICLR 2023
ImageNet (Deng et al., 2009) distribution shifts: ImageNet is one of the most popular image classification datasets. In our ImageNet experiments, we take ImageNet as the source distribution P and we consider the following natural distribution shifts of ImageNet the target distribution Q:
ImageNetV2 (Recht et al. 2019) was constructed by following the same procedure as for constructing and labeling the original ImageNet dataset. However, all standard models perform significantly worse on ImageNetV2 relative to the original ImageNet testset.
ImageNet-Sketch (Wang et al. 2019) contains sketch-like images of the objects in the
original ImageNet, but otherwise matches the original categories and scales.
ImageNNe-R (Hendrycks et al. (022)) contains artwork images of the ImageNet class objects found in the web. ImageNet-R only contains images for 200-class subset of the original ImageNet. We don't 't limit our experiments to this subset but instead consider the adverse setting of calibrating on all 1000 classes since our main goal is to provide end-to-end solution for recalibration of the conformal predictors and we are interested in how well our method performs against possible adversaries such as dataset imbalance that can be encountered in practice.
For ImageNet and the above variations, we use fixed ResNet-50 and DenseNet-121 that were pretrained on the ImageNet training set.
BREEDS (Santurkar al. 2021) distribution shifts: The BREEDS datasets were constructed using the existing ImageNet images. but use different classes. BREEDS utilizes the hierarchical WordNet structure of the classes to choose parent class that makes the original ImageNet classes the leaves. For example, in the BREEDS Living-17 dataset, one of the classes is domestic cat. This is a parent class of several ImageNet classes, which are tiger cat, Egyptian cat, Persian cat and Siamese cat. BREEDS induces subpopulation shift from the source distribution to the target by assigning these leaf classes exclusively to either the source or target. For example, the images in the source dataset of Living-17 under the domestic cal class that of either tiger cafy Egyptian cats, whereas in the target are that of either Persian cals or Siamese cats. Therefore, despite having the same label (domestic caf), the source and target distributions semantically differ due to the differences between the breeds, which induces a subpopulation shift. We consider three BREEDS datasets: Entity- 13, Entity-30 and Living-17. 17, which are named using the convention theme/object type-Hclasses. Since we can't 't use ImageNet pre-trained models (even with finetuning, as all layers have been trained on all ImageNet classes already), we train a ResNet-18 18 model from scratch for the BREEDS datasets such that the classifiers only sees examples from the source distribution.
For all experiments, we first calibrate the conformal predictor on the source distribution to find the cutoff threshold 7P. For QTC and variants, we find the threshold using the expression 5)) For the regression methods, we use the ImageNet-C dataset (Hendrycks & Dietterich] 2019) as the source of synthetic distributions, find the cutoff threshold 7 for each of the distributions, and fit regressor by minimizing the loss (9). For the regression function we use a 4-layer MLP with ReLU activations. ImageNet-C consists of 90 different distributions obtained by synthetically perturbing the images of ImageNet- Val for 18 different types of perturbations at 5 different levels of severity, resulting in 90 distinct distributions.
Recalibration experiments for a fixed target coverage. We first evaluate the recalibration meth- ods for fixed target coverage of a 0.9. The results in Figure 2 for recalibrating TPS show that while regression methods can fall short on reducing the coverage gap, QTC is able to reduce the coverage gap significantly and even close in many cases. Often QTC works best, but for the distribution shifts of BREEDS, QTC-SC performs better. This can be attributed to the difference of the nature of shifts between ImageNet distributions and BREEDS distribution.
Recalibration experiments for different target coverage levels. The coverage gap (i.e., the dif- ference of achieved coverages and targeted coverage) varies across the desired coverage level - a. We there next evaluate the performance as function of the desired coverage level. Figure] 3 shows the coverage obtained after recalibration TPS and APS for different values of - a for the natural distribution shifts from ImageNet. Both QTC and QTC-SC close the coverage gap significantly for all choices of - a, whereas the best performing regression-baas based bascline method, CHR-, fails to consistently significantly improve the coverage gap across all choices of 1 a.
7

---

Under review as a conference paper at ICLR 2023
ImageNetV2
ImageNct-Sketae
ImageNet-R
achieved coverage
0.8
0.8
0.6
0.4
0.2
achieved coverage
0.8
ongirrll
QTC
0.8
QTC-SC
0.6
0.6
QTC-ST
4+ CTR-
0.7
0.8
0.9
0.8
0.9
0.8
0.9
desired coverage
desired coverage
desired coverage
Figure 3: Coverage obtained by TPS (top row) and APS (bottom row) the target distribution Q for various settings of (1 a²) after recalibration with the respective prediction method. For regression methods, only the best performing method of CHR- is shown. Both QTC and QTC-SC significantly close the coverage gap across the range of a, while CHR- yields inconsistent or insufficient performance improvements.
THEORETICAL RESULTS
We consider simple binary classification distribution shift model from Nagarajan et al. (2021); Garg et al.) (2022), and adapt the analysis from Garg et al. (2022) to show that recalibrating provably succeeds within this model. Specifically, we show that the conformal predictor TPS with QTC yields the desired coverage of a on the target distribution based on unlabeled examples.
We start by describing the distribution shift model from Garg et al. (202)) Consider binary classification problem with response y E {-1, 1} and with two features x [Kine, Tap] E IR, an invariant one and a spuriously correlated one. The source and target distributions P and Q over the feature vector and label are defined as follows. The label is uniform distributed over 1, 1}. The invariant cully-preeietive feature Finv is uniformly distributed in an interval determined by the constants e > y 2 0, with the interval being conditional on y::
17.7c if y= 1 -1
Pinv ~
(10)
if y -=1
The spurious feature Tap is correlated with the response y such that P(xy)> (Map y > 0] = p" where yd E (0.5, 1.0) for some joint distribution P. A distribution shift is modeled by simulating target data with different degrees of spurious correlation such that P P(x.))n [Mip y
where 8 E [0, 1). There distribution shift from source to target when pd # 2 Two example distributions P and Q are illustrated in Figure
consider a logistic regression classifier that predicts class probability estimates for the classes w
y -1 and y = as f(x) 1+ew"x> 1te"" where w = [Wine, Wap] E R2, Note that the classifier with Winv > 0 and Wap 0 minimizes the misclassification error across all choices of distributions P and Q (i.e., across all choices of p). However, a classifier learned by minimizing the empirical logistic loss via gradient descent depends on both the invariant feature Zinv and the apuriously-corellae feature Tap. ie.. Wap * 0 due to the geometric skews on the finite data and statistical skews of the optimization with finite gradient descent steps (Nagarajan al. 2021
8

---

Under review as a conference paper at ICLR 2023
Source
Target 2
yy= +1
-2
2
0
Finv
Zive
Figure 4: Example source and target distributions and Q for the binary classification model, and a classifier with Winv, Wap = 1. The decision boundary is shown with a faded dotted line. The correlation between the feature Tsp and the label is higher for the source than target (p" > po).
We consider the conformal predictor TPS (Sadinle et al. 2019) applied to this problem to generate
confidence sets. We extend the results of Garg et al. (2022) Theorem 3) and show that for logistic regression classifier described as above (i.c., Wjnv 0, Wap * 0), TPS recalibrated using QTC provably yields 1 a coverage on the target distribution:
Theorem (Informal). Consider the logistic regression classifier for the binary classification problem described above with Winy > O, Wap O, let n be the number of samples for the source and target datasets and a E (0,e) é) be user-defined value, where e is the error rate of the classifter on the source. The coverage achieved on the target by recalibrating TPS the source with the QTC estimate obtained in (6) by finding the QTC threshold on the target as in (5) converges to 1 as nL 00 with high probability.
First, we comment on the assumption on a. value of a that is larger than the error rate of the classifier would not make sense as it would result in empty confidence sets for portion of the examples in the dataset. This is because returning a confidence set consisting of the top prediction alone always achieves coverage of e by definition.
In order to understand the intuition behind Theorem D we first explain how the coverages is off under a distribution shift in this model. Consider a classifier that depends positively on the spurious feature (i.c., Wep > 0). When the spurious correlation is decreased from the source distribution to the target, the eπrо rate of the classifier increases. TPS calibrated on the source samples finds a threshold 7 such that the prediction sets yield a coverage on the source dataset as n - co. In other words, the fraction of misclassified points for which the model confidence is larger than the threshold is equal to a on the source. As the spurious correlation decreases and the error rate increases from source to target, the fraction of misclassified points for which the model confidence larger than the threshold т surpasses a, leading to a gap in targeted and actual coverage.
Now, we remark how QTC recalibrates and ensures the target coverage is meet. Note that there exists an unknown coverage - 3 that can be used to calibrate TPS on the source distribution such that it yields and therefore recalibration of the conformal predictor using QTC yields the desired coverage level of 1 a on the target.
a coverage on the target. Theorem I guarantees that QTC correctly estimates
CONCLUSION
We considered the problem of providing reliable uncertainty estimates for conformal prediction algorithms under distribution shifts based on unlabeled examples. We propose a simple test-time recalibration method dubbed Quantile Thresholded Confidence (QTC) that recalibrates conformal predictors based only on unlabeled examples. QTC provably succeeds on the distribution shift model from Nagarajan et al. (2021); 1): Garg et al. (2022). and most importantly reduces, even closes, the coverage gap (i.e., the difference of achieved coverage and desired coverage) of conformal predictors under distribution shifts for variety of natural distribution shifts.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. International Conference on Learning Representations (ICLR), 2020.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift. arXiv:2008.04280 04267 [cs, stat], 2020.
Mayee Chen, Karan Goel, and Nimit Sohoni. Mandoline: Model evaluation under distribution shift. International Conference on Machine Learning (ICML), 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? Conference on Computer Vision and Puttern Recognition (CVPR), 2021.
Weijian Deng, Stephen Gould, and Liang Zheng. What does rotation prediction tell about classifier accuracy under varying testing environments? International Conference on Machine Learning (ICML), 2021.
Saurabh Garg, Sivaraman Balakrishnan, and Zachary C Lipton. Leveraging unlabeled data predict out-o--distribution performance. International Conference on Learning Representations (ICLR), 2022.
Asaf Gendler, Tsui-Wei Weng. Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. International Conference on Learning Representations (ICLR), 2022.
Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Predicting with confidence on unseen distributions. IEEE International Conference on Computer Vision (ICCV), 2021.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. International Conference on Learning Representations (ICLR), 2019.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: A critical analysis of -iitt---ittiittionn generalization. IEEE International Conference on Computer Vision (ICCV), 2021.
Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and Zico Kolter. Assessing generalization of sgd via disagreement. arXiv:2106.13799 [cs, stat), 2021.
Jing Lei, Max G Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- Free Predictive Inference For Regression. 10Xxv:6604.0411 [math, stat], 2017.
Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure
modes of -fist---ditiibuttin generalization. International Conference Learning Representations (ICLR), 2021.
Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. Pac prediction sets under covariate shift. In International Conference on Learning Representations (ICLR), 2022.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi sourti- domain adaptation. In IEEE International Conference on Computer Vision (ICCV), 2019.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? International Conference on Machine Learning (ICML), 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems (NeurIPS), 2020.
10

---

Under review as a conference paper at ICLR 2023
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 2019.
Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. Breeds: Benchmarks for subpopulation shift. International Conference on Learning Representations (ICLR), 2021.
Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Vladimir Vovk, A. Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005.
Haohan Wang, Songwei Ge, Eric P Xing, and Zachary C Lipton. Learning robust global representa- tions by penalizing local predictive power. Advances in Neural Information Processing Systems (NeurIPS), 2019.

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM
In this section, we state and prove a formal version of Theorem Our results rely on adapting the proof idea of Garg al. (2022 Theorem 3) for predicting the classification accuracy of model to our conformal prediction setup.
Recall that consider distribution shift model for binary classification problem with an invariant predictive feature and a spuriously correlated feature, where distribution shift is induced by the spurious feature of the target distribution being more or less correlated with the label than the source distribution (Nagarajan et al. 2021 Garg et al. 2022).
We consider logistic regression classifier that outputs class probability estimates for the classes of y = -1 and y = +1 as
www x
f(x) = 1+ c + e
where [Wi' Wap] IR2, The classifier with Winy >> 0 and Wap minimizes the misclassi- fication error across all choices of distributions P and Q (i.e., across all choices of p). However, classifier learned by minimizing the empirical logistic loss via gradient descent depends on both the invariant feature Tinv and the metric skews on the finite data and statistical skews of the optimization with finite gradient descent steps NNagrajann et al. 2021).
feature Esp, ie., Wsp & 0 due to the geo-
In order to understand how geometric skews result in learning a classifier that depends on the spurious feature. suppose the probability that the spurious feature agrees with the label is high, i... p is close to 1.0. Note that finite-size training set drawn from this distribution, the fraction of samples for which the spurious feature disagrees with the label (i.e., Tsp * y) is small. Therefore, the margin the invariant feature for these samples alone can be significantly larger than the actual margin y of the underlying distribution. This implies that the max-margin classifier depends positively the spurious feature, i.e., Wsp > 0. Furthermore, we assume that Winy >> 0, which is required to obtain non-trivial performance (heating random guess).
Conformal prediction in the distribution shift model. We consider the conformal prediction method TPS (Sadinle al., 2019) applied the linear classifier described above. While other conformal prediction methods such as APS and RAPS also work for this model, the smoothing induced by the randomization of the model scores used those conformal predictors would introduce additional complexity to the analysis. TPS also tends to be more efficient in that it yields smaller confidence sets compared APS and RAPS at the same coverage level, see (Angelopoulos et al.. 2020 Table 9).
In the remaining part of this section, we establish Theorem [ which states that TPS recalibrated on the source calibration set with QTC achieves the desired coverage of 1 - on any target distribution that has a (potentially) different correlation probability for the spurious feature. We show this in two steps:
First, we show that the oracle TPS that achieves 1 a coverage on the target distribution achieves 1 - B coverage the source distribution. We then show that TPS calibrated to achieve 1 B empirical coverage on the source dataset achieves at least 1 a coverage on the target distribution,
Second, we provide a bound on the deviation of the QTC estimate from the true value of B. We show that in the infinite sample size case, the QTC estimate converges to the true value of B. Those two steps prove Theorem I
Recall that the calibration of TPS entails identifying cutoff threshold computed by the formula ( The set generating function of TPS for the linear classification problem described above simplifies to
CTPS (x, {e 1), fe(x) 2 1- 1)
(11)
where fo(x) and fi (x) are the first and second entry of f(x) defined above.
We are only interested in the regime where the desired coverage level 1 - a larger than the classifier's accuracy, equivalently < with being the emrrr rate of the classifier. This is because
12

---

Under review as a conference paper at ICLR 2023
trivial method that constructs confidence sets with equal length of 1 for all samples (i.e., singleton sets of only the predicted label) already achieves coverage
c.
QTC relies the fact that there exists unknown 3 E (0, 1) that can be used to calibrate TPS on the source distribution such that it yields 1 a coverage on the target. Here, we show that TPS calibrated to achieve 1 - 3 coverage the source calibration set Deal via computing the threshold 2 achieves a coverage on the target distribution Q as n - DC.
Step 1:
We utilize the following coverage guarantee of conformal predictors established by Vovk et al. (2005
Lei et al. (2017): Angelopoulos et al. (2020):
Lemma 1. Lei er al. 2017 Thm. 2.2). (Angelopoulos et al. 2020 Thm. 1, Prop. 1) Consider
Us). i I..... n drawn iid from some distribution P. C(x, T) be the conformal set generating
function that satisfies the nesting property in T, i.e, C(x, C C(X,T) if S.. Then, the conformal
predictor calibrated by finding r" 'hht achieves 1 - ar coverage on the finite set ((x,, y) y)}iz as in (2) satisfies the coverage over a sample (Xn+1, 1n+1) drawn from the same distribution P
Plyn+1 E ((xx+117") 2 ax
(12)
Furthermore, assume that the variables 8; = M(x inl(T T E E((x,,T) ( 1,.... are distinct almost surely. Then, the coverage achieved by the calibrated conformal predictor with the set generating function C(x, T) = {e E s( E) S J is also accurate, in that it satisfies
P Plan+1 C(xx+1; T"]] S a
(13)
n n+1
Both the lower bound (12) and the upper bound 13 of Lemma I apply to TPS in the context of the binary classification problem that we consider: To see this, we verify that TPS calibrated with the set generating function (II) satisfies both assumptions of Lemma [ First, note that TPS satisfies the nesting property, since we have CTPS r') S CTTS((x 7) for T S Next, note that for TPS we have s(x, y) = Fy (x). Further note that the linear logistic regression model we consider assigns distinet score each data point and since the invariant feature Tinv is uniformly distributed in continuous interval conditional on the variables 8, are distinct almost surely.
Next,
Now, consider the oracle TPS threshold 2 that achieves 1 coverage, or equivalently a miscover- age, on the target distribution, i.e.,
P(x,)~ [y $ CTPS(x. (x,+ : =
(14)
Next, note that y & CTPS(x, =8) if and only if arg max S3 (x) # y and (a fy (x) 2 T.O. To see that, note that the confidence set returned by TPS is a singleton containing only the top prediction of the model when the confidence of this prediction is higher than the threshold 7. Moreover, the confidence set returned by TPS for the binary classification problem above does not contain the true label only when the confidence set is the singleton set of the top prediction of the model and is different than the true label. Thus, equation
implics
P P arg max f (x) + y and max (E(D,1)
f3 (x) - = a. jE(0,1)
(15)
We define 3 as the miscoverage that the oracle TPS yields on the source distribution, i.e.,
8 = P ((xx)>PP arg max fy (x) # y and max jE(o,1)
(x) -
(16)
jEfo,1)
We have 3 A if there is a distribution shift from target to source.
Consider the threshold +3" found by calibrating TPS on the set DP to achieve empirical coverage of 1- B as in (2) TPS with the threshold t.P achieves coverage on the source distribution P as a result of Lemma Moreover, combining (2) with (13) at n + oo yields exact coverage of 1 - 3 on the source distribution P. Thus, we have
P ((x.))> arg max Jj (x) + y and max JJ (x) (0,1)
P 3
(17)
je (0.1)
Comparing equation 17 to the definition of /3 in equation (16) yields F 2 Therefore, follows
that TPS calibrated to achieve - B coverage on the source calibration set D as in 2 achieves exactly 1 a coverage on the target distribution Q as > xo.
13

---

Under review as a conference paper at ICLR 2023
In the second step, show that QTC correctly estimates the value of described above. This is formalized in the theorem below.
Step 2:
Theorem 2. Given the logistic regression classifier for the binary classification problem described above with any Winy 0, Wsp # O, assume that the threshold q for QTC is computed using dataset Dº consisting of n samples, sampled from some target distribution such that
Σ
1 (max;c10.1) 1,(x)<a) =t.
(18)
XEDO
Consider the oracle TPS conformal predictor with conformal threshold TO i.e., the predictor that achieves 1 - coverage the target distribution Q. Denote with 1 3 the coverage achieved on the source distribution P by this oracle TPS. Fix a 5 > O. The QTC estimate of the miscoverage B, denoted by
1
BQTC
Σ
[s(((())<<))
(19)
DD
XED
satisfies the following inequality with probability at least 1 8 over a randomly drawn set of examples D2
2 llo((16/))
13OTc 31 S
(20)
n Cup
where Cup = (1 (1- (1- (1- if Wapp > 0 and Cup p (pP)² otherwise.
Proof. We adapt the proof idea of Garg et al. (2022 Theorem 3), which pertains the problem of estimating the classification error of the classifier on the target, to estimating the source coverage of the oracle conformal predictor that achieves
a coverage on the target distribution.
For notational convenience, we define the event that a sample (x. y) is not in the prediction set of the oracle TPS with conformal threshold TO (i.e., y & CTPS (x, Ta as
Emc {y & CTPS (x, =
{arg max fy (x) # y and max fy (x) ]. JE(0,1)
JE(0,1)
The infinite sample size case (n + oo). In this part we show that as n + co, the QTC estimate Bqrc found as in (19) converges to the source miscoverage B to illustrate the proof idea. For oc, the QTC estimate Squc in 19 becomes
BQuc B(x,y)~P
(1ax) f(())9)
P(xx)~>
max fy (x) < jEf0,1}
P(x.u)~P [Eme]
(21)
3,
where the last equality is the definition as given in equation (6 The critical step equation which we establish in the remainder of this part of the proof.
21
First, we condition on the label y. Using the law of total probability, we get
P (xxy)>>
max fa (x) < = P Pp-P- [E((..1)
max f (x) P P(xx))~pyy =
[EE(0.))
P Px~Ply=+1
max fy (x) <9 jE(0.1)
P(xxy)>Plb = +1]
(i) 1
P
XxvPl Px~Ply=-1
max fj (x) < [Ef0.1
2
1
P PxxPlu=t1
max $3 (x) < (E(0.1)
2
18)
P PxwPly
f, (x) <
(22)
(E(0.1)
14

---

Under review as a conference paper at ICLR 2023
For equation (t), we used that y is uniformly distributed across {-1, 1}. and for equation (ti) that x is symmetrically distributed with respect to the label y. That is, we have Pinv
U --- -?1 and
P [Zsp -1] p if = -1 and Zinv Uly cl and P [xep +1] if y +1, so the two probabilities in (z) are equal.
We can further expand the expression for the probability Px~Ply [max)e((.1]] Si (x) < q] by addi- tionally conditioning on the spurious feature Zsp, which yields
max fi (x) < <0 [jE(O,1)
P(xy)/
P Zin 2n Ply.sn
S3 (x) <q] P Pxxxll (Tap y] [jE(0.1)
max
P PimmPlaapp
max fy (x) q PxxPly (Fap # z) JEf0,1}
(23)
In order to simplify the expression in the RHS of equation
23 x q if Tep y. Therefore, we have
consider the cases of Wap
and Wep < separately. If Wsp > 0, we have max fJ
P Snow~Ply.m y (0. fy (x) < q) = 0 if Wap and equation simplifies to
P P(xa)>D
max f, (x) < (E(0,1}
Fiav Pl
max f, (x) 9 JE(U,1}
Px-Ply Fep # yl
P PRinv #up
max
Jj (x) < 9
(1 (1-1²).
(24)
(E(0,1}
Similarly, if Wap < 0, we have max)e(0.1) fs (x) > q if Tapp # y. and equation 23
becomes
P ((x.)>/P max S3 (x) (E(0.1}
<9
P Plampy
max J; (x) (x) < 9 (E(0,1}
PxwPly (Tep = v)
P Plam
max (E(0,1)
(x) 9 pp.
(25)
We next follow the same steps that we carried out above for P ((x,))> [max,eç0.1] J3 (x) < s) to
rewrite the probability P(x.))>< [Eme]. If Wap >> O, the classifier makes no errors if Tsp = y and only misclassifies fraction of examples if Tup # Therefore, we have
P Px~P y [Eme]
P 2mm0 Kep [Eme] PxwPly (Tep + vl
P Ziav ~ tap [Emel (1 p²).
(26)
Similarly, for Wap 0, we have
P Px-P/ep by [Eme]
= P Sinw aap [mel PxmPly (Zep vl
P Zine P Wa Ky [Eme] p..
(27)
Therefore, in order to establish equation 21 it suffices to show
P Bige PPll Kap
max fj (x) < jE(0.1)
P Pin M Ply. [Emo]
for Wap > 0 and
(28)
P Rine / Ply.
max S, (x) <
P Penr [Eme]
for Wap < 0.
(29)
(E(O.1)
The feature Tinv is identically distributed conditioned on y, i.e., uniformly distributed in the same interval, regardless of the underlying source or target distributions P and Q. Therefore, equations (28) and (99 are equivalent to
P Binw 2l Hy
max J3 (x) < jE(0.1)
P Qlp.seppy [Eme],
for Wap >> 0 and
(30)
P Siny Oyp
max fy (x) (E(0.1)
P Pin Qly.t [Emo], for Wap < 0.
(31)
15

---

Under review as a conference paper at ICLR 2023
Equations (30 and (31 in turn follow from
P @
max fy (x) < - (x..)~0 [Eme] (e(0.1)
(32)
by earrying out the same steps that we carried out to expand the probabilities Px~Plu [Eme] and ((x.))> [Eme] starting from equation (32) to establish equations (28) and (2).. Equation (32) in turn
is a consequence of combining 15 with (88) at n + oc. This establishes equation (I)). as desired.
The finite sample case: We next show that the desired results approximately hold with high
probability over randomly drawn finite-sized set of examples D2_ We bound the difference between the LHS and RHS of (30) and (31) with high probability.
First, consider the case of Wap > O. Recall that for the case of Wssp > are interested in the regime where Wap # y. We denote the set of points in the target set D for which the spurious feature disagrees with the label as
XD = {i = 1,.., n Tap # (x,, V/) E DP),
and denote the set of points for which the spurious feature agrees with the label as
XA
.,.,, n Tap y/ (Xi, ye) E DP).
Note that the QTC threshold found on the entire set D2 as in (18) satisfies
1
1 (maxx)eto.,,(((0))e)) NEDD
Σ
(Emc(xx)))
(33)
ITD
|gD
NEND
which follows from noting that the classifier only makes an error on the subset XD if Wap > and therefore the only points for which the event &me is observed lie in the set Np Similarly, as established before in the infinite sample case, we have 1 1) (DKWM) inequality, for any q
= 0 for all E X
By the siferrky-Kieeee-ooffooiiiii probability at least 1 - 5/8
have with
log(16/5)
Σ iEND
1 fmox) f(()))a)) Ex Qlu.sspp (m.x (100)))))
$ V
2|
(34)
Plugging equation
33 into
34 we have with probability at least 1 - -8/8
1
log log(16/))
Exie Qu
(maxse (000
[mmec
S
(35)
XPD
2/X'pl
seAD
We next bound the second term in the LHS of equation inequality, we have with probability least 8/8
35 from its expectation. Using Hoeffding's
(66())
1 (Eme)
E Eaan ~ Qly. [1(mm))] S
(36)
|DD
2|XDl
tEXD
Combining equations (35) and (36) using the triange inequality and union bound, have with probability at least 1 0/4
2 (16(1))))
Exur Qup.a [ (mmxxscoon) ((0000) - Ex. (M <
(37)
X'p
Recall that the invariant feature Znn is uniformly distributed in the same interval con- ditioned on y regardless of the source or target distributions P and Q and that Pame lemely.s.ppp [maxyeço.1] J3 (x) > q] 2in ly (arg maxje(o.1) J3 (x) * v] 0 for the
16

---

Under review as a conference paper at ICLR 2023
case of Wsp > 0 as shown before. Therefore, by dividing both sides of (37 with 1/Px x Fes + vl we have with probability at least 8/4
1
2 2log(16/0)
I (xx))// [mmxxxeton [(())=)))))))))))))
B( [T [EEm))]]
S
Px Pl Tap # yl
[Dl
1log
p
|
(38)
For the case of Wap < O, can show an analogous result by noting that the above results can be shown on the set XA, where Zsp y. Specifically, noting that [A EiExa [maxxeronn) fx(x)s)))
ΣsExa (Eme) if Wap and following exactly the same steps from equation 33 onward
that lead to equation 38 we have with probability at least 1 - 8/4
2 logí 16/0)
E P (max)eto.)) [())) FX
[1 [Eme>>
S pp
(39)
[AA
Using Hoeffding's inequality can further bound the RHS of (38) and have with probability at least - 6/2
39
For the set Xp, we
log( (4g()
K n (1-p9)|
(40)
2n
and for the set XA. we have with probability least 1 - 5//2
log(4/6)
||aa| n n
(41)
2n
We next bound the difference between the finite sample QTC estimation the source from its expectation. By DKWM inequality, for any q > 0 we have with probability at least 1 - 8/4
Σ
1 [max to fx(x)<a) B(xx)~D [1 (max,eta.) 1(()
log (8/( (42)
S
IDP
2n
XED
We first show the result for the case Wap > O. Combining equations (38 and 42 using the triangle inequality and union bound, we have with probability at least 1-8 -8/2
(16//)6))
Σ 1 (max, (x())))))
B(x 1 (Emo))
$ 1- pp)
(43)
IDP cal
XEDF
Plugging in the definitions of BQre in (99 and | in 16 above, equivalently we get
1
log(16/0)
1 - 31 <
(44)
p
[t
which holds with probability least 8/2. Combining 44 with (40) proves equation (20 for Wap >> 0, as desired.
Similarly, for the case Wap following the same steps by first combining equation 39 with
we have with probability at least 1 5/2
1
2 llog(16/))
BQTC--
(45)
P
Combining 45 with 41 yields equation 20 as desired, for the case Wap 0, which concludes the proof.
17

---

Under review as a conference paper at ICLR 2023
p DemainNetAll
p DomainNetReal
original
achieved coverage
QIC
0.8
0.8
QTC-SC
QTC-ST
0.6
0.6
PS-W
+ WSCI
0.4
0.4
10a
avg: set size
102
10
10
10
10"
0.8
0.9
0.8
0.9
desired coverage a
desired coverage
Figure 5: Coverage (top row) and the average set size (bottom row) obtained by TPS on the target distribution DomainNet-Infograph for various settings of (x) after recalibration with QTC (ours) and covariate shift based methods of WSCI (Tibshirani et al.) (219)) and PS-W (Park et al.) 2022). We show the results for the setting where all domains (including the target) are available as the source (left) well for the setting where all domains available at training time but only the DomainNet-RRe
domain is available for the source at calibration time (right). For the setting of P = DellinNetAll, WSCI closes the coverage gap while QTC considerably improves whereas for the setting of P DomainNetReal, QTC slightly outperforms WSCI. In both settings, PS- W fails by constructing uninformatively large confidence sets for the range and QTC-ST fail to successfully recalibrate the conformal predictor.
0.9 and QTC-SC
B COMPARISON TO METHODS BASED ON ESTIMATING COVARIATE SHIFT
In this section, compare the performance of QTC methods that assume covariate shift distribution shift, and recalibrate by estimating the amount of covariate shift from unlabeled target data (Tibshirani al. 2019 Park al. 2022).
Covariate shift refers to the case where the conditional distribution of the label y given the feature vector x is fixed across the source and target distributions, but the marginal distribution of the feature vectors differ. Specifically, we have
source
(x, ~ P p x p(y|x) (x, Q = (x() p(y) xx)
target
where po (x) and (2(x) are the marginal PDFs the feature vector x, p(y(x) is the conditional PDF of the label y. and (x()) # (x).
In order to account for the covariate shift, the methods from (Tibshirani et al. 2019 Park et al. 2022) utilize an approach called weighted conformal calibration. In weighted conformal calibration, the likelihood ratio of the covariate distributions, i.e., w(x) (x() (x((x//ppp) (x),,, used to weigh the scores used for the set generating function of the conformal predictor for each sample (x, E DP
The weights wxx) are called the importance weights (IWs) and the conformal predictor calibrated on source calibration set with the true importance weights (if known) for given target distribution
18

---

Under review as a conference paper at ICLR 2023
is guaranteed to achieve the desired coverage the target, see Tibshirani et al. (2019 Cor. 1). In practice, the true IW's are not known and are therefore estimated heuristically.
In general, covariate shift is not well defined for complex tasks such image classification. We therefore follow the experimental setup of Park et al. (2022) and consider a backbone ResNet-101 classifier trained using unsupervised domain adaptation based on training sets sampled from both the source and target distribution. Furthermore, following Park et al. (2022), we train an auxillary classifier (discriminator) g that yields probability estimates of given input example being drawn from the source distribution or the target distribution. For the weighted split conformal inference (WSCI) method of TTbshiianii et al. (2019), we estimate the importance weights using this discriminator g. For the PAC prediction sets method of Park et al. (202)) based on rejection sampling (PS-W), we estimate the importance weights using histogram density estimation over the output probabilities of the discriminator g on the unlabeled examples of the source and target calibration sets. We use TPS as the conformal predictor for all of the considered methods. For details on the experimental setup for the covariate shift based methods, see Park et al. (2022) Sec. 4.1)
Note that QTC is significantly more versatile compared to the above covariate shift based methods in that QTC applies in the setting where labeled examples from the target distribution may not be available during training to train an auxillary tauretttareet discriminator, which is required to estimate the importance weights for the covariate shift based methods (Tibshirani et al.] 2019 Park et al. 2022).
In order to compare QTC to WSCI and PS-W following Park al. 2022), ) consider the Domain distribution shift problem (Peng et al, 2019). We first consider the original setup of Park et al. (2022). where the source distribution comprises of multiple domains and the target distribution corresponds to only specific domain out of these multiple domains. Specifically, the source distribution contains examples from all six domains of the DomainNet dataset, which are DomainNet-Skerr Clipart, DomainNer- Periitin DomainNet Comainnet-Qnnicddrav DomainNet-Red. and DomainNet Comainnet-Innooraaph In contrast, the target distribution contains examples from only the DomainNet- DomainNet-Infograpph domain. We focus on the Cetmainnet-Ifforraag for other choices of the target domains are considerably small or even negligible even without any recalibration (see Park et al. (2022) Table 1)). We also consider a more challenging scenario in which all domains are available at training time, but only a single domain (different than the target) is available for the source at calibration time. For this setting. inspired by the ImageNet distribution shift setups, we consider the DomainNet-PR Reall domain that features real images as the source and the DomainNet-Inforraph domain as the target.
DomainNer-
domain for the target distribution as the performance drop
We present our findings in Figure 5 The results show that when the source includes all the domains, WSCI outperforms other methods. However, when only DomainNet-Reen is available for the source at calibration time, QTC slightly outperforms WSCI. In both settings, PS-W fails if a is chosen such that a 0.9, by constructing uninformatively large confidence sets that tend to contain all possible labels. On the other hand, QTC and WSCI tend to construct similarly sized confidence sets consistently across the range of 1 a. Note that while QTC considerably closes the coverage gap in both setups, QTC-SC and QTC-ST fail to improve the coverage gap. We believe this might be due to the fact that ResNet-101 trained with domain adaptation tends to yield very high confidence across all examples. While a separate discriminator that uses the representations of the ResNet-100 101 before the fully-connected linear layer is utilized for the covariate shift based methods, this is not the case for QTC and its variants. Therefore, the threshold found by QTC-SC and QTC-ST tends to be very close or even equal to 1.0, hindering the performance.
C RAPS RECALIBRATION EXPERIMENTS
However, other conformal predictors (Sadinle) ct al., 2019; Angelopoulos et al., 2020) are more efficient (in that they have on average smaller confidence sets for a given desired coverage 1 a).
APS is a powerful yet simple conformal predictor.
In this section, we focus on the conformal predictor proposed by Angelopoulos et al. (020). dubbed Regularized Adaptive Prediction Sets (RAPS). RAPS is an extension of APS that is obtained by adding a regularizing term to the classifier's 's probability estimates of the higher-order predictions (i.e., subsequent predictions after the top-k predictions). RAPS is more efficient and tends to produce
19

---

Under review as a conference paper at ICLR 2023
ImageNetV2
ImageNet-Skene
ImageNet -
achieved coverage
0.9
0.8
0.8
original
0.6
0.6
0.8
+ QTC
QTT--K
QTC-ST
0.4
0.4
0.7
CHR-
0.8
0.9
0.8
0.9
0.8
0.9
desired coverage
-
desired coverage
desired coverage a
Figure 6: Coverage obtained by RAPS on the target distribution Q for various settings of (1 a)) w/ and w/o recalibration using QTC.
smaller confidence sets when calibrated the same calibration set as APS, it penalizes large sets. While TPS tends to achieve slightly better results in terms of efficiency compared to RAPS, see (Angelopoulos al. 2020 Table 9), RAPS coverage tends to be more uniform across different instances (in terms of difficult vs. easy instances) and therefore RAPS still carries practical relevance.
Recall that while efficiency can be improved by constructing confidence sets more aggressively, efficient models tend to be less robust, meaning the coverage gap is greater when there is distribution 0.9 coverage on ImageNet- Val and
shift at test time. For example, when calibrated to yield 1 tested on Image-Sketch, the coverage of RAPS drops to 0.38 in contrast to that of APS, which only drops to 0.64 (see Section 2). It is therefore of great interest to understand how QTC performs for recalibration of RAPS under distribution shift.
RAPS calibrated using exactly the same conformal calibration process as APS and only differs from APS in terms of the prediction set function C(x, u. u, The prediction set function for RAPS is defined as
CRAPS (x, U) lE (1. D}: Σ (x) 11 Al TT) (x) ST
(46)
regularization
where UO, 1), similar to APS and X, Kreg the hyperparametters of RAPS corresponding to the regularization amount and the number top non-penalized predictions respectively.
calibration set DPP be larger than one due to the added regularization. Therefore, in order to apply QTC-ST, we map 7' back to the [0, 1] range by dividing by the total scores after added regularization. QTC and QTC-SC do not require such additional step the coverage level a [0, by definition. We show the results of RAPS' performance under distribution shift with or without calibration by QTC in Figure 6 The results show that while QTC able completely mitigate the coverage gap, it significantly reduces it.
Note that the cutoff threshold 7? obtained by calibrating RAPS
Recall that RAPS utilizes a hyperparameter X, which is the added penalty the scores of the predictions following the top-kreg predictions, that can significantly change the cutoff threshold 7? when we calibrate on the calibration set Dd, The regularization amount À also implicitly controls the change in the cutoff threshold - - 7P| when the conformal predictor is calibrated on different distributions P and Q. That is, the value | 7?l increases with increasing as long as the distributions P and Q are meaningfully different, as is the case for all the distribution shifts that consider.
Therefore, good recalibration method should be relatively immune to the choice of X in order to successfully predict the threshold 7 based only on unlabeled examples. In Figure 7 we show the performance of RAPS under the ImageNetV2 distribution shift for various values of X. While QTC able to improve the coverage gap for various choices of X, the best performing regression based baseline method does not generalize well to natural distribution shifts when À is relatively large. In
20

---

Under review as a conference paper at ICLR 2023
À = 0.2
À = 0.5
À ==10 1.0
achieved coverage
0.9
0.9
0.9
0.8
0.8
0.8
oiginal
- QTC ST
0.7
0.7
0.7
0.8
0.9
0.8
0.9
0.8
0.9
1
desired coverage 1
desired coverage
desired coverage 1
Coverage obtained by RAPS on the target distribution Q (ImageNetV2) for kine 2 and various settings of À when the threshold replaced with the predicted threshold F with the respective prediction method. For regression methods, only the best performing method of CHR- is shown.
Figure 7:
ImageNetV2
ImageNet-Skent
ImageNet-R
achieved coverage
0.9
0.8
0.8
0.6
0.6
0.8
orgiial
UTC ST
0.4
0.7
CHR
0.8
0.9
0.8
0.9
0.8
0.9
1
desired coverage 1
desired coverage
desired coverage
Figure Coverage obtained by RAPS the target distribution Q for À 0.1 and various settings of (1 - ()) when the threshold 7 is replaced with the predicted threshold with the respective prediction method. For regression methods, only the best performing method of CHR- is shown.
contrast, as demonstrated in Figure 8 when the regularization amount is relatively small, the best performing regression-basse method of CHR- does very well in reducing the coverage gap of RAPS under various distribution shifts.
21


Reviews:
[{"review_id": "q57BxaNTIdz", "reviewer": "Reviewer_9GdY", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper considers the problem of domain shift at test time. They consider how to use the shifted unlabeled test data to recalibrate the cutoff threshold. The method is shown to be valid for some natural distribution shifts. Their method is mainly based on QTC in equation 6. Validity is also shown in binary classification in section 5. Empirical methods are based on image net and breeds.", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "Strength: this paper is clearly written. Most parts are easy to follow.\n\nWeakness: \n\n1. The method proposed is not intuitive, I really double whether this method will work on multiple class classification problems theoretically. From the expression of 6, it seems it only based on the maximal logic, and unlike TPS and APS, based on all logic explicitly. A theoretical study beyond 2 classes is appreciated.\n\n2. The experiments cannot justify a wide family of natural distribution shifts. More datasets should be discussed to show more comprehensive results.\n\nIn summary, the beauty of distribution-free uncertainty quantification is rigorous analysis and handy to use, but this paper missed these parts.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gaEvLTsFYY", "reviewer": "Reviewer_4zCm", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors propose a method for recalibrating a conformal predictor on a shifted data distribution with only unlabeled data. To this extent, they intend to estimate a confidence level beta that, if used for calibration on the original data distribution, would give empirical coverage 1 – alpha (the target coverage) on the target distribution. This is done using a unlabeled confidence-score.", "summary_of_the_review": "In its current form I am not fully convinced that this paper is ready for publication. There are several disconnects that are missing for me to fully understand the details and judge the method properly.", "strength_and_weaknesses": "Strengths:\n- Thorough introduction and problem statement and nice review of work on accuracy estimation with distribution shift and conformal prediction with distribution shift.\n- The authors tackle two important problems in my opinion: First, recalibration under distribution shift, second, calibration with unlabeled data.\n- Realistic experiments on ImageNet.\n- Theoretical analysis based on prior work that may give some indication why the method works.\n\nWeaknesses:\n- The paper is a bit notation heavy due to the strong reliance on thresholds, confidence levels and quantiles and I feel giving a bit more intuition on the calibration processes could help the reader.\n- Notation-wise, the opposite inequalities in (3) and (4) are confusing and I do not understand why 1 – alpha is used in (7). Generally, of course, there is some duality (e.g., replacing the 1 – tau with tau in equation (3) will correspond to calibrating against alpha instead of 1 – alpha), but it seems that this is not consistent across equations.\n- Figure 1 is aimed at illustrating the method, but it does not work well for me. First, the steps in the caption where confusing at first (are these text or part of the caption) and context for the confidence levels and thresholds is missing, i.e. the figure is on its own not helpful. Also, I am missing the connection to the calibration with TPS/APS with labels.\n- Some related work is missing in my opinion, e.g., online adaptive calibrators such as [a] that I feel are very similar.\n\n[a] https://arxiv.org/pdf/2106.00170.pdf\n\n- For the method, I think that I am missing an important point. The calibration on P is done with labels, correct? Meaning, we calibrate the threshold tau^P such that coverage 1 – alpha on P is obtained and the APS/TPS scores are used for that. However, there is no intuition or connection whatsoever between calibration of APS/TPS with labels and the unlabeled score s on P. For APS, the score is not even similar (while for TPS, s is just the maximum conformity score). This seems to be an integral part because calibrating against alpha on P using s might not mean anything for the actual TPS or APS scores. This is of course because the maximum confidence might not correspond with the true label.\n- I am also slightly confused by the QTC-ST baseline. For the conformity score being the maximum confidence, this works. But if my scores are logits, equation (5) does not seem to work since tau^P could be outside of [0, 1] while the confidence levels are in [0, 1]. For tau^P > 1, equation (5) should not work/be meaningful.\n- In section 3.2, it is also extremely difficult to follow why we are suddenly interested in regression baselines that predict accuracy. I expect that these are used to predict coverage from which beta is derived? The experiments section does, unfortunately not provide any more details.\n- I am also missing a clear statement that this approach does not provide any guarantee. Often, coverage is associated with a guarantee and I think this should be discussed and stated accordingly.\n- For the theoretical analysis, I would expect a proper statement in Theorem 1 beyond just saying “converges to 1 – alpha with high probability”. I feel without an exact statement, the toy example is not insightful. From the appendix, I deduce that this does not correspond to a standard coverage guarantee but, but a guarantee on that beta can be estimated reasonable close. However, only because beta is close, coverage does not need to be close, too. Or am I missing anything?", "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": {}}, {"review_id": "fgygDPcAtcJ", "reviewer": "Reviewer_gDoT", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors approach the recalibration of the prediction set in the conformal prediction procedure to overcome the distribution shift using only unlabeled data. Although this problem is intractable in general terms, it can be solved using the assumption about the family of shifts used. The authors propose a simple method Quantile Thresholded Confidence (QTC) which proposes to estimate the quantile on the target distribution on the desired level, after which a parameter beta is calculated to calibrate the predictor on the calibration data. To calculate threshold on source data, it is proposed either to search for parameter beta and estimate threshold from it, or to estimate threshold directly.", "summary_of_the_review": "The paper is well written and the results presented are interesting, but I have serious doubts on robustness of the method. No theoretical guarantees are given which is an important part of success for conformal prediction.", "strength_and_weaknesses": "Strengths:\n* The work is neatly written and easy to read.\n* The problem presented is relevant, which is confirmed by many examples of the lack of guarantees when the test distribution is shifted compared to the calibration set. \n* For the experimental study, authors use variations of ImageNet, which is a large and challenging dataset, which makes the obtained results rather strong.\n* The paper also presents a comparison with a number of baselines and an extensive theoretical study of the proposed method.\n\nWeaknesses:\n* While reading is easy the main idea of predicting the quantile is not explained enough. To the best of my understanding, you characterize datasets by some features and try to predict the quantiles with some predictor based on this features. It is not that easy to grasp from the paper. I recommend giving some example in the main body of the paper.\n* Are there any theoretical guarantees for the resulting method? Why do we expect it to work well?\n* While experimental results are promising, I am really curious how stable is the solution. It worked well on give example but what will predictor output for some very new data (with more significant shift for example).\n* The method is a direct adaptation of the analysis of Garg et al. 2022, so the contribution is limited.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WTtw2yojD4", "reviewer": "Reviewer_h3g1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "Conformal prediction methods guarantee validity only when the the calibration set comes from the same distribution as the test set. This paper aims to construct a more reliable conformal predictive set under distribution shift with unlabeled data. They consider predicting the cutoff threshold for a new distribution based on unlabeled data only. Experiments are conducted to demonstrate the performance of the proposed method in reducing the coverage gap.\n", "summary_of_the_review": "Though the paper proposes a simple method to obtain a predictive set under distribution shift, the experimental results are not very convincing. Moreover, the coverage is not guaranteed, which is a big issue.", "strength_and_weaknesses": "Strength:\nAppropriate experiments are conducted with some comparative methods.\n\nWeaknesses:\n-- The coverage is not exact. Actually, the proposed method is even not guaranteed to achieve the desired coverage probability asymptotically, which largely limits the contribution and novelty of this paper.\n\n-- I am curious about efficiency about the recalibration method. This paper does not provide enough analysis and experimental results about efficiency. Maybe the authors can provide some experiments to compare the size of the predictive sets of different methods (on synthetic or real data sets). Simultaneous analysis of validity and efficiency is more informative and meaningful.\n\n-- Comparisions in more datasets with conformal methods under distribution shift are recommended. The current version only provides comparison with some covariate-shift-based conformal methods in Appendix B. From the results (e.g., Figure 5), the performance of the proposed method is not convincing.\n\n-- It is not clear which one of the three recalibration methods we should use in practice. From experimental results, each one may fail to achieve the desired coverage on target data (the gap may be large). Can the authors provide more discussions and practical guidance?\n\n-- Why in Figures 7 and 8, are only results of QTC-ST provided? From other results, QTC-ST seems more likely to perform worse than the other two recalibration methods. Please provide all relevant results.\n\n-- The authors only provide some theoretical results under a toy example. For some other types of distribution shift such as covariate shift (unlabeled data seems sufficient), can the proposed method guarantee the coverage on the target data?\n\n-- What is the main difference between the proofs in this paper and that in Garg et al. (2022)? Please state clearly about the additional effort required in this work.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject