Class-Conditional Conformal Prediction for Imbalanced Data via Top-$k$ Classes

We thank the reviewer for their thoughtful comments and feedback.

Q1: The value of the k-CCP contribution over CCP is unclear. It seems relatively modest to restrict to the top-k classes.

A1: The $k$-CCP algorithm adapts the double calibration mechanism (calibration on both non-conformity score and ranks in Equation (9), instead of a single calibration in standard CCP) to take a good trade-off of coverage and efficiency. The key advantage of the additional calibration over rank is to exclude those data where their true labels are ranked beyond top-$\widehat k(y)$ positions (i.e., poorly predicted data) in the calibration process, which in turn helps remove labels beyond top-$\widehat k(y)$ positions in the testing process.

Q2: The importance of Theorem 2 and the numerical results are unclear.

A2: The contribution of Theorem 2 is to theoretically identify the source of reduced prediction set sizes by $k$-CCP, so that it enables verification in experimental results shown in Figure 1 (last column). We additionally verify it on calibration data in Figure 24 of the updated paper. We believe that Theorem 2 reveals this insight/knowledge and wraps up the key factors into the condition numbers $\sigma_y$.

Our experiments on multiple benchmark datasets demonstrate the following three remarks.

(i) MCP fails to provide class-conditional coverage in the first columns of Figure 1 and 4 .

(2) $k$-CCP produces smaller prediction sets over the baseline CCP method in Table 1. We also added Table 15, 16, and 17 in our revised paper to compare $k$-CCP with cluster-CP [R20] (a newly added baseline for achieving approximate class-conditional coverage) with APS score function (Table 15) and RAPS score function [R21] (Table 16). Moreover, we perform comparison between $k$-CCP and the above CP algorithms using a conformalized training algorithm [R22] (Table 17).

(3) The condition numbers $\sigma_y$ in Theorem 2 are valid and verified in the last columns of Figure 1 and 4. We also added Figure 24 in our revised paper that verifies these condition numbers on calibration data.

Q3: For the theorem, the condition is fairly unintuitive.

A3: The condition (12) in Theorem 1 in the revised paper follows the algorithmic design in Algorithm 1, i.e., iterating over all classes, which results in the summation over $y \in \mathcal Y$ in (12). Within each element (a fixed $y$), we define a condition $\sigma_y$ as the source of the reduced prediction set size for $k$-CCP. This insight can be easily verified in experiments (The last columns of Figure 1 and 4) and theoretically supports smaller prediction sets from $k$-CCP.

Q4: For the numerical results, e.g., Table 1 (Table 15 and 16 in our revised paper), I'm not sure that setting the UCR of k-CCP and CCP to be the same necessarily leads to a fair comparison.

A4: It is necessary to set UCR to the same value (also close to $0$) for all methods, because it is a measure of the violation of class-conditional coverage. Our paper studies the efficiency of CP methods that guarantees the class-conditional coverage. If UCR is not close to $0$ (like MCP), we cannot verify the class-conditional coverage is achieved, so that it is consequently not meaningful to compare prediction set sizes as the measure of efficiency.

Q5: A concrete example instead of or combined with Proposition 1 would help. It seems like a more intuitive example could be provided.

A5: We would like Proposition 1 to be a general and easy-to-verify theoretical result. This is why we did not connect it to the learning observation (recall that a key advantage of CP is model-agnostic, i.e., invariant to the learning algorithm). Instead, we can easily interpret from Proposition 1 and experiments to verify the conditions. The first columns of Figure 1 and 4 show the ease of under-coverage of MCP over each class, which in fact provides a concrete illustration for Proposition 1.

Q6: The algorithms could be written out more clearly without referencing theorems, remarks, and equations in the main text.

A6: Thank you for your suggestion. We have revised $k$-CCP in the Algorithm 1 (in our updated paper) by linking Line 5 to the new Equation (11) in the updated paper, i.e., $\widehat k(y) = \min\{ c \in [C]: \frac{1}{n_y} \sum_{i \in \mathcal I_y} 1[ r_f(X_i, Y_i) > c ] \leq \alpha - g / \sqrt{n_y} \}$, where $1[]$ is the indicator function.

