Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Authors: Yuanjie Shi
Hooman Shahrokhi
Xuesong Jia
Xiongzhi Chen
Jana Doppa
Yan Yan
Venue: ICML 2025 poster (2025)
Keywords: conformal prediction
uncertainty quantification
deep classifiers
conformal training
Primary area: general_machine_learning
TL;DR: We propose the Direct Prediction Set Minimization (DPSM) approach by integrating the principle behind the standard quantile regression with a differentiable measure of the prediction set size that is conditioned on the learned quantile.

Abstract: Conformal prediction (CP) is a promising uncertainty quantification framework which works as a wrapper around a black-box classifier to construct prediction sets (i.e., subset of candidate classes) with provable guarantees. 
However, standard calibration methods for CP tend to produce large prediction sets which makes them less useful in practice. 
This paper considers the problem of integrating conformal principles into the training process of deep classifiers to directly minimize the size of prediction sets. 
We formulate conformal training as a bilevel optimization problem and propose the {\em Direct Prediction Set Minimization (DPSM)} algorithm to solve it. 
The key insight behind DPSM is to minimize a measure of the prediction set size (upper level) that is conditioned on the learned quantile of conformity scores (lower level). 
We analyze that DPSM has a learning bound of $O(1/\sqrt{n})$ (with $n$ training samples),
while prior conformal training methods based on stochastic approximation for the quantile has a bound of $\Omega(1/s)$ (with batch size $s$ and typically $s \ll \sqrt{n}$).
Experiments on various benchmark datasets and deep models show that DPSM significantly outperforms the best prior conformal training baseline with $20.46\\%\downarrow$ in the prediction set size and validates our theory.

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Yuanjie Shi
Hooman Shahrokhi 1
Xuesong Jia"
Xiongzhi Chen 2 Janardhan Rao Doppa' Yan Yan
Abstract
2016). However, safely deploy deep machine learning (ML) classifiers in high-stakes applications (c.g., medical diagnosis (Begoli et al., 2019; Yang & Fevens, 2021)) and to build efficient human-ML. collaborative systems (e.g., a classifier produces a small set of decisions and a human selects from them (Cresswell et al., 2024; Straitouri et al., 2023; Babbar et al., 2022)), we need reliable uncertainty quantification (UQ) (Abdar al., 2021). UQ could take the form of prediction set (a subset of classes) for classifica- tion tasks. For example, in medical diagnosis (Begoli et al., 2019; Yang & Fevens, 2021), such prediction sets allow a doctor to rule out harmful diagnoses such as stomach cancer, even if the most likely diagnosis is a stomach ulcer.
Conformal prediction (CP) is promising uncer- tainty quantification framework which works as a wrapper around a black-box classifier to construct prediction sets (i.c., subset of candidate classes) with provable guarantees. However, standard cal- ibration methods for CP tend to produce large prediction sets which makes them less useful in practice. This paper considers the problem of in- tegrating conformal principles into the training process of deep classifiers to directly minimize the size of prediction sets. We formulate confor- mal training as a bilevel optimization problem and propose the Direct Prediction Set Minimiza- tion (DPSM) algorithm to solve it. The key in- sight behind DPSM is to minimize measure of the prediction set size (upper level) that is con- ditioned on the learned quantile of conformity scores (lower level). We analyze that DPSM has a learning bound of (n) (with n training samples), while prior conformal training meth- ods based on stochastic approximation for the quantile has bound of (11/s) (with batch size s and typically < vn). Experiments various benchmark datasets and deep models show that DPSM significantly outperforms the best prior conformal training baseline with 20.46% I in the prediction set size and validates our theory.
Conformal prediction (CP) is general framework that pro- vides finite-sample guarantees of valid prediction sets to include the correct output, which are agnostic the ML model and data distribution (Vovk et al., 2005; Angelopou- los & Bates, 2021). As a result, CP is increasingly used for UQ in real-world problems (Cresswell et al., 2024; Lu et al., 2022b;a). The general principle behind CP is to con- vert the output of an ML. model on a given input example (e.g., softmax scores of a deep classifier) into a prediction set (Romano al., 2020) that contains the true label with user- specified probability (e.g., 90% probability) referred to as coverage via calibration step. One of the main limitations of standard CP is that it tends to produce large prediction sets, which may not be useful in practice (Vovk et al., 2016; Babbar et al., 2022; Straitouri et al., 2023). Recent prior work focused on how to improve the predictive efficiency of CP (Fisch al., 2021 aa;;; Angelopoulos al., 2021; Huang et al., 2023a; Ding et al., 2024; Shi et al., 2024). However, their focus is on the calibration step only by considering the underlying ML model as a black-box.
1. Introduction
Deep neural networks have achieved high prediction accu- racy and enabled numerous applications in diverse domains including computer vision (He et al., 2016; 2017) and natu- ral language processing (Vaswani et al., 2017; Kumar al.,
Recent work has considered integrating CP into classi- fier training to trade-off between prediction accuracy and conformal alignment (c.g., minimizing the size of predic- tion sets) in end-to-end fashion (Stutz al., 2021; Ein- binder et al., 2022; Yan et al., 2024). For instance, ConfTr (Stutz et al., 2021) incorporates a stochastic approximation (SA) of the average prediction set size into the training objective function based on empirical quantiles over mini- batches. To achieve accurate conditional coverage, con- formal uncertainty- training (CUT) (Einbinder et al., 2022) employs similar SA approach to acquire the empiri-
Equul contribution 'School of Electrical Engineering and Computer Science, Washington State University, Pullman, Wash- ington, USA DDeparmentt of Mathematics and Statistics, Wash- ington State University, Pullman, Washington, USA. Correspon- dence to: Yan Yan <yan.yanl @ wwsu.edu>, Janardhan Rao Doppa <jana.doppa@ @ wsu.edu>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
cal quantiles of non-conformity scores on mini-batches and penalizes their deviation from the uniformity. However, primary challenge for these SA-based conformal training methods is the large error between the empirical batch-level quantiles and the true quantiles, resulting in a learning bound of up to ((1/ /5) with batch size s (Einbinder et al., 2022). This bound is significantly larger than the standard learning bound of ( /n) with n training samples in empirical risk minimization (ERM) (Mohri et al., 2018; Shalev-Shwarte & Ben-David, 2014). Consequently, it notably degenerates the overall trade-off between the prediction accuracy and conformal alignment of the trained classifier. This motivates the main question of this paper. can we develop a confor- mal classifier training method to calibrate the conformal uncertainty with a standard (L//vT) learning bound?
The DPSM code is available at https: pettps://githbb /githbb.
com/Yuan wawaanjjeS/DDPP_CCCM code.
2. Related Work
Conformal Prediction has been extensively studied (An- gelopoulos & Bates, 2021) recently. Key contributions in- clude laying the foundational principles in CP (Vovk et al., 2005; 1999; Shafer & Vovk, 2008). There is some focus eross- vooss-valiitiion methods (Vovk, 2015) and the jack- knife+ approach (Barber et al., 2021), but split CP is the most common (pproach(Vovk et al., 2005; Romano et al., 2020; Oliveira et al., 2024), where calibration of a given pre-trained model is performed on a held-out dataset. CP is applied in many tasks including classification (Romano et al., 2020; Angelopoulos et al., 2021; Cauchois al., 2021). regression (Romano et al., 2019; Gibbs et al., 2023; Gibbs & Candes, 2021; Sesia & Romano, 2021), computer vision (Angelopoulos et al., 2024; 2022; Bates et al., 2021), adversarial attacks (Liu et al., 2024; Ghosh et al., 2023b), online learning (Angelopoulos et al., 2023; Bhatnagar et al., 2023), and generative tasks (Shahrokhi al., 2025). Valid coverage and predictive efficiency are two critical and often competing evaluation measures in CP (Angelopoulos et al., 2021). Recent CP advances include the development of new conformity scores (Angelopoulos et al., 2021; Huang et al., 2023a) and calibration procedures (Fisch et al., 20;;;;a; Guan, 2023; Ghosh et al., 2023a; Ding et al., 2024; Kiyani et al., 2024b; Shi et al., 2024; Zhu et al., 2025) to improve predictive efficiency with valid coverage. These methods follow the general CP workflow by relying on pre-trained models. Consequently, their predictive efficiency critically depends on the underlying ML model. However, since the ML models are not specifically trained for conformal align- ment, CP may produce large prediction sets (Bellotti, 2021).
This paper gives affirmative answer by developing novel conformal classifier training algorithm referred to as Direct Prediction Set Minimization (DPSM). The key idea behind DPSM is to formulate conformal training as a bilevel optimization problem (Ghadimi & Wang, 2018: Zhang et al., 2024) that estimates the empirical quantile of non-conformity scores by learning a quantile regression (QR) in the lower-level subproblem. Conditioned on this learned quantile, the upper-level subproblem measures and minimizes the prediction set size of CP. This bilevel formu- lation implicitly defines a conformal alignment objective and we analyze that minimizing the resulting function leads to learning bound of O(1/ Vn). In contrast, we show that the learning bound of the prior SA-based conformal training methods is lower bounded by (2(1s)) with batch size s (typi- cally= < vT). Moreover, to optimize the DPSM objective, we develop a simple and practical stochastic first-order algo- rithm. Our experiments on diverse real-world datasets with different conformity scores and deep models demonstrate that DPSM achieves significant reduction (L 20.46%) in prediction set sizes compared the best baseline.
Conformal Training aims at integrating CP into the clas- sifier training process to promote conformal alignment. A typical approach is to introduce regularization function that integrates conformity property into the training pro- cesslBellott,, 2021; Stutz et al., 2021; Einbinder et al., 2022; Yan et al., 2024). For example, ConfTr (Stutz et al., 2021) integrates CP into the training of deep classifiers through a differentiable approximation for the average prediction set size, allowing for smaller and valid prediction sets using the CP-aware classifier. Conformalized uncertainty-aware training (CUT) (Einbinder et al., 2022) combines the con- formity scores with uncertainty- accurate conditional coverage. It penalizes the deviation of the conformity scores from the uniformity during the training process. However, both ConfTr and CUT employ a stochastic quantile of non-conformity scores from a mini- batch of 8 samples, resulting in a large (L/vV)) error with respect to the true quantile depending on the batch size
Contributions. The key contributions of this paper include:
We develop a new conformal training algorithm DPSM as a bilevel formulation, which directly minimizes the prediction set size (upper level) conditioned on the learned quantile of the conformity scores (lower level).
We analyze the learning bound of DPSM and find that it is bounded above by 0(1/ vn), which significantly improves over the existing conformal training methods whose lower bound is at least ((1/s).
loss function for
We develop a simple stochastic first-order algorithm to optimize the DPSM training objective.
Experiments on multiple benchmark datasets to demon- strate significant improvements of DPSM over the best prior conformal training baseline (20.46% 4 predic- tion set size) and to validate our theoretical results.
2

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Bilevel Optimization has been extensively studied due to its critical role in many MI use-cases (Liu al., 2021), including reinforcement learning (Cheng et al., 2022; Zhou, 2024: Shen et al.), federated learning (Huang et al., 2023b; Yang et al., 2023), and continual learning (Borsos et al., 2020; Zhou et al., 2022; Hao et al., 2024; Borsos et al., 2024). Bilevel optimization methods can be roughly catego- rized into three groups: (i) implicit gradient methods (Chen et al., 2021; Ji et al., 2021; Dagréou al., 2022; Ghadimi & Wang, 2018; Pedregosa, 2016; Domke, 2012), (ii) itera- tive differentiation methods (Bolte et al., 2022; 2021), and (iii) penald methods (Lu & Mei, 2024; Chen et al., 2024b;a; Shen & Chen, 2023; 2025). Compared to penalty- based methods, implicit gradient methods typically require more restrictive assumptions, such as twice differentiable and strongly-convex lower-level function (Shen & Chen, 2025). On the other hand, iterative differentiation methods typically require an iterative subroutine for the lower-level problem with more computational cost (Shen & Chen, 2025). Instead, genalty-based methods build a single level problem and only use first-order information (Shen & Chen, 2023). To summarize, bilevel optimization algorithms either require restrictive assumptions or have complex update steps. It is non- con-trivial to find a practical algorithm that is particularly tailored for our proposed conformal training problem.
scoring function. Let S X y - R denote a non- conformity scoring function to measure the difference be- tween a new data and existing ones (Vovk et al., 2005). For simplicity of notation, we denote the non- confoorfrrm score of the i-th example as S = ( s, Y:) for (X,, Vi) E Drr and of the j-th smallest value in { as S(z). Many non- conformity scoring functions are proposed in prior work (Huang et al., 2023a; Angelopoulos et al., 2021; Shafer & Vovk, 2008). In this paper, we consider Homogeneous Prediction Sets (HPS) (Sadinle et al., 2019), Adaptive Pre- diction Sets (APS) (Romano et al., 2020), and Regular- ized Adaptive Prediction Sets (RAPS) (Angelopoulos et al., 2021) (details are in Appendix A). We assume that there is no tie in non-conformity scores (Romano et al., 2020).
Given the mis-coverage parameter a and an underlying model f. on a testing data (Xusa, Yus)). CP aims to achieve coverage of the true label with a prediction set C₁ X + 2 with probability at least 1 - a, i.e.,
2 a. Yox (Yeu e E (cu(
(I)
CP typically constructs Cy (Xxss) via the empirical quantile @s(() on the calibration set Dent:
Cx(Xies) = tu y:: S v) S ar(a)),
(2)
Our goal is to develop a bilevel conformal training algo- rithm with (i) a standard O(1/ learning bound for n (s)/vs) Vs) for batch size s from prior conformal training methods, and (ii) a practical stochastic first-order bilevel optimization algorithm.
where (a) is computed as the [1+=)) th smallest value in { and is an estimation to the population quantile (a) = min IP (Syv(S Y) S 2 1 1-a). Throughout this paper, unless otherwise specified, we omit the target mis-coverage a for notation simplicity, e.g.. Qy-
training samples to improve over O(1/
Quantile-based Conformal Training. The goal is to align the classification model f with favorable conformal prin- ciples (Bellotti, 2021). A general framework (Stutz et al., 2021; Einbinder et al., 2022) is to establish the trade-off between prediction accuracy and conformal alignment on the training set Drr with an objective structured as follows:
3. Background and Motivation
Notations. Suppose X E X' is an input from X, and Y E y = (1, ... K} is the ground-truth label, where K is the number of candidate classes. Let (X, Y) be a data sample drawn from an underlying distribution P detined on X x V. Let f(X): X + AK denote the confidence prediction by soft classifier ʃ E F (e.g.. Softmax scores), where A is the (k-1)-dimensione probability simplex, f(X), is the confidence score of class y and F denotes a hypothesis class. Define Dr = {(,,, ) as the train- ing set of n samples for training classifier f. We denote Deal and Dues as two separate calibration and testing datasets, respectively. We assume that there are m calibration sam- ples. i..., |Deall m. Define 1|-] as an indicator function. Denote B- = {(x,, e. Yili E } as randomly sampled batch of training data of size 8, such that the batch index set I. C. (1. ... with [I| = s. Given a function h(x, y). we denote /, 3) as the directional derivative of h in x and Vzh((,, y) as its stochastic estimation.
min, Lass (f) + A Lo(f),
where Lfts()) is the classification loss (c.g., cross entropy), Ce(f) is the conformal alignment loss based on the quantile Q5. and X is the regularization hyper-parameter. Follow- ing (Stutz et al., 2021), this paper focuses on a concrete definition of Lo(f) as the expected differentiable size of prediction sets:
Ce(f) = e(f, such that
(4)
e(f.g) A Ex
Σ vEY
i i[s) v)
differentiable
Ex [[C)(X)]]
Conformal Prediction. As mentioned above, CP calibrates predictions from given model based on a non-confommity
where î[[] is a smoothed estimator for the indicator function 1[-] and defined by a Sigmoid function (Stutz et al., 2021),
3

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
i.e., ils S g) 1/(1 + exp(-(1 53 Tiggmiaa)))) with tunable temperature parameter TSggmoid- Here, we denote ((f, q) as a general conformal loss function that takes any f and g as inputs, and Lc(f) requires the true quantile Qj as the input to l.
Proposition 3.4. (Distribution of mini-batch quantiles) De-
fine an event Z(j) as "the j-th smallest score Sig) from {S:) is randomly selected as @ (a) on a mini-batch B". Then the probability of Z(i) is:
P(ZG)) = ((u-ole+u)) la- nーjーi
However, it is challenging to accurately compute C. Qf) when training f. as Q is an implicit function of f. On one hand, updating f iteratively also changes , accordingly. On the other hand, after getting an updated f. re-computing an empirical quantile 2 on training data Dr requires sort- ing all n non-conformity scores of training data, with a computational complexity of (m (o))))))))
Furthermore, we have the following asymptotic result
lim P(Z()) = -P PPeea (2:((1 - a) + 1)] + 1; n=0000
s s- + 1)1)
To address the above- mentinne challenge, prior conformal training methods (Stutz et al., 2021; Einbinder et al., 2022) employ a stochastic approximation (SA) method esti- mate (f( in batches. Specifically, at each iteration during training, they use the empirical batch-level quantile from a mini-batch B sampled from Dr. denoted by qy. as the input to f, i.e., {(f. .r). Since q depends on the randomly sampled batches, we regard T as a random variable drawn from its underlying distribution 2,. i.e., Tf ~ 22 (we defer our analysis for 2 to Proposition 3.4 stated below). Then the in-effect SA-based conformal loss (SA(F) (f) is given by
where P Beeia b) is the PDF of Beta distribution with two shape parameters o, b and is the Euler's 's number.
With the above proposition that captures the random sam- pling process of the quantile ōy in each mini-batch, we are ready to present the following main result analyzing the learning bound of the SA-based conformal training method.
Theorem 3.5. (Learning bounds of SA method) Suppose that Assumption 3.1 and 3.2 hold. Assume (1-a)(s aa)(s 1) is not integer. If [(1 a=)( + 1)] (1 a))
(11/s) and s S Vn, then the following inequality holds with probability at least 1 - 8:
(f) = =E 1, R.),, such that
(5)
?(.0g) A Σ Σ i[s,(X..)) S s
2118s) S () L.(N S 001/8).
vEY
Remark 3.6. Throughout this paper, we use Ô to suppress the log dependency. The above result shows the upper bound ((1//²) and lower bound 12(1/s) of learning error of the SA-based conformal training method. It is worth noting that even the lower bound 12(1/s) can be significantly larger than the standard result O(1/Vn) as in empirical risk minimiza- tion (Mohri et al., 2018) under a common setting s S vn for training deep models (Masters & Luschi, 2018).
where Z(f.g) q) an empirical version of E(f, q) on Du--
A key limitation of the SA method is the large error gap between the true and in-effect conformal alignment loss functions, i.e., (f) Lo(f). Prior work (Einbinder et al., 2022) showed that the error of SA-based conformal alignment loss is upper bounded by 0(1/v5) with batch size s. We further analyze the learning error for the SA- based conformal alignment loss in this paper, including its lower bound. We start with the following assumptions.
4. Direct Prediction Set Minimization Method
Assumption 3.1. (Bi-Lipschitz continuity of score S(n) Siy) is bi-Lipschitz continuous for normalized order j/n
In this section, we first propose Direct Prediction Set Minimization (DPSM) algorithm by formulating it as a bilevel optimization problem. Next, we show that the learn- ing bound of DPSM is most ((I/vn) (Theorem 4.1), which improves over the SA-based conformal training meth- ods (1)1/s), Theorem 3.5). Finally, we develop a simple and practical optimization algorithm to solve it.
such that Ta 1/4 j - (Su.) - S(a) < T.2 d1 l2 for
L1, L2 >0 O.
Assumption 3.2. (u-strongly concavity of ({.g)) ef 9) is jusstronly concave locally around [[yy] for fixed f.
Remark 3.3. We conduct experiments to empirically verify the Assumptions 3.1 and 3.2 (See Fig 4). These assumptions allow us to analyze how the SA-based conformal training method approaches the true conformal alignment loss.
4.1. Bilevel Problem Formulation and Learning Bound
The key idea to directly minimize the prediction sets is inspired by quantile regression (QR), a well-studied method to learn the quantile of a set of random variables. A common approach to training QR is to minimize an average pinball loss on a set of data (Narayan et al., 2024; Gibbs et al.,
The following proposition reveals the specification of the distribution 2, aforementioned in ČSA (5) that considers T as random variable drawn from the training dataset Drr-
4

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
2023; Koenker, 2005; Koenker & Bassett Jr, 1978). For the - -u-unnntill, the pinball loss is defined as follows.
during training rather than the immediate dependency as in the SA-based conformal training, i.e., Of 2j. Specif- ically, QR in the lower-level subproblem, due to its well- known property, enables the iterative updates for until attaining the (1 q)-quantile of non-conformity scores as training f. If an optimization algorithm ensures the simulta- neous convergence of both variables in Problem (8) to their optimal solution sets (discussed in Section 4.2), i.c.
Palg, { (1 (1- a)S 4), i 15S20 4, a(q- S), S),
(6)
otherwise,
where S and g represent real value and quantile prediction, respectively. Minimizing the average pinball loss on a set of data {Si (i) gives the (1 - a---aantqluneeeee of n scores {S /=
q q-u(f) f arg Los( + (f),
G" E arg ming
1 n
Σ
n
Palg,
then we can achieve an improved learning bound for the conformal alignment loss [CPM (f) (ff) that is indepen- dent from batch size This is the reason why we named (7)
Conformal Training via Bilevel Optimization. Instead of using stochastic quantile each batch of data, we propose to incorporate QR into the conformal training objective constraint. Conditioned on solving this QR-based constraint and acquiring the accurate quantile, we directly minimize the average size of prediction sets. Specifically, we for- mulate the following bilevel optimization problem for our DPSM method for conformal training:
our method as direct prediction set minimization (DPSM),
Improved Learning Bound of DPSM. As in Theorem 3.5, we show that the learning error of SA-based method (f) - Ce(f)) is upper bounded by O(1/ /3) and lower bounded by 12(1/s), respectively. We then show that the learning eπrоr of DPSM CF)( [f)l can be bounded above by O(1/vn) in the following result.
Theorem 4.1. (Learning bound of DPSM) Suppose As- sumption 3.1 holds. For any classifier model f E F, with probability at least 1 1 8, we have:
minsa Ea((S) + A- 2DM (J.9)
s,t. q E Uf) & arg ming (f.g'),
where _OR (f. = # (g, Sq (X,, Yi)) in the lower level is the average pinball loss for the non-conformity scores on n training samples, and the conformal alignment loss (DM q) is given by
(P) Ō(1/VR).
Remark 4.2. The above theorem directly answers the central question that we asked in the introduction, i.e., bilevel con- formal training calibrates the conformal uncertainty with a standard O(L/VR) learning bound as in ERM (Mohri et al., 2018; Shalev-Shwartz & Ben-David, 2014). In comparison with the learning error bounds of the SA-based conformal training method derived in Theorem 3.5, the DPSM bound improves by dropping the dependency on the batch size s.
CDM (J.)) = Σ
Σ BEY
iXs, v) s sf
(9)
which follows the definition of DEA (f) in (5) except that it allows any variable as the input quantile, instead of a stochastic quantile ワy ~ 2,. To analyze DPSM, following the bilevel optimization literature (Chen al., 2024a; Shen & Chen, 2023), we define the implicit conformal loss:
The improved learning bound of DPSM over SA-based methods is mainly due to smaller error in estimating the true quantile, i.e., 14 1 Indeed, results shown in Fig 7 (c) and (d) empirically demonstrates this hypothesis. The practical significance of this result is that the smaller estimation error of DPSM results in improved conformal alignment of the classifier leading to smaller prediction set sizes.
(f) e mingeu(s) 2DM (0M((. (f.q).
The key innovation in the proposed bilevel conformal train- ing problem (8) compared with the SA-based method is to explicitly parameterize the quantile with single score variable q. This approach has been used in the CP literature (Gibbs et al., 2023; Gibbs & Candès, 2024; Kiyani et al., 2024a; Deshpande et al., 2024; Podkopaev et al., 2024), and we employ it for conformal training in our bilevel formu- lation for the first time. Conditioned on q. regardless of how accurate q is during training relative to the true Q,, the conformal alignment loss 2DM (f, g) participates in training.
4.2. Stochastic Optimization for DPSM
Challenges for DPSM. There is a large literature on meth- ods for bilevel optimization (Liu et al., 2021; Beck et al., 2023). However, existing methods typically require restric- tive assumptions to guarantee convergence. Some exam- ples of such assumptions include requiring Lipsethiz Hes- sians (Chen et al., 2024a; 2021; Dagréou et al., 2022; Yang et al., 202 twice continuously differentiable (Kwon et al., 2024); requiring solving a subproblem (Liu et al., 2020); strongly convex lower-level subproblem (Gong et al., 2024b;
The major benefit of the quantile parameterization idea is that it decouples the quantile q from the stochastic batches
5

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Algorithm 1 Direct Prediction Set Minimization (DPSM)
Definition 4.3. (Hölderian error bound) A function h(r)), where its domain dom(h) is closed convex set, satisfies Hölderian error bound if there exists 2 and > 0 s.t.
1: Input: Training dataset Du. regularization parameter X, learning-rate -ratenggrrregeeeee 77 > O, mis-coverage level a
2: Randomly initialize the deep neural network fo and quantile regression model parameter Qo R
dist(r, x² S c(h(x) mi(=))x-((z'),,, Vx E dom(h),
3: Randomly split Dr into two disjoint subsets Dj and D2 with the same size such that [Dil = [Pal = 2
where X = arg ( ((z) is the optimal solution set for minimizing k(z) and dist(2; X*) = min ||2 x'll denotes the Euclidean distance between 2' and X
4: for 4 0: T -1 do
5: Randomly sample two batches Bi C Di, C D2
Remark 4.4, Hölderian error bound (HEB) is a well-studied condition in optimization (Pang, 1997: Bolte et al., 2017). It captures the local sharpness of the objective function that helps accelerate the optimization convergence (Roulet & d' Aspremont, 2017; Yang & Lin, 2018). The following result shows that 2DM (f, q) satisfies HEB w.I.t. q.
6: Compute V, < (o((((e-1) on batch B!
7: Compute DOR t V.CoR (fi-1: q(-1) batch Bi
8: Compute DM + 8, (f-M(f(.. on batch B3
9: f411 + ft - n f.t + f.t)
(.
PP)M)
10: at+1 4- - > DOR g.t
11:
end for
Lemma 4.5. (HEB for QR loss) Suppose there is no tie in conformity scores { Then for a fixed f. L (f / q) sattisiess HEB w.E.. for the exponent v = 1 and c > 0.
12:
Output: the trained classification model Jr
Corollary 4.6. (Global solution of penalized problem) Sup- pose Le and (f q) is Lete and Lou-Lipschitz continuous, respectively. For any given >> 0, let I = (Lets + LOM) and a = cl in (10). Then the e-optimal solu- fion of the penalized problem is an (e, e/ o/p)ooptimal solution of the original problem.
Kwon et al., 2023; Ji et al., 2021; Gong et al., 2024a; Chen et al., 2024c; Hong et al., 2023; Khanduri et al., 2021); con- vexity in both upper and lower levels (Sabach & Shtern, 2017); unique lower-level solution (Liu et al., 2022); and Lipschitz smoothness (Shen& & Chen, 2023) (less restrictive).
In the DPSM problem (8), the standard classification loss (fs(f) and the conformal alignment loss 2DM (f: 9) are not necessarily convex in f and g. Meanwhile, the QR loss [OR (f, q) in the lower level is not continuously differen- tiable, not strongly convex, and typically has non-unique solution set even for the case without any tie in confor- mity scores. To the best of our knowledge, there no prior stochastic optimization algorithm that solves DPSM problem with the assumptions of bilevel optimization liter- ature satisfied and convergence guaranteed. Consequently, it is non-trivial and an open challenge to develop a simple stochastic gradient optimization algorithm to solve a prob- lem that shares similar conditions with DPSM. We leave this challenge for future work.
This is an immediate result from Theorem 2.7 in (Chen et al., 2024b) and connects the solution of the penalized DPSM problem (10) to that of the original DPSM problem (8).
Simple Stochastic Gradient-based Algorithm. We further present a simple stochastic gradient algorithm to optimize Problem (8). We summarize this approach in Algorithm 1. It mainly follows the common schemes in standard stochastic gradient methods to iteratively update the two variables f and q simultaneously. First, it randomly splits the training set Dy into two disjoint subsets D1 and D2 with the same size (Line 3). Next, given the fixed model ft-1 and quantile variable 4t-1- we compute three stochastic gradients over mini-batches in each training iteration: (i) F on mini-batches of D1 (Line 6), (ii) , CDM 9-1 on mini-batches of D2 (Line 8), and (iii) V , qt I1- on bani-batches of Dj (Line 7). Next, we update the model ft (Line 9) and quantile a: (Line 10) accordingly with their learning rates T7, and %
Penalty-based Reformulation. Given that the lower-level function in DPSM is not strongly convex, implicit gradient methods,e.g. (Ghadimi& & Wang, 2018), cannot handle it. Penalty-based methods is another large family in the bilevel optimization literature. A recent paper (Chen et al., 2024b) studied a penalty-based method when the lower-level prob- lem satisfies Hölderian error bound, and meanwhile both upper and lower level objectives are non-smooth, which is one of the most relevant setting to the DPSM problem at hand. Hence, we reformulate DPSM as penalty-based problem and analyze the global solution of the penalty-basod DPSM problem with a penalty parameter a.
It is worth noting that the proposed DPSM optimization algo- rithm is particularly tailored for our bilevel conformal train- ing problem (8). 1) We employ D2 to compute V f (f) and V,COR (f, q). while evaluate (C on D2. This has been used in conformal training (Einbinder et al., 2022) and helps to prevent over- wver-fitting- 2) We rely on simple first- order information to update, rather than hyper- syperr-grddiett or penalization from the existing bilevel optimization methods. This design keeps the iterative update simple especially for practitioners. Our empirical results in Figure 7 demonstrate
min,, Lals( + A- 2-2M (f.g) (f.(f.g)
(10)
+ (LORRRR - (f.(("))) where 9" E(())
6

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Table 1. HPS Training, HPS and APS Calibration/Testingg (details Appendix E): The average prediction set size (APSS) on three datasets with two deep models trained with HPS and calibrated/tested with HPS and APS when 0.1. 4 indicates the percentage improvement in predictive efficiency compared to the best existing method, whereas 1 denotes a percentage decrease in predictive efficiency. All results are averaged over 10 different runs, with the mean and standard deviation reported. DPSM significantly outperforms almost all the best baselines with 20.46% reduction in prediction set size on average across all three datasets and two scores.
HPS
APS
Model
CF
CUT
ConfTr
DPSM
CF
CUT
ConITTr
DPSM
CalTech-101
DenseNet ResNet
3.50 0.10
1.62 0.030
4.10 = 0.19
0,90 = 0.003 (L 44.44%)
8.44 + 0.15
3,87 = 0.11
8,64 = 0.21
1.58 : 0.022 (L 59.17%)
= 0.018
1.64 0.049
1.52 0.040
0.91
0.005 (4 44.51%)
4.50 0.059
+ 0.072
3.61 : 0.08
1.74 0.031 (1 51.80%
CIFAR-100
DenseNet ResNet
2.59 + 0.053
2.27 + 0.09
2.28 + 0.07
2.17
0.086 (1 4.82%)
3,38 + 0.12
2.41 = 0.11
3.08 + 0.11
2.64 + 0.086 (? 8.71%) 3.53 = 0.11 (L 7.35%)
= 0.10
3.01 + 0.11
3.77 = 0.14
2.94 + 0.08 2.32%)
3,98 10.13
3.81 0.08
4,90 = 0.18
iNaturalist
DenseNet
94.58 +: 3.45
77.13 3.72
79.93 + 3.70
61.22 : 2.49 20.63%)
101.97 +: 3.16
88.93
3.06
90.79 3.17
75.98 = 2.99 (L 14.56%)
ResNet
99.48 + 8.95
73.09 2.00
76.73 + 3.87
70.04 1.99 4.19%)
95.81 3.80
79.00 2.21
88.70 3.88
79.43 + 2.39 ( 0.54%)
stable convergence of both upper and lower level problems of DPSM by employing standard practices for learning rates and y.
Pax EiEDI. 1[2 E Cy(x,)]. Our second evaluation metric is the prediction set size (Avg-Set-Size), defined Avg-Set-Size |Pail Eieo.. (C,(X:))- To make the conformal aligmment loss smooth, DPSM and ConfTr use the Sigmoid function to approximate the average prediction set size (APSS) during training, so we use the third evalu- ation metric as the Soft Set Size Avg-Soft--Szz), defined as Avg-Softset-Size = Daan ΣiEDu, EvEy
1
5. Experiments and Results
This section describes our experimental evaluation of the proposed DPSM algorithm and baselines real datasets.
i (X,)(X,,)) .y) S क recall that is S q] = 1/(1+ [x1+exp(-(4) - 5)/ ////ggsg)))) with a hyperparameter TSigmoid-
5.1. Experimental Setup
Datasets. We utilize the benchmark datasets CIFAR-IO0 100 (Krizhevsky et al., 2009), Caltech- and iNaturalist (Van Horn et al., 201 8), where all details are summarized in Table 2 of Appendix E.
101 (Fei-Fei et al., 2004),
5.2. Results and Discussion
We discuss the results comparing DPSM with baseline meth- ods, fine-grained analysis for DPSM to demonstrate its ef- feetiveness and validate our theoretical results.
Deep Models. We train two widely used neural network architectures with HPS scoring function: ResNet (He et al., 2016) and DenseNet (Huang et al., 2017). The training hyperparameters are provided in Table of Appendix.
DPSM generates smaller prediction sets. Table presents the prediction set sizes for different methods using HPS score for training, HPS and APS scores for calibration and testing phases at a = 0.1, as detailed in Appendix E. On average, DPSM reduces the prediction set size by 20.46% across the three datasets relative to the best baseline. Specif- ically, DPSM provides the best predictive efficiency com- pared all other existing methods when calibrated with HPS. It also outperforms the best baselines when calibrated with APS in all cases except 1 8.71 % increase on CIFAR- 100 with DenseNet and 1 0.54% increase on iNaturalist with ResNet in terms of the prediction set size.The cover- age results for overall comparison and additional results for calibrating with RAPS scoring function are in Appendix F.I. We also visualize the coverage rate and APSS with con- fidence intervals of all methods using DenseNet and HPS score in Figure I. It clearly confirms that DPSM achieves significantly smaller prediction set size while maintaining the valid coverage.
Conformity scoring functions. We consider three non- conformity scoring functions: HPS (Vovk et al., 2005; Lei et al., 2013) APS (Romano et al., 2020), and RAPS (An- gelopoulos et al., 2021). The detailed review of these scor- ing functions is in Appendix A.
Baseline methods. We select three different training meth- ods as baselines: (i) CE, training with standard cross-entropy loss only; (ii) CUT (Einbinder et al., 2022), mitigating the overconfidence of the deep neural network by penalizing the gap between the CDF of the non-conformity scores and the uniform distribution; and (iii) ConfTr (Stutz et al., 2021), aiming to decrease prediction set size by inducing confor- mal loss as the average differentiable prediction set size. The details of CUT and ConfTr are in Appendix A.
Evaluation metrics. Our first evaluation metric is the marginal coverage (Marg-Cov), defined as MargCov =
7

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Caltech-101
(b) CIFAR-100
(c) iNaturalist
0.910
0.915
0.92
0.905
0.910
0.91
Covera
5..900
Coverage
8.0.95
0.895
0.900
0.90
0.899
0.895
0.89
0.890
0.885
0.88
0.885
0.880
CE
ConfTr CUT
DPSM
CE
ConfTr CUT
DPSM
CE
ConfTr
CUT DPSM
Method
Method
Method
4.5
2.7
100
4.0
2.6
3.5
Average size
2.5
3.0
2.5
2.4
80
2.00
2.3
1.5
2.1
60
CE
ConfTr CUT Method
DPSM
CE
ConfTr CUT
DPSM
CE
ConfTr CUT
DPSM
Method
Method
Figure 1. Box plots of coverage (Top row) and APSS (Bottom row) of all methods using DenseNet and HPS score. DPSM achieves
significantly smaller prediction set size while maintaining the valid coverage.
Upper loss
(b) Lower loss
port the results of 40-epoch training regime Appendix for reference. As shown, the upper-level loss of DPSM ex- hibits initial increase during the first 5 epochs, reaching the peak, then steadily decreases before stabilizing around epoch 35. In contrast, the lower-level loss decreases sharply within the first 5 epochs, followed by gradual reduction until convergence near the end of training. These results empirically demonstrate that DPSM effectively converges in terms of both upper and lower level training errors, val- idating its bilevel optimization approach. To investigate how the learned quantiles influence the optimization ror, we compute both conformal and QR losses using the learned quantiles and the optimal (dataset-level) quantiles. The corresponding optimization errors arrors-defined as the loss differences between learned and optimal quantiles- are vi- sualized in Figure (c) and (d). Both errors converge to nearly O, indicating that the learned quantiles effectively approximate the optimal quantiles over training epochs.
5.5
5.0
Upper_ loss
los
0.10
Lower_log
4.5
0.08
4.0
0.06
S
3.5
0.04
3.0
0.02
20
60 Epochs
40
100
Epochs
(c) Conformal loss
(d) QR loss optimization
optimization gap
gap
Conformal Opt Gap
0.005
$0.004
2
Ogt
0.003
0.002
0.001
0.000
20
40
60
80
100
60
Epochs
Epochs
Figure 2.
Justification experiments for the convergence of DPSM on CIFAR-100 using DenseNet and HPS score. (a) Upper level loss (i.c,, combination of classification loss and conformal alignment loss): (b) Lower level loss (i.e.. QR loss); (c) Opti- mization gap conformal loss, defined as the difference between conformal losses using learned batch-level quantiles and dataset- level quantiles on training set; (d) Optimization gap of lower-level QR loss, defined similarly as the loss difference he- tween learned batch-level quantiles and datasct-level quantiles.
DPSM estimates empirical quantiles with small error. To compare the precision of empirical quantiles estimation in ConfTr and DPSM, we plot the estimation error between Q7 (quantiles evaluated on the whole training dataset) and 9y (quantiles evaluated in ConfTr or learned in DPSM on mini mini-batches). Figure (a) plots this estimation error training epochs. For the first 25 epochs, the estimation er- rors for DPSM are significantly larger compared to ConfTr. However, as the training progresses, the estimation errors for DPSM decrease rapidly. converging close to 0 after epoch 35. This result verifies the theoretical result for smaller esti- mation eтror in learning bound analysis from Theorem 4. The rapid reduction in estimation error also reflects the con- vergence of the lower loss (i.e., QR loss), highlighting the effectiveness of DPSM in accurately estimating quantiles.
DPSM converges stable error for bilevel optimization. To further explore how DPSM effectively generates smaller prediction sets, analyze the convergence of DPSM by plotting the loss of the upper level function (i.e., combi- nation of classification loss and conformal alignment loss) and the lower level function (i.e.. QR loss) over training epochs. Figure (a) and (b) show the upper-level loss and lower-level loss over 100 epochs, respectively. We also re-
8

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Estimation error of quantiles
(b) Average soft set size
(c)
Learning bound approximation
Quantile estimation errc
50
2 $ g
0.8
DPSM
2.5
DPSM ConfTr
0.6
ConfTr
Softset Size
45
2.0
40
DPSM
abs(train APSS
1.5
0.4
ConfTr
1.0
35
0.2
0.5
30
0.0
0.0
10
20 30 40 50 Epochs
60
10
20 30
40 Epochs
50
60
5
10
15
20
25 30 35 40 45 50 55 60 Epochs
Figure 3. Justification experiments for the learning bound of DPSM on CIFAR-100 using DenseNet and HPS score. (a) Estimation error between the Q7 (i.c., the dataset-level quantiles on training data) and ūy (i.e., either the batch-level quantiles evaluated in ConfTr or the learned ones DPSM); (b) Average soft set size (approximated using Sigmoid function) of DPSM and ConfTr: (c) Approximated learning enror comparison between DPSM and ConiTr, measured by their gaps between the training and testing APSS.
Learning bound of DPSM is much tighter than ConfTr: To approximately compare the learning bounds of DPSM and ConfTr, we compare the conformal alignment losses of ConiTr and DPSM during training in terms of the average soft set size, as shown in Figure 3 (b). The soft set size of DPSM consistently smaller than that of ConfTr during training. Combining the empirical results of the smaller estimation error of quantiles from Figure (a), we can con- clude that the learning bound of DPSM is much tighter than
Assumption 3.2 is empirically valid. Figure 4 (b) visu- alizes the soft set size of ConfTr, with input as coverage rate E [0.02, 0.98] with range 0.02. When coverage rate approaches 0.9, the curves of all methods exhibit a concave shape (zoom-in version also shown), providing empirical verification for Assumption 3.2.
(a) Bi-Lipschitz continuity of conformity score
(b) Strongly concavity of conformal loss
the learning bound of ConfTr, providing the empirical ver- ification of Theorem 4.1 and 3.5. Although the learning bound cannot be empirically computed, we approximate it using a common strategy in ML literature (Yuan et al., 2019;
Conformity Score
1.0
Conformal Loss
0.a
&
0.6
40
0.4
35
Yang et al., 2021b), which estimates the generalization error
0.2
30
0.0
by the absolute gap between training and test errors. For
0.2 0.6
2.000
0.2
0.4
0.6
0.8
1.0
Normalized Order
Coverage Rate
CP, we use APSS evaluated on the train and test sets to approximate the learning errors. Specifically, for DPSM, at each iteration, we: (i) compute APSS on the training set using the learned quantiles as thresholds. It includes opti- mization error since the Iearned quantiles are not optimal (true letaset-level quantiles); (ii) compute the APSS on the testing set using the dataset-level quantiles as thresholds. The gap between these two APSS values is employed as approximation of the learning bound. We apply the same strategy to the SA-based ConfTr, where the training APSS is computed using the quantiles evaluated on mini-batches from the training data, and the test APSS is computed using the dataset-level quantiles from the test data. This compari- son is shown in Figure 3 (c), which demonstrates that the approximated learning error is improved by DPSM.
Figure 4. Assumption verification CIFAR-100 using DenseNet and HPS score on the calibration dataset. (a) HPS scores over corresponding normalized index produced by ConfTr. The x-axis is the normalized order, the y-axis is the corresponding conformity score: (b) The soft set size measure of ConfTr. The input coverage rate is from [0.02, 0.98) with 0.02 range with its zoom-in version where coverage rate is close to the target coverage 0.9; When coverage rate is close to 0.9, the curve for the soft set size exhibits concave shape.
6. Conclusion
This paper developed Direct Prediction Set Minimization (DPSM), a novel conformal training algorithm formulated as a bilevel optimization problem. By leveraging quantile regression in the lower-level subproblem, DPSM precisely learns the empirical quantile of non-conformity scores, lead- ing to smaller prediction sets. Theoretical analysis showed that DPSM attains tight learning bound of O(1/vm) with n training samples. Empirical evaluation on real-world datasets confirmed that DPSM significantly outperforms existing conformal training methods, validating both its the- oretical advantages and practical effectiveness.
Assumption 3.1 is empirically valid. Figure 4 (a) illus- trates the conformity scores against their corresponding normalized order. The x-axis represents the normalized or- der, while the y-axis represents conformity scores. is clear that the curve does not remain near the x-axis or y-axis, in- dicating that the gradient of conformity scores with respect to normalized index is both upper and lower bounded. This observation empirically validates Assumption 1.

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Acknowledgements
Barber, R. F,, Candes, E. J., Ramdas, A., and Tibshirani, J. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507, 2021.
The authors gratefully acknowledge the in part support by USDA-NIFA funded AgAID Institute award 2021-6700 35344 and the NSF grant CNS-2312125. The views ex- pressed those of the authors and do not reflect the official policy or position of the USDA-NIFA and NSF.
Bates, S., Angelopoulos, A., Lei, L.., Malik, J., and Jor- dan, M. Distribution- free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-34 2021.
Beck, Y., Ljubié, I,, and Schmidt, M. A survey on bilevel optimization under uncertainty. European Journal of Operational Research, 31 (1)(4)401--26 2023.
Impact Statement
This paper focuses on integrating conformal principles into the training procedure of deep neural network classifiers to produce small prediction sets. The insights in this pa- per could improve the safe deployment of deep classifiers in may high-risk applications. There is not any negative consequences to be specifically highlighted here.
Begoli, E., Bhattacharya, T., and Kusnezov, D. The need for uncertainty quantification in machine-assisted medical decision making. Nature Machine Intelligence, 1(1):20-
23, 2019.
Bellotti, A. Optimized conformal classification us- ing gradient descent approximation. arXiv preprint arXiv:2 //255, 2021.
References
Abdar, M., Pourpanah, F,, Hussain, S., Rezazadegan, D., Liu, L., Ghavamzadeh, M., Fieguth, P., Cao, X., Khos- ravi, A., Acharya, U. R., et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information Fusion, 76:243-297, 2021.
Bhatnagar, A., Wang, H., Xiong, C., and Bai, Y. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learn- ing, pp. 2337-2363. PMLR, 2023.
Bolte, J., Nguyen, T. P., Peypouquet, J., and Suter, B. W. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Program- ming, 1 165:471-25 475-077, 2017.
Angelopoulos, A. N. and Bates, S. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXi::210.005111, 2021. 2021.
Angelopoulos, A. N., Bates, S., Jordan, M., and Malik, Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021.
Bolte. J., Le, T., Pauwels, E., and Silveti-Falls, T. Nons- mooth implicit differentiation for machine- learning and optimization. Advances in neural information processing systems, 34:13537-13549 2021.
Bolte, J., Pauwels, E.,, and Vaiter, S. Automatic differentia- tion of nonsmooth iterative algorithms. Advances in Neu- ral Information Processing Systems, 2022.
Angelopoulos, A. N., Kohli, A. P., Bates, S., Jordan, M., Malik, J., Alshaabi, T., Upadhyayula, S., and Romano, Y. Image-to-image regression with distribution-free un- certainty quantification and applications in imaging. In International Conference on Machine Learning, pp. 717- 730. PMLR, 2022.
Borsos, Z., Mutny, M., and Krause, A. Coresets via bilevel optimization for continual learning and streaming. Ad- vances in neural information processing systems, 33: 14879-14890, 2020.
Angelopoulos, A. N., Candes, E., and Tibshirani, R. Con- formal pid control for time series prediction. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
Borsos, Z.. Mutný, M., Tagliasacchi, M., and Krause, A.
Data summarization via bilevel optimization. Journal of Machine Learning Research, 25(33): 2024.
Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L., and Schuster, T. Conformal risk control. In The Twelfth International Conference on Learning Representations, 2024.
Cauchois, M., Gupta, S., and Duchi, J. C. Knowing what you know: valid and validated confidence sets in mul- ticlass and multilabel prediction. Journal of machine learning research, 22(81):1 42, 2021.
Babbar, V., Bhatt, U., and Weller, A. On the utility of prediction sets in human-ai teams. In Proceedings of the Thirty-Firs First International Joint Conference on Artificial Intelligence (IJCAI-22), 2022.
Chen, L., Xu, J., and Zhang, J. On finding small hyper- gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Anmual Confer- ence on Learning Theory, pp. 947-980. PMIR, 2024a.
10

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Chen, P., Shi, X., Jiang, R., and Wang. J. Penalty-based methods for simple bilevel optimization under hölderian error bounds. In The Tiihty- Annual Conference Neural Information Processing Systems, 2024b.
expanded admission. In Proceedings of The Tenth Inter- national Conference on Learning Representations, 2021a.
Fisch, A., Schuster, T., Jaakkola, T., and Barzilay, R. Few- shot conformal prediction with auxiliary tasks, In Interna- tional Conference Machine Learning, pp. PMLR, 2021b.
Chen, T., Sun, Y., and Yin, W. Closing the gap: Tighter anal- ysis of alternating stochastic gradient methods for bilevel problems. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021.
Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv: 1802.02246, 2018.
Chen, X., Xiao, T., and Balasubramanian, K. Optimal algo- rithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1-51, 2024c.
Ghosh, S., Belkhouja, T., Yan, Y., and Doppa, J. R. Im- proving uncertainty quantification of deep classifiers via neighborhood conformal prediction: Novel algorithm and theoretical analysis. In AAAI, pp- 7722-7730, 2023a.
Cheng, C.-.,, Xie, T., Jiang, N., and Agarwal, A. Adversar- ially trained actor critic for offline reinforcement learning. In International Conference Machine Learning, pp. 3852-3877 PMLR, 2022.
Ghosh, S., Shi, Y., Belkhouja, T., Yan, Y., Doppa, J. and Jones, B. Probabilisticall robust conformal prediction. Uncertainty in Artificial Intelligence, pp. 681-690.
Cresswell, C., Sui, Y., Kumar, B., and Vouitsis, N. Confor- mal prediction sets improve human decision making. In Forty-first International Conference on Machine Learn- ing. 2024.
PMLR, 2023b.
Gibbs, and Candes, E. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34: 11111166-1600 1672, 2021.
Dagréou, M., Ablin, P., Vaiter, S., and Moreau, T. A frame- work for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 55:26698-267106 2022.
Gibbs, I. and Candès, E. J. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162): 1-36, 2024.
Deshpande, S., Marx, C., and Kuleshov, V. Online calibrated and conformal prediction improves bayesian optimization. In International Conference Artificial Intelligence and Statistics, pp. 1450-1458. PMLR, 2024.
Gibbs, I., Cherian, J., and Candès, E. Conformal prediction with conditional guarantees. arXiv preprint arXiv:2305.12611 2023.
Gong, X., Hao, J., and Liu, M. An accelerated algorithm for stochastic bilevel optimization under unbounded smooth- ness. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024a.
Ding, T., Angelopoulos, A., Bates, S., Jordan, M., and Tib- shirani, R. J. Class-conditional conformal prediction with many classes. Advances in Neural Information Process- ing Systems, 36, 2024.
Gong, X., Hao, J., and Liu, M. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In ICML, 2024b.
Domke, Generic methods for optimization- based model- ing. In Artificial Intelligence and Statistics, pp. 318-326. PMLR, 2012.
Guan, L. Localized conformal prediction: A generalized in- ference framework for conformal prediction. Biometrika, 1 110(1):33 2023.
Einbinder, B.-S., Romano, Y., Sesia, M., and Zhou, Train- ing uncertainty aware classifiers with conformalized deep learning. Advances in Neural Information Processing Sys- fems, 35:22380-22395, 2022.
Hao, J., Ji, K., and Liu, M. Bilevel coreset selection in continual learning: A new formulation and algorithm. Advances in Neural Information Processing Systems, 36, 2024.
Fei-Fei, L., Fergus, R., and Perona, Learning genera- tive visual models from few training examples: An in- cremental bayesian approach tested on 101 object cate- gories. Computer Vision and Pattern Recognition Work- shop, 2004.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Fisch, A., Schuster, T., Jaakkola, T., and Barzilay, R. Effi- cient conformal prediction via cascaded inference with

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
He, K., Gkioxari, G., Dollár, P., and Girshick, R. Mask enn. In Proceedings of the IEEE international conference on computer vision, pp. 2961-2969, 2017.
Kumar, A., Irsoy, O., Ondruska, P., lyyer, M., Bradbury, J., Gulrajani, I., Zhong, V., Paulus, R., and Socher, R. Ask me anything: Dynamic memory networks for natu- ral language processing. In International conference on machine learning, pp. 1378-1387. PMLR, 2016.
Hong, M., Wai, H.-T., Wang. Z., and Yang, Z. A two- timescale stochastic algorithm framework for bilevel op- timization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023. doi: 10. (0.1137/0013887311
Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. A fully first-order method for stochastic bilevel optimiza- tion. In International Conference on Machine Learning, pp. 18083 10083-18122 18113. PMLR, 2023.
Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700 4708, 2017.
Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In The Twelfth Inter- national Conference on Learning Representations, 2024.
Huang. J., Xi, H., Zhang, L., Yao, H., Qiu, Y., and Wei, H. Conformal prediction for deep classifier via label ranking. arXiv preprint T..::33000064:00 2023a.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Huang. M., Zhang, D., and Ji, K. Achieving linear speedup in non-iid federated bilevel learning. In International Con- ference on Machine Learning, pp. 14039-14059. PMLR, 2023b.
Lei, J., Robins, J., and Wasserman, L. Distribution-Fii prediction sets. Journal of the American Statistical Asso- ciation, 108(501):278-255)) 2013.
Ji, K., Yang. J., and Liang, Y. Bilevel optimization: Con- vergence analysis and enhanced design. In International conference on machine learning, pp. 4892-4892. PMLR, 2021.
Liu, B., Ye, M., Wright, S., Stone, P., and qiang liu. BOME! bilevel optimization made easy: A simple first-order ap- proach. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Process- ing Systems, 2022.
Kawaguchi, K. and Lu, H. Ordered sgd: A new stochastic optimization framework for empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 669-677 689-679. PMLR, 2020.
Liu, R., Mu, P., Yuan, X., Zeng. S., and Zhang, J. A generic first-order algorithmic framework for bi-level program- ming beyond lower-level singleton. In International con- ference machine learning, pp. 6305-6315. PMLR, 2020.
Khanduri, P., Zeng. S., Hong. M., Wai, H. T., Wang, Z., and Yang, Z. A near-optimal algorithm for stochastic bilevel optimization via Gouble-momentee
In Beygelzimer, A., Dauphin, Y., Liang. P., and Vaughan, J. W. (eds.), Ad- vances in Neural Information Processing Systems, 2021.
Liu, R., Gao, J., Zhang, J., Meng, D., and Lin, Z. Investigat- ing bi-level optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 44 (12):10045-1007 2021.
Kiyani, S., Pappas, G. J.. and Hassani, H. Conformal pre- diction with learned features. In Forty-first International Conference on Machine Learning, 2024a.
Liu, Z., Cui, Y., Yan, Y., Xu, Y., X., Liu, X., and Chan, A. B. The pitfalls and promise of conformal inference under adversarial attacks. In International Conference on Machine Learning, pp. -0908-30928. PMLR, 2024.
Kiyani, S., Pappas, G. J., and Hassani, H. Length optimiza- tion in conformal prediction. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b.
Lu, C., Angelopoulos. A. N., and Pomerantz, S. Improving trustworthiness of ai disease severity rating in medical imaging with ordinal conformal prediction sets. In Inter- national Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 545-554. Springer, 2022a.
Koenker, R. Quantile regression, volume 38. Cambridge university press, 2005.
Koenker, R. and Bassett Jr, G. Regression quantiles. Econo- metrica: journal of the Econometric Society, pp. 33-50, 1978.
Lu, C., LLeaa, A., Chang, K., Höbel, K., and Kalpathy- Cramer, J. Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
12

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
on Artificial Intelligence, volume 36, pp. 12008-12016, 2022b.
Shafer, G. and Vovk, V. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
Lu, Z. and Mei, S. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1937- 1969, 2024.
Shahrokhi, H.,, Roy, D. R., Yan, Y., Arnaoudova, V., and Doppa, J. R. Conformal prediction for deep gen- erative models via reduction conformal regression. CoRR, abs/2503. 2503.10512. URL https: /tt./iiiio//// http:////do...//...//./ 48550/ arXiv. 2503.. 250.. 10512.
2025. doi: 10.48550/ARXIV.
Masters, D. and Luschi, C. Revisiting small batch training for deep neural networks. arXiv preprint vrXiv:1804.0700 2018.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- lions of machine leurning. MIT press, 2018.
Narayan, T., Wang. S. L.,, Canini, K. R., and Gupta, M. Ex- pected pinball loss for quantile regression and inverse cdf estimation. Transactions on Machine Learning Research, 2024.
Shen, H. and Chen, T. On penalty- based bilevel gradient descent method. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202, pp. 30992-31015, 2023.
Oliveira, R. I., Orenstein, P., Ramos, T., and Romano, J. V. Split conformal prediction and non-exchangeable data. Journal of Machine Learning Research, 25(225):1-38, 2024.
Shen, H. and Chen, T. On penalty-based bilevel gradient descent method. Mathematical Programming (MAPR), to appear, 2025.
Shen, H., Yang, Z., and Chen, T. Principled penalty- -based methods for bilevel reinforcement learning and rlhf. In Forty-first International Conference on Machine Learn- ing.
Pang. J.-S. Error bounds in mathematical programming. Mathematical Programming, 79(1):299-332 1997.
Pedregosa, F. Hyperparameter optimization with approxi- mate gradient. In International conference on machine learning, pp. 737-746. PMLR, 2016.
Shi, Y., GHOSH, S., Belkhouja, T., Doppa, J., and Yan, Y. Conformal prediction for class-wise coverage via augmented label rank calibration. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Podkopaev, A., Xu, D., and chih Lee, K. Adaptive con- formal inference by betting. In Forty-first International Conference on Machine Learning, 2024.
Romano, Y., Patterson, E., and Candes, E. Conformalized quantile regression. Advances in neural information pro- cessing systems, 32, 2019.
Straitouri, E., Wang, I.., Okati, N., and Rodriguez, M. G. Im- proving expert predictions with conformal prediction. In International Conference on Machine Learning (ICML), 2023.
Romano, Y., Sesia, M., and Candes, E. Classification with valid and adaptive coverage. Advances in Neural Infor- mation Processing Systems, 33:3581-3591, 2020.
Stutz, D., Cemgil, A. T., Doucet, A., et al. Learning optimal conformal classifiers. arXiv preprint arXiv:2110.09192. 2021.
Roulet, V. and d' Aspremont, A. Sharpness, restart and acceleration. Advances in Neural Information Processing Systems, 30, 2017.
Van Horn, G., Mac Aodha, O., Song, Y., Cui, Y., Sun, C., Shepard, A., Adam, H., Perona, P., and Belongie, S. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8769-8778 2018.
Sabach, S. and Shtern, S. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-660, 2017. doi: 10.1137/ 16M105592X.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances neural information processing systems, 30, 2017.
Sadinle, M., Lei, J., and Wasserman, L. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223- 234, 2019.
Vovk, Cross-conformal predictors. Annals of Mathemat- ics and Artificial Intelligence, 74(1):9-28, 2015.
Sesia, M. and Romano, Y. Conformal prediction using conditional histograms. Advances in Neural Information Processing Systems, 34:6304 6315, 6315, 2021.
Vovk, V., Gammerman, A., and Saunders, Machine- learning applications of algorithmic randomness. 1999.
13

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in random world. Springer Science & Business Media, 2005.
Zhou, X., Pi, R., Zhang, W., Lin, Y., Chen, Z., and Zhang, T. Probabilistic bilevel coreset selection. In International Conference on Machine Learning, pp. 27287-27302. PMLR, 2022.
Vovk, V., Fedorova, V., Nouretdinov, I., and Gammerman, A. Criteria of efficiency for conformal prediction. In Confor- mal and Probabilistic Prediction with Applications: 5th International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 5, pp. 23-39. Springer, 2016.
Zhu, Y., Hernández, D., He, Y., Ding, Z., Xiong, B., Khar- lamov, E., and Staab, S. Predicate-condition conformal- ized answer sets for knowledge graph embeddings. arXiv preprint
16877, 2025.
Yan, G., Romano, Y., and Weng, T.-W. Provably robust conformal prediction with improved efficiency. In The Twelfth International Conference Learning Represen- tations, 2024.
Yang. J., Ji, K., and Liang, Y. Provably faster algorithms for bilevel optimization. In Beygelzimer. A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021a.
Yang, S. and Fevens, T. Uncertainty quantification and esti- mation medical image classification. In Artificial Neu- ral Networks and Machine Learning-ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14-17, 2021, Proceed- ings, Part III 30, pp. 671-683. Springer, 2021.
Yang, T. and Lin, Q Rsg: Beating subgradient method without smoothness and strong convexity. Journal of Machine Learning Research, 19(6):1-33, 2018.
Yang. Y., Xiao, P., and Ji, K. SimFBO: Towards simple, flexible and communication--ffiieee. federated bilevel learning. In Thirty-seventl Conference on Neural Infor- mation Processing Systems, 2023.
Yang, Z., Bai, Y., and Mei, S. Exact gap between general- ization error and uniform convergence in random feature models. In International Conference on Machine Learn- ing. pp. 1 11704 11715. PMLR, 2021b.
Yuan, Z., Yan, Y., Jin, R., and Yang, Stagewise training accelerates convergence of testing error over sgd. Ad- vances in Neural Information Processing Systems, 32, 2019.
Zhang, Y., Khanduri, P., Tsaknakis, I., Yao, Y., Hong, M., and Liu, S. An introduction to bilevel optimization: Foun- dations and applications in signal processing and machine learning. IEEE Signal Processing Magazine, 41(1))38- 59, 2024.
Zhou, W. Bi-level offline policy optimization with limited exploration. Advances in Neural Information Processing Systems, 36, 2024.
14

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
A. Additional background details
Non-conformity scoring functions. The homogeneous prediction sets (HPS) (Sadinle et al., 2019) scoring function defined as follows:
(11)
(Romano et al., 2020) has proposed another conformity scoring function, Adaptive Prediction Sets (APS). APS scoring function is based on sorted probabilities. For given imput X, we sort the softmax probabilities for all classes {1, K} such that (1) (o( 2 O, and compute the cumulative confidence follows:
SYPS (X,Y)
Σ
So(X)( + So(X
(12)
where U [0, is uniform random variable to break ties.
To reduce the probability of including unnecessary labels (i.e., labels with high ranks) and thus improve the predictive
efficiency, (Angelopoulos et al.. 2021) has proposed Regularized Adaptive Prediction Sets (RAPS) scoring function. The
RAPS score is computed as follows:
(X,))
SRAPS (x,Y)
fo(X) +U (o) (RAPS(T)(X,))) Krrg)t
(13)
where ARAPS and kreg are two hyper-parametent
Objective function for conformal training methods. ConfTr (Stutz et al., 2021) estimates soft measure of the prediction set size, defined as follows:
ASA (f) =E
Σ
Σ WE>
(X v) - 2r
(14)
where i[.] is a smoothed estimator for the indicator function 1[:] and defined by Sigmoid function (Stutz et al., 2021), i.e.,
i[S q) = 1/(1 + exp(-(q - S)/TTiimmiia) with tunable temperature parameter TSigmoid
CUT (Einbinder et al., 2022) measures the maximum deviation from the uniformity of conformity scores, defined follows:
CSA (stur()) - su (1 a. - ")(())
(15)
where (a) the empirical batch-level quantile B of input [0, 1].
B. Proof for Section 3
In this section, we prove Proposition 3.4 and Theorem 3.5 from Section 3.
B.1. Proof for Proposition 3.4
Proposition B.1. (Proposition 3.4 restated, distribution of mini-batch quantiles) Define an event Z(j) as "the j-th smallest score Sty) from {5 is selected as (a)) on mini-batel B". Then the probability of (jj) is:
P(Z())) (ra-a)to+1n) (-r
n-j-1 (--((a)(e+]))-))
Furthermore, we have the following asymptotic result
lim P(Z())) - (2: 1)] + 1;8 [(1 a1) + 1)1).
where PReea 0; b) the PDF of Beta distribution with two shape parameters a,
15

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Proof. (Proof of Proposition 3.4) This proof follows the proof for Proposition I in (Kawaguchi & Lu, 2020).
Recall the Stirling's approximation that is used to prove this proposition:
n! v2mn(n/e)"
To simplify the representation, we denote
[(1 - a) + 1)] in this proof. Then, the P(Z(i)) could be rewritten as:
P(Z())
(t) (--d-tt
alu 1s-a-11 [1 jtaj stajl
(n-j-1) 1)1
s!
j!
(n- - j - 1)! (n - s)!
al(s a 1)11 (j - a)! (n - + aa)! n!
3l(==]]
(16)
Applying the Stirling's approximation when n oc, we have that:
j! (n j - 1)!
(n 8)!
G a-a (n j + a) n!
(2)
n-j=1 jn-j-1
2r(n 8) 1
V2T(j a) (- j-0 v 2T j 8 a) p-i=sta injj-ota
v2Tn 15 m)
(n - j- 8 + ) n e statl )
(n j 1)m-ーー1
(j a)--a
(n) n
(n (n-1)) 1-
(n)r-
e (j a
(n - j-n) j)a- (n)*
(n)(1)
(n j) s)---11- (n)-
(m)-=a( (- y-
2
n - I p0----11 a- (n))-aan (n)
(n)a.
(1-))--
n
a--a-1
(17)
Combining the Equation (16) and (17), we have that:
lim P(Z()))
e n a!(s a - 1)! n
(2 (1 2---a11 e I(a 1+s a) nl + 1)l a) (2 (1 -2 20-0-1
22000
n
e PBeu [ 711(11 (s + 1)] 1;8 [(1 - a))s 111) 1)1)
n
n
where [(n) (n 1 is gamma function and P (2; b) T(a+b) [(]](b)
. 10 xz)0-1 is the probability density function
of Beta distribution with shape parameters a and at x.
B.2. Proof for Theorem 3.5
Theorem B.2. (Theorem 3.5 restated, learning bounds of SA method) Suppose that Assumption 3.1 and 3.2 hold. Assume a))s + 1) is not an integer. If [(1 - (s + 1)] - (1 - (s) + 1) Z 12(1/s) and s S vn, then the following inequality holds with probability least 5:
((1/s) < ESA - = O(1/33)
Proof. (Proof of Theorem 3.5)
We need the following helpful technical lemmas:
Lemma B.3. (Lower bound for Z(f, Egy (rr) - -Egy ((): Suppose that Assumptions 3.1 and 3.2 hold. Then, the following inequality holds:
( Eay (r))
Eag ((F))))) 2 2(1/s).
16

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Lemma B.4. (Lower bound for ( ZU, Suppose that Assumption 3.1 holds. Assume (1 a)) + 1) is an integer. [f - (s) + 1)] -1-a)) 1) (11ss) and S vn, hen the following inequality holds:
RU, - (1) 9(1/8).
Lemma B.5. (Distance between Le Tf) and Fa, (r) Suppose that Assumption 3.1 holds, With probability at least 1 - 8, the following inequality holds:
The proofs of Lemma B.3, B.4, and B.5 are deferred to the end of this proof.
Recall that
1 E
(f) E,,-o, E
e
[S v) s कr
Dey
=((ras)
Cc(5) ((f))=(f.)))-BB =xx
Σ
(Xs,(X.0) v) S Qn1
NvE
We start with the lower bound in Theorem 3.5.
-(00))))=((E000000 (C) fa(l))² =( ((. = = (Eg- 0, (((f. E(F,E(T))) + E((s) - 2(F
+ ((, ((1Q1))
20(1/82). Lomma B.3
20
(Eng-2, [e(f. f(f 20(1/8), Lemma B.3
(f. - (
- -1.
200168) Lemma B.4
001//)), Lemma C.4
20(1/8?),
where the last inequality is due nz. The above inequality thus indicates the result:
- 9(1/s).
Next, we begin to prove the upper bound in Theorem 3.5:
(c(f.11)) Ee <(6,(11r) L.() + (c( (F:
20(1/v3), according Lemma
<L1Q, क5| +(L/V8)
-[|S)(((-)((+++)) -+
SL. L2 a)(s +1)1
[[1 a -1 -(1]v())(++ +0(1/v8)
*
<L L2 0(1/33) + - - +01//3 = 0(1/33)
where the first inequality is due to the triangle inequality, the second inequality is due to the L-Lipschitz continuous of Le(f. Qγ) in Lemma C.3 and Lemma B.5, and the third inequality is due to (24) and Assumption 3.1.
Combining the lower and upper learning bound, the proof of Theorem 3.5 finished.
17

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
B.3. Proof for Lemma B.3
Proof. (of Lemma B.3)
We begin prove the lower bound of ((f, Eg,f.E,,101 (5yl) Egy (
By the j-strong-concavity of {(,, 4) in q (Assumption 3.2), we have
(ū (11)) En, [[] = Eg [((. Egg (g1) - [(( E
10, E,, (0 - E(gy)) + 2 (qr E(
FF qg [0s - E( [ _ (I(1-a) an + 1)] 1)1 ))
E (ELi] -))
11
2 [.
n
ni²
=L P ([(1-a)(e 1)1 + () [(1- (s + 1)1) (s + () +2
2 L
# 0(1/s) = 12(1/s),
2
2
where the second inequality due to Proposition 3.4 and Bi-Liischitz continuity of score Stz) in (Assumption 3.1), the third inequality due to the property of variance, i.e., V(X) = [[(E[X] - x) z El(a- X) for any a, and the third ob
equality is due the variance of Beta distribution (j satisfies Beta distribution, Proposition 3.4) [o+b)*a+++o] with the shape parameter a, b.
B.4. Proof for Lemma B.4
Proof. (of Lemma B,4)
To prove Lemma B.4, we need the following technical lemma (proof is deferred to Section B.6).
Lemma B.6. Assume (s) + is not an integer. If (((--a)) + 1)] (1- as) 1) 2 221/s) and vn.
then
(1-a)(++1] (1-a) 2 (11/s).
++1
By using the p-strong-concavin of ((f.g) )) in g, we have
(()) (5) 2
-(ūr) 11 (Q; F 2
0, - Qr) + -Q)) B- (E(0rl - Q2),
O0 due to no tie
20
where the second inequality due to no tie in the distribution of non-conformity scores and there exists a value B > 0 as in (25) such that 0,((S,g) 4) B 0. It suffixes to show the lower bound of [[(r]] Q5.
Due to satisfies the Beta distribution with the two shape parameters (Proposition 3.4) and the mean of Beta random variable is a/(a + 1), we know that the corresponding probability for E Ø [[1=1] and it is larger than a if (1 (s 1) is not an integer.
[(1 a) + and s- s- 1)]
*+1
Recall that Q is the empirical quantile on set of data. We regard Q, as the [II-a))=-I quanttie on Dr. Since Qs(a) is increasing decreases,
" the Bi-Lipschitz continuity of S (Assumption 3.1):
I [ - O, - - - Q, In [1- + 1)1
[(1 aa)((n + 1) + ( (Q)-Q
8+1
-
0(1ss).
where the two inequalities are due Lemma B.6, Bi-Lipschitz continuity of Sty (Assumption 3.1) and the concentration inequality for the empirical and population quantiles in (24).
B.5. Proof for Lemma B.5
Proof. (of Lemma B.5)
18

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
According to Chebyshev's inequality, have that:
- S ) 21 - (c,()()))
P([C.(5.0) Fūy (C.((((
c²
21 E (ūj E (7)))- 21 L3 ([(1-a) + 1)] + () (s 1)1) +1)1) 2 1 8,
2²
(s + 1) +
where the first and last inequality hold due to the Chebyshev's inequality, the second inequality is due to the L-Lipschitz continuous of C. Q2) in Lemma C.3.
Rearranging the above inequality, the following inequality holds with probability at least 1 - 6:
S L- L2- (I(1 - a) + 1)1 () - [[1 ax(( + 1)1) SL L2-22-01// 0(1V3)
(c.(f.g)) -
8 + ()
where the first inequality is due to Assumption 3.1 and Lemma C.3.
B.6. Proof for Lemma B.6
Proof. (of Lemma B.6)
Recall that (1 (s 1) is not an integer. Then we begin to compare the upper and lower bound of [[I-a)(n+]] [[=+))(++1]] respectively: s+1
and
(1 a1+ + 1-a a
- (n + +1]
2 2 < (1 - a) +
(18)
(1 a) < -
a)) + 1)]
1
< -1-a) a) a1
(19)
++1
s+1'
where all inequalities are due to (1 - a) + 1) < - a) + 1)] < (1 a) +1
Due to < n and a E [0, 1]. we have that:
[11 (s) + 1>] [(1 (n + 1)]
2
1
max
a) +
(1 a), (1 a) +
(1
a)
8 +
n
2 n
8 8
n
1
max
n
s s
n
s 011ss).
On the other hand, letting B = [11 a)) + 1)] - (1 (s + 1), the lower bound for
[11 (s) + 1)]
[(1 (n + 1)]
(1 as) + 1)
+ B) - ((1 (11- a) + 2-a
=B 2 N 2(1/s),
s +1
n
s+1
n
where the last inequality is due to the assumption
[(1- + 1)1 (1 - as) + 2(1/8) and 8 S Vn.
C. Proof for Theorem 4.1
Theorem C.I. (Theorem 4.1 restated, learning bound of DPSM) Suppose that Assumption 3.1 holds. For any model f E F, the following inequality holds with probability at least 1 8:
CDM (f. (f)) <OL//T)
Proof. (Proof of Theorem 4.1)
To prove Theorem 4.1, we need the following three technical lemma and defer their proof after proving Theorem 4.1.
19

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Lemma C.2. (Distance between Oj and q' UU) Let of E u(}) arg mingeR [QR( a)-quantile computed by minimizing QR loss. Suppose that Assumption 3.1 holds. Then the following inequality holds with probability at least - 8;
[Q -3
o3 - ÓL//VT).
Lemma C.3. (Lipschitz continuity of 22M (f.()))) 22M
L-Lipschitz continuous in input q with K
Lemma C.A. (Generalization error) Let f X + R and Kn,...KKa be i..d samples dram from an underlying distribution. If there exists M > O such that [f - M for all X E X, then with probability at least - 8, we have
Exif(x)) - Σ f( f(X,)
l2g(2/))
S SMV
2n
1=1
Then we begin to prove Theorem 4.1. Recall [f) = PoM where of eu(f), and define the empirical version of the conformal alignment loss (f)
Ł(f)= = Σ
(X,,) S sa1
=LOM (f, see (4) and (9).
iED vEy
We start with the following triangle inequality:
(F) - Le(f))
Eo(5)+ ((())+((f)) S 2.0M (f.()))))))))) - (f. [C(()) - Co(f)
I.Ilipcchitr, Lemma C.3
<0(1/VT). Lemma C.4
SL
- +0(1//)) S O(1/vm).
{ó(1/vA), Lemma C:2
C.I. Proof for Lemma C.2
Proof. (of Lemma C.2)
In this proof, define (a) E ((()) = arg min,ER (f. We explicitly write the probability 1 - a for our analysis.
First, we prove that oj (ax (l/vm)) < (a) < (f O(g/vn))
Define Z, = f,, S {Q)))) where 1 < i < Thus 7, is Bernoulli random variable. According to the definition of (a),), we have that P(Z,- = 1) a and P(Z: 0} a. Let 2 -= - Z, and E[2] a. According to Chernoff bound, we know
n
S 22exp -E[2)=²/3 -eexp (-n(1 1 -o)="/3)
P
Σ
Σ 2, [12]
-nn(1
By setting 8 = 2 2exp(-1i n1 u))2/3), i.e., /(3log(2/00))((1 - a)))) we have with probability at least 1 - 8:
114 [(() - (1- a) <5(1 a)) (o0 O(4/V/)
(20)
Recall the definition of (7) argmingeR _ (f.g). Then we know the following upper bound and lower bound for
1 0:
1 Σ (1 a) <
n
161 5 (a)),,
(1-a)
[SSr S <gf(a 1/n)).
71
20

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Re-arranging (20) and using the above upper/llwer bounds, with probability least 1 ö, we have
1 1| s { (1-a)(++))
(1 (1- π i=1
1
1 - (1 (1- a)(1 (1- S
1| [y((a)) s - (1 (1 (1-a) + +E)
n
=0/
=a"
1
1
1Spز S af(a' + 1/n1)] S
Σ
1 S (Q((a)) S
1[ S o7(a"))
i=1
aj(a' 1//)+)/n)=0 S Qy(a)= s "j(a").
(21)
Finally, by using the definition of & above, we analyze a' and a" as follows
a' = - (1 (1 e) a s(1 - a) + 3(( - a-) -
(22)
a" = 1 (1- a1 + a -a e(1 a) 3 a))1- -001/V/T))
(23)
Thus, plugging (22) and (23) into (21), we have
0j + O(1/vo) s Qy(a) 2 4j((a ((1/V))
(24)
Next, we prove that [Q((a) (7( s 5(1 from (24):
[(1 (n + 1)] [[1 ((1/ +]]
- gf(( s L2
<((lv\)).
n
7
where the first inequality is due to Assumption 3.1.
C.2. Proof for Lemma C.3
Proof. (of Lemma C.3)
Recall that i[s < 4] = 1+exp( SSgnndd
Define
u Q-S Tagmmad
We start with the gradient of (J q) in q as follows
aCDM (f.
5E i s
Σ
O
(1eexp(-))
Ou = =Σ
exp(
1
dq
dq
du
0g
NEY (1 exp(-u))2 (1))
Tsigmoid
yEY
exp(-
Q-S
Tsiencis
> 0,
(25)
VEv
Sigmoid
(1 + exp(
Tagmana
S
3
where the first inequality is due to exp(x) > 0. Thus, (f, q) is increasing function in input
For each component of the summation in above (25), define h(u) (I+exp(-a)]= then the gradient of h(u) is:
exp(-u]
+ H'(u) = - (1x(-u)((++xp-xx)))) - exp(-u) 2(1 + exp(-u)) (- (-ex((-u))
(1 (1+ exp(-u))
(1 +xxx((--)) exp(-u) -- (x++ex((-u)) + 2(exp(-u)
+ ++ex(p--)))
(1 + exp(-u)) exp(-u) (exp(-u)= -1) (1 + exp(-u))*
(26)
21

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
We take closer look at the value of (u) in (26): when exp(-u) (0, 1), equivalently a have // (((u) >> 0: when exp(-u) (1, +o0), equivalently < O, have N'(u) 0. It means that h(u) increases when 0 and decreases when < 0. Further, when O, we achieve the maximal value of h(u), ie., max,h(u) h(0) = 1/4, or
equivalently [T+pxp( x))² S 1//4.
exp(-w> u)
(2. O in (25) and plugging the above inequality into (25),
(f.a(f.) 0q
Therefore, considering
is bounded as
8q
follows
aLDM OCDM(S. (f.9)
exp(
9-5 Taipredd
Σ
0q
BEY Sigmood
(1 + exp(
Tiigncid
9-8
NEY
Sigmooid
4TSigmoid
Tiigmoid # and | = K. Therefore, Lo(f.g) is L-Lipschitz continuous for input g with 475ggmiid
C.3. Proof for Lemma C.4
Proof. (of Lemma C.4)
Let A = f(X;) with [A,] S M. According to Hoeffding's 's inequality, we have:
P Σ A E[A] 29
) s exp
(-
2nc²
M
By setting 5 = eexp(-2ne) /M2), i.e.,
M /log((2/6))(2 we have the following inequality:
1 ΣA A
1og(2/5)
P
E[A]
< M
2 1 6.
2n
Therefore, with probability at least 1 8, we have
Ex[[(x) 1 Σ ((x)) M
log(2/8)
Ö(1/V)).
n
D. Proofs for Results in Section 4.2
Lemma D.1. (Lemma 4.5 restated, Hölderian ervor bound condition for QR loss) Suppose there is no rie in (S.)a Then, fixing J, the QR loss ZOR (f,4) satisfies Hölderian bound w.r.l. q for 1.
Proof. (of Lemma D.1)
Below we assume f is fixed and let g(g) [J, q). omit the dependence of y f for simplicity of notations. Similarly, we denote the optimal solution set by U = arg gin,g(g) in this proof.
In the following, we consider two cases to prove Lemma D.1.
Case Suppose we have two quantile variables (1, 42 such that q & U, d < 92 E l and ga = arg min,/ - qıll
22

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
the quantile in the optimal set closest 91- Then have
n(g(a)) - g((2)) Σ
(alli S:) - Pra Pra(1,, S:))
i|s: s qil (a(0) - S.) - -a(12 -i) + +1/0 < < aol 00l(1 (1- - -1) - -a(12 - -S:)
+ +1/02 s sil (is((1 (L- 91) -(1 aa(s - -22)
Σ
71
1|5: s ail
- -2))) + 1/1 < < (0l(s S - q1 a(gi - 92)
+ 1/0 s Sil (3 (u- - (11) a)))
(27)
1|5: S 52)a((1 - 42) + 1/22 S Si](1 - () - q1) 1/0 < < <z](S, - -qi)
Σ 1[: S 02/a((1 -2) Σ
1 [02 S 5: a) (1)) + Σ 1an S 92](S: - -n1
i=1
(1 a))(11 (2) a(1 - (g 92) + Σ
1/g < <S: < 92](S - 91)
Σ 14n < < < (S - 41).
(28)
On the other hand, let ñ = Σm= [q] < S; < 92). Denote (1 (1-d) c')m + d' as the weighted average between Φi and q2
with a weight parameter d' (0, 1). Due to that the weighted average between şi and q2 can be always smaller than the average score in the set (S: Q1 S < q2) for sufficiently small c' (0. 1), we have
n
a1 + c - 91) (1 c)g + cc S
Σ
1/a < S, < 9g]s;
+ ū(q + c'(42 91)) v
1mn < < 92](S 91 + 91)
i=1
dñl(g 91) <
1/0 < S < g2](S n) (28)
n(g(9n) - s(92))
1=1
dn (42 - 91) S g((1) g((2).
Recall that 92 = arg min seengrelllll lull qı1l and (42 - q1) = dist(qı.24). Plug it into the above equality, we have
c'n dist(gi,24 U) S 9(q1) - g(g2).
n
Denoting c e= ==/(ñcc)= > 0, then we have
dist(gi, < c(g(q)) - g4),
(29)
which satisfies the HEB condition shown as Definition 4.3 with the exponent v
23

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Case 2. Suppose that v1 E, 41 92 u and Q1 arg ming 92l1- We start from (27) follows
n(g(1)) - s(12)) Σ
||S s qil (a(0) (02)) (2))
en + +a(1 2z) + 1(2 < < rel S (s)ss
+ 1/2 s =S (1)0))(2-911)) -91))
1/s S qı/ar(1 - 42) + 1ln - S:1(1 - a) 21) + 11 < S. < <s](S: (2)
1/ S < <2](S 92).
With the same notation of ñ = Ei=l 1/91 < S < 92), we know that there must exist constant E (0, such that
Q2 c(1 -2) = d' + (1 c')o2 2
Σ 1=1
1/m < S 42]S;
Therefore, we have
g(qi) - g(92) S -c'(ai 92) (2,
Denoting e = =n/(fc) > 0, then we have
dist(g2; S clg(22) ming)u
(30)
By combining (29) and (30), we show that the QR loss satisfies the Hölderian error bound condition with a constant e and an exponent
E. Additional Experimental Setup Details
Dataset and Split. We consider the benchmark datasets C10AR-100 (Krizhevsky et al., 2009), Caltech- 101 (Fei-Fei et al., 2004), and INaturalist (Van Horn et al., 2018). We split the original testing datasets into used calibration and testing datasets. Table 2 summarizes key statistics the used datasets which we elaborate on in the following.
Hyperparameters for training. We set datasets, base models, batch size, training epochs, training parameters (learning rate, learning schedule, momentum, gamma, and weight decay), and À hyperparameter choices. We search for hyperparameters on batch size {64, 128). epochs {30, 40, 60), learning rate (7)) E {0.001, 0.005, 0.01, 0.05, 0.1}, learning rate schedule [2]], [25, 40] Momentum 0.9, weight decay E {0.1, 0.97), and X {0.01, 0.05, 0.1, 0.5, 1.0, 5.0} to select the best combination of hyperparameters of each methods. We also search the learning rate for lower function (?) E {0.0001, 0.001, 0.005, 0.01, 0.05, 0.1, 0.2, 0.5) for DPSM. The hyerparameters employed to get the results presented in the main paper are summarized in Table 3.
Table 2. Description of the data sets are given in the table. "The number of classes in the iNaturalist data set depends on the taxonomy level (e.g.. species, genus, family). We employ"Fungi" species which 341 different categories. Data
Number of Number of Number of Vali-
Number of Cali-
Number of Test
Classes
Training Data
dation Data
bration Data
Data
CIFAR-100
100
45000
5000
3000
7000
Caltech- 101
101
4310
1256
1111
2000
iNaturalist
341#
15345
1705
1410
2000
24

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Table The helow table shows the details used to train our models. We reported the hyperparameters which gives the hest predictive efficiency. We employed SGD optimizer for all training unless specified.
Data
Architecture
Batch size
Epochs
"
Ir schedule
Momentum
weight decay
7
A
DenseNet
64
40
0.1
25
0.9
0.1
0.01
0.05
CIFAR-100
ResNet
128
40
0.1
25
0.9
0.1
0.01
0.01
DenseNet
128
60
0.05
25, 40
0.9
0.1
0.1
1.0
Caltech-101
ResNet
128
60
0.05
25, 40
0.9
0.1
0.05
0.1
DenseNet
128
60
0.001
3
0.9
0.97
0.001
1.0
iNaturalist
ResNet
128
60
0.001
3
0.9
0.97
0.001
0.5
In our study, we primarily apply cross-entropy loss for the classification model. For the ConfTr and DPSM methods, we minimize both the classification loss and the HPS non-conformity score-based predictive inefficiency loss during training. Post-training, we estimate the HPS non-conformal scores using equation 11 for all three methods during calibration and testing. We report the marginal coverage and the prediction set size with the correpsonding mean and standard deviation, with the results presented in Table 4.
HPS - Training, APS - Calibration/Testing. In study, we primarily apply cross-entropy loss for the classification model. For the ConfTr and DPSM methods, we minimize both the classification loss and the differentiable HPS non- conformity score-based inefficiency loss during training. After training, we estimate APS non-conformal scores using equation 12. We calculate the marginal coverage and the prediction set size, with the results presented in Table 5.
HPS Training, RAPS - CalibrationTTesting our study, we primarily apply cross-entropy loss for the classification model. For the ConfTr and DPSM methods, we minimize both the classification loss and the differentiable HPS non- conformity score-based inefficiency loss during training. After training, estimate RAPS non-conformal scores using equation 13. Then, calculate the marginal coverage and the prediction set size, with the results presented in Table 6.
F. Additional Experiments
F1. Additional Experiments for Marginal Coverage
Table HPS Training/Cabbrratiin/eesini calibrated with HPS when a = 0.1. + indicates the pereentage improvement in predictive efficiency compared to the best existing method, whereas denotes percentage decrease in predictive efficiency. All results are the average over different runs, with mean and standard deviation reported. DPSM significantly outperforms almost the best baselines with 20.32% prediction set size reduction across
The APSS on three different datascts with two different deep models trained and
all datasets.
Marginal Coverage
Prediction Set Size
Model
CE
CUT
ConfTr
DPSM
CE
CUT
ConfTr
DPSM
CalTech- 101
DenseNet ResNet
0.90 0.006
0.90 + 0.005
0.90 + 0.008
0.90 0.003
3.50 + 0.10
1.62 + 0.030
4.10 + 0.19
0.90 + 0.003
44.44%)
0.90 0.004
0.90 +: 0.007
0.90 1: 0.006
0.90 0.005
1.57 + 0.018
1.64 +: 0.049
1.52 0.040
0.91 :: 0.005
44.51%)
CIFAR- 100
DenseNet ResNet
0.90
0.007
0.90 +: 0.009
0.90 + 0.007
0.90
0.006
2.59 = 0.053
2.27 + 0.09
2.28 1 0.07
2.17
0.086 (L 4.82%)
0.90 0.006
0.90 + 0.005
0.90 + 0.007
0.90 0.007
3.39 + 0.10
3.01 # 0.11
3.77 + 0.14
2.94 0.08 () 2.32%)
iNaturalist
DenseNet
0.90 + 0.009
0.90 + 0.011
0.90 + 0.011
0.90
0.008
94.58 + 3.45
77.13 + 3.72
79.93 + 3.70
61.22
2.49 (L 20.63%)
ResNet
0.90 + 0.019
0.90 + 0.007
0.90 + 0.012
0.90 0.008
99.48
8.95
73.09 + 2.00
76.73 + 3.87
70.04 + 1.99 (L 4.1%%
DPSM generates smaller prediction sets. Table 4 presents the set sizes and coverage rates for different methods using HPS score across training, calibration, and testing phases. DPSM outperforms all existing baselines with 20.32% reduction in terms of prediction set size across all datasets. Table 5 presents the set sizes and coverage rates for different methods using HPS for training and APS for calibrating. DPSM outperforms nearly all existing baselines with 20.61% % reduction in terms of prediction set size across all datasets, except 1 8.71% increase on CIFAR- 100 with DenseNet and f 0.54% increase on iNaturalist with ResNet in terms of prediction set size. Table presents the set sizes and coverage rates for different methods
25

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
Table HPS - Training, APS Calibration/Testing: The APSS on three different datasets with two different deep models trained with HPS and calibrated with APS when a = 0.1. L indicates the percentage improvement in predictive efficiency compared to the best existing method, whereas t denotes a percentage decrease in predictive efficiency. All results are the average over different runs, with the mean and standard deviation reported. DPSM significantly outperforms almost the best baselines with 20.61% % prediction set size reduction across datasets.
Marginal Coverage
Prediction Set Size
Model
CF
CUT
ConfTr
DPSM
CR
CUT
ConfTr
DPSM
CalTech- 101
DenseNet
0.90 +: 0.006
0,90 + 0.007
0.90 +: 0.008
0,90 + 0.005
8.44 1 0.15
3.87 = 0.11
8.64
0.21
1.58 +: 0,022 (1 59.17%)
ResNet
0.90 + 0.006
0.90 + 0.004
0.90 + 0.007
0.90 + 0.005
4.50 + 0.059
4.59 + 0.072
3.61 0.08
1.74 + 0.031 (L (1.86)
CIFAR-100
DenseNet
0.90 + 0.007
0.90 + 0.009
0.90 + 0.008
0.90 + 0.006
3.38 + 0.12 3.98 +0.13
2,41 = 0.11
3.08 0.11
2.64 + 0.86 (1 8.71%) 3.53 + 0.11 () 7.35%)
ResNet
0.90 + 0.006
0.90 + 0.11
0.90 + 0.007
0.90 + 0.007
3.81 + 0.08
4.90 0.18
iNaturalist
DenseNet
0.90 + 0.009
0.90 + 0.010
0.90 + 0.011
0.90 + 0.010
101.97 + 3.16
88,93 + 3.06
90.79 + 3.17
75.98 +: 2.99 (L 14.56%)
ResNet
0.90 + 0.013
0.90 + 0.006
0.90 + 0.012
0.90 + 0.009
95.81 3.80
79.00 + 2.21
88.70 + 3.88
79.43 + 2.39 (f -0,54%)
Table 6. HPS- - Training, RAPS - Calibration/Testingg The APSS on three different datasets with two different deep models trained with HPS and calibrated with RAPS when a 0.1, where ARAPS = 0.01 and lngg = 5. indicates the percentage improvement in predictive efficiency compared to the best existing method, whereas denotes a percentage decrease in predictive efficiency. All results are the average over 10 different runs, with the mean and standard deviation reported. DPSM significantly outperforms almost the best baselines with 19.04% prediction set size reduction across all datasets.
Marginal Coverage
Prediction Set Size
Model
CF
CUT
ConfTr
DPSM
CF
CUT
ConfTr
DPSM
CalTech- 101
DenseNet ResNet
0.90 0.007
0.90 1 0.008
0.90 + 0.009
0.90
0.006
6.58 1 0.12
3.53 0.11
6.88 0.17
1.50 1 0.020
57.51%)
0.90 0.005
0.90 + 0.004
0.90 +: 0.007
0.90 0.004
3.89 + 0.047
3.98 0.59
3.19 1 0.69
1.67 1 0.025 (1 47.65%)
CIFAR- 100
DenseNet ResNet
0.90 = 0.007
0.90 + 0.007
0.90 + 0.006
0.90 + 0.006
2.73 = 0.043
2.14 0.55
2.69 + 0.053
2.34 + 0.035 (1 8.55%)
0.90 0.006
0.90 + 0.11
0.90 + 0.007
0.90 0.007
3.25 + 0.14
2.93 0.60
4.02 + 0.11
2.93 + 0.05
iNaturalist
DenseNet
0.90 1 0.013
0.90 1 0.008
0,90 1 0.015
0.90
0.008
97.27 1 4.23
82,88
1 2,47
86.77 1 6.17
68.17
2.18 (U 17.74%) 76.81 1: 2.68 (1 0.08%)
ResNet
0.90 0.012
0.90 1 0.011
0.90 1 0.015
0.90 0.009
97.43 1 4.17
76.75 1 4.47
81.18 1 4.93
using HPS for training and RAPS for calibrating. DPSM outperforms existing baselines on several datasets, achieving a 19.04% reduction in prediction set size across all datasets, except for CIFAR-100. On iNaturalist with ResNet, shows a marginal 0.08% increase in prediction set size. Combined with above three tables, DPSM improve the predictive efficiency with 19.99% reduction in term of prediction set size across all settings and all datasets. We also visualize the coverage rate and APSS with confidence intervals of all methods using DenseNet and HPS score in Figure 5. It clearly confirms that DPSM achieves significantly smaller prediction set size while maintaining the valid coverage.
DPSM converges to stable error for bilevel optimization. To further explore how DPSM effectively generates smaller prediction sets, we analyze the convergence of DPSM by plotting the loss of the upper level function (i.e., a combination of classification loss and conformal alignment loss) and the lower level function (i.e., QR loss) over training 100 epochs with ResNet model. Figure 6 (a) and (b) show the upper-level loss and lower-level loss over epochs, respectively. We also report the results of 40-epoch training regime in Figure 7 and 8 for reference. As shown, the upper-level loss of DPSM exhibits an initial increase during the first 2 epochs, reaching the peak, then steadily decreases before stabilizing around epoch 35. In contrast, the lower-level loss decreases sharply within the first 2 epochs, followed by gradual reduction until convergence near the end of training. These results empirically demonstrate that DPSM effectively converges in terms of both upper and lower level training errors, validating its bilevel optimization approach. To investigate how the learned quantiles influence the optimization error, we compute both conformal and QR losses using the learned quantiles and the optimal (dataset-level) quantiles. The corresponding optimization errors defined as the loss differences between learned
26

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Caltech-101
(b) CIFAR-I00
(c) iNaturalist
0.910
0.915
0.93
0.910
0.92
Coverage
0.905
50.905
0.991
0.900
Covero
0.900
0.90
0.89
0.895
0.895
0.88
0.890
0.87
0.890
0.86
CE
ConfTr CUT
DPSM
CE
ConfTr CUT
DPSM
CE
ConfTr
CUT
DPSM
Method
Method
Method
4.0
110
Average size
3.8
Average size
100
3.6
3.4
90
3.2
3.0
1.0
70
CE
ConfTr CUT
DPSM
CE
ConfTr CUT
DPSM
CE
ConfTr
CUT
DPSM
Method
Method
Method
Figure 5. Box plots of coverage (Top row) and APSS (Bottom row) of all methods using ResNet and HPS score.
DPSM achieves
significantly smaller prediction set size while maintaining the valid coverage.
(a) Upper loss
(b) Lower loss
(c) Conformal loss
(d) QR loss optimization gap
3.00
0.12
Lower_loss
optimization gap
0.0030
0.0035
2.50
8 2.75
Upper_ [ppse_loss
Lower
0.08
0.10
Conformel Ogt Geo
0.33
0.4
00.0025
30.0015
0.0020
2.00
0.06
00.0100
0.2
1.75
0.04
0.0005
1.50
0.02
0.0000
20
40
80
100
20
60 Epochs
40
80
100
20
40
100
0.0
Epochs
Epochs
Epochs
Figure 6. Justification experiments for the convergence DPSM CIFAR- using ResNet and HPS score. (a) Upper level loss (i.e., a combination of classification loss and conformal alignment loss); (b) Lower level loss (i.e., QR loss): (c) Optimization gap of conformal loss, defined the difference between conformal losses using learned batch-level quantiles and dataset-level quantiles on the training set; (d) Optimization gap of the lower-level QR loss, defined similarly the loss difference hetween learned batch-level quantiles dataset-level quantiles.
and optimal quantiles are visualized in Figure 6 (c) and (d). Both errors converge to nearly 0, indicating that the learned quantiles effectively approximate the optimal quantiles over training.
DPSM estimates empirical quantiles with small error. To compare the precision of empirical quantiles estimation in ConfTr and DPSM, we plot the estimation error between Q7 (quantiles evaluated on the whole training dataset) and T (quantiles evaluated in ConfTr learned in DPSM mini-batches) with ResNet. Figure 9 (a) plots this estimation error training epochs. For the first 25 epochs, the estimation errors for DPSM significantly larger compared to ConfTr. However, as the training progresses, the estimation errors for DPSM decrease rapidly, converging close to 0 after epoch 32. This result verifies the theoretical result for smaller estimation eπrоr in learning bound analysis from Theorem 4.1. Furthermore, the rapid reduction in estimation error also reflects the convergence of the lower loss (i.e., QR loss), highlighting the effectiveness DPSM accurately estimating quantiles.
Learning bound of DPSM is much tighter than ConfTr. To approximately compare the learning bounds of DPSM and ConfTr, compare the conformal alignment losses of ConfTr and DPSM during training terms of the average soft set size, as shown in Figure 9 (b). The soft set size of DPSM is consistently smaller than that of ConfTr during training. Combining the empirical results of the smaller estimation error of quantiles from Figure 9 (a), we can conclude that the learning bound of DPSM is much tighter than the learning bound of ConiTr, providing the empirical verification of Theorem 4.1 and 3.5. Although learning bound cannot be empirically computed, we approximate it using a common strategy in ML literature (Yuan al.. 2019; Yang et al., 2021b), which estimates generalization error by the absolute gap between training and test errors. For CP, we use APSS evaluated on train and test sets to approximate the learning errors. Specifically, for
27

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Upper loss
(b) Lower loss
(c) Est. error of quantiles
(d) Average soft set size
5.5
1os5
Upper_los llss__sss____
0.12
0.10
Lower_loss
estimation
0.8
47.5
45.0
4.5
0.6
42.5
4.0
00.08
0.06
0.4
DPSM
ConfTr
M 40.0
t 37.5
3.3.5
0.04
81 32.5
35.0
DPSM
3.0
0.02
0.0
30.0
27.5
ConfTr
0
10 15 20 25 35 Epochs
40
5 10 15 20 25 30 Epochs
35
40
0
5
10 15 20 25 30
35 40
0
5 10 15 20 25 30 35 40 Epochs
Epochs
Figure 7. Justification experiments for effectiveness of DPSM trained with 40 epochs on CIFAR- 100 using DenseNet and HPS score. (a) Upper level loss (i.e., combination of classification loss and conformal alignment loss) in DPSM; (b) Lower level loss (i.c., QR loss) in DPSM; (c) Estimation error between the Q7 (quantiles evaluated on the whole training data) and ō (quantiles evaluated in ConfTr or learned in DPSM on mini- bini-batches); and (d) Average soft set size DPSM and ConfTr (using Sigmoid function).
(a) Upper loss
(b) Lower loss
(c) Estimation error of quantiles
(d) Average soft set size
2.8
3.0
0.12
Lower_los loss
0.8
0.7
2.6
0.10
60.6
45.0
0 2.2
12.4
Upper loss
10.08
0.0
0.4
DPSM
44.55
40.0
2.2
0.3
ConfTr
518
1.6
0.04
0.0
0.1
5
35.0
32.5
30.0
Confii/
DPSM
0 5 10 15 20 25 30 35 Epochs
40
5 10 15 20 25 30 35 40 Epochs
10 15 20 25 30 35 40 Epochs
20
Epochs
Figure 8. Justification experiments for effectiveness of DPSM trained with 40 epochs CIFAR-100 using ResNet and HPS score. (a) Upper level loss (i.c., a combination of classification loss and conformal alignment loss) DPSM; (b) Lower level loss (i.c., QR loss) DPSM: (c): Estimation error between the Q7 (quantiles evaluated the whole training data) and दΙ (quantiles evaluated in ConfTr
learned in DPSM on mini- mini-batches); and (d): Average soft set size of DPSM and ConfTr.
Estimation error of quantiles
(b) Average soft set size
(c) Learning bound approximation
Quantile estimation errc
0.8
abs(train APSS test APSSI
5
0.7
DPSM
47.5
45.0
4
DPSM
0.6
ConfTr
2 42.5
ConfTr
0.5
Sn 40.0
DPSM
2 3
0.4
37.5
ConfTr
0.3
35.0
0.2
32.5
1
0.1
30.0
0.0
O
10
20
30
40
50
60
0
10
20
30
40
50 60
10 15 20 25 30 35 40 45 50 55 60 Epochs
Epochs
Epochs
Figure 9. Justification experiments for the learning bound of DPSM CIFAR- 100 using ResNet and HPS score. (a) Estimation error between the Q7 (dataset-level quantiles on training data) and q5 (batch-level quantiles evaluated in CoufTr or learned in DPSM): (b) Average soft size of DPSM and ConfTr (using Sigmoid function); (c) Approximated learning comparison between DPSM and ConfTr, measured by their gaps between the training and testing APSS.
DPSM, at each iteration, we: (i) compute APSS on the training set using the learned quantiles as thresholds. It includes optimization error since the learned quantiles are not optimal (true lataset-level quantiles): (ii) compute the APSS on testing set using the dataset-level quantiles as thresholds. The gap between these two APSS values is employed as an approximation of the learning bound. We apply the same strategy to the SA-based ConfTr, where the training APSS is computed using the quantiles evaluated on mini-batches from the training data, and the test APSS is computed using the dataset-level quantiles from the test data. This comparison is shown in Figure 9 (c), which demonstrates that the approximated learning error is improved by DPSM.
Assumption 3.1 is empirically valid. Figure 10 (a) illustrates the conformity scores plotted against their corresponding normalized order. The x-axis represents the normalized order, while the y-axis represents conformity scores. From this figure, is clear that the curve does not remain near the x-axis or y-axis, indicating that the gradient of conformity scores
28

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Bi-Lipschitz continuity of conformity score
(b) Strongly concavity of conformal loss
Conformity mitt Score
1.0
Conformal Loss
50
Zoom-In
0.8
45
40
0.6
40
0.4
35
0.2
30
$8.50
0.85
0.90
0.95
0.0
25
0.0
0.2
0.4 0.6 0.8 1.0
0.0
0.2
0.4
0.6
0.8
1.0
Normalized Order
Coverage Rate
Figure 10. Verification studies on CIFAR-100 100 with ResNet model using HPS scoring function calibration dataset. (a): HPS scores over corresponding normalized order produced by ConfTr. The x-axis is normalized order. the y-axis is the corresponding conformity score; (b): The soft set size measure of ConfTr. The input coverage rate is from [0.02, 0.98] with 0.02 range with its zoom-in version where a is close to target coverage 0.9; When coverage rate close to 0.9, the curve soft set size exhibits a concave shape.
Table The WSC (f hetter), SSCV (4 better) and CovGap (1 hetter) of all methods CIFAR-100 with HPS score: The best results are in bold. These results show that DPSM achieves the best performance for class-conditional coverage (the smallest CovGap). For size-stratified coverage (SSCV), DPSM a worse measure compared with CE and CUT, but is better than ConfTr. For WSC, CUT and DPSM have comparable performance.
DenseNet
ResNet
Mcasures
CB
CUT
ConfTr
DPSM
CE
CUT
ConfTr
DPSM
WSC
0.88 + 0.016
0.90 + 0.022
0.88 + 0.018
0.89 = 0.011
0.88 0.012
0.88 0.020
0.88 + 0.020
0.89 = 0.019
SSCV
0.12 = 0.024
0.09 + 0.019
0.21 + 0,061
0.17 = 0.034
0.09 + 0.018
0.11 = 0.017
0.14 + 0.022
0.12 = 0.019
CovGap
4.54 0.49
5.20 0.29
4.56 + 0.28
4.43 + 0.41
4.71 + 0.38
4.71 0.32
4.70 0.34
4.69 0.26
with respect to normalized index is both upper and lower bounded. This observation empirically supports the validity of Assumption 3.1.
Assumption 3.2 is empirically valid. Figure 10 (b) visualizes the soft set size of ConfTr, with input coverage rate [0.02, 0.98] with range 0.02. When coverage rate approaches 0.9, the curves of all methods exhibit concave shape (zoom-in version also shown), providing empirical verification for Assumption 3.2.
E22 Additional Experiments for Conditional Coverage
DPSM achieves comparable conditional coverage performance and strong class-conditional coverage performance compared to baselines. To evaluate the impact of prediction set size reduction the conditional coverage performance of DPSM, we report three metrics CIFAR- 100 using the HPS score in Table 7: (i) WSC (Worst-Slab Coverage, 1 better), introduced in (Romano et al., 2020); (ii) SSCV (Size-Stratified Coverage, + better), from (Angelopoulos et al., 2021) )); and (iii) CovGap (Average Class Coverage Gap, | better), proposed in (Ding et al., 2024) to measure class-conditional coverage. The results show that DPSM achieves the best class-conditional coverage, reflected by the lowest CovGap. For SSCV, DPSM performs slightly worse than CE and CUT, but better than ConfTr. In terms of WSC, DPSM and CUT achieve comparable performance. We further visualize the distribution of class-conditional coverage and class-wise average prediction set size in Figure 11 and 12, providing ine-grained insights into class-conditional performance. DPSM demonstrates slightly more concentrated class-wiss wise coverage and generally smaller class-win wise prediction set sizes.
29

---

Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
(a) Class-wise coverage and size
(b) Class-wise coverage and size
(c) Class-wise coverage and size
(DPSM vs CE)
(DPSM vs CUT)
(DPSM vs Conftr)
12.0
Method
20.0
Method
Method
10.0
CE
17.5
CUT
10.0
ConfTr
Frequency
DPSM
~15.
DPSM
Frequency
8.0
DPSM
8.0
FrequE
12.5
6.0
10.0
6.0
4.0
7.5
5.0
2.0
2.5
2.0
00.70
0
0.
0.78
2.57
Class Conditional Coverage
Class Conditional Coverage
Class-wise Set Size
Method
Method
Method
12.0
CE
50.0
CUT
10.0
ConfTr
Frequency
10.0
DPSM
Frequency
44..0
DPSM
Frequency
8.0
8.0
30.0
6.0
6.0
20.0
4.0
2.0
10.0
2.0
0..8
0
0
2.73
4.27
7.35
15.68 Class-wise Set Size
6.02
10.85
20.51
2.57
5.35
6.74
Class-wise Set Size
Class-wise Set Size
Figure 11. Class conditional coverage and class-wise prediction set size of all methods CIFAR-100 with DenseNet and HPS. To better compare the class conditional coverage, we compare the class-conditional coverage between DPSM baselines (a), (b) and (c) separately. DPSM shows bit more concentration in terms of class coverage to the nominal coverage (90%) and smaller prediction set size.
(a) Class-wise coverage and size
(b) Class-wise coverage and size
(c) Class coverage and size
(DPSM vs CE)
(DPSM vs CUT)
(DPSM vs Conftr)
Method
12.0
Method
Method
CE
CUT
12.0
ConfTr
DPSM
DPSM
DPSM
Frequency
8.0
Frequency
8.0
Frequency
8.0
6.0
6.0
6.0
4.0
4.0
4.0
2.0
2.0
2.0
0,8.7
0.79
0.86
0.93
1.00
0
0.79
0.86
0.93
1.00
0.0
0.79
0.86
0.93
1.00
Class Conditional Coverage
Class Conditional Coverage
Class Conditional Coverage
Method
10.0
Method
Method
CE
CUT
12.0
ConfTr
Frequency
8.0
DPSM
Frequency
8.0
DPSM
Frequency
10.0
DPSM
6.0
8.0
6.0
6.0
4.0
4.0
4.0
2.0
2.0
2.0
0.0.54
0.P.50
0.0
3.53
5.51
7.50
9.49
3.38
5.25
7.12
9.00
4.17
6.89
9.51
12.33
Class-wise Set Size
Class-wise Set Size
Class-wise Set Size
Figure 12. Class conditional coverage and class-wise prediction set size of all methods CIFAR-ION 100 with ResNet and HPS. To better compare the class conditional coverage, we compare the class-conditional coverage hetween DPSM and baselines in (a), (b) and (c) separately. DPSM shows bit concentration terms of class-wise coverage the nominal coverage (90%) and smaller prediction set size.
30


Reviews:
[{"review_id": "fhbSP4ymie", "reviewer": "Reviewer_j13f", "summary": "This paper proposed a new method, called DPSM, for minimizing the size of the prediction set for conformal prediction (CP) via bi-level optimization. The main idea is to reformulate the quantile estimation in CP into an optimization problem, such that it can be treated as a lower-level optimization, while the set size minimization as the upper-level one. The authors claimed and theoretically showed that such a formulation can improve the learning bound of previous methods that are also devoted to minimizing the prediction set's size. Experimental results demonstrate the effectiveness of the proposed method, that it reduces the average size of the prediction sets over existing methods in most cases.\n\n## update after rebuttal\nI would keep my initial rating after reading the authors' responses.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review. We provide an **external PDF** [(click this link to access)](https://anonymousicml.tiiny.site) to present the empirical results needed to answer some of your questions.\n\n**Q1: Learning bound not empirically tested? Questionable if achievable due to optimization approximation?**\n\nA1. 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:\n\n1) 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);\n\n2) compute $APSS^{te}(f_t,q^{te}(f_t))$ on testing data, where $q^{te}(f_t)$ is the true quantile\n\nThen 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.\nWe 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.\n\n**Opt. approximation**: We showed the convergence of losses and est. error of learned quantile empirically in Fig 1(a)-(c) of original paper. \nTo 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\n\n**Q2: Why can DPSM achieve much better learning bound as SA is also adopted?**\n\nA2: DPSM mainly differs from the SA-based method in how the quantile is instantiated\n\n**DPSM**: the quantile is a learnable parameter in lower-level QR\n\n**SA-based**: uses batch-level quantile at each iteration\n\nAlthough 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).\nInstead, 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 \n\n**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.**\n\nA3: 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.\n\n**Q4: The algorithm did not sufficiently converge with 40 epochs.**\n\nA4: 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**. \n\n**Q5: Verify assumption with other conformity scores.**\n\nA5: We originally selected HPS score to verify assumptions following the  recent conformal training literature [r6]. \n\nWe 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.\n\n[r1] Mohri, et al. Foundations of machine learning. MIT press 2018\n\n[r2] Yang, et al. Exact gap between generalization error and uniform convergence in random feature models. ICML 2021\n\n[r3] Yuan, et al. Stagewise Training Accelerates Convergence of Testing Error Over SGD. NeurIPS 2019\n\n[r4] Emami, et al. Generalization error of generalized linear models in high dimensions. International conference on machine learning. ICML 2020\n\n[r5] Velikanov, et al. Generalization error of spectral algorithms. ICLR 2024\n\n[r6] Sharma, et al. PAC-Bayes generalization certificates for learned inductive conformal prediction. NeurIPS 2023", "claims_and_evidence": "The main claim by the authors is that the proposed DPSM has better learning bound with respect to sample complexity than existing methods, which is theoretically verified. Experiments also demonstrate the effectiveness of DPSM. However, a concern is that the learning bound was not empirically tested. Due to the approximation in the optimization, it is a little questionable that the theoretical bound can be indeed achieved.", "methods_and_evaluation_criteria": "Since the proposed method focuses on the prediction set's size, the average prediction set's size is directly used as the performance measure, which is reasonable.\n\nFor the method itself, the motivation is clear, and the theoretical results seem good (though I haven't checked the proofs in detail). However, I am a little confused that, since the stochastic approximation is also adopted in DPSM implementation for optimizing the quantile as that in SA-based methods, why it can achieve much better learning bound.", "theoretical_claims": "I haven't checked all the details of the proofs, but I have a concern about the proof for Theorem 3.5. Specifically, I notice that the proof for Theorem 3.5 relies on some properties of Beta distribution, which are only available in the asymptotic sense according to Proposition 3.4.", "experimental_designs_or_analyses": "The overall experimental designs and analyses are promising. A small issue:\n\n- In Figures 1 and 3, it seems that the algorithm did not sufficiently converge with 40 epochs. So, I suggest more iterations.", "relation_to_broader_scientific_literature": "The existing SA-based conformal training methods [1, 2] compute the empirical batch-level quantile during each training iteration. The proposed DPSM tries to improve the theoretical learning bound and practical effectiveness by a bi-level optimization-based formulation.\n\n[1] Stutz, D., Cemgil, A. T., Doucet, A., et al. Learning optimal conformal classifiers. arXiv preprint arXiv:2110.09192,2021.\n\n[2] Einbinder, B.-S., Romano, Y., Sesia, M., and Zhou, Y. Training uncertainty-aware classifiers with conformalized deep learning. Advances in Neural Information Processing Systems, 35:22380–22395, 2022.", "essential_references_not_discussed": "Related references have been properly cited and discussed.", "other_strengths_and_weaknesses": "Strength:\n\n- The bi-level optimization for conformal training is new and inspirative.\n\n- Theoretical analysis is provided to support the reasonability of the proposed method.\n\n- Experimental results are promising.\n\nWeakness:\n\n- The gap between the theory and implementation of the proposed method was not discussed.", "other_comments_or_suggestions": "- In the caption of Table 3, \"above\" should be \"below\".\n\n- Figure 4 shows the assumption verification using different networks but the same conformity score, compared with that in Figure 2. I suggest trying other conformity scores.", "questions_for_authors": "No further questions.", "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": "N8b9oAz2KU", "reviewer": "Reviewer_aEdV", "summary": "This paper introduces the Direct Prediction Set Minimization (DPSM) algorithm, a novel bilevel optimization approach that minimizes prediction set sizes in conformal classifier training with a learning bound of $O(1/\\sqrt{n})$, surpassing prior methods limited by $\\Omega(1/s)$. Experimental results on benchmark datasets demonstrate a significant 20.46% reduction in prediction set size compared to the best baselines, validating its theoretical and practical effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review. We provide an **external PDF** [(click this link to access)](https://anonymousicml.tiiny.site/) to present the empirical results needed to answer some of your questions.\n\n**Q1: Assessing the score function with fixed hyper-parameter settings provides little insight.**\n\nA1: 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].\nSpecifically, 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. \n\nTo 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.\n\n| Methods | CE | CUT | ConfTr | **DPSM** |\n|----|------|-------|--|----|\n| DenseNet |$2.73\\pm 0.043$|$2.14 \\pm 0.055$|$2.69 \\pm 0.053$|$2.34 \\pm 0.055$|\n| ResNet     |$3.25\\pm 0.14$|$2.93 \\pm 0.60$|$4.02 \\pm 0.11$|$2.93 \\pm 0.05$|\n\nThese 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.\n\n**Q2: Including conditional coverage metrics such as WSC, SSCV, or CovGap is essential.**\n\nA2: 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:\n\n| Mesures | CE   |  CUT | ConfTr  | **DPSM** |\n|------|--------|---------|----------|-------------|\n| WSC      |$0.88\\pm 0.016$|$0.90\\pm 0.022$|$0.88\\pm 0.018$|$0.89\\pm 0.011$|\n| SSCV     |$0.12\\pm 0.024$|$0.09\\pm 0.019$|$0.21\\pm 0.061$|$0.17\\pm 0.034$| \n| CovGap  |$4.54 \\pm 0.49$|$5.20 \\pm 0.29$  |$4.56 \\pm 0.28$ |$4.43 \\pm 0.41$ |  \n\nThese 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.\nFor WSC, CUT and DPSM have comparable performance.\n\n**Visualized class-conditional coverage and prediction set size**\n\nWe 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.\n\n**Q3: The authors should report model accuracy across different loss functions.**\n\nA3: 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:\n\n| Methods   | CE   |  CUT   | ConfTr   | **DPSM**  |\n|---------|---------|---------|-----------|------------|\n| DenseNet |$0.775\\pm 0.006$|$0.752 \\pm 0.006$|$0.739 \\pm 0.006$|$0.751 \\pm 0.005$|\n| ResNet     |$0.739\\pm 0.005$|$0.701 \\pm 0.004$|$0.648 \\pm 0.004$|$0.699 \\pm 0.005$|\n\nThese 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.\n\n[r1] Ding, et al. Class-conditional conformal prediction with many classes. NeurIPS 2023\n\n[r2] Tawachi, et al. Multi-dimensional conformal prediction. ICLR 2025\n\n[r3] Correia, et al. An information theoretic perspective on conformal prediction. NeurIPS 2024.\n\n[r4] Lu, et al. Federated conformal predictors for distributed uncertainty quantification. ICML 2023.\n\n[r5] Angelopoulos, et al. Uncertainty Sets for Image Classifiers using Conformal Prediction. ICLR 2021", "claims_and_evidence": "1. DPSM is a novel conformal training algorithm using bilevel optimization to minimize prediction set size.\n2. The proposed method is theoretically robust, as the authors provide comprehensive theoretical analysis and an upper bound on the learning error.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The theoretical analysis is interesting and solid. The bilevel approach and pinball loss integration make it intriguing, while rigorous proofs and clear assumptions ensure solidity.", "experimental_designs_or_analyses": "1. Assessing the score function with fixed hyper-parameter settings provides little insight; a parameter-tuning approach would more effectively demonstrate DPSM's advantages.\n2. Including conditional coverage metrics such as WSC, SSCV, or CovGap is essential to evaluate how DPSM’s set size reduction affects conditional coverage.\n3. The authors should report model accuracy across different loss functions, as higher accuracy, which significantly influences set size, could result in smaller prediction sets and needs to be documented.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "E249an40vY", "reviewer": "Reviewer_yHxc", "summary": "This paper introduces a novel training strategy for deep classifiers, leveraging insights from conformal prediction. Specifically, it proposes a new training loss function that is formulated as the sum of two components: a conventional loss function—aiming to enhance predictive accuracy—and a (regularized) conformal alignment loss designed to reduce the size of the conformal prediction set.\n\nCompared to the existing work [1], which had the same idea but calculated the conformal alignment loss using minibatch data and an empirical quantile derived from the minibatch, this work parameterize the quantile as a variable and propose a simultaneous optimization of both the model weights and the quantile. This is achieved by formulating the problem as a bilevel optimization task: at the upper level, the objective is to minimize the sum of the conventional loss and the conformal alignment loss, while at the lower level, the goal is to estimate the $(1-\\alpha)$-th quantile of the nonconformity score distribution. The authors demonstrate that, under certain assumptions, their proposed conformal alignment loss—parameterized by both the model and the quantile—achieves an improved learning bound for the conformal alignment loss. Specifically, they achieve an $O(1/\\sqrt{n})$ upper bound, where $n$ is the training sample size, while the existing works [1,2] only achieve an upper bound of $O(1/\\sqrt{b})$, where $b<<n$ represents the minibatch sample size.\n\n[1] \"Learning Optimal Conformal Classifiers\", Stutz et. al., 2022.\n[2] \"Training Uncertainty-Aware Classifiers with Conformalized Deep Learning\", Einbinder et. al., 2022.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review. We provide an **external PDF** [(click this link to access)](https://anonymousicml.tiiny.site) to present the empirical results\n\n**Q1: Evaluation: No conditional coverage**\n\nA1: Please refer to A2 for Reviewer aEdV and **Fig 4 in external PDF** for updated conditional coverage measures. DPSM shows improved class-conditional coverage\n\n**Q2. Minimizing average prediction set size (APSS): motivation not convincing since:**\n\n1\\) it is a secondary advantage of conformal training. The primary objective is adaptive prediction sets to hardness and conditional coverage across heterogeneous data;\n\n2\\) 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\n\nA2: **1) Predictive efficiency is one of the primary desiderata in CP, rather than a secondary advantage**\n\nFor practitioners, smaller prediction sets of CP are found practically useful to improve downstream decision making from humans [r1, r2].\nTherefore, 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].\nTherefore, it is a central and practically important goal.\nDPSM 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\n\n**Clarification: DPSM can also be used for conditional coverage.**\nThe 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\n\n**2) Small prediction sets for easy inputs and empty sets for difficult ones are informative and practically useful**\n\nUnder 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\n\n**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)**\n\nA3: 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\n\n**Q4: Why is $\\hat \\ell (f,q)$ defined over all training samples rather than batch?**\n\nA4: **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)\n\n**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?**\n\nA5: 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.\nIt is analogous to applying SGD to optimize a loss defined over all training samples: iterative SGD update can train the deep model to convergence\n\nWe clarify that $D_1$ is employed to train classification loss and QR loss, rather than conformal loss.\nData split helps prevent overfitting and has been in the conformal training literature (see [r9]).\n\n[r1] Conformal Prediction Sets Improve Human Decision Making. ICML 2024\n\n[r2] On the Utility of Prediction Sets in Human-AI Teams. IJCAI 2022\n\n[r3] Uncertainty sets for image classifiers using conformal prediction. ICLR 2021\n\n[r4] Conformal Prediction for Deep Classifier via Label Ranking. ICML 2024\n\n[r5] The Pitfalls and Promise of Conformal Inference Under Adversarial Attacks. ICML 2024\n\n[r6] Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training. AAAI 2025\n\n[r7] Large language model validity via enhanced conformal prediction methods. NeurIPS 2024\n\n[r8] Conformal language modeling. ICLR 2024\n\n[r9] Training uncertainty-aware classifiers with conformalized deep learning. NeurIPS 2022", "claims_and_evidence": "The authors assert that (1) the proposed algorithm achieves an improved learning bound compared to existing methods, and (2) their approach empirically results in smaller conformal prediction set sizes. Both claims are substantiated through theoretical justifications and empirical evidence from numerical experiments.", "methods_and_evaluation_criteria": "The datasets used for evaluating their proposed method and the benchmark methods selected for comparison are appropriate.\n\nRegarding the evaluation criteria, the authors employ marginal coverage and average set size, both of which are standard metrics in the conformal prediction literature. However, this paper does not evaluate conditional coverage, which may be essential for fully assessing the improvements of an uncertainty-aware classifier trained with the proposed loss function. A more detailed discussion on this point can be found in the Other Strengths and Weaknesses section.", "theoretical_claims": "Yes, I have reviewed the proof of Theorem 4.1 and did not notice any apparent issues.", "experimental_designs_or_analyses": "Yes, I have reviewed the experimental setup in Section 5.1 and the corresponding analysis in Section 5.2.", "relation_to_broader_scientific_literature": "The key contribution of this paper is the introduction of a training loss function that explicitly incorporates the objective of reducing conformal prediction set sizes. The innovation lies in the use of a bi-level optimization framework, which jointly learns both the model and the quantile of nonconformity scores. However, the primary motivation of consistently favoring smaller prediction sets may limit the practical utility and broader significance of the approach, as discussed in detail in the weaknesses section.", "essential_references_not_discussed": "To the best of my knowledge, the most relevant works essential for understanding the paper’s key contribution have been appropriately cited.", "other_strengths_and_weaknesses": "Strengths: \nThe paper is generally well-organized and well-structured. The main message and key contributions of this work are clearly articulated and easy to follow.  \nThe idea of simultaneously optimizing the quantile and model weights in the conformal alignment loss is novel. \n\nWeaknesses: \nOne of my primary concerns regarding this work is the underlying motivation—specifically, the emphasis on minimizing the prediction set size as the main objective, irrespective of the characteristics of the underlying data. In uncertainty quantification, the goal is to accurately capture and represent the uncertainty associated with predictions. However, reducing the prediction set size alone does not necessarily equate to improved uncertainty quantification. For example, in practical scenarios, datasets often contain a mix of both easy-to-classify and hard-to-classify samples. Ideally, an uncertainty quantification method should be able to distinguish between these cases—producing small prediction sets for easy samples while allowing larger prediction sets for more challenging samples to reflect their inherent difficulty. Prioritizing the minimization of prediction set size across the board may not align with this fundamental principle. For instance, if 90% of the data consists of easy samples while the remaining 10% are difficult, one could achieve a very low average prediction set size by assigning small sets to the easy samples while returning empty sets for the hard ones. However, such an approach is not particularly practical or useful, as it fails to provide meaningful predictions for more challenging cases.\n\nIn the context of conformalized training, optimizing for a classifier that solely aims to minimize prediction set size seems less convincing. A more meaningful objective would be to develop a classifier that can offer fair and adaptive predictions, differentiating samples based on their intrinsic difficulty. Indeed, prior work, such as [2], has pointed out that training with the ConfTr loss function, which also seeks to minimize the smallest set size, does not necessarily improve conditional coverage, particularly when the data exhibits heterogeneity. That being said, while achieving a smaller average prediction set size can be beneficial as a secondary advantage, it is not entirely convincing to frame this as the primary goal in conformalized training. Instead, a more robust approach would be to balance prediction set size minimization with a framework that ensures fair and informative coverage across different types of samples.\n\n[2] \"Training Uncertainty-Aware Classifiers with Conformalized Deep Learning\", Einbinder et. al., 2022.", "other_comments_or_suggestions": "In the second line of Theorem 3.5, there is an extra right parenthesis between $(1-\\alpha)$ and $(s+1)$.\n\nAdditionally, $\\frac{1}{n}\\sum_{i=1}^n \\left[ \\sum_{y\\in \\mathcal{Y}} \\tilde{1}[S_f(X_i, y) \\leq q] \\right]$ appears to be repeatedly defined in Equation (9) and the second line of Equation (5), which may lead to potential confusion.", "questions_for_authors": "My apologies if I have overlooked anything, but I found the following two points unclear and would appreciate further clarification from the authors.\n\n1. In the second line of Equation (5), why is $\\hat{\\ell}(f, q)$ defined as an empirical estimation over all $n$ training samples? Shouldn't $\\hat{\\ell}(f, q)$ be computed using only the sampled batch?\n\n2. If I understand correctly, the main proposed algorithm, DPSM, aims to solve the optimization problem formulated in Equation (8), where $q$ is estimated by minimizing the average pinball loss over the nonconformity scores of all $n$ training samples. This suggests that the quantile loss is trained on the full batch of training data in each epoch after updating the model $f$. Furthermore, the improved learning bound established in the main theorem also assumes that the quantile function is trained using all $n$ samples. However, in Algorithm 1, the gradient of the quantile loss is computed using mini-batches. Could you clarify the reasoning behind or if I misunderstood? Additionally, why is the same subset $\\mathcal{D}_1$ used for both the conformal alignment loss and the quantile loss? Would there be any benefit in performing a further data split?", "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": "6qaWoQusbY", "reviewer": "Reviewer_2spM", "summary": "This paper introduces a conformal training algorithm called Direct Prediction sEt Minimization (DPSM). Existing training method suffers from a learning bound depending on the batch size. DPSM is formulated as a bilevel optimization that minimizes the prediction set size (upper level) conditioned on the learned quantile of conformity scores (lower level). This paper introduces algorithm to solve DPSM objective and show that it improves the learning bound to be dependent on the number of training samples instead.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful review. We provide an **external PDF** [(click this link to access)](https://anonymousicml.tiiny.site) to present the empirical results needed to answer some of your questions.\n\n**Q1: No theoretical results on the convergence of bilevel optimization are obtained as the authors pose it as an open challenge.**\n\nA1: 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.\nE.g., implicit gradient methods require a twice differentiable and strongly convex lower-level function.\nIterative differentiation methods require an iterative subroutine for the lower-level problem with more computational cost.\nPenalty-based methods typically require continuously differentiable upper and lower-level functions, but our lower-level QR loss is nonsmooth.\n\nAlthough 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&ouml;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.\n\nAdditionally, we empirically verify convergence behavior in experiments:\n\nFigure 1(a) and 1(b): upper and lower loss.\n\nFigure 1(c): error of the learned quantile in DPSM vs. batch quantile in ConfTr.\n\nFigure 1(d): convergence conformal loss (average soft set size) in DPSM vs. ConfTr.\n\nWe further plot the convergence of optimization error to 0 in **Fig 1(b) and (c) of external PDF** (See also A1 to Reviewer j13f).\nThese empirical results demonstrate the stable convergence of DPSM for the bilevel problem.\n \n**Q2: The numerical experiments are not very extensive in terms of datasets.**\n\nA2: 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.\n\n**Why is conformal training expensive?**\n\n(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)\n\n(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..\n\nComparing our datasets with previous conformal training literature.\nWe 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). \nIn 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.\n\n**Q3: The number of trials 10 is a bit few. Visualizations with confidence intervals could be better**\n\nA3: 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). \n\nTo study the robustness of DPSM, we show additional experiments with 20 trials on CIFAR-100 using HPS score in the table below.\n\n| Methods | CE | CUT | ConfTr | **DPSM**  |\n|-|-|-|-|-|\n| DenseNet |$2.59\\pm 0.075$|$2.28 \\pm 0.070$|$2.27 \\pm 0.054$|$2.17 \\pm 0.047$|\n| ResNet|$3.39\\pm 0.13$|$3.00 \\pm 0.71$|$3.77 \\pm 0.10$|$2.94 \\pm 0.072$|\n\nThese results are very similar to those obtained with 10 trials (Table 1), confirming that the improvement of DPSM in predictive efficiency is robust. \n\nAdditionally, we plot the visualizations with confidence intervals to further illustrate the stability and robustness of DPSM in **Fig 5 in the external PDF**. \nWe will include  results with more trials in the final paper.\n\n[r1] Sharma, et al. PAC-Bayes generalization certificates for learned inductive conformal prediction. NeurIPS 2023\n\n[r2] Correia, et al. An information theoretic perspective on conformal prediction. NeurIPS 2024\n\n[r3] Einbinder, et al. Training uncertainty-aware classifiers with conformalized deep learning. NeurIPS 2022\n\n[r4] Stutz, et al. \"Learning Optimal Conformal Classifiers. ICLR 2022\n\n[r5] Ding, et al. Class-conditional conformal prediction with many classes. NeurIPS 2024\n\n[r6] Huang, et al. Conformal Prediction for Deep Classifier via Label Ranking. ICML 2024", "claims_and_evidence": "* Theoretical\n  * The theoretical claims in Theorem 4.1 show that the learning bound is improved, which is standard ML generalization analysis. \n  * However, no theoretical results on the convergence of bilevel optimization is obtained as the authors pose it as an open challenge.\n* Numerical\n  * DPSM is shown to outperform other conformal training methods with significant reduction in prediction set sizes. It also has better predictive efficiency. \n  * DPSM is shown to converge effectively.\n  * Assumption 3.1 and 3.2 are empirically validated. \n  * The numerical experiments are not very extensive in terms of datasets. Also the number of trials 10 is a bit few. Visualizations with confidence intervals could better illustrate the robustness of algorithm performance.", "methods_and_evaluation_criteria": "The proposed method to resolve the dependence of learning bound on batch size is principled and well explained. The evaluation metrics of coverage guarantee and prediction set sizes make sense.", "theoretical_claims": "The proof of Theorem 4.1 appears to be correct.", "experimental_designs_or_analyses": "The experimental design makes sense but could benefit from a more extensive comparison on a wider range of datasets.", "relation_to_broader_scientific_literature": "Improve conformal training will contribute to the active field of uncertainty quantification, with meaningful implications to high-stake applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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:

Meta-review: The paper introduces Direct Prediction Set Minimization (DPSM), a novel conformal training algorithm that leverages bi-level optimization to minimize prediction set sizes in conformal prediction (CP). DPSM presents a compelling contribution to conformal training through its bi-level optimization framework, offering a theoretically grounded improvement in learning bounds and strong empirical performance in reducing prediction set sizes. The authors’ rebuttal effectively addresses concerns about conditional coverage, empirical robustness, and implementation clarity, reinforcing the method’s potential. However, the singular focus on set size minimization raises valid concerns about its alignment with broader uncertainty quantification goals, and the lack of theoretical convergence guarantees limits its theoretical completeness. The reviewers’ consensus leans positive, reflecting confidence in its contributions to conformal prediction. The suggested improvements can be incorporated in the final version to enhance clarity and impact.
Decision: Accept (poster)