Direct Prediction Set Minimization via Bilevel Conformal Classifier Training

We thank the reviewer for the insightful review. We provide an external PDF (click this link to access) to present the empirical results needed to answer some of your questions.

Q1: No theoretical results on the convergence of bilevel optimization are obtained as the authors pose it as an open challenge.

A1: As we discussed in Section 2 and 4.2, in the current bilevel optimization literature, the convergence guarantee requires some restrictive conditions that do not hold in our problem. E.g., implicit gradient methods require a twice differentiable and strongly convex lower-level function. Iterative differentiation methods require an iterative subroutine for the lower-level problem with more computational cost. Penalty-based methods typically require continuously differentiable upper and lower-level functions, but our lower-level QR loss is nonsmooth.

Although we do not provide a theoretical convergence result for our simple stochastic gradient method, we link it to a most relevant bilevel study by showing that the lower-level QR loss satisfies Hölderian error bound condition (Lemma 4.5), which, to some extent, justifies that using the simple first-order stochastic gradient updates in our algorithm can possibly achieve the $\epsilon$-optimal solution for the original bilevel problem (Corollary 4.6). Finding an affirmative answer to this challenge is part of our future work.

Additionally, we empirically verify convergence behavior in experiments:

Figure 1(a) and 1(b): upper and lower loss.

Figure 1(c): error of the learned quantile in DPSM vs. batch quantile in ConfTr.

Figure 1(d): convergence conformal loss (average soft set size) in DPSM vs. ConfTr.

We further plot the convergence of optimization error to 0 in Fig 1(b) and (c) of external PDF (See also A1 to Reviewer j13f). These empirical results demonstrate the stable convergence of DPSM for the bilevel problem.

Q2: The numerical experiments are not very extensive in terms of datasets.

A2: We would like to highlight that conformal training is expensive in practice, and our experiments are extensive compared with the existing conformal training literature. We will try to add results with more datasets in the final paper.

Why is conformal training expensive?

(i) Requires fine-tuning several hyperparameters (e.g., learning rates, batch size, regularization parameter, $\tau_{{\text{sigmoid}}}$, etc.) and selecting appropriate options (backbone model, conformal scoring function, etc.) from both ML and CP (see Appendix E)

(ii) Typically, requires additional operations such as computing and sorting conformity scores in each iteration, which is more expensive than standard SGD based training of deep models..

Comparing our datasets with previous conformal training literature. We conducted experiments on three widely-used benchmark datasets (CIFAR-100, Caltech-101 and iNaturalist) that span diverse difficulty levels and scales, e.g., 341 classes of data with 224x224 resolution for iNaturalist (see Table 2). In contrast, prior conformal training papers [r1, r2, r3, r4] worked on MNIST, CIFAR-10, or CIFAR-100, which are smaller than ours, e.g., up to 100 classes of data with 32x32 resolution for CIFAR-100.

Q3: The number of trials 10 is a bit few. Visualizations with confidence intervals could be better

A3: Our experiments followed common practice in the CP and conformal training literature [r1, r2, r5, r6], where 10 random splits are widely adopted and considered sufficient to evaluate algorithm performance (in our Table 1).

To study the robustness of DPSM, we show additional experiments with 20 trials on CIFAR-100 using HPS score in the table below.

These results are very similar to those obtained with 10 trials (Table 1), confirming that the improvement of DPSM in predictive efficiency is robust.

Additionally, we plot the visualizations with confidence intervals to further illustrate the stability and robustness of DPSM in Fig 5 in the external PDF. We will include results with more trials in the final paper.

[r1] Sharma, et al. PAC-Bayes generalization certificates for learned inductive conformal prediction. NeurIPS 2023

[r2] Correia, et al. An information theoretic perspective on conformal prediction. NeurIPS 2024

[r3] Einbinder, et al. Training uncertainty-aware classifiers with conformalized deep learning. NeurIPS 2022

[r4] Stutz, et al. "Learning Optimal Conformal Classifiers. ICLR 2022

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

[r6] Huang, et al. Conformal Prediction for Deep Classifier via Label Ranking. ICML 2024