[R20] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.

[R21] Angelopoulos, A., Bates, S., Malik, J., & Jordan, M. I. (2020). Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.14193.

[R22] Stutz, D., Cemgil, A. T., & Doucet, A. (2021). Learning optimal conformal classifiers. arXiv preprint arXiv:2110.09192.

We thank the reviewer for their thoughtful comments and feedback.

Q1: The proof demonstrating superiority to naive CCP relies on a strong assumption.

A1: Theorem 2 is a general result and depends on very mild assumptions.

1. No assumption on top-$k$ accuracy

We clarify that our $k$-CCP algorithm is model-agnostic, since it does not impose any assumed properties of the learned classifier and can be used with any pre-trained classifier. The only extra information (compared with standard CP, such as MCP and CCP) is to estimate the top-$k$ accuracy (or equivalently, top-$k$ error in Remark 2) to determine the calibrated rank $\widehat k(y)$. However, estimation of the top-$k$ error does not make any assumption on the learned classifier, since taking different values of $\widehat k(y)$ from $1$ to $C$ gives a full span of $[0, 1]$ for top-$k$ accuracy. Therefore, our method remains valid and practically classifier agnostic.

2. Assumption in Equation (10) (Equation (12) in our updated paper) is commonly satisfied

The only assumption of condition numbers $\sigma_y$ in Equation (12) is commonly satisfied and supported by empirical results (see Section 5.2, Figure 1, the last column with the standard training process). In addition, in Figure 24 of the updated paper, we also verify this assumption firmly holds on the calibration set.

Q2: The notation of the paper is slightly confusing. Using $r_f(X,Y)$, where $X,Y$ are datasets. However, earlier, using $r_f(X_{n+1},y)$ correspond to a specific datapoint $X_{n+1},y$. Which is it?

A2: We summarize our main notations in Section 2. Specifically, “$(X, Y)$ is a data sample”, and $\mathcal D$ denotes the dataset, e.g., the training set $\mathcal D_{\text{tr}}$ and the calibration set $\mathcal D_{\text{cal}}$. Moreover, $r_f(X, Y)$ denotes the rank of the ground-truth label $Y$ predicted by the classifier $f$ on input $X$.

In Equation (3) of Section 3, we introduce “a new testing input $X_{n+1}$”. Accordingly, in Section 4.1 and 4.2, $r_f(X_{n+1}, y)$ denotes the rank of $y$ (this $y$ may be any label rather than the ground-truth one) predicted by classifier $f$ on the testing data $X_{n+1}$, where $y$ is a fixed label. Both CCP and $k$-CCP require iterating over all possible $y$ from $\mathcal Y$ (in our multiclass case, $\mathcal Y = \{1, \cdots,C\}$ for a total of $C$ classes).

Q3: The computation of $\hat k(y)$ that achieves sufficiently small ϵy seems very difficult. Indeed, the equation provided to calculate this calibrated class value seems very computationally expensive to find.

A3: Verifying if Equation 10 is satisfied in practice does not require significant computation/data overhead. The complexity for verification is $O(n C)$ (or improved to $O(n \log(C))$ with binary search over classes from top-$1$ to top-$C$ for a large value $C$) with $n$ calibration samples (or $n$ testing samples if verification on testing data) and $C$ classes. Under the standard i.i.d. condition, the empirical estimates approximate population values in $O(1/\sqrt{n})$.

Q4: Comparing a method for which the hyperparameters have been extensively tuned to another algorithm for which this is not the case is not a fair empirical comparison.

A4: Our $k$-CCP does not require more hyper-parameters to be tuned compared with baselines CCP and cluster-CP [R13] (an added baseline in the updated paper, Table 1, 15, 16, and 17, Figure 1, 2, 4, 5, and 24 in our updated paper). The only hyper-parameter $g$ has to be tuned for each CP method to achieve class-conditional coverage (their UCR close to $0$), under which we can compare their prediction set sizes as an efficiency measure. As a result, we believe our experiments provide a fair comparison.

