Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration
Authors: Yuanjie Shi
SUBHANKAR GHOSH
Taha Belkhouja
Jana Doppa
Yan Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: Uncertainty Quantification
Conformal Prediction
Imbalanced Data
Class-conditional Coverage
Deep Models
Primary area: safety_in_machine_learning
TL;DR: Provable conformal prediction method to produce small prediction sets for class-conditional coverage for imbalanced classification problems using the augmented rank calibration.

Abstract: Conformal prediction (CP) is an emerging uncertainty quantification framework that allows us to construct a prediction set to cover the true label with a pre-specified marginal or conditional probability.
Although the valid coverage guarantee has been extensively studied for classification problems, CP often produces large prediction sets which may not be practically useful.
This issue is exacerbated for the setting of class-conditional coverage on imbalanced classification tasks with many and/or imbalanced classes.
This paper proposes the Rank Calibrated Class-conditional CP (RC3P) algorithm to reduce the prediction set sizes to achieve class-conditional coverage, where the valid coverage holds for each class.
In contrast to the standard class-conditional CP (CCP) method that uniformly thresholds the class-wise conformity score for each class, the augmented label rank calibration step allows RC3P to selectively iterate this class-wise thresholding subroutine only for a subset of classes whose class-wise top-$k$ error is small.
We prove that agnostic to the classifier and data distribution, RC3P achieves class-wise coverage. We also show that RC3P reduces the size of prediction sets compared to the CCP method. 
Comprehensive experiments on multiple real-world datasets demonstrate that RC3P achieves class-wise coverage and  $26.25\\%$ $\downarrow$ reduction in prediction set sizes on average.

Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration
Yuanjie Shi Washington State University
Subhankar Ghosh
Taha Belkhouja Washington State University
Washington State University
Janardhan Rao Doppa Washington State University
Yan Yan Washington State University
Abstract
Conformal prediction (CP) is emerging uncertainty quantification framework that allows us to construct a prediction set to cover the true label with a pre-specified marginal or conditional probability. Although the valid coverage guarantee has been extensively studied for classification problems, CP often produces large pre- diction sets which may not be practically useful. This issue is exacerbated for the setting of classcconiiio coverage on classification tasks with many and/or imbalanced classes. This paper proposes the Rank Calibrated Class-conditionss CP (RC3P) algorithm to reduce the prediction set sizes to achieve class- cass-conditional coverage, where the valid coverage holds for each class. In contrast to the stan- dard class-conditional CP (CCP) method that uniformly thresholds the class wise conformity score for each class, the augmented label rank calibration step allows RC3P to selectively iterate this class-wis thresholding subroutine only for subset of classes whose class-wise top-k error is small. We prove that agnostic to the clas- sifier and data distribution, RC3P achieves class-wise coverage. We also show that RC3P reduces the size of prediction sets compared to the CCP method. Comprehen- sive experiments on multiple real-world datasets demonstrate that RC3P achieves class-wise coverage and 26.25% reduction in prediction set sizes on average.
Introduction
Safe deployment of machine learning (ML) models in high stakes applications such as medical diagnosis requires theoretically-sount uncertainty estimates. Conformal prediction (CP) [60] is an emerging uncertainty quantification framework that constructs prediction set of candidate output values such that the true output is present with a pre-specified level (e.g., 90%) of the marginal or conditional probability [65] 19..
promising property of CP the model-agnostic and distribution-free coverage validity under certain notions 120 For example, marginal coverage the commonly studied validity notion 1 65). while conditional coverage is stronger notion. There general taxonomy group data (i.e., input-output pairs) into categories and to study the valid coverage for each group (i.c., the group-wise validity) [6] 60). This paper focuses on the specific notion of class-conditional coverage that guarantees coverage for each class individually, which is important for classification tasks with many and/or imbalanced classes (e.g., medical applications)
39 56
In addition to the coverage validity, predictive efficiency another important criterion for CP 20 59 which refers to the size of the prediction sets. Both coverage validity and predictive efficiency are used together to measure the performance of CP methods [ 45| 47 [5] 22 [8]. Since the two measures competing M. our goal is guarantee the coverage validity with high predictive efficiency,
i.e. small prediction sets 20 47 18 Some studies improved the predictive efficiency under the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

marginal coverage setting using new conformity score function [ and new calibration procedures However, it is not known if these methods will benefit the predictive efficiency for the class-conditional coverage setting. A very recent work [15 proposed the cluster CP method to achieve approximate class-conditional coverage. It empirically improves predictive efficiency over the baseline tlass-wiss, CP method (i.e., each class is one cluster) [58], but the approximation guarantee for class-wise coverage is nepee-dependent (i.e., requires certain assumptions on the model). The main question of this paper is: how can we develop model-agnostee CP algorithm that guarantees the class-wise coverage with improved predictive efficiency (i.e., small prediction sets)?
19 18 26
To answer this question, we propose novel approach referred to as Rank Calibrated Class-conditionss CP (RC3P) that guarantees the wise coverage with small expected prediction sets. The class- conditional coverage validity of RC3P is agnostic to the data distribution and the underlying ML model, while the improved predictive efficiency depends on very mild conditions of the given trained classifier. The main ingredient behind the RC3P method is the label rank calibration strategy augmented with the standard conformal score calibration from the class-wise CP (CCP) 58 2
The CCP method finds the class-wise quantiles of non-conformity scores on calibration data. To produce the prediction set for new test input Xlest, it pairs Xiest with each candidate class label and includes the label if the non-conformity score of the pair (Xust: ()) is less than or equal to the corresponding class-wise quantile associated with y. Thus, CCP constructs the prediction set by uniformly iterating over all candidate labels. In contrast, the label rank calibration allows RC3P to selectively iterate this class-wise thresholding subroutine only if the label y is ranked by the classifier f(Xies) (e.g., [-) denotes the softmax prediction) in the top ki candidates, where the value of ky calibrated for each label y individually according to the class-wise top-ki error. In other words, given Xieu, RC3P enables standard class-wise conformal thresholding for the sufficiently certain class labels only (as opposed to all labels). Our theory shows that the class-wise coverage provided by RC3P is agnostic to the data distribution and the underlying ML model. Moreover, under very mild condition, RC3P guarantees improved predictive efficiency over the baseline CCP method.
Contributions. The main contributions of this paper are:
We design a novel algorithm RC3P that augments the label rank calibration strategy to the standard conformal score calibration step. To produce prediction sets for new inputs, selectively performs class-wise conformal thresholding only on subset of classes based on their corresponding calibrated label ranks.
We develop theoretical analysis to show that RC3P guarantees class- coverage, which is agnostic to the data distribution and trained classifier. Moreover, it provably produces smaller average prediction sets over the baseline CCP method (58).
We perform extensive experiments on multiple imbalanced classification datasets and show that RC3P achieves the class-wise coverage with significantly improved predictive efficiency over the existing class-conditional CP baselines (26.25% reduction in the prediction size on average on all four datasets or 35% reduction excluding CIFAR-10). The code is available at https://ghhbbb.cmyyyyuje////CCip
2
Related Work
Precise uncertainty quantification of machine learning based predictions is necessary in high-stakes macksion-making applications. It is especially challenging for imbalanced classification tasks. Al- though many imbalanced classification learning algorithms [10 25 are proposed, e.g., re-sampling 54 [3] and re-wcighting (28, [40. they do not provide uncertainty quantification with rigorous guarantees over predictions for each class.
M 42 33
Conformal prediction 662 60 a model-agnostic and distribution-free framework for uncertainty quantification by producing prediction sets that cover the true output with a pre-specified proba- bility, which means CP could provide valid coverage guarantee with any underlying model and
data distribution 332 52
16]. Many CP algorithms are proposed for regression [35 46
23 I7].
classification 45
64
structured prediction 6 3 30,, online learning 24 and co-
variate shift 31
5 5
settings. Coverage validity and predictive efficiency are two common and
competing desiderata for CP methods []. Thus, small prediction sets are favorable whenever the e.g., human and machine learning collaborative systems
coverage validity is guaranteed
20 47 8

---

Recent work improved the predictive efficiency for marginal coverage by designing new conformity score I and calibration procedures [19 18 26 21 These methods can be combined with class-conditional CP methods including RC3P as we demonstrate in our experiments, but the effect on predictive efficiency not clear.
39 56 38
In general, the methods designed for specific coverage validity notion are not necessarily compatible
with another notion of coverage, such as object-conditional coverage [58), class-conditional coverage
188. local coverage [36] which are introduced and studied in the prior CP literature [6 60 20 13 [
The standard conditonnii CP method in [58 49 guarantees the class- wise coverage, but does not
particularly aim to reduce the size of prediction sets. The cluster CP method [[5] which performs CP
over clusters of labels achieves a cluster-conditional coverage that approximates the class-conditional guarantee, but requires some assumptions on the underlying clustering model.
Our goal is to develop a provable class-conditional CP algorithm with small prediction sets to guarantee the class-wise coverage that is agnostic to the underlying model.
3 Notations, Background, and Problem Setup
Notations. Suppose (X,Y) is a data sample where X E X' is an input from the input space X. and Y 3 = 21...... KK is the ground-truth label with K candidate classes. Assume (X, Y) is randomly drawn from an underlying distribution P defined on X' x y. where we denote Py = Pxy y). Let f X' + A& denote soft classifier (e.g., soft-max classifier) that produces prediction scores for all candidate classes on any given input X, where A denote the K K-dimensional probability simplex and f(X), denotes the predicted confidence for class y. We define the class-wise top-k error for class from the trained classifier f as y = ((r)((,Y)) > k|Y = y), where
ry(X, Y)
f(X)y] returns the rank of Y predicted by f(X) in a descending order, and [.] is an indicator function. We are provided with training set DDr for training the classifier f. and a calibration set Deal = {(X,; Y))=== for CP. Let Iy {i: Y; y, for all (X,, Yi) E Deai) and n, [Zy| denote the number of calibration examples for class y.
2 [
1[((X),
Problem Setup of CP. Let V X x ) + R denote non-conformity scoring function to measure how different a new example is from old ones [60]. It is employed to compare a given testing sample (Xues, YseSt) with set of calibration data Deal: if the non-conformity score is large, then (Xest, Yess) conforms less to calibration samples. Prior work has considered the design of good non-conformity scoring functions, e.g.. 22 50 [7 In this paper, we focus the scoring functions of Adaptive Prediction Sets (APS) proposed in [47] and Regularized APS (RAPS) proposed in [I] for classification based on the ordered probabilities of and true label rank ry (X, Y). For the simplicity of notation, we denote the non-conformity score of the i-th calibration example as V = V(X,, Y.).
Given input X, we sort the predicted probability for all classes [1, .1. K) of the classifier I such that 1 2 f(X)()) 2 2 f(X)(K) 2 O are ordered statistics, where I (())()) denotes the k-th
largest prediction. The APS 47 score for a sample (X, Y) is computed as follows:
v(X,))
Σ
f(X)) UU ((X)))(())))
where U [0, is uniform random variable to break ties. We also consider its regularized variant RAPS D. which additionally includes rank-based regularization A(r (X, Y) kreg)) to the above
equation, where (+)+ max (0,-) denotes the hinge loss, X and kreg are two hyper-parameters.
For a target coverage 1 a, we find the corresponding empirical quantile on calibration data Deal defined as
Q
i = min (:: Σ
1 I[ s S a]
-=1
which can be determined by finding the [(1 1 )1 + 1
-th smallest value of (V)).. The prediction set of a testing input Xtest can be constructed by thresholding with -i-a:
(X {v E 3) V v) S --
A concurrent work by Huang and colleagues 29 studied a method named sorted adaptive prediction sets which uses label ranking information improve the predictive efficiency in the marginal coverage setting.
3

---

Therefore, Či gives marginal coverage guarantee 44 1: P(x,y) PfY E (x)a 20
To achieve the caas-conniiional coverage, standard CCP [88
uniformly iterates the class-wise
thresholding subroutine with the class-wise quantiles {Qi hey:
(X = {u EV: ( (Xeest test; v) - Q (u)),
where Qi - (y) = min { t Σ 1 Σー
1T S 2
VEI, Rg
Specifically, CCP pairs Xies with each candidate class label y, and includes y in the prediction set CCCP (Xust) ) if V (Xest 3) I Qi (v) holds. After going through all candidate class labels y E y it achieves the class-wise coverage for any y E y [1:
P(X,))-(( E CPCP (X)a = y) a.
CCP produces large prediction sets which are not useful in practice. Therefore, our goal develop a provable CP method that provides class-conditional coverage and constructs smaller prediction sets than those from CCP. We summarize all the notations in Table 3ff Appendix.
Rank Calibrated Class-Conditional CP
We first explain the proposed Rank Calibrated
Conformal Prediction (RC3P) algorithm and present its model-agnostic coverage guarantee. Next, we provide the theoretical analysis for the provable improvement of predictive efficiency RC3P over the CCP method.
4.1 Algorithm and Model-Agnostic Coverage Analysis
We start with the motivating discussion about the potential drawback of the standard CCP method in terms of predictive efficiency. Equation (I) shows that, for a given test input Xust, CCP likely contains some uncertain labels due to the uniform iteration should be included into the prediction set or not. For example, given a class label y and two test samples X1, X2, suppose their APS scores V(X1, y) 0.9, V(X2, x) v) 0.8, with ranks L,,,( v) = 5. Furthermore, Qi (y) = 0.85, then by I for CCP, we know that y & C (X1) and y E ČCCP (X2), even though f(X,) ranks y at the #1 class label for X₁ with very high confidence f(Xi)y 0.9 and CCP can still achieve the valid class-conditional coverage. We argue that, the principle of CCP to scans all E Y uniformly can easily result in large prediction sets, which is detrimental to the effectiveness of human-Mi ML collaborative systems 4 51).
each class label y E y check
(x( (x =
Consequently, to improve the predictive efficiency of CCP (i.e., reduce prediction set sizes), it is reasonable to include label rank information in the calibration procedure to adjust the distribution of non-conformity scores for predictive efficiency. As mentioned in the previous sections, better scoring functions have been proposed to improve the predictive efficiency for marginal coverage, e.g., RAPS. However, directly applying RAPS for class-wise coverage presents challenges: I) tuning its
for each class requires extra computational overhead, and 2) fixing its hyper-parameters for all classes overlooks the difference between distributions of different classes. Moreover, for the approximate class-conditions coverage achieved by cluster CP [5]. it still requires some assumptions the underlying model (i.e., it is not fully model-agnostic).
Therefore, the key idea of our proposed RC3P algorithm (outlined in Algorithm class-wiss calibration procedure using label rank calibration strategy augmented to the standard conformal score calibration, to enable adaptivity to various classes. Specifically, in contrast to CCP, RC3P selectively activates the class-wise thresholding subroutine in (1) according to their class-wise top-k error e for class y. RC3P produces the prediction set for a given test input X with two calibration schemes (one for conformal score and another for label rank) as shown below:
! to refine the
aRCAP (Xiea {u y V(Xies, 3) S 11-ay (v), ry (Xeea y) S T((w) }
conformal score calibration
label rank calibration
where Qplass (v) and k(y) are score and label rank threshold for class y, respectively. In particular, R(v)
kg() controls the class-wise uncertainty adaptive each class y based on the top-k error eg of the

---

Algorithm RC3P Method for Class-Conditioall CP
1: Input: Mis-coverage rate E (0, 1)., top-k errors ef for all classes and ranks y, k E (1,... K}
2: Randomly split data into train Dur and calibration D and train the classifier f on Dur
3: for y E {1.-.. K} do
4: Compute {Vi
Ph i for all (i), E Deal such that Y; =
5: Configure calibrated label rank k(y) and nominal emror oy:
6: Option (model-agmostic coverage):
M(v) k(y) E {k: + < <a), 0 ay S a Ey as per Eq
7: Option II (model-agnostte coverage improved predictive efficiency::
k(y) min h= E < at, By
Ey k(v) per Eq
8:
Qelass
11-a
(v) + [(1 - a,) + ny) 1-th smallest value in (V) according to Eq 1b
9: end for
Construct CRC3P (eess) with Qa (y) and k(y) for a test input Xest using Eq 3
classifier. By determining k(y), the top k predicted class labels of ((Xies) will more likely cover the true label Yeea, making the augmented label rank calibration filter out the class labels y that have a high rank (larger ry (X, v)). As result, given all test input and label pairs {(Xuest v) wey, RC3P performs score thresholding using class-wisc quantiles only on a subset of reliable test pairs.
Determining k(y) and Cy for model-agnostic valid coverage. For class y, intuitively, we would like value for R(y) such that the corresponding top-k(y) error is smaller than so that it is possible guarantee valid coverage (recall [PA,, B} (AA)- P P(B]A)). Since larger R(y) gives smaller R(v) ey untill 5x it is guaranteed to find value for k(yy), in which the corresponding by R(y) As result, given all test input and label pairs {(Xuest y) bey, RC3P performs score thresholding using class-wise quantiles only on a subset of reliable test pairs and filters out the class labels y that have a high rank (larger (X, y)). The following result formally shows the principle to configure k(y) and & to guarantee the class-wise coverage that agnostic to the underlying model.
Theorem 4.1. (Class-conditional coverage of RC3P) Suppose that selecting k(yy) values result the class-wise top-k error ey
E(()) for each class y y. For target class-conditional coverage a, if
we set ay and k(y) in RC3P
(3) in the following ranges:
Te(y)) E [k l6:c; a), 0 a Sa J((y)
then RC3P can achieve the dass-conditionaa coverage for every Y:
PY E GREH (X)JY = y) 2 a.
4.2 Analysis of Predictive Efficiency for RC3P
We further analyze the predictive efficiency of RC3P: under what conditions RC3P can produce smaller expected prediction set size compared to CCP, when both achieve the same (1 a)-class- conditional coverage. We investigate how to choose the value of a, and k(y) from the feasible ranges in 4 to achieve the best predictive efficiency using RC3P.
Lemma 4.2. (Trude-off condition for improved predictive efficiency of RC3P) Suppose ã. and k(y) satisfy in Theorem 4.1, If the following inequality holds for any y E Y.:
P Xua (X v) s Qulass ry (X y) S Te(y)) Pxx [V(Neers v) S Qullasss) (5)
then RC3P produces smaller expected prediction sets than CCP, i.e.,
E Ex
GRC3P (X,ea) Ex... 11 (X,e))]]-
Remark, The above result demonstrates that when both RC3P and CCP achieve the target - class-conditional coverage, under the condition of (5), RC3P produces smaller prediction sets than CCP. In fact, this condition implies that the combined (conformity score and label rank) calibration
5

---

of RC3P tends to include less labels with high rank or low confidence from the classifier. In contrast, the CCP method tends to include relatively more uncertain labels into the prediction set, where their ranks are high and the confidence of the classifier is low. Now we can interpret the condition ( by defining condition number, termed as Ty:
P Xise
V(X lest: y) S Q (V), ( v) S k(U)
0g
(6)
IP x ((Xrests y) S Q9 (v)
In other words, if we can verify that By I for all y, then RC3P can improve the predictive efficiency over CCP. Furthermore, if oy is fairly small, then the efficiency improvement can be even more significant. To verify this condition, our comprehensive experiments (Section 5.2 Figure show that By values are much smaller than on real-world data. These results demonstrate the practical utility of our theoretical analysis to produce small prediction sets using RC3P. Note that the reduction in prediction set size of RC3P over CCP is proportional to how small the By values are.
Theorem 4.3. (Conditions of improved predictive efficiency for RC3P) Define D = -|rr (X,1) S k(D)YY * g). (y
[ Denote B (e)( I Qqtne (y)ly # yl if
2
+X S (y)lY + y] is If D Py (a Ey M(u) Py
is APS, or B =
then yy < 1.
Remark.
The above result further analyzes when the condition in Eq (5) of Lemma 4.2 (or equiv- alently, Bg S 1) holds to guarantee the improved predictive efficiency. Specifically, the condition
k(t)) of Theorem 4.3 can be realized in two ways: (i) making LHS B D as
B B- D 1-Ps (a
Cy Cy
large as possible; (ii) making the RHS Py (a Ey Mi()) as small as possible. To this end, we can set
1-Px
Line 7 in Algorithm | in the following way:
k(()) min (k: + < aa,
C, a klv)
Therefore, this setting ensures og S and as a result improves predictive efficiency.
Experiments and Results
We present the empirical evaluation of the RC3P algorithm and demonstrate its effectiveness in achieving class-conditional coverage to produce small prediction sets. We conduct experiments using two baselines (CCP and Cluster-CP), four datasets (each with three imbalance types and five imbalance ratios), and two machine learning models (trained for 50 epochs and 200 epochs, with 200 epochs being our main experimental setting). Additionally, we use two scoring functions (APS and RAPS) and set three different values (a E 0.1, 0.05, 0.01, with 0.1 main setting).
5.1 Experimental Setup
Classification datasets. We consider four datasets: CIFAR-10, CIFAR 100 (34), mini- ImageNet [57]. and Food-101 -01
(8) by using the standard training and validation split. We employ the same [4 to create an imbalanced long-tail setting for each dataset as harder challenge: 1) We use the original training split as training set for training f with training samples (Mer is defined as the number of training samples), and randomly split the original (balanced) validation set into calibration samples and testing samples. 2) We define an imbalance ratio p. the min, (# samples in class s}
methodology as 41 10
ratio between the sample size of the smallest and largest class: p max, [# samples in class 2J. 3) For each training set, we create three different imbalanced distributions using three decay types over the class indices E (1..... K): (a) An pioonential-based decay (EXP) with fer x p examples in class c, (b) A polynomial-basee decay (POLY) with
K
Top +1 examples in class c, and (c) A
majority-based decay (MAJ) with Per x p examples in classes C > 1. We keep the calibration and test K set balanced and unchanged. We provide an illustrative example of the three decay types in Appendix (Section C.3 Figure 4). Towards a more complete comparison, we also employ balanced datasets. Following Cluster-CFd we employ CIFAR-100, Places365 [66), iNauuralist (55), and ImageNet[48)

---

Table I: Imalanced classification data experiment on CIFAR-10, CI0,R-100, mini-ImageNet, F0od-101. APSS results comparing CCP, C Cluster-CP, and RC3P with ResNet-20 model trained with 200 epochs under different imbalance types and ratios when a = 0.1. For a fair comparison of APSS, we set UCR of RC3P the same as or smaller (more restrictive) than that of CCP and Cluster-CE under 0.16 on CIFAR- 10 and 0.03 on other datasets. The specified UCR values are in Table and of Appendix C.4 and C.5 The APSS results show that RC3P significantly outperforms CCP and C1 ustuu----- CP in terms of average prediction set size with 24.47% (four datasets) or 32.63% (excluding CIFAR- 10) reduction over min (CCP, cluster-CP).
Conformity Score
Methods
EXP
POLY
MAJ
055
p=
p=05
p=0.1
p=05
p=
CIFAR-10
CCP
1,585
0.010
1.855
1,538
1.776
0.012
1,800
2.629
0.013
APS
Cluster-CP
1,714
+ -.0088
2,162 + 0.015
1,706 + 0.014
1.928
0.0033
1.948 + 0.023
3,220
0.020
RC3P
1,555
0.010
1.855
0.014
1,538
0.010
1.776
0.012
1.840
0.020
2.629
0.013
CCP
1,555
0.010
1.855
0.014
1.538
0.010
1.776
0.012
1.840 1: 0.020
2.632
0.012
RAPS
Cluster-CP
1,714 + 0.018
2.162 + 0.015
1,706 + 0.014
1,929
= D.013
1.987 + 0.019
2.968
0.024
RC3P
1,558
0.010
1.855
0.014
1,538
0.010
1.776
0.012
1.840
0.020
2.632
0.012
CCP
1.144
0.005
1.324 :: 0.007
1.137 1: 0.003
1.243
0.005
1,272 1: 0.008
1,936
0.010
HPS
Cluster-CP
1,214 0.008
1,508 0.010
1,211 0.004
1.354
0.005
1,336 0
2.312
0.025
RC3P
1.144
0.008
1.324
0.007
1.137
0.003
1.243
0.005
1,272 0.008
1,9%
0.010
CIFAR-100
CCP
14,224=00334
50,969 = 0.345
49,889 + 0.353
64,343 :: 0.237
44,194 = 0,514
64.642 : 0.535
APS
Cluster-CP
29,238
0.609
37.992 0.857
38.252
0.353
52.391 0.595 33.185 0.005
31,518
0.335 18:581
50,883 0.673
RC3P
17.705 = 0.004
0.005 21,954
23.048 0.008
0.007
32,699
0.005
CCP
44,250 + 0.342
0.345 50,970
49,886
0.353
64,352
0.236 52.374
48.343 + 0,353
64 66. 0.535
RAPS
Cluster-CP
29.267
0.612
37.795
38,258
0.320
31.513
0.325
50,379
RC3P
17,705
+ 0.004
0.005 21.954
23,048 +: 0.008
33.185
0.005
18.581 + 0.006
32,699
0.006
CCP
41.351
0.242
49.469
0,344
48.063 0.376
63.963
0.277
46.125
0.351
64.371 0.564
HPS
Cluster-CP CP
27.566
1: 0.555
35.528
0.979
36.101 1. 0.565
51.353
0.776
29.323 1: 0.363
50.519
0.679
RC3P
20,363 0,006
25,212 0,010
25,908
0,007
36,951 0.018
21.149
0,006
0.005 35,606
mini-ImageNee
CCP
26.676 1: 0.171
26.111
0.194
26.626 0,133
26.155
0.208
27.313
0,154
25.629
0.207
APS
Cluster-CP
25,889
0.301
25,253 0.346
26.
0.393
25.633
0.268 17,465
26.918
0.241
25.343 0.334
RC3P
18.129 :: 0.003
17,082 0.002
17,784 : 0.003
0.003
18.111
0.002
17.167 0.004
CCP
26.756
0.178
26.212
26.689 0.142
26.248
0.219
27.397
0.162
25.725
RAPS
Cluster-CP
26.027
+ 0.325
25.415
0.289 17,082
26,288 + 0.407
25.712
:: 0.315
26,969 + 0,308
25,532 + 0.350
RC3P
18.129
0.003
0.002
17,784 0.003
17,465
0.003
18.111 0.002
17.167 0.004
CCP
24.633 4: 0.212
24.467
0.149
24.379
0.152
24.472
0.167
25,449
0.196
23,885
0.159
HPS
Cluster-CP
23,911
+ 0.322
24.023
0.195
24.23
0.428
23 23,2633 0.295
24.987
0,319
23.323
0.378
RC3P
17,830
0.104
17,036
0.014
17.684
0.062
17.393
0.013
18.024
0.049
17,086
0.059
Food-101
CCP
27,022 = 0.192
30,900
0.170
30,943 = 0.119
35,912 0.105
27.415 0.194
36,776 0.132
APS
Cluster CP
28.953
- 0.333
33.375
1 0.377
33.079
1: 0.393
38,301
1: 0.232
30,071
1 0.412
39.632 1 0.342
RC3P
18.369
0.004
21.556
0.006
21.499 0.003
25,853
0.004
19.398 0.006
26.585
0.004
CCP
27.022 : 0.192
30,900 = 0.170
30,966 2 0.125
35,940 :: 0.111
27.439 + 0.205
36,802 : 0.138
RAPS
Cluster-CP
28.953 1 0.333
33.375
0.377
33.337
0,409
38.499
0,216
29.946
0.407
39,529
0.306
RC3P
18.369 + 0.004
21.556:
0.006
21.499 + 0.003
23,853 0.004
19.397 = 0.006
26.585 0.004
CCP
26.481 + 0.142
30.524
0.152
30.788 : 0.099
35.657
0,107
26.826 0,163
36,518 0.122
HPS
Cluster
29.347
0.288
33.407 0.345
38,956
29.
0.436
0.318
RC3P
18.337
= 0.004
21.558:2 0.006
21.477 : 0.003
25.853 : 0.005
19,396 :: 0.008
26.584 0.003
Deep neural network models. We consider ResNet-20 [27] as the main architecture to train classifiers for imbalanced classification datasets. To handle imbalanced data, we employ the training algorithm "LDAM" proposed by [10] that assigns different margins to classes, where larger margins assigned to minority classes in the loss function. We follow the training strategy in [10] where
all models are trained with 200 epochs. The class-wise performance with three imbalance types and
imbalance ratios p = 0.5 and p 0.1 on four datasets evaluated (see Appendix C. We also train models with 50 epochs and the corresponding APSS results are reported in Appendix C.8
For balanced datsets, we follow the same settings from Cluster-CP, which uses IMAGENETIK V2 as pre-trained weights from PyTorch 44] and then fine-tune models with ResNet-50 for all datasets except ImageNet. For ImageNet, we use SimCLR-v2
12 training models.
CP baselines. We consider three CP methods: 1) CCP which estimates class-wise score thresholds and produces prediction set using Equation (T) 2) Cluster-CP [15] that performs calibration over
clusters to reduce prediction set sizes; and 3) RC3P that produces prediction set using Equation
(3). All CP methods are built on the same classifier and non-conformity scoring function for fair comparison. We employ the three common scoring functions: APS 47], RAPS [. and HPS [49].
We set = 0.1 as main experiment setting and also report other experiment results of different
7

---

Table 2: Balanced experiment CIFAR-I00, Places365, iNaturalist, ImageNet. The models are pre-trained.
UCR is controlled 0.05. RC3P significantly outperforms the best haseline with 32.826% reduction in
APSS ( better) on average over min(CCP, cluster-C;
Conformity Score
Mcasure
Methods
CIFAR-100
Places365
iNaturalist
ImageNet
CCP
0.045 = 0.008
0.012
0.002
0.016
0.001
0.036 = 0.001
UCR
Cluster-CP
0.023
0.029 0.003
0.026
0.031 1 0.002
RC3P
0,006 + 0.003
0,003 0.001
0,008
0.001
0.023 + 0.001
APS
CCP
30,467 + 0.307
19.698 + 0.050
18.802 + 0.023
101.993 + 0.8T2
APSS
Cluster-CP
32,628 + 0.720
20.818 + 0.173
23,467 + 0.494
66.285 + 1.433
RC3P
12.551 + 0.005
13.772 + 0.005
12.736 + 0.006
6,518 + 0.001
CCP
0.043 = 0.006
0.013 = 0.002
0.016 = 0.020
0.038 = 0.020
UCR
Cluster-CP
0.016 1 0.005
0.036 1 0.002
0.027 1 0.003
0.046 1 0.004
RC3P
0.002 1 0.001
0.002 1 0.001
0.006 1 0.001
0.017 1 0.001
RAPS
CCP
26.135 + 0.308
15.694 + 0.049
14,812 + 0.042
37.748 0.304
APSS
Clustcr-CP
28.084 + 0.609
16,750 + 0.143
23.964 + 0.419
16.155 1.241
RC3P
12.586 0.002
14.192 0.001
13.251 0.001
6.560 0.002
CCP
0.034 = 0.006
0.015 0.002
0.018
0.002
0,036 + U.OU2
UCR
Cluster-CP CP
0.029
0.035
1 0.005
RC3P
0,003 0,002
0,002
0,001
0.018
0.002
0,006 1 0.000
HPS
CCP
25.898 + 0.321
14,020 + 0.044
9.751 + 0.033
24,384 0.249
APSS
Cluster-CP
27.165 + 0.600
14,530 + 0.143
13,080 + 0.374
8.810 = 0.046
RC3P
12.558 + 0.004
13.919 + 0.004
9.751 = 0.033
6.533 = 0.001
values (See Appendix C.7
Meanwhile, the nypper-paameeters for each baseline are tuned according to their recommended ranges based on the same criterion (see Appendix C.2). We repeat experiments over 10 different random calibration-testing splits and report the mean and standard deviation.
Evaluation methodology. We use the target coverage - a = 90% class-conditional coverage for CCP, Cluster-CP, and RC3P. We compute three evaluation metrics on the testing set:
Under Coverage Ratio (UCR).
Ex 1 [y (1) s.t. y = cj < 1 - <1-a
UCR == Σ
Ex 1 1/y =
cE[K]
Averuge Prediction Set Size (APSS).
Ex 1y cj (1)1a(x) /K.
APSS =
Σ
E Ex 1 =
cE[K]
Note that coverage and predictive efficiency are two competing metries in CP [1 e.g., achieving better coverage (resp. predictive efficiency) degenerates predictive efficiency (resp. coverage). Therefore, following the same strategy 200 we choose to control their UCR as the same level that close to 0 for fair comparison over three class- class-conditional CP algorithms in terms of APSS. Meanwhile, to address the gap between population values and empirical ones (c.g., quantiles with Õ(1/ (ry) Bty
error bound, common all CP methods [58] 22 2, or class-wist wiis top-k error ey with Õ(1/ (Ty) error bound 433), we uniformly add g/ TTy (the same order with the standard concentration gap) inflate the nominal coverage 1 a on each baseline and tune E {0.25, 0.5, 0.75, 1} on the calibration dataset in terms of UCR. The detailed values of each method are displayed in Appendix
C.2 In addition, the actual achieved UCR values are shown the complete results (see Appendix and C.6.. For complete evaluation, we add the experiments without controlling coverage on imbalanced datasets under the same setting and use the total under coverage gap (UCG) metrie: Under Coverage Gap (UCG).
P|Y E Č(X), s.t. Y=c)
UCG = Σ max [E[K]
P|Y =
Experiments with UCG metric evaluation shown in the Appendix C.9

---

5.2 Results and Discussion
We list empirical results in Table 1 for an overall comparison on four imbalanced datasets with P 0.5, 0.1 using all three training distributions (EXP, POLY MAJ) based the considered APS, RAPS and HPS scoring functions. Complete experiment results under more values of are in Appendix C). Results with APS, RAPS, and HPS scoring functions on balanced datasets are also summarized in T We make the following two key observations: (i) CCP, Cluster- RC3P can guarantee the class-conditional coverage (their UCRs are all close 0) for all settings; (ii) RC3P significantly outperforms CCP and Cluster-CP in APSS on almost all imbalanced settings by reducing APSS with 24.47% on all four datasets and 32.63% on three datasets excluding CIFAR- 10 compared with min { (CCP, Cluster-Ca J on average, while for balanced settings, RC32 still significantly outperforms the best baselines in terms of APSS with 32.826% APSS reduction.
and
To investigate the challenge of imbalanced data and more importantly, how RC3P significantly improves the APSS, we further conduct three careful experiments on imbalanced datasets. First, report the histograms of class-conditional coverage and the corresponding histograms of prediction set size. This experiment verifies that RC3P derives significantly more class-conditional coverage above 1 a- and thus reduces the prediction set size. Second, we visualize the normalized frequency of label rank included in prediction sets on testing datasets for all class-wise algorithms: CCP, C1 Cluster-CP,
Ex 3 (xy(( R.
and RC3P. The normalized frequency is defined as: P(k)= ΣX Ex.. (ry (X))))))) =. Finally,
we empirically verify the trade-off condition number {0,, ]K Equation 6 on calibration dataset to reveal the underlying reason for RC3P producing smaller prediction sets over CCP with our standard training models (epoch = 200). We also evaluate {a with less trained models (epoch = 50) on imbalanced datasets in Appendix C.10 Additionally, we also repeat all three experiments on balanced datasets (i.e., the histograms of class caas-connitional coverage and prediction set size, the normalized frequency of label rank included in prediction sets, and for k in Appendix C.11 Below
discuss our experimental results and findings in detail.
(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-ImageNNtt
(d) Food-101
3.5
4.0
50.0
17.5
25.0
G3.0
Method
7:40.0
Method
15.0
Mothed
2000
Mathod
11.5
12:5
RCCPP
Cluster-CP
CCP
20.0
30.0
cluster-CP RC3P
CCP
12.5 CCP
10.0
7.5
cluster-CP
RC3P
Free
15.0
10.0 cluster-CP RC3P
CCP
11.0
0.5
10.0
5.0
2.5
5.0
8,50
0.92
0.95
0.97
0.99
0 0.90
0.93
0.96
1.00
0 87
0.90
0.93
0.97
1.00
0 8888
0.91 0.94
0.97
1.00
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
Method
160.0
30.0
Method
Method
2.0
3.5
CCC
cluster-CP
0120.0
140.0
25.0
20.0 custter-CP
CCP
30.0 dluste-CP CP
40.0
CCP
2.5
RC3P
100.0
3200
1.5
60.0
80.0
Cluster-CP
RC3P
E 10.0
E 15.0
20.0 Sa
1.0
0.5
20.0
40.0
5.0
10.0
0.0
186
99
9
9,9
27.64
Prediction Set
Prediction
Prediction Set
Prediction Set
Figure 1: Class-conditional coverage (Top row) and prediction set size (Bottom row) achieved by CCP, Cluster-CP, and RC3P methods when = 0.1 and models are trained with 200 epochs four imbalanced datasets with imhalance type EXP & = 0.1. We clarify that RC3P overlaps with CCP CIFAR-10. It is clear class-conditioaal
that RC3P has more densely distributed consiconniiional coverage above 0.9 (the target coverage) than CCP and Cluster- with significantly smaller prediction sets on CIFAR-I00 muii--mageNNet and Food-101.
RC3P significantly outperforms CCP and Cluster-CP. First, is clear from Table 6
g and
7 and 2 that RC3P, CCP, and Cluster-CP guarantee class-conditional coverage on all settings. This can also be observed by the first row of Fig L where the class-wise coverage bars of CCP and RC3P distribute on the right-hand side of the target probability 1 - a (red dashed line). Sec- ond, RC3P outperforms CCP and Cluster-CE with 24.47% (four datasets) or 32.63% (excluding CIFAR- 10) on imbalanced datasets and 32.63% on balanced datasets decrease in terms of average prediction set size for the same class-wise coverage. We also report the histograms of the correspond- ing prediction set sizes in the second row of Figure which shows (i) RC3P has more concentrated class-wise coverage distribution than CCP and Cluster-CP; (ii) the distribution of prediction set sizes produced by RC3P is globally smaller than that produced by CCP and Cluster-Ce which

---

(a) CIFAR-10 10
(b) CIFAR- 100
(c) mini Maiii-lmaeeNet
(d) Food-101
01.75
Method
Jaee Heqqann
20.05
Method
20:07
Mathod CCP
Hoymaltoo nequercy
Method
8 1.000
21225
11.50
CCP
Cluster-CP
RC3P
20.03
0.04
cluster-CP
RC3P
OCP
$ 20.05
20.06
50.04
clustenn-CP - RC3P
0.003
0.04
CCP
-cluste-CCP
_RC3P
20.75
3.002
20.03
0.002
0.000
0:25
0.03
0.01
0.00
0.01
20.00
0.00
24
48
72
95
0.000
17
34
50
66
0.00
26
50
75
100
Rank
Rank
Rank
Rank
Figure 2: Visualization for the normalized frequeney distribution of lahel ranks included the prediction set of CCP, usteerrCPP, and RC3P with p 0.1 for imbalance type EXP when o = 0.1 and models are trained with 200 epochs. It is clear that the distribution of normalized frequency generated by RC3P tends be lower compared to those produced by CCP and Cluster-CP Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
is justified by better trade-off number of {ay) ) shown in Figure 3. Note that the class-wise coverage and the corresponding prediction set sizes RC3P overlap with CCP on CIFAR-10 in Figure [
Visualization of normalized frequency. Figure illustrates the normalized frequency distribution of label ranks included in the prediction sets across various testing datasets. It is evident that the distribution of label ranks in the prediction set generated by RC3P tends be lower compared to those produced by CCP and Cluster-CP. Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods. This indicates that RC3P more effectively incorporates lower-ranked labels into prediction sets, as a result of its augmented rank calibration scheme.
(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food-101
10.0
10.0
10.0
1.0
Frequency
8.0
8.0
Prequency
8.0
6.0
6.0
6.0
6.0
4.0
4.0
4.0
4.0
2.0
2.0
2.0
1.0
2.0
0.0
1.00
8,06
0.30
0.53
0.77
1.00
0
0.35
0.57
0.78
1000
882
0.40
0.60
0,80
1.00
Sigma_y
Sigma
Sigma
Sigma
Figure 3: Verification of condition numbers { 1 in Equation 6 with imbalance type EXP, p 0.1 when a = 0.1 and models are trained with 200 epochs. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than 1. This verifies the validity of the condition for Lemma and thus confirms that RC3P produces smaller prediction sets than CCP using calibration on both non-conformity scores and label ranks.
Verification of Tg. Figure 3 verifies the validity of Equation 66 on testing datasets and confirms the optimized trade-off between the coverage with inflated quantile and the constraint with calibrated label rank leads to smaller prediction sets. It also confirms that the condition number {a ) could be evaluated on calibration datasets without testing datasets and thus decreases the overall computation cost. We verify that By < 1 for all settings and og is much smaller than I on all datasets with large number of classes.
Summary
This paper studies a provable conformal prediction (CP) algorithm that aims to provide class- conditional coverage guarantee and to produce small prediction sets for classification tasks with many and/or imbalanced classes. Our proposed RC3P algorithm performs double-calibration, one over conformity score and one over label rank for each class separately, to achieve this goal. Our experiments clearly demonstrate the significant efficacy of RC3P over the baseline class-conditional CP algorithms on both balanced and imbalanced classification data settings.
Acknowledgments. This research was supported in part by United States Department of Agriculture (USDA) NIFA award No. 2021-67021-3534 (AgAID Al Institute) and by NSF CNS-23 2212 grant.
10

---

References
[1] Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. /4/93, 2020.
[2] Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.075// 2021.
[3] Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXiv:2208. 020.028288.081,, 2022.
[4] Varun Babbar, Umang Bhatt, and Adrian Weller. On the utility of prediction sets in human-ai teams. In Proceedings of the Thirty- First International Joint Conference on Artificial Intelligence (IJCAI-22), 2022.
[5] Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshiiani. Conformal prediction beyond exchangeahility. The Annals of Statistics, 51(2):11-844 2023.
[6] Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-34, 2021.
[7] Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online lcarning. In International Conference on Machine Learning, pages 2337-2363. PMLR, 2023.
[8] Lukas Bossard, Matthicu Guillaumin, and Luc Van Gool. Food-101-mining discriminative components with random forests. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6- 2014 4, Proceedings, Part VI 13, pages 446-461. Springer, 2014.
[9] Henrik Boström, Ulf Johansson, and Tuwe Löfström. Mondrian conformal predictive distributions. In Conformal and Probabilistic Prediction and Applications, pages 24 24-38. PMLR, 2021.
[10] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datascts with sabel-distribution-eee -wwrb margin loss. Advances in neural information processing systems, 32, 2019.
[11] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
[12] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self- supervised models are strong semi- -upersuperei learners. Advances in neural information processing systems, 33:22243 22255,22222222 2020.
[13] Kfir M Cohen, Sangwoo Park, Osvaldo Simcone, and Shlomo Shamai. Cross-validation conformal risk control. arXiv preprint arXiv:2401. /1974, 2024.
[14] Yin Cui, Menglin Jia, Tsung-Yi Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss hased on effective number of samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9268-92717 9278-9977,220 2019.
[15] Tiffany Ding, Anastasios Angelopoulos, Stephen Bates, Michael Jordan, and Ryan J Tibssirani. Class- conditional conformal prediction with many classes. Advances in Neural Information Processing Systems, 36, 2024.
[16] Robin Dunn, Larry Wasserman, and Aaditya Ramdas. Distribution-Fie free prediction sets with random effects. arXiv preprint 1rXiv: 07444, 2018
[17] Shai Feldman, Stephen Bates, and Yaniv Romano. Calibrated multiple-output quantile regression with representation learning. Journal of Machine Learning Research, 24(24):1 2023.
[18] Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Efficient conformal prediction via cascaded inference with expanded admission. arXiv preprint arXiv:2007.03114, 2020.
[19] Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Few-shot conformal prediction with auxiliary tasks. In International Conference on Machine Learning, pages 3329-3339. PMLR, 2021.
[20] Matteo Fontana, Gianluca Zeni, and Simone Vantini. Conformal prediction: a unified review of theory and new challenges. Bernoulli, 29(1):1-25 2023.
[21] Subhankar Ghosh, Taha Belkhouja, Yan Yan, and Janardhan Rao Doppa. Improving uncertainty quantifica- tion of deep classifiers via neighborhood conformal prediction: Novel algorithm and theoretical analysis. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 7722-7730 2023.
11

---

[22] Subhankar Ghosh, Yuanjie Shi. Taha Belkhouja. Yan Yan, Jana Doppa, and Brian Jones. Probabilistically robust conformal prediction. In Uncertainty in Artificial Intelligence, pages 681-690. PMLR. 2023.
[23] Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34:1660-1677 2021.
[24] Isaac Gibbs and Emmanuel Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, (5(162):1-36 2024.
[25] Lee-Ad Gottlieh, Eran Kaufman, and Aryeh Kontorovich, Apportioned margin approach for cost sensitive large margin classifiers. Annals of Mathematics and Artificial Intelligence, 89( 1215-1223,,,, 2021.
[26] Leying Guan. Localized conformal prediction: A generalized inference framework for conformal prediction. Biometrika, 1 11031)33-500 2023.
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-775 2016.
[28] Chen Huang. Yining Li, Chen Change Loy, and Xiaoou Tang. Deep imbalanced learning for face recognition and attribute prediction. IEEE transactions on pattern analysis and machine intelligence, 42(1 12:271111122 2019.
[29] Jianguo Huang. Huajun Xi, Linjun Zhang. Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking, 2024.
[30] Kexin Huang, Ying Jin, Emmanuel Candès, and Jure Leskovee. Uncertainty quantification over graph with conformalized graph neural networks. In NeurlPS 2023.
[31] Ying Jin and Emmanuel J. Candès. Model-free selective inference under covariate shift via weighted conformal p-values.
[32] Lisa Jöckel, Michael Kläs, Janek Groß, and Pascal Gerber. Conformal prediction and uncertainty wrapper: What statistical guarantees can you get for uncertainty quantification machine learning? In International Conference on Computer Safety, Reliability, and Security, pages 314-327. Springer, 2023.
[33] Bartosz Krawczyk. Michal Koziarski, Michal Wožniak. Radial-based oversampling for multiclass imbalanced data classification. IEEE transactions on neural networks and learning systems, (18:2888 2831, 2019.
[34] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[35] Jing Lei, Max G Scll, Alessandro Rinaldo, Ryan J Tibshirami, and Larry Wasserman, Distribution-free predictive inference for regression. Journal of the American Statistical Association, (13052)):1094-111) 2018.
[36] Jing Lei and Larry Wasserman. Distribution free prediction bands for non parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71 01677196766771 2014.
[37] Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):91 1-938, 2021.
[38] Charles Lu, Anastasios N Angelopoulos, and Stuart Pomerantz. Improving trustworthiness of ai disease severity rating in medical imaging with ordinal conformal prediction sets. In International Conference on Medical Image Computing and Computer Comiuter-Assisted Intervention, pages 545 545-554. Springer, 2022.
[39] Charles Lu, Andréanne Lemay. Ken Chang, Katharina Höbel, and Jayashree Kalpathy- -Cramer Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 2208-12206, 2022.
[40] Harish Tayyar Madabushi, Elena Kochkina, and Michael Castelle. Cost-sensitive bert for generalisable sentence classification with imbalanced data, arXiv preprint arXiv:2003. /5563, 2020.
[41] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, Sanjiv Kumar. Long-tail learning via logit adjustment. arXiv preprini arXiv:2007.07314, 2020.
[42] Roweida Mohammed, Jumanah Rawashdeh, and Malak Abdullah. Machine learning with oversampling and undersampling techniques: overview study and experimental results. In 2020 11th international conference information and communication systems (ICICS), pages 243-248. IEEE, 2020.
12

---

[43] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[44] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelkhein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[45] 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):4, 2020.
[46] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
[47] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advancey in Neural Information P Processing Systems, 33:3581-3591, 2020.
[48] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-2521 2015.
[49] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 1 14(555))223--34, 2019.
[50] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
[51] Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez. Improving expert predictions with conformal prediction. In International Conference on Machine Learning (ICML.), 2023.
[52] Jiankai Sun, Yiqi Jiang, Jianing Qiu, Parth Nobel, Mykel Kochenderfer, and Mac Schwager. Conformal prediction for uncertainty-awarr planning with diffusion dynamics model. Advances in Neural Information Processing Systems, 36, 2024.
[53] Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
[54] Chih-Fong Tsai, Wei-Chao Lin, Ya-Han Hu, and Guan-Ting Yao. Under-sampling class imbalanced datasets by combining clustering analysis and instance selection. Information Sciences, 477:47-54, 2019.
[55] 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 Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8769-8778, 2018
[56] Janette Vazquez and Julio Facelli. Conformal prediction in clinical medical sciences. Journal of Healthcare Informatics Research, 6(3):241-252, 2022.
[57] Oriol Vinyals. Charles Blundell, Timothy Lillicrap. Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
[58] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 4755490. PMLR, 2012.
[59] Vladimir Vovk, Valentina Fedorova, Ilia Nouretdinov, and Alexander Gammerman. Criteria of efficiency for conformal prediction. In Conformal and Probabilistic Prediction with Applications: Sth International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 5, pages 23 3-39. Springer, 2016.
[60] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithaiic learning in random world. Springer Science& Business Media, 2005.
[61] Vladimir Vovk, David Lindsay, Ilia Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical Report, 2003.
[62] Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-leaming applications of algorithmic randomness. 1999.
[63] Pattaramon Vutipittayamonkol and Eyad Elyan. Neighbourhoodd-baee undersampling approach for handling imbalanced and overlapped data. Information Sciences, 509:47-70, 2020.
[64] Yunpeng Xu, Wenge Guo, and Zhi Wei. Conformal risk control for ordinal classification. In Uncertainty in Artificial Intelligence, pages 2346 2255. PMLR, 2023.
13

---

[65] Margaux Zaffran, Aymeric Dieuleveut, Julie Josse, and Yaniv Romano. Conformal prediction with missing values. In International Conference Machine Learning, pages 40578-40608 PMLR, 2023.
[66] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE transactions pattern analysis and machine intelligence. 40(6))1452-1444 2017.
14

---

A
Mathematical Notations
Table 3: Key notations used in this paper.
Notation
Meaning
X
Input example
YEY
The ground-truth label
The soft classifier
A
The K' KC-dimensional probability simplex
f(X),
The predicted confidence on class y
ck
The class-wise top-k error for class y from
Y
The rank predicted by f(X)
Du
Training data
Deal
Calibration data
Diest
Test data
The number of calibration examples for class
V)
Non-conformity scoring function
Ci-a( (Xia)
Prediction for input X
Target mis- cosscooerage rate
0g
Nominal mis-coverage rate for class y
B Technical Proofs of Theoretical Results
B.1 Proof of Theorem 4.1
Theorem B.1. (Theorem 4.1 restated, class-conditional coverage of RC3P) Suppose that selecting
k(y) values result in the class-wise top-k error Ey T(y) for each class y E y. For target class- conditional coverage a, we ag and k(y) in RC3P
(3) in the following ranges:
T((y) E (k: : <a), 0 then RC3P can achieve the class-conditional coverage for every y y:
k(()) 0 a Sa Ey
(8)
P(X E C.CE (X))( (X)JY y} 2 a.
Proof. (of Theorem
Let E y denote any class label. In this proof, we omit the superscript ie in the top-k error notation & for simplicity.
With the lower bound of the coverage on class (Theorem in 47 we have
- â < rest E C (ies))l = y}
(X Yues) < Yoluss (3) y}
=P(V (Xrea Yrew S class (y). y (X YEE) S <k(w)ly y}
(V(VXiess Yiea) S Qelus (v). .r ( Yuea) k(y)ly = y)
PP (VV (Xrest- Yeew) S Q (3). y [ Yees) S < =y}
(X Yiea) > R(())l =
(Yes E CRCPP (w) = y} + T(()
Re-arranging the above inequality, we have
(Y E CRCP (v) Y y) 1 R(y) a,
where the last inequality is due to ay S a - Eg k(v) This implies that RC3P guarantees the class- conditional coverage any class y. This completes the proof for Theorem 4.1
D
15

---

B.2 Proof of Lemma 4.2
Theorem B.2. (Lemma 4.2 restated, improved predictive efficiency of RC3P) Let ag and k(y) satisfy
Theorem 4.1 If the following inequality holds for any y E y:
Xun [X( y) S Qi ( y) S k(y)] Pxm (X y) S 1i (v)] (9)
then RC3P produces smaller expected prediction sets than CCP, i.e.
E X
CRC3P/ (Xtex) S E Ex Fx__iICC-0 CCCP (X {es))]
Proof. (of Lemma 4.2)
The proof idea is to reduce the cardinality of the prediction set made by RC3P to that made by CCP
in expectation. Let Exas
According to the assumption in V(Xua. a ry (X
Pxwe
v(Nam.)) (v)
we know that øy I 1, which will be used later.
We start with the expected prediction set size of RC3Pand then derive its upper bound.
Exxx
@RCSP (Xies))] = Ex,
Σ E1[v(Xme (X v) S Qi (v), Ty (xes v) s k(w)
KEY
Σ Exxi [[V y) S To (v),
(v), Ty (Xiet, v) S k(v)]
DEy
PP Px V(Xiesss v) I Qo (v): r (Xret: v) s R(vi
DEy
(a)
By Pxxm V(Xreas 8) 5 V (v))
(10)
8Ey
(b)
Expa [[Veeets y) - Jeluss (w)]
DEy
=Exux
[[V (Xwa: v) S Qullaa
Ex (X
(11)
yey
where the equality (a) is due to the definitions of oy. and inequality (b) is due to the assumption
Σn ooy Pxmx V(Xust: ust v) S Qutues (v)
PP
Xxx V(X y) S Quluss (w)
NEJ
WEY
This shows that RC3P requires smaller prediction sets to guarantee the class-conditional coverage compared to CCP.
B.3 Proof of Theorem 4.3
Theorem B.3. (Theorem 4.3 restated, conditions of improved predictive efficiency for RC3P) Define
D (Xr k Y + v). and (X, y) [x(X,a)+11 Denote B (F) (x) S
Qulax Y + 2] V is APS, or B = PP + < Qutey (y)lY + vl V is RAPS. If
R(t) then By S
B D (a cy
Ps
Proof. (of Theorem 4.3
Based the different choices of scoring function, first divide two scenarios:
(i): If V(X,y) is the APS scoring function, since the APS score cumulatively sums the ordered prediction of f(X): V(X,v) v) Σx((x,) f(X) it is easy verify that V y) is concave in
16

---

terms of L. As a result, we have
(xy)
((X,))
f(X) STy(X, f(X), (1ETT1 1/ry(X.011) (1)((x))) =r((X,))
f(X)
()(
س [x(
where yy(
L(ry(XX,) 2) 1)/2].
Now we lower bound Px Px[V (V(V 8) & Ti (v) as follows.
Px|V 3) T (y)
= -Y = y) PxxV y) S S (1)) / = + Pxy (Y # vl Px(V((X)) < (1
(u)lY + z
PP
21-a
PP
2B
2Py(1 - +) (1 + py -c B(v) (1 P2) py(1 BB(l) (1 - Py)
(X S k(v)) - Py - E, R(0)) + (1 - PB) D).
(12)
According to the assumption B B 2 Py (ax Ey B(()), ), we have
I-p
Px(ry(X.u) S R(y)) S Px(V(X,)) & (u
(ii) (XX,)) v) is the RAPS scoring function and ry (x(,,) 3) S kreg. then the RAPS scoring function could be rewritten V(X,y) Exr(Xx)) f(X)()) As result, we have:
(x(Xa)
V(X,v) r))
Σ f(X)
r,(X, 1=1
(x,(X,v) f(()) f(x) (1222(00))) 1/r1(Xxw1l)
(x,(X,v) ((())1((x)))
(x)(X,y) ((xx)) +x).
If (X kreeg then the RAPS scoring function could be rewritten as: V(X,y)
Σd((a0 f(X)() + X(rr(X,)) kreg). As a result, we have
(x,)
(X.v)
v(X,8)
E
f(X)() + (rr((X,y) kres)
rx(,,))
$ (x)(X,y)
(fxX) + +1(1-
krog
))
rx(X,y)
S (X,(X,)) (f(X) + +1).
Then, by applying the Inequality 12 we have:
Pxlr,(X,y) < R(y) & PxIV(X,)) S QutLts (1))
This completes the proof for Theorem
Complete Experimental Results
C.1
Training Details
For CIFAR-10 and CIFAR-100, we train ResNer20 using LDAM loss function given in 10) with standard mini-batch stochastic gradient descent (SGD) using learning rate 0.1, momentum 0.9, and weight decay 2e 4 for 200 epochs and 50 epochs. The batch size is 128. For experiments
17

---

mini- Immi-em,,eNet, we use the same setting, For Food-101 101, the batch size is 256 and other parameters are kept the same. We reported our main results when models were trained in 200 epochs. Other results are reported in Appendix C.8 and Table 11
We also evaluate the top-1 accuracy over the majority, medium, and minority groups classes as the class-wise performance when 200 epochs. To show the variation of class-wiss performance, divide some classes with the largest number data samples into the majority group, and the number of these classes is quarter (25%) of the total number of classes. Similarly, we divide the classes with the smallest number of data into the minority group (25%) and the remaining classes as the medium group (50%). In the above table, show the accuracy of three groups with three imbalance types and two imbalance ratios p = 0.1, 0.5 on four datasets.
The results are summarized in Table 4 As can seen, the group-wiss wise performance can vary significantly from high to very low. The class mass-imbalance setting is the case where the classifier does not perform very well in some classes.
Table 4: Top-1 1 accuracy minority, medium, and majority groups with three imbalance types and two imbalance ratios = 0.1, 0.5 on four datasets. We could observe that the class-wis performance varies significantly over different classes.
EXP
POLY
MAJ p=
Groups
0.5
p= 0.1
0=
0=
p= 0.1
CIFAR-IU 10
Minority
0.913
0.961
0.932
0.901
0.940
0,927
Medium
0.872
0.822
0.867
0.847
0.848
0.75
Majority
0.949
0.832
0.933
0.948
0.914
0.795
CIFAR-100
Minority Medium
0.554
0.295
0.468
0.352
0.572
0.365
0.589
0.536
0.517
0.413
0.574
0.476
Majority
0.668
0.720
0.671
0.588
0.616
0.562
mini ImageNet
Minority Medium 0.527
0.677
0.640
0.624
0.627
0.626
0.642
0.546
0.533
0.530
0.526
0.538
Majority
0.633
0.679
0.684
0.67
0.673
0.686
Food-101
Minority
0.453
0.231
0.379
0,289
0.505
0.333
Medium
0.579
0.474
0.496
0.398
0.579
0.467
Majority
0.582
0.660
0.596
0.563
0.532
0.490
C.2 Calibration Details
As mentioned in Section 5.I balanced split the validation set of CIFAR-10 and CIFAR-I00, the number of calibration data is 5000. For mini- ImageNe,, the number of calibration data is 15000. For Food-101, the total number 12625. To compute the mean and standard deviation for the overall performance, we repeat calibration experiments for 10 times. In our main results, We set = 0.1. We also report other experiment results of different a values, a 0.05 and a = 0.01, Appendix C.7 and Table TO
The regularization parameter for RAPS scoring function is from the set kreg E {3, 5, 7] and À E (0.001, 0.01, 0.1} based the empirical setting in c usstrrCC. We select the combination of kreg and for each experiment with the same imbalanced type and imbalanced ratio on the same dataset, where most of the APSS values of all methods are minimum.
The hyper-parameter g is selected from the set {0.25, 0.5, 0.75, 1.0) to find the minimal that CCP, Cluster- CP and RC3P achieve the target class-conditional coverage. We clarify that for each dataset and each class-conditional CP method, we use fixed g values. The detailed values
18

---

are displayed in Table 5 From Table 5 we could observe that the hyperparameter g for RC3P is always smaller than other methods, which means that comparing other wasss-wise CP algorithms, our algorithm needs the smallest inflation on ã to achieve the target class-conditional coverage. This cass-conditional coverage.
could also match the result of histograms
Table Hyperparameter g choices each class conditional methods CCP, cluster-aee and RC3P on four datasets CIFAR-10 10, CIFAR-10M mini-ImageNet, and Food101. We could observe that all g values are in constant order to make fair comparison. Meanwhile, the hyperparameter g for RC3P is always smaller than other methods.
Dataset
Methods
CIFAR-10
CIFAR-100
Mani-lmageNet
FOOD-101
CCP
0.5
0.5
0.75
0.75
Cluster-CP RC3P
1.0
0.5
0.75
0.75
0.25
0.5
C.3
Illustration of Imbalanced Data
(a) EXP
POLY
(c) MAJ
300
8400
300
300
300
Cass Index
Casss Index
Clsss Index
Figure 4: Illustrative examples of the different imbalanced distributions of the number of training examples per class index on CIFAR-100
C.4 Comparison Experiments Using APS Score Function
Based on the results in Table we make the following observations: (i) CCP, Cluster-CP, and RC3P guarantee the class-conditional coverage; and (ii) RC3P significantly outperforms CCP and Cluster- CCt on three datasets by producing smaller prediction sets.
19

---

Table 6: Results comparing CCP, Cluster-CP, and RC3P with ResNet-20 model and APS scoring function under different imbalance ratios p = 0.5 and p 0.1 when = 0.1. We set UCR RC3P the same as or better than that of CCP and Cluster-CP for fair comparison of prediction set size. The APSS results show that RC3P significantly outperforms Cluster-CE in terms of the average prediction set size over all settings CIF,R-100, mini-ImageNNt, and Food-101.
EXP
POLY
MAJ
Mensure
Methods
p=
p= 0.1
0=0.5
p=0.1 0.1
p=0.
p= 0.1
CIFAR-10
CCP
0,050 :: 0.016
0.100 +: 0.020
0.100 i: 0.032
0,050
0.021
0.070 +: 0.014
0.040
0.015
UCR
Cluster CP
0.010
0.009
0.090
0.009
0,080
0.019
0.060
0.001
0.020
0.012
0.070
0.014
RC3P
0.050
0.016
0.100
0.020
0.100
0.032
0,050
0.021
0.070
0.014
0.040
0.015
CCP
1.555 + 0.010
1,855 + 0.014
1,538 + 0,010
1.776 0.012
1.400 0.020
2.629
0.013
APSS
Cluster-CP
1.714
2.162 + 0.015
1,706
0.014
1.928
0.013
1.948 0.025
3.220
0.020
RC3P
1.555 0.010
18855 = 0.014
1,538
0.010
1.776 0.012
1.840 = 0.020
0.013 2.629
CIFAR-100
CCP
0.007 0.002
0.010 1 0.002
0.010 1 0,002
0.014
0.003
0.016
0.003
0.008
0.004
UCR
Cluster CP
0.012 0.002
0.066 1: 0.004
0.020 1: 0,003
0.004
0.002
0.016
0,003
0.019
0.005
RC3P
0.002 0.005
0.011 + 0.002
0.009 +: 0.003
0.015 + 0.003
0.002 0.008
0.008
0.004
44.224
0.341
50,969
49
64.343 0.237
0.535
APSS
Cluster-CP
29.238
0.609 17.705
37,592 + 0.857
38 252 0.353
52,391 + 0.595
31,518
0.335
50.883 + 0.673
RC3P
0.004
21.954 0.005
23.048 0.008
33.185 1 0.005
0.007 18.581
32.699 + 0.005
mini-ImageNNet
CCP
0.008
0.004
0.008 1 0.004
0.005 1 0.002
0.004 1. 0.001
0.010 1 0.004
0.005
0.002
UCR
Cluster-CP CP
0.014
0.004
0.012 + 0.004
0.011 + 0.003
0.014 0.003
0.008
0.002
0.010
0.003
RC3P
0.000
0.000
0.001 1 0.001
0.000 1: 0.000
0,000 0.000
0,000
0.000
0.000
0.000
OCP
26.676 + 0.171
26. 111111100 0.144
26.626
0.133
26.159 + 0.208
27.313 + 0.154
25.629 + 0.207
APSS
Cluster-CP
889
0.301
25.253 0.346
26.150
0.393
25. + 0.268
26.918
0.241
25,348 + 0.354
RC3P
18.129 0.003
17.082
0.002
17.784
0.003
17.465 + 0.003
0.002 18.111
17.167 + 0.004
Food- 101
CCP
0.006 0.002
0.006 = 0.002
0.009 = 0.005
0.008 0.001
0.006 0.001
0.008 0.002
UCR
Cluster-CP RC3P
0.003
0.002
0.009 : 0.003
0.004 : 0.001
0.009
0.002
0.011 = 0.003
0.011
0.002
0.000 0.000
0.000
0.000
0.000
0.000
0.001 0.001
0.000 0.000
0.000
0.000
CCP
27.022 0.192
30,900
30.943
0.105
27.415
36.776
0.132
APSS
Cluster CP
28.953
+ 0.333
33.375
0.377
33.079
0.393
38.301 4 0.232
30.071
4 0.412
39.632 4 0.342
RC3P
0.004 18.369
21.556
0.006
21.499 0.003
25.853 0.004
19,398
0.006
20

---

C,5 Comparison Experiments Using RAPS Score Function
With the same model, evaluation metrics, and RAPS score function 1. we add the comparison experiments with CCP, and Cluster-CP on four datasets with different imbalanced types and imbalance ratio p 0.5 and 0.1. The regularization parameter for RAPS scoring function is from the set Kreg E {3, 5, 7 and À E {0.001, 0.01, We select the combination of kyeg and for each experiment with the same imbalanced type and imbalanced ratio on the same dataset, where most of the APSS values of all methods are minimum. The overall performance is summarized in Table 7 We highlight that also select the g from the set g E {0.25, 0.5, 0.75, 1.0} to find the minimal that CCP, Cluster-Cu CP, and RC3P approximately achieves the target class conditional coverage.
Based on the results in Table 7 we make the following observations: (i) CCP, Cluster-CP, and RC3P can guarantee the class-conditional coverage; and (ii) RC3P significantly outperforms CCP and Cluster-CP CP on three datasets by producing smaller prediction sets.
Table 7: Results comparing CCP, Cluster-C3 CP, and RC3P with ResNet-20 model and the RAPS scoring function under different imbalance ratios = 0.5 and p = 0.1 when a = 0.1. The regularization parameter for RAPS scoring function is selected from the set [3, 5, 7] and [0.001, 0.01, 0.1]. We select the best results better than that of CCP and Cluster-CE for a fair comparison of prediction set size. The APSS results show that RC3P significantly outperforms CCP
for each element in the table. We set UCR of RC3P the same
and Cluster-Ot CP in terms of average prediction set size over all settings on CIFAR- 100, mini- Mini-ImageNNt, and
Food- 101.
Mensure
Methods
EXP
POLY
MAJ
p
p 0.1
0.5
p= 0.1
p 0.5
p= 0.1
CIFAR-10
CCP Cluster-CP RC3P
0.050 0.016
0.010 = 0.020
0,100 = 0.028
0.050 = 0.021
0.070 = 0.014
0.040 = 0.015
UCR
0,010 0.009
0.010
0.010
0,080
0.019
0.060 0.015
0,020
0.025
0.070 0.014
0,050 :: 0.016
0.010 = 0.020
0.100 = 0.028
0.050 = 0.021
0.070 = 0.014
0.040 = 0.015
CCP
1.555 0.010
1855 1 0.014
1.538
0.010
1.776
0.012
1.840
0.020
2.632
0.012
APSS
Cluster-CP
1.714 0.018
2.162 = 0.015
1.706 = 0.014
1.929
0.013
1.787 = 0.019
2,968
0.024
RC3P
1.555 0.010
1,855 1 0.014
1,538
0.010
1,776 0.012
0.020 1.840
2.632
0.012
CIFAR- 100
OCP
0.007 + 0.002
0.011 + 0.002
0.010 + 0,002
0.015 0.003
0.015 + 0,003
0.008
0.004
UCR
Cluster-CP
0.012 +: 0.002
0.017 + 0.004
0.019 + 0.004
0.034 = 0.005
0.008 = 0.003
0.018 0.006
RC3P
0.005 0.002
0.002 0.011
0.003 0.009
0.003 0.015
0.015 0.003
0.008 0.004
CCP
44.250 = 0,342
50,970 = 0.345
49.886
0,353
64.332 + 0.236
48.343 = 0.353
64.665 + 0.535
APSS
Cluster-CP
29.267 = 0.612
37.795
0.862
38.258 0.320
52,374 1 0.592
31.513 = 0.325
50,379 1 0.684
RC3P
17.705 0.004
21.954 0.005
23.048 0.008
33.185
1 0.005
18.581
0.006
32,699
0.006
mini ImageNet
OCP
0.008 + 0.003
0.009 + 0.004
0.005 + 0.002
0.004 + 0.002
0.009 + 0.003
0.005
0.002
UCR
Cluster-CP RC3P
0.006 0.002
0.013 0.005
0.009 = 0.003
0.016
0.007
0.002
0.009
0.004
0.000 i: 0.000
0.001 = 0.001
0.000 : 0.000
0.000 = 0.000
0.000 = 0.000
0.000 = 0.000
CCP
26.756 = 0.178
26.212
0.199
26.689
0.142
26.248 + 0.219
27.397 = 0.162
25.725-5 + 0.214
APSS
Cluster-CP
26.027 1: 0.325
25.415
0.289
26. 08.288822 0.407
25.712 1 0.315
26.969
0.305
25.532 1 0.350
RC3P
18.129 0.003
17.082
0.002
17.784 0.003
17.465
1. 0.003
18.111
0.002
17.167 1. 0.004
Food-101
OCP
0.006 0.003
0.006 + 0.002
0.009 + 0.003
0.008 0.001
0.006
0.002
0.008
0.002
UCR
Cluster-CP RC3P
0.004 :: 0.003
0.012 = 0.004
0.006 = 0.002
0.006 = 0.003
0.011 = 0.003
0.014 = 0.004
0.000
0.000
0.000 = 0,000
0.000 0.000
0,001 0.001
0.000 0,000
0.000
0.000
CCP
27.022 = 0.192
30,900 0.170
30.966 0.125
35.940 1: 0.111
27.439
0.203
36.802 + 0.138
APSS
Cluster-CP
28.953 0.333
33.375 0.377
33.337
0.409
38,499
+ 0.216
29.946
0.407
39.529 + 0.306
RC3P
18.369 0.004
21.556: 0.006
21.499 0.003
25.853 1 0.004
19.397 0.006
26.585 + 0,004
C.6
Comparison Experiments Using HPS Score Function
With the same model, evaluation metrics, and HPS score function D. we add the comparison experiments with CCP, and Cluster-CE CP on four datasets with different imbalanced types and imbalance ratio p 0.5 and p 0.1. The overall performance is summarized in Table g We highlight that we also select the g from the set g E (0.25, 0.5, 0.75, 1.0) to find the minimal y that CCP, CP, and RC3P approximately achieves the target class conditional coverage.
21

---

Based on the results in Table we make the following observations: (i) CCP, Cluster-CP, and RC3P can guarantee the class-conditional coverage; and (ii) RC3P significantly outperforms CCP and Cluster-CP on three datasets by producing smaller prediction sets.
Table 8: Results comparing CCP, wwwster-ucceec and RC3P with ResNet-20 model and the HPS scoring function under different imbalance ratios p 0.5 and p 0.1 when 0.1. We set UCR of RC3F the same as better than that of CCP and Cluster-CC CP fair comparison prediction set size. RC3P significantly outperforms
CCP and Cluster-CF with 20.91% % (four datasets) or 27.88% (excluding CIFAR-10) reduction in APSS.
Measure
Methods
EXP
POLY
MAJ
p=0
p= 0.1
0=5
P=
p=0.
==
CIFAR-10
CCP
0.050 1.300.10000 0.016
0.010 1 0.020
0.100 1. 0.028
0.050
0.021
0.070
0.014
0.040
0.015
UCR
Cluster-CP
0.010
0.009
0.010 + 0.010
0,080 + 0.019
0.000
0.015
0.020
0.025
0.070
0.014
RC3P
0,050 +0 0.016
0.010 = 0.020
0,100 + 0.028
0.050 = 0.021
0.070 = 0.014
0.040
0.015
OCP
1.144 0.005
1.324 + 0.007
1.137 + 0.003
1.243 0.005
1.272 0.008
1.936
0.010
APSS
Cluster-CP
1.214 0.008
1.508 = 0.010
1.211 = 0.004
1.354 = 0.005
1.336 = 0.009
2.312 0.025
RC3P
1.144 0.005
1.324 1 0.007
1.137 1 0.003
1.243 0.005
1.272 :: 0.008
1.936
0.010
CIFAR-100
CCP
0.007 0.002
0.011 1 0.002
0.010 1: 0,002
0.015
0.003
0.015
0,003
0.008
0.004
UCR
Cluster-CP
0.012 +: 0.002
0.017 + 0.004
0.019 + 0.004
0.034 + 0.005
0.008 + 0.003
0.018
0.006
RC3P
0,005 0.002
0.011 0,002
0.009 0.003
0,015
0.003
0.015 0.003
0.008
0.004
OCP
41.351 = 0.242
49,469
0.344
48 063 0.376
63.963 + 0.277
46.125 + 0.351
64,371 + 0.564
APSS
Cluster-CP
27.566 = 0.555
35.528
0.979
36.101 0.565
51.333 + 0.776
29.323 0.363
50,519 + 0.679
RC3P
20,363 0.006
25.212 0,010
25.908 0.007
36,951 + 0.018
21.149 0.006
35.606 + 0,005
mini-ImageNNe
CCP
0.008
0.003
0.009 + 0.004
0.005 + 0.002
0.004
0.002
0.009
0.003
0.005
0.002
UCR
Cluster-CP RC3P
0.006
0.002
0.013 1 0.005
0.009
1 0.003
0.016
0.001
0.007
1: 0,002
0.009
0.004
0.000
0.000
0.001 + 0.001
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
CCP
24.633 0.212
24.467
24.379
24.472
0.167
25.449
0.159
APSS
Cluster-CP
23.911 + 0,322
24.023
+ 0.195
24.233 + 0.428
23.263 + 0.295
24.987 + 0.319
23.323 + 0.378
RC3P
17,830
0.104
17.036
0.014
17.684 0.062
17.393 + 0.013
18,024
0.049
17.086 + 0.059
Food-101
CCP
0.006 +: 0.003
0.006 = 0.002
0.009 = 0.003
0.008
0.001
0.006 = 0.002
0.008
0.002
UCR
Cluster CP
0.004
1. 0.003
0.012 1 0.004
0.006
1. 0,002
0.006
0.003
0.011
0.003
0.014
0.004
RC3P
0.000
0.000
0,000
0.000
0.000
0.000
0,101
0.001
0.000
0.000
0.000
0.000
CCP
26.481 a. 0.142
30,524
0.152
30.787
0.099
35.657 1: 0.107
26.826
1: 0.163
36.518 1 0.122
APSS
Cluster-CP
29.347
0.288
33.806
0.513
33.407
0.345
38,956
0.242
29.606
0.436
39,880
0.318
RC3P
18.337 0.004
21,558= 0.006
21.477 0.003
25.853 + 0,005
19,396
0.008
26.584 + 0,003
C.7
Comparison Experiments with different a values
With the same model, evaluation metrics, and scoring functions, add the comparison experiments with CCP, and C1 ussuer-CP on four datasets with different imbalanced types and imbalance ratio p 0.5 and p 0.1 under the different a values. The overall performance summarized in Table g and 10 with a = 0.03 and a = 0.01, respectively. We highlight that we also select the g from the set g E 0.15,, 0.75] with 0.05 range to find the minimal g that CCP, Cluster-CP, and RC3P approximately achieves the target class conditional coverage.
Based on the results in Table 7 we make the following observations: (i) CCP, Cluster-CP- and RC3P can guarantee the class-conditional coverage; and (ii) RC3P significantly outperforms CCP and Cluster-CP on three datasets by producing smaller prediction sets.
22

---

Table 9: APSS results comparing CCF, Cluster-CP, and RC3P ResNet-20 model under different imbalance ratio 0.5 and = 0.1 where a 0.05. For a fair comparison of prediction set size, we set UCR of RC3P the same as smaller (more restrictive) than that of CCP and Cluster-CP under 0.16 on CIFAR-10 10 and 0.03 on other datasets. The APSS results show that RC3P significantly outperforms CCP and Cluster-CP in terms of average prediction set size with 21 21.036% (four datasets) 28.048% (excluding CIFAR-10) reduction in prediction size on average over min CCP, & cluster-C.).
Conformity Soore
EXP
POLY
MAJ
0.5
0.1
0=
0.1
p= 0.5
0.1
CIFAR-10
CCP
2,861
0.027
3.496 + 0.037
2.744
0.033
3,222 + 0.018
3.269 + 0.037
4,836
0.035
APS
Cluster-CP
3.443
4.551
0.037
0.039
4,075
5,958
0.070
RC3P
2.861
0.027
3.496
0.037
2.744
0.033
3.222
0.018
3.269
0.037
4.8%
0.035
CCP
2,833
0.018
3,448
0.036
2.774
0.033
3,231
0.021
3,301
0.024
4.842
0.037
Clusta-CPP
3,430
0.044
4,389
0.062
3.352
0.035
5,876
0.034
4,044
0.055
5,959
0.083
RC3P
2,833
0.018
0.036 3.448
2.774
0.033
3,231
0.021
3.301
0.024
4.842
0.037
CCP
44,019
0.295
51,004
0,366
49.564
0.315
64.314
0.231
48.024
0,386
64.941
0.532
Cluster RC3P
32.128
0.011
38.769
0.006
39.930
0.008
53.147
0.010
34.361
0.007
51,498
0.009
CCP
44,234
64.339
RAPS
Cluster
39,212
0.365
46.840
0.186
0.280 39,871
49,094
62.095
0.278
0.323 34.380
41.596
60.158
0.536
RC3P
32,135
0.010
38,793
0.007
0.010
$3.169
0.009
0.007
51,512 0.008
Ming-Tnnge-Ner
CCP
58.527
0.445
57.527
0.408
60.327
0.520
56.581
0.438
59.360
0.430
56.636
0.469
Cluster-CP
47.613
0.544
0.699
47.117
0.930
45,360
0.582
59,002
0.434
0.456
RC3P
32.046
: 0.102
31.729
0.003
31,718 :: 0.004
32,048
0.003
32,909
0.007
31.441
0.004
CCP
57.626
60.173
56.702
59.532
RAPS
Cluster-CP
47.421
= 0.588
46.767
0.724
47.302 +: 1.126
45 603 0.639
59 408
0.482
56.779 :: 0.486
RC3P
32,040
0,003
31,741
0.003
31,752
0,003
32,067
0.002
32,914 0.005
31,417 0.005
Food-101
CCP
55.967
0.464
60.374
0.383
60.717
01.96
65.698
0.405
56.934
0.446
66.654
0.511
APS
Cluster RC3P
48.699
0.512
55.288
0.815
54,063
0.885
60.104
0.608
48.894
0.919
59 432
0.754
31,224
0.004
35,273
0.007
38.364
0.003
41,109
0.005
31.661
0.005
39,135
0.003
0.579
$6.982
RAPS
Cluster CP
48,371
1: 0.513
55.155
0.775
53,813
1. 0.864
59.912
0.530
49.259
0.846
59.307 0.648
RC3P
31,229
0.004
35.283
0.006
35.379
0.003
41.113
0.005
31,631
0.004
39.118 0.003
23

---

Table 10: APSS results comparing CCP, Cluster-C2, RC3P with ResNet-20 model under different imbalance ratio 0.5 and p 0.1 where a 0.01. For a fair comparison of prediction set size, we set UCR of RC3P the same as smaller (more restrictive) than that of CCP and Cluster-CP under 0.16 on CIFAR-10 and 0.03 on other datasets. The APSS results show that RC3P significantly outperforms CCP and cluster-CP in terms of average prediction set size with 16.911% (four datasets) 22.549% (excluding CIFAR-10) reduction in prediction size on average over min (CCP, cl cluster-C.).
Conformity
EXP
POLY
MAJ
p= 0.5
0.1
0.5
0.1
p= 0.5
0.1
CIFAR-I0
CCP
7,250 + 0.166
7.387 + 0.116
7.173 + 0.079
7.596
+ 0.109
7.392 + 0.128
8,864
0.108
APS
Clustar-P
5.528
0.060
6,954
7.5%
0.054
RC3P
5.671
0.046
7.387
0.116
6.309
0.042
7.276
0.010
6.779
0.013
8.864
0.108
CCP
7.294
0.160
7.458
0.101
7.067
0.106
7.597
0.096
7.547
0.134
8.884
0.106
Clusta-CPP
5,568
8,288
0.118
6.867
0.078
7,795
0.136
7,813
0.142
9,239
0.055
RC3P
5.673
0.040
7.458
0.101
6.310
0.046
7.253
0.006
6.780
0.015
8.884
0.106
CCP
100.0 +:
100,0 +: 0.0
100,0 1: 0.0
100.0 1: 0.0
100.0 1:
100.0 1 0,0
Cluster RC3P
$8.621
0.007
63.039
0.007
60.258
0.005
74.927
0.007
100.0
100.0 0.0
100.0
100.0
RAPS
Cluster 65.584
0.508
69.373
0.466 63,021
66.313
0.745
82.043.1 0.439 74.885 0.006
100.0
100.0 0.0
RC3P
55.632
0.008
0.006
60.205 0.006
100.0 + 0.0
100.0 0.0
mini-InageNer
CCP
100.0 1
100.0 + 0.0
100,0 1 0.0
100.0 +: 0.0
100.0 1 0.0
100.0 1: 0.0
Cluster-CP
74.019
0.699
71,300
75.546 0.683
70.996
0,702
74.508
0.531
72,803
RC3P
55.321 :: 0.103
54.214 0.004
$6.018 : 0.106
53.732 0.004
54.483 :: 0.007
53.522
0.005
CCP
100.0
100.0
100.0
RAPS
Cluster-CP
73,893
0.734
0.657 $4,184
70.638
75.546 + 0.683
71,098
0.706 $3.736
74.675 = 0.578
73.345
0.474
RC3P
55,270
0,003
0.003
56.733
0,006
0.004
55,304 0,004
53,532 0.005
Food-101
CCP
101.0
101.0 0.0
101.0
101.0 0.0
101.0
101.0 0.0
Cluster RC3P
81.489
0.957
87,092
0.588
82.257 -1 0.514
86.539
0.453
83.293
0.583
0.401
67.443 + 0.004
$7.055
0.005
57,722 0.006
62.931
0.005
68.267 0.005
65.413 + 0.005
RAPS
Cluster CP RC3P
81.505 :L 0.955
0.587 $7.069
87.103
82,272
0.513
0.455 62.938
86.517
83.367 1: 0.635
88.604
0.404
67.444
0.004
0.005
87.722
0.006
0.004
68.266
0.003
65.487 0.006
24

---

C.8 Comparison Experiments when models are trained in different epochs
With the same loss function, training criteria, evaluation metries, and two scoring functions, we add the comparison experiments with CCP, and Cluster- -CP on four datasets with different imbalanced types and imbalance ratio p 0.5 and p 0.1 and a 0.1 when models are trained with 50 epochs. The overall performance is summarized in Table 11 We highlight that we also select the g from the set g E {0.25, 0.5, 0.75, 1.0} to find the minimal g that CCP, Cluster-CP, and RC3P approximately achieves the target class conditional coverage.
Based on the results in Table we make the following observations: (i) CCP, C1 Cluster-CP, and RC3P can guarantee the class-conditional coverage; and (ii) RC3P significantly outperforms CCP and Cluster-CP on three datasets by producing smaller prediction sets.
Table 11: APSS results comparing CCP, Clustcr-C2, and RC3P with ResNet-20 model under different imbalance ratio م = 0.5 and 0.1 where a = 0.1 and models are trained with 50 epochs. For fair comparison of prediction set size, set UCR of RC3P the same of CCP and Cluster-CP under 0.16 CIFAR-10 and 0.03 other datasets. The APSS results show that RC3P significantly outperforms CCP and Cluster- --P terms average prediction set size with 21 21.441% (four datasets) or 28.588% (excluding CIFAR-10) reduction in prediction size on average over min (CCP, c cluster-CP).
smaller (more restrictive) than that
Conformity Score
Methods
EXP
POLY
MAJ
p=
p=
0.5
p=
p=
p
CIFAR-I0
CCP
2.420
2.661
0.015
2.399
2.519
2.651
4.053
0.021
APS
Cluster-CP
4.006
= 0.019
3,574 = 0.023
3.144 = 0.020
2.994 = 0.009
3.698 2: 0.044
5,290 = 0.016
RC3P
2.420
0,019
2,661
0,015
2.399
0,013
2,519
0,022
2.651 0.031
4,053
0,021
CCP
2.096
0.014
2.533
0.019
2.383
0.026
2.247
0.017
2.232
0.019
3,233
0.021
RAPS
Cluster-CP
2.625
0.017
3,099
= 0.021
2,840 = 0.043
2,843
0.026
2.770 = 0.025
3,961
0.029
RC3P
2.096
2.533
0.019
2.383
2.247
0.017
2.232
3,233
0.021
CIFAR-100
CCP
52.655
0.473
54,523
0.441
61,768
52.119 0.197
APS
Cluster CP
42,990
1: 0.655
43,275
0.833
44.114 1: 0.458
58,226
0.627
39,841 1 0.836
53.409
0.520
RC3P
24.872
0.008
25.107
0.006
27.757
0.004
35.733
0.010
24.496
0.010
32,172
0.007
CCP
52,662
0.473
$2.841
0.307
54.528
01442
61.766
0.195
52.129
0.197
58.331
0.299
RAPS
Clusten CP RC3P
43.024
0.648
43.277
0.839
44.120
0,458
58,212
0.629 35,733
39,864
0,845
53.402
0.518
24,872
0.008
25.107
0.006
27.757
0.004
24.496
0.010
32,173
mini- Imageee
CCP
42,404 = 0.213
41.154
0.191
38.433
0.248
36.363 0.228
36,047 0.191
37,600 0.208
APS
Cluster-CP
42.006
0.430
41.101 0.224 31,909
0.273 28.460
39.016
36,046
0.467
35,721
0.355
37,975
0.559
RC3P
32,022
0.005
0.003
26.383
26.128
0.005
28.127
CCP
42,516 :: 0.215
37,552
= 0.192
38.730 :: 0.218
37.80
:: 0.186
36.595 2: 0.244
36.057 1: 0.206
RAPS
Cluster-CP
42.231
0.386
37,448
0.332
38.602 0.327
37,939 0.309
36.351
0.308
35.724 0.242
RC3P
32,022
1 0.005
29.114 0.004
28.197
0.006
27.626 0.004
25,853
0.003
0.003 25,948
Food-
CCP
41,669
0.118
51.395
0.247
44,261
0.165
58.816
0.162
$2.672
0.169
57,312 0.162
APS
Cluster-CP
44,883
0.336
54,684
0.475
47.794
0,420
60.727
0,178 49.299
56. 100
0.257 43,680
60,200
0.543
RC3P
31,987
0.005
34,576
0.006
0.005
47.649
0.006
CCP
41,503 + 0.157
0.107 $1,091
48.548
44,288
0.165
56.592
0.165
47.264
0,120
56 666
0.160
RAPS
Cluster-CP
44.810
0.565
0.375
47,861
0.428
0.306
50.211
0.474
60.183 0.507
RC3P
34.240 0.115
36.425 0.024
0.006 34.576
46.074
0.004
37.055
0.006
48.012 0.076
C.9
Comparison Experiments with UCG metrics
We add the experiments without controlling coverage on imbalanced datasets under the same setting as the main paper. We then use the total under coverage gap (UCG, J. better) between class conditional coverage and target coverage 1 - of all under covered classes. We choose UCG as the metric to differentiate the coverage performance in our experiment setting. Conditioned on similar APSS of all methods, RC3P significantly outperforms the best baselines with 35. 18..urrfour datasets) or 46.91 % (excluding CIFAR (oreutinn in UCG on average.
25

---

Table 12: UCG and APSS results comparing CCP, Cluster-CP, and RC3P with ResNet-20 model trained with 200 epochs under different imbalance types with imbalance ratio 0.1, where the coverage of each method are aligned. The APSS results show that RC32 outperforms CCP and cluster-Ce average prediction set size with 1.64%(four datasets) or 2.19% (excluding CIFAR- 10) reduction prediction size on average over min (CCP, cluster-CP]. The UCG results show that RC3Pachieve the similar class conditional coverage CCP and Cluster-CE in terms of with 35.18 35.18%(four datasets) or 46.91% (excluding CIFAR- 10) increment in the proportion of under coverage classes average over CCC, cluster-CP
terms of
Conformity Score
Methods
EXP
POLY
MAJ
UCG
APSS
UCG
APSS
UCG
APSS
CIFAR-10
CCP
0.014 =: 0.000
1.573 1 0.009
0,032 1 0.000
1.494 1: 0.015
0.068 0.000
2.175 1: 0.019
APS
Cluster-CP
0.166 0.000
0.124 0.000
1.280
0.007
2,079
RC3P
0.014 = 0.000
1.533 = 0.009
0.032 = 0.043
1 + 0.015
0.068
0.031
2.175 + 0.019
0.000
0.032
RAPS
Cluster-CP
0.166 = 0.000
1438 = 0.012
0.124 = 0.000
1.280 + 0.007
0.144
0.000
2.079 = 0.023
RC3P
0.014 0.050
0.009
0.032 0.000
+ 0.015
0.070
0.000
2.179
CIFAR-100
2,000
APS
Cluster-CB CP
1,500 1. 0.000
15.657 1 0.417
2.580 1. 0.000
26,709
0.422
2.660 0.000
25.145 0.385
0.000
CCP
1.920
0.000
16.724 + 0.1
2,020 + 0.000
26.817
0.155
2.400
0.007
26.199
0.216
RAPS
Cluster-CP
RC3P
0,840 = 0.000
14.642 1 0.005
1.200 =: 0.000
24.480 1: 0.004
1.460
0.000
23.332 : 0.006
mini Imageem
CCP
1.486
0.000
10.525 1 0.093
1.620 1. 0.000
11,188
0.094
1,280
0.000
10.642
0.055
Cluster-CP
1.313 = 0.000
11.133
1: 0.118
1.453
1: 0,000
11.547
0.129
1.640
0.000
11.186
0.151
RC3P
0,713 = 0,000
10.360 + 0.042
0.653
= 0,000
11,089
0.052
0,600
0,000
10,545
0.029
CCP
1.526
0.000
10.570 1. 0.093
1.620
0,000
11.250
0.095
1.293
0.000
10.702
0.055
RAPS
Cluster-CP
1.480
0.000
11.192
1 0.123
1.513
+ 0.000
11.704
0.124
1.586
0.000
11.231
0.156
RC3P
0.713 0.000
10.377 + 0.035
0.653
0.000
11.126
0.046
0.000 0.600
10.571
0.021
Food-101 101
OCP
1.176 = 0.000
14.019 + 0.064
1.208 + 0.000
17. 17,288
+: 0.075
1.748
0.000
17.663 + 0.076
APS
Chister-CP
1,296
0.000
13.998
4 0.107
1.704
+ 0.000
17.300
0.183
2.148
0.000
17.410
0.130
RC3P
0.000 0.556
13.564 1 0.003
0.664
0.000
16.608
0.006
0.000 0.924
16.890
0.005
CCP
1,160
0.000
14.019
0.064
1.208
0.000
17.301
0.075
1,764
0.000
17.679
0.076
RAPS
Cluster-CP
1.308
0.000
14,080
1: 0.113
1.804
1: 0.000
17.370
0.198
1.944
0.000
17.488
038
RC3P
0.556
0,000
13.564 1 0.003
0.664 1: 0,000
16.608
0.006
0.924
0,000
16.890
0.005
26

---

C.10 Complete Experiment Results on Imbalanced Datasets
In this subsection, we report complete experimental results over four imbalanced datasets, three decaying types, and five imbalance ratios when epoch 200 and a 0.1. Specifically, Table [3]
14
report results on CIFAR-10 with three decaying types. Table [6] 17 18 report results on
CIFAR- 100 with three decaying types. Table 19 20 21 report results mini- ImageNer with three report results on Food- 101 with three decaying types.
decaying types. Table 22
23
Figure Figure 6 Figure 7 Figure 8 and Figure 9 show the class-conditionall coverage and the corresponding prediction set sizes on EXP p = 0.5, POLY p = 0.1, POLY 0.5, MAJ = 0.1,
MAJ p = 0.5, respectively. This result EXP p 0.1 is in Figure 1
Figure 10
Figure 11 Figure 12
Figure 13 and Figure 14 illustrates the normalized frequency
distribution of label ranks included in the prediction sets on EXP p = 0.5, POLY P = 0.1, POLY 0.5, MAJ p 0.1, MAJ 0.5, respectively. This result on EXP evident that the distribution of label ranks in the prediction set generated by RC3P tends to be lower compared to those produced by CCP and Cluster-CP Furthermore, the probability density function tail for label ranks the RC3P prediction set is notably shorter than that of other methods. This indicates that RC3P more effectively incorporates lower-ranked labels into prediction sets, result of its augmented rank calibration scheme.
0.1 is in Figure 2 It
Figure 19 verify the condition numbers By when models are fully trained (epoch 200) on EXP 0.5, POLY p 0.1, POLY p 0.5, MAJ 0.1, MAJ p 0.5, respectively. This result on EXP p = 0.1 in Figure Figure 3 We also evaluate the condition numbers σ, when models are lessly trained (epoch = 50) and a U. EXP = 0.5, EXP p = 0.1, POLY 0.1, POLY P = 0.5, MAJ p = 0.1, MAJ = 0.5, respectively. These results are shown from Figure 21 to Figure 25 These results verify the validity of Lemma 4.2 and Equation and confirm that the optimized trade-off between the coverage with inflated quantile and the constraint with calibrated rank leads smaller prediction sets. They also show stronger condition (o,, S 1 for all y) than the weighted aggregation condition in ()) They also confirm that the condition number {o could evaluated on calibration datasets without testing datasets and thus decreases the computation cost. We notice that RC3P degenerates to CCP on CIFAR-10, so By for all y and there is no trade-off. On the other three datasets, we observe significant conditions for the optimized trade-off in RC3P.
Figure 15
Figure 16 Figure 17 Figure 18
Table 13: Results comparing CCP, cl cluteer-CP, and RC3P with ResNet-20 model under different imbalance ratio 0.5, = 0.4, = 0.2, and = 0.1 with imbalance type EXP and two scoring functions, APS and RAPS, dataset CIFAR- 10. We set UCR of RC3P the same as or better than that of CCP and Cluster-CP for fair comparison of prediction set size.
Scoring function
Measure
Methods
EXP
p= 0.5
0= 0.4.4
p= 0.3
p= 0.2
0.2
A= 0.1
CCP
0.050
0.016
0.06 0.021
0.050 1: 0.016
0.050
0.021
0.100
0.020
UCR
Cluster-CP
0.010
0.009
0,050 0.021
0.0 1 0.0
0.030
-: 0.015
0.090
0.009
RC3P
0.050 1: 0.016
0.06 +: 0.021
0.050 1 0.016
0.050
0.021
0.100 1 0.020
APS
CCP
1,555 0.010
1.595 = 0.013
1,643 0.008
1676
1.855
APSS
Cluster-CP
1.714 + 0.018
1.745 1 0.018
1.825 1 0.014
1.901 1 0.022
2.162 0.015
RC3P
1,555 = 0.010
1,595 + 0.013
1.643 = 0.008
1.676 - 0,014
1.855 - 0.014
CCP
0.050 1 0.016
0.060 1 0.021
0.050 1 0.016
0.050 1 0.021
0.010 1 0,020
UCR
Cluster-CP
0.010
0.010
0.050
+ 0.021
0.000 + 0.000
0.030 + 0.014
0.010 + 0.010
RC3P
0.050
1: 0.016
0.060 1 0.021
0.050 1 0.016
0.050 : 0.021
0.010 + 0.020
RAPS
CCP
1,555
0,010
1,395 1 0.013
1.643 1 0.008
1.676 1 0.014
18855 1 0.014
APSS
Cluster-CP
1.714
0.018
1.745
1 0.018
1.825 1 0.014
1.901 1 0.022
2.162 1 0.015
RC3P
0.010 1,555
1.595
0.013
1.643 + 0.008
1.676 0.014
1.855 0.014
27

---

Table 14; Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalance ratio p 0.5, p 0.4, p 0.2, and p 0.1 with imbalance type POLY and two scoring functions, APS and RAPS, dataset CIFAR-I0 10. We UCR of RC3P the same as or better than that of CCP and cluster-CP for a fair comparison of prediction set size.
Scoring function
Mcasure
Methods
POLY p= 0.3
0.5
p = 0.4
p. 0.2
p= 0.1
CCP
0.100 1: 0.028
0.060 1 0.026
0.060 1 0.015
0.050
1 0.021
0.050 1: 0.021
UCR
Cluster-CP
0.080
0.019
0.050 + 0.021
0.050 + 0.025
0.050
0.016
0.060 + 0.015
RC3P
0.100 0.028
0.060 1: 0.026
0.060 1
0.050
0.050
0.021
APS
CCP
L338 0.010
1,546 0.011
1,500 0.014
L627
1,76=
APSS
Cluster-CP
1.706 0.014
1.718 +: 0.014
1,758 +: 0.016
1.783
0,016
1,928 - 0,013
RC3P
1,538 0.010
1.546 = 0.011
1,580 = 0.014
1.627 = 0,011
1.776 = 0.012
CCP
0.100 0.028
0.060 + 0.025
0.060 + 0.016
0.050
0.021
0.050
0,021
UCR
Cluster-CP
0.080
0.019
0.050 + 0.021
0.050 + 0.025
0.050 + 0.016
0.060 + 0.015
RC3P
1.100 + 0.028
0.060 1 0.025
0.060 1 0.016
0.050
+ 0.021
0.050 + 0.021
RAPS
CCP
1,538
0.010
1.346 1 0.011
1,581 1 0.014
1.627
0.011
1,776 1 0,012
APSS
Cluster-CP
1.706
1 0.014
1.719
1 0.014
1.759
1 0.016
1.783 1 0.016
1.929 + 0.013
RC3P
1,538
0.010
1.546 + 0.011
1.581 0.014
1.627
0.011
1.776 0.012
Table 15: Results comparing CCP, cluster-CF, and RC3F with Re model under different imbalance ratio 0.5. 0.4, p 0.2, and p = 0.1 with imbalance type MAJ and two scoring functions, APS and RAPS, dataset CIFAR-IO. We UCR of RC3P the same or better than that of CCP and Cluster-CP for a fair comparison of prediction set size.
Scoring function
Mcasure
Methods
MAJ p= 0.3
p 0.5
p= 0.4
0=2 0.2
0=0.1
CCP
0.070 = 0.014
0.050 + 0.016
0.080 = 0.019
0.070 0.025
0.040 = 0.015
UCR
Cluster-CP
0.020 0.012
0.040 + 0.015
0.020
= 0.013
0.010 = 0.010
0.070 = 0.014
RC3P
0.070 + 0.014
0.050 1 0.016
0.080 1 0.019
0.070
0.040
0.015
APS
CCP
1.4 0.020
1,255 0.014
1,939 F 0.016
2.04
2629 0.013
APSS
Cluster-CP
1948 0.023
1.999 + 0.027
2.167 = 0.030
2.457
0.021
3.220 0.020
RC3P
1.84 = 0.020
1.825 + 0.014
1,939 = 0.016
2.054 + 0.013
2.629 = 0.013
CCP
0.070 0.014
0,050 + 0.016
0.080 = 0.019
0.070 + 0.025
0.040
0.015
UCR
Cluster-CP
0.020 0.013
0.040 1 0.015
0.020 1 0.012
0.010 1 0.010
0.070 1 0.014
RC3P
0.070 1 0.014
0.050 1 0.016
0.080 1 0.019
0.070 1 0.025
0.040 1 0.015
RAPS
CCP
1840 + 0.020
1825 1 0.014
1,940 1 0.016
2.055 1 0.013
2.632 1 0,012
APSS
Cluster-CP
1.988 = 0.023
1.999
+ 0.028
2.168
- 0.030
2.458
- 0.021
3.219 - 0.030
RC3P
1.840 0.020
1.825 + 0.014
1.940 = 0.016
2.055 - 0.013
2.632 = 0.012
Table 16: Results comparing CCP, cluster-CE, and RC3F with ResNet-20 model under different imbalance ratio p 0.5, p 0.4. p 0.2, and p 0.1 with imbalance type EXP and two scoring functions, APS and RAPS, on dataset CIFAR-100. We set UCR RC3P the same as or better than that CCP and cluster-Cr for a fair comparison of prediction set size.
Scoring function
Measure
Methods
EXP
e 0.5
p= 0.4
0=
p= 0.2
p= 0.1
CCP
0.00741 0.002
0.0174 0.004
0.0124: 0.004
0.015 0.003
0.010 0.002
UCR
Cluster-CP
0.012 0.002
0.0124: 0.003
0.006:: 0.002
0.035 0.008
0.0161: 0.004
RC3P
0.005= 0.002
0.009 0.001
0.011# 0.003
0.013 0.003
0.01
0.002
APS
CCP
44.224+ 0.341
44,486
0.420
47.672+
0.463
46.955+
0.402
50.969+
0.345
APSS
Cluster-CP
29.238 0.609
30.602-
0.553
32. 32.126-: 0.563
33.714-t:
0.863
37.5924:
0.857
RC3P
17.7051: 0.004
18.311
0.005
19.608 0.007
20.675
0.005
21.9541: 0.005
CCP
0.007:1 0.002
0.01741 0.004
0.012+ 0.003
0.015 0.003
0.011= 0.002
UCR
Cluster-CP
0.011 0.003
0.009:: 0.002
0.006 0.002
0.034 0.007
0.017 0.004
RC3P
0.005= 0.002
0.012+ 0.003
0.01 0.003
0.013+ 0.003
0.011 0.002
RAPS
CCP
44.2501 0,342
44.499
0.420
47.688 0.569
46.96011 0.404
50.9701 0.345
APSS
Cluster-CP
29.267+ 0.612
30.595 0.549
32, 161 = 0.564
33.713+ 0.864
37.595 0.862
RC3P
17.705: 0.004
18.311 0.005
19.609 0.007
20.675:1 0.005
21.9541: 0.005
28

---

Table 17: Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalance ratio p 0.5, p = 0.4, p 0.2, and p 0.1 with imbalance type POLY and scoring functions, APS and RAPS, on dataset C10. We set UCR RC3P the same as or better than that CCP and cluster- C for a fair comparison of prediction set size.
Scoring function
Measure
Methods
POLY p= 0.3
p 0.5
p
p
p = 0.1
CCP
0.010= 0.002
0.008: 0.002
0.016= 0.003
0.012= 0.004
0.014 0.003
UCR
Cluster-CP CP
0.020 0.003
0.020= 0.002
0.026 0.004
0.009+ 0.003
0.034+ 0.005
APS
RC3P
0.009: 0.003
0.0054 0.002
0.0134 0.004
0.011 0.004
0.015 0.003
CCP
49,889+ 0.353
54.01T= 0.466
56,031 0.406
59,888E 0.255
6,237
APSS
Cluster-CP
38,252-1 0.316
39,58511 0.545
43,310 0,824
47,461 0.979
$2.391 0.595
RC3P
23.048:: 0.008
24.335:: 0.005
26.366: 0.010
28.887
0.006
33.829 0.005
CCP
0.010 0.002
0.008 0.002
0.016 0.003
0.012 0.004
0.015 0.003
UCR
Cluster-CP
0.019 0.004
0.020 0.002
0.026 0.005
0.009 0.003
0.034: 0.005
RAPS
RC3P
0.0091 0,003
0.005: 0,002
0.013 0,004
0.011 0.004
0.015 0.003
CCP
49,88611 0,353
53.9941 0.467
$6.020 0.406
59,870 0.253
64.332- 0.236
APSS
Cluster-CP
38.258-1 0.320
39. 566:1 0.549
43. 33.304-t 0.549
47 450- 0.969
$2.374 0.592
RC3P
23.048+ 0.008
24.335+ 0.005
26.366
28.886 0.006
33.185 0.005
Table 18: Results comparing CCP, cluster-CF. and RC3P with ResNet-20 model under different imbalance ratio 0.5. 0.4, = 0.2, and = 0.1 with imbalance type MAJ and two scoring functions, APS and RAPS, dataset CIFAR-100. We UCR of RC3P the as better than that of CCP and Cluster-CP for a fair comparison of prediction set size.
Scoring function
Measure
Methods
MAJ
0.5
p= 0.4
p= 0.3
p 0.2
0.1
CCP
0.016 0.003
0.007 0.002
0.017 0.004
0.010 0.002
0.088 : 0.004
UCR
Cluster-CP
0.008 0.002
0.012- 0.003
0.021 0.004
0.021 0.005
0.019: 0.005
APS
RC3P
0.016 0.003
0.010 0.003
0.015 0.004
0.01011
0,002
0,088 0.004
CCP
44.1941 0.514
49.23140.1229
53.6761 0.372
55.0244 0.254
64.6421 0,535
APSS
Cluster-CP CP
31.518:t 0.335
35.355:1 0.563
37.514 0.538
43.619-: 0.600
$0.883+t 0.673
RC3P
18.5811 0.007
21.080 0.010
22.606
0.007
26.7851:
0.007
32.699 0.005
CCP
0.015 0.003
0.007 0.002
0.011 0.004
0.010 0.003
0.008 0.004
UCR
Cluster-CP
0,008 0.003
0.011 0.003
0.021=0.000
0.021 0.002
0.018 0.005
RC3P
0.015 0.003
0.010 0.003
0,015 0.004
0.010 0.002
0.008 0.004
RAPS
CCP
48.343:1 0.353
49.252.1 0.128
$3.666.1 0.371
55.01611 0.254
64.633. 0.535
APSS
Cluster-CP
31,513++
35.352++ 0.547
37.503+ 0.535
43.615+ 0.608
50.379+ 0.684
RC3P
18.581 0.006
21.080 0.010
22.605 0.007
26.786 0.007
32.699 0.006
Table 19: Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalance ratio p = 0.5, p = 0.4, م = 0.2, and p = 0.1 with imbalance type EXP and two scoring function, APS and RAPS, on dataset mini- ImageNe. We set UCR of RC3P the same as or better than that of CCP and Cluster-CP for fair comparison of prediction set size.
Scoring Mcasure
Methods
EXP
function
0.5.
0.5
p=
p= 0.3
p=
p= 0.1
CCP
0.008 0.004
0.003 0.002
0.003 0.001
0.003 0.003
0.008 0.004
UCR
Cluster-CP
0.014 0.004
0.005 0.002
0.010 0.002
0.010 0.003
0.012 0.004
RC3P
0.0+ 0.0
0.01 0.0
0.0+ 0.0
0.01 0.0
0.001 0.001
APS
CCP
26.676: 0.171
25,6631 0.182
25.9411 0.180
26.1271 0.187
26.111=
APSS
Cluster-CP
25.889-1 0.301
25,878:1 0.258
25.680:1 0.294
25,522-1 0.311
25:253:: 0.346
RC3P
18.1294: 0.003
17,546 0.002
17.352= 0.003
17.006 0.003
17.082 0.002
CCP
0.008 0.004
0.004 0.003
0.003-: 0.001
0.003:: 0.003
0.009 0.004
UCR
Cluster-CU CP
0.006 0.002
0.003+ 0.001
0.009 0.002
0.008+ 0.003
0.013+ 0.005
RAPS
RC3P
0,0:1
0.01 0.0
0,0+1
0.0:1 0.0
0.0011 0.001
CCP
26.756:1 0.178
26.621 0.182
25.021 0.182
26.216:1 0.188
26.212-
APSS
Cluster-CP CP
26.027++ 0.325
26.000+ 0.283
25,922-+ 0.253
25.5644 0L.558
25.415+ 0.289
RC3P
18.129 0.003
17.546:: 0.002
17.352- 0.003
17.006 0.003
17.082+ 0.002
29

---

Table 20: Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalance ratio p 0.5, p 0.4, p 0.2, and p 0.1 with imbalance type POLY and two scoring function, APS RAPS, on dataset mmgg--mageNNet.
set UCR RC3P the same as or better than that of CCP and Cluster-CP for a fair comparison of prediction set size.
Scoring Meusure
Methods
POLY
function
p= 0.5
p=
p= 0.3
p=
p=
CCP
0.005 0.002
0.004 0.002
0.005 0.002
0.002: 0.001
0.004 0.001
Cluster-CP
0.011 0.003
0.013= 0,003
0.015 0.004
0.012
0.0141 0.003
RC3P
0.0
0.0+:
0.0
0.0::
APS
CCP
26.626:1 0.133
26.3431 0.214
27.1681 0.203
27.363:1 0.252
26.159: 0.208
APSS
Cluster-CP
26.150++ 0.393
25.348 0.231
26.132+ 0.415
26.390+ 0.270
25.633++ 0.268
RC3P
17.784:: 0.003
17.752:1 0.003
17.652:: 0.003
17.629 0.003
17,465 0.003
CCP
0.005 0.002
0.004 0.002
0.005 0.002
0.002+ 0.001
0.004+ 0.002
UCR
Cluster-CP
0.009 0.003
0.016 0.004
0.017 0.004
0.009 0.003
0.016 0.003
RC3P
0.0+ 0.0
0.0+ 0,0
0.0 0,0
0.0+ 0,0
0.0 0.0
RAPS
CCP
26.689 0.142
26.437+ 0.213
27.254++ 0.201
27.450+ (1.249
26.248 0.219
APSS
Cluster-CP
26,288:4 0.407
25.6274 0.318
26.220:t 0.432
26.559: 0.242
25.7124 0.315
RC3P
17.784:: 0.003
17.752 0.003
17.652= 0.003
17.629 0.003
17.465= 0.003
Table 21: Results comparing CCP, cluster-CE and RC3F with ResNet-20 model under different imbalance ratio P = 0.5, p 0.4, p 0.2, and p = 0.1 with imbalance type MAJ and two scoring function, APS and RAPS, on dataset mini- ImageNet We set UCR of RC3P the same as or better than that of CCP and Cluster-CP for fair comparison of prediction set size.
Scoring function
Measure
Methods
MAJ
p = 0.5
p=
p = 0.3
p.
p =
CCP
0.010 0.004
0.009:: 0.003
0,0:1
0.005:: 0.002
0.005 0.002
UCR
Cluster-CP
0.008 0.002
0.010 0.000
0.010
0,003
0.012 0.004
0.010 0.003
APS
RC3P
0,0+:
0.0+ 0.0
0,0+:
0.0+ 0.0
0.0+:
CCP
27.313+
27.233: 0.246
0.177 26,939-E
26.676: 0.267
25.629:t 0.207
APSS
Cluster-CP CP
26.918++ 0.241
26.156+ 0.255
25.786++ 0.356
25.632++ 0.383
25.348++ 0.334
RC3P
18.111: 0.002
17.874:: 0.002
18.081 0.003
17,800 0.002
17.167 0.004
CCP
0.009 0.003
0.009 0.003
0.01 0.0
0.005 0.002
0.005 0.002
UCR
Cluster-CP
0.007 0.002
0.011 0.002
0.013
0.014
0.009:: 0.002
RC3P
0.0:1(0.0)
0.0:((0.0)
0.0:1(0.0)
0.01((0.0)
0.0:1(0.0)
RAPS
CCP
27.3971
27.320:1 0.244
27.0131 0,177
26.7824 0.269
25.725 0.211
APSS
Cluster-CP
26.969-1 0.305
26.293:1 0.245
25 256-1 0.308
25 803-1 0.440
25.532.1 0.350
RC3P
18.111+ 0.002
17.874 0.002
18.081
17,800 0.002
17.167 0.004
Table 22: Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalancc
ratio p = 0.5, م 0.4, P 0.2, and p == 0.1 with imbalance type EXP and two scoring function, and RAPS, on dataset Food-101 101. We set UCR of RC3P the same as or better than that of CCP and Cluster-CF for fair comparison of prediction set size.
Scoring function
Mcasure
Methods
EXP
p 0.5
p= 0.4
0=0.3
0.2
p= 0.1
CCP Cluster-CP
0.006:: 0.002
0.010+ 0.002
0.008:: 0.002
0.014: 0.004
0.006: 0.002
UCR
0.003+ 0.002
0.009::: 0.003
0.006:: 0.003
0.008= 0.003
0.009: 0.003
RC3P
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
0.0 0.0
APS
CCP
27.003= 0.183
27.024=
28.074 0.199
28.512
30.8754 0.163
APSS
Cluster-CP
29.020+ 0.281
30.120== 0.440
30.529- 0.381
31.096: 0.350
33.327+: 0.440
RC3P
18.369+ 0.003
18.339
0.004
18.803+
0.003
19.612+ 0.005
21.556+ 0.006
CCP
0.006.1 0.003
0.010.1
0.002
0.008
0.002
0.0141
0.004
0.006.1 0.002
UCR
Cluster-CP
0.0044: 0.003
0.010.1
0.003
0.006:1
0.003
0.002 0.010::
0.0124 0.004
RAPS
RC3P
0.02(0..)
0.0=(0.0)
0.0
0.0:
0.0=(0.0)
CCP
27.022 0.192
27.043=
0.163
28.09%=
0.199
28.5355 0.155
80.900=00.11
APSS
Cluster-CP
28.953+ 0.333
30.242+
01.666
30.587+
0.377
30.924+ 0.317
33.375+ 0.377
RC3P
18.369 0.004
18.339
0.004
18.803::
0.003
19.612 0.005
21.556 0.006
30

---

Table 23: Results comparing CCe, cluster-CF, and RC3F with ResNet- 20 model under different imbalance ratio 0.5. 0.4, p 0.2, and p= 0.1 with imbalance type POLY and two scoring function, APS and RAPS, dataset F0od-101. We set UCR of RC3P the same better than that of CCP and Cluster-CP for a fair comparison prediction set size. Scoring function
Methods
POLY p= 0.3
p= 0.5
p=
p
p= 0.1
CCP
0.009 0.003
0.005= 0.003
0.009 0.003
0.011 0.003
0.008+ 0.001
UCR
Cluster-CP
0.004 0.001
0.012 0.002
0.012: 0.004
0.011 0.002
0.009: 0.002
RC3P
0.0+:
0.0
0.0+:
0.0
APS
CCP
30.943+ 0.119
31,239+ 0.198
52,283+
0.169
33,570+ 0.163
35,912+ 0.105
APSS
Cluster-CP
33.079: 0.393
33.9511: 0.531
34.626:t 0.352
36,546: 0.490
38.301 0.232
RC3P
21.499:: 0.003
21.460 0.005
22.882-2 0.005
23.708 0.004
25.853+ 0.004
CCP
0.009 0.003
0.006 0.003
0.009 0.003
0.01 0.003
0.008: 0.001
UCR
Cluster-CP
0.006 0.002
0.013 0.002
0.012 0.004
0.016 0.002
0.006 0.003
RC3P
0.0 0.0
0.0+ 0.0
0.0 0.0
0.0 0.0
0.001 0.001
RAPS
CCP
30,966:1 0.125
31,257 0.197
32,3021 0.169
33.5951 0.164
35,9402 0.III
APSS
Cluster-CP
33.3374 0.409
33,9364 0.448
34.878: 0.282
36.5051 0.520
38.499 0.216
RC3P
21,499: 0.003
21.460 0.005
22.882 0.005
23,708 0.004
25.853 0.004
Table 24: Results comparing CCP, cluster-CP, and RC3P with ResNet-20 model under different imbalance ratio 0.5, 0.4, 0.2, and p 0.1 with imbalance type MAJ and two scoring function, APS and RAPS, dataset Food-101. We set UCR of RC3P the same better than that of CCP and Cluster-CF for a fair comparison prediction set size.
Scoring function
Measure
Methods
MAJ
0.5
p
p 0.3
p 0.1
CCP
0.006 0.001
0.005= 0.002
0.008 0.003
0.010 0.002
0.008:: 0.002
UCR
Cluster-CP CP
0.011 0.003
0.005= 0.002
0.014: 0.004
0.016
0.004
0.011 0.002
RC3P
0,01
0.0:1 0.0
0,04
0.0:1 0.0
0.0: 0.0
APS
CCP
27.4154
29.369- 0.120
30.6724
0.182
31.966:
0.165
36.776 0.132
APSS
Cluster-CP
30.071: 0.412
31.656: 0.261
32.857:: 0.469
33.7741
0.494
39.632.1
0.342
RC3P
19,398:: 0.006
20.046: 0.004
21.425= 0.003
22.175
0.004
26.585 0.004
0.006 0.002
0.005 0.002
0.008 0.003
0.010 0.002
0.008.1 0.002
UCR
Cluster-CP
0.011 0.003
0.005 0.002
0.013 0.004
0.014 0.004
0.014: 0.004
RC3P
0.0=((0.0)
0.0+=(0.0)
0.0++00.0
0.0+
0.0+
RAPS
CCP
27.439 0.203
29,393:1 0.120
30.6911 0.182
31.9871 0.165
36.802.1 0.138
APSS
Cluster-CP
29.946.t: 0.407
31.409-1 0.303
32.724
0.501
39.529-t
RC3P
19.397= 0.006
20.046 0.004
21.425 0.003
22.175 0.004
26.585 0.004
31

---

(a) CIFAR-10 10
(b) CIFAR-100
(c) mini -mai--mmaeeNett
(d) Food-101
2.5
2.0
3.0
1.5
RC3P
Clustor
Methad
50.0
20.0
60.0
RC3P
dlustenCP
Mathod
215.0
20.0
10.0
12.5
7-5
CCP
RC3P
cluster
Mothod
200.0
$00.0
25.0
15.0
Cluster-CP
CCP
RC3P
Mathod
0.5
10.0
5.0
2-5
0
0854
0
0 Class-wise Coverage
Coverage
Class-wise Ceraae
Coverage
4.0
Method
160.0
Mathod
30.0
Mothed
40.0
Mathod
1r00 25
003.0
2.5
3.5
CCCP
RC3P
cluster-CP
6120.00
100.0
140.0
RC3P
cluster-CP
20.0
RC3P
CCP
cluster-P
D30.0
35.0
cluster-CP
CCP
RC3P
2-0
20.0
10.0
10.0
0.5
20.0
5.0
0.0
09
1.30
1.51 1.73 1.94
24.12
22. 31 39.63.48.14 48.14
99.11 41 18 2 25.41 29.08
19.43
A3 19.01 22.60 26.18 29.76
Prediction Set Size
Prediction Set Size
Prediction Set Size
Prediction Set Size
Figure 5: Class-conditional coverage (Top row) and prediction set size (Bottom row) achieved by CCP, Cluster-CP, and RC3P methods when 0.1 CIFAR-IO, CIFAR-I00, mini- mini--mageNNe. and Food- imbalance ratio p = 0.5. We clarify that RC3P overlaps with CCP on CIFAR-10. It is clear that RC3P has more densely distributed class-conditinnal coverage above 0.9 (the target 1 a class-conditional coverage) than CCP and C1 uster--eee with significantly smaller prediction sets on CIFAR-100, mini- ImageNtt and Food-101.
101 datasets imbalance type
(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNt
(d) Food- 101
20.0
191. 1.5
2.0
Method
_ 20.0
g 30.0
40.00
Method
10.0
12.5
7.5
CluuserrCPP
Method
15.0
10.0
Method
0.5
1.0
10.0
5.0
2.5
0.91
0.93
0.96 0.99
98 0.88
0.92
0.96 1.00
0.86
0.90
0.93
0.96
1.00
o 8
092
0.95
0.97
1.00
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
03.0
3.5
4.0
55000
Method
25.0
30.00
35.0
40.0
2.5
50.0
20.0
2.0
3-0.0
cluster-CP
020.0
1.55
30.0
RC3P
10.0
215.0
10.0
5.0
1.01 Prediction Set Size
32.10
40.84
9
93 18.32
029
Prediction Set Size
Prediction Set Size
Prediction Set Size
Figure Class-conditional coverage (Top row) and prediction size (Bottom row) achieved by CCP, Cluster-CP. CP, and RC3P methods when a 0.1 on CIFAR-10. CIFAR-100, mini-ImageNet, and Food- 101 datasets with imbalance type POLY for imbalance ratio p p= 0.1. We clarify that RC3P overlaps with CCP on CIFAR-10. 00. is clear that RC3P has more densely distributed class-conditin coverage above 0.9 (the target 1 class coass-cnniiional coverage) than CCP and Cluster-CB with significantly smaller prediction sets CIFAR-100, mini-ImageNet and Food-101.
32

---

(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-iImm Muni-ImageNNe
(d) Food-100 101
4.0
40.0
822 22.0
[1 11.5
2.55
CCPP
RC3P
Chutter-CP
Method
2e.30.0
20.0
30.0
clustor-CP
RC3P
515.0
CCP
clusteCPP
Method
$20.00
10.0
15.0
CCP
Method
1.0
10.0
2.5
5.0
8
8
0
0.
Class-wise Coverage
Class-wise Cevera
Class-wise Coverage
Class-wise wiswiiss Coverage
123.0
2.5
4.0
2-0
3.5
-RC3P
CCP
cluster-CP
E 100. 0
2-100.5 0
140. 0
80 0
RC3P
ElusterCP
25.0 clusterCP
15.0
RC 3P
CCP
Method
23.00
25.0
35.0
40.0
Cluster-CC
CCP
RC3P
Method
60.0 0
40.0
10.0
1..00
15.0
20.0
5.0
5.0
00
1.23
145 1:68
1.90
988 36366.333 36.76 44-9953.22
9,9
34 18.15 21. 25.77 29.58
Prediction Set Size 16. Prediction Set Size
32 22,80 26.28 29.77 33.25
Prediction Set Size
Prediction Set Size
Figure 7: Class-conditional coverage (Top row) and prediction set size (Bottom row) achieved by CCP, el Cluster-CP, and RC3P methods when a 0.1 CIFAR-10, CTFAR-100, mini-ImageNet, and Food- datasets with imbalance type POLY for imbalance ratio P = 0.5. We clarify that RC3P overlaps with CCP on CIFAR-10. It is clear that RC3P has more densely distributed class-conditional coverage above 0.9 (the target
1 cass-conditional coverage) than CCP and Cluster- with significantly smaller prediction sets on CIFAR-100 100, mini- ImageNet and Food-100
(a) CIFAR-10
(b) CIFAR-100
(c) mini- Mini--ImaeeNet
(d) Food- 101
2.55
3.0
20.0
17.5
20.0
1.0
2.0
1.5
clustor-Cr
RC3P
Method
40.00
20.0
30.0
cluston
RC3P
Mathod
15.0
10.0
7.5
CCP
Clusser
Mothed
10.0
15.0
cluster CP
CCP
RC3P
Mathod
0.5
5.0
2.5
5.0
0828
0..7a
0.
0.50
Class-wise Coverage
Cererage
Coverage
Class-wiss Coverage
26.0
5.5
7.0
8.0
CCP
RC3P
cluterCCP
Method
100.0
60.0
RC3P
clusterCP
Mathod
30.0
20.0
CCP
Cluster-PP
Method
40.0
30.0
Cluster-CP
CCP
RC3P
Method
40.0 0
10.0
20.0
2200
1.0
5.0
10.0
01
2,27
2.64 3:01
3.37
9,8
7040.11444 515.91
9,93 3 17.58 20 24.39 27.79
0.9.7 77 28.72 32.68 36.63 40.58 Prediction Set Size
Prediction Set Size
Prediction Set Size
Prediction Set Size
Figure 8: Class-conditional coverage (Top row) and prediction set size (Bottom row) achieved by CCP, Cluster-CP, and RC3P methods when 0.1 CIFAR-10. CIFAR-100, mini-ImageNet, and Food- datasets with imbalance type
for imbalance ratio p 0.1. clarify that RC3P overlaps CCP on CIFAR-10. It is clear that RC3P has more densely distributed class-conditional coverage above 0.9 (the target
1 conditionnl coverage) than CCP and Cluster-Ga with significantly smaller prediction sets on CIFAR- 100, mini- mini--mmaeNet and Food-101.
33

---

(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food-101
50.0
20.0
2.0
2.5
1.5
CP
G40.0
30.0
0 01..0
10.0
12.5
CC
Mothod
015.0
11.5
122.5
cluster
Mathod
1.0
RC3P
20.0
RC3P
7.5
0.5
10.0
5.0
2.5
5.0
23
82
0.97
888 0.1
0.97
8 0.91
0.97
8.88
0.01
0.97
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
wise Coverage
440
3.0
(2.0
5.0
RCC3P
G150.0
100.00
175.0 0
200.0 0
125.0
cluster-CP
CCP
RC3P
Method
25.0
30.0
15.0
CCP
<luster-CP
Method
40.0
20.0
30.0
cluster-CP
Method
1.0
5.0
10.0
0.0 0.36
1.98 Prediction Set Size
0,8
52,04
1 08 76.6 22.44
18.42
20.27 24.13 27.99 Prediction Set Size
Prediction Set Size
Prediction Set Size
Figure Class-conditional coverage (Top row) and prediction size (Bottom row) achieved by CCP, Cluster-CP, and RC3P methods when a 0.1 on CIFAR-IO, CIFAR- 100, mini-ImageNNe, and Food- 101 datasets with imbalance type MAJ for imbalance ratio = 0.5. We clarify that RC3F overlaps with CCP on CIFAR-10. It clear that RC3P has more densely distributed class-conditional coverage above 0.9 (the target 1 class-conditional coverage) than CCP and Cluster-CP with significantly smaller prediction sets on CIFAR-100, mini-ImageNet and Food-101.
(a) CIFAR-10
(b) CIFAR-100
(c) miie--mmaeNNet
(d) Food-101
E2.00
11.50
2.50
3.00
CCP
RC3P
cluster-CP
Methad
20.06
20.04
$0.05
RC3P
30.03
70.05
20.07
30.06
cluster-CP
RC3P
50.05
0..04
00008
cluster-CP
RC3
0.02
0.002
9.002
0.50
0.01
E0.01
0.01
2 0.00
0.00
97
20,00
Rank
Rank
Rank
Rank
Figure 10: Visualization for the normalized frequency distribution of label ranks included in the prediction of CCP, Cluster-CP, and RC3P with p = EXP when a = 0.1. is clear that distribution normalized frequency generated by RC3P tends to be lower compared to those produced by CCP and cluster-CE Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
(a) CIFAR-10
(b) CIFAR-100
(c) mini- mini-ImageNNet
(d) Food- 101
Method
C0.03
Method
20.06
20.05
Method
2.50
1.50
1.00
cluster-CP
CCP
RC3P
20.02
20.03
20.01
0.01
Cluster-CP
RC3P
CCC
20.04
0.005
0.002
cluster-CP
CCP
RC3P
E0.03
5..02
0.04
cluster-CP
CCP
RC3P
0.01
20001
0.01
0.00
5.000
20.00
20
38
75
0.00
40
Rank
Rank
Rank
Rank
Figure 11: Visualization for the normalized frequency distribution of label ranks included in the prediction set of CCP, Cluster-C2, and RC3F with p 0.1 POLY when a 0.1. clear that the distribution normalized frequency generated by RC3P tends be lower compared to those produced by CCP and Cluster-CP. Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
34

---

(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food-101
2.00
2.55
cluster-CP RC3P
Method
Nomai 1a0.ea0 requercy
0.04
0.03
cluster-CP
RC3P
Method
20.04
0.005
0.06
cluster-CP
CCP
RC3P
Method
b0.06
20.04
0.00
CCluster-CP
CEP
RR3P
Method
11.50
0.02
20.03
50.03
1.00
0.02
50.02
0.50
0.01
0.01
0.01
2 0.00
0.00
25
50
74
98
20.00
18
3G
53
70
20,00
43
Rank
Rank
Rank
Rank
Figure 12: Visualization for the normalized frequency distribution of label ranks included in the prediction set of CCP. Cluster-C2, and RC3P with p = 0.5 POLY when a = 0.1. is clear that the distribution of normalized frequency generated by RC3P tends to be lower compared to those produced by CCP and Cluster-CP. Furthermore, the probability density function tail for label ranks in the RC3P prediction set notably shorter than that of other methods.
(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food- 101
11.00
W
CCP
RC3P
cluster-CP
Method
2.003
50002
$0.03
RCSP
cluster-CP
CCP
60.05
20.04
9.06
cluster-CP
CCP
RC3P
8.003
0.04
RC3P
clusten-CP
Method
0.40
0.001
0.00
0.20
0.01
0.01
00001
0.00
0.01
0.00
26
34
0.000
Rank
Rank
Figure 13: Visualization for the normalized frequency distribution of label ranks included in the prediction set of CCP, Cluster-CP and RC32 with o = 0.1 MAJ when a = 0.1. is clear that the distribution of normalized frequency generated by RC3P tends to be lower compared to those produced by CCP and cluster-CE Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-ImageNNe
(d) Food-101
50
80 80.75
21 01.50
E2
11.00
11.25
20.50
61.75
- RC3P
Method CCP
cluster-CP
2.004
0.05
0.02
0.01
CCP
RC3P
clustar-CP
Method
3.00
3.002
0.05
0.01
50.03
cluster-CP
OCP
RC3P
Method
d
$..05
2.004
20.03
E0.06
0.01
0.02
CCP
cluster-CP
RC3P
Mathod
0:00
2.000
55
20.00
20
Rank 76
0.000
Rank
Rank
Rank
Figure 14: Visualization for the normalized frequency distribution of label ranks included in the prediction set of CCP, Cluster-CE and RC32 with p = 0.5 MAJ when a 0. is clear that distribution of normalized frequency generated by RC3P tends to be lower compared to those produced by CCP and Cluster-Ca Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
(a) 10
(b) CIFAR-100
(c) mini-Image.Na
(d) F01
10.0
10.0
1.0
1.0
1.0
10.0
Frequency
8.0
26.0
8.0
8.0
6.0
6.0
84.0
4.0
4.0
2.0
2.00
1.0
2,0
2.0
0.0
1
0g
8.00
0,28
0.52
0.76
3.00
0
0.31
0.54
0.77
1.00
08.24
0.43
5.67
0
3.00
Sigma_y
Sigma_y
y
Sigma_y
Sigma_y
Figure 15: Verification of condition numbers {a, of Equation 6 when epoch 200 and & 0.1 with = 0.5 EXP. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than 1. This verifies the validity of the condition for Lemma 4.2 and thus confirms that RC3 PC3dprod smaller prediction than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
35

---

(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-Image.le
(d) Food- -01
10.0
12.0
8.0
1.0
10.0
1.0
10.0
1.0
10.0
1.0
6.0
0.0
6.0
8.0
6.0
6.0
8.0
4.0
4.0
2.0
2.0
0.0
000
0,30
0.53
0.77
0.38
0.59
0.79
1.00
0.22
0.46
0.64
0.82 2.00
Sigma_y
Sigma_y
Sigma_y
Sigma_y
Figure 16: Verification of condition numbers { of Equation when epoch = 200 and a = 0.1 with = 0.1 POLY. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma 4.2 and thus confirms that RC3Pproduces smaller prediction sets than CCP by the optimized trade-off' between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-I0
(b) CIFAR-100
(c) mini--ImaeeVa
(d) Food- 101
10.0
Frequency
8.0
6.0
1.0
C
6.0
1.0
6.0
1.0
Frqqeeccy
10.0
8.0
6.0
1.0
4.0
4.0
4.0
2.0
2.0
2.0
0.0
0,00
0.53
0.70
8825
0.44
0.63
08.20
0.40
0.50
2.00
Sigma
Sigma
Sigma
Sigma
Figure 17: Verification of condition numbers fow of Equation 6 when epoch = 200 and a = 0.1 with P 0.5 POLY. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma and thus confirms that RC3Pproduces smaller prediction sets than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food- 101
10.0
10.0
Frequency
8.0
6.0
1.0
10.0
8.0
6.0
1.0
6.0
1.0
requenty
6.0
8.0
1.0
4.0
4.0
4.0
2.0
2.0
2.0
2.0
0.0
1,00
0,00
0.27
0.51
0.76
1.00
0.59
0825
0.44
0.63
0.8
1.00
Sigma
Sigma_y
Sigma ma
Sigma
Figure 18: Verification of condition numbers fa bo of Equation 6 when epoch = 200 and a 0.1 with = 0.1 MAJ. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma and thus confirms that RC3Pproduces smaller prediction sets than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-10 10
(b) CIFAR-
(c) mini-ImageNet
(d) Food- food-101
10.0
12.0
12.0
8.0
1.0
1.0
10.00
1.0
10.0
1.0
6.0
6.0
8.0
8.0
4.0
4.0
4,0
4.0
2.0
2.0
2,0
0.0
1,00
0
0.27
0.51
0.76
08
0.39
0.59
0.80
1.00
0..1
0.39
0.60
0.80
3.00
Sigma_y
Sigma_y
Sigma_y
Sigma_y
Figure 19: Verification of condition numbers {a of Equation 6 when epoch = 200 and a = 0.1 with 0.5 MAJ. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma 4.2 and thus confirms that Pr3puuueeess smaller prediction sets than CCP by the optimized trade-off between calibration on conformity scores and calibrated label ranks.
36

---

(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNtt
(d) Food- -01
10.0
12.0
Frequency
8.0
1.0
1.0
10.0
1.0
10.0
12.0
1.0
6.0
6.0
8.0
8.0
4.0
4.0
4.0
6.0
2.0
2.0
2.0
2.0
0.0
0
0,30
0.53
D.77
0
0.42
0.81
1.00
0.30
053 0.69
0.84 1,00
Sigma_y
Sigma_y
Sigma_y
Sigma_y
Figure 20: Verification of condition numbers {o of Equation 6 when epoch = 50 and a = 0.1 with = 0.1 EXP. Vertical dashed lines represent the value and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma 4.2 and thus confirms that RC3pproduces smaller prediction sets than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-I0
(b) CIFAR-100
(c) mini- AmaiiNeteeNNtt
(d) Food-101
10.0
Frequency
8.0
6.0
1.0
10.0
0.0
6.0
1.0
6.0
1.0
resuers
10.0
6.0
8.0
1.0
4.0
4.0
2.0
2.0
2.0
0.0
0000
0.29
0,70
0
0.48
0.65
1.00
0..29
0.47
0.65
2.00
Sigma
Sigma_y
Sigma.y
Sigma
Figure 21: Verification of condition numhers for of Equation 6 when epoch 50 and a = 0.1 with P 0.5 EXP. Vertical dashed lines represent the value and we observe that all the condition numbers smaller than This verifies the validity of the condition for Lemma and thus confirms that RC3Pproduces smaller prediction sets than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-10
(b) CIFAR-100
(c) mini-ImageNNe
(d) Food- 101
Frequentyy
10.0
8.0
6.0
1.0
10.0
8.0
6.0
1.0
6.0
1.0
10.0
12.0
8.0
1.0
4.0
4.0
6.0
2.0
2.0
2.0
0.0
1,00
084
0.28
0.52
0.76
1.00
0
0.48
0.65
0.63
1.00
0..1
0.56 0.71
0.65
1.00
Sigma
Sigma_y
Sigma_y
Sigma_y
Figure 22: Verification of condition numbers for of Equation 6 when epoch = 50 and a = 0.1 with = 0.1 POLY. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma 4.2] and thus confirms that RC3Pproduces smaller prediction sets than CCP by the optimized trade-off between calibration on non-conformity scores and calibrated label ranks.
(a) CIFAR-10
(b) CIFAR-100
(c) mini-
(d) Food- F01
10.0
1.0
1.0
1.0
10.0
8.0
6.0
6.0
6.0
trequency
8.0
6.0
4.0
4.0
4.0
2.0
2.0
2.0
0.0
1,00
00
0.35
0.55
0.78
0
0.42
0
1.00
0
054
0.85 1.00 Sigma_y
0.69
Sigma_y
Sigma_y y
Sigma_y
Figure 23: Verification of condition numbers {aw]o= of Equation 6 when epoch 50 and a = 0.1 with 0.5 POLY. Vertical dashed lines represent the value 1, and we observe that all the condition numbers are smaller than This verifies the validity of the condition for Lemma 4.2 and thus confirms that Prrpuuuee smaller prediction sets than CCP by the optimized trade-off between calibration on conformity scores and calibrated label ranks.
37

---

(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-ImageNNe
(d) Food-100
12.0
8.0
1.0
25.0
1.0
1.0
10.0
55.0
54.0
6.0
33.0
2.0
2.0
2.0
1.0
0.0
1,00
0
0.27
0.51
0.76
0
0.53
0.69 Sigma
0.84
1.00
08.37
0.53
0.68
0.86 1.00
Sigma y
Sigma
y
Sigma
Figure 24: Verification of condition numhers fou of Equation when epoch 50 and 0.1 with / = 0.1 MAJ. Vertical dashed lines represent the value and we observe that all the condition numbers are smaller than 1. This verifies the validity of the condition for Lemma 4.2 and thus confirms that RC3 pc3dpoos smaller prediction sets than CCP by the optimized trade-off between calibration on con-conformity scores and calibrated label ranks.
(a) CIFAR-10 10
(b) CIFAR-100
(c) mini-ImageNNet
(d) Food- 101
8.0
1.0
1.0
Seequente
8.0
1.0
14.0
12.0
1.0
4.0
2.0
2.0
0.0
0.77
0 0
0,80
08.39
0.70
1.00
Sigma_y
Sigma_y
Sigma_y y
Sigma_y
Figure 25: Verification of condition numbers {ov1s of Equation 6 when epoch and 0.1 with P = 0.5 MAJ. Vertical dashed lines represent the value and we observe that smaller than This verifies the validity of the condition for Lemma 4.2 and thus confirms that Rropuuuuuces smaller prediction sets than CCP by the optimized trade-off between calibration on non-confornity scores and calibrated label ranks.
condition numbers are
38

---

C.11 Complete Experiment Results on Balanced Classification Datasets
In this subsection, we report complete experimental results over four balanced datasets and a = 0.1. Specifically, Figure 26 shows the conditcon coverage and the corresponding prediction set sizes. From the first row of Fig the class wise coverage bars of CCP and RC3P distribute on the right-hand side of the target probability 1 (red dashed line). Second, RC3P outperforms CCP and C1 cluster-CC with 24.47% (on four datasets) or 32.63% (excluding CIFAR-10) on imbalanced datasets and 32.63% on balanced datasets decrease in terms of average prediction set size the same class-wise coverage. The second row of Figure 26 shows (i) RC3P has more concentrated class- wise coverage distribution than CCP and Cluster C:; (ii) the distribution of prediction set sizes produced by RC3P is globally smaller than that produced by CC2 and Cluster CP, which is justified by better trade-off number of { as shown in Figure 3
Figure 27 illustrates the normalized frequency distribution of label ranks included in the prediction sets on balanced datasets. It is evident that the distribution of label ranks in the prediction set generated by RC3P tends to be lower compared to those produced by CCP and C1 uster-CP. Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods. This indicates that RC3P more effectively incorporates lower-ranked labels into prediction sets, as result of its augmented rank calibration scheme.
Figure 28 verifies the condition numbers By on balanced datasets. This result verifies the validity of Lemma 4.2 and Equation 6 and confirm that the optimized trade-off between the coverage with inflated quantile and the constraint with calibrated rank leads to smaller prediction sets.
(a) CIFAR-100
(b) Places365
(c) iNaturalist
(d) ImageNet
25.0
40.0
80.0
100.0
20000
15.0
Method
30.0
Method
Method
80.0 10000e Aorouun
Method
10.0
RC3P
20.0
20.0
RC3P
40.0
cluster-CP
40.0
dluster-CD
RC3P
5.0
10.0
20.0
20.0
0,..7
0.90
0.94
0.97
1.00
8 0.99
0.93
0.98
1.00
0 0.89
0.93
0.96
1.00
0 0.87 0.93
0.98
1.00
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
Class-wise Coverage
35.0
70.0
Method
350.0
50.0
60.0
CCP
300.0
225.0
Cluster-CP RC3P
40.0
cluster-CP RC3P
250.0
cluster-CP
2500.
ClusterCP
20.0
RC3P
200.0
RC3P
- 10.0
155.0
20.0
20.0
20.0
E
7150.0
100.0
5.0
10.0
10.0
50.0
0g.51 13.07 29.53 39.99 50.45
0..7
Prediction Set Size 0.233
12.16
20.60 19.04.33
59.47 78.52
0. 18.53151.5620 0226.5300.40
Prediction Set Size
Prediction Set Size
Prediction Set Size
Figure 26: Class-conditional coverage (Top row) and prediction size (Bottom row) achieved by CCP, Cluster-CP, and RC3P methods when a 0.1 on four balanced datasets. clear that RC3P more densely distributed class-conditional coverage above 0.9 (the target 1 - a class-conditional coverage) than CCP and Cluster-CP with significantly smaller prediction sets on all datasets.
(a) CIFAR-100
(b) Places365
(c) iNaturalist
(d) ImageNet
20.08
Method
Mathad
2o.07
Method
20.34
Method
E 0.05
50.07
20.04
Cluster-CP
RC3P
DCP
E0.05
g.004
20.03
cluster-CP
RC3P
CCP
20.04
30.05
10.06
20.03
CCP
Cluster-CP
RR3P
E g0.06
80.10
E0.08
80.12
Cluster-CP
CCP
RC3P
20.02
20.02
5.002
0.04
0.001
50.01
0.001
0.02
2.00
26
50
75
100
0.00
78
156
233
310
20.00
156
316 Rank
473
630
80,00
250
498
747
996
Rank
Rank
Rank
Figure 27: Visualization for the normalized frequency distribution of label ranks included in the prediction set of CCF, Cluster-CF and RC3P with p 0.1 on balanced datasets. It is clear that the distribution of normalized frequency generated by RC3P tends to be lower compared to those produced by CCP and cluster-cr Furthermore, the probability density function tail for label ranks in the RC3P prediction set is notably shorter than that of other methods.
39

---

(a) CIFAR-100
(b) Places365
(c) iNaturalist
(d) ImageNet
25.0
25.0
200.0
12.0
1.0
20.0
i.0
20.00
1.0
350.0
60.0
1.0
8.0
15.0
15.0
40.0
6.0
10.0
10.0
30.0
20.0
2.0
5.0
10.0
98.5
0813
0.78
8.07
0.30
0.77
1.00
8..0
1.00
Sigma_y
Sigma_y
Sigma_y
Sigma_y
Figure 28: Verification of condition numbers [o in Equation 6 on balanced datasets. Vertical dashed lines represent the value 1, and we observe that all the condition numbers smaller than 1. This verifies the validity of the condition for Lemma 4.2] and thus confirms that RC3P produces smaller prediction than using calibration on both non-conte non-conformity scores and label ranks.
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction has stated the contributions and important assumptions of paper and match our theoretical and experimental results. We have summarize all claims at the end of introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [No]
Justification: A limitation of our paper that assume that (X;, Y)) are exchangeable (for example, i...... This assumption is common and fundamental in CP works, so we do not discuss in our paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: In Section 4.1 and we provide the the full set of assumptions for our
theoretical result. Corresponding proofs are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have provided all all the information needed to reproduce the experiments, including experiments setting, evaluation metric and codes.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
42

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We have provided the codes in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https//nnips.ccppbble)
guidessCoodSSbbmissioooollyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https: for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided the detail about dataset, training and calibration in Section 5.1 and Appendix C.I. C.2 and C.3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We have provide the standard deviation of our main results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We follow the training setting previous papers, so we choose to not discuss the computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://eeerrss..cpppuliieetttts
Answer: [Yes]
Justification: Our work strictly adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The methodological improvements gained in our paper can lead to improve- ments in safe deployment of classifiers in human-ML, collaborative systems. We do not anticipate any negative ethical or societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
44

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our experiments are conducted on public and benchmark datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All the assets used in the paper are open-source and have been properly cited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assetts are released, the license, copyright information, and terms of use package should be provided. For popular datasets, paperswithcode, htwpswtthhoode..cmdaaaasesee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
45

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have provided anonymized zip file in supplementary materiel.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "xB3DMQYgbr", "reviewer": "Reviewer_yaTg", "summary": "The paper proposes a new algorithm called Rank Calibrated Class-conditional CP (RC3P) that augments the label rank calibration to conformal classification calibration step. It theoretically proves it", "questions": "In the simulation result, you \"set the UCR of RC3P the same as or smaller (more restrictive) than that of other methods under 0.16 on CIFAR-10 and 0.03 on other datasets\". I though UCR is a metric and why would you be able to do that.", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Overall, the idea is clearly presented, and the motivation behind the problem—improving efficiency in CCP for imbalanced data—is compelling.\n- The idea of only using top-k classes in the conformal calibration is intuitive.\n- The experimental results are adequate, covering different datasets/settings.", "weaknesses": "- R3CP heavily relies on the ranking of candidate class labels. If the classifier's ranking is not reliable, the result could be more conservative.\n- Lemma 4.2 is not very convincing, since the assumption is basically the conclusion itself. Theorem 4.3 tries to give a condition on when Lemma 4.2 holds, but it is still not very informative. It's not clear to me that R3CP is better than CCP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.\n\n\n**Q1: R3CP heavily relies on the ranking of candidate class labels?**\n\nA1: \nRC3P does not heavily rely on model’s label ranking to guarantee the class-conditional coverage, and is instead agnostic to the model’s ranking performance, as shown in Theorem 4.1. \n\nThe improved predictive efficiency of RC3P relies on certain conditions of the model, as specified in Lemma 4.2 and Theorem 4.3. However, these conditions, e.g., the parameterized condition number $\\sigma_y \\leq 1$, very likely holds in practice: we empirically verify it and it holds for all experiments. See Figure 3 in the main paper and Figures 15-25 in Appendix.\n\n\n**Q2: Lemma 4.2 not convincing and Theorem 4.3 not informative. Not clear why R3CP is better than CCP**\n\nA2: (See also **GR2**)\n\nWe highlight that **Lemma 4.2** is not our main intellectual contribution  for the improved predictive efficiency of RC3P. Instead, it showcases a condition number $\\sigma_y$ that **parametrizes** whether a target event $\\mathcal E$ “the predictive efficiency is improved by RC3P’’ happens or not, i.e., $\\sigma_y \\leq 1 \\Rightarrow \\mathcal E$.\n\nThen **Theorem 4.3** further analyzes the **transition** from the parameter $\\epsilon_y^{\\widehat k(y)}$ of RC3P to the parameter $\\sigma_y$ of the target event to indicate how to configure RC3P to improve predictive efficiency. Specifically, as pointed out in its Remark, if we set $\\alpha - \\epsilon_y^{\\widehat k(y)}$ as small as possible but still guarantee $\\epsilon_y^{\\widehat k(y)} < \\alpha$ (required by the model-agnostic coverage, Theorem 4.1) in RC3P, then we have a higher probability to guarantee $\\sigma_y \\leq 1$. Therefore, the overall **transition** of parameters is expressed by: \n$$\\text{Setting RC3P with (i) } \\epsilon_y^{\\widehat k(y)} < \\alpha, \\text{and (ii) } \\epsilon_y^{\\widehat k(y)} \\text{ as small as possible } ~~~ \\Longrightarrow ~~~ \\sigma_y \\leq 1 ~~~ \\Longrightarrow ~~~ \\mathcal E,$$ \nwhich is equivalent to (7) in Remark and helps us configure RC3P to most likely improve the predictive efficiency over baseline CCP method.\n\nPractical Implications for the analysis of predictive efficiency in experiments:\nWe conducted extensive experiments across multiple datasets to compare the predictive efficiency of each method and verify the conditional number $\\sigma_y$. See Figure 3 in the main paper and Figures 15-25 in Appendix.\n\nOur empirical results consistently show that RC3P achieves better predictive efficiency than CCP and the condition $\\sigma_y \\leq 1 \\forall y$ holds across  all experimental settings. This empirical validation demonstrates that the practical implementation of RC3P aligns with the theoretical improvements shown in Lemma 4.2 and Theorem 4.3.\n\n**Q3: UCR is a metric and why would you be able to set it.** \n\nA3: (See also **GR3***)\n\nWhy: While UCR is a coverage metric, fixing it to a certain value (e.g., 0) across methods allows us to ensure fair comparisons to  make valid conclusions about the predictive efficiency of all CP methods.\n\nBecause coverage and predictive efficiency are two competing metrics in CP, e.g., achieving better coverage (resp. predictive efficiency) degenerates predictive efficiency (resp. coverage).\nIf we do not fix one of them, then we cannot conclude which method has more predictive efficiency by comparison. We add the experiments on balanced CIFAR-100 datasets without controlling the UCR. See the table below.\n\n|Methods|CCP|Cluster-CP|RC3P| \n|-|-|-|-|\n|UCR|0.444|0.446|0.228| \n|APSS|11.376|9.7865|10.712|\n\nAs shown, RC3P achieves the best coverage metric (UCR), while Cluster-CP achieves the best metric for prediction set sizes (APSS). So this comparison does not conclude which one is more efficient.\n\n\nTherefore, we fix UCR to first guarantee the class-conditional coverage, conditioned on which we can perform a meaningful comparison of predictive efficiency. This strategy is also discussed in [r1].\n\nHow:\nWe add an inflation quantity to the nominal coverage, i.e., $1-\\alpha+g/\\sqrt{n_y}$, where $g \\in \\\\{0.25,0.5,0.75,1\\\\}$ is a tunable hyper-parameter and $n_y$ represents the number of calibration samples in each class $y$ (for CCP and RC3P) or each cluster (for Cluster CP). The structure $g/\\sqrt{n_y}$ follows the format of generalization error when setting the empirical quantile, as in [r2]. We select the minimal value from the above range for $g$ such that UCR is under 0.16 on CIFAR-10 and 0.03 on other datasets.\n\nWe add the experiments **without controlling UCR in Experiment (1) of GR1** (Table 7 in PDF) under the same setting with the main paper\n\nThe model is trained from scratch using LDAM [r1]. UCR is not controlled. We then use the total under coverage gap (UCG, $\\downarrow$ better) between class conditional coverage and target coverage $1-\\alpha$ of all under covered classes. \nWe choose UCG as the fine-grained metric to differentiate the coverage performance in our experiment setting. Conditioned on similar APSS of all methods, RC3P significantly outperforms the best baselines with 35.18% reduction in UCG on average.  \n\n[r1] Fontana et al., 2023. Conformal prediction: a unified review of theory and new challenges\n\n[r2] Vladimir Vovk, 2012. Conditional validity of inductive conformal predictors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VunevpKtvQ", "reviewer": "Reviewer_Bzsm", "summary": "This paper aims to reduce the prediction set sizes of conformal predictors while achieving class-conditional coverage. The authors identify that class-wise conformal prediction (CCP) scans all labels uniformly, resulting in large prediction sets. To address this issue, they propose Rank Calibrated Class-conditional Conformal Prediction (RC3P), which augments the label rank calibration strategy within CCP. Theoretical analysis and experimental results demonstrate that RC3P outperforms CCP.", "questions": "- What is the ratio of training set, calibration set and test set? Does RC3P still outperform other methods when the size of calibration set is small? I think an ablation experiment about the size of calibration set is better.\n    \n- How do you control the UCR of RC3P? Please provide some details.", "limitations": "They are adequately discussed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is well-motivated, and the paper is easy to follow. The authors find that CCP scans all labels uniformly, resulting in large prediction sets.\n    \n2. The proposed method introduces a novel conformal predictor for class-conditional coverage, achieving smaller set sizes than other classical methods on imbalanced datasets.", "weaknesses": "1. The proposed methods and experiments appear logically incoherent. The authors provide an explanation for the large prediction sets of CCP, but the interesting conclusion is not related to imbalanced data. Why do the authors only consider imbalanced datasets? Additionally, could the authors report the performance of different methods on balanced data?\n    \n2. The datasets used in the experiments are small, which is impractical for real-world applications. As shown in Section 5, the number of classes in the four datasets is fewer than 101. Moreover, Cluster-CP was proposed for datasets with many classes, so it may be unfair to compare these methods only on small-scale datasets. Furthermore, the classical method THR[1] should be considered in the experiments.\n    \n3. The contribution of Lemma 4.2 is limited. The assumption in Lemma 4.2 is very strong, which can directly infer the final results.\n\n[1] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.\n\n\n\n**Q1: Why only consider imbalanced datasets? Report the performance on balanced data?**\n \nA1:\nRC3P is a general class-conditional CP method and works for the models trained on both imbalanced and balanced classification data. We did imbalanced experiments originally in the main paper, since the imbalanced setting is more common and challenging in practice, which can also differentiate the performance of RC3P with baselines. \n\nThe  example  in Section 4.1 only gives an intuitive motivation, but it is valid for both balanced and imbalanced settings. Additionally, since the standard CCP iterates over all class-wise quantiles, the prediction set sizes can be more diverse and exhibit large variance under the imbalanced setting, which further degenerates the predictive efficiency.\n\n**We add balanced experiment on diverse datasets (CIFAR-100, Places365, iNaturalist, ImageNet) in Experiment (1) of GR1** (see Table1 in the attached PDF).  The models are pre-trained. UCR is controlled to $\\leq 0.05$. RC3P significantly outperforms the best baseline with $32.826\\\\%$ reduction in APSS ($\\downarrow$ better) on average, with $10.539\\%$ on iNaturalist and $59.393\\%$ on ImageNet. We get similar improvements with APS and THR scoring functions.\n\n\n**Q2: It may be unfair to compare these methods only on small-scale datasets.**\n\nA2: \nIn addition to the large-scale experiments on balanced data in Experiment (1) of GR1, in **Experiment (2)  Large-scale imbalanced classification experiment**  (Table 2 in PDF), we also tested baselines and RC3P on a large-scale dataset (ImageNet-LT) with a deep model trained from scratch using the imbalanced training method LDAM [r1]. UCR is controlled to $\\leq 0.12$. RC3P significantly outperforms the best baseline with $28.523\\\\%$ reduction in APSS ($\\downarrow$ better) on average.\n\n\n**Q3: Furthermore, the classical method THR[1] should be considered in the experiments.**\n\nA3: We have added the experiments with **the THR scoring function [r2] in Experiment (4) of GR1** (Table 4 in PDF) for baselines and RC3P. UCR is controlled to $\\leq 0.16$ on CIFAR-10 and $\\leq 0.03$ on other datasets. RC3P significantly outperforms best baselines with $26.9\\\\%$ on mini-ImageNet reduction compared with the best baseline. Similar improvements of RC3P can be found on other datasets.\n\n**Q4: The contribution of Lemma 4.2 is limited. The assumption in Lemma 4.2 is very strong, which can directly infer the final results.**\n\nA4: (See also **GR2**)\n\nWe highlight that **Lemma 4.2** is not our main intellectual contribution  for the improved predictive efficiency of RC3P. Instead, it showcases a condition number $\\sigma_y$ that **parametrizes** whether a target event $\\mathcal E$ “the predictive efficiency is improved by RC3P’’ happens or not, i.e., $\\sigma_y \\leq 1 \\Rightarrow \\mathcal E$.\n\nThen **Theorem 4.3** further analyzes the **transition** from the parameter $\\epsilon_y^{\\widehat k(y)}$ of RC3P to the parameter $\\sigma_y$ of the target event to indicate how to configure RC3P to improve predictive efficiency. Specifically, as pointed out in its Remark, if we set $\\alpha - \\epsilon_y^{\\widehat k(y)}$ as small as possible but still guarantee $\\epsilon_y^{\\widehat k(y)} < \\alpha$ (required by the model-agnostic coverage, Theorem 4.1) in RC3P, then we have a higher probability to guarantee $\\sigma_y \\leq 1$. Therefore, the overall **transition** of parameters is expressed by: \n$$\\text{Setting RC3P with (i) } \\epsilon_y^{\\widehat k(y)} < \\alpha, \\text{and (ii) } \\epsilon_y^{\\widehat k(y)} \\text{ as small as possible } ~~~ \\Longrightarrow ~~~ \\sigma_y \\leq 1 ~~~ \\Longrightarrow ~~~ \\mathcal E,$$ \nwhich is equivalent to (7) in Remark and helps us configure RC3P to most likely improve the predictive efficiency over baseline CCP method.\n\n\n**Q5: What is the ratio of training set, calibration set and test set?**\n\nA5: We show the description of datasets in the following table. Thank you for your suggestion. We will add it  in the revised paper.\n\n|Dataset|CIFAR-10|CIFAR-100| mini-ImageNet|FOOD-101|\n|-|-|-|-|-|\n|Number of training samples| 50000| 50000 | 30000|75750|\n|Number of classes| 10|100 | 100 | 101|\n|Each class calibration samples| 500 |50 |150|125 |\n|Imbalanced ratios| \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\} | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\} | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\}  | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\}|\n\n**Q6:  Does RC3P still outperform other methods when the size of calibration set is small?**\n\nA6: We have added the experiments with **various sizes for the calibration sets in Experiment (3) of GR1** (Table 3 in PDF): Baselines and RC3P are calibrated with calibration sets of various numbers of samples. UCR is controlled to $\\leq 0.12$ for CCP and $\\leq 0.07$ for Cluster-CP and RC3P. Following Cluster-CP, we set each class calibration samples $\\in \\\\{20,50,75 \\\\}$. RC3P significantly outperforms the best baseline with $29.68\\\\%$ reduction in APSS ($\\downarrow$ better) on mini-ImageNet. Similar improvements of RC3P can be found on other datasets.\n\n**Q7: How do you control the UCR of RC3P?**\n\nA7: (See also **GR3***)\n\n\\\n[r1] Sadinle et al., 2019. Least ambiguous set-valued classifiers with bounded error levels.\n\n[r2] Ding et al., 2024. Class-conditional conformal prediction with many classes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qQrDxsd82c", "reviewer": "Reviewer_vcMw", "summary": "This paper introduces the Rank Calibrated Class-conditional CP (RC3P) algorithm, which reduces prediction set sizes while ensuring valid class-conditional coverage by selectively applying class-wise thresholding. The RC3P algorithm achieves class-wise coverage regardless of the classifier and data distribution, and show improvement empirically.", "questions": "- For fairness evaluation, especially for many classes, what's the worst under coverage ratio? Only the mean is provided.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea is simple but effective, supported by solid theoretical and empirical evidence.", "weaknesses": "- Some notions, especially the Y and y, are confusing. Similarly, k is for label class, $\\hat{k}(y)$ is for a different notion of label rank, but both uses k.\n- More extra illustrations may be helpful for understanding. For example, regarding the tony example in para 1 of section 4, try give a concrete figure example. Also, give a table of important dataset statistics, e.g., total sample size, number of class, imbalance rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.\n\n\n**Q1: Some notions, especially the Y and y, are confusing. Similarly, k is for label class, $\\hat k(y)$ is for a different notion of label rank, but both uses k.**\n\nA1: Our notations are consistent, but we will try to make them more clearer. We denote $Y$ as the ground-truth label of data sample $(X, Y)$ (see Line 103) and $y$ as a realized class label (see Line 107). $K$ is the number of candidate classes, where the maximum rank is still $K$ (see Line 103). $k$ is used to describe the rank threshold of  top-$k$ class-wise error $\\epsilon^k_y$ (see Line 108). Thus, we use $\\hat k(y)$ as the rank threshold of class $y$.\n\n**Q2: Try to give a concrete figure example.**\n\nA2: We plot the **class-wise score distribution as a concrete example of the explanation in Section 4.1** (Table 6 in PDF).\n\n\nThe true labels of all data from class $1$ are ranked within $\\\\{1, …, 4\\\\}$, which indicates low uncertainty in class $1$. However, nearly half of APS scores with high ranks (i.e., rank 2, 3) are larger than class quantile (the dashed straight line), and the corresponding label will not be included in prediction sets through CCP. On the contrary, the maximum true label ranks of data in class $5$ are 9, which indicates high uncertainty in the model's predictions, but most of the APS scores in class $5$ are smaller than the class quantile (the dashed straight line). Thus, the uniform class-wise iteration strategy of CCP includes more uncertain labels in the prediction sets and  degenerates the predictive efficiency.\n\n**Q3: Give a table of important dataset statistics?**\n\nA3: We show the description of datasets in the following table. Thank you for your suggestion.e will add it in the revised paper.\n\n| Dataset | CIFAR-10 | CIFAR-100 | mini-ImageNet | FOOD-101|\n| --------------------- | ------------------- |-------------|----------- |-----------|\n| Number of training samples   | 50000  | 50000 | 30000   | 75750 |\n| Number of classes  | 10      | 100   | 100   | 101  |\n| Each class calibration samples  | 500 |50 |150  |125 |\n| Imbalanced ratios  | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\} | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\} | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\}  | \\{ 0.5, 0.4, 0.3, 0.2, 0.1\\} |\n\n ​​\n**Q4: What's the worst under coverage ratio?**\n\nA4: \nWe add the experiments to report the **worst class-conditional coverage (WCCC) as a new metric** (Table 5 in PDF) on imbalanced mini-ImageNet datasets under the same setting from Table 16 in the Appendix. In WCCC, RC3P significantly outperforms CCP and Cluster-CP with $4.29\\\\%$ improvement. Similar improvements of RC3P can be found on other datasets.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kF6QvrsjAP", "reviewer": "Reviewer_2LUb", "summary": "This paper introduces the Rank Calibrated Class-conditional Conformal Prediction (RC3P) algorithm, designed to address the issue of large prediction sets in conformal prediction (CP), especially in imbalanced classification tasks. The RC3P algorithm enhances class-conditional coverage by selectively applying class-wise thresholding based on a label rank calibration strategy. This method reduces the size of prediction sets compared to the standard class-conditional CP (CCP) method while maintaining valid class-wise coverage. The authors demonstrate that RC3P achieves significant reductions in prediction set sizes across multiple real-world datasets.", "questions": "1) Can the authors provide more details on the computational complexity of the RC3P algorithm compared to the CCP and Cluster-CP methods?\n2) How does the RC3P algorithm perform on larger and more diverse datasets beyond the ones tested in this paper?", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The introduction of a rank calibration strategy to the class-conditional CP framework is a novel contribution. It offers a practical solution to the challenge of large prediction sets in CP, especially for imbalanced datasets.\n2) The paper provides comprehensive experimental results across various datasets and imbalance types, showing a significant reduction in prediction set sizes while maintaining valid class-wise coverage.\n3) The authors provide rigorous theoretical guarantees for the class-wise coverage and improved predictive efficiency of the RC3P algorithm, demonstrating its robustness and general applicability.\n4) The paper is well-structured and clearly written, with detailed explanations of the algorithm, theoretical analyses, and experimental setups.", "weaknesses": "1) While the paper provides theoretical guarantees for coverage, the theoretical analysis of the predictive efficiency could be expanded. Specifically, a deeper exploration of the conditions under which RC3P outperforms CCP in terms of predictive efficiency would strengthen the paper.\n\n2) Although the experiments are thorough, additional experiments on more diverse and larger-scale datasets could further validate the generalizability of the RC3P method.\n\n3) One additional comment is to verify the predictive efficiency using approximate conditional coverage metrics suggested in the literature, for example, by \"Cauchois, M., Gupta, S., and Duchi, J. (2021). Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22(81):1–42\" to ensure that approximate conditional coverage is not negatively impacted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.\n\n\n**Q1: The theoretical analysis of the predictive efficiency could be expanded.**\n\nA1: We agree that a deeper exploration of the conditions under which RC3P outperforms CCP would  strengthen our paper. However, predictive efficiency analysis is challenging and there is no existing theoretical framework for thoroughly analyzing the predictive efficiency of CP methods (most of them focus on coverage guarantees), especially for the class-wise coverage setting.  In an attempt to fill this gap in the current state of knowledge, we provide Lemma 4.2 and Theorem 4.3 to show under what conditions of the model, the predictive efficiency can be improved (See also **GR2**).\n\nWe highlight that **Lemma 4.2** is not our main intellectual contribution  for the improved predictive efficiency of RC3P. Instead, it showcases a condition number $\\sigma_y$ that **parametrizes** whether a target event $\\mathcal E$ “the predictive efficiency is improved by RC3P’’ happens or not, i.e., $\\sigma_y \\leq 1 \\Rightarrow \\mathcal E$.\n\nThen **Theorem 4.3** further analyzes the **transition** from the parameter $\\epsilon_y^{\\widehat k(y)}$ of RC3P to the parameter $\\sigma_y$ of the target event to indicate how to configure RC3P to improve predictive efficiency. Specifically, as pointed out in its Remark, if we set $\\alpha - \\epsilon_y^{\\widehat k(y)}$ as small as possible but still guarantee $\\epsilon_y^{\\widehat k(y)} < \\alpha$ (required by the model-agnostic coverage, Theorem 4.1) in RC3P, then we have a higher probability to guarantee $\\sigma_y \\leq 1$. Therefore, the overall **transition** of parameters is expressed by: \n$$\\text{Setting RC3P with (i) } \\epsilon_y^{\\widehat k(y)} < \\alpha, \\text{and (ii) } \\epsilon_y^{\\widehat k(y)} \\text{ as small as possible } ~~~ \\Longrightarrow ~~~ \\sigma_y \\leq 1 ~~~ \\Longrightarrow ~~~ \\mathcal E,$$ \nwhich is equivalent to (7) in Remark and helps us configure RC3P to most likely improve the predictive efficiency over baseline CCP method.\n\n\n\n\nIn addition to serving as a guideline for configuring RC3P to improve the predictive efficiency, we can further investigate how to interpret the involved condition, e.g., the defined terms D and B involve  properties of the underlying model. Further analyzing how to ensure a large $B-D$ can help guarantee the improved predictive efficiency of RC3P over CCP. For instance, according to the definition in Theorem 4.3, a small $D$ requires a high top-k accuracy. Given the challenging  nature of analyzing predictive efficiency, we will continue to expand the theoretical analysis as  part of immediate future work.\n\n**Q2: Additional experiments on more diverse and larger-scale datasets**\n\nA2:  \n**We add balanced experiment on diverse datasets (CIFAR-100, Places365, iNaturalist, ImageNet) in Experiment (1) of GR1** (see Table1 in the attached PDF).  The models are pre-trained. UCR is controlled to $\\leq 0.05$. RC3P significantly outperforms the best baseline with $32.826\\\\%$ reduction in APSS ($\\downarrow$ better) on average, with $10.539\\\\%$ on iNaturalist and $59.393\\\\%$ on ImageNet. We get similar improvements with APS and THR scoring functions.\n\nIn addition to the large-scale experiments on balanced data in Experiment (1) of GR1, in **Experiment (2)  Large-scale imbalanced classification experiment**  (Table 2 in PDF), we also tested baselines and RC3P on a large-scale dataset (ImageNet-LT) with a deep model trained from scratch using the imbalanced training method LDAM [r1]. UCR is controlled to $\\leq 0.12$. RC3P significantly outperforms the best baseline with $28.523\\\\%$ reduction in APSS ($\\downarrow$ better) on average.\n\n\n**Q3: Adding approximate conditional coverage metrics?**\n\nA3: We highlight that our goal is class conditional coverage, which is a parallel notion with the conditional coverage. Class-conditional coverage that is conditioned on (output space) each class, i.e., $Y = y$ while conditional coverage conditioned on the (input space) features $X \\in G$, i.e., $X$ belongs to “pre-specified groups”. We will add other approximate conditional coverage metrics in the revised version based on the recent work from Gibbs and Candes (2024).\n\n**Q4: The computational complexity of the RC3P, CCP and Cluster-CP**\n\nA4: Suppose $n_y = O(n/K)$, where $n_y$ is the number of calibration samples in each class $y$, $n$ is the total number of calibration samples, and $K$ is the number of candidate class labels. CCP needs to sort the conformity scores of each class to compute class-wise quantiles. The computational complexity for CCP is $O(n \\cdot \\log(n/K))$\n\nCompared with CCP, the additional process in RC3P is to find the rank threshold $\\hat k(y)$ for each class, where the computational complexity is either $O(n K)$ with brute-force search or $O(n \\log(K))$ with binary search over classes. Therefore, by combining the computation costs from rank calibration and score calibration in RC3P, we get the total complexity as $O(n \\cdot \\log(n/K) + n K)$ or $O(n \\cdot \\log(n/K) + n \\log(K))$. \n\nCluster-CP first runs $k$-means clustering algorithm where $k=M$ is the number of clusters. The computational complexity for the clustering algorithm is $O(M T n)$, where $T$ is the number of iterations. Then, Cluster-CP computes cluster-wise quantiles with time complexity as $O(n \\cdot \\log(n/M))$ where we assume the number of samples in each cluster is in $O(n/M)$. Therefore, the total computation complexity for Cluster-CP is $O(M T n + n \\log(n/M))$", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their constructive feedback. Below we provide a summary of our rebuttal for key questions from reviewers’ as a global response. 

\
**GR1. We added 7 new experiments for all CP baselines and RC3P** (We train the model from scratch in imbalanced settings by [r1])

**(1) Balanced experiment on diverse datasets (CIFAR-100, Places365, iNaturalist, ImageNet)**  (Table 1 in PDF), as suggested by Reviewer Bzsm.

In the table, RC3P significantly outperforms the best baseline with $32.826\\%$ reduction in APSS ($\downarrow$ better) on average, with $10.539\\%$ on iNaturalist and $59.393\\%$ on ImageNet. We get similar improvements with APS and THR scoring functions.
 
**(2)  Large-scale imbalanced classification experiment** (Table 2 in PDF), as suggested by Reviewer Bzsm and 2LUb.

RC3P significantly outperforms the best baseline with $28.523\\%$ reduction in APSS ($\downarrow$ better) on average.

**(3) Various sizes for the calibration sets** (Table 3 in PDF), as suggested by Reviewer Bzsm.

RC3P significantly outperforms the best baseline with $29.68\\%$ reduction in APSS ($\downarrow$ better) on mini-ImageNet. Similar improvements of RC3P can be found on other datasets.

**(4) Calibration with the THR scoring function** [r2] (Table 4 in PDF) for baselines and RC3P, as suggested by reviewer Bzsm. 

RC3P significantly outperforms best baselines with $26.9\\%$ on mini-ImageNet reduction compared with the best baseline. Similar improvements of RC3P can be found on other datasets.

**(5) Worst class-conditional coverage (WCCC) as a new metric under the same setting from Table 16 in the Appendix** (Table 5 in PDF) on imbalanced mini-ImageNet, as suggested by Reviewer vcMw.

In WCCC, RC3P significantly outperforms CCP and Cluster-CP with $4.29\\%$ improvement. Similar improvements of RC3P can be found on other datasets.

**(6) Class-wise score distribution as a concrete example of the explanation in Section 4.1** (Table 6 in PDF), as suggested by Reviewer vcMw.

**(7) Comparison without controlling UCR under the same setting with the main paper** (Table 7 in PDF), as suggested by Reviewer yaTg and Bzsm

We then use the total under coverage gap (UCG, $\downarrow$ better) as fine-grained metric for coverage. 
Conditioned on similar APSS of all methods, RC3P significantly outperforms the best baselines with 35.18% reduction in UCG on average.  

\
**GR2. Theoretical significance of Lemma 4.2 and Theorem 4.3?**

We highlight that **Lemma 4.2** is not our main intellectual contribution  for the improved predictive efficiency of RC3P. Instead, it showcases a condition number $\sigma_y$ that **parametrizes** whether a target event $\mathcal E$ “the predictive efficiency is improved by RC3P’’ happens or not, i.e., $\sigma_y \leq 1 \Rightarrow \mathcal E$.

Then **Theorem 4.3** further analyzes the **transition** from the parameter $\epsilon_y^{\widehat k(y)}$ of RC3P to the parameter $\sigma_y$ of the target event to indicate how to configure RC3P to improve predictive efficiency. Specifically, as pointed out in its Remark, if we set $\alpha - \epsilon_y^{\widehat k(y)}$ as small as possible but still guarantee $\epsilon_y^{\widehat k(y)} < \alpha$ (required by the model-agnostic coverage, Theorem 4.1) in RC3P, then we have a higher probability to guarantee $\sigma_y \leq 1$. Therefore, the overall **transition** of parameters is expressed by: 
$$\text{Setting RC3P with (i) } \epsilon_y^{\widehat k(y)} < \alpha, \text{and (ii) } \epsilon_y^{\widehat k(y)} \text{ as small as possible } ~~~ \Longrightarrow ~~~ \sigma_y \leq 1 ~~~ \Longrightarrow ~~~ \mathcal E,$$ 
which is equivalent to (7) in Remark and helps us configure RC3P to most likely improve the predictive efficiency over baseline CCP method.

\
**GR3. Why control UCR? How to control UCR?**

Why: While UCR is a coverage metric, fixing it to a certain value (e.g., 0) across methods allows us to ensure fair comparisons to get valid conclusions about the predictive efficiency of all CP methods.

Because coverage and predictive efficiency are two competing metrics in CP, e.g., achieving better coverage (resp. predictive efficiency) degenerates predictive efficiency (resp. coverage).
If we do not fix one of them, then we cannot conclude which CP method  has  better predictive efficiency by comparison. We add the experiments on balanced CIFAR-100 datasets without controlling the UCR. See the table below.

|Methods|CCP|Cluster-CP|RC3P| 
|-|-|-|-|
|UCR|0.444|0.446|0.228| 
|APSS|11.376|9.7865|10.712|

As shown, RC3P achieves the best coverage metric (UCR), while Cluster-CP achieves the best metric for prediction set sizes (APSS), so this comparison does not conclude which one  has higher predictive efficiency. Therefore, we fix UCR to first guarantee the class-conditional coverage, conditioned on which we can perform a meaningful comparison of predictive efficiency. This strategy is also discussed in [r3].

How:
We add an inflation quantity to the nominal coverage, i.e., $1-\alpha+g/\sqrt{n_y}$, where $g \in \\{0.25,0.5,0.75,1\\}$ is a tunable hyper-parameter and $n_y$ represents the number of calibration samples in each class $y$ (for CCP and RC3P) or each cluster (for Cluster CP). The structure $g/\sqrt{n_y}$ follows the format of generalization error when setting the empirical quantile, as in [r4]. We select the minimal value from the above range for $g$ such that UCR is under 0.16 on CIFAR-10 and 0.03 on other datasets due to the variability of data.


\
[r1] Cao et al, 2019. Learning imbalanced datasets with label-distribution-aware margin loss

[r2] Sadinle et al., 2019. Least ambiguous set-valued classifiers with bounded error levels

[r3] Fontana et al., 2023. Conformal prediction: a unified review of theory and new challenges

[r4] Vladimir Vovk, 2012. Conditional validity of inductive conformal predictors

Meta-review: The paper concerns the problem of conformal predictions. The Authors introduce a new algorithm that reduces the size of prediction sets to achieve class-conditional coverage, using an additional label rank calibration step. Theoretical analysis and experimental results are provided to justify the proposed solution in comparison to the baseline.

The paper is clearly presented and the introduced algorithm is novel, well-motivated and sound, supported by solid theoretical and empirical evidence. The reviewers raised several critical remarks, including inconsistency between motivations of the method and empirical studies (the absence of experiments on imbalanced datasets in the original submission), limitations in the theoretical analysis, unclear notation in some places, or the choice of benchmark datasets. The Authors prepared rebuttal with additional empirical results and clarifications regarding theoretical and empirical results. Overall, the reviewers are satisfied with the Authors' response.
Decision: Accept (poster)