We thank the reviewer for the insightful review. We provide an external PDF (click this link to access) to present the empirical results

Q1: Evaluation: No conditional coverage

A1: Please refer to A2 for Reviewer aEdV and Fig 4 in external PDF for updated conditional coverage measures. DPSM shows improved class-conditional coverage

Q2. Minimizing average prediction set size (APSS): motivation not convincing since:

1) it is a secondary advantage of conformal training. The primary objective is adaptive prediction sets to hardness and conditional coverage across heterogeneous data;

2) it alone does not imply meaningful UQ. Predictions with small APSS may not be adaptive and practically useful, e.g., small prediction sets for easy inputs and empty sets for hard inputs fail to provide informative predictions on difficult ones

A2: 1) Predictive efficiency is one of the primary desiderata in CP, rather than a secondary advantage

For practitioners, smaller prediction sets of CP are found practically useful to improve downstream decision making from humans [r1, r2]. Therefore, recent work in CP explicitly aims to improve predictive efficiency of CP [r3, r4]. Others target training the underlying model to encourage predictive efficiency in CP [r5, r6]. Therefore, it is a central and practically important goal. DPSM contributes to this line of work by providing provable improvements in predictive efficiency that is verified by experiments, e.g., 20% reduction of APSS over the best baseline

Clarification: DPSM can also be used for conditional coverage. The idea of DPSM is to learn the quantile, rather than estimating it in batches. It is agnostic to the considered coverage type and thus highly compatible with different conditional coverages. For class-conditional coverage, we can use the same principle to learn the quantile for each class and regularize fair distributions of conformity scores over heterogeneous classes

2) Small prediction sets for easy inputs and empty sets for difficult ones are informative and practically useful

Under nominal coverage, a small prediction set (e.g., singleton) implies high confidence of the model. On the other hand, an empty prediction set indicates selective rejection, which attracts increasing focus in large language models, e.g., abstention over unreliable prediction (e.g., hallucination) on difficult inputs [r7, r8]. In addition, conformity score is a more fine-grained adaptive measure

Q3: $1/n \sum^n_{i=1}[\sum_{y \in \mathcal Y} \tilde 1 [S_f(X_i, y) \leq q]]$ is repeatedly defined in Eq (9) and (5)

A3: This was intentional because it is a shared part to define SA and DPSM conformal losses in Eq (5) and (9), respectively (as stated in L247 below Eq (9)). This highlights the key difference between the two conformal losses: the input quantile of SA conformal loss is from a random batch, while DPSM uses a learnable quantile as input in Eq (9). Their definitions are used in their corresponding learning bound results

Q4: Why is $\hat \ell (f,q)$ defined over all training samples rather than batch?

A4: We aim to compare learning bounds for SA and DPSM conformal losses, so we ensure their learning error is defined over the entire training set, rather than a random batch. Although we compute the batch-level quantile for SA method in practice, to make the comparison agnostic to the randomness of batches, we derive an in-effect conformal loss over all training data (Prop 3.4) used for learning bounds (Thm 3.5)

Q5: Why is QR loss defined over all data in Eq (8), but Algo 1 computes batch gradient? Any benefit for this further data split?

A5: An optimal solution of QR loss over all samples is the ($1-\alpha$)-quantile over all data. In Algo 1, we use stochastic gradients to iteratively update the learnable quantile until QR loss converges. It is analogous to applying SGD to optimize a loss defined over all training samples: iterative SGD update can train the deep model to convergence

We clarify that $D_1$ is employed to train classification loss and QR loss, rather than conformal loss. Data split helps prevent overfitting and has been in the conformal training literature (see [r9]).

[r1] Conformal Prediction Sets Improve Human Decision Making. ICML 2024

[r2] On the Utility of Prediction Sets in Human-AI Teams. IJCAI 2022

[r3] Uncertainty sets for image classifiers using conformal prediction. ICLR 2021

[r4] Conformal Prediction for Deep Classifier via Label Ranking. ICML 2024

[r5] The Pitfalls and Promise of Conformal Inference Under Adversarial Attacks. ICML 2024

[r6] Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training. AAAI 2025