Q5: Moreover, a detailed section on the computability of the calibrated class is in order.

A5: See A3 above Q3.

Q6: The assumption in Theorem 2, i.e., equation 10 (Equation (12) in our updated paper), is a very strong assumption.

A6: See A1 above Q1.

Q7: Do existing conditional coverage methods [12] achieves suboptimal set length compared to this weaker notion of conditional coverage.

A7: Indeed the class-conditional coverage is a special notion of general conditional coverage (such as the group-conditional coverage of Mondrian conformal predictor [R18], [R13]). However, the general conditional CP can be realized to multiple subtypes, including attribute conformal prediction [R18] and input-conditional conformal prediction [R19]. Consequently, these different realized algorithms for various conditional coverages are not directly comparable.

In our experiments, we have selected the CCP which is introduced in [R16] (also refer to [R17]) as the baseline, without comparing with other non-comparable conditional CP methods. In addition, we added a new baseline cluster-CP [R13], a CP method that achieves class-conditional coverage under some conditions over the learned clustering function.

Q8: If the nominated coverage $\tilde \alpha$ is larger than $\alpha$, then why are the generated sets shorter? Is it because this allows for the use of only the top-$k$ classes, which shortens the intervals?

A8: Yes, the additional calibration for the top-$k$ class improves efficiency (produced smaller prediction sets). The $k$-CCP algorithm adopts the double calibration mechanism to achieve improved trade-off between coverage and prediction set size. The key advantage of the additional calibration over rank is to exclude those data where their true labels are ranked beyond top-$\widehat k(y)$ positions (i.e., poorly predicted data) in the calibration process, which in turn helps remove labels beyond top-$\widehat k(y)$ positions in the testing process.

Q9: In the experiments, how were the hyperparameters chosen? Were the hyperparameters for the baselines chosen in a similar manner to that of the proposed method?

A9: See A4 above Q4.

Q10: Do existing works guarantee that their method of CCP outperforms the naive CCP method in terms of the size of the prediction set, or is this unique to this work?

A10: We add a baseline cluster-CP [R13] that achieves approximate class-conditional coverage (see Table1, 15, 16, and 17 in the updated paper) and find our $k$-CCP out performs it in efficiency. In [R13], the authors empirically showed improved efficiency, but did not provide theoretical analysis or guarantee. In contrast, our paper theoretically analyzes the factors ($\sigma_y$ in Theorem 2) that reduce prediction set sizes of our $k$-CCP and also verifies in experiments in the last column of Figure 1 (we further verify these condition numbers on calibration data in Figure 24 of the updated paper).

Q11: Only compare the method to the simplest baseline of CCP.

A11: We added the following experimental results as requested by the reviewers.

(1) Comparison with Cluster-CP [R13], an accepted NeurIPS-2023 paper, using both APS and RAPS scoring functions

(2) Comparison experiments for MCP [R14], CCP [R16], [R17], Cluster-CP, and $k$-CCP with both APS and RAPS scoring functions

(3) Comparison experiments with conformal training to show the synergistic benefits of CP methods including $k$-CCP using a better classifier

(4) Ablation study for hyper-parameter $g$ with CCP, Cluster-CP, and $k$-CCP

(5) Verification of $\sigma_y$ on calibration data for different datasets

Input space conditional CP methods pointed out by reviewers are not applicable for output space conditional CP (i.e., class-conditional CP). So we could not add such comparison experiments. We would like to point out that we included all the baselines used by the Cluster-CP paper which is accepted for publication at NeurIPS-2023.

Q12: An ablation study on how different values of $g$ affect the generated length of the sets.

A12: We add the ablation study to verify how hyper-parameter $g$ affects the performance of CCP, cluster-CP, and $k$-CCP. We use the under coverage ratio (UCR) and average prediction set size (APSS) as metrics (see Figure 2, 5, and 23 in the updated paper). According to the results, we observe that UCR and APSS of $k$-CCP are much smaller than CCP and cluster-CP with the same $g$ value. It verifies that $k$-CCP achieves a better trade-off between coverage and prediction set size.

[R13] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.

