Conformal Prediction for Deep Classifier via Truncating

Thank you for the constructive and elaborate feedbacks. Please find our response below:

1. Asymptotic marginal coverage [W1&Q1]

Thank you for suggesting the use of two calibration steps for CP. In case of misunderstanding, we evaluate the following two variants of PoT:

Method 1(PoT-1). We equally split the total calibration set and then use the first subset to calculate $r^*$ (like PoT). The second calibration set is used to calculate the threshold $\hat{Q}$.

Method 2(PoT-2). We equally split the calibration set into two subsets. The first subset is used to calculate $r^*$ (as in PoT). For the second subset, we exclude samples where the ground truth label's rank exceeds $r^*$. The remaining samples are used to calculate the threshold $\hat{Q}$.

Both PoT-1 and PoT-2 construct their final prediction sets following the same approach as PoT. We evaluated these methods on the ImageNet dataset using Average Prediction Size (APS) across 10 independent trials.

As shown in the tabel below, the base method, PoT, and PoT-1 achieve valid empirical coverage. Among these methods, PoT achieves the smallest average set size across multiple models. PoT-1 shows comparable efficiency to PoT and warrants further investigation in our future work.

2. Asymptotic marginal coverage [W2]

When the oracle model is available, the ground-truth label would always be ranked first, resulting in $r^*$=1. However, in practice, the rank of the ground-truth label is unknown and unpredictable. Therefore, we can estimate $r^*$ more precisely with the calibeation set size n approaching infinity, where this optimal $r^*$ value need not be equal to K.

Experimental results in Figures 3 and 5 demonstrate that PoT consistently reduces the average size of prediction sets compared to standard CP. This misleading trend can be explained by the calibration set size: when the calibration set is too small, the threshold (defined in Equation 1) may be imprecise, resulting in large reductions from PoT.

3. Typos and sandard errors of results [Q2]

Thank you for the correction and suggestion. We have added the standard errors in our manuscript.

Thank you for implementing the PoT-1, which is the method I had in mind. The PoT-2 method is invalid due to the selection process. I strongly encourage the authors to prove that PoT-1 attains CP-like finite sample guarantees in this submission; this is in line with Weakness 2 raised by Reviewer GSMe.

When the oracle model is available, the ground-truth label would always be ranked first

This statement is incorrect. For example, take a 3-class classification with P[Y=1|X=x] = 0.5, P[Y=2|X=x] = 0.4, P[Y=3|X=x] = 0.1. Then the "ground truth" label is a sample from this distribution. Here, w.p. 0.1 the rank can be 3 and the classifier is the oracle.

In light of this, I kindly ask the authors to update their comment to my concern: I expect that for well-fitted classifiers, the value of r* would increase as the size of the calibration set increases.

We appreciate the reviewer's recognition and valuable suggestions. Please find our response below:

1. Further clarification of motivation [W1]

We agree that the broader implications of reducing conformal prediction set sizes deserve more emphasis in our paper. We rephrase the second paragraph of Introduction as follows:

In addition to the marginal coverage, the length of the prediction set refers to the efficiency. Higher efficiency (i.e., smaller prediction sets) could speed up the decision-making process or assist users in better assessing the model's reliability. For instance, in medical diagnosis, smaller prediction sets enable doctors to make faster and more focused decisions while maintaining uncertainty awareness, and in autonomous driving, compact prediction sets allow systems to react more quickly while preserving safety guarantees. Thus, improved efficiency could enhance the practicality of CP in modern machine learning systems, bridging the gap between theoretical guarantees and real-world deployability.

2. The average set size of under coverage and over coverage [W2]

Thanks for the suggestion. We analyze the prediction set sizes using four metrics: 'Size' (total average size), 'NoE' (average size excluding empty sets), 'CovS' (average size of sets containing ground-truth labels), and 'UCovS' (average size of sets excluding ground-truth labels). We conducted experiments on ImageNet using APS with significance level $\alpha$ = 0.1. As shown in the following Table, PoT-CP effectively reduces both 'NoE' and 'CovS' while maintaining stable 'UCovS' values. We add the empirical results to Appendix E of the revised manuscript.

3. Clarification for uncertainty [W3]

Sorry for the misunderstanding sentence. In this work, we use non-conformity scores (e.g., 1-class probability or APS) to quantify prediction uncertainty. Specifically, for a given input $\boldsymbol{x}$, a higher non-conformity score $V(\boldsymbol{x},y_2) > V(\boldsymbol{x},y_1)$ indicates greater uncertainty in predicting class $y_2$ compared to $y_1$. Therefore, the truncated classes typically have higher non-conformity scores, reflecting greater prediction uncertainty. We have revised these explanations in the manuscript for clarity.

4. Explanation of Figure 3 [Q1]

Since RAPS and SAPS are score functions with hyperparameters, these parameters may be less accurately tuned with small calibration sets. As the calibration set size increases, RAPS and SAPS can achieve smaller prediction set sizes due to better hyperparameter estimation. We have added experiments with smaller calibration sets (500 and 800 samples), which demonstrate that RAPS and SAPS produce larger prediction sets under limited calibration data.

We appreciate the reviewer for the insightful and detailed comments. Please find our response below:

1. Statistical Reasoning of PoT-CP [W1]

