Uncertainty Sets for Image Classifiers using Conformal Prediction
Authors: Anastasios Nikolas Angelopoulos
Stephen Bates
Michael Jordan
Jitendra Malik
Venue: ICLR 2021 Spotlight (2021)
Keywords: classification
predictive uncertainty
conformal inference
computer vision
imagenet

Abstract: Convolutional image classifiers can achieve high predictive accuracy, but quantifying their uncertainty remains an unresolved challenge, hindering their deployment in consequential settings. Existing uncertainty quantification techniques, such as Platt scaling, attempt to calibrate the network’s probability estimates, but they do not have formal guarantees. We present an algorithm that modifies any classifier to output a predictive set containing the true label with a user-specified probability, such as 90%. The algorithm is simple and fast like Platt scaling, but provides a formal finite-sample coverage guarantee for every model and dataset. Our method modifies an existing conformal prediction algorithm to give more stable predictive sets by regularizing the small scores of unlikely classes after Platt scaling. In experiments on both Imagenet and Imagenet-V2 with ResNet-152 and other classifiers, our scheme outperforms existing approaches, achieving coverage with sets that are often factors of 5 to 10 smaller than a stand-alone Platt scaling baseline.

Published as a conference paper at ICLR 2021
UNCERTAINTY SETS FOR IMAGE CLASSIFIERS USING CONFORMAL PREDICTION
Anastasios N. Angelopoulos; Stephen J Malik, & Michael I. Jordan
Departments of Electrical Engineering and Computer Sciences and Statistics University of California, Berkeley {angelopoulos, stephenbates, ma ik, jordan]ecs (rrddan)essbberkeeee..... edu
ABSTRACT
Convolutional image classifiers can achieve high predictive accuracy, but quanti- fying their uncertainty remains an unresolved challenge, hindering their deploy- ment in consequential settings. Existing uncertainty quantification techniques. such as Platt scaling, attempt to calibrate the network's 's probability estimates, but they do not have formal guarantees. We present an algorithm that modifies any classifier to output predictive set containing the true label with user-specified probability, such as 90%. The algorithm simple and fast like Platt scaling, but provides formal finite-sample coverage guarantee for every model and dataset. Our method modifies an existing conformal prediction algorithm to give more sta- ble predictive sets by regularizing the small scores of unlikely classes after Platt scaling. In experiments on both Imagenet and Imagenet- V2 with ResNet-152 and other classifiers, scheme outperforms existing approaches, achieving coverage with sets that are often factors of 5 to 10 smaller than stand-alone Platt scaling baseline.
INTRODUCTION
Imagine you are doctor making a high-stakes medical decision based on diagnostic information from computer vision classifier. What would you want the classifier to output in order to make the best decision? This is not a casual hypothetical; such classifiers are already used in medical settings (e.g.. Razzak et al., 2018; Lundervold Lundervold, 2019; Li al., 2014). A maximum- likelihood diagnosis with an accompanying probability may not be the most essential piece of in- formation. To ensure the health of the patient, you must also rule in or rule out harmful diagnoses. In other words, even if the most likely diagnosis is stomach ache, it is equally more important to rule out stomach cancer. Therefore, you would want the classifier to give you-in addition to an estimate of the most likely nutcome-actionalie dictions that provably covers the true diagnosis with high probability (e.g.. 90%). This called prediction set (see Figure 1). Our paper describes method for constructing prediction sets from any pre-trained image classifier that are formally guaranteed to contain the true class with the de- sired probability, relatively small, and practical to implement. Our method modifies conformal predictor (Vovk et al., 2005) given in Romano et al. (2020) for the purpose of modern image classi- fication in order to make it more stable in the presence of noisy small probability estimates. Just as importantly, we provide extensive evaluations and code for conformal prediction in computer vision.
uncertainty quantification, such set of pre-
Formally, for a discrete response Y E y = (I...., uncertainty set function, C(X), mapping a feature vector to subset of {1..... K) such that
,,, K} and feature vector X EE Rd,, we desire an
P(Y E C(X)) 2 a,
(1)
for a pre-specified confidence level a such as 10%. Conformal predictors like our method can mod- ify any black-box classifier output predictive sets that rigorously guaranteed satisfy the desired coverage property shown in Eq. (I), For evaluations, we focus on Imagenet classification
'Equal contribution. Blog: bttps::/ppepp: http:/ppppppee.......eooop eecs. wtt.eeee....eeeeeeeeeeeeeeee
p conforaal classi fication

---

Published as a conference paper at ICLR 2021
fox squirrel 6.0
Zox 0.02
gEAY 9,00
Figure 1: Prediction set examples on Imagenet. We show three examples of the class fox squirrel and the 95% prediction sets generated by RAPS to illustrate how the size of the set changes as function of the difficulty of test-time image.
using convolutional neural networks (CNNs) as the base classifiers, since this is a particularly chal- lenging testbed. In this setting, X would be the image and Y would be the class label. Note that the guarantee in Eq. (1) is marginal over and Y-it holds on average, not for a particular image X.
A first approach toward this goal might be to assemble the set by including classes from highest to lowest probability (e.g., after Platt scaling and a softmax function; see Platt et al., 1999; Guo et al., 2017) until their sum just exceeds the threshold 1 a. We call this strategy naive and formulate it precisely in Algorithm 1. There are two problems with na ive: first, the probabilities output by CNNs are known to be incorrect (Nixon et al., 2019), the sets from naive do not achieve cov- erage. Second, image classificattin models' tail probabilities are often badly miscalibrated, leading to large sets that do not faithfully articulate the uncertainty of the model; see Section 2.3. Moreover, smaller sets that achieve the same coverage level can be generated with other methods.
be solved by picking a new threshold using holdout samples. For exam- ple, with a = 10%, if choosing sets that contain 93% estimated probability achieves 90% coverage on the holdout set, we use the 93% cutoff instead. We refer this algorithm, introduced in Ro- mano et al. (2020), as Adaptive Prediction Sets (APS). The APS procedure provides coverage but still produces large sets. To fix this, we introduce regularization technique that tempers the in- fluence of these noisy estimates, leading to smaller, more stable sets. We describe our proposed algorithm, Regularized Adaptive Prediction Sets (RAPS), Algorithms and 3 (with APS as a special case). As we will see in Section 2, both APS and RAPS are always guaranteed to satisfy Eq. reggrrgadsssss of model and dataset. Furthermore, we show that RAPS is guaranteed to have better performance than choosing fixed-size set. Both methods impose negligible computational requirements in both training and evaluation, and output useful estimates of the model's uncertainty on new image given, say, 1000 held-out examples.
The coverage problem
In Section we conduct the most extensive evaluation of conformal prediction in deep learning to date Imagenet and Imagenet- V2. We find that RAPS sets always have smaller average size than na vive and Ssets. For example, using a ResNeXt-101, na ve does not achieve coverage, while APS and RAPS achieve it almost exactly. However, APS sets have an average size of 19, while RAPS sets have an average size of 2 at = 10% (Figure 2 and Table 1). We will provide an accompanying codebase that implements our method as wrapper for any PyTorch classifier, along with code to exactly reproduce all of our experiments.
1.1 RELATED WORK
Reliably estimating predictive uncertainty for neural networks is an unsolved problem. Historically, the standard approach has been to train a Bayesian neural network to learn distribution over net- work weights (Quinonero-Cande Gal, 2016). This approach requires computational and algorithmic modifications; other approaches avoid these via ensembles (Lakshminarayane) et al., 2017; Jiang et al., 2018 8) or approximations of Bayesian inference (Riquelme et al., 2018; Sensoy et al., 2018). These methods also have major practical limitations; for example, ensembling requires training many copies of neural network ad- versarially. Therefore, the most widely used strategy is ad-hoc traditional calibration of the softmax scores with Platt scaling (Platt al., 1999; Guo et al., 2017; Nixon al., 2019).
et al., 2005; MacKay. 1992: Neal, 2012; Kuleshov et al., 2018;
This work develops a method for uncertainty quantification based on conformal prediction. Originat- ing in the online learning literature, conformal prediction is an approach for generating predictive sets that satisfy the coverage property in Eq. (1) (Vovk et al., 1999; 2005). We use a convenient data-splittig version known split conformal prediction that enables conformal prediction meth-

---