[R14] Romano, Y., Sesia, M., & Candes, E. (2020). Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33, 3581-3591.

[R15] Feldman, S., Bates, S., & Romano, Y. (2021). Improving conditional coverage via orthogonal quantile regression. Advances in neural information processing systems, 34, 2060-2071.

[R16] Angelopoulos, A. N., & Bates, S. (2021). A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511.

[R17] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475–490. PMLR, 2012

[R18] Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world (Vol. 29). New York: Springer.

[R19] Sesia, M., & Romano, Y. (2021). Conformal prediction using conditional histograms. Advances in Neural Information Processing Systems, 34, 6304-6315.

We thank you for your valuable and insightful review; we appreciate your increasing score.

FQ1: $\sigma_y$ is strictly less than $1$, so the Condition from Equation 12 should always be satisfied. Is this not true?

A1: Yes. The empirical verification results show a stronger condition ($\sigma_y$ is much smaller than 1 for all $y$, see the last column of Figure 1 and Figure 4 in our revised paper ), which ensures that the assumption in Theorem 2 (Equation (12) ) is always satisfied. Note that the reduction in prediction set size of $k$-CCP over CCP is proportional to how small the $\sigma_y$ values are, which are classifier-dependent.

FQ2: The only weakness I have is that there should still be more baselines.

A2: We highlight that our revised paper includes a comprehensive comparison with most class-conditional conformal prediction algorithms, such as Cluster-CP [R23] and [R25] based CCP as baselines. For example, all baselines compared in [R23] are denoted as ''MCP‘’ and ''CCP‘’ in our paper. Note that [R23] is a NeurIPS-2023 accepted paper and our paper has all the baselines included in that paper. We note that papers mentioned by reviewers on conditional CP methods for input space [R26, R27]are not applicable to output space, i.e., the class-conditional setting. We updated the related work in the revised paper.

FQ3: The notes on computability of $\widehat k$, the ablations of $g$, and the remarks on when the assumption from equation 12 is satisfied should be added to the camera-ready version.

A3: Thank you for your suggestions. We have added the computability of $\widehat k$, the condition explanation of Equation (12), the ablation study of $g$, and the overall experiments with a new baseline [R23] and new score function [R21] in our updated paper. The revised paper reflects the camera copy version with all the changes.

[R23] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335. Accepted for NeurIPS-2023.

[R24] Angelopoulos, A., Bates, S., Malik, J., & Jordan, M. I. (2020). Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.14193.

[R25] Stutz, D., Cemgil, A. T., & Doucet, A. (2021). Learning optimal conformal classifiers. arXiv preprint arXiv:2110.09192.

