Class-Conditional Conformal Prediction with Many Classes
Authors: Tiffany Ding
Anastasios Nikolas Angelopoulos
Stephen Bates
Michael Jordan
Ryan Tibshirani
Venue: NeurIPS 2023 poster (2023)
Keywords: conformal prediction
uncertainty quantification
class imbalance
TL;DR: We tackle the problem of producing prediction sets with good class-conditional coverage in the challenging limited-data, many-classes classification setting.

Abstract: Standard conformal prediction methods provide a marginal coverage guarantee,
which means that for a random test point, the conformal prediction set contains 
the true label with a user-specified probability. In many classification
problems, we would like to obtain a stronger guarantee--that for test points
of a specific class, the prediction set contains the true label with the
same user-chosen probability. For the latter goal, existing conformal prediction
methods do not work well when there is a limited amount of labeled data per
class, as is often the case in real applications where the number of classes is
large. We propose a method called clustered conformal prediction that
clusters together classes having "similar" conformal scores and performs 
conformal prediction at the cluster level. Based on empirical evaluation across
four image data sets with many (up to 1000) classes, we find that clustered
conformal typically outperforms existing methods in terms of class-conditional
coverage and set size metrics.

Class-Conditional Conformal Prediction with Many Classes
Tiffany Ding University of California, Berkeley edu
Anastasios N. Angelopoulos University of California, Berkeley angeloppulls@beekeelyy edu
Stephen Bates MIT s_ bataessmitteed
Michael I. Jordan
Ryan J. Tibshirani
University of California, Berkeley jordan@cs. berkeley.ede edu
University of California, Berkeley ryantibs@berkeley. edu edu
Abstract
Standard conformal prediction methods provide a marginal coverage guarantee, which means that for random test point, the conformal prediction set contains the true label with a user-specified probability. In many classification problems, we would like to obtain stronger guarantee- that for test points of specific class, the prediction set contains the true label with the same user-chosen probability, For the latter goal, existing conformal prediction methods do work well when there is limited amount of labeled data per class, as is often the case in real applications where the number of classes is large. We propose a method called clustered conformal prediction that clusters together classes having "similar" conformal scores and performs conformal prediction at the cluster level. Based on empirical evaluation across four image data sets with many (up to 1000) classes, we find that clustered conformal typically outperforms existing methods terms of class- conditional coverage and set size metrics.
1 Introduction
Consider a situation which a doctor relies on machine learning system that has been trained to output set of likely medical diagnoses based CT images of the head. Suppose that the system performs well on average and is able to produce prediction sets that contain the actual diagnosis with least 0.9 probability. Upon closer examination, however, the doctor discovers the algorithm only predicts sets containing common and relatively benign conditions, such as { (normal, concussion) ), and the sets never include less common but potentially fatal diseases, such intracranial hemorrhage. In this case, despite its high marginal (average) performance, the doctor would not want to use such an algorithm because may lead to patients missing out on receiving critical care. The core problem is that even though the average performance of the algorithm is good, the performance for some classes quite poor.
Conformal prediction (Vovk et al., 2005) is method for producing set- valued predictions that serves a wrapper around existing prediction systems, such neural networks. Standard conformal prediction takes a black-box prediction model, a calibration data set, and a new test example Xtest E X' with unknown label Yrest E y and creates prediction set C(Xurst) C that satisfies marginal coverage:
P(Yest E C(Xteat)) 2 1-
(I)
for a coverage level a E [0, 1] chosen by the user. However, as the example above shows, the utility of these prediction sets can be limited in some real applications. In classification, which study in
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

this paper, the label space Y is discrete. and it is often desirable to have class-conditional coverage:
P(Yeett E C(Xeest) Yeest = v) l a, for all y E y,
(2)
meaning that every class has at least 1 - a probability of being included in the prediction set when it is the true label. Note that (2) implies ( Predictions sets that only satisfy (T) may neglect the coverage of some classes, whereas the predictions sets in (2) are effectively "fair" with respect to all classes, even the less common ones.
Standard conformal prediction, which we will refer to as STANDARD, does not generally provide class-conditional coverage. We present brief case study to illustrate.
ImageNet case study. Running STANDARD using a nominal coverage level of 90% on 50,000 examples sampled randomly from ImageNet (Russakovsky et al., 2015), large-scale image data set described later in Section [3] yields prediction sets that achieve very close the correct marginal coverage (89.8 9.)... However, this marginal coverage is achieved by substantially undercovering some classes and overcovering others. For example, water jug is severely undercovered: the prediction sets only include it in 50.8% of the cases where it is the true label. On the other hand, flamingo is substantially overcovered: achieves a class-conditional coverage of 99. 99.2%. This underscores the need for more refined methods in order to achieve the class-conditions coverage defined in
In principle, it is possible to achieve (2) by splitting the calibration data by class and running conformal prediction once for each class /Vok 2012). We refer to this as CLASSWISE. However, this procedure fails to be useful in many real applications since data-splitting can result in very few calibration examples for each class-level conformal prediction procedure. This typically happens in problem settings where we have many classes but limited data; in such settings, the classwise procedure tends to be overly conservative and produces prediction sets that are too large be practically useful. We note that previous papers (Shi et al.] [0133] Löfström et al. 2015) on class-conditional conformal have not focused the many classes regime and have instead studied binary or most 10-way classification tasks.
In this work, we focus on the challenging limited-data, many-class classification setting and develop a method targeted at class-conditional coverage. Our method mitigates the problems that arise from data-splitting by clustering together classes that have similar score distributions and combining the calibration data for those classes. Figure Tillustrates how the method we propose strikes a balance between STANDARD and CLASSWISE. As will later show in our experiments, this can improve class-conditional coverage in many situations.
Low variance but insufficient granularity
Clustered conformal prediction
Sufficient granularity but high variance
A schematic comparison of conformal prediction methods, including the CLUSTERED method we propose. Each colored circle represents the calibration data for particular class. Existing methods fall on extremes of the spectrum: STANDARD is very stable because it groups data for all classes together, but it is not able to treat classes differently when needed; CLASSWISE has high granularity, but it splits all of the data by class and consequently has high variance in limited-di settings; CLUSTERED strikes a balance by grouping together data for "similar" classes.
Figure 1:
2

---

Our contributions. We make three advances in tackling the problem of class- conditionl coverage.
We propose an extension of conformal prediction called clustered conformal prediction that often outperforms standard and classwise conformal, in terms of class-conditional coverage, when there is limited calibration data available per class.
We present a comprehensive empirical evaluation of class-conditional coverage for con- formal methods on four large-scale classification data sets, each with many (100 to 1000) classes.
We provide general guidelines to practitioners for how to choose an appropriate conformal prediction method in order to achieve class-conditions. coverage in the problem setting at hand.
1.1 Related work
Mondrian conformal prediction. We work in the split-conformal prediction framework (Pa padopoulos al., 2002, Lei et al. 2018) which the training data set (to train the base classifier) and calibration data set are disjoint. Mondrian conformal prediction (MCP) is general procedure that encompasses many kinds of conditional conformal prediction (Vovk et al., 2005). For any chosen grouping function G A' x y + G where 9 denotes the set of all groups, MCP provides coverage guarantees of the form P(Y test E ((Xtett) G( iest)) = g) 2 1 for all groups g E G. The high-level idea behind MCP is to split the calibration data by group and then run conformal prediction on each group. The CLASSWISE conformal procedure a special case of MCP where each value of )² defines group (this is also sometimes referred to as label-conditional conformal prediction).
To the best of our knowledge, previous work has not focused on conddiiond coverage of con- formal methods in the many-classes, limited-data regime that is common to many real classification applications. Löfström al. (2015) present an empirical study of STANDARD and CLASSWISE on binary, 3-way, and 4-way classification data sets (with a focus on the binary setting). For class- imbalanced problems, they find that STANDARD tends to overcover the majority class, and undercover the minority class. [Shi et al. (2013) consider CLASSWISE on the MNIST and USPS data sets, which are 10-way classification problems. [Sun et al.] (2017) use a cross-fold variant of CLASSWISE for binary classification on imbalanced bioactivity data. Hechtlinger et al. (2018) run class-conditional experiments on the 3-class Iris data set, and provide preliminary ideas on how to incorporate inter- actions between classes using density estimation. Guan and Tibshirani (2022) use CLASSWISE in an outlier detection context. Sadinle et al. (2019) consider CLASSWISE with a modification to avoid empty prediction sets and perform experiments on 3-way 10-way classification tasks. To reiterate, the aforementioned papers all focus on the regime that is generally favorable to CLASSWISE, where data is abundant relative to the number of classes. Our work focuses the limited-data regime that often arises in practice.
Other types of conditional conformal prediction. "Conditional coverage" is term that, within the conformal prediction literature, often refers to coverage at a particular input value X = a. is known to be impossible achieve coverage conditional on X x. for all æ, without invoking further distributional assumptions (Lei and Wasserman 2014 Vovk 2012 Barber et al. 2021). However, approximate X- X-conditional coverage can be achieved in practice by designing better score functions (Romano et al.] 2019 2020b Angelopoulos et al. 2022) or by modifying the conformal procedure itself (Romano al., 2020a Guan 2023 Gibbs et 2023). Our work draws inspiration from the latter camp, but our aim is to achieve cans-conniiionl (Y (Y-conditional) coverage rather than X X-conditional coverage. Note that X X-conditional coverage is hard to interpret settings in which Y is not random given X (e.g., in image classification, if x: is an image of a dog, then the true label always y = dog, with no intrinsic randomness after conditioning on X 2r). such settings, more natural to consider class-conditional coverage.
1.2 Preliminaries
We work in the classification setting in which each input X; E X has a class label Y; V, for some discrete set y. Let {(x,, (X),Y.)) N denote calibration data set, where each (X,, Y.) F. Given new independent test point Xust: Ylest) ~ F, our goal is to construct (without knowledge of Yrest) prediction set C(Xtest) that satisfies for some user-specified a E 1].
3

---