[r7] Large language model validity via enhanced conformal prediction methods. NeurIPS 2024

[r8] Conformal language modeling. ICLR 2024

[r9] Training uncertainty-aware classifiers with conformalized deep learning. NeurIPS 2022

We thank the reviewer for the insightful review. We provide an external PDF (click this link to access) to present the empirical results needed to answer some of your questions.

Q1: Learning bound not empirically tested? Questionable if achievable due to optimization approximation?

A1. Learning bound in Thm 4.1 cannot be empirically computed (conformal loss ${\mathcal L}_c$ is defined over population, as per the standard generalization error [r1]). However, we can verify it via a strategy in ML literature that approximates the generalization error by the absolute gap between the train and test error [r2, r3]. For our CP case, we use the average prediction set size (APSS) evaluated on train and test sets to approximate our learning bound. Specifically, at iteration t, we:

1. compute APSS on train set using $f_t$ and $q_t$ (as the threshold for CP), denoted by $APSS^{tr}(f_t, q_t)$. It includes opt. error since $q_t$ is not optimal (true quantile on train set);

2. compute $APSS^{te}(f_t,q^{te}(f_t))$ on testing data, where $q^{te}(f_t)$ is the true quantile

Then we compute $|APSS^{tr}(f_t, q_t)-APSS^{te}(f_t, q^{te}(f_t))|$ as an approximation of the learning bound. We follow the same strategy to approximate the learning bound for the SA-based ConfTr, where we use the batch-level quantiles from batches randomly sampled from train set for train APSS, and from testing data for test APSS, respectively. We include this comparison in Fig 1 (a) in the external PDF to verify that the approximated learning error is improved (and converges to 0) by DPSM despite optimization approximation.

Opt. approximation: We showed the convergence of losses and est. error of learned quantile empirically in Fig 1(a)-(c) of original paper. To investigate how the learned $q_t$ impacts the opt. error on conformal and QR losses, we compute these two losses with the learned $q_t$ and optimal $q^{tr}(f_t)$. On train set, we further show the gap between the conformal loss (and QR loss resp.) with $q_t$ vs. $q^{tr}(f_t)$ (we denote as opt. error) in Fig 1 (b) and (c) of external PDF. Both opt. error converges to nearly 0

Q2: Why can DPSM achieve much better learning bound as SA is also adopted?

A2: DPSM mainly differs from the SA-based method in how the quantile is instantiated

DPSM: the quantile is a learnable parameter in lower-level QR

SA-based: uses batch-level quantile at each iteration

Although they share the same SA-type update (SGD), the bottleneck of SA-based method is the large deviation of the batch-level quantile w.r.t the true quantile (at least $\Omega(1/s)$, Thm 3.5). Instead, DPSM decouples the quantile estimation from stochastic batches via learning a quantile parameter. By releasing the bottleneck of estimating batch-level quantiles, it allows a much smaller learning bound (at most $O(1/\sqrt{n​})$, Thm 4.1) when DPSM learns the optimal quantile. We further show that DPSM learns a very accurate quantile (the gap w.r.t true quantile converges to 0 as in Fig 1(c) of original paper). Thus, it secures the improved learning bound

Q3: The proof for Thm 3.5 relies on some properties of beta distribution which are only available in the asymptotic sense according to Prop 3.4.

A3: Thank you for pointing this out. We will revise Thm 3.5 to explicitly include the assumption used by Prop 3.4. For the asymptotic result, following some standard analysis techniques in ML literature, e.g., [r4, r5, r2], we use it to formally construct the in-effect conformal loss over $n$ training data characterized by Beta distribution. Based on it, we derived the learning bounds for the SA-based method that are compared with DPSM in Section 4.

Q4: The algorithm did not sufficiently converge with 40 epochs.

A4: Thank you for your suggestion. We have extended training epochs to 100 to show the sufficient convergence of upper and lower loss in Figure 2 of external PDF.

Q5: Verify assumption with other conformity scores.

A5: We originally selected HPS score to verify assumptions following the recent conformal training literature [r6].

We add the verification experiments with APS and RAPS scores in Figure 3 of external PDF, where Assumption 3.1 and 3.2 are still empirically valid. We will report the results in the revised paper.