Published as a conference paper at ICLR 2021
empirical coverage
1.00
100
Naive
0.95
APS
80
RAPS
60
0.90
40
0.85
0
0.9
0.95
0.99
0.9
0.95
0.99
desired coverage (1-a)
desired coverage (1-a)
Figure 2: Coverage and average set size on Imagenet for prediction sets from three methods. All methods use ResNet-152 as the base classifier, and results are reported for 100 random splits of Imagenet- Vaaee, each of size 20K. See Section 3.1 for full details.
ods to be deployed for essentially any predictor (Papadopoulos et al., 2002; Lei et al., 2018). While mechanically very different from traditional calibration as discussed above, we will refer to approach as conformal calibration to highlight that the two methodologies have overlapping but different goals.
Conformal prediction is a general framework, not a specific algorithm important design decisions must be made to achieve the best performance for each context. To this end. Romano et al. (2020) and Cauchois et al. (2020) introduce techniques aimed at achieving coverage that similar across regions of feature space, whereas Vovk al. (2003); Hechtlinger al. (2018) and Guan & Tib- shirani (2019) introduce techniques aimed at achieving equal coverage for each class. While these methods have conceptual appeal, thus far there has been limited empirical evaluation of this general approach for state-of sate-offthhe-ar CNNs. Concretely, the only works that we are aware of that include some evaluation of conformal methods on ImageNet the gold standard for benchmarking com- puter vision methods are Hechtlinger et al. (2018), Park et al. (2019), Cauchois et al. (2020), and Messoudi et al. (2020), although in all four cases further experiments are needed to more fully eval- uate their operating characteristics for practical deployment. At the heart of conformal prediction the conformal score measure of similarity between labeled examples which is used com- pare new point to among those in hold out set. Our theoretical contribution can be summarized as a modification of the conformal score from Romano et al. (2020) to have smaller, more stable sets. Lastly, there prediction (Pearce et al., 2018; Zhang et al., 2018). These methods can be used as input to a con- formal procedure to potentially improve performance, but they do not have finite-sample coverage guarantees when used alone.
alternative approaches to returning prediction sets not based conformal
METHODS
In developing uncertainty methods to improve upon raive, we guided by three desiderata. First and most importantly, the coverage desideratum says the sets must provide a coverage, as discussed above. Secondly, the size desideratum says we sets of small size, since these convey more detailed information and may be more useful in practice. Lastly, the adaptiveness desidera- tum says we want the sets communicate instance- wise uncertainty: they should be smaller for easy time-iime& examples than for hard ones; see Figure 1 for an illustration. Coverage and size are obviously competing objectives, but size and adaptiveness are also often in tension. The size desideratum seeks small sets, while the adaptiveness desideratum seeks larger sets when the classi-
Algorithm Naive Prediction Sets
Input: sorted scores 8, associated permutation of classes 7, boolean rand
1: procedure NAIVE(a, s, 1, rond)
2:
1+1
3: while L
1= 8 < 1 a do
> Stop 1 - a probability exceeded
4:
L+L+1
5:
randd then
Break ties randomly (explained in Appendix B)
6:
U 10)
V + (EL -i= S; (1 - a))/sL
7:
8:
U < then
9:
++ 1-1
10:
return [T1...,, |n}
Output: The prediction set, {I,,..,II IL}

---