Let s X' x + R denote a (conformal) score function, where we take s(z, y) to be negatively oriented, which means that lower scores indicate better agreement between the imput a and the proposed class label The score function is typically derived from a pre-trained classifier f (a simple example to keep in mind s(x y) - (2),, where (x) represents the yoh entry of the softmax vector output by f for the input 2:). For brevity, we denote the score of the ith calibration
data point as 8; = s(X;, Y.). For T E [0, 1] and a finite set A C IR, let Quantile(r, A) denote the smallest A such that T fraction of elements in A are less than equal to For T > 1, we take Quantile(T, A) OC.
With this notation, the STANDARD conformal prediction sets are given by
CSTANdARd (aaaannoXereee (Xrest) = {y 8(( y) S q},
where
[(N 1)(1 a)1
Quantile
N
These prediction sets are guaranteed to satisfy ( (Vovk et al. 2005). We can interpret é as samile adjusted (1 -a) of the scores in the calibration data set. Note that all N data points are used for computing a single number, q.
In contrast, the CLASSWISE procedure computes a separate quantile for every class. Let I {i E [N] Y; = y the indices of examples in the calibration data set that have label y. The CLASSWISE conformal prediction sets are given by
(cLAssWIs((1ess)) = {y: s(Xtest 3) S {
where
[[IZ||
+ 1)(1 a)
T't = Quantile
(Bi)iez))
[Tu]
These prediction sets are guaranteed to satisfy computed using a subset of the data of size [yyl which might be quite small. Importantly, for any class for which [I < (1/a) 1, we will have q" = co. hence any prediction set generated by CLASSWISE will include y, no matter the values of the conformal scores.
2 Vovk 2012). However, the quantile q" is only
The advantage of STANDARD is that we do not need to split up the calibration data to estimate q, so the estimated quantile has little noise even in limited-data settings; however, it does not in general yield class-conditional coverage. Conversely, CLASSWISE is guaranteed to achieve class-con classcoonitiinall coverage, since estimate diffeerent threshold q" for every class; however, these estimated quantiles can be very noisy due to the limited data, leading to erratic behavior, such as large sets.
When we assume the scores are almost surely distinct, the exact distribution of the CLASSWISE class-conditional coverage of class y given a fixed calibration set (Vovk 2012 Angelopoulos and Bates 2023
P(Yestt E CELASSWISE (Xtesss Ytest = ((X,,, ( ~ Beta(k", II + R
where ky [[[Za| + 1)(1 ai]. Note that the probability the left-hand side above is taken with respect to the test point Xtest as the only source of randomness, as we have conditioned on the calibration set. The beta distribution Beta(kg, I
+ 1 -kg) has mean k2/ <Z/([I*| + (which, as
expected, is always at least 1 a) and variance
ky (I" [ +
k2)
a(1 a) I +
which can be large when [T]] is small. For example, if class y only has 10 calibration examples and we seek 90% coverage, then the caas--onddiionall coverage given fixed calibration set is distributed as Beta(10, 1), so there is probability than 80%. Somewhat paradoxically, the variance of the class-conditional coverage means that on a given realization of the calibration set, the CLASSWISE method can exhibit poor coverage on substantial fraction of classes if the number of calibration data points per class is limited.
0.107 that the coverage of class y will be less

---

2 Clustered conformal prediction
With the goal of achieving the class-conditional coverage guarantee in 2 we introduce clustered conformal prediction. Our method strikes balance between the granularity of CLASSWISE and the data-pooling STANDARD by grouping together classes according to a clustering function. For each cluster, we calculate single quantile based on all data in that cluster. We design the clustering algorithm so that clustered classes have similar score distributions, and therefore, the resulting cluster- level quantile is applicable to all classes in the cluster. Next, in Section 2.1 we formally describe the we describe the clustering step in detail.
clustered conformal prediction method; then, in Section 2.2
2.1
Meta-algorithm
To begin, we randomly split the calibration data set into two parts: the clustering data set D₁ {(X,, Yi) iiE E Σı}. for performing clustering, and proper calibration data set D2 {X,, Yi) 8 EE ]2), for computing the conformal quantiles, where [Z] = [>>V] and [Zp N [ for some tuning parameter y E [0, 1]. Then, we apply a clustering algorithm to Dj to obtain clustering M) U [null} that maps each class y E Y to one of M clusters or the "null"
function h: > {1, cluster (denoted null). The reason that we include the null cluster is to handle rare classes that do not have sufficient data to confidently clustered into any the M clusters. Details on how to create are given in the next subsection.
After assigning classes to clusters, we perform the usual conformal calibration procedure within each cluster. Denote by Ií fi E In =y=y) y) the indices of examples in D2 with label y, and by [mmm) U y:h(g)=m Ih the indices of examples in D2 with labels in cluster m. The CLUSTERED conformal prediction sets are given by
COLUSTERED (Xtrss) = {y: : ((eest: 9) S (((ly))),
where, for m 1,...,M, M,
@(m) = Quantile [(Iz(m))
(sihezam)
[T2(m]]
and
[1[Za] + 1)(1 o:] {si))ezz I
(null) =
Quantile
In words, for each cluster m, we group together examples for all classes in that cluster and then estimate a cluster-level quantile q(m). When constructing prediction sets, we include class in the set if the conformal score for class is less than equal the quantile for the cluster that contains For classes assigned to the null cluster, we compare the conformal score against the quantile that would be obtained from running STANDARD the proper calibration set.
We now consider the properties the CLUSTERED prediction sets. For all classes that do not belong to the null cluster, we have the following guarantee (the proof of this result, and all other proofs, are deferred to Appendix[A] A).
Proposition 1. The prediction sets CeLUSTERED from CLUSTERED achieve cluster-conditional coverage:
P(Yrsst E C(Xrest) ii(Yrest) = m) 2 11- a, for all clusters m 1,...,M.. M.
This coverage result comes from the exchangeability between a test point drawn from cluster m and all of the calibration points that belong to cluster m. We get this exchangeability for free from the assumption that the calibration point and test points are sampled i.i.d. from the same distribution. Cluster-come cunttercooniiiionl coverage is a stronger guarantee than marginal coverage, but it is still not strong as the dlas--coniiionall coverage property that we hope to achieve. However, coverage implies class-oonditional in an idealized setting: suppose we have access to an "oracle" clustering function hs* that produces M clusters such that, for each cluster m = 1, 1,.... M, the scores for all classes in this cluster are exchangeable (this would hold, for example, if all classes in the same cluster have the same score distribution). In this case, we have guarantee on class-conditional coverage.
contterconditiooal
5

---

Proposition 2. If = h-, the "oracle" clustering function as described above, then the prediction from CLUSTERED satisfy caass-conditioall coverage 2 for all classes such that h" (y) * null.
This coverage result arises because the oracle clustering function ensures exchangeability between test point drawn from class y and all of the calibration points that belong to the cluster to which belongs. To try to achieve this exchangeability, we want to design so that the scores within each cluster m = 1,..., ,,, M are as close to identically distributed possible, an idea pursue next.
need to construct the clusters carefully. Specifically,
2.2 Ctuatile-bbsed clustering
We seek to cluster together classes that have similar score distributions. To do so, we first summarize the empirical score distribution for each class via vector of score quantiles evaluated at a discrete set of levels E ' S [0, 1]. In this embedding space, a larger distance between classes means their score distributions are more different. While there are various options for defining such an embedding. recall that to achieve clss-conditional coverage, we want to accurately estimate the fimite-sample adjusted) (1 - a) quaantlee for the score distribution of each class. Thus, we want to group together classes with similar quantiles, which is what our embedding is designed to facilitate. After obtaining these embeddings, we can then simply apply any clustering algorithm, such as k-means.
In more detail. denote by I" = {i E I1 YY; = y the indices of examples in Dj with label We compute quantiles of the scores esty from class y at the levels
[[[IV]
1) T (.65, 0,,,5,06,0,7,00.. U1 (10,0,00000000001111-a)0)1) }
T
Iv
and collect them into embedding vector 2D E RI If [I na. where n. = (1/ minfa, 0.1}) 1, then the uppermost quantile in n will not be finite, so we simply assign to the null cluster. For a pre-chosen number of clusters M, run k-means clustering with k M the data {=") y where Youll denotes the set of labels assigned to the null cluster. More specifically, we use a weighted version of k-means where the weight for class y is set | this allows the class embeddings computed from more data to have more influence on the cluster centroids. We denote the cluster mapping that results from this procedure by h 3 {1, .., M) U {null).
Of course, we cannot generally recover an oracle clustering function h with the above (or any practi- cal) procedure, Proposition] 2 does not apply. However, if the score distributions for the classes that assigns to the same cluster are similar enough, then we can provide an approximate condiioonii coverage guarantee. We measure similarity in terms of the colmogorov-Smirno (KS) distance, which defined between random variables X and Y as Dks(X,Y) Y) = supXeR [P(X P(Y < A)].
Proposition 3. Let Sy denote a random variable sampled from the score distribution for class y, and assume that the clustering map h satisfies
DKs(Sy, (
S, )
for all y. 1/ such that h(y)) = h((y') F null.
Then, C = CELUSTERED and for all classes such that such that i((y)) o null,
P(Yestt E C(Xeest) Yeest = v) 2 211a-c
To summarize, the two main tuning parameters used in the proposed method are y E [0, 1]. the fraction of points to use for the clustering step, and M 2 1, the number of clusters to use in k-means. While there are no universal fixed values of these parameters that serve all applications equally well, we find that simple heuristics for setting these parameters often work well in practice, which we describe in the next section.
3 Experiments
We evaluate the class-conditional coverage of STANDARD, CLASSWISE, and CLUSTERED con- formal prediction on four large-scale image data sets using three conformal score functions on each. Code for reproducing our experiments is available stthttp::/// htatps///ggtuubb.c//fffaaaaaaii com/tiifanydiin//
class cow.iiiiioalloooooooooooooo

---

3.1 Experimental setup
We run experiments on the ImageNet (Russakovsky et al. 2013). CIFAR-ION 100 (Krizhevsky 2009). Places365 (Zhou et al., 2018). and iNaturalist (Van Horn al.) 2018) image classification data sets, whose characteristics are summarized in Table LI The first three have roughly balanced classes, the fourth, iNaturalist, has high class imbalance. We consider three conformal score functions: softmax, one minus the softmax output of the base classifier; APS, a score designed to improve X --conditional coverage; and RAPS, regularized version of APS that often produces smaller sets. Precise definitions of the score functions are provided in Appendix [B.]] we refer also to Romaaoo et al. (2020b); Angelopoulos et al. (202T) for the details and motivation behind APS and RAPS. Throughout, we set a 0.1 for a desired coverage level of 90%.
Table I: Description of data sets. The class balance metric is described precisely in Appendix B.3
Data set
ImageNet CIFAR-100
Places365
iNaturalist
Number of classes 1000
100
365
663*
Class balance
0.79
0.90
0.77
0.12
Example classes
mitten
orchid
beach sushi bar legume catacomb
salamander
triceratops guacamole bicycle
forest
common fern
"hhe number classes the iNaturalist data set can be adjusted by selecting which taxonomy level (e.g.. species, genus, lamily) to use as the class labels. We use the species family as our label and then filter out any classes with < 250 examples in order to have sufficient examples to properly perform evaluation.
Our experiments all follow a common template. First, we fine-tune a pre- treitrd neural network as our base classifier (for details on model architectures, Appendix [.2) a small subset D of the original data, leaving the rest for calibration and validation purposes. We construct calibration sets of varying size by changing the average number of points in each class, denoted aavg. For each navg E {10, 20, 30, 40, 50, 75, 100, 150), we construct a calibration set Deal by sampling Ravg x [ examples without replacement from the remaining data D (where denotes the set complement). We estimate the conformal quantiles for STANDARD, CLASSWISE, and CLUSTERED on Deat- The remaining data (Dee U Peal) is used as the validation set for computing coverage and size metrics. Finally, this process- sancess--plitting Di into random calibration and validation sets-is repeated ten times, and the reported metries are averaged over these repetitions.
Details about clustering. For CLUSTERED, choose 7 E [0, 1] (the fraction of calibration data points used for clustering) and M 2 (the number of clusters) in the following way. First, we define Miin eyy |I the number of examples in the rarest class in the calibration set, and na (1/a) - 1, the minimum sample size needed so that the finite-sample adjusted (1 a -quantile used in conformal prediction is finite (e.g., na 9 when a 0.1). Now define and let K be the number of classes with at least ñ examples. We then set = K/(75 + K) and M = = These choices are motivated by two goals: we want M and y to grow together (to find more clusters, we need more samples for clustering), and we want the proper calibration set to have least 150 points per cluster on average; see Appendix [B.4 for details on how the latter is achieved. Clustering is carried out by running k-means on the quantile-based embeddings, as described in Section 2.2; we use the implementation in sklearn. cluster. KMeans, with the default settings (Pedregosa et al., 2011).
max((min na)
3.2 Evaluation metrics
Denote the validation data set by ((X). ), (recall this is separate from the fine-tuning and calibration data sets) and let JV = {i E [N'] Y = y} be the indices of validation examples with label y. For any given conformal method, we define & = / EiE 1 (Y; C(X))} as the empirical class-conditional coverage of class y. Our main evaluation metrie is the average class coverage gap (CovGap):
CovGap = 100 x
Σ 12, (1 a)]- vE
7

---

This measures how far the class- coasisonniiional coverage is from the desired coverage level of a, in terms of the f distance across all classes (multiplied by 100 to put it on the percentage scale). We also measure the sharpness of the prediction sets by average set size (AvgSize):
N' I(())))
AvgSize
N
For a given class-conditional coverage level (a given CovGap), we want smaller average set size.
3.3 Results
To begin, we investigate the CovGap of the methods on each data set, and display the results in Figure 2 In brief, CLUSTERED achieves the best comparable performance across all settings. Restricting our attention to the baseline methods, note that the CovGap of STANDARD does not change much we vary Ravg; this is as expected, because navg | samples being used to estimate the conformal quantile q. which will be stable regardless of navg. provided | is large. Conversely, the CovGap of CLASSWISH decreases significantly nlay increases, because the classwise conformal quantiles q" are volatile for small Flagg.
For the softmax score (left column of the figure), STANDARD, and the gap widens with navgi further, CLUSTERED outperforms CLASSWISE for small enough values of Ravg (that is, Ravg 75 for ImageNet and Places365, Ravg < 150 for CIFAR- 100, and navg < 50 for iNaturalist). The comparison between CLUSTERED and CLASSWISE is qualitatively similar for APS score (right column of the figure), with the former outperforming the
that CLUSTERED clearly outperforms
ImageNet: softmax
ImageNet: APS
Standard
Classwise
CovGap
Clustered
CIFAR-100: softmax
CIFAR-100: APS
CovGap
Places365: softmax
Places365: APS
CovGap
INaturalist: softmax
INaturalist: APS
CovGap
20
50
75
100
navg
navg
Figure 2: Average class coverage gap for ImageNet, CIFAR-100, Places365, and iNaturalist, for the softmax (left) and APS (right) scores, vary the average number of calibration examples per class. The shaded regions denote + +1.6 times the standard errors (often, the standard errors are too small to be visible).
8

---

latter for small enough values of Ravg- However, the behavior of STANDARD changes notably we move from softmax APS: it becomes comparable CLUSTERED and only slightly worse for large Mavg. Lastly. the results for RAPS (not shown, and deferred to Appendix C.1 are similar to APS but the CovGap is shifted slightly higher.
To examine the potential tradeoff's between class-conditional coverage and average set size, we focus on the Ravg E {10, 20, 50, 75] settings and report CovGap and AvgSize in Table for all data sets and score functions. We see that CLUSTERED achieves the best or near-best CovGap in any experimental combination, and its improvement over the baselines particularly notable in the regime where data is limited, but not extremely limited (Navg = 20 or 50). Meanwhile, AvgSize for STANDARD and CLUSTERED relatively stable across values of Ravg. with the latter being generally slightly larger; AvgSize for CLASSWISE decreases as we increase Maagg but is still quite large relative to STANDARD and CLUSTERED, especially for iNaturalist.
We finish with two more remarks. First, we find CovGap tends to behave quite similarly to the fraction of classes that are drastically undercovered, which we define having a class-conditional coverage at least 10% below the desired level. Results for this metric are given in Appendix C.2 Second, as the case in any conformal method, auxiliary randomization can be applied STANDARD, CLASSWISE, or CLUSTERED in order to achieve a coverage guarantee (marginal, class-conditional, respectively) of exactly
or cluster-conditiona included in Appendix C.3 In terms of CovGap. we find that randomization generally improves CLASSWISE, and does not change STANDARD or CLUSTERED much at all; however, the set sizes from randomized CLASSSISF are still overall too large to be practically useful (moreover, injecting auxiliary randomness is prediction sets not always practically palatable).
a, rather than least a. These results are
Discussion
We summarize our practical takeaways, in an effort towards creating guidelines for answering the question: for given problem setting, what is the best way to produce prediction sets that have good class-conditional coverage but are not too large to be useful?
Extremely low-data regime. When most classes have very few calibration examples (say, less than 10), this is not enough data to run CLUSTERED or CLASSWISE unless a is large, so the only option to run STANDARD. With this method, softmax and RAPS are both good score functions. RAPS tends to yield better class-conditional coverage, while softmax tends to have smaller sets.
Low-data regime. When the average number of examples per class is low but not tiny (say, around 20 to 75), CLUSTERED tends to strike a good balance between variance and granu- larity and often achieves good class-conditional coverage and reasonably-sized prediction sets with either softmax or RAPS. The STANDARD method with RAPS is also competitive towards the lower-data end of this regime.
High-data regime. When the average number of examples per class is large (say, over 75), CLUSTERED conformal with either softmax or RAPS continues to do well, and CLASSWISE with these same scores can also do well if the classes are balanced. In settings with high class imbalance, CLASSWISE is unstable for rare classes and produces excessively large prediction sets, whereas CLUSTERED is more robust due to the data-sharing it employs.
Extremely high-data regime. When the calibration dataset is so large that the rarest class has at least, say, 100 examples, then CLASSWISE with softmax RAPS will be a good choice, regardless of any class imbalance.
The boundaries between these regimes are not universal and are dependent on the data characteristics, and the above guidelines are based only our findings from our experiments. We also note that the precise boundary between the low-data and high-data regimes is dependent on the particular score function that is used: the transition happens around 20-40 examples per class for softmax and 50- 100 for RAPS. This serves as further motivation for CLUSTERED, which performs relatively well in all regimes.
As a possible direction for future work, it might be interesting to generalize our approach to the broader problem of group-conditional coverage with many groups. In the present setting, the groups

---

Table 2: Average class coverage gap and average set size for select values of navg on ImageNet, LLFAR-100, Places365, and iNaturalist. Bold emphasizes the best (within =0.2) class coverage gap each experimental combination. Standard errors are reported in parentheses.
naag 10
Ravg
20
navg
50
Vlag 75
CovGap
AvgSize
CovGap
AvgSize
CovGap
AvgSize
CovGap
AvgSize
Data
Score
Method
TmageNet
STANDARD
5.20
(0.0) (.20)
(0.0)
5.3)
(.9))
(..0)
(0.0)
CLASSWISE
(0.0
(2.0)
(..0)
3.4 23.9
(.1))
(.00
(.1)
CLUSTERED
(.1.
(.1)) (.9
2.7 (0.1)
(.0)
2.6(0..1
(.80
2.7 (0.0)
APS
STANDARD
1..0
(0.9) 2.10..0
25.8 (0.1)
2.50
20.6
26.0
20.7
CLASSWISE
(0.)
(1.9) (0.0)
76.9 (0.8) 3.5 (0.0)
39.7 (0.2)
(0.0)
(0.0
CLUSTERED
(..1)
(1.5
(0.0)
2.30 (0.7)
27.3 (0.4)
RAPS
STANDARD
(.0
(0200..0) 3.0
5.1 (0.0)
3..00.05
5.1 (0.0) (.00
5.1 (0.0)
CLASSWISE
(.1)
(1.99 5.600.0)
34.2
3.4 (0.0)
8.8 (0.3)
(.00
7.1)
CLUSTERED
(0.0)
(17(
(.00
6.6
2.6 (0.0)
6.5 (0.3)
(0.0)
6.8
CIEAR-100 softmax
STANDARD
(0.2) (..0
(0.2)
7.9 (0.1) (0.0)
(.
CLASSWISE
(.6)
(0.6)
(.6)
19.3 (0.5)
3.8 (0.0)
(0.2)
(.1)
10.8 (0.1)
CLUSTERED
(.2(
(.9)
36.00.)
(0.3)
2.9
9.3 (0.3) 2.8 2.00
(02)
APS
STANDARD
(.7
(0.3 3.7 (0.0)
10.8 (0.2)
3.8 (0.0)
(1.0
(.0)
(0.)
CLASSWISE
(..1)
49.4 (0.5) (..)
22.6 (0.5)
3.8 (0.1)
15.0
(.1)
13.7 (0.1)
CLUSTERED
4.0.)..))
(0.5
(..)
12.1 (0.5)
3.1
(0.4)
(0.1)
(2.2
RAPS
STANDARD
4.7(0.1)
(0.3) (..)
8.3 (0.3)
4.8 (0.0)
(.3
(.1)
8.1 (..))
CLASSWISE
(..1)
(0.7) (0.1)
20.7 (0.6)
3.8 (0.1)
(0.2)
(0.1)
12.1 (0.1)
CLUSTERED
(.1.)
9.5 (0.5)
(..1)
8.7 (0.5)
3.7 (0.1)
9.5 (0.3)
(..1
(.1)
Places365
softmax
STANDARD
4,5 (0.0)
6.9
4.5
6.9
4.6 (0.0)
(0.0)
4.6 (0.0)
(.90
CLASSWISE
7.6.
(1.75
5..0)
18.0 (0.2)
(.50)
10.1 (0.1)
(..0)
(.3)
CLUSTERED
(.1)
(..)
39.0..)
3.00
7.8
(.1))
(.1)
APS
STANDARD
(.,0)
(0.1) (.0)
10.9 (0.1) (..))
10.8 (0.1) 3.3 (0.0) 10. (0.1)
CLASSWISE
(.1)
(1.75 (0.1
23.5 (0.3)
(0.0)
(0.1) (0.0
13,4 (0.1)
CLUSTERED
10.9 (.5)
(.0)
10.9 (0.2)
2.6 (0.0)
11.8 (0.1) 2.7 (.1) (1.6
RAPS
STANDARD
(0.0)
7.9 (0.0) (..)
(0.0)
3.8 (0.0)
7.9 (0.0) (..0)
(.9)
CLASSWISE
(1.79 (..)
(.5
21.3 (0.3)
3.6 (0.0)
(0.1) (.00
(0.1)
CLUSTERED
(.9(0.1)
(..) (.4)
8.2 (0.2)
3.0
8.8 (0.1)
(0.0)
(.0)
iNaturalist
softmax
STANDARD
(.01
3.1 (0.0)
(..)
3.1 (0.0)
(0.1)
3.2
(..0)
(.2)
CLASSWISE
8.7
(1.8
(0.0)
(1.40
(0.0)
(2.2)
4.8 (0.0)
(1.3
CLUSTERED
(.9)).2)
6,4 (.1)
(0.1)
5,7 (0.1)
(00))
3,8 (.1)
APS
STANDARD
(.1)
(0.))
4.2 (0.1)
844 (0.1)
4.1 (0.0)
8..0
(.20
(..)
CLASSWISE
(0.0)
(1.8
(..0)
(1.44
5.7 (0.0)
(2.2)
(0.0) (1.7
CLUSTERED
(.1)
(0.)
4.1 (0.1)
8.3 (0.1)
3,9 (0.0)
8.5 (0.1) (0.0)
(.1)
RAPS
STANDARD
5.000.0
(0.0)
5.000.0)
(,2
CLASSWISE
(.7)).0)
473.8
(.80
369.2 (1.5)
5,8 (0.0)
155.3 (2.3) (.00
63.1
CLUSTERED
(.0
(.0)
(...
(0.0)
(..)
(0.) (0.1)
(.1)
defined by class labels, but clustering methodology could also be applied to other group structures (e.g., defined by the input features or components of mixture distribution).
Acknowledgments and Disclosure of Funding
We thank Margaux Zaffran and Long Nguyen for helpful suggestions that improved our paper. This work was supported by the National Science Foundation (NSF) Graduate Research Fellowship Program under grant no. 2146752, the European Research Council (ERC) Synergy Grant Program, the Office of Naval Research (ONR) the Mathematical Data Science Program, and the ONR Multi- University Research Initiative (MURI) Program under grant no. N00014-20-1-2787.
References
Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. Foundations and Trends in Machine Learning, 16(4): 494-591, 2023.
Anastasios N. Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I. Jordan. Uncertainty sets for image classifiers using conformal prediction. In Proceedings of the International Conference on Learning Representations, 2021.
10

---

Anastasios N. Angelopoulos, Amit Pal Kohli, Stephen Bates, Michael Jordan, Jitendra Malik, Thayer Alshaabi, Srigokul Upadhyayula, and Yaniv Romano. maaeett-immage regression with distribution- free uncertainty quantification and applications in imaging. In International Conference on Machine Learning, 2022.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-fiee conditional predictive inference. Information and Inference, 10(2):455-44) 482, 2021.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong semi-supervised learners. In Advances in Neural Information Processing Systems, 2020.
Isaac Gibbs, John J. Cherian, and Emmanuel J. Candès. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305. /2616, 2023.
Leying Guan. Localized conformal prediction: A generalized inference framework for conformal prediction. Biometrika, 110(():33 50, 2023.
Leying Guan and Robert Tibshirani. Prediction and outlier detection in classification problems. Journal of the Royal Statistical Society: Series B, 84(2):524, 2022.
Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman. Cautious deep learning, arXiv preprint arXiv:1805. ww... 09460, 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series B, 76(1):71-96, 2014.
Jing Lei, Max G'Sell, 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
Tuve Löfström, Henrik Boström, Henrik Linusson, and Ulf Johansson. Bias reduction through conditional conformal prediction. Intelligent Data Analysis, 1965):13551135, 2015.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning. 2002.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Veto,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, higg-peeformance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg. Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay, Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12(85):2825- 2830, 2011.
Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems, 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2(2), 2020a.
Yaniv Romano, Mattco Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems, 2020b.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet large scale visual recognition challenge. International Journal of Computer Vision 115:21 1-252, 2015.

---

Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-2355 234, 2019.
Fan Shi, Cheng Soon Ong, and Christopher Leckie. Applications class-conditional conformal predictor in multi-class classification. In International Conference Machine Learning and Applications, 2013.
Jiangming Sun, Lars Carlsson, Ernst Ahlberg, Ulf Norinder, Ola Engkvist, and Hongming Chen. Ap- plying Mondrian cross-conformal prediction estimate prediction confidence large imbalanced bioactivity data sets. Journal of Chemical Information and Modeling, 57(7):1591-1598, 2017.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pictro Perona, and Serge Belongie. The iNaturalist species classification and detection dataset. In IEEE Conference on Computer Vision and Pattern Recognition, 2018.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian Conference on Machine Learning, 2012.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, 2005.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 40(6): 2018.
12

---

A Proofs
Proof of Proposition For each m (I....,,, M), denote by G)() the distribution of the score s(X, Y) conditioned on Y being in cluster Consider randomly sampled test example (Xtests Yrest) with a label in cluster ma; the test score Stest = s ((X test, Yeest) then follows distribution G(m), Next consider (8i)))Z.()) the scores for examples in the proper calibration set with labels in cluster mi, these also follow distribution G Furthermore, Stest and the elements of {&s hezz(() all mutually independent, so the result follows by the standard coverage guarantec for conformal prediction with exchangeable scores (c.g., see Vovk et al. (2005) or Lei et al. (2018)).
Proof of Proposition 2
This is a direct result of exchangeability and Proposition I
Let S = s(X, Y) denote the score of randomly sampled example (X, F. Fix an m {1..... ... Define yrmm) {u } h(y) m) as the set of classes that h assigns to cluster m. Without a loss of generality, we treat both i and ((m) as fixed for the remainder of this proof. This can done by conditioning on both the clustering and proper calibration sets, leaving only the randomness in the test point (X,Y) ~ F, and then integrating over the clustering and proper calibration sets in the end.
Proof of Proposition
Let G(m) denote the distribution of S conditional on Y E {)(m), and let 5(m) ~ G(m), Similarly, let G" denote the distribution of conditional Y = y, and let 5 CV Since assume that the KS distance between the score distribution for every pair of classes in cluster m is bounded by and G)m) is a mixture of these distributions (that is, G(m) Eyex(m) Ty. GV for some fixed probability weights T. y E )omm),, it follows by the triangle inequality that
DKs(S", ((()) Se,
for all y E y(m).
By definition of KS distance, this implies
IPSS s ((m) Y = v) - P(S S ((m) Y wim))) Sc.
Since the CL CLUSTERED procedure includes the true label Y from the prediction set C when S S ((m). these probabilities can be rewritten terms of coverage events:
PPY E C(X)) YY= = - P(Y e c(() Y E y(m)) Sc.
Combining the result from Proposition gives the desired conclusion.
B Experiment details
B.1 Score functions
We perform experiments using three score functions:
softmax: The softmax-based conformal score at an input æ and a label y is defined as
8softmax (z. y) = - (x)
where fy(x) is entry y of the softmax vector output by the classifier f at input x.
APS: The Adaptive Prediction Sets (APS) score of Romano et al. (2020b) is designed to improve X X-conditional coverage as compared to the more traditional softmax score. This score is computed at an input x and label as follows. Let
fay(2) S (12)()) S ... S (1
denote the sorted values the base classifier softmax outputs fz) y V. Let kv be the index in the sorted order that corresponds to class y, that is, f(k. (w)) fx). The APS score is then defined
R (1))-
(A =
Σ
(o( + So.
1=1
13

---

RAPS: The regularized APS (RAPS) score of Angelopoulos et al. (2021) is modification of the APS score that adds regularization term designed to reduce the prediction set sizes (which can often be very large with APS). The RAPS score is defined as
SRAPS (æ, y) SAPs(x, y) + max (0, ((kx kveg)),
where kr (y) is as defined above, and À and kreg are user-chosen parameters. In all of our experiments, we use À = 0.01 and Kireg 5, which Angelopoulos al. (202T) found to work well for ImageNet.
B.2
Model training
An important consideration when we fine-tune and calibrate our models that we must reserve sufficient data evaluate the class-conditional coverage of the conformal methods. This means aim to exclude at least 250 examples per class from the fine-tuning and calibration sets so that we can then use this data for validation (applying the conformal methods and computing coverage and set size metrics).
For all data sets except ImageNet, we use ResNet-50 model as our base classifier. We initialize to the IMAGENET1K_ V2 pre-trained weights from PyTorch (Paszke et al., 2019), and then fine-tune all parameters by training the data set at hand. For ImageNet, we must do something different, as explained below.
ImageNet. Setting up this data set for our experiments is a bit tricky because we need sufficient data for performing validation, but we also need this data be separate from the fine-tuning and calibration sets. The ImageNet validation set only contains 50 examples per class, which is not enough for our setting. The ImageNet training set is much larger, with roughly 1000 examples per class, but if we want to use this data for validation, then we cannot use the ResNet-50 initialized to the IMAGENETIK
pre-trained weights, as these weights were obtained by training on the whole ImageNet training set. We therefore instead use SimCLR-v2 model (Chen et al.) 2020). which was trained on the ImageNet training set without labels, to extract feature vectors of length 6144 for all images in the ImageNet training set. We then use 10% of these feature vectors for training linear head (a single fully connected neural network layer). After training for 10 epochs, the model achieves validation accuracy of 78%. We then apply the linear head the remaining 90% of the feature vectors to obtain softmax scores for the calibration set.
This data set has 600 images per class (500 from the training set and 100 from the validation set). We combine the data and then randomly sample 50% for fine-tuning, and we use the remaining data for calibrating and validating our procedures. After training for 30 epochs, the validation accuracy is 60%.
CIFAR-100.
Places365. This data set contains more than 10 million images of 365 classes, where each class has 5000 30000 examples. We randomly sample 90% of the data for fine-tuning, and we the remaining data for calibrating and validating our procedures. After training for one epoch, the validation accuracy is 52%.
iNaturalist. This data set has class labels of varying specificity, For example, at the species level, there are 6414 classes with 300 examples each (290 training examples and 10 validation examples) and a total of 10000 classes with at least 150 examples. We instead work at the family level, which groups the species into 1103 classes. We randomly sample 50% of the data for fine-tuning, and we use the remaining for calibrating and validating our procedures. After training for one epoch, the validation accuracy is 69%.
However, due to high class imbalance and sampling randomness, some classes have insufficient validation samples, so we filter out classes with fewer than 250 validation examples, which leaves us with 633 classes. The entries of the softmax vectors that correspond rare classes are removed and the vector is renormalized to sum one.
14

---

B.3 Measuring class balance in Table
The class balance metric in Table | is defined as the number of examples in the rarest 5% classes divided by the expected number of examples if the class distribution were perfectly uniform. This metric bounded between 0 and 1, with lower values denoting more class imbalance. We compute this metric using Dine-
B.4 Choosing clustering parameters
To choose y [0, 1] and M 2 1 for CLUSTERED, described briefly in Section 3.1 employ two intuitive heuristics. We restate these heuristics in more detail here.
First, to distinguish between more clusters (or distributions), we need more samples from each distribution. As a rough guess, to distinguish between two distributions, we want at least four samples per distribution; to distinguish between five distributions, we want at least ten samples per distribution. In other words, we want the number of clustering examples per class be least twice the number of clusters. This heuristic can expressed as
nn 2 2M,
(3)
where yn is the expected number of clustering examples for the rarest class that is not assigned to the null cluster.
Second, we want enough data for computing the conformal quantiles for each cluster. Specifically, we seek at least 150 examples per cluster on average. This heuristic can be expressed as
M 2 150,
44)
where K/M is the average number of classes per cluster and (1-7)ñ is the expected number of proper calibration examples for the rarest class assigned to the null cluster.
Changing the inequalities of
33 and 4 into equalities and solving for and M yields
M ?
K
and
K + 75
Varying the clustering parameters. As sensitivity analysis, we examine the performance of CLUSTERED across wide range of values for the tuning parameters 7 and M. As the heatmaps in Figure 3 confirm, the performance of CLUSTERED not particularly sensitive to the values of these parameters. When Ravg = 10, the heuristic chooses 7 0.89 and M = 4, meanwhile, when navg = 50, the heuristic chooses E [0.88, 0.92] and M E [7, 12] (since the calibration data set is randomly sampled, and 7 and M are chosen based on the calibration data set, there is randomness in the chosen values). However, there are large areas surrounding these values that would yield similar performance. We observe that the heuristics do not always choose the parameter values that yield the lowest CovGap. The heatmaps reveal that the optimal parameter values are dependent not only on data set characteristics, but also on the score function. Future work could be done to extract further performance improvements by determining better method for choosing ? and M.
C Additional experimental results
We present additional experimental results in this section. As in the main text, the shaded regions in plots denote 1196 times the standard errors.
C.1 RAPS CovGap results
Figure shows the CovGap all data sets when RAPS score function.
C.2 Additional metrics
Average set size. To supplement Table from the main text, which reports AvgSize for select values of navg. Figure plots AvgSize for all values of navg that use in our experimental setup. Note
15

---

Imageleet
Imagebatt Gay
Fraction for clusew O
02
5.2
5.2
5.2
2.6
2.6
2.6
5.3
5.3
5.
5.3
5.
5.3
5.3
5.3
5.8
5.3
2.6
2.5
26
26
2.5
2.6
2.6
2.5
2.5
2.5
2
3
3
3
9.2
5.2
5.2
52
5.3
5.3
5.3
5.3
5.2
2.6
23
2.7
2.2
2.7
2.7
2.7
3.1
3.1
2.1
3.1
3.1
3.1
3.1
03 06 05
5.2
52
5/2
5.3
2.7
2.8
3.1
3.1
3.1
3.2
5.1
5.3
2.7
2.8
3.1
3.2
3.2
3.3
5.1
5.1
51
5
5.2
5.6
2.8
2.8
2.8
2.8
2.8
2.9
2.9
3.2
3.6
3.1
3.1
3.1
3.1
3.1
3.2
3.2
3.3
3.4
3.8
4.9
4.8
4.5
4.8
4.9
4.9
4.8
5.1
5.7
2.8
2.7
2.6
2.4
2.9
3
3.5
3.4
3.1
3.1
3.1
3.1
3.1
3.2
3.3
3.4
3.5
4.2
4.9
4.8
4.5
4M9
5.3
54
2.8
3.2
3.8
5.1
3.2
3.2
3.3
3.5
3.6
3.6
ImageNett sottmax,
ImageNet: APS,
Imagelet: RAPS,
Fraztion for clutoring [v]
0.3 02
2.5
2.5
25
4.3
3.9
3.8
3.8
3.8
3.7
3.7
3.7
3.6
2.5
2.4
24
244
2.4
2.4
2.4
2.4
24
2.4
29
2.9
28
288
2.7
2.7
277
2.7
4.2
3.8
3.7
3.6
3.5
3.5
3.5
3.4
3.4
3.4
2.5
2
24
24
2.5
2.3
2.3
2.3
2.4
2.4
24
2.5
2.7
2.7
2.7
2.7
2.6
2.5
2.6
2.7
4.1
5.7
3.5
3.4
3.3
3.3
3.2
3.2
2.5
23
2.1
2.5
2.3
2.3
2.3
2.3
2.8
2.7
2.7
2.6
2.6
2.5
2.5
0. 07
3.3
3.2
3.1
3.1
2.4
23
22
2.3
2.6
2.5
2.5
2.5
2.5
3.3
3.2
3.2
3.1
3.1
3
3.2
2.4
2.3
22
22
2.2
22
2.2
2.
2.3
2.6
2.7
2.6
2.6
2.5
2.5
2.5
2.5
2.5
2.5
2.8
1.5
1.5
1.2
3.2
1.1
9.1
1.1
3.1
1.6
2.4
2.1
2.2
2.
2.2
7.2
2.1
2.1
2.4
2.7
2.6
2.5
2.5
2.5
2.5
2.5
2.5
2.7
2
clusters
(M)
(M)
Figure 3: Average class coverage gap on ImageNet for navg E {10, 50}. using the softmax, APS, and RAPS scores, as we vary the clustering parameters, Each entry is averaged across 10 random splits of the data into calibration and validation sets.
ImageNet: RAPS
CIFAR-100: RAPS
Classwise
Clustered
CovGap
Places365: RAPS
iNaturalist: RAPS
CovGap
20
30
50
75
100
150
10
20
150
nevg
nevg
Figure 4: Average class coverage gap for ImageNet, CIFAR-100, Places365, and iNaturalist, using the RAPS score, as we vary the average number of calibration examples per class.
that RAPS sharply reduces AvgSize relative to APS on ImageNet and also induces a slight reduction for the other three data sets. This asymmetric reduction is likely due to the fact that the RAPS hyperparameters, which control the strength the set size regularization, were tuned on ImageNet. The set sizes of RAPS other data sets could likely be improved by tuning the hyperparameters for each data set.
Fraction undercovered. In various practical applications, we want to limit the number of classes that are severely undercovered, which we define as having a class-conditional coverage more than 10% below the desired coverage level. We define the fraction of undercovered classes (FracUnderCon)
16

---

ImageNet: softmax
ImageNet: APS
ImageNet: RAPS
40
Standard
30
Classwise
AvgSize
Clustered
20
CIFAR-100: softmax
CIFAR-100: APS
CIFAR-100: RAPS
40
AvgSize
20
10
Places365: softmax
Places365: APS
Places365: RAPS
40
30
AvgSize
20
10
INaturalist: softmax
INaturalist: APS
INaturalist: RAPS
40
30
AvgSize
10
10 20 30 4050
75 nagg
100
150
10
20
30
4050
75 nlvg
100
150
10
20 30 4050
75 100
150
novg
Figure 5: Average set size for ImageNet, CIFAR-100, Places365, and iNaturalist, for the softmax, APS, and RAPS scores, as we vary the average number of calibration examples per class.
metric as:
| Σ y=1
1 y
FracUnderCov
(āg S 0.1},
recalling that & is the empirical class-conditional coverage for class y. Figure 0 plots FracUnderCov for all experimental settings. Comparing to the CovGap plots in Figure 2 and Figure we see that the trends in Underrderoov generally mirror the trends in CovGap. However, FracUnderCh is much noisier metric, as evidenced by the large error bars. Another difference is that FracUnderCov metric is unable penalize uninformatively large set sizes. This is best seen the performance of CLASSWIS on iNaturalist: for every score function, CLASSWISE has very low FracUnderCov, but this is achieved by producing extremely large prediction sets, shown in the bottom row of Figure 5 Meanwhile, CovGap is somewhat able to penalize this kind of behavior since unnecessarily large set sizes often lead overeoverage. and CovGap penalizes overcoverage.
C.3 Auxiliary randomization
The conformal methods in the main paper generate deterministic prediction sets, running the method on the same input will always produce the same prediction set. These prediction sets are designed to achieve at least 1 marginal, class-conditional, cluster-conditional coverage. In
17

---

ImageNet: softmax
ImageNet: APS
ImageNet: RAPS
Standard
FracUnderCov
Classwise
0.06
Clustered
0.04
0.02
0.00
CIFAR-100: softmax
CIFAR-100: APS
CIFAR-100: RAPS
0.10
FracUnderCov
0.06
0.04
0.02
0.00
Places365: softmax
Places365: APS
Places365: RAPS
0.08
FracUnderCov
0.06
0.04
0.02
0.00
iNaturalist: softmax
iNaturalist: APS
iNaturalist: RAPS
0.20
FracUnderCov
0.15
0.10
0.05
0.00
10
20
4050
75 100 flvg
150
10
30 4050
75 100 flag
150
20 30 4050
75 100
150
flaug
Figure 6: Fraction of severely undercovered classes for ImageNet, CIFAR-100, Places365, and iNaturalist, using the softmax, APS, and RAPS scores, as we vary the average number of calibration examples per class.
most practical situations, it is arguably undesirable sets (say, if you are patient, you would not want your doctor to tell you that your diagnoses change depending random seed). However, if one is willing accept randomized prediction sets, then the conformal methods described in the main text can be modified to achieve exact a coverage.
non-detemministic randomized prediction
Randomizing achieve exact coverage. used in the main paper uses
Recall that the unrandomized STANDARD method
[N 1) a)l
Quantile
N {s:
which yields coverage guarantee of
[(N + 1)(1aa]] 21-a,
IP C(Xtest)
) Yrest = y)
N+1
under the assumption that the scores are distinct almost surely. The equality above holds because the event that Yrest is included in C(Xtest) is equivalent to the event that s(Xtest Yustt is one of the [[N + (1 a smallest scores the set containing the calibration points and the test point, and, by exchangeability, this occurs with probability exactly [[N +1(11-1 ()][N) 1). By similar
18

---

reasoning, if we instead use
[(N + 1)(1 - a)] -
q -
Quantile
N
as our conformal quantile (note the added -1 in the numerator), then we would have
test E ((eee)) Yust = y) [(N 1)(1 - ([[1-a]]-1 a..
N ++1
To summarize, using ④ results at least a coverage, and using ① results less than a coverage. Thus, to achieve exact 1 coverage, can randomize between using & and q. Let
5 [(N + 1) a)] (1 (1-a)
N
be the amount by which the coverage using á overshoots the desired coverage level and let
a) [(N + 1)(1 a)]
be the amount by which the coverage using ğ undershoots the desired coverage level. Then, if define the Bernoulli random variable
B Bern
b+c)
independent of everything else that is random, and set
grand
Bq + (1 B)g
then the prediction sets created using grand will have exact 1 - a marginal coverage. The same idea translates CLASSWISE and CLUSTERED methods (where randomize q" and @(m). respectively).
Figures 7 and display the CovGap, AvgSize, and FracUnderCov for randomized versions of the conformal methods. Comparing against earlier plots, we observe that the performance of unrandomized and randomized STANDARD and CLUSTERED are essentially identical in terms of all three metrics. However, we cam see that randomized CLASSSISE exhibits large improvement relative to unrandomized CLASSWISE in terms of CovGap and AvgSize. That said, the previously- given qualitative conclusions do not change, and the set sizes of randomized CLASSWISE are still too large to practically useful.
19

---

ImageNet: softmax
ImageNet: Net: APS
ImageNet: RAPS
zod Stan
candomized Classwise
CovGap
Deizo Clustered
(Original) Classwise
CIFAR-100: softmax
CIFAR-100: APS
CIFAR-100: RAPS
CovGap
Places365: softmax
Places365: APS
Places365: RAPS
CovGap
INaturalist: softmax
iNaturalist: APS
iNaturalist: RAPS
CovGap
10 20 30 4050
100 Devg
150 10
20 30
4050
100 Gavg
150
20 30 4050
75 100
150
Revy
Figure 7: Average class coverage gap for randomized methods on ImageNet, 100, Places365, and iNaturalist, for the softmax, APS, and RAPS scores, as we vary the average number of calibration examples per class. The unrandomized original CLASSWISE method is also plotted for comparison purposes.
20

---

ImageNet: softmax
ImageNet: APS
ImageNet: RAPS
40
Randomized Standard
30
Randomized Classwise
AvgSize
Randomized Clustered
(Original) Classwis se
20
10
CIFAR-100: softmax
CIFAR-100: APS
CIFAR-100: RAPS
40
30
AvgSize
20
10
Places365: softmax
Places365: APS
Places365: RAPS
40
30
AvgSize
20
10
0
iNaturalist: softmax
iNaturalist: APS
iNaturalist: RAPS
40
30
AvgSize
20
10
10.
20
4050
75 100 navg
150
10
20
30
4050
75 100 Davg
150
10
20 30
4050
75 100 navg
150
Figure 8: Average set size for randomized methods on ImageNet. CIFAR- Places365, and iNaturalist, for the softmax, APS, and RAPS scores, as we vary the average number of calibration examples per class. The unrandomized original CLASSWISE method is also plotted for comparison purposes.
21

---

ImageNet: softmax
ImageNet: APS
ImageNet: RAPS
0.08
Randomized Standard
FracUnderCov
Randomized Clasovise
0.06
Randomized Clustered
(Original) Classwise
0.04
0.02
0.00
CIFAR-100: softmax
CIFAR-100: APS
CIFAR-100: RAPS
0.10
FracUnderCov
0.08
0.06
0.04
0.02
0.00
Places365: softmax
Places365: APS
Places365: RAPS
0.08
FracUnderCov
0.06
0.04
0.02
0.00
iNaturalist: softmax
iNaturalist: APS
iNaturalist: RAPS
0.20
FracUnderCov
0.15
0.10
0.05
0.00
10
20
4050
75 100 Bav
150 10
30 4050
75 100 navg
150 20 30 4050
75 100
150
nav
Figure 9: Fraction of severely undercovered classes for randomized methods ImageNet, CIFAR- 100, Pla- ces365, and iNaturalist, for the softmax, APS, and RAPS scores, as we vary the average number of calibration examples per class. The unrandomized original CLASSWISE method is also plotted for comparison purposes.
22


Reviews:
[{"review_id": "Vzgh2vLgXt", "reviewer": "Reviewer_xNf7", "summary": "The paper describes a method for conformal prediction specially addressed for the case where there is few avaliable data in some of the classes. To address this problem, the proposed method performs a clustering of classes with similar score distributions with the goal of increasing the data used to select the set of classes for a given sample. Experimental results on standard image datasets with a large number of classes with different settings of data availability are reported comparing the proposed method with other standard approaches for conformal prediction.", "questions": "See above, specially questions regarding performance on specific classes with few data. \n\n-----------------------------\n\nI have read the rebuttal and it has clarified most of the questions I had about the paper, specially those related with classes with few samples and technical issues. After reading all comments and discussion, I increase my rating to weak accept.", "limitations": "The authors discuss on the limitations of the method and no potential negative impacts are foreseen", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses the problem of conformal prediction with a large number of classes and with few data per classe, and proposes a new method specifically designed for this setting. The method is well motivated and formalized.\n2. Extensive experiments are performed on different datasets and different settings of data availability, comparing the proposed method with standard and classwise approaches. Results show that the proposed method achieves a better average coverage. \n3. The paper include useful practical recommendations about when to use each of the conformal prediction approaches.", "weaknesses": "1. One of the motivating points of the paper is that, in some cases average coverage can be good enough, but specific coverage for some underepresented classes can be very low. Results show that average coverage improves with the proposed method, but there is not any discussion or results about the specific coverage for particular classes, specially those with few data. Therefore, we cannot validate the original motivation of the paper. Furthermore, as fas as I understand, classes with few data will most probably assigned to the null cluster and then, those classes will follow the standard approach, and there will be no difference between the proposed method and the standard one for these classes. \n2. Although the average coverage improves, the AvgSize measure is, in general worse than with the standard method. \n3. Some technical details could be better explained or motivated.\n- In section 2.1, what do you exactly mean by \"scores for all classes in a given cluster are exchangeable? That score distributions are equal?\n- The k-means clustering algorithm is very dependent on the selected number of clusters. Although there is a explanation on how the number of cluster is defined, wouldn't it be better to use an adaptive clustering algorithm where the number of clusters can be automatically determined?\n- The representation used to perform the clustering is based on a few discrete number of quantile scores. Wouldn't it be better to use a larger and more dense number of quantile scores that could give a better approximation of the distribution of score values?\n\n3. Related work is very oriented to describe on which types of data conformal prediction has been applied. I miss a more technical discussion describing the different techniques and methods used in the existing works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and, in particular, for highlighting our practical recommendations, which we hope will provide useful guidance for practitioners. \n\nIn response to weaknesses: \n\n>\tW1: Classes with few examples\n\nSee our common response, which describes additional experiments we ran to look at potential undercoverage. It is true that classes with very few examples (say, 5) will end up in the null cluster. In our practical recommendation in the Discussion, we highlight that in regimes where we expect many classes to have very few examples, one should run standard conformal. However, if most classes have few, but not very few, examples (say, 20), clustered conformal will provide a boost in performance. \n\n>\tW2: AvgSize of clustered conformal is larger than standard conformal  \n\nThis is true — there is no free lunch! To get class-conditional coverage, clustered has to output sets that are slightly larger than standard conformal. Standard conformal is not guaranteed to yield class-conditional coverage and can have bad class-conditional coverage in some settings. In many cases, the trade-off of slightly larger sets in return for class-conditional coverage is worth it. Compared to the classwise conformal procedure, we get similar class-conditional coverage with much smaller sets.\n\n>\tW3: Adaptive clustering algorithm \n\nWe agree that an adaptive clustering algorithm seems nice in theory. However, implementing this in our setting is trickier than it might initially appear. There are several methods designed for choosing $k$ in k-means (e.g., elbow, gap statistic), and we experimented with many of them. However, none of them worked well in our particular clustering setting. The problem of clustering distributions is relatively unexplored and would be interesting to dive into, but it was not the focus of our work. Combining this with the fact that our method is robust to the choice of $k$ in the k-means procedure (see our sensitivity analysis in Appendix B.3) made it reasonable to just use the intuitive procedure for choosing $k$ that we described in the paper. \n\n>\tW4: Representation used for clustering\n\nYes, there is flexibility in choosing the representation upon which to perform clustering. We chose one that makes intuitive sense and stuck with it, since we found it to work well in practice. Increasing the number of quantiles used to create the representation is not necessarily better: for example, if there are only 10 examples, the 85% quantile and the 90% quantile will correspond to the same example. \n\n>\tW5: Related work \n\nThanks for this suggestion; we have expanded our related work. We originally focused on datasets in previous work since the only existing techniques/methods are STANDARD and CLASSWISE, which we described earlier on in the Introduction. CLASSWISE is a special case of Mondrian CP (Line 85), which we now present in more detail. For some related problems (such as creating prediction sets with group-conditional coverage), we have also added some additional discussion of techniques used in previous works.\n"}, {"review_id": "UQBCqda3Wq", "reviewer": "Reviewer_aaQt", "summary": "The paper studies how to achieve class-conditional coverage (in the setting of conformal prediction) for multiclass classification problems, in particular for tasks with large label spaces. Previous techniques either provide no class-wise guarantees or tend to produce conservative prediction sets due to lack of data.\n\nThe key insight here is that non-conformity scores from different classes may be grouped together if their class-conditional score distributions are similar, since the $(1- \\alpha)$-quantile value to achieve desired coverage would be the same across these classes. Essentially, we can extrapolate about a class with low amounts of data by simply using data from other classes with a similar score distribution. \n\nThis work is particularly applicable in settings where there is a large number of classes (and thus higher likelihood of small amount of data for some of these classes) and / or high class imbalance. \n", "questions": "•\tThough equation (2) implies equation (1), in general we may not achieve the guarantee of (2) as you have mentioned in Section 2.2, so the CLUSTERED algorithm may not necessarily achieve marginal coverage. Do you see this method as more of on a continuum with STANDARD and CLASSWISE, with each of them having situations where they work better, especially since CLUSTERED guarantees are not as consistent as the others? \n\n•\tClarification about the usage of Algorithm CLASSWISE: when generating a prediction set for a new input, to choose a conformal predictor to use, we need to know the true label, which we do not. So which of the K predictors is chosen? Do we run all of them and choose the most conservative quantile value? \n", "limitations": "•\tThe theoretical guarantee on class-conditional coverage depends on the value of $\\epsilon$ defined in Proposition 3 which can vary based on the actual score distributions across classes, the value of $m$ used and the clustering algorithm used, so there may be concern on achieving close to $(1 - \\alpha)$-coverage performance in general, although in all experiments, the method seems to work quite well. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "•\tFirstly, I found this paper particularly well-written and structured; was written to make the discussion quite intuitive and easy to follow. \n\n•\tMethod is a natural solution in settings where there is an underlying structure / similarity in how the base model performs on certain groups of classes. \n\n•\tStrikes a balance between getting meaningful prediction sets (not overly conservative) and getting low variance in class-wise coverage rates.\n\n•\tEmpirically, the proposed method performs quite well, performing on par or better than the baseline methods for the studied metrics. \n", "weaknesses": "•\tThis performance of CLUSTERED seems to be essentially a data and model-driven problem. If there are different classes with similar score distribution, it improves performance.  Is there a possibility of artificially inducing clusters, if such a similarity doesn’t exist? \n\n•\tThe CovGap metric seems to penalize both overcoverage and undercoverage without distinguishing between the two. It would be nice to see how much each of the methods overcover and undercover (classwise) separately. For example, in Table 2 I would expect that the high CovGap values for CLASSWISE is mostly due to overcoverage, while for STANDARD it is probably undercovering and overcovering in equal measure, but this metric hides that potential distinction. \n\n•\tMinor typo: use of $h$ in line 146, equation after line 146 and in Proposition 1 should be $\\hat{h}$. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your nice summary of the paper! \n\nIn response to weaknesses:\n\n>\tW1: Inducing artificial clusters\n\nOur method does, in a sense, induce artificial clusters, but we do not view this as a weakness. In the original datasets, there is no true clustering. We simply partition the classes in the way that the data suggests in order to yield good class-conditional coverage.  \n\n>\tW2: CovGap\n\nWe thank the reader for this point. We have conducted a substantial additional experiment to investigate this. Please see the file attached to the common response for plots that separately show undercoverage and overcoverage. \n\n\nIn response to questions: \n\n>\tQ1: Marginal coverage\n\nClustered conformal may not always yield perfect class-conditional coverage, but it always yields cluster-conditional coverage (see Proposition 1), which is a stronger guarantee than marginal coverage. Whether cluster-conditional coverage implies class-conditional coverage is dependent on the quality of the clustering (see Proposition 3). \n\nTo better clarify this point, we will update the exposition surrounding Proposition 1 and 3 in the text. We thank the reviewer for this point.\n\n>\tQ2: Classwise conformal \n\nFor a more technical explanation of how the conformal sets are formed by the CLASSWISE procedure, please see Lines 111-112. In words: We first compute a separate conformal quantile for each class $y$. Then, given an input $X$, we compute the conformal prediction set as follows: for each possible label $y$, we compute the conformal score $s(X,y)$ and then include $y$ in the prediction set if $s(X,y)$ is less than the conformal quantile for class $y$.\n"}, {"review_id": "z7Bmip8Kqc", "reviewer": "Reviewer_omUB", "summary": "This article studies the clustered conformal prediction, mitigating the issues in the standard conformal and class-wise conformal, by grouping some similar classes together. ", "questions": "* The strikingly large prediction set of class-wise conformal is due to the threshold set as in Line 115, but why don’t we set it as the largest score in the calibration data instead of the infinity? There might be a loss of coverage, but it is unclear how large it is in these empirical results, and whether or not this kind of loss is tolerable, especially when the other two competing methods may also lose the coverage for the individual class.\n\n* Line 149: It seems the idea of finding the threshold for the null cluster is the same as that for the marginal coverage. Now that you criticized the standard conformal’s overall coverage ability, why not merge some clusters until you get the desired sample size instead of merging all clusters in the proposed method?\n\n* Line 176: The authors also notice the issue of class imbalance may affect the clustering, then can we up-sample the minor classes to mitigate the issue mentioned in Line 115 and then follow the class-conditional conformal instead of the proposed clustered conformal? Or what if you do the clustering on the original dataset to obtain the desired sample size, and then use class-conditional conformal?\n", "limitations": "Please see the above two parts.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The authors proposed clustered conformal prediction to strike the balance between marginal coverage and class-wise coverage for the setting of many classes with limited data per class. \n* When calibration data is limited, the empirical results show that the proposed method achieves a relatively small coverage gap according to the designed metric (CovGap), effectively balancing marginal coverage and class-wise coverage.", "weaknesses": "* The authors need to specify the low-data scenario (at least on the calibration data from the perspective of the experiments) in the title, otherwise, there are other works related to many classes. Moreover, from the main manuscript, it looks more like cluster-conditional conformal instead of class-conditional conformal in the title.\n\n* The setting and the numerical study somehow contradict each other. Now that the authors used deep learning to train the score function, it does not make sense that there is a limited calibration dataset in practice. If that, why don’t allocate some from the training data? \n\n* There is no sensitivity analysis on the clustering procedure. What if different schemes are used for choosing $M$?  How does $M$ (e.g., $M < K$ or $M > K$) affect the results? \n\n* Using CovGap as a metric might obscure the issue of coverage for each class from methods, e.g., the standard and the proposed method. The results are difficult to say without explicitly showing the coverage for each class. For example, class-wise conformal has high coverage than $1-\\alpha$ with the larger gap, but the proposed method could return the coverage below $1-\\alpha$ with a smaller gap.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and questions. \n\nIn response to weaknesses:\n\n>\tW1: “Low-data scenario”;  cluster-conditional conformal vs. class-conditional conformal\n\nWe are not aware of other works that focus on creating prediction sets that target class-conditional coverage in the many-class regime. If you are aware of work in this setting, please share! As mentioned in our Related Work section, existing work that evaluates class-conditional coverage focuses on classification problems with at most 10 classes, which is still an order of magnitude off from the setting we work in (100-1000 classes). \n\nOur goal is to produce prediction sets with good class-conditional coverage. We perform clustering as a means towards this goal. The choice of titling the manuscript “cluster-conditional conformal” or “class-conditional conformal” is a matter of emphasizing the mechanism behind the procedure or the result of the procedure. We chose the title of “class-conditional conformal” to highlight this desirable property of the resulting prediction sets.\n\n>\tW2: Reallocating training data to increase calibration data\n\nThis is a good point. There are many reasons that the amount of calibration data per class may be limited in practice. Nowadays, it is common that models are first pre-trained on large amounts of data that are not from the same distribution that you will deploy the model on and then fine-tuned on a much smaller dataset from the target distribution. Moving data from the pre-training data to the conformal calibration dataset will not lead to valid conformal prediction sets due to the distribution shift. Even if you do have a reasonably large labeled dataset from your target distribution, it is generally undesirable to exclude large amounts of data from training: suppose that we want 100 calibration examples per class but we have 1,000 classes; we would have to set aside 100,000 examples. Removing such large amounts of data from the training dataset will often reduce model accuracy.\n\nWe thank the reviewer for raising this point, and we will explicitly raise this in the manuscript.\n\n>\tW3: Sensitivity analysis\n\nYou can find the sensitivity analysis on the clustering procedure in Appendix B.2. We find that our method is robust to the choice of $M$. \n\n>\tW4: CovGap and potential undercoverage\n\nThis is another important point, and we have carried out an extensive experiment to investigate this. Please see the common response for details. \n\n\nIn response to questions:\n\n>\tQ1: Using largest calibration score rather than infinity\n\nAs you point out, your suggested modification will not yield a coverage guarantee. To test the effect in practice, we ran an additional experiment following your suggestion. The tl;dr is that (1) as expected, the modified classwise conformal procedure does have smaller set size and results in undercoverage and (2) clustered conformal still does better than modified classwise in terms of both set size (lower AvgSize) and class-conditional coverage (lower CovGap). \nIn more detail: (CIFAR-100, with 1000 total calibration points sampled using fixed random seed). FracUnderCov is the fraction of classes with less than 80% coverage.\n* `Classwise`: CovGap = 7.8, AvgSize = 46.1, FracUnderCov = 0.08\n* `Modified Classwise`: CovGap = 7.9, AvgSize = 18.0, FracUnderCov = 0.18\n* `Clustered`: CovGap = 4.5, AvgSize = 8.2, FracUnderCov = 0.08\n\n>\tQ2: Null cluster; merging clusters\n\nHow we treat classes in the null cluster makes very little practical difference. With that said, one way to get cluster-conditional coverage even for the null cluster is to treat it like any other cluster and estimate a conformal quantile for that cluster. We choose to not do this and opt instead to use the threshold that provides marginal coverage since it is lower variance and works well in practice. \n\n>\tQ3: Alternative methods for handling with rare classes \n\nWe would not gain anything by up-sampling rare classes and running class-conditional conformal on the synthetically generated sampled dataset. First, from a theoretical perspective, this would not come with any coverage guarantee. The issue is that upsampling the data results in a data set that is not exchangeable with test data – there will be many duplicates in the calibration data, but we know that with probability 1 we will not see any duplicates in the test data. Thus, upsampling would fight against the guarantees underlying conformal prediction.\n \nSecond, from a practical perspective, the resulting estimated conformal thresholds would be extremely volatile. Regarding your suggestion to “do the clustering on the original dataset to obtain the desired sample size, and then use class-conditional conformal?” — this is a very reasonable idea and is in fact what we do! What is special about our clustering is that the clusters we produce make it so that we will get good class-conditional coverage and not just cluster-conditional coverage. \n"}, {"review_id": "PR7Q6DXdcV", "reviewer": "Reviewer_MBi5", "summary": "Standard conformal prediction provides a marginal coverage guarantee which is insufficient for many practical applications. Class-conditional conformal prediction is suitable for many applications, especially in $Y \\rightarrow X$ settings, e.g., image data. Achieving class-conditional coverage relies on learning a separate threshold for each label, and hence splitting the calibration set into label-dependent groups. This becomes prohibitive in classification problems with many classes. The current paper proposes a method based on clustering similar classes (which share similar conformal scores) and performing cluster-conditional conformal threshold calibration.", "questions": "I hope that the authors can provide answers to the following questions/concerns:\n\n1. One of the issues with class-conditional CP which has been pointed out in [1] is that there could be cases when the resulting prediction sets are empty (the authors also proposed several ways to handle this issue). Does this issue also apply to the proposed method?\n\n2. I am concerned regarding clustering based on nonconformity scores. Is it possible to (empirically) demonstrate that (even in the most straightforward cases) such classes form \"meaningful\"/\"interpretable\" clusters if nonconformity scores are used as features? Consider CIFAR-100 dataset as an example: class \"apples\" is \"closer\" to the class \"mushrooms\" than it is to the class \"rocket\". However, suppose those happened to be assigned to the same cluster. In that case, the coverage guarantee reads as \"among images with apples, mushrooms, and rockets, the true label is contained in the prediction set with probability at least $1-\\alpha$\" and may not be that interpretable.\n\n3. For many datasets, there is a known taxonomy/hierarchy of classes, e.g., for CIFAR-100, even though there are 100 classes, these are grouped into 20 superclasses. Such taxonomies can also be used to convert the low-data class-conditional calibration step to a high-data group-conditional calibration step, while resulting in interpretable clusters/groups. Even if such taxonomy is not provided, one can still try to come up with one that guarantees that there are \"enough\" calibration points in each group. What are the advantages of the proposed method over this strategy?\n\n[1] \"Least Ambiguous Set-Valued Classifiers with Bounded Error Levels\". Sadinle et al., 2016", "limitations": "The current work is a part of methodological research and does not have a potential negative societal impact. Overall, I hope that the authors can better highlight the downsides of the proposed method (e.g., grouping based on existing dataset taxonomy).", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written, and provided figures help the reader to follow the content easily. Relevant works and the limitations of the respective methods are highlighted. The proposed method is validated on a large number of large-scale public datasets, illustrating its general practical relevance.", "weaknesses": "To avoid tautology, most of my concerns will be outlined in the questions box: those are related to the issues arising empty prediction sets and clustering based on the nonconformity scores. There is also a couple of minor typos:\n1. Line 26: $\\mathcal{C}(X_{test})\\subseteq \\mathcal{Y}$.\n2. Proposition 1: missing full stop in the equation between lines 156 and 157.\n\nFinally, a couple of stylistic suggestions:\n1. In Figure 1, it may be better to make sub-captions consistent (i.e., point out that the left su-plot refers to standard CP and the right one to Classwise CP). \n2. In Figure 2, it may be better to use different markers (in addition to different colors) for depicting the results of using different methods.\n3. I believe that [1] should also be cited and discussed.\n\n[1] \"Least Ambiguous Set-Valued Classifiers with Bounded Error Levels\". Sadinle et al., 2016\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We appreciate your summary of the motivation for achieving class-conditional coverage and why it can be difficult in multi-class classification problems. Thanks for suggesting we cite Sadinle et al., 2016, which presents a variant of classwise conformal. We have added it to our discussion of related work. \n\nIn response to your questions:\n\n> Q1: Empty sets\n\nIn our experiments, we did not observe null sets to be a problem. The problem of empty sets is a real one that appears with some conformal prediction methods, but this problem is orthogonal to the problem we are focused on. If null sets were to appear when the clustered conformal procedure is applied to other settings, we could apply some method for addressing empty sets in other conformal procedures. For example, a simple modification that can be applied to any conformal procedure to avoid empty sets is to return the union of the conformal set and $\\\\{y_{\\min}\\\\}$ where $y_{\\min}$ is the class with the smallest conformal score (i.e., the “most likely” class). Since this modified set is a superset of the original conformal set, the new set will also have a $1-\\alpha$ coverage guarantee. (Also, there are further improvements that can make this procedure non-conservative as well.)\n\nIn a different direction, Guan and Tibshirani ‘22 [1] use empty sets intentionally and give them semantic meaning. In that work, the empty set is used to indicate that a data point does not appear to be consistent with any class and should be treated as an outlier. While we do not pursue this approach in our present work, with some conformity scores, the same idea could be used in conjunction with the clustering we propose.\n\n[1]  \"Prediction and outlier detection in classification problems.\" Guan and Tibshirani, 2022.\n\n> Q2: Meaningful clusters\n\nOur investigations into cluster memberships showed that indeed, classes that are semantically similar are generally not grouped together (i.e., did not have similar conformal score distributions). If semantically similar classes did have similar conformal score distributions, our problem would be simpler to solve! The fact that this relationship does _not_ hold is what makes our data-driven clustering approach necessary and what prompted our investigation in the first place. Nonetheless, exploring what determines which classes are grouped together is something we would like to better understand. We thank the reviewer for this point and we will explicitly discuss this in the updated manuscript.\n\n> Q3: Clustering based on taxonomy\n\nThis is another very interesting direction. The advantage of the alternative method you described is that the clusters are more interpretable, so the cluster-conditional coverage guarantee is perhaps more intuitive. The disadvantage is that this alternative method will not in general yield class-conditional coverage – the errors will be traded off, with some hard classes having low coverage and some easy classes having high coverage.\n\nConversely, our method produces clusters that are not generally not semantically meaningful, so the cluster-conditional coverage guarantee is less interpretable; however, the advantage is that our method is designed to yield class-conditional coverage (due to the approximate exchangeability of the conformal scores for classes grouped in the same cluster). Echoing our reply to your previous question, the fact that semantically related classes do not have similar distributions is what makes our proposal necessary, and motivated us to pursue this direction in the first place. To summarize: if you want good coverage _for each taxonomic group_, the method you described will be better, but if you want good coverage _for each class_, our proposed method will be better. \n"}]

Author rebuttal:
We would like to thank the reviewers for engaging with our paper and for providing helpful comments and suggestions. We have incorporated the feedback into the paper, and have run a new set of experiments (described below). 

The reviewers agreed the paper was well-written and that we thoroughly validated our method via extensive experiments on several datasets. 

A couple points we would like to address to all reviewers:

* Several reviewers expressed concerns that the CovGap metric could obscure undercoverage of some classes. To investigate this, we ran experiments that looked specifically at the fraction of classes with less than 80% coverage (FracUnderCov). These results are included in Appendix C.2 and we find that clustered conformal also does well in this metric and  trends in FracUnderCov generally mirror the trends in CovGap. Additionally, in the attached pdf we have included new plots that show the amount of undercoverage (UnderCovGap) and the amount of overcoverage (OverCovGap). More explicitly, UnderCovGap is CovGap restricted to classes with less than the desired coverage level: $$\text{UnderCovGap} = 100 \times \frac{1}{|\mathcal{Y}|}\sum_{y \in \mathcal{Y}}  |\hat{c}_y -(1-\alpha)| \cdot  \mathbf{1}\\{\hat{c}_y \leq (1-\alpha)\\}$$ where $\hat{c}_y$ is the coverage of class $y$. OverCovGap is computed analogously but with $\mathbf{1}\\{\hat{c}_y \geq (1-\alpha)\\}$.
* The goal of our paper is not to champion the use of the clustered conformal method in all settings (and we hope our writing reflects this, particularly in the discussion section). We perform extensive experiments to understand when baselines do well, and we identify a regime in which we can be smarter about how we use our data — in this regime, we recommend the use of clustered conformal. 

We provide individual replies to specific comments from each reviewer. 


Meta-review: In this paper, the authors investigate conformal prediction that ensures class-conditional coverage guarantees for each class in a multi-class classification problem with numerous classes. It is widely recognized as a significant limitation that conventional conformal prediction can only provide marginal coverage guarantees. This paper can be regarded as one of the studies that overcome this limitation. The authors' main idea is to improve class conditional coverage, particularly for small-sized classes, by clustering similar classes together. All reviewers find the main idea of the proposed method interesting. During the rebuttal and discussion period, most of the reviewers' concerns have been addressed.
Decision: Accept (poster)