Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration

We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.

Q1: The theoretical analysis of the predictive efficiency could be expanded.

A1: 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).

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.

In 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.

Q2: Additional experiments on more diverse and larger-scale datasets

A2:
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.

In 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.

Q3: Adding approximate conditional coverage metrics?

A3: 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).

Q4: The computational complexity of the RC3P, CCP and Cluster-CP

A4: 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))$

Compared 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))$.

Cluster-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))$

We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.

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.

A1: 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$.

Q2: Try to give a concrete figure example.

A2: We plot the class-wise score distribution as a concrete example of the explanation in Section 4.1 (Table 6 in PDF).

The 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.

Q3: Give a table of important dataset statistics?

A3: We show the description of datasets in the following table. Thank you for your suggestion.e will add it in the revised paper.

​​ Q4: What's the worst under coverage ratio?

A4: We 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.

We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.

Q1: Why only consider imbalanced datasets? Report the performance on balanced data?

A1: RC3P 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.

The 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.

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.

Q2: It may be unfair to compare these methods only on small-scale datasets.

A2: In 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.

Q3: Furthermore, the classical method THR[1] should be considered in the experiments.

A3: 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.

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.

A4: (See also GR2)

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.

Q5: What is the ratio of training set, calibration set and test set?

A5: We show the description of datasets in the following table. Thank you for your suggestion. We will add it in the revised paper.

Q6: Does RC3P still outperform other methods when the size of calibration set is small?

A6: 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.

Q7: How do you control the UCR of RC3P?

A7: (See also GR3*)

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

[r2] Ding et al., 2024. Class-conditional conformal prediction with many classes.

We thank the reviewer for the constructive feedback. Below we provide our rebuttal for the key questions from the reviewer.

Q1: R3CP heavily relies on the ranking of candidate class labels?

A1: RC3P 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.

The 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.

Q2: Lemma 4.2 not convincing and Theorem 4.3 not informative. Not clear why R3CP is better than CCP

A2: (See also GR2)

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.

Practical Implications for the analysis of predictive efficiency in experiments: We 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.

Our 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.

Q3: UCR is a metric and why would you be able to set it.

A3: (See also GR3*)

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 make 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 method has more predictive efficiency by comparison. We add the experiments on balanced CIFAR-100 datasets without controlling the UCR. See the table below.

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 is more efficient.

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 [r1].

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 [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.

We add the experiments without controlling UCR in Experiment (1) of GR1 (Table 7 in PDF) under the same setting with the main paper

The 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. We 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.

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

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