Published as a conference paper at ICLR 2021
100%
0.5
empirical coverage
1-d
penalized probabliig
Kreg
Tecal
75%
0.4
50%
penally
0.2
0.92
probabilty
25%
1.02
1.09
1.15
Ccaal
0.0
setsize parameter
class
(a) Conformal calibration
(b) RAPS prediction set
Figure 3: Visualizations of conformal calibration and RAPS sets. In the left panel, the y-axis shows the
11)(11a))//m a)n/n. In the right panel, the empirical coverage on the conformal calibration set, and 1 - a' = [(n+ +1++1)(1 1
printed numbers indicate the cumulative probability plus penalty mass. For the indicated value Fool, the RAPS prediction is {c, d, f, b).
fier is uncertain. For example, always predicting a set of size five could achieve coverage, but is not adaptive. As noted above, both AP Sand RAPS achieve correct coverage, and will show that RAPS improves upon APS according to the other two desiderata.
to the specifics of our proposed method. We begin in Subsection 2.1 by describing an abstract data-splitting procedure called conformal calibration that enables the near-automatic con- struction of valid predictive sets (that is, sets satisfying Eq. (I)). Subsequently, in Subsection 2.2, we provide a detailed presentation of our procedure, with commentary in Section 2.3. In Subsection 2.4 we discuss the optimality of our procedure, proving that is least as good the procedure that returns sets of a fixed size, unlike alternative approaches.
We
2.1 CONFORMAL CALIBRATION
We first review a general technique for producing valid prediction sets, following the articulation in Gupta al. (2019). Consider procedure that outputs a predictive set for each observation, and further suppose that this procedure has tuning parameter r that controls the size of the sets. (In RAPS, + is the cumulative sum of the sorted, penalized classifier scores.) We take small independent conformal calibration set of data, and then choose the tuning parameter such that the predictive sets are large enough to achieve 1 - a coverage on this set. See Figure for an illustration. This calibration step yields choice of and the resulting set is formally guaranteed to have coverage a on a future test point from the same distribution; see Theorem below.
Formally, let (X,, YK,,), be an independent and identically distributed (i.i.d)) of variables that was not used for model training. Further, let C(x, .) Rd [0, R - 2 be set- valued function that takes a feature vector x to a subset of the possible labels. The second argument is included to allow for randomized procedures; let U1, ...... Un be i.i.d. uniform [0, 1] random variables that will serve as the second argument for each data point. Suppose that the sets are indexed by such that they nested, meaning larger values of lead to larger sets:
C(x, u, TI) S C(x, u, T2) if T S T2.
(2)
To find a function that will achieve - a coverage on test data, we select the smallest 7 that gives least a coverage on the conformal calibration set, with a slight correction account for the finite sample size:
focal inf T Hi Y, C(X,, [nn + 1)(1 - a)]
(3)
n
n
The set function C(ε, u, 7) with this data-driven choice of 7 is guaranteed to have correct finite- sample coverage fresh test observation, stated formally next.
Theorem 1 (Conformal calibration coverage guarantee). Suppose (X,, Y,, U.)==..... and (Xx+1, Yn+1, Un41) are i.i.d. and let C(x, u, be set-valued function satisfying the nesting prop- erly in Eq. (2). Suppose further that the sets C(x, u, grow to include all labels for large enough T: for all x E Rdd, C(x,u, u, y for some T. Then for focal defined as Eq. (3), we have the following coverage guarantee:
P(Ynt1 C(Xxti, Unt1, Fecal) a.

---

Published as a conference paper at ICLR 2021
This is the same coverage property as Eq. (1) in the introduction, written in a more explicit manner. The result not new-u special case of this result leveraging sample-splittin first appears in the regression setting in Papadopoulos et al. (2002), and the core idea of conformal prediction was introduced even earlier; see (Vovk et al., 2005).
As a technical remark, the theorem also holds if the observations to satisfy the weaker condition of exchangeability; see Vovk et al. (2005). In addition, for most families of set-valued functions C(x, u. r) there is a matching upper bound:
P(Ya+1 E C(Xn+1,, feci)) S - a
n n+1
Roughly speaking, this will hold whenever the sets grow smoothly in See Lei et al. (2018) for formal statement of the required conditions.
2.2 OUR METHOD
Conformal calibration is powerful general idea, allowing one to achieve the coverage desideratum for any choice of sets Czz, u, T). Nonetheless, this is not yet a full solution, since the quality of the resulting prediction sets can vary dramatically depending on the design of Car, u, 7). In particular, recall the size and adaptiveness desiderata from Section 1-we want uncertainty sets to be as small as possible while faithfully articulating the mnstance-wise uncertainty of each test point. In this section, we explicitly give algorithm, which can be viewed special case of conformal calibration with the uncertainty sets C designed to extract information from CNNs.
Our algorithm has three main ingredients. First, for feature vector I. the base model computes class probabilities A₂ E RR and we order the classes from most probable to least probable. Then, add regularization term promote small predictive sets. Finally, we conformally calibrate the penalized prediction sets to guarantee coverage on future test points.
Formally, let Par (v) = -y==1 #z [ ( be the total probability mass of the set of labels that are more likely than y. These are all the labels that will be included before is included. In addition, let (v) = Hi' E E'= (v/) 2 [y)}] be the ranking of y among the label based on the probabilities म. For example, if is the third most likely label, then (3) = 3. We take
C* C²(x,,, == {u px(x) (v) + X (ox - k sT}
(4)
regularization
where (2)+ denotes the positive part of and kieg 2 are regularization hyperparameters that are introduced to encourage small set sizes. See Figure 3 for a visualization of RAPS predictive set and Appendix E for a discussion of how to select kreg and X.
Since this is the heart of our proposal, we carefully parse each term. First, the Par Py) term increases as y ranges from the most probable to least probable label, so our sets will prefer include the y that are predicted to be the most probable. The second term, (v) u. is randomized term to handle the fact that the value will jump discretely with the inclusion each new y. The randomization term never impact more than but y & C(x, 1, T). These first two terms can be viewed as the CDF transform after arranging the classes from most likely to least likely, randomized in the usual way result in continuous uniform random variable (ef. Romano et al., 2020). We discuss randomization further in Appendix B.
value of y: there is at most value of y such that y E C(x, 0. r)
Lastly, the regularization promotes small set sizes: for values of y that occur farther down the ordered list of classes, the term A (o, it is included in the predictive set. For example, if kreg 5, then the sixth most likely value of y has an extra penalty of size X, so it will never be included until 7 exceeds Ps pz(y) + f (v) u + X. whereas it enters when exceeds Px + (3)
+ makes that value of y require a higher value r before
the nonregularized version. Our method has
the following coverage property:
Proposition 1 (RAPS coverage guarantee). Suppose (Xi, Ys, Ut)i=I..... and (X,-1, Ynt1, Un+1) are i.i.d. and let C* (z, u. T) be defined as in Eq. (4). Suppose further that oz > 0 for all x and y. Then for Faoll defined as in Eq. (3), we have the following coverage guarantee:
1 S P (Yn41 E CX"(Xx+,, fcmi)) 51
n n+1
For ease of notation, assume distinct prohabilities. Else, lahel-ordering ties should be broken randomly.

---

Published as conference paper at ICLR 2021
Algorithm 2 RAPS Conformal Calibration
Input: E [0,1]=*
{L,... K)"*,, and one-hot y {0, 1 corresponding respectively to the sorted scores, the associated permutation indexes, and labels for each of n examples in the calibration set; Krey: X; boolean rand
1: procedure RAPSC(a,s,...j.)))
2: for i E (1...... , do
3:
L + 1 115= V/s
4:
E, < 2 A(Li Kreg + 1)+
5:
if rand then
6:
1n) t Ej St, + U si,14
7:
8: Focal f- the [(1 a1 + n.] largest value {E
9: return Fooat
Output: The generalized quantile, Fecul
The value in Eq. (3)
Algorithm RAPS Prediction Sets
Input: a, sorted scores and the associated permutation of classes I for test-time example, fecal
from Algorithm& 2, kireg- X, boolean rand
1: procedure RAPS(a,
Fecal, Kreeg X, rand)
2:
L L+ E E 0 + A(L - kreg)
S Focal ++1
3: V (traal - rL-1 8, A(L- - kregg
+ + 81. ) 881-1
=0
4: if rand & V < < (ni 1) then
5:
1 6: return {
The most likely classes
Output: The confidence set,
>> The set in Eq. (4)
Note that the first inequality is a corollary of Theorem 1, and the second incquality is special case of the remark in Section 2.1. The restriction that n (y) > is not necessary for the first inequality.
2.3 WHY REGULARIZE?
In our experiments, the sets from APS are larger than necessary, because APS sensitive to the noisy probability estimates far down the list of classes. This noise leads to permutation problem of unlikely classes, where ordering of the classes with small probability estimates determined mostly by random chance. If 5% of the true classes from the calibration set are deep in the tail due to the permutation problem, APS will choose large 95% predictive sets; see Figure 2. The inclusion the RAPS regularization causes the algorithm avoid using the unreliable probabilities in the tail; see Figure 4. We discuss how RAPS improves the adaptiveness of APS S in Section 4 and Appendix E.
2.4 OPTIMALITY CONSIDERATIONS
To complement these experimental results, we now formally prove that RAPS with the correct reg- ularization parameters will always dominate the simple procedure that returns fixed set size. (Sec- tion 3.5 shows the parameters are easy to select and RAPS is not sensitive to their values). For a feature vector x, let (t))() be the label with the jth highest predicted probability. We define the top-k predictive sets to be (í(a) (x)...., (1))
Proposition 2 (RAPS dominates top-k sets). Suppose (X,, Yi, U&)i=i..... and (Xn-1; Yuti, Un+1) are i.i.d. draws. Let k- be the smallest lo such that the top-k predictive sets have coverage at least [(n + 1)(1 (311-))//n on the conformal calibration points (Xa, Yi)==...... Take C* (x, u, T) as in Eq. (4) with any kreg I k² and X 1. Then with focll chosen as in Eq. (3), we have
C* (*xxx+1 Un+1, F C ( ((.))()))
In words, the RAPS procedure with heavy regularization will be at least as good as the top-k proce- dure in the sense that it has smaller same average set size while maintaining the desired coverage level. This is not true of either the naive baseline or the APS procedure; Table 2 shows that these two procedures usually return predictive with size much larger than As.
3 EXPERIMENTS

---

Published as a conference paper at ICLR 2021
Accuracy
Coverage
Size
Model
Top-1
Top-5
Top K
Naive
APS
RAPS
Top K
Naive
APS
RAPS
ResNeXt101
0.793
0.945
0.900
0.889
0.900
0.900
2.42
17.1
19.7
2.00
ResNet152
0.783
0.94
0,900
0.895
0.900
0.900
2.63
9.78
10.4
2.11
ResNet101
0.774
0.936
0,900
0.896
0.900
0.900
2.83
10.3
10.7
2.25
ResNet50
0.761
0.929
0.900
0.8%6
0.900
0.900
3.14
11.8
12.3
2.57
8
0.698
0.891
0.900
0.895
0.900
0.900
5.72
15.5
16.2
4.43
16nseNet161
0.771
0.936
0,900
0.894
0.900
0.900
2.84
11.2
12.1
2.29
VGG16
0.716
0.904
0,900
0.895
0.901
0.900
4.75
13.4
14.1
3,54
Inception
0.695
0.887
0,900
0.885
0.900
0.901
6.30
75.4
89.1
5.32
ShuffleNet 0.694
0.883
0,900
0.891
0.900
0.900
6.46
28.9
31.9
5.05
Table Results on Imagenet- Val. We report coverage and size the optimal, randomized fixed sets, naive, APS, and RAPS S sets for nine different Imagenet classifiers. The median of-means for each column is reported over 100 different trials. See Section 3.1 for full details.
In this section we report on experiments that study the performance of the predictive sets from naive, APS, and RAPS, evaluating each based on the three desiderata above. We begin with a brief preview of the experiments. In Experiment 1, we evaluate naive, APS, and RAPS on Imagenet- Val. Both APS and RAPS S provided almost exact coverage, while naive sets had coverage slightly below the specified level. APS has larger sets on average than naive and RAPS. RAPS has much smaller average set size than APS and na i ve. In Experiment 2, we repeat Experiment on Imagenet- V2, and the conclusions still hold. Experiment 3, we produce histograms of set sizes for nai ve, APS, and RAPS for several different values of X. illustrating simple tradeoff between set size and adaptiveness. In Experiment 4, we compute histograms of RAPS sets stratified by image difficulty, showing that RAPS sets smaller for casier images than for difficult ones. In Experiment 5, we report the performance of RAPS with many values of the tuning parameters.
In our experiments, repository (Paszke et al., 2019) with standard normalization, resize, and crop parameters. Before applying ivv, APS, RAPS, calibrated the classifiers using the standard temperature seal- ing/Platt scaling procedure as in Guo et al. (2017) on the calibration set. Thereafter, na ive, APS, and RAPS were applied, with RAPS using data-driven choice of parameters described in Ap- pendix E. We use the randomized versions of these algorithms-aae see Appendix B for discussion.
nine standard, pretrained Imagenet classifiers from the torchvision
3.1 EXPERIMENT 1: COVERAGE VS SET SIZE ON IMAGENET
In this experiment, we calculated the coverage and mean set size of each procedure for two different choices of a. Over 100 trials, randomly sampled two subsets of Imagenet- Val: one conformal calibration subset of size 20K and one evaluation subset of size 20K. The median-of- trials for both coverage and set size are reported in Table Figure illustrates the performances of naive, APS, and RAPS; RAPS has much smaller sets than both nai haive ive and APS, while achieving coverage. We also report results from a conformalized fixed-k procedure, which finds the smallest fixed set size achieving coverage on the holdout set, k", then predicts sets of size k* - 1 or k on new examples order to achieve exact coverage; see Algorithm 4 in Appendix
over
3.2 EXPERIMENT 2: COVERAGE VS SET SIZE ON IMAGENET-V? V2
The same procedure as Experiment was repeated on Imagenet- V2, with exactly the same normal- ization, resize, and crop parameters. The size of the calibration and evaluation sets was 5K, since Imagenet-V2 is a smaller dataset. The result shows that our method can still provide coverage even for models trained on different distributions, as long as the conformal calibration set comes from the new distribution. The variance of the coverage is higher due to having less data.
3.3
EXPERIMENT 3: SET SIZES OF NAIVE, APS, AND RAPS ON IMAGENET
We investigate the effect of regularization in more detail. For three values X, we collected the set sizes produced by each of naive, APS, and RAPS and report their histograms in Figure 4.
3.4
EXPERIMENT 4: ADAPTIVENESS OF RAPS ON IMAGENET
We now show that RAPS sets are smaller for easy images than hard ones, addressing the adaptiveness desideratum. Table 4 reports the size-stratified coverages of RAPS S at the 90% level with kreg = and different choices of X. When À is small, RAPS allows sets to be large. But when À 1, RAPS

---

Published as a conference paper at ICLR 2021
Accuracy
Coverage
Size
Model
Top-1
Top-5
Top K
Naive
APS
RAPS
Top K
Naive
APS
RAPS
ResNeXt101
0.678
0,874
0.900
0.888
0.899
0.899
7.48
43.0
50.8
6.18
ResNct152
0.67
0.876
0.899
0,896
0.900
0.900
7.18
25.8
27.2
5.69
ResNet101
0.657
0.859
0.901
0.894
0,900
0.898
9.21
28.7
30.7
6.93
ResNet50
0.634
0.847
0.898
0.894
0.899
0.900
10.3
30.3
32.3
7.80
ResNet18
0.572
0.802
0.902
0.895
0,900
0,900
17.5
35.3
37.4
13.3
DenseNet161
0.653
0.862
0.902
0.895
0.901
0.901
8.6
29.9
32.4
6.93
VGG16
0.588
0.817
0.902
0.897
0,900
0.899
15.1
31.9
32.8
11.2
Inception
0.573
0.797
0.900
0.893
0.900
0.899
21.8
145.0
155.0
20.5
ShuffleNet 0.559
0.781
0.899
0.892
0.900
0.899
26.0
66.2
71.7
22.5
Table Results on Imagenet-V2, We report coverage and size of the optimal, randomized fixed sets, naive, AP S, and RAPS sets for nine different Imagenet classifiers. The median of-means for each column is reported over 100 different trials at the 10% level. See Section 3.2 for full details.
frequency
10
A-0.01
10-1
A-0.1
10-2
A=1
method
10
10-2
10-2
Naive
10-3
10-1
10-3
APS
25
50
75
100
0
25
50
75
100
25
50
75
100
size
size
Figure 4: Set sizes produced with ResNet-152. See Section 3.3 for details.
clips sets to be maximum of size 5. Table 7 (in the Appendix) stratifies by image difficulty, showing that RAPS sets are small for easy examples and large for hard ones. Experiments 3 and 4 together illustrate the tradeoff between adaptiveness and size: the average set size decreases, the RAPS procedure truncates sets larger than the smallest fixed set that provides coverage, taming the heavy tail of the APS procedure. Since RAPS with large undercovers hard examples. must compensate by taking larger sets for easy examples to ensure the - a marginal coverage guarantee. However, the size only increases slightly since easy images are more common than hard ones, and the total probability mass can often exceed fecal by including only one more class. If this behavior is not desired, we can instead automatically pick À to optimize the adaptiveness of RAPS; see Section 4.
3.5 EXPERIMENT 5: CHOICE OF TUNING PARAMETERS
While any value of the tuning parameters À and kreg lead to coverage (Proposition 1), some values will lead to smaller sets. In Experiments I and 2. we chose kreg and À adaptively from data (see Appendix E), achieving strong results for models and choices of the coverage level. Table 3 gives the performance of RAPS with many choices of kireg and À for ResNet-152.
4 ADAPTIVENESS AND CONDITIONAL COVERAGE
In this section, point definition of adaptiveness that is more natural for the image classifi- cation setting than the existing notion of conditional coverage. We show that APS does not satisfy conditional coverage, and that RAPS with small \ outperforms it in terms of adaptiveness.
We say that a set-valued predictor C Rd + 2 satisfies exact conditional coverage if P(Y E a for each æ. Distribution-fre guarantees on conditional coverage are im-
C(X) X = x) possible (Vovk, 2012; Lei & Wasserman, 2014), but many algorithms try to satisfy it approximately (Romano al., 2019; 2020; Cauchois et al., 2020). similar spirit, Tibshirani al. (2019) sug- gest notion of local conditional coverage, where one asks for coverage in neighhorhood of each point, weighted according to a chosen kernel. Cauchois et al. (2020) introduce the worst-case slab metric for measuring violations of the conditional coverage property. We present different way of measuring violations conditional coverage.
Proposition 3. Suppose P(Y E C(X) x= x) =1 1 - O for each x E Rdd Then, P(Y E c(X) (IC(X) E A)) = 1 for any A 10,
In words, if conditional coverage holds, then coverage holds after stratifying by set size. Based on this result, In Appendix E, we introduce the size-stratified coverage violation criterion, a simple and pragmatic way of quantifying adaptiveness. Then, we automatically tune on this metric RAPS S markedly outperforms the adaptiveness of APS (see Table 8).

---

Published as a conference paper at ICLR 2021
KreglA A
0
le-4
le-3
0.01
0.02
0.05
0.2
0.5
0.7
1.0
11.2
10.2
7.0
3.6
2.9
2.3
2.1
2.3
2.2
2.2
2
11.2
10.2
7.1
3.7
3.0
2.4
2.1
2.3
2.2
2.2
11.2
10.2
7.2
3.9
3.4
2.9
2.6
2.5
2.5
2.5
10
11.2
10.2
7.4
4.5
4.0
3.6
3,4
3.4
3,4
3,4
50
11.2
10.6
8.7
7.2
7.0
6.9
6.9
6,9
6.9
6,9
Table 3: Set sizes of RAPS with parameters kreg and X, a ResNet-112, and coverage level 90%.
0
À
0.001
X 0.01
0.1
X
size
cnt
cvg
cnt
cvg
cnt
cvg
cnt
cvg
cnt
cVg
0 to
11627
0.88
11539
0.88
11225
0.89
10476
0.92
10027
0.93
2 to 3
3687
0.91
3702
0.91
3741
0.92
3845
0.93
3922
0.94
4 to 6
1239
0.91
1290
0.91
1706
0.92
4221
0.89
6051
0.83
7 10
688
0.93
765
0,93
1314
0,91
1436
0.71
11 to 100
2207
0.94
2604
0.93
2014
0.86
22
0.59
0
101 to 1000
552
0.97
100
0.90
0
0
0
Table 4: Coverage conditional on set size. We report average coverage of images stratified by the size of the set output by RAPS using ResNet-152 for varying X. The marginal coverage rate is 90%.
In Table 4, we report on the coverage of APS and RAPS, stratified by the size of the prediction set. Turning our attention to the À = () column, we see that when APS outputs a set of size 101 1000, APS has coverage 97%, substantially higher than 90% nominal rate. By Proposition 3, we conclude that APS is not achieving exact conditional coverage, because the scores are far from the oracle probabilities. The APS procedure still achieves marginal coverage by overcovering hard examples and undercovering easy ones, an undesirable behavior. Alternativeyy, RAPS can be used to regularize the set sizes-for À = .001 to = .01 the coverage stratified by set size is more balanced. In summary, purely based on the adaptiveness desideratum, RAPS with light regularization is preferable to APS. Note that as the size of the training data increases, as long as f consistent, naive and APS will become more stable, and so we expect less regularization will be needed.
Lastly, we argue that conditional coverage is a poor notion of adaptiveness when the best possible model (i.e., one fit infinite data) has high accuracy. Given such a model, the oracle procedure from Romano et al. (2020) would return the correct label with probability 1 and the empty set with probability a. That having correct conditional coverage for high-signal problems where Y is perfectly determined by X requires perfect classifier. In our experiments on ImageNet, APS does not approximate this behavior. Therefore, conditional coverage isn't 't the right goal for prediction sets with realistic sample sizes. Proposition suggests relaxation. We could require that we have a for any A C f0, 1, }; Appendix E.2 develops this idea. We view this as promising way to reason about adaptiveness in high-signal problems such as image classification.
the right coverage, no matter the size of the prediction set: P(Y E C(X) {[C(x)) E A})
5 DISCUSSION
For classification tasks with many possible labels, our method enables a researcher to take any base classifier and return predictive sets guaranteed to achieve pre-specified eтror level, such as 90%, while retaining small average size. It is simple to deploy, so an attractive, automatic way to quantify the uncertainty of image classifiers- an essential task in such settings as medical diag- nostics, self-driving vehicles, and flagging dangerous internet content. Predictive sets in computer vision (from RAPS and other conformal methods) have many further identify hard test-time examples. Finding such examples is useful in active learning where one only has resources to label small number of points. In a different direction, one improve efficiency of a classifier by using a cheap classifier outputting a prediction set first, and an expensive one only cascade; see, e.g., Li al. 2015), and Fisch et al.
since they systematically
when the cheap classifier outputs large (2021) for an implementation of conformal prediction in this setting, One can also use predictive sets during model development to identify failure cases and outliers and suggest strategies for improving its performance. Prediction sets are most useful for problems with many classes; returning to our initial medical motivation, we envision RAPS could used by doctor to automatically screen for a large number of diseases (e.g. via blood sample) and refer the patient to relevant specialists.

---

Published as a conference paper at ICLR 2021
REFERENCES
Maxime Cauchois, Suyash Gupta, and John Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. 2020. 10t::2000.011811
Adam Fisch, Tal Schuster, Tommi S. Jaakkola, and Regina Barzilay. Efficient conformal predic- tion via cascaded inference with expanded admission. In International Conference on Learning Representations, 2021.
Yarin Gal. Uncertainty in Deep Learning. University of Cambridge, 1(3), 2016.
Leying Guan and Rob Tibshirani. Prediction and outlier detection in classification problems. 2019. LtXiv:1905.04396
Chuan Guo, Gcoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. 2017. arXiv:1706.045%)
Chirag Gupta, Arun K Kuchibhotla, and Aaditya K Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. arXiv, pp. 1910v-1910, 2019.
Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman. 1rXiv:1805.0946)
Cautious deep learning, 2018.
Heinrich Jiang, Been Kim, Melody Guan, and Maya Gupta. To trust or not to trust classifier. In Advances in Neural Information Processing Systems, pp. 5541-5552, 2018.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. 2018. D.XXvv:807.0066:
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, pp. 6402-6413, 2017.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-paramen non-parametric regression. Journal of the Royal Staristical Society: Series B (Statistical Methodology), 76(1):71-96 2014.
Jing Lei, Max GeSll, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111 2018. doi: 1,.1080001221459.211..3330
Haoxiang Li, Zhe Lin, Xiaohui Shen, Jonathan Brandt, and Gang Hua. A convolutional neural network cascade for face detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
2015.
Qing Li, Weidong Cai, Xiaogang Wang, Yun Zhou, David Dagan Feng, and Mei Chen. Medical image classification with convolutional neural network. International Conference on Control Automation Robotics & Vision, pp. 848. IEEE, 2014.
Alexander Selvikvág Lundervold and Arvid Lundervold. An overview of deep learning in medical imaging focusing MRI. Zeitschrift für Medizinische Physik, 1922):102-127, 2019.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
Soundouss Messoudi, Sylvain Rousseau, and Sebastien Destercke. Deep conformal prediction for robust models. In Information Processing and Management of Uncertainty in Knowledge-Bant Systems, pp. 528-540. Springer, 2020.
Radford M Neal. Bayesian Learning for Neural Networks. Springer Science Business Media, 2012.
Jeremy Nixon, Michael W Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Measur- ing calibration in deep learning. In CVPR Workshops, pp. 38 -1, 2019.

---

Published as a conference paper at ICLR 2021
Harris Papadopoulos, Kostas Proedrou, Vladimir Vovk, and Alex Gammerman. Inductive confi- dence machines for regression. In Machine Learning: European Conference on Machine Learn- ing ECML 2002, pp. 345-356, 2002.
Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. PAC confidence sets for deep neural networks via calibrated prediction. 2019. arXiv:2001.00 100000000.00006..
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, pp- 2019.
Tim Pearce, Mohamed Zaki, Alexandra Brintrup, and Andy Neely. High-quality prediction inter- vals for deep learning: A distribution-free, ensembled approach. In International Conference on Machine Learning, pp. 6473-6482, 2018
John Platt al. Probabilistic outputs for support vector machines and comparisons regularized likelihood methods. Advances in Large Margin Classifiers, 10(3):1177,, 1999.
Joaquin Quinonero-Candela, Carl Edward Rasmussen, Fabian Sinz, Olivier Bousquet, and Bern- hard Schölkopf. Evaluating predictive uncertainty challenge. In Machine Learning Challenges Workshop, pp. 1-27. Springer, 2005.
Muhammad Imran Razzak, Saeeda Naz, and Ahmad Zaib. Deep learning for medical image process- ing: Overview, challenges and the future. In Classification in BioApps, pp. 323-3333333 323-350. Springer, 2018.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian bandits showdown: An empir- ical comparison of Bayesian deep networks for Thompson sampling. 2018. arXiv:1802.09127.
Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems, pp. 3543-3553. 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. 2020. arXiv:2006.02544.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Stutistical Association, 114(525):223-234 2019.
Murat Sensoy, Lance Kaplan, and Melih Kandemir, Evidential deep learning to quantify classifica- tion uncertainty. In Advances Neural Information Processing Systems, pp. 3179-3189, 2018
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal predic- tion under covariate shift. In Advances Neural Information Processing Systems, pp. 2530-2540.. 2019.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning, volume 25, pp. 475-490, 2012.
Vladimir Vovk, Alexander Gammerman, and Craig Saunders. Machine-leaming applications of
algorithmic randomness. In International Conference on Machine Learning, pp. 444-453, 1999.
Vladimir Vovk, David Lindsay, Ilia Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical report, 2003. Technical report.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer, 2005.
Chong Zhang, Wenbo Wang, and Xingye Qiao. On reject and refine options in multicategory clas- sification. Journal of the American Statistical Association, 113(522)773--445 2018.

---

Published as a conference paper at ICLR 2021
A PROOFS
Theorem I. Let u,), in E C(r,,, and let 8; s(X,, Us. Vi) for i ,,..., n.
Then
{y s v. S <T {v E C(x, u, T, because C(2, u, T) is finite set growing in by the assumption in Eq. (2). Thus,
(T: (T:1(8:8 ST) [(1 (m 1)1} = {T. Hi: Y, E E
U,,
[(n + 1) a)
Considering the left expression, the infimum over of the set on the left hand side is the [[1 an + 1)] smallest value of the 8i, so this is the value of focal- Since $1,..., Sn s(x,11, Un-1:
exchangeable random variables, Ki
s(Xn+1, Unt1, v2+1) > 8:)l stochastically dominated by the discrete uniform distribution
on 10,1,...,,9 n]. We thus have that
P(Y++1 & C(xx+1, Unti, feca)) ((8(((nt1, (+ focal)
P (((i: s(Xn+1, Un+1, Yn+1) > si}l 2 [n + 1)(1 =)]]
P [é: ((d:s((N+)) s(Xn41, UntI, Yn+1) > si
(n + 1) [[[1=a]] a)]
S a.
Proposition The lower bound follows from Theorem prove the upper bound, using the result from Theorem 2.2 of Lei et al. (2018) it suffices to show that the variables s(X,, U, Y,) inf(T: Y, E C(X,, T} are almost surely distinct. this end, note that that
s(Xi, U, Y,) = px. (Yi) + #x, (Yi) U, + (Xo -
and due to the middle term of the sum, these values distinct almost surely provided fx, (Y)
Proposition 2. We first show that feall I 1++ k* kreg. Note that since at least [(1 an + 1)] of the conformal calibration points are covered by set of size k", at least [[1 a) + 1)] of the F; in Algorithm 2 are less than or equal to + ks kreg. Thus, by the definition of focal. we have that it is less than or equal to h. lireg- Then, note that by the definition of C* in Eq. (4), we have that
IC* (X*+x, Un+1, facl)) k*
as long as Focal 5 1 kreeg since for the h- + 1 most likely class, the sum in Eq. (4) will exceed A (1 k kree) (1 +1+16 K² kreg) 2 facali and so the ks + class will not be in the set.
Proposition 3. Suppose P(Y C(X) X=
x)x)=1 =1 a for each E Rd. Then,
P(Y c(() ((xX)110(2 [(() E S, E x X
P((C(X)| A)
[ (((((()))))))((()) P([(()] E A)
a-a.

---

Published as a conference paper at ICLR 2021
Accuracy
Coverage
Size
Model
Top-1
Top-5
Top K
Naive
APS
RAPS
Top K
Naive
APS
RAPS
ResNeXt101
0.794
0,945
0.905
0.938
0,950
0.950
5.64
36.4
46.3
4.21
ResNct152
0.783
0.940
0.950
0,943
0.950
0.950
6.36
19.6
22.5
4,40
ResNet101
0.774
0.936
0.950
0.944
0.950
0.950
6.79
20.6
23.2
4.79
ResNet50
0.762
0.929
0.951
0.943
0,950
0.950
8.12
22.9
26.2
5.57
ResNet18
0.698
0.891
0.950
0.943
0,950
0.950
28.9
33.2
11.7
DenseNet161
0.772
0.936
0.950
0.942
0.950
0.950
6.84
23.4
28.0
5.09
VGG16
0.716
0.904
0.950
0,943
0,950
0.950
12.9
24.6
27.8
8.98
Inception
0.695
0.887
0.950
0.937
0.950
0.950
20.3
142.0
168.0
18.5
ShuffleNet 0.694
0.883
0.950
0.940
0.950
0.950
19.3
58.7
71.6
16.3
Table Results on Imagenet- Val.. We report coverage and size the optimal, randomized fixed sets, naive, APS, and RAPS sets for nine different Imagenet classifiers. The median of-means for each column is reported over 100 different trials. See Section 3.1 for full details.
Accuracy
Coverage
Size
Model
Top-1
Top-5
Top K
Naive
APS
RAPS
Top K
Naive
APS
RAPS
ResNeXt101
0.678
0.875
0.950
0.937
0.950
0.950
21.7
86.2
107.0
18.5
ResNet152
0.670
0.876
0.951
0.944
0.950
0.950
21.3
51.0
56.6
16.2
ResNet101
0,656
0.86
0.95
0.944
0.950
0.949
25.7
55.8
63.1
19.1
ResNe150
0.634
0.847
0.949
0.944
0,949
0,950
65.9
21.5
ResNet18
0.572
0,802
0.950
0.942
0.950
0,949
48.3
65.0
74.0
35.3
DenseNet161
0.653
0.861
0.951
0.941
0.950
0.949
25.9
60.0
72.7
20.4
VGG16
0.588
0.816
0.950
0.943
0.950
0.949
38.5
57.8
63.9
26.4
Inception
0.573
0.797
0.950
0.943
0,949
0.950
253.0
275.0
70.2
ShuffleNet 0.560
0.781
0.950
0.941
0.949
0.949
80.0
125.0
140.0
67.4
Table Results on Imagenct-V2 V2. report coverage and size of the optimal, randomized fixed sets, naive, APS, and RAPS sets for nine different Imagenet classifiers. The median-of-mean for each column is reported over 100 different trials the 5% level. See Section 3.2 for full details.
B
RANDOMIZED PREDICTORS
The reader may wonder why we choose to use randomized procedure. The randomization is needed to achieve a coverage exactly, which we will explain via an example. Note that the randomization is of little practical importance, since the predictive set output by the randomized procedure will differ from the that of the non-randomized procedure by at most one element.
Turning to example, assume for particular input image expect set of size l to have 91% coverage, and a set of size & - to have 89% coverage. order to achieve our desired coverage of 90%, we randomly choose size & or k with equal probability. In general, the probabilities will not be equal, but rather chosen so the weighted average the two coverages is exactly 90%. If a user of method desires deterministic sets, it is easy to turn off this randomization with single flag, resulting in slightly conservative sets.
C IMAGENET AND IMAGENETV2 RESULTS FOR a = 5%
We repeated Experiments 1 and 2 with a 5%. See the results in Tables 5 and 6.
D COVERAGE AND SIZE CONDITIONAL ON IMAGE DIFFICULTY
In order to probe the adaptiveness properties of APS and RAPS we stratified coverage and size by image difficulty (the position of the true label in the list of most likely least likely classes, based on the classifier predictions) in Table 7. With increasing X, coverage decreases for more difficult images and increases for easier ones. In the most difficult regime, even though APS can output large sets, those sets still rarely contain the true class. This suggests regularization is sensible way to stabilize the sets. As a final word Table 7. notice that as À increases, coverage improves for the more common medium medium-difficuly examples, although not for very rare and difficult ones.

---

Published as a conference paper at ICLR 2021
À = 0
À
0.001
X 0.01
À 0.1
=
difficulty
count
cVg
SZ
cVg
57
CVg
SZ
cVg
57
CVg
57
15668
0.95
5.2
0.95
3.8
0.96
2.5
0.97
2,0
0.98
2.0
2 to
2578
0.78
15.7
0.78
10.5
0.80
6.0
0.84
3.9
0.86
3.6
4 to
717
0.68
31.7
0.68
19.7
0.70
9.7
0.71
5.3
0.64
4.4
to
334
0.63
41.0
0.63
24.9
0.60
11.6
0.22
5.7
0.00
4.5
11
622
0.53
57.8
0.51
34.1
0.26
14.7
0.00
6.4
0.00
101 to 1000
81
0.23
96.7
0.00
51.6
0.00
19.1
0.00
7.1
0.00
4.7
Table 7: Coverage and size conditional on difficulty. We report coverage and size of RAPS sets using ResNet- 152 with kreg and varying À (recall that À = is the APS procedure). The desired coverage level is 90%. The 'dfffiuutty is the ranking of the true class's estimated probability.
Violation at a
10%
Violation a = 5%
Model
APS
RAPS
APS
RAPS
ResNeXt101
0,090
0.049
0.048
0.021
ResNet152
0,069
0.038
0.037
0.017
ResNet101
0.073
0.041
0.038
0.017
ResNet50
0.069
0.037
0.037
0.016
ResNet18
0.046
0.025
0.032
0.019
DenseNet161
0,080
0.047
0.040
0.016
VGG16
0.046
0.022
0.030
0.022
Inception
0.085
0.045
0.043
0.023
ShuffleNet
0.061
0.033
0.035
0.020
Table 8: Adaptiveness results after automatically tuning A. We report the median sizc-stratified coverage
violations of APS and RAPS over 10 trials. See Appendix E.2 for experimental details.
E CHOOSING kreg AND À OPTIMIZE SET SIZE AND ADAPTIVENESS
This section describes two procedures for picking kreg and À that optimize for set size adaptive- ness, outperforming APS in both cases.
E.1
OPTIMIZING SET SIZE WITH RAPS
Algorithm 4 Adaptive Fixed-K
Input: o; I {1,..., K)**K, and one-hot y E {0, 1] corresponding respectively the classes
from highest to lowest estimated probability mass, and labels for each of examples in the dataset
1: procedure GET-KSTAR(a.T.9)
2: for i (1..... , do
3:
4+ [ lij = yi
4:
k - the [11 - (1 + n]1 largest value in {L+}
5: return 2.-
Output: The estimate of the smallest fixed size set that achieves coverage, A-
To produce Tables 1, 2, and 6, we chose kreg and À adaptively. This required extra data splitting step, where small amount of tuning data {I,, y4 (=1 were used estimate k" and then kreg is set
to A* Taking m Re 1000 was sufficient, since the algorithm is fairly insensitive to kroe (see Table 3).
Then, i was calculated with Algorithm 4. We produced the Imagenet V2 tables with 1000 and the Imagenet tables with m 10000.
After choosing k=", we chose to have small set size. We used the same tuning data to pick f and for simplicity (this does not invalidate coverage guarantee since conformal calibration still uses fresh data). A coarse grid search on À sufficed, since small parameter variations have little impact on RAPS. For example, on the m holdout samples in order to produce Tables 1, 5, 2, and 6. We include subroutine that automatically chooses is and À to optimize size in our GitHub codebase.
chose the À {0.001, 0.01, 0.2, 0.5) that achieved the smallest size

---

Published as a conference paper at ICLR 2021
E.2 OPTIMIZING ADAPTIVENESS WITH RAPS
In this appendix, we show empirically that RAPS with an automatically chosen set of Kreg and improves the adaptiveness of APS. Recall our discussion in Section 4 and Proposition 3, wherein we propose size-stratified coverage useful definition of adaptiveness in image classification. After picking Kreg as in Appendix E, we can choose À using the same tuning data to optimize this notion of adaptiveness.
We now describe particular manifestation of our adaptiveness criterion that we will use to optimize
x. Consider disjoint set-size strata {S.) where U S; {l,..., | Then define the indexes
of examples stratified by the prediction set size of each example from algorithm as Jj { [C,,, Y, U.) E Sz}. Then we can define the size-stratified coverage violation of an algorithm on strata { as
[[: Y, C(X,, Y, U.) E JH a1
SCCV (SH=E) sup
(5)
[J]
In words, Eq. (5) is the worst-case deviation of C from exact coverage when it outputs sets of a certain size. Computing the size-stratified coverage violation thus only requires post-stratifying the results of C' on a set of labeled examples. If conditional coverage held, the worst stratum coverage violation would be 0 by Proposition 3.
To maximize adaptiveness, we'd like to choose À to minimize the size-stratified coverage violation of RAPS. Write Cx to mean the RAPS procedure for a fixed choice of kreg and x. Then we would like to pick
À min SSCV (
(6)
X
In our experiments, we choose a relatively coarse partitioning of the possible set sizes: 0-1, 2-3, 4- 10, 11-100, and 101-1000. Then, we chose the À E {0.00001, 0.0001, 0.0008, 0.001, 0.0015, 0.002) which minimized the size-stratified coverage violation on the tuning set. The results in Table 8 show RAPS always outperforms the adaptiveness of APS on the test set, even with this coarse, automated choice of parameters. The table reports the median size-stratified coverage violation over 10 independent trials of APS and RAPS with automated parameter tuning.
F COMPARISON WITH LEAST AMBIGUOUS SET- VALUED CLASSIFIERS
In this section, compare RAPS to the Least Ambiguous Set-valued Classifier (LAC) method introduced in Sadinle et al. (2019), an alternative conformal procedure that is designed to have small sets. The LAC method provable gives the smallest possible average set size in the case where the input probabilities are correct, with the idea that these sets should be small even when the estimated probabilities are only approximately correct. In the notation of this paper, the LAC method considers nested sets of the following form:
CLA (I, (v nz (x) 1-
which can be calibrated using as before in using Rccal from Eq. (3).
We first compare nai ve, APS, RAPS, and LAC in terms of power and coverage in Table 9, In this experiment, we tuned RAPS to have small set size as described Appendix E. We see that LAC also achieves correct coverage, as expected since is conformal method and satisfies the guarantee from Thcorem 1. We further see that it has systematically smaller sets that RAPS, although the difference is slight compared to the gap between APS and RAPS APS and LAC.
We next compare RAPS to LAC in terms of adaptiveness, tuning RAPS as in Section E.2. First, in Table 10, report on the coverage of LAC for images of different difficulties, and that LAC has dramatically worse coverage for hard images than for easy ones. Comparing this to RAPS in Table 7, we see that RAPS also has worse coverage for more difficult images, although the gap is much smaller for RAPS. Next, in Table 11, we report on the SSCV metric for of adaptiveness (and conditional coverage) for APS. RAPS. and LAC. We find that APS and RAPS have much better adaptiveness than LAC, with RAPS being the overall winner. The results of all of these comparisons are expected: LAC is not targetting adpativeness and instead trying to achieve the smallest possible set size. It succeeds at its goal, sacrificing adaptiveness to do so.
15

---

Accuracy
Coverage
Size
Model
Top-1
Top-5
Top K
Naive
APS
RAPS
LAC
Top K
Naive
APS
RAPS
LAC
ResNeXt101
0.793
0.945
0.900
0.889
0.900
0.900
0.900
2.42
17.2
19.9
2.01
1.65
ResNet152
0.783
0.941
0.900
0.894
0.900
0.900
0.900
2.64
9.68
10.4
2.09
1.76
ResNet101
0.774
0.936
0.900
0.895
0.900
0.900
0.900
2.83
10.0
10.8
2.25
1.87
ResNer50
0.761
0,929
0.899
0.896
0.900
0.900
0.900
3.13
11.7
12.3
2.55
2.05
ResNet18
0.698
0.891
0.900
0.895
0.900
0.900
0.900
5.74
15.3
16.1
4.38
3.64
DenseNet161
0.771
0.936
0.900
0.894
0.900
0.900
0.900
2.84
11.2
12.0
2.29
1.90
VGG16
0.716
0,904
0.900
0.896
0.901
0.900
0.900
4.75
13.4
14.1
3.54
3.00
Inception
0.695
0.886
0.899
0.884
0.900
0.899
0.900
6.27
74.8
88.8
5.24
4.06
ShuffleNet 0.694
0.883
0.900
0.892
0.900
0.899
0.900
6.45
28.8
32.1
5.01
4.14
Table 9: Results on Imagenet-Vat Val. We report coverage and size of the optimal, randomized fixed sets, naive, APS, RAPS and the LAC sets for nine different Imagenet classifiers. The median-of of- means for each column reported 100 different trials at the 10% level. See Section 3.1 for full details.

---

Published as a conference paper at ICLR 2021
difficulty
count
cvg
15668
1.00
1.5
2 to
2578
0.81
2.6
4
717
0.23
3.0
7 to 10
334
0.00
2.9
11 100
622
0.00
2.7
101 to 1000
81
0.00
2.4
Table 10: Coverage and size conditional difficulty. We report coverage and size of the LAC sets for ResNet-152.
Violation at
10%
Violation
5%
Model
APS
RAPS
LAC
APS
RAPS
LAC
ResNeXt101
0.086
0.047
0.217
0.047
0.022
0.127
ResNet152
0.067
0.039
0.156
0.04
0.021
0.141
ResNet101
0.075
0.060
0.152
0.039
0.015
0.120
ResNet50
0.071
0.042
0.131
0.037
0.014
0,109
ResNet18
0.050
0.024
0.196
0.031
0.021
0.059
DenseNet161
0.076
0.055
0.140
0.039
0.016
0.110
VGG16
0.051
0.023
0.165
0.029
0.019
0.070
Inception
0.086
0.042
0.181
0.043
0.023
0.135
ShuffleNet
0.058
0.030
0.192
0.033
0.019
0.045
Table 11: Adaptiveness results after automatically tuning X. We report the median SSCV of APS RAPS and LAC over 10 trials. See Appendix E.2 for experimental details.


Reviews:
[{"review_id": "jIp_dZg3Yo6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=== Summary ===\n\nIn this paper, the authors propose a regularized conformal score for use in a conformal prediction framework. This regularizer is motivated by the instabilities of top-p variations on conformal scores (cf. Romano et. al., 2020) and the resulting high-variance in output conformal prediction set sizes. The proposed regularizer smooths top-p scores with top-k scores, which empirically results in more robust predictive sets. The authors also perform a large-scale evaluation on ImageNet with modern architectures, which serves as a helpful benchmark for conformal prediction algorithms.\n\nFor those not familiar with the goal of conformal prediction: it is a method to provide prediction *sets* in-place of single (top-1) predictions, where the sets satisfy marginal probabilistic performance guarantees (i.e., the correct answer is included in the set with probability ≥ 1 - alpha).\n\n=== Justification for Score ===\n\nThe main contribution of the paper (RAPS) is reasonable, but has perhaps somewhat limited novelty when taken in context with the broader conformal prediction literature. The paper, at least at its current version, also has several presentational and clarity issues which makes it somewhat hard to follow at points, and some of the results difficult to verify. I am willing to be convinced to increase my score if at least 1) the language of the introduction is reworked to reflect the broad conformal prediction literature, and 2) it is demonstrated that RAPS significantly improves over a naive \"adaptive\"  (i.e., conformalized) top-k baseline (see \"Concerns\").\n\n=== Strengths ===\n\n+ Uncertainty quantification is a relevant and timely topic.\n\n+ Conformal prediction and the resulting uncertainty sets they produce is also a practical and important instantiation of uncertainty quantification/prediction with performance guarantees.\n\n+ The proposals put forth in the paper are interesting and potentially useful.\n\n=== Concerns ===\n\n- Overall, there are unfortunately several clarity and presentation issues (see also \"Minor Comments\" below for more on this). At a high level, however, it seems to me that the framing in this paper is confusing when it comes to distinguishing the contributions put forth here, versus those of the broader conformal prediction literature. This stems from language in the abstract, such as \"we present an algorithm that...\" or in the introduction, such as \"Our paper describes a novel method for constructing prediction sets...\". Yet, the main contribution appears to rather be a particular formulation of a *conformal scoring function*, i.e., S(x, y) := \\rho_x(y) + \\hat{\\pi_x}(y) * u + \\lambda * (o_x(y) - k_reg)^+.  Similar variants (as the authors do point out) have already been proposed in Romano et. al., 2020 and Cauchois et. al., 2020. I would strongly recommend updating the language and introductory claims so as not to mislead readers.\n\n- It should be clarified that the guarantee expressed in Eq. 1 is *marginal*, i.e., taken over all permutations of (X_1, Y_1), ..., (X_{n+1}, Y_{n+1}). It also should hold for exchangeable rather than just i.i.d. samples; I didn't see a reason in the method to weaken this standard CP result. Finally, the comment on \"require only 1000 held-out data points in practice\" is confusing to me... in practice to achieve what? The guarantee in Eq. 1 should hold for all finite samples.\n\n- Eq. 1 stipulates a ≥ 1 - alpha criterion (which the methods support)---but Section 2 begins by saying \"exactly 1 - alpha\" coverage. Can you clarify?\n\n- In the introduction it states, \"for examples where the model is not confident, naive must select many classes...\". It's not immediately apparent why this is a problem. If the model probability p(y | x) is indeed calibrated, then it seems that naive should indeed be the oracle method (in order to guarantee both marginal *and* conditional coverage). Of course, softmax outputs in standard deep nets can be far from calibrated, which leads to the suboptimal behavior. But this doesn't seem to be the problem the introduction is pin-pointing. \n\n- In fact, related to the above, both Romano et. al., 2020 and Cauchois et. al., 2020 motivate their conformalizations as an approach to asymptotically get conditional coverage (assuming p(y | x) converges with more data and better models). Accordingly they also measure a \"worst slab coverage\" to quantify how far the method deviates from conditional coverage in the worst case. The proposed top-k regularizer breaks this asymptotic property, which at least should be something to note relative to those related works. It would be even better if some additional experiments in the appendix showed what realized trade-off, if any, there is between WSC and tighter set sizes due to regularization.\n\n- Proposition 2 claims strictly better than top-k performance, but the proof seems to suggest that this is rather only \\subseteq?\n\n- In a similar vein, Proposition 2 makes comparisons to top-k performance, but (adaptive) top-k isn't shown in Table 1. Only top-1 and top-5 are. If simply using the rank as the conformal score, how does the set size compare to RAPS? Note that top-k will have many ties, so it also makes sense to use a randomized variant of top-k (i.e., S(x, y) := o_x(y) + u) for fair comparison.\n\n- lambda and k_reg are hyper-parameters that must be set. In addition to the n calibration data points, it would seem that one would also require additional development data to use to pick these. It's also unclear what data was used to do the platt scaling. If on the same calibration data, it's not clear to me that this is retains exchangeability, which will affect the formal guarantees.\n\n=== Minor Comments ===\n\n* The pseudo code in the algorithms, which uses a mixture of python-style notation and mathematical indexing (e.g., I_i[j] in Algorithm 2), is quite hard to follow. I suggest sticking to one.\n\n* Algorithm 1 line 7 is missing a sum of some sort around scores[0: L].\n\n* Algorithm 2 lines 3-4 has sloppy notation: it appears a set (L_i) is being added to a scalar (k_reg + 1).\n\n* Though I certainly appreciate the page constraints, Tables 1 & 2 are too small to easily read. I don't think that the Top-1 and Top-5 accuracy add much (see earlier comments on adding a conformalized top-k result).\n\n* Similarly, the left side of Fig. 4 is hard to read.\n\n=== Response After Rebuttal === \n\nThank you for what I found to be an impressive and convincing rebuttal, both in terms of the detailed responses to every comment---and not to mention the extensive rewrite of this paper in the limited amount of time available. In short, I think that the paper is significantly improved, and is now at a level of quality that I feel warrants acceptance. As such, I am choosing to raise my initial score of 4 to 7 (good paper, accept).\n\nAs the revised version introduces many changes, I have some new (minor) comments:\n\n- The last line of the abstract claims \"sets that are often factors of 5 to 10 smaller\". This is true for APS and NAIVE, but not adaptive top-k. You might wish to qualify this statement as to which comparison you are referring to. \n\n- Thank you for clarifying the introduction w.r.t. problems with NAIVE. The third \"problem\" seems a bit funny to me; it doesn't identify a *problem* with NAIVE, but rather that other methods are better (which seems to stem from problems 1 and 2). Can you clarify this point to make it more precise?\n\n- Typo, related work: \"[...] data-splitting version known as *split conformal prediction* THAT enables conformal prediction [...]\"\n\n- Related work when talking about equal coverage per class, you might want to cite the earlier reference of mondrian conformal prediction: Vladimir Vovk, David Lindsay, Ilia Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical Report, 2003.\n\n- Theorem 1's remark on \"this result is not new\". Not to nitpick, but I'm not sure which aspects of Thm. 1 makes it \"first appear\" in Papadopoulus et. al. and Hechtlinger et. al? This result can likely be found in (or if not explicitly in, then derived from) from late 1990's work by Vovk and co. on Ridge Regression Confidence Machines, Transductive Confidence Machines, etc. Or the journal/book papers (i.e., Algorithmic Learning in a Random World, Hedging Predictions in Machine Learning, etc).\n\n(It goes without saying, however, that this revision is much better in terms of proper citation than before!)\n\n- Proposition 2 seems to have some funny crowding around the \\subseteq operator.\n\n-  Nice work on adding section 4. In the proof of proposition 3 I believe you accidentally left out set size (| |) around C(X) on the r.h.s.\n\n- In the discussion, you mention improving efficiency via prediction cascades. You might be interested to refer to a concurrent ICLR submission (https://openreview.net/forum?id=tnSo6VRLmT) which does precisely this, and to which your work on larger label spaces seems quite complementary.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "j7YczQTgqTp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n Prediction sets are used to quantify the uncertainty of classification. The naive approach which include the labels until a pre-specified coverage probability is satisfied often leads to large prediction sets. Adaptive Prediction Sets (APS) can output prediction sets with desired coverage but set sizes are still not satisfyingly small and the results are unstable, especially when many probability estimations fall into the tail of the distribution. \n\nIn order to make the prediction stable and sets as narrow as possible under pre-specified coverage probability, this paper extends APS to Regularized Adaptive Prediction Sets (RAPS) by penalizing those class with small probabilities beyond k many classes already included, which leads to a small prediction size. The regularization is an interesting idea in terms of minimizing prediction sets, which is different from previous works where most of them directly minimize a quantity related to the cardinality of prediction sets or intervals. Empirically, compared with other set-valued classifiers extracting information from the same base model CNNs, the proposed method outperforms significantly in terms of set sizes when fixing pre-specified coverage. Moreover, this work shows adaptiveness: it tries to allow large prediction size for difficult instances and small prediction size for easy instances.\n\n##########################################################################\n\nReasons for score: \n\nOverall, I vote for accepting. I think the method is well motivated and the solution is simple and portable (can be applied to many base methods).  However, there could be more discussions on several aspects of the problem.\n\n \n##########################################################################\n\nPros: \n\n1. Studies an important problem.\n\n2. The proposed method is easy to implement and can be applied to general scores or be used to improve base conformal prediction methods.\n\n3. Very impressive empirical performance.\n\n ##########################################################################\n\nCons: \n\n1. Theoretically the \"optimal\" set-valued classifier is based on P(Y=k | X=x). In this sense, the naive approach can be viewed as a plug-in approach when the score is an estimate of P(Y=k | X=x). When regularization is applied, something must be lost. This is as much like in lasso for high-dimensional regression, a penalty function makes the coefficient estimate biased (to trade for sparisity). It is unclear what is lost here with regularization. Is the solution no longer \"Fisher consistent\" in a sense?\n\n2. More to the point: it seems that the proposed method is cut out for problems in which there are MANY classes. I wonder whether it will perform just as well for traditional problems in which there are only a few classes (like in the medical field.)\n\n3. Choose a good value for k_reg and lambda seems to be critical. How sensitive is the result to k_reg? Is there any general theory or guidelines about tuning parameter lambda? In the experiments, the validation (calibration) data sets have huge sample size, which may be common in image data domains, but can be unrealistic for broader applications domains. I wonder if the good performance is largely relying on the large validation (calibration) sample size. \n \n##########################################################################\n\nQuestions during rebuttal period: \n\nThe goal of narrowing prediction set size is achieved with the help of regularization, which does not directly try to minimize the cardinality of the prediction set. Can we theoretically prove it is asymptotically optimal? Any comparison to these direct approaches? There is a literature called high-quality prediction interval which directly minimizes the prediction size.\n\n+ Tim Pearce, Mohamed Zaki, Alexandra Brintrup, and Andy Neely. High-quality prediction intervals for deep learning: A distribution-free, ensembled approach. arXiv preprint arXiv:1802.07167, 2018.\n\nAny comments on the relation of the uncertainty set approach with the classification with rejection/abstain methods?\n\n+ Zhang, C., Wang, W. and Qiao, X. (2018), “On Reject and Refine Options in Multicategory Classification,” Journal of the American Statistical Association, 113 (522), pp. 730–745.\n+ Ramaswamy HG, Tewari A, Agarwal S. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics. 2018;12(1):530-54.\n \n#########################################################################\n\nSmall comments: \n\nMost of the figures and tables are far away from the descriptions which makes it hard to read.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ImNowXaW8U7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe paper proposes a new conformalized procedure for computing uncertainty sets in classification tasks. The key feature of the method is that the size of the uncertainty sets are regularized via a penalty on the size. The issue of large uncertainty sets produced by conformalized procedures is an interesting one, which the paper does well to highlight. The proposed solution of using an additive regularizer is reasonable, and appears to be effective for sensible choices of the hyper-parameters. However, the paper has some significant weaknesses.\n\n---\n## Strengths\n1. The method is easy to understand and to implement.\n2. The method satisfies some meaningful theoretical guarantees. (The proofs have been checked for correctness.)\n\n## Weaknesses (and Questions)\n1. I am not 100% convinced that one would _want_ to prune extremely large uncertainty sets arising out of the APS procedure. Because the marginal coverage must be maintained, this forces some small uncertainty sets to be enlarged. However, in many practical classification tasks (including the experiments in this paper), it tends also to be the case that difficult examples are less common than the easier ones. It is hard for me to imagine that one would ever be in a situation that one would wish to over-cover typical examples and undercover atypical ones to an even larger extent, even if the over-coverage is only by one or two classes.\n\nHowever, perhaps there are real world situations in which this is precisely the case. It would be nice if the authors could offer additional insights on this point.\n\n2. The method requires the user to choose two hyper-parameters $k_{reg}$ and $\\lambda$, with some combinations leading to decidedly less desirable results. For the particular case of $k_{reg} = k_*$, perhaps one could look at the RAPS solution as \"interpolating\" between the APS solution and the top-$k_*$ solution. Related to #1 above, it isn't clear to me why this would be desirable in any way. Furthermore, although the hyper-parameters can be loosely interpreted as having to do with the size and the tradeoff with adaptivity, respectively, the precise relationship does not appear to be understood for general cases, making it more challenging to predict the behavior of the method. This is in contrast to the APS, which can be motivated via an oracle procedure with certain optimality properties.\n\n---\n## Recommendation\nA borderline reject. The paper has some significant weaknesses, but does contain some interesting insights.\n\n---\n## Additional Feedback\n1. Section B in the appendix is an essential reading for anyone looking to implement the procedure. I think it ought to be included in the paper.\n2. It looks to me that the method could suffer from poor choices of $k_{reg}$ and $\\lambda$. To prevent such choices, if $k_{reg} = k_*$ is in some sense an oracle choice, wouldn't it be better to give the procedure _with_ the particular hyper-parameter tuning procedure already incorporated?\n3. Personally, I found Tables 4 and 5 far more informative than Figure 4. I would prefer to see the tables in the paper.\n4. I am not sure if the median-of-means is the right metric for performance comparisons. One way to view the RAPS is that it \"tames\" the tail of the distribution of the size of uncertainty sets produced by the APS. Personally, I would prefer a direct comparison of the distributions, as in the tables in the appendix. However, even if a summary measure must be used, there are probably better options. \n5. I find the comment in Section 3.2 \"The result shows that our method can still provide exact coverage under a significant distribution shift\" somewhat misleading. In a split conformal setup, the only distribution shift of any import (with regards to the marginal coverage guarantee) is the one between the calibration set and a new test point.\n\n## Update\nPlease see my reply to the authors' message.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8Mir6Ot-8rx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a regularized generalization of adaptive prediction sets (APS by Romano et al 2020) that results in smaller prediction sets that still maintain the correct coverage level for statistical validity.\n\nThe basic idea of the new regularization is very well-explained and quite elegant: roughly speaking, there is an indifference between classes of low probability so we should penalize including them in the prediction set. Despite the simplicity of this idea, I consider this paper's contribution to be a significant advance and I suspect this idea to be useful beyond classification problems with images, although from my understanding, a crucial assumption is that the number of classes needs to be sufficiently large (e.g., the regularization will not really yield any benefit if it's binary classification). I also found the experiments to be well-chosen.\n\nMy main comment instead is perhaps more of a follow-up: would it be possible to get a conditional guarantee rather than a marginal guarantee (Proposition 1) by adapting proof ideas from Tibshirani et al's \"Conformal Prediction Under Covariate Shift\" (2019)? This seems more aligned with the healthcare related question the paper starts the paper with. In the healthcare context, the patient would ideally want the coverage to be conditional rather than marginal (i.e., in Proposition 1, for the probability that's being sandwiched, we want a version conditioned on $X_{n+1}$ landing near an anchor feature vector to suggest randomly sampling feature vectors *similar* to, for instance, a specific patient in the healthcare context). Separately, it would be interesting if the approach from Tibshirani et al can help RAPS construct even smaller prediction sets than what you get in bold for Table 2 (in the marginal coverage setting and not worrying about conditional coverage).\n\nStrengths:\n- elegant, well-explained method with crisp theory\n- nice suite of experiments\n- helps popularize conformal prediction, which I think more machine learning researchers should know about\n\nWeakness:\n- the paper opens up with a high-stakes motivation but I don't think it really gets back to this high-stakes problem properly; I'd suggest discussing conditional coverage more (also some high-stakes classification problems have very few classes, which the proposed regularization doesn't provide much benefit for?)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agreed that the paper is a solid contribution.

Pros:
- A simple and reasonable extension to adaptive prediction sets that performs well empirically.
- The procedure presented is versatile (i.e. can be applied to general scores or be used to improve base conformal prediction methods).
- A very thorough experimental analysis, including large datasets (i.e. Imagenet) and a wide range of model architectures including ResNet-152.
- Some formal theoretical guarantees are provided for the procedure, although they appear to be straightforward.

Cons:
- Limited technical novelty.

Overall, I recommend a spotlight because the reviewers felt that the topic of predictive uncertainty is of interest to the broader ML and computer vision community, and the paper can have a potentially large impact in popularizing conformal methods as a viable uncertainty estimation method.
Decision: Accept (Spotlight)