Our algorithm can be described as a two-stage hypothesis test. For each label $y$,

1. Stage 1: We set the null hypothesis as $H_0: Y_{n+1}=y$. The p-value is defined by $p(y)=\frac{\\{i=1, \ldots, n+1 \mid V_{i} \geq V_{n+1}\\}}{n+1}$. Then, if $p(y)>\alpha$, proceed to Stage2. if $p(y)\leq \alpha$, reject $H_0$.
2. Stage 2: We set null hypothesis as $H_{0,f}: V_f(X_{n+1},y)\leq r^*$, where $r^*$ can be seen as the $1-\beta$ quantile of $V_f$ scores with $\beta << \alpha$. Then, if $V_f(X_{n+1},y)\leq r^*$, we include $y$ in final prediction set $C_T(X_{n+1})$.

Than, the final prediction set: $C_T(X_{n+1})= \{y\in\mathcal{Y}| p(y)>\alpha , V_f(X_{n+1},y)\leq r^* \}$.

2. Fundamental assumptions of CP [W2]

Thank you for highlighting this key point. Our asymptotic analysis provides valuable insights into the truncation behavior and efficiency quantification of PoT-CP. The empirical findings support our theoretical analysis: as shown in Figure 4 and Figure 5 in the revised manuscript, PoT-CP achieves comparable coverage guarantees with a small calibration set. Moreover, our asymptotic results require the i.i.d. assumption, which is standard for both machine learning and conformal prediction theory [1,2]. We acknowledge that extending our theoretical analysis to weaker conditions is an important direction for future work.

3. Discussion about the empty set in our motivation [W3]

Thank you for pointing out the misleading sentence. We agree that relative comparison between the set sizes could present uncertainty in the prediction. However, in the manuscript, we assume that the ground truth label of a test example is known, thus we can judge whether the prediction set contains the ground truth label. If not, we can directly reject the predictive results from the model. Although the oracle setting is unavailable in practice, the trivial idea motivates the design of our approach. We have revised the relevant discussion in the paper to clarify this reasoning better.

4. SSCV for conditional coverage [Q1]

We respectfully disagree that SSCV is not a useful metric. In our theoretical analysis, we prove that PoT-CP asymptotically achieves the same conditional coverage (both object-conditional and class-conditional) as standard CP. SSCV serves a different purpose by measuring coverage consistency across different set sizes. The improved SSCV results for PoT-CP complement, rather than contradict, our theoretical conclusions, suggesting that PoT-CP maintains theoretical guarantees while achieving better practical performance in terms of coverage stability.

5. Explanation of Figure 3[Q2]

Thank you for pointing out the interesting phenomenon. Since RAPS and SAPS are score functions with hyperparameters, these parameters may be less accurately tuned with small calibration sets. As the calibration set size increases, RAPS and SAPS can achieve smaller prediction set sizes due to better hyperparameter estimation. We have added experiments with smaller calibration sets (500 and 800 samples), which demonstrate that RAPS and SAPS produce larger prediction sets under limited calibration data.

6. some typos and reformulation of Theorem 3 [Q3&Q4]

Thank you for the correction and suggestion. We have revised them in the updated version.

References

[1] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2020

[2] Lei, Jing, et al. "Distribution-free predictive inference for regression." Journal of the American Statistical Association 113.523 (2018): 1094-1111.

Thanks for your recognition and valuable comments. Please find our response below:

1. Empirical coverage across calibration set size [W1,Q1]

Thank you for highlighting this missing analysis. The empirical coverage rates across different calibration set sizes on the ImageNet dataset are presented in the following table. The results demonstrate that PoT maintains comparable marginal coverage to the base method. We have included the detailed results in Section 4.2 and Appendix E of the manuscript.

2. Discussion about convergence rates[W2]

We provide an analysis of the convergence rate as follows. To quantify the coverage rate, we use Hoeffding's inequality for bounded independent random variables. Let $Z_{i}$, for $i= 1,2, \ldots, m$ , be independent random variables where $Z_{i}=1$ if $E_{W_i}$ occurs given $E_{V_i}$ on the $i$-th instance, and $Z_{i}=0$ otherwise. The empirical estimate of the conditional probability is $\widehat{\mathbb{P}}\left(E_{W} \mid E_{V}\right)=\frac{1}{m} \sum_{i=1}^{m} Z_{i}$ , which takes values in $[0,1]$. Thus, for any $\epsilon >0$, we can get that $\mathbb{P}(|\mathbb{P}(E_{W}|E_{V}) -\widehat{\mathbb{P}}(E_{W}|E_{V}) | \geq \epsilon) \leq 2\exp{(-2m\epsilon^2)}.$ With $\widehat{\mathbb{P}}(E_{W}|E_{V}) =1$, we have

Let $2\exp{(-2m\epsilon^2)} = \delta$ and $m\approx (1-\alpha)n$. Then, $\epsilon = \sqrt{\frac{\ln{(2/\delta)}}{2n(1-\alpha)}}$. Assuming $\delta$ decrease polynomially with $n$, e.g., $\delta = n^{-k}$ where $k>0$. Thus, the convergence rate becomes: $\epsilon = \mathcal{O} (\sqrt{\frac{\ln{(n)}}{n}}).$