[R26] Isaac Gibbs, John J Cherian, and Emmanuel J Cand`es. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.12616, 2023

[R27] Shai Feldman, Stephen Bates, and Yaniv Romano. Improving conditional coverage via orthogonal quantile regression. Advances in neural information processing systems, 34:2060–2071, 2021.

We thank the reviewer for their thoughtful comments and feedback.

Q1: The terminology is sometimes somewhat non-standard. CCP from the paper is often called Mondrian conformal prediction in the literature.

A1: Thank you for your suggestion, but our $k$-CCP is not a Mondrian conformal predictor. In fact, Mondrian conformal prediction (MCP) is a general procedure that encompasses many kinds of conditional conformal prediction [R11] [R12], including class conditional conformal prediction and group (attribute) conditional conformal prediction, etc. Our paper focuses on only class-conditional conformal prediction, instead of the general conditional coverage. Therefore, we use the terminology “class-conditional conformal prediction” to represent the relevant algorithms.

Q2: Proposition 1 feels a bit overly complex. Although technically sound, the content should be straightforward. This has also been discussed in a recent paper by Ding et al. "Class-conditional conformal prediction with many classes", Neurips 2023

A2: Proposition 1 is a general result to show the ease of under-coverage for Marginal CP. Technically, we only use very mild assumptions in Equation (7) as the condition for the violation of class-conditional coverage. Although other literature may discuss the same observation, our Proposition 1 theoretically quantifies the gap of class-conditional coverage and importantly makes this quantity easily verifiable in experiments (See the first column of Figure 1 and 4).

Q3: What Theorem 2 contributes. The theorem more or less assumes that the new method is better (the sigma factors), so obviously it will be better on average.

A3: The contribution of Theorem 2 is to theoretically identify the source of reduced prediction set sizes by $k$-CCP, so that it enables verification in experimental results shown in Figure 1 (last column). We additionally verify it on calibration data in Figure 24 of the updated paper. We believe that Theorem 2 reveals this insight/knowledge and wraps up the key factors into the condition numbers $\sigma_y$.

[R11] Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world (Vol. 29). New York: Springer.

[R12] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.

Q12: How the proposed method compares to other approaches with conditional guarantees such as [R5], or other approaches to improve the size of the prediction sets [R6].

A12: The target of [R5] is conditional coverage conditioned on the (input space) feature $X \in G$, i.e., $X$ belongs to “pre-specified groups”. Instead, our paper focuses on the class-conditional coverage that is conditioned on (output space) each class, i.e., $Y = y$. We believe these two coverage guarantees are not comparable. [R6] proposed a training algorithm that aims to improve the size of prediction sets constructed by the subsequent CP algorithms. In contrast, our $k$-CCP is a model-agnostic (not a training algorithm) class-conditional CP algorithm with smaller prediction sets. Consequently, [R6] and our $k$-CCP are not comparable. However, we can still compare the efficiency of our $k$-CCP with other baselines based on the model trained by the learning algorithm in [R6]. We add these experimental results in Table 17 in the updated paper to compare $k$-CCP with CCP and cluster-CP [R6] based on two score functions (APS and RAPS [R4]) using the model trained by [R5]. Results still verify that our $k$-CCP significantly reduces the size of prediction sets.

[R4] Angelopoulos, A., Bates, S., Malik, J., & Jordan, M. I. (2020). Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.14193.

[R5] Gibbs, I., Cherian, J. J., & Candès, E. J. (2023). Conformal Prediction With Conditional Guarantees. arXiv preprint arXiv:2305.12616.

[R6] Stutz, D., Cemgil, A. T., & Doucet, A. (2021). Learning optimal conformal classifiers. arXiv preprint arXiv:2110.09192.

[R7] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.

[R8] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475–490. PMLR, 2012

Q6: Showing that MCP does not necessarily provide class-conditional guarantees does not seem as a strong motivation for the current work.

A6: We do not use the fact that MCP does not guarantee class-conditional coverage as the only key motivation. Instead, we use its failure analysis to highlight the ease of under-coverage on imbalanced data (see the first column of Figure 1 for significant deviation of class-wise quantiles even for relatively balanced data where $\rho = 0.5$). On the other hand, the existing CCP method guarantees the class-conditional coverage but produces large prediction sets. These two observations together motivate the need for efficient CP algorithms which provide class-conditional coverage with small prediction sets.

Q7: Typos, grammatical errors and presentation in text and captions in the paper.

A7: Thank you for your careful corrections and suggestions. We will fix typos, grammatical errors, unclear presentation and complicated notations in text/tables/captions in the revised paper.

Q8: In page 5, in the definition of the top-k error it the random variable $Z$ is not defined. Also, in the same paragraph $\hat k(y)$ is not formally defined and lack of the difference of $k(y)$ and $\hat k(y)$.

A8: We highlight that $\widehat k(y)$ is formally defined in Equation (9) and the paragraph before Theorem 1. Later we introduce how to determine its value in Remark 2. However, we do not use $k(y)$ in our paper. For the notation $Z$, we define it as $Z = (X, Y)$ as the features-label pair. We will include a clear definition of the random variable $Z$ in revision.

Q9: It is not clear why $\sigma_y$ is necessary in (10), as the denominator cancels out.

A9: We use $\sigma_y$ for a simpler notion of the condition number of the learned classifier. Our ablation study verifies the validity of Theorem 2 (see Section 5.2, the last column of Figure 1, $\sigma_y$ is exactly the X-axis).

Q10: The under coverage indicator in the Under Coverage Ratio assumes a fixed calibration set. However, conformal coverage guarantees on $1−\alpha$ are in expectation over the calibration set and the test sample. As a result the UCR definition appears incorrect.

A10: We disagree that the UCR definition appears incorrect as a measure of under-coverage. Although CCP algorithms guarantee class-conditional coverage in expectation, we do not have access to the underlying distribution, so we can only measure the coverage empirically. As a result, we define UCR as the measure of under-coverage on a realized testing set, i.e., it is the percentage of classes on which under-coverage occurs. To better avoid the bias of the realized testing set, we also “repeat experiments over 10 different random calibration-testing splits and report the average performance with standard deviation”. Therefore, we believe UCR is a reasonable metric to measure the class-conditional coverage and provides a fair condition for efficiency (prediction set size) comparison over CP methods.

Q11: There is no comparison with CPP using the RAPS method [R4].

A11: We added the following experimental results as requested by the reviewers.

(1) Comparison with Cluster-CP, an accepted NeurIPS-2023 paper, using both APS and RAPS scoring functions

(2) Comparison experiments for MCP, CCP, Cluster-CP, and $k$-CCP with both APS and RAPS scoring functions

(3) Comparison experiments with conformal training to show the synergistic benefits of CP methods including $k$-CCP using a better classifier

(4) Ablation study for hyper-parameter $g$ with CCP, Cluster-CP, and $k$-CCP

(5) Verification of $\sigma_y$ on calibration data for different datasets

Input space conditional CP methods pointed out by reviewers are not applicable for output space conditional CP (i.e., class-conditional CP). So we could not add such comparison experiments. We would like to point out that we included all the baselines used by the Cluster-CP paper which is accepted for publication at NeurIPS-2023.

We thank the reviewer for their thoughtful comments and feedback.

Q1: Assumptions on the classifier make the method no longer applicable as a post-hoc procedure working with a black-box ML model. In addition, in realistic scenarios it may be hard to make valid assumptions on the top-k accuracy of the classifier.

A1: No, $k$-CCP does not make assumptions on the top-$k$ accuracy to configure (see Theorem 1 and Remark 2).

$k$-CCP degenerates to CCP in the worst-case when the label rank threshold for each class is set to the total number of classes. Intuitively, the reduction in prediction set sizes from $k$-CCP over CCP depends on how small the label rank thresholds are which is classifier-dependent. If the top-$k$ accuracy of the classifier is good, then we will achieve significantly small prediction sets using $k$-CCP (Theorem 2 and condition numbers $\sigma_y$). Our experimental results on four diverse datasets demonstrate that $k$-CCP significantly reduces prediction set size over CCP and Cluster-CP (NeurIPS-2023 paper).

Q2: The authors do not elaborate on this overhead neither on the process of selecting the hyper parameter as well as the implications that this process can have.

A2: Tuning the hyper-parameter $g$, similar to the model selection process for the other hyper-parameters like learning rate, only requires minor computational overhead. We select the $g$ from the interval [0.1, 1] to find the minimal $g$ that UCR of $k$-CCP and CCP equal to $0$. The detailed tuning approach is introduced in Remark 2 and Appendix C.2. Moreover, it is necessary for every CP method (including compared baselines) to tune the effective $1-\alpha$ to ensure their UCR is smaller than a universal threshold close to $0$ in practical experiments (refer to our response to Q12 for why UCR has to be set near $0$ for all class-conditional CP methods uniformly). In other words, tuning this hyperparameter $g$ for $k$-CCP does not cost more overhead compared to baselines.

Q3: It is not clear if the proposed $\hat k$ will never be such that it violates the target coverage $1−\alpha$.

A3: Under the standard i.i.d. condition, the estimated top-$k$ error concentrates around the population value. Although a concentration error occurs, it is in $O(1/\sqrt{n})$ and can be merged with the tuning process of the hyper-parameter $g$ for estimating the quantile $Q_{1-\alpha}^{\text{class}}$ (their concentration errors are in the same order). As a result, the calibrated $\widehat k(y)$ can be accurate enough to achieve the target class-conditional coverage as demonstrated by our strong empirical results across multiple benchmark datasets.

Q4: A definition of $\hat k$ in theorem 1 as well as guarantees that the error terms in theorem 1 are small or can be small with high probability for that $\hat k$ could strengthen the contribution.

A4: The notion of $\widehat k(y)$ is given in Equation (9) and the paragraph before Theorem 1 provides this detail, which says ``can be any integer from $1$ to $C$‘’. We do not determine the value of $\widehat k(y)$ because we would like Theorem 1 to be general. In Remark 2, we give how to determine their values from the feasible set in a unified framework that meanwhile handles the constant $g$ from concentration errors. For the top-$k$ errors ($\epsilon_y$ in our paper), we do not assume they are very small. Instead, we select the value $k$ such that the corresponding top-$k$ error stays in a certain range, i.e., $\leq \alpha - g/\sqrt{n_y}$. Among these feasible values, we pick the minimal one, i.e., determining $\widehat k(y)$ as per Remark 2. As for the concentration errors ($\varepsilon_{n_y}$ in our paper), it depends on the number of class-wise calibration samples $n_y$.

Q5: This assumption seems to depend on the probability distributions that may be hard to safely evaluate and verify in practice without a significant data overhead. It would be very useful to provide insights, or data efficient method with which one could check if (10) is satisfied.

A5: Verifying if Equation 10 is satisfied in practice does not require significant computation/data overhead. The complexity for verification is $O(n C)$ (or improved to $O(n \log(C))$ with binary search over classes from top-$1$ to top-$C$ for a large value $C$) with $n$ calibration samples (or $n$ testing samples if verification on testing data) and $C$ classes. Under the standard i.i.d. condition, the empirical estimates approximate population values in $O(1/\sqrt{n})$.

In our verification experiments, it reduces to verifying if condition numbers $\sigma_y \leq 1$. If calibration data and testing data are i.i.d., then this verification experiment can also be done on the calibration set (See Section I, Figure 24 in our updated paper).

Q7: If we will have a larger set-valued prediction for the ''majority'' classes.

A7: We added new experiments to compare the average prediction set size of majority, medium, and minority groups in MCP, CCP, cluster_CP [R9], and $k$-CCP (See Figure 21 with APS scoring function and Figure 22 with RAPS [R10] scoring function in Appendix H of the revised paper). We select the top $1/4$ classes of the largest number of data to the majority group. Similarly, we assign the bottom $1/4$ classes of smallest number of data to the minority group and the remaining $1/2$ classes to the medium group. In conclusion, for the same CP method, we find that the group-wise average prediction set sizes do not differ too much, while the sizes generated by different CP methods can be large, e.g., $k$-CCP outperforms baselines significantly.

[R9] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.

[R10] Angelopoulos, A., Bates, S., Malik, J., & Jordan, M. I. (2020). Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009.14193.

We thank the reviewer for their thoughtful comments and feedback.

Q1: The purposed method heavily relies on the ranking of candidate class labels by the classifier, which could be a limitation if the classifier's ranking is not reliable.

A1: No, $k$-CCP does not make assumptions on the top-$k$ accuracy to configure (see Theorem 1 and Remark 2).

$k$-CCP degenerates to CCP in the worst-case when the label rank threshold for each class is set to the total number of classes. Intuitively, the reduction in prediction set sizes from $k$-CCP over CCP depends on how small the label rank thresholds are which is classifier-dependent. If the top-$k$ accuracy of the classifier is good, then we will achieve significantly small prediction sets using $k$-CCP (Theorem 2 and condition numbers $\sigma_y$). Our experimental results on four diverse datasets demonstrate that $k$-CCP significantly reduces prediction set size over CCP and Cluster-CP (NeurIPS-2023 paper).

Q2: Chapter 3 appears somewhat redundant. Using an overall score for each class in conformal prediction (MCP) would lead to marginal coverage rather than class-specific coverage seems evident. Previous works by (Lei, 2014; Sadinle et al., 2019) studied overall coverage and class-specific coverage separately.

A2: We do not use the fact that MCP does not guarantee class-conditional coverage as the only key motivation. Instead, we use its failure analysis to highlight the ease of under-coverage on imbalanced data (see the first column of Figure 1 for significant deviation of class-wise quantiles even for relatively balanced data where $\rho = 0.5$). On the other hand, the existing CCP method guarantees the class-conditional coverage but produces large prediction sets. These two observations together motivate the need for efficient CP algorithms which provide class-conditional coverage with small prediction sets.

Q3: In Theorem 2, could assumption (10) (Equation (12) in our updated paper) be too strong to achieve?

A3: The assumption of condition numbers $\sigma_y$ in Equation (12) is commonly satisfied and supported by empirical results (see Section 5.2, Figure 1, the last column with the standard training process). In addition, in Figure 24 of the updated paper, we also verify this assumption firmly holds on the calibration set.

Q4: How this assumption was validated?

A4: To verify the assumption in Equation (10), we directly estimate the empirical values of $\sigma_y$ for each class label $y$ on testing data (Section 5.2, the last column of Figure 1). For fixed $y$, we go over all testing samples $X_{n+1}$ and calculate the frequencies of two events: (1) the joint event “the coverage of non-conformity scores and calibrated rank”, i.e., $V(X_{n+1}, y) \leq \widehat Q_{1-\tilde \alpha}^{\text{class}}$ with $\tilde \alpha \leq \alpha$” and meanwhile the rank of $y$ stays in top-$\widehat k(y)$, i.e., $r_f(X_{n+1}, y) \leq \widehat k(y)$

(2) the event “the coverage of non-conformity scores”, i.e., $V(X_{n+1}, y) \leq \widehat Q_{1-\alpha}^{\text{class}}$ with nominated mis-coverage $\alpha$”.

After that, we compute the fraction of these two frequencies, to estimate $\sigma_y$.

Q5: How can we choose $k$ by hyper-parameter $g$ in general?

A5: In Appendix C.2, we explained that we selected the value of $g$ from the interval $[0.1, 1]$ in increments of $0.05$ to find the minimal $g$ that $k$-CCP and CCP achieved the target class conditional coverage. We will move this explanation to the main text in the revised paper.

Q6: Present the comparison of the overall average prediction lengths.

A6: We report the overall average prediction lengths on the balanced testing set. Because our goal is class-conditional coverage, the macro average prediction set size is more suitable for fair comparison. Additionally, we use a balanced calibration dataset, even though the training dataset itself is imbalanced. It means that the macro average prediction set size equals the micro average prediction set size, which is also adapted by another class conditional conformal prediction method [R9].

Thank you for your detailed responses which I have carefully reviewed. While they haven't altered my initial assessment of the paper, I appreciate the clarity and effort put into addressing the concerns raised.

CQ7: Is there any baseline other than CCP [R1], [R2] for class conditional conformal prediction?

A7: We added an additional baseline cluster-CP [R3] that achieves approximate class-conditional coverage (see Table 15, 16, and 17 in the updated paper) and found that $k$-CCP outperforms it by producing significantly smaller prediction sets. In [R3], the authors empirically showed improved efficiency (small prediction sets), but did not provide theoretical analysis for exact class-conditional coverage. Moreover, their class-conditional coverage guarantee requires sufficiently good performance on the clustering map (see Proposition 3 therein). In contrast, our $k$-CCP does not. Instead, $k$-CCP is adaptive and classifier-agnostic (see our response to CQ1 above).

CQ8. Typos, grammatical errors, and presentation in text and captions in the paper.

A8: Thank you for your careful corrections and suggestions. We have fixed typos, grammatical errors, unclear presentation, and complicated notations in text/tables/captions in the revised paper and highlighted the new changes using blue color.

[R1] Angelopoulos, A. N., & Bates, S. (2021). A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511.

[R2] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475–490. PMLR, 2012

[R3] Ding, T., Angelopoulos, A. N., Bates, S., Jordan, M. I., & Tibshirani, R. J. (2023). Class-Conditional Conformal Prediction With Many Classes. arXiv preprint arXiv:2306.09335.