[r1] Mohri, et al. Foundations of machine learning. MIT press 2018

[r2] Yang, et al. Exact gap between generalization error and uniform convergence in random feature models. ICML 2021

[r3] Yuan, et al. Stagewise Training Accelerates Convergence of Testing Error Over SGD. NeurIPS 2019

[r4] Emami, et al. Generalization error of generalized linear models in high dimensions. International conference on machine learning. ICML 2020

[r5] Velikanov, et al. Generalization error of spectral algorithms. ICLR 2024

[r6] Sharma, et al. PAC-Bayes generalization certificates for learned inductive conformal prediction. NeurIPS 2023

We thank the reviewer for the insightful review. We provide an external PDF (click this link to access) to present the empirical results needed to answer some of your questions.

Q1: Assessing the score function with fixed hyper-parameter settings provides little insight.

A1: In our original experiments, we use the score functions (HPS, APS, and RAPS) and set their hyper-parameters following the established practice in recent CP and conformal training papers [r1, r2, r3, r4]. Specifically, only RAPS involves explicit hyperparameters, i.e., $\lambda$ and $k_{reg}$, and we used standard fixed hyperparameter settings commonly adopted in the CP literature, e.g., [r1, r2, r3]. HPS and APS do not have hyperparameters.

To investigate the impact of the hyperparameters of RAPS over DPSM, we additionally evaluated the average prediction set size based on all conformal training methods with different values for the two hyperparameters in RAPS, where the values follow the original setting in the RAPS paper [r5]. We selected the best combination with the smallest prediction set size for each conformal training method and reported their average prediction set sizes as follows.

These results are the same as those obtained originally with the fixed RAPS hyperparameters (Table 6 of original paper). We will include the additional results with the tuned RAPS score in the revised paper.

Q2: Including conditional coverage metrics such as WSC, SSCV, or CovGap is essential.

A2: To investigate the impact of DPSM’s set size reduction over the conditional coverage, we report a table of WSC ($\uparrow$ better), SSCV ($\downarrow$ better) and CovGap ($\downarrow$ better) of all conformal training methods on CIFAR-100 with HPS score and DenseNet backbone below:

These results show that DPSM achieves the best performance for class-conditional coverage (the smallest CovGap, with 2.4% $\downarrow$ over the best baseline CE). For size-stratified coverage (SSCV), DPSM has a worse measure compared with CE and CUT, but is better than ConfTr. For WSC, CUT and DPSM have comparable performance.

Visualized class-conditional coverage and prediction set size

We further plot Fig 4 in the external PDF to show the distribution of class-conditional coverage and class-wise average prediction set size as fine-grained measures for class conditional coverage. DPSM shows a bit more concentration in terms of class-wise coverage and smaller class-wise prediction set size. This result is supported by the above table, where CovGap is a measure for the violation of class-conditional coverage and DPSM has 2.4% $\downarrow$ over the best baseline (CE) as per the above table.

Q3: The authors should report model accuracy across different loss functions.

A3: We agree that explicitly reporting model accuracy across different training loss functions would provide a more comprehensive understanding of the benefits in DPSM. Below, we report the testing accuracy on CIFAR-100 of all methods in the following table:

These results show that while DPSM achieves slightly lower accuracy than CE, it maintains comparable accuracy to CUT and significantly outperforms ConfTr. Combined with the best performance of DPSM in terms of average prediction set size reported in Table 1 of original paper, DPSM demonstrates an effective balance between model accuracy and predictive efficiency of CP. We will include these accuracy results in the revised paper.

[r1] Ding, et al. Class-conditional conformal prediction with many classes. NeurIPS 2023

[r2] Tawachi, et al. Multi-dimensional conformal prediction. ICLR 2025

[r3] Correia, et al. An information theoretic perspective on conformal prediction. NeurIPS 2024.

[r4] Lu, et al. Federated conformal predictors for distributed uncertainty quantification. ICML 2023.

[r5] Angelopoulos, et al. Uncertainty Sets for Image Classifiers using Conformal Prediction. ICLR 2021