Leave-One-Out Stable Conformal Prediction
Authors: Kiljae Lee
Yuan Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Conformal Prediction
Algorithmic Stability
Regularized Loss Minimization
Stochastic Gradient Descent
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: Conformal prediction (CP) is an important tool for distribution-free predictive uncertainty quantification.
Yet, a major challenge is to balance computational efficiency and prediction accuracy, particularly for multiple predictions.
We propose **L**eave-**O**ne-**O**ut **Stab**le **C**onformal **P**rediction (LOO-StabCP), a novel method to speed up full conformal using algorithmic stability without sample splitting.
By leveraging *leave-one-out* stability, our method is much faster in handling a large number of prediction requests compared to existing method RO-StabCP based on *replace-one* stability.
We derived stability bounds for several popular machine learning tools: regularized loss minimization (RLM) and stochastic gradient descent (SGD), as well as kernel method, neural networks and bagging.
Our method is theoretically justified and demonstrates superior numerical performance on synthetic and real-world data.
We applied our method to a screening problem, where its effective exploitation of training data led to improved test power compared to state-of-the-art method based on split conformal.

Published as a conference paper at ICLR 2025
LEAVE-ONE-OUR STABLE CONFORMAL PREDICTION
Kiljae Lee, Yuan Zhang The Ohio State University 1ee. www.110488.s.c.. edu, ychanghfestat.osu.cm
ABSTRACT
Conformal prediction (CP) is an important tool for distribution-free predictive un- certainty quantification. Yet, a major challenge is to balance computational effi- ciency and prediction accuracy, particularly for multiple predictions. We propose Seave-One-Ore Stable Conformal Prediction (100-StabCP), a novel method to speed up full conformal using algorithmic stability without sample splitting. By leveraging leave-one-out stability, our method is much faster in handling a large number of prediction requests compared to existing method D0-StabCP based on replace-one stability. We derived stability bounds for several popular machine learning tools: regularized loss minimization (RLM) and stochastic gradient de- scent (SGD), as well as kernel method, neural networks and bagging. Our method is theoretically justified and demonstrates superior numerical performance on syn- thetic and real-world data. We applied our method to a screening problem, where effective exploitation of training data led to improved test power compared to state-of-the-ee method based on split conformal.
INTRODUCTION
Conformal prediction (CP) offers a powerful framework for distribution-free prediction. It is useful for a variety of machine learning tasks and applications, including computer vision (Angelopoulos) jet al. 2020), medicine (Vazquez& & Facelli [022 Lu et al., (022), and finance (Wisniewski et al. 2020 where reliable uncertainty quantification for complex and potentially mis-specified models is in much need. Initially introduced by Vovk al, (2005), conformal prediction has gained renewed interest. Numerous studies significantly enriched the conformal prediction toolbox and deepened theoretical understandings (Lei al., 2018: Gibbs & Candes 202 Barber et al. 2023).
Given data D = {X,, Y) where (X,,Y) E (2,)) lid.
Px,,, the goal is to predict the unob- i.j.d.
served responses (Y 1 on the test data Deest = {(Xntj. Yn+j=?)) m j=ml Px,y Conformal prediction constructs prediction intervals C. (Xn+)) at any given level E (0, 1), such that
IP(Y++ E Ca 2 aa, for all
(1)
A highlighted feature of conformal prediction is distribution-free even when wrong model is used for prediction, the coverage validity (I) still holds (but the prediction interval will become wider).
A primary challenge in conformal prediction lies in balancing computation cost with prediction ac- curacy. Among the variants of conformal prediction, full conformal is the most accurate (i.e., short- est predictive intervals) but also the slowest; split conformal greatly speeds up by data-splitting scheme, but decreases accuracy and introduces variability that heavily depends on the particular split (Angelopoulos & Bates 202 | Vovk 2015 Barber et al. 2021). Derandomization (Solari & Djord- jilović] [022] Gasparin & Ramdas 2024) addresses the latter issue but increases computational cost
and may make the method more conservative (Ren & Barber 2024).
Algorithmic stability is an important concept in machine learning theory (Bousquet & Elisseeff 2002). It measures the sensitivity of learning algorithm to small changes in the input data. Nu- merous studies have focused on techniques that induce algorithmic stability, such as regularized loss minimization Shalav-Shwartz al. [2100] Shalev-Shwarzz & Ben--avid 2014) and stochastic gradient descent (Hardt et al. [016]] Bassily et al.] (2020). Recent research has applied the concept of algorithmic stability to the field of conformal prediction (Ndiaye) 2022 Liang Barber 2023

---

Published as a conference paper at ICLR 2025
Ndiaye (022)
proposed replace-one stable conformal prediction (RO-StabCP) that effectively accelerates full conformal by leveraging algorithmic stability. While it accelerates full conformal without introducing data splitting, thus preserving prediction accuracy, the prediction model needs to be refit for each Xa+j. lowering its computational efficiency for multiple predictions.
In this paper, we introduce Leave-One- One-Out Stable Conformal Prediction represents is a distinet form of algorithmic stability type than that in RO-St The key innova- tion is that our stability correction no longer depends on the predictor at the test point Xn+j- As result, our method only needs one model fitting using the training data D. This enables our method to effectively handle a large number of prediction requests. Theoretical and numerical studies demon- strate that our method achieves competitive prediction accuracy compared to existing method, while preserving the Unite-sample coverage validity guarantee.
which
PRIOR WORKS ON CONFORMAL PREDICTION (CP)
To set up notation and introduce our method, we begin with a brief review of classical CP methods.
Full conformal. We begin by considering the prediction of a single Yu+j- Fix j E [m] = (1...... m) and let y denote a guessed value of the unobserved Yn+j- We call Dj D DU ((Xn+),00) })} the augmented data and train a learning algorithm f (such as linear regres- sion) on Dj. To emphasize that the outcome of the training depends on both Xn+s and y. we denote the fitted model by fy. Here we require that the training algorithm is permutation invaaiian,,, meaning that P3 remains unchanged if any two data points (Xi, Y2) and (Xx, Yp) are swapped for 1' [n] {n j}. Next, for each i l....,,,, n, ion++1 j. we define a non-conformity score Sr = S(Y, fy (X.)) = Y. (X,)) to measure f.''s goodness of prediction on the ith data point. Notice that S also depends on Xnty through f/ (X,), thus its subscript j. For simplicity, we set j = 1 and write SY, as Sp only for this part. Now, plugging in y = Ya+1, by symmetry, all non-conformity scores (S/ )i= U (S" are exchangeable, and then the rank of S (in ascending order) is uniformly distributed over {I..... n 1}, implying that
IP S (15) (+ y U (oo))) 2 1-a,
M where (S) == inf((x)F(())) 2 p} denotes the lower-p sample quantile of data S. This implies coverage validity IP(Yn-1 E C (X 2 a of the prediction set Cfull (X.+1) defined as cfull (X = {y E y: S < 21-a(1 ( {xx)))
(2)
This leads to the full conformal (F (FullCP) method: compute Chulll (Xn+1) by a grid search over V
Split conformal. The grid search required by full conformal is expensive. The key to acceleration is to decouple the prediction function /. thus most non-conformity scores (S from both j and y: if S S*+ is the only term that depends on y, then the prediction set be analytically solved from ( Split conformal (Sp1 i tCP) (Papadopoulos et al. 2002 Vovk 2015) randomly splits D into the training data Dirain and the calibration data Dealibs train f only on Dirain. and compute and rank non-conformity scores only on Dealib U {(Xn+j,)) y) While split conformal effectively speeds up computation, the flip side is the reduced amount of data used for both training and calibration, leading to wider predictive intervals and less stable output.
Replace-one stable conformal. Ndiaye 2022) accelerated Ful CCP by leveraging algorithmic sta- bility. From now on, we will switch back to the full notation for S and no longer abbreviate 5 as S.- To decouple the non-conformity scores from y, Ndiaye (2022) evaluate these scores using y. an arbitrary guess of y. Therefore, we call his method replace-one stable conformal prediction (RO-StabCP). To bound the impact of guessing he introduced the replace-one (RO) stability.
Definition 1 (Replace-Ong Algorithmic Stability). A prediction method f is replace-one stable, if RR
< 00, such that for all j E [m] and E [m] U (n + j}, there exists T..
RO 18 (X.)) S(2, 17 (X.) T.
sup v.T.EEy
Herr we replaced "S,,, " in (5 N=i U (
} by oo. This does not change the quantile.
2

---

Published as a conference paper at ICLR 2025
where f3 is trained on D U [(Xn+). for 1 y or y.
Recall that Sh = i - (x.)) denote the non-conformity score computed using ÿ. Then it suffices to build predictive interval that contains jja (X xx+z) in (2). By Definition i the following
inequality ly T_,((XX,,) (Xn+z)) - S Sutis S 21 (15 U {(o)) S (1 + Ro f. Fiml U foo}) holds true for any y E (Xn+)) Consequently, the RO stable prediction set
jo (Xn+))= = e (X Tntjs I Q1-a(15), + T.. 2o1r u (oo1)}
(3)
contains Chull (Xn+j) subset, thus also has valid coverage. The numerical studies in Ndiaye (022) demonstrated that RO-St abCP computes as fast as SplitC? while stably producing more narrower predictive intervals (i.e., higher prediction accuracy).
LOO-STABCP: LEAVE-ONE-OU STABLE CONFORMAL PREDICTION
3.1 LEAVE-ONE-OUT (LOO) STABILITY AND GENERAL FRAMEWORK
When predicting one Yn+j, RO- has accelerated full conformal to the speed comparable to split conformal. However, its non-conformity scores S 's still depend on Xn+j. Consequently, in order to predict (Yn+))ī=ı RO-St would refit the model times, once for each Xn-3-
This naturally motivates our approach: can we let all predictions be based off a common model J. which only depends on D {X,, r=) but not any of (Xn+s)/=1 Interestingly, the idea might appear similar to a beginner's ' mistake when learning Ful1CP, overlooking that the model fitting in Fulllc 1 should also include (Xn+j. y), not just D. Clearly, to ensure a valid method, we must correct for errors inflicted by using f in lieu of Py. Since these two model fits (ours vs FullCP) are computed on similar sets of data, with the only difference of whether to consider (Xn+j, V), our strategy to study the leave-one-oul (LOO) stability of the prediction method.
Algorithmic Stability). A prediction method is leave-one-out stable, for all j E [m]] and i E [m] U {n + j}. there exists Ti,)
Definition 2 (Leave-One-Ol)
1.00 < OC, such that
sup [8(=, (xx)) S(,,, ((x,)( & T..1 y.zEy
L,00
,,LO''s appearing in Definition are called LO0 stability bounds. Their values can often be The '..j determined by analysis of the specific learning algorithm f. For each j. we used a different set of LOO stability bounds (T (T4,00))e (=e])]((ntj)- This approach is adopted to achieve sharper bounds compared to using a uniformly bound for all j. We clarify that the concept of algorithmic stability non non-parametric f's alike. For an f parameterized by some 8, the stability bound does not focus on the whereabout of the optimal 0, but on how much impact leaving out (n + t)th data point will have on the trained J. possibly via quantifying its impact on the estimated 0. We will elaborate using concrete examples in Section For now, we assume that .LL0''s are known and present the general framework of our method, called leave-one-out stable conformal prediction (LOO- SbaCP), as Algorithm I
is well-defined for parametric
The implementation requires computation of ((mn) many T.. values. However, these compu- tations are relatively inexpensive and do not significantly impact the overall time cost. In many examples (such as SGD, see Section (32.2), the main computational cost comes from model fitting, especially for complex models. We empirically confirm this in Section 4 through various numerical experiments.
Table I presents comparison of the computational complexity for conformal prediction methods. The concept of leave-one-out perturbations conformal prediction has been studied in Liang & Barber (2023), but their angle is very different from ours. They focused studying the LOO as part of Jackknife+ (Barber et al. 2021). which fits n models, one for each D \ {(x,, Y.) Then use LOO technique in a very different way, developing a fast algorithm that fit only one model to D (without deletion). The "one" in our leave-one-our refers to "(Xn+j, y)" in D U (Xx+)j y)), for each j.
all these n models are used simultaneously for each prediction. In contrast,
3

---

Published as a conference paper at ICLR 2025
Algorithm 1: (100-StabCC) Letp:aab----Lae-------ee--- Leave-One-Out Stable Conformal Prediction Set Input : Training set D = {(X,, Y.) test points (Xn+s)y=1 desired coverage a.
Output: Prediction interval Cj,00 (Xn+z) for each j E [m]
1. Fit the prediction function f on D;
2. Compute (uncorrected) non-conformity scores on D: S -Y, f(X:) for [m]:
for j E [m]] do
Compute stability bounds 7.000 for E [n] j}:
4. Compute prediction interval:
ja (Xn+s)= = [f(x+t)) = ( (1S, (10 +1100 100 1 u (oo)) + - }
end
FulicP
SplitCP
RC RC-StabCP
L00-StabCP
of model fits
[ m
m
# of prediction evaluations
(n + 1) D
a m Not applicable
(n + 1) m (n + 1) mm
n + m (n + 1) m
# of stability bounds
Not applicable
Table 1: Computational complexities of our method and benchmarks, where | is the size of the search grid used in FullcP. We emphasize that in many examples, such as SGD (Section 3.2.2) one model fitting is much more costly than one prediction or computation of one stability bound.
Next, we provide the theoretical guarantee of algorithm's 's coverage validity.
Theorem 1. the prediction method is leave-one-out stable in Definition Then for each j E [m], the prediction set 1, (Xn+s) constructed by Algorithm 7 satisfies
IP(Yn-j E 1,,00 (1000(a+t)) 21 a.
3.2 LOO STABLE ALGORITHMS
So far, we have been treating the stability bounds T.j 71.00 as given without showing how to obtain them. In this section, we derive these bounds for two important machine learning tools: Regularized Loss Minimization (RLM) and Stochastic Gradient Descent (SGD). Many machine learning tasks aim to minimize a loss function Eyy, fe [x() over training data. Empirical Risk Minimization (ERM) a common approach, which seeks to minimize A D E(Y,, (Xx)) with respect to 9. However, the objective function is often highly nonconvex, making the optimization challenging. RLM alle- viates nonconvexity by adding an explicit penalty (e.g., ridge and LASSO) to the objective function (Hoerl & Kennard [970; Tibshirani 1996). Alternatively. SGD implicitly regularizes the optimiza- tion procedure (Robbins & Monro, 1951) by iteratively updating model parameters using one data point time. Its computational efficiency makes it preferred method in deep learning (LeCun)
et al. 2015 He et al. 2016).
3.2. 1
EXAMPLE 1: REGULARIZED LOss MINIMIZATION (RLM)
To derive the LOO stability bound, we compare two versions of RLM, only differing by their training data. The first trained on D, producing i = arg minsge n En= fo + ((0),, where θ is the parameter space and 12(0) is the explicit penalty term; while the sec- ond is trained on the augmented data Dÿ (recall DY arg minsgel | (Σ E(Y,, fo())) + Ely, fo(Xx+s)) }}} + [())]. The LOO stability for RLM is described by Definition with f(.) = fa(.) and P/ (.) fay (-). To state our main result, we need some concepts from optumization.
U {(Xn+xx v))). producing Ø4
Definition 3 (p-Lipschitz). continuous functioo g R2 129 is p-ipscchitz if
(la(z) - g(v)) s p||z - vll. for any x, y E RP.
4

---

Published as a conference paper at ICLR 2025
Definition 4 (Strong Convexity). A function g RR - R is X-strongly convex, if
X
g(tx + (1 t)y) S (g(x)) + (1 - +))(())
2 | - y for any x, y E RpP and & (0, 1).
In addition, a function g is convex it is O-strongly convex.
Now we are ready to formulate the LOO stability bounds for RLM.
Theorem 2. Suppose: for each i E [n + m] and given any y, the loss function Ely, fo(X,)) is convex and pi-Lipschitz in 0; 2) the penalty term St is >-strongly convex; 3) for each i E In + m], the prediction function (X) is vi-Lipschitz in 0; and 4) given any y, the non-conformity score S(y, 2) is --Liscchitz in Then, RLM has the following LOO and RO stability bounds.
1,00 2yps(pnns + P)
RR 4yvspati Ti.j X(n + 11)
J
X(n + 1)
and
(4)
where ranges in [n] U (n j} for each S S m, and n ---=n-1 Pi-
As side remark, uniform RO stability bound has been established in Ndiaye (022)) (Corollary 3.10). Our RO bound in (4) is non-uniform (not maximizing over X;) and potentially sharper.
3.2.2 EXAMPLE 2: STOCHASTIC GRADIENT DESCENT (SGD)
For simplicity, we recap how SGD operates when trained on D. starts with an initial parameter value 9n and runs for R epochs. In each epoch, generate a random permutation π (T...... Tn) of [n]. Then for each i [m]. update the model parameter by 0 = of xx: (X(x;)) (xx)), where 1 > 0 is a user-selected learning rate. After a total of R'n updates, the output 0 is used for prediction. Like in RLM, our LOO stability bound compares and Dj, respectively.
versions of SGD, trained on D
Theorem 3. Suppose: for each E [n m.) the loss function Ely, (oy.fo(X)) (X:)) is convex, p pi-Lipschitz in 0, and its gradient Vol(y, fo(X.)) is Lp-Lippchiiz in 0, for any y; for each i E [n + m]] the prediction function (X) is vi-Lipschitz in 0; and 3) the non-conformity score S(y. z) is 7- Lipsehitz in z, for any y. Then, with learning rate n S m SGD has the following LOO and RO stability bounds.
Ti
LO0 = Rm--nve NVGPnts and
RO Ti 2nn WVsPt+s
(5)
where i ranges in [n] U (n j) for each S S m.
Readers may have noticed that for SGD, L0O is only half of RO which is very different from the case for RLM (c.f. Theorem 2 The gap here stems from the iterative nature of SGD. Recall that in each epoch, SGD performs n (or n n 1) gradient descent (GD) updates, with each update depending on a single data point. Consequently, leaving out one data point results in one fewer GD update. In contrast, replacing one data point means performing one GD update differently in the worst-case scenario, this update may move in opposite directions before and after the replacement, doubling the stability bound.
"i.j
SGD's iterative nature makes it an excellent example where the number of model fits is the main bottleneck in scaling erucial learning technique. For SGD, each model requires O(Rm) gradient updates, while each prediction costs 0(1) time, and evaluating stability bounds for each prediction costs (n) time. Combining this understanding with Table [ we see that our method provides significantly faster stable conformal prediction than RO-StabCP for performing large number of predictions.
3.2.3 TOWARDS BROADER APPLICABILITY OF LOO-STABCP
The kernel method (or "kernel trick") (Schölkopf 2002 is commonly used technique in statistical learning. It implicitly transforms data into complex spaces through a kernel function k(xx,' x"). This leads to the reformulated optimization problem: Ø arg minggeR 1 E E(Y,, 6.7 0) + 20 K0, where K is a positive-definite kernel matrix K = &(Xi, X,). and k; denotes its i-th row. is not difficult to verify that the kernel method is a special case of RLM, thus Theorem 2 applies to the kernel method.
Kernel method:
Here, represents the prediction output, and therefore, this is an assumption independent of the model.
5

---

Published as a conference paper at ICLR 2025
Neural networks: The stability bounds for RLM and SGD rely convexity assumptions that might not always hold in practice, such as in (deep) neural networks. Here, we analyze the LOO stability of SGD popular optimizer for neural networks, without assuming convexity.
Theorem 4, Assume the conditions of Theorem 3 except that the loss function fo (x)) is not required be convex in O. Then, for the same range of (1,3), SGD has the following LOO and RO stability bounds:
LOO RR " and
RO 1.
22 MVpPn-
where R > K" and K. 1T= tp:)-
While Theorem does provide rigorous theoretical justification for neural networks, in practice, the term & may be large if the learning rate 7 is not sufficiently small or the activation function is not very smooth, leading to large Lipschitz constants yo Therefore, this stability bound may turn out to be conservative. Similar to HHaddt et al. (2016). we also observed that the empirical stability of SGD for training neural networks is often far better than the worst-case bound described by Theorem see our numerical results Section[3] This suggests practitioners to still apply the stability bound Theorem B dismissing non-convexity. It is intriguing but challenging future work to narrow the gap between theory and practice here.
Bagging: Bagging (bootstrap aggregating) (Soloff al., 2024 general framework that aver- ages over B models trained on resamples of size from D. Random forest (Wang et al.) 2023) is a popular special case of bagging, in which each f(b) is a regression tree. Therefore, we focus on studying bagging. predicts by fd ual model trained on the 6th resample. For simplicity, here we analyze a "derandomized bagging" Soloff et al. 2024). i.e., setting + oo. The prediction function becomes (x) = (x)()) Below is the LOO stability of derandomized bagging. Here, we denote ().(0())) and f (x) as the individual models obtained from Dj and D, respectively.
Em= (x)),, where ((b indicates the individ-
Theorem 5. Assume that for any j [mi] and (2r, v) E X y,, all individual prediction functions f3 ( (x) and (( (x)) are bounded within a range of width wy; 2) the nonconformity score S z) L-Liscchitz for any y. Then, derandomized bagging achieves the following LOO stability bound:
1.00 = y00 P
2 V 1-p'
where p 1- 41
1)th and i [m] U (n + j} for j ....., m.
From above, note that the only assumption about the prediction model is bounded output. For example, regression trees satisfy this assumption.
Due to page limit, we relegate more results and discussion to Appendix A.3
4 SIMULATION
In this simulation, we compare several CP methods serving RLM and SGD. We set n = m 100, 0.1 and generated synthetic data using X, i.idd AV ( with d 100, where E, p (i.e., AR(1)). In particular, we chose = 0.5 in this experiment. For the response variable we set
1.1dd 1).
Y, () + 6, where 6;
We considered two models for M(:;B): linear u(=; = Ed= 85æy and nonlinear [=<;; 1) = E/= 2/100 In both models, set By xc (1 j/d) for j E [d]. and normalize: | = d. To fit the model, we used robust linear regression, equipped with Huber loss:
1 (v fx(x))2 cly fo(z) 12, yy - fo(z) >
fy fo(x))
fly, fo(r)
where (x) = TT and we set e = 1 throughout. We used absolute residual as con-conformity scores. In RLM, set 2(0)) | and solved it using gradient descent DDiamond & Boyd

---

Published as a conference paper at ICLR 2025
2016
Throughout, ran SGD for R 15 epochs for all methods, except R = 5 for the very
slow PullCP. For both RLM and SGD, we set the learning rate to be = 0.001. For more repeated 100 times.
implementation details, see Appendix G.1 Each experiment
We compare our method to the following benchmarks: 1) OracleCP (Appendix C.T Algorithm 4h impractical method that uses the true (Yn+j)}= to prediet; 2) Ful PullCP; 3) Sp ppiittP: 70% Trining + 30% calibration; and 4) RO-StabCP. The performance of each method is evaluated by three measures: 1) coverage probability (method validity); 2) length of predictive interval (prediction
accuracy); and 3) computation time (speed).
Lincar Setting: RIM
Linear Setting:
Nouliearr Setting:
Noolineur Setting: Scil
Oudte
tonatar
Paiic
hater
speicy
Russact
Lonsaace
Oedect
Spoer
a0
Langih
12
Idt Stac?
hare
Syor?
R01 Star??
lei Seor?
Log time (logfoss))
Oudic
shore
100 ion-acr
Owierr
Spiie
Mnsacc
Dusic?
Asor
tonaace
Order
100
Figure 1: Comparison of CP methods. Our method (ta0-P achieves competitive prediction accuracy and computes at the speed comparable to SplitCP, while maintaining coverage validity.
Figure presents the results of our simulation. In the plots for coverage and length, the horizontal dashed lines represent the desired coverage level (1 - a) and the length of the tightest possible prediction band obtained from the true distribution of the date respectively. As expected, all methods maintain valid coverage. Our method shows competitive prediction accuracy, comparable to those of OracleCP, FullCP, and RO-StabCP. These four methods exhibit more consistent and overall superior accuracy compared to SplitCP. In terms computational efficiency, our method performs on par with SplitCP and is clearly faster than other methods. Notably, our method significantly outperforms RO- St-bbtabPP in handling large number of prediction requests.
5 DATA EXAMPLES
We showcase the use of our method on the two real-world data examples analyzed in Ndiaye 2022) The Boston Housing data (Harrison Jr & Rubinfeld (978) contain 506 different areas in Boston, each area has 13 features as predictors, such as the local crime rate and the average number of rooms. The goal is to predict the median house value in that area. The Diabetes data (Efron al.) 2004) measured 442 individuals at their "baseline" time points for 10 variables, including age, BMI, and blood pressure, aiming to predict diabetes progression one year after baseline. Both datasets are complete, with no missing entries. All continuous variables have been normalized, and no outliers were identified.
For each data set, we randomly held out data points (as the test data) for performance evaluation and released the rest to all methods for trainingccaliration. We tested two settings: m 1 and 100, two model fitting algorithms: RLM and SGD; and repeated each experiment 100 times.
In our setup, it is 3. 3.290 since PP([ea] < 1.645) 0.9.

---

Published as a conference paper at ICLR 2025
The other configurations, including the model fitted to data (e, Ω etc.), the list of compared benchmarks and the performance measures, all remained unchanged from Section
Boston: RLM
Bosron: SGD
Dracctes RIM
Diahetes: SGD
Length
Pomp
spary
Ossicy
Oodecy
Peppy
Poiie
entoe
12
1
Spar7
Oldec
Paice
Log time (lrggtee:)))
Chock
Long time (agieeec))
K K00
Spler?
har
Guder??
hoce
Figure 2: Comparison of prediction interval lengths, under choices m and m 100.
Figure 2 shows the result. While most interpretations are consistent with that of the simulation, observe two significant differences between the settings m
m = 100. First, under m = 1. RO-StabCP and our method take comparable time, but when increases to 100, our method exhibits remarkable speed advantage, as expected. Second, with an increased m, the amount of available data for prediction/calibran all methods. Also, Sp1 i tCCP continues to produce more variable and lengthier prediction intervals compared to most other methods for (1, 100). In summary, advantagcous performances in all aspects across different settings. The empirical coverage rates are consistent with those in the previous experiments and are provided in Appendix G.3
also decreases. This leads to wider prediction intervals for
method LO0-StabCP exhibits
Coverage
Length
Log-time (logíscc.))
10
0.9
0.5
500
Badaa
Tlubsice
Bastte
Dulectes
Busoon
Dabeta
SpliCP
RO-SaACP
LOO-SubCCP
Figure 3: Comparison of CP methods with neural networks with single hidden layer under choice of m = 100. LCO-StabCP continues to closely achieve the target coverage while exhibiting lower variability prediction intervals.
To further evaluate the performance of L00-StabCP with non-convex learning methods, we con- ducted experiments with neural network of a single hidden layer of 20 nodes and sigmoid ac- tivation function. We set = 0.001 and R = 30. For stability bounds, we borrowed from the practical guidance in Hardt et al. (2016) and Ndiaye 2022) and set T Rn ||II
for Lo0-St abCP and 7 ze 2R X X for RO- StabCP, respectively. This choice is
elaborated in Appendix A.2 see (8. Figure presents the results. 1.00-StabCP maintained valid
8

---

the Published as a conference paper at ICLR 2025
coverage across all scenarios. These findings highlight the robustness of LO0-StabCP in handling complex models like neural networks.
Finally, since could consider derandomization by aggregating results across multiple differ- ent splits to reduce variation of SplitCP (Solari & Djordjilovid) 2022, Gasparin & Ramdas 2024), also numerically compared our method to this approach. The result demonstrated that our LO0-StabCP is computationally faster and less conservative than two popular derandomized
SplitCP methods Solari & Djordjilović (2022); Gasparin & Ramdas (024).. Due page limit, we relegate all details of this study to Appendix
APPLICATION: CONFORMALIZED SCREENING
Many decision-making processes, such drug discovery and hiring, often involve screening stage to filter among a large number of candidates, prior to more resource-intensive stages like clinical trials and on-site interviews. The data structure what we have been studying in this paper: training data D = {(,,, Y=) and a large number of test points [X 1==1 without observing Yn+z" Ss. Suppose higher values of Y are of interests, Jin & Candès (0023) formulated this as the following randomized hypothesis testing problem:
mm
Hoj Yu+j Cj
H1y : oj. for E [m].
where cy's are user-selected thresholds (e.g., qualifying score for phone interviews). Then screening candidates means simultaneously testing these m randomized hypotheses. To control for error in multiple testing, popular criterion is the false discovery rate (FDR), defined the expected false discovery proportion (FDP) among all rejections.
Ej= ((Ho is incorrectly rejected)
FDR E(FDP), where FDP
1 1vE 1(Hoz is rejected]
Jin & Candès (2023) proposed method called cBBH based on SplitCP. Our narration will build upon non-contormity scores without repeating details about model fitting. In this context, the non- conformity score should be defined differently, for instance: S(y, y without the absolute value, where y is the observed response and & is the fitted value. On the calibration data, S f(Xn=)))))) Jin & Candès
S(Y, f(X,)), whereas on the test data, we would consider 5 2003 cfBH method computes the following conformal p-value:
EiEloin 1(S; < S.) 1
pi splic
[eatib| +
where Tealih denotes the index set corresponding to the calibration data. To intuitively under- stand (6). notice that papllt a if and only cj falls outside the level-(1 a) (one-sided) split conformal prediction interval for Yn+j- Finally, plugging {ppplit 1 === into
Benjamnin--Hohbbee
(BH) procedure (Benjamini & Hochberg. 1995) controls the FDR at a desired level q: compute k* = max(k:
Sm 10 < qk//m) mm] 2 k). and reject all Hoj 's with split < qmk
While Jin & Candes 2202)'ss method effectively controls FDR and computes fast, the data splitting mechanism leaves space for thoroughly exploiting available information for model fitting. To this end, we propose a new approach, called L00-cfBE built upon our main method L00-StabCP. We compute stability-adjusee p-values as follows:
Σn (S,
LO0
< S
10O
) +1
1.00 Pj
I.j
ntj
"nij)
n
Algorithm describes the full details our method.
To numerically compare our method to existing approaches, we used the recruitment data set Ganatara (020) that was also analyzed in Jin Candes (2023). It contains 215 individuals, each measured 12 features such education. work experience, and specialization. The binary sponse indicates whether the candidate receives a job offer. We import the robust regression from Section as the prediction method, optimized by SGD. Since the task is classification,

---

Published as a conference paper at ICLR 2025
Algorithm 2: (L00-cfBH) Conformal Selection by Prediction with Leave-One-Ous p-values
Input : Training set D, test points (Xn+s thresholds {c FDR level q.
Output: Set of rejected null hypotheses
1. Fit the prediction function on D;
2. Compute (uncorrected) non-conformity scores on D: S ((X), for [n];
for j E [m] do
Compute stability bounds T.. for [n] {n j}:
Compute LOO conformal p-values p).00 as in 7
end
Implement BH Procedure: k* max ΣØ= 1 11 I gk/m} 2 k) and reject all
Hojss is satisfying p1:00 < gkk /m.
100y f. For illus- tration, we also formulated benchmark RO-CfBH, following the spirit of Ndiaye (202)) and using replace-one stability. RO-cfBH replaces all 71.00 terms in (7) by the corresponding RO terms; is otherwise identical to LO0-cfil cBB.. We repeated the experiment 1000 times, each time leaving 20% data points the test data. In cBBH, the data split into 70% for training and 30% for calibration. We tested three target FDR levels E {0.1,0.2 0.3} and consider three performance measures: 1) FDP; 2) test power, defined as m H is rejected)) (E}= 1(H true))) and 3) time cost.
clip function in Jin & Candès 2203 the non-conformity score: Syy, f
Mid al
1.0
0.5
Long time (log
-.0
0.6
-1.5-
2.2
0.4
2.0
RodB0
0.
Figure 4: Comparison of screening methods on recruitment data. Time cost does not vary with
Figure shows the result. Our method achieves valid FDP control for all tested g. Compared to CFBH, our method is more powerful, due to improved exploitation of available data for prediction. The performance measures also reflect that our method LO0-CfBH produces more stable prediction intervals, while sample splitting introduces additional artificial random variations to the result of cfBH. Compared to RO-C fBH, we highlight our method's significant speed advantage. Moreover, we showed in Theorem 3 for SGD, our LOO approach achieves tighter stability bound than RO. As result, our method is less conservative and more powerful compared to RO-cfBH.
7 CONCLUSION AND FUTURE WORK
In this paper, we propose a novel approach to stable conformal prediction. Our method significantly improves computational efficiency for multiple prediction requests, compared to the classical stable conformal prediction (Ndiaye) 2022). Here, we mention three directions for future work. First, while we have derived stability bounds for RLM, SGD, neural networks and bagging, improving the tightness of bounds for complex methods remains an important avenue for future research. Second, have been focusing continuous responses. It would be an intriguing future work to expand our theory to classification. A third direction is to investigate algorithmic stability for adaptive conformal prediction.
10

---

Published as a conference paper at ICLR 2025
SUPPLEMENTAL MATERIALS
The Supplemental Materials contains all proofs and additional numerical results. The code for re- producing numerical results is available at: htttp::/ wwt.coom///..../
ACKNOWLEDGMENT
The authors thank Eugene Ndiaye for helpful discussion and the anonymous reviewers for construc- tive criticism. This research was supported by NSF grant 2M119911109.
REFERENCES
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv: 14193, 2020.
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.001 107.01111, 2021.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49866:48 507, 2021. doi: 10.1214/
A0-AOS1965. URL https: //doi .rrg/.rgg//oo.o /10, 2 A0S1 965.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 51(2): 81-855888-85,,,, 2023.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances Neural Information Processing Systems, 33: 4381-4391, 2020.
Yoav Benjamini and Yosef Hochberg, Controlling the false discovery rate: a practical and powerful approach multiple testing. Journal of the Royal statistical society: series (Methodological), 57(1):289-300, 1995.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526 2002.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. The
Annals of Statistics, 32(2):407-499, 2004.
Dhimant Ganatara. Campus recruitment.
https::/www.tk. wwggla..gll..... ctm/d/ttast// benroohan/Faae wwwtors-afoeetttoeeeeeeeea innporsssaaaeiiinnnnnnass------ pww.mppepppaaaeeett...... 2020.
Matteo Gasparin and Aaditya Ramdas. Merging uncertainty sets via majority vote. arXiv preprint
DoXiv:2401.09379 2024.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Ad- vances in Neural Information Processing Systems, 34:1660-1672, 2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pp. 1225-1234. PMLR, 2016.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1::11-102, 1978.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-67, 1970.
11

---

Published as a conference paper at ICLR 2025
Ying Jin and Emmanuel J Candès. Selection by prediction with conformal p-values. Journal of Machine Learning Research, 24(244):1-411 2023.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 2015.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):094-11111, 2018.
Ruiting Liang and Rina Foygel Barber. Algorithmic stability implies training-conditional coverage for distribution- creebbuttoo-free prediction methods. arXiv preprint arXiv:2311.04295, 2023.
Charles Lu, Andréanne Lemay, Ken Chang, Katharina Höbel, and Jayashree Calpathy-Cramee Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 12008-12016 2022.
Eugene Ndiaye. Stable conformal prediction sets. In International Conference on Machine Learn- ing. pp. 16479. PMLR, 2022.
Harris Papadopoulos, Kostas Proedrou, Vladimir Vovk, and Alexander Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, 2002. URL
org/CorpusID- : 42084298
Zhimei Ren and Rina Foygel Barber. Derandomised knockoffs: leveraging e-values for false dis- covery rate control. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86 (1):122-154, 2024.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400 400-407, 1951.
B Schölkopf. Learning with kernels: support vector machines, regularization, optimization, and beyond, 2002. 2002.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 1 11:2635-2670, 2010.
Aldo Solari and Vera Djordjilović. Multi split conformal prediction. Statistics & Probability Letters, 184: 10939,, 2022.
Jake A Soloff, Rina Foygel Barber, and Rebecca Willett, Bagging provides assumption-free stability. Journal of Machine Learning Research, 25(131):1-33 2024.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, (226:77872 1996.
Janette Vazquez and Julio C Facelli. Conformal prediction in clinical medical sciences. Journal of Healthcare Informatics Research, 6(3):241-252, 2022.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74: 9-28, 2015.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning a random world, volume 29, Springer, 2005.
Yan Wang, Huaiqing Wu, and Dan Nettleton. Stability of random forests and coverage of random- forest prediction intervals. Advances in Neural Information Processing Systems, 36:31558- 31569, 2023.
Wojeiech Wisniewski, David Lindsay, and Sian Lindsay. Application of conformal prediction inter- val estimations to market makers' net positions. In Conformal and probabilistic prediction and applications, pp. 285-301. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Supplemental Materials for "Leave-one-out Stable Conformal Prediction"
Kiljae Lee and Yuan Zhang
A DETAILED INSIGHTS ON PRACTICAL EXTENSIONS OF LOO-STABCP
In this appendix, we provide further numerical and theoretical analysis to support the approaches discussed in Section 3.2.3
A.1 NUMERICAL EXPERIMENTS USING KERNEL TRICK
The key insight of the kernel trick is that by transforming the data into a higher-dimension feature space using a kernel function, the original optimization problem
3
= arg min BERd
(Vi, + +|1311
can be reformulated as
0 = arg min
Σ DER 72
EYY,, 0) + K0. X0
This reformulation using the kernel trick does not violate the assumptions required for RLM and SGD, as the transformation maintains the core structure of the optimization problem. Specifically, the kernel matrix K implicitly defines the high-dimensional feature space through the kernel func- tion k(X,, without requiring explicit computation of the transformed features. This ensures that the problem remains computationally tractable.
For RLM, the regularization term || in the original formulation translates directly 0 K0 in the kernelized version, preserving the strong convexity of the optimization problem as long as we use positive definite kernel (e-g. radial basis kernel, polynomial kernel, etc.). Similarly, for SGD, the smoothness and Lipschitz continuity of the loss function are preserved, as the transformation affects only the inner product computations, which is linear, and does not alter the fundamental properties of the objective function. Thus, if our original problem satisfies the conditions of LOO stability of RLM and SGD, the kernel trick enables the model to capture nonlinear patterns the data while ensuring that the theoretical guarantees remain intact.
By integrating the kernel trick, we revisit the scenarios in Section where we initially considered synthetic data examples using standard robust linear regression methods. For our experiments, employed the radial basis function (RBF) kernel KRBF(I, (I, x²) exp
| 2
and the polyno-
mial kernel (I, x') = (af x'' + c)d, both chosen for their ability to model complex nonlinear relationships effectively. For hyperparameters, we chose a 0.1, e = 1, and d = 2. We compared these results to the outcomes in Section 4 and this can be theoretically viewed kernel robust regression using a linear kernel.
special case of
As shown in Figure LO0 100-Sttboe StabCP continues to perform reliably under both settings settings with- out any loss of coverage, validating its adaptability to more sophisticated model structures. More- over, compared to the linear setting, the of the kernel trick in nonlinear settings leads to notable reduction in prediction interval length. This reduction highlights the ability of LO0-StabCB with kernel trick to provide more precise predictions while capturing the complex patterns inherent in data, thereby enhancing its practical utility.
A.2 DETAILED INSIGHTS INTO NONCONVEX OPTIMIZATION
In Section 3.2.3
we derived stability bounds for SGD under nonconvex settings. Here, we provide additional details on the derivation and implications of these bounds.
13

---

Published as a conference paper at ICLR 2025
Linear Setting
Nonlineur Setting
1.0
1.0
Cuverage
1.8
0.5
SpliCP
SplaCP
Length
2-
Sphnt
RO-SacC
LOO-SmbCr
SpleCy
RO-SWACP
Log-time (logisec.)
SpinCC
RO-SubC?
L00-SmhCP
SpleCC
No Kenel
RBF Keradl
Polyzomial Kemel
Figure 5: Comparison of CP methods using kernelized technique.
In the convex case (Theorem the stability bounds for SGD are given by:
1,0 = Rn "Vsppt5 T.j
RO 2 yVsPu+j-
Tij
On the other hand, for the nonconvex case (Theorem term R
4p. these bounds are modified include the
LOO fJ
= RR MiPptts
RO Tij
2R* nj "PiPtti
where R E R - N² and (1= myp:). Note that the only distinction in the nonconvex case is that R- replaces R. Hence, Ht can be interpreted as representing the cumulative effect of nonconvexity. This term influenced by the learning rate 7) and the Lipschitz constants of the gradients p0, Specifically, if x = R+ approximates R, aligning with the convex optimization sce- nario. However, when is significantly greater than I, R* can grow exponentially with Rt resulting in overly loose bounds. The practical implication of this result is that 1 and y; significantly influ- ence the tightness of stability bounds. While smaller values of r can mitigate this issue, they may also slow down convergence, creating trade-off between theoretical stability and computational efficiency.
As described in Section 5 we conducted experiments with neural network featuring a single hidden layer and employed approximated stability bounds:
LOO Tif ~ - X X and T.j ~ 2ng -Bnn>>]XXxlll x1]
RO
Although these terms approximate our problem as it were convex, they still capture the interaction between the training and test points in our dataset, providing practical measure of stability. By using these approximations, we adapted our conformal prediction framework without relying on overly conservative worst-case bounds. Alongside the results in Section 5 Figurelo outcomes for a wwo-hidden-layee network with 10 and nodes, respectively, under the same settings.
Our empirical results, shown in Figure 3 and Figure 6 demonstrate that these approximations, de- spite their theoretical looseness, do not compromise the validity of 200-StabCP These findings consistent with prior observations (Hardt et al.) 2016 Ndiaye 2022), where theoretical stability bounds in nonconvex settings are often pessimistic, yet empirical results tend to outperform these expectations.
14

---

Published as a conference paper at ICLR 2025
Coverage
Length
Log-time (log(soc.))
0.5
23-
Bodtaa
Liubetes
Dubeees
Boaton
Dubetts
RO-SaACP
100-SuiCP
Figure 6: Comparison of CP methods with neural networks with two hidden layers under choice of 100.
A.3 ADDITIONAL RESULTS AND DISCUSSION ON BAGGING
While derandomized bagging discussed in 3.2.3 provides conceptual insights into stability, practical bagging methods have internal randomness induced by the resampling scheme. To account for this randomness, here, provide theoretical results the LOO stability of bagging in practice.
The randomness bagging is two-fold. One source is the resampling process, where datasets created by sampling with replacement from the original dataset. Another arises from the base learning algorithm itself, as seen in random forest, where random feature subsets are selected in each bag. The latter can be characterized by random variable & (d(O, 1). Algorithm Algorithm iillustrates the implementation of bagging.
Algorithm 3: Bagging
Input Training set D = {(X,, Yo) Number of bags B, Number of samples in each bag
m
Output: Prediction function f(-) (B) D (-).
for b [B] do
1. Sample bag (b) = -1(0) ..... ( where 1900 lid. U([n]) for j [m]:
Sample seed g(0)_ ~ (10, 1]);
3. Fit model (b) with (b) and (())
end
The prediction function of bagging is inherently random, making it challenging to derive de- terministic stability bound. Nonetheless, based on Theorem 5 we can deduce with high prob-
ability that bagging is LOO stable. In the context of bagging, (z)
1 f (x) and
== f(z) B -ا ( (xx,, where the sample average replaces the expectation compared to deran- domized bagging. The following theorem provides a probabilistic guarantee on the LOO stability bounds for bagging.
Theorem 6. Suppose the conditions of Theorem 5 hold. Then, for any 5 E (0, 1). bagging has the following LO0 stability bounds with probability least
6.
LOO (8) yw
22 I-p + log
4
with 1 (1 2) 1 where i ranges in [n]] U fn + for each 1 S m.
The implications of Theorem 5 and Theorem only the minimal assumption that the base model fitting algorithm used in bagging has bounded output. This suggests that building the stability of bagging, Wang et al. (2023) extended the results to the stability of random forest. Their key insight was that random forest utilize weak decision trees as their base model fitting algorithm, and the final output of decision tree is always determined the average of the responses
aare as follows. Note that the above theorem requires
can applied to a wide range of algorithms. For example,
15

---

Published as a conference paper at ICLR 2025
in the training data it uses. As result, it is straightforward to that the output of decision tree cannot exceed the range of the responses in the training set. Moving forward, these insights can serve foundation for exploring stability guarantees in other complex learning algorithms.
B COMPARISON WITH DERANDOMIZATION APPROACHES
In this appendix, we extend our numerical experiments to include comparisons with derandom- ization approaches (Solari & Djordjilovid 2022 Gasparin & Ramdas 2024), which are potential alternatives to LO0-St abCP in terms of reducing the variability of SplitCP. Specifically, these methods differ from Spli SplitCP, which relies on a single data split, by merging multiple prediction intervals constructed from various splits into one final prediction interval.
Linear Setting: RLM
Linear Setting: SGD
Nonlinear Setting: RLM
Nonlinear Settng:: SGD
Mi sybi????
Lenasace
Splac
ABM Seire
Mas Sparcy
Rik Spocc
spack
ABM snice
Lengih
Spice
Mi1-poort
Space
JBM Splie
Spice
FBM SMM- Mis-pokc
Ionsarr
JBM Spice
Lun time (lugisecc
15
stor?
gea??
Spice
spicc
Londuc
Figure 7: Comparison of CP methods including derandomization approaches on synthetic datasets.
Among these, two notable methods have been proposed in the literature. Solari & Djordjilovćd (2022) were the first to propose this approach. They generated split conformal prediction intervals with - -f validity from multiple data splits and then derived final prediction interval through ma- jority voting (i.e., the range covered by more than half of these intervals). They showed that this final interval maintains 1 validity. We refer to their method MM-SplitCB (Majority Multi-Split Conformal Prediction). Meanwhile, Gasparin & Ramdas (2024) focused on the exchangeability of each prediction interval derived through MM- Splippiiieee CCP. Building this property, they proposed an alternative aggregation technique that produces tighter yet still valid prediction intervals by apply- ing a majority vote correction. We denote this method as EM- EM-Sp1 Split(t (Exchangeable Multi-Split Conformal Prediction). For further details on these methods, we refer readers to Solari & Djord- jilović 2022 ; Gasparin Ramdas (2024).
We compare the performance of these two derandomization techniques with our proposed method, LCO-StabCP. To this end, we applied the methods to the settings described in Section and Sec- tion For MM-Spl i tCP and EM-Spl itCP, we merged 30 splits. Figures and 8 present the results on synthetic and real datasets, respectively. From the results, we observe that variabil- ity in coverage and interval length produced by MM MM-SplitCP and EM-Split is noticeably lower than that SplitCP, indicating that these derandomization techniques effectively reduce the internal variability of data-splitiing approaches.
However, we also find that the average coverage of MM-SplitCP and EM-SplitC2 is gener- ally higher than the predetermined level, suggesting that these derandomization techniques tend to produce conservative intervals. Furthermore, both methods require significantly more computa- tional time, which be attributed to their reliance on multiple model fits, unlike SplitCt and
16

---

Published as a conference paper at ICLR 2025
Bosion Selting: RLM
Besium Seliing: SGD
Diabdies Settnn:: RLM
Disocics Settnn SGD
81
Speic
Aar Spic
Spor?
100 100-00c
Spice
Moxppac
fir fpric
100 soae
Spoce
Jerspaca
100 lon-
12
101
$oic7
Stir?
Mi-
Soice
1/09-
Log litze (lagfoecc))
15
12
Seop
lett spbre
Spacy
AS SHccp
100 micc
Seaco
MB MSS
Spicc
Spak?
AM
ABM
Figure Comparison of CP methods including derandomization approaches on real datasets.
LOO-StabCP, which rely a single model fit. In contrast, LO0-StabCP produces tight and stable intervals while maintaining reasonable coverage. These results underscore the computational These findings are consistent across both synthetic and
efficiency and precision of real data scenarios, showcasing the adaptability and efficiency -tabC compared to other derandomization methods.
C IMPLEMENTATIONS OF CONFORMAL PREDICTION METHODS
C.1 ORACLE CONFORMAL PREDICTION
Algorithm 4: (Orac leCP) Oracle Conformal Prediction Set
Input Training set D = {(X,, Yo) test sets Dreet = {(Xn+j, Yn desired
coverage
Output: Prediction interval Cgracle (Xa+s) for each j E [m].
for j [m] do
Fit the prediction function F, on Vn+s;
Compute non-conformity scores on D. Ditts: Sty = =1= [x(x,) for [m] (n + s}:
3. Compute prediction interval:
Coracle (Xn+j) (Xn+s) + Q1 Q1-a((8,,) U(S++is))l:
end
17

---

Published as a conference paper at ICLR 2025
C.2 FULL CONFORMAL PREDICTION
Algorithm 5: (Fu1ICP) Full Conformal Prediction Set
Input Training set D ((X,, Yi) test points (Xn+s) search grid 9, desired coverage - a.
Output: Prediction interval Ch (Xx+s) for each j [m].
for j E [m]] do
for y E G do
Fit the prediction function f on Dy:
Compute non-conformity scores on D: S = =Y; (xx)) for [n]:
Compute quantile value 21-a(15, i.j li {oo});
end
Compute prediction interval
Chull ja (xn-j)= = {y E g S Sh+ss S Q1-a(15% (
end
C.3 SPLIT CONFORMAL PREDICTION
Algorithm 6: (SplitCP) Split Conformal Prediction Sct
Input : Training set Dirain = {(X,, Yj) HiE calibration set Dralib {(X,, Ii test points {-x++J)=1 desired coverage a.
Output: Prediction interval Cypch (Xn+j) for each j [m]]
1. Fit the prediction function Firain on Derain'
2. Compute non-conformity scores on Dealib: S = ||; Peraii (X:)l for E Tealib: for j E [m] do
Compute prediction interval Caplit ja (Xn+s) = [fraai (Xn+s) + Q1-a(15)))Ezan)) U foot))];
end
C.4 REPLACE-ONE STABLE CONFORMAL PREDICTION
Algorithm 7: StRbCS) Replace-One Stable Conformal Prediction Set
Input Training set D = [(X,, Y:) test points (X k initial guesses (Ün+s im desired coverage
Output: Prediction interval CRa (Xn-;) for each j E [m]]
for j [m] do
Fit the prediction function F, on D
Compute (guessed) non-conformity scores on D: = |Y; [xX))) for [n]]
Compute stability bounds RO for E [n] {n an++j +
4. Compute prediction interval:
Cg (Xn+)) = [f, + (Qi-a([S) T 1 Uf2o)) + -
Ro1n
end
18

---

Published as a conference paper at ICLR 2025
D IMPLEMENTATIONS OF LOO STABLE ALGORITHMS
D.1 REGULARIZED Loss MINIMIZATION
Algorithm 8: (RLM) Regularized Loss Minimization
Input : Training set D = {(X,, Y)
Output: Prediction function f(-) fg(-).
1. Compute optimal parameter 0 == arg m Ei (oX,), + +(0)):
D.2 STOCHASTIC GRADIENT DESCENT
Algorithm 9: (SGD) Stochastic Gradient Descent (with Random Reshuffling)
Input Training set D [(X,, Y.) number of epochs R, step size n, initial value 0g. Output: Prediction function f(-) fz(.).
1. Initialize parameter := Po:
for r E [R]
2. Sample a permutation ı of [n] uniformly at random;
for E [n] do
3. Update parameter 0 = 0 - Vo fo(xx)))
end
end
4. Set the final parameter 0 ;= 0;
E USEFUL LEMMAS
Lemma (Lemmaa 13.5 in Shalev-Shwartz Shwartz & Sen-David (0114). Let g, : :R - R be comve function and X-strongly convex function, respectively. Then, g is X-strongly convex. 2. Let 9: TRP + R be Å-strongly convex and minimize 9. then, for any I,
g(x) -g()) 2 2
x y|1
Lemma 2 (Lemma 3.6 in Hardt et al. (0166). Ler g R R be function such that Vg R +
R is a Lipischhitz. Define h R R such that h(0) = B a Vg(0) with S 2/4. Then, is
(1 + -ippsciz If 9 is in addition convex, h is 1-Lipschitz.
F PROOFS OF THEOREMS
F.1 PROOF OF THEOREM
Proof. By Definition 2 we have SY, I S; + 1.j
.L.00 for E [n] and j = [m]. Similarly, for any S 5 "tjs" Therefore, for any j. the following holds for all *+jJ
j. we have ly - f(Xn+s))
.000
contained in clull (Xn+z):
1.00 by f(Xn+)) - 21 + +1
1,00' 1 U (oo)),
which is equivalent to
y E [f(X + (Qi-a (1S, + Ti.j L101 U 100 = This directly implies C (Xn+s) 2 Ci (Xn+j) and hence P(Yntj E cl.0 cl.00((444)) (Xn+s)) 2 IP(Yn+s E cfull (Xn+z)) 2 1-a,
for any choice of a.
19

---

Published as a conference paper at ICLR 2025
F.2 PROOF OF THEOREM 2
Proof. For E y and E [m]] define ()( = पF ( Jx.)) + ely, Jo(n+s)) +
2(0) and F(0) = n = (X.)) + 2(0). Then, 0y = arg mingee F)(() and Ø
arg mingee F(0).
We begin by proving the LOO algorithmic stability, Fix y and and suppose that 100 01 s 2p0+ Then, for all i E [n] U {n + 5} and 2 E y. A(++1)
[S(2. (xx,)) ((2, S (X,) f(X)I = =n15ay (Xi) - fa(x,))
S yu:100 01
2yv:(pnt3 +
A(n Mn++1)
The first and the second inequalities follow from the Lipschitz property of non-conformity score function and the prediction function, respectively. Therefore, it suffices to obtain the bound of
| 0| assumed above. By the first part of Lemmal | Fl and F are X-strongly convex functions
of f. Using the second part of the Lemma]
1 we have:
1100011 F3
( (0) (0))
(F(O) - F(0))}
(9)
+ fo fg(Xx+))) - Ely, foy (Xn+j)) + 200) 200)))
{E(y fg (Xn+))) E(v. Ely. Jay (X++z)) + 2(0) ((09)}
The last inequality follows from the optimality of 0. Now, by the Lipschitz property of the loss function, we have:
Ely. fa(Xn+))) E(y, Fay (Xn+s)) Pnt,110 0011
(10)
On the other hand, again by the optimality of 8, it holds that
0 s F(Oy) F(0)
Σ (00Y (xy()))) e(Y, (x(,)) +000) - 2(00)
which implies
20 200 000 Ø
(11)
by the Lipschitz property of the loss function. Finally, combining TT) and to get +P)++++p) A(n+1)
100 ` <
For the RO algorithmic stability, fix y. T. and j. By the similar arguments as for 9 we have
110 - -0910 <
+ (e loy (Xa+s)) Ely. Jöy (Xn+s))} +
n + 1 { (((ū, Jāy (Xm+s)) - ((T, fay (Xn+s))}
< 2pn+J 04 0/11 |||
and this implies 10/ -011 <
4p The rest of the proof is similar to the previous case.
Ma+1y)
20

---

Published as a conference paper at ICLR 2025
F.3 PROOF OF THEOREM 3
Proof. We start with proving the case of RO algorithmic stability first, for clearer presentation.
R is straightforward. Let π be an arbitrary permutation of [n + 1] and k be such that Tn = n + 1. Fix
Also, we only prove the case of j = 1 and R = 1 since extending to the case of
and y. Let (0% oy ,, 0% 11 and (0 04 ..... 0 # be the updating sequences of SGD sharing for Dÿ and DJ, respectively. Note that f = fr fok., and f = f = foR_. As in the proof of
Theorem we first bound the distance between the two terminal parameters, 100 0 +
Let us first consider the case of k for all i = [n]] since for SGD update, the two sequences share the first n data points as well as the initial parameter. Therefore, have
1. Then, by the SGD update rule, we can see that 0 0
10 1 = 110%% voVoly Joy (or - 10 VVV loz (X++1)))I
$ n/ Vol(y, for (Xn+1))ll + + VlV for (Xn+1))ll
< 21px+1.
Here, we used triangle inequality, and then the Lipschitz property of loss function.
Now, consider the case of & < + 1. If i k. by the similar argument, we can show that 110" -0 < 10 0% 11 + 21 Otherwise, if o k. by Lemma 2 with the choice of := 7, P = Pm; S 3, and (0)
xx(x;;)) we have:
10" - 0.1 - 1110%-1 - V)Vol( n.. Soy (X )) -00 10-10-1-100 - (xx.)))))1
(12)
$ |10| 000 l|,
since ((Y=u, Fo (x()x,)) is convex. Unraveling the recursion from the above two inequality, we get |10 0% 2 l| < 110 - لل' + 21ppx+1 = 21pp+11- The last equality holds since the two updating
sequences share the common initial value. The remaining parts follow similarly to the proof of Theorem 2
Next, to prove the LOO algorithmic stability, fix y and let मं -=i,...,,,, 7/, be the sequence obtained from π by excluding the kth entry. For example, if we choose n = 4 and π = (3. 2, 1, 4), then A and n' (3, 1, 4). Then, can be shown that n' an arbitrary permutation of [n]. Define an updating sequence of SGD, (0o, 01.....,,, (2) for D induced by i', f f fo.. Note that t 0% As the case of the RO algorithmic stability, it suffices to show that |10 0n S 7p++1-
If l then we have 0 0, for i [m]. Therefore, it follows that
1 M++1
0. 0 Volo( fay (Xn+1))3 0, // Vl fox (X.+1))Il
S nPt+j
For the case of & < + 1 and further remaining parts, we can follow the same procedure used in the RO algorithmic stability.
F.4 PROOF OF THEOREM 4
Proof. The overall structure of the proof is almost identical to that of Theorem 3 Again, let us focus on the proof of RO stability with / - 1 first. Recall that in that proof, the convexity assumption was used only in (2).. Since we have discarded the convexity assumption of ((Y,,, (X,,,) )) by Lemma V fo(Xx.) is replaced from to + mppm. That is, we obtain the following recursive inequalities:
2 agaain, the Lipschitz constant of h0)
10000 - -0 < |10%_ - الام || + 21p if i i= h
(13)
119+=)))) 110 ال1حم if i<k k.
21

---

Published as a conference paper at ICLR 2025
Considering |00 - 0, unraveling these inequalities yields
x++1
10 1
0a+ill 11 -
II (1 + m/
2mp
VimA++1
n++1
II (1 + m9mm))
2mp
i=1
II (1 + mp:)) 1=1
2mpn+s
287potjj
since 1p;; > 0 by definitions. Extending this to the case of R >> is not as straightforward as the proof of Theorem 3 hence we also present the corresponding proof. In this case, we can use induction. Set R > and let E [R]. Suppose that up to (r 1)th epoch, the difference of parameter
is bounded by 2
Σ 1== 12*
MPn++5 Then, rth iteration can be treated as the case of R = 1 with
|10 0/ || 2 E N²*
MPn+j-- In this case, unraveling 13 yileds
n-1
10 - x+ s
(1 + mpp))
+ mPr.) )
1108 0g1 + 2mp
ji=++1
II
(1 + Nppx))
np )
Σ nr Σn
Mpu+s + 2mputs
\i=k+1
n+1
(1 + memr)) ]
S 2mpa+s
II + mpm)))
Σ nー
+
II
Epple
a=1
iin+1
r-1
< 2nmPPots
+
2
R
nPn+j-
Since we already proved the case of r = 1, this completes proof for RO stability. For the LOO stability, we can use the same reasoning.
F.5 PROOF OF THEOREM 5
Proof. Fix y) x y and j E [m]. Due to the symmetry of the resampling scheme, i.c., sampling uniformly with replacement, we have
f(x) E (3 (x) 12 + 1
Therefore, using the above facts along with the Lipschitz property of the non-conformity score function, we get
|S(2. (()) S(z, S(z,f)) < ()(x) - F(x)
= E | (x:) - EE (00 + E +
=7 E [1p (x) - E [ (x)
+ $ r|
Next, by the definitions of conditional expectation and covariance,
E 12 (x)
R.. (1((0)))))
(x))
$
P(n + 1 r) F.
(x) (x) [1(()()000)
(o)) } 1 1 + 11
Pn++177) Cov (x)
22

---

Published as a conference paper at ICLR 2025
Combining the above results, we have
- f())) - 1-p Cov
(14)
where p = ( 1- (1 - 1m Furthermore, it holds that
Cov (19.10) (z)), Im + rr) - Vaa (17)0)(a)) Var (1 +1 rr)
w² p(1 p)
Wij 2
vp(1 - p)).
Here, the first inequality follows from the Cauchy-Schward inequality. For the second inequality, apply Popoviciu's inequality for variance and the properties of the Bernoulli distribution. Sub- stituting this bound into (14) completes the proof.
F.6 PROOF OF THEOREM
Proof. Fix (x. v) E X x y and j E [m]. Let (x) and (xx) denote the predictions correspond-
ing to bagging, and let f7.00 (x) and (x) denote the predictions corresponding to derandomized bagging. Then,
15(2.fy(x)) 5(2, f(x))) s < (p)(()) F(oo)
=7 -T((T](0) 13000 (x)) ( + (x)
- No)
s (1]1)/() P3 0 (x) + - + 70 - f(x))
(15)
Consider each term on the last line of
15
For the first term, note that
1
(b) (x) - E (1)00
B
Since each single prediction py pu.(0) Hoeffding's 's inequality, we have
(x) is almost surely bounded within an interval of range wy, by
P - -3) st) 2 1 - exp (-2Bt//u/)
for any t > 0. Setting & = 2expl -Bt? /wz) yields
PP - (z)) - V
w2 2B
4
8
log
5
2 1
2
Similarly, for the third term, obtain an identical bound:
[ s
8
log
2 1
2B
2
For the second term, direct application of Theorem 5 gives the following deterministic bound:
pr. (x)
(x))
s 7
p
2
V
1-p
23

---

Published as a conference paper at ICLR 2025
Combining all the bounds for the three terms in probability at least 1 6,
13
using the union bound, have that, with
(t)) S(z, (()) 57
V
log
4
W
p
log
4 σ
2B
2
P
2B
(5)
4
2
1-
+
1
B
log
G DETAILS OF NUMERICAL EXPERIMENTS
G.1 DETAILS OF ALGORITHMM
The configurations satisfy the assumptions of Theorem 2 and Theorem 3 allowing us to compute the stability bounds concretely. First, for RLM, the following stability bounds were used. For i Un]
U {m + j} for each j E [m].
LOO
2e Xill
[Ixntsil
+ n Σ
RO Ti
4e|1 X Xn+
TE X(n + 1)
Next, the stability bounds for SGD are as follows:
LOO
Rme X; |||| Xn+
RO
i.j
G.2 ADDITIONAL RESULTS FROM SECTION
Cracl eCP
Pul
Sp1 i t:P
RO-StabCP
L0O-StabCP
Coverage
0.903 (0.040)
0.896 (0.043)
0.903 (0.060)
(0.009)
(0.039)
RLM
Length
3.272 (0.250)
3,300 (0.257)
3.455 (0.514)
3.442 (0.257)
3.442 (0.257)
Time
3.201 (0.172)
176.783 (15.704)
0.017 (0.006)
3.190 (0.176)
0.035 (0.008)
Linear
Coverage
0.903 (0.041)
0.896 (0.043)
0,900 (0.059)
0.911 (0.040)
0.906 (0.040)
SGD
Length
3.252 (0.250)
3,300 (0.257)
3.420 (0.557)
3.464 (0.259)
3.405 (0.259)
Time
0.720 (0.087)
19.320 (2.018)
0.005 (0.003)
0.720 (0.075)
0.009 (0.005)
Coverage
0.892 (0.045)
0,886 (0.047)
0.893 (0.059)
0.897 (0.044)
0.897 (0.044)
RLM
Length
3.659 (0.317)
3.690 (0.340)
3.812 (0.554)
3.828 (0.344)
3.827 (0.344)
Time
3.289 (0.219)
163.101 (22.120)
0.017 (0.005)
3.275 (0.221)
0.038 (0.010)
Nonlinear
Coverage
0.892 (0.045)
0,886 (0.047)
0.895 (0.062)
0.900 (0.043)
0.894 (0.044)
SGD
Length
3.641 (0.318)
3.690 (0.340)
3.855 (0.612)
3.849 (0.345)
3.789 (0.345)
Time
0.732 (0.074)
17.425 (2.206)
0.005 (0.003) 0.746 (0.093)
0.009 (0.005)
Table 2: Mean (and standard deviation) of empirical coverage, average prediction interval length, and execution time across 100 iterations for each scenario in simulation.
24

---

Published as a conference paper at ICLR 2025
G.3
ADDITIONAL RESULTS FROM SECTION 5
OracleCP
FullCP
SplitC2
RO-StabCP
L00-StabCP
RLM
0.920 (0.273)
0.910 (0.288)
0.910 (0.288)
0.920 (0.273)
0.920 (0.273)
Boston
SGD
0.900 (0.302)
0.920 (0.273)
0.910 (0.288)
0,900 (0.302)
0.900 (0.302)
RLM
0.910 (0.288)
0.900 (0.302)
0.890 (0.314)
0.910 (0.288)
0.910 (0.288)
Diabetes
SGD
0.920 (0.273)
0,910 (0.288)
0.920 (0.273)
(0.256)
0.920 (0.273)
RLM
0,906 (0.031)
0.897 (0.031)
0.898 (0.040)
0.903 (0.030)
0,905 (0.030)
Boston
SGD
0,905 (0.029)
0.901 (0.032)
0,901 (0.036)
0.910 (0.028)
0.906 (0.029)
100
RLM
0.900 (0.035)
0.889 (0.037)
0.894 (0.043)
0,900 (0.035)
0,900 (0.035)
Diabetes
SGD 0.902 (0.031)
0.890 (0.036)
0,902 (0.037)
0.914
0.906 (0.031)
Table 3: The mean (and the standard deviation) of empirical coverage over 100 iterations for each scenario on Boston Housing and Diabetes datasets.
G.4 ADDITIONAL RESULTS FROM SECTION
cfBH
RQ-cFBH
LO0-cfBH
FDP
0.0928 (0.0713)
0.0038 (0.0115)
0.0657 (0.0617)
q 0.1
Power
0.6319 (0.2053)
0.3041 (0.1452)
0.6744 (0.1295)
Time
0.0037 (0.0006)
0.2976 (0.0114)
0.0060 (0.0011)
FDP
0,2000 (0.0807)
0.0602 (0.08133
0.1836 (0.0560)
g = 0.2
Power
0.9277 (0.0838)
0.6522 (4514
0.9430 (0.0486)
Time
0.0037 (0.0005)
0.2971 (0.0100)
0.0060 (0.0002)
FDP
0.2882 (0.0806)
0.2483 (0.1212)
0.2837 (0.0934)
q 0.3
Power
0.9923 (0.0198)
0.9627 (0.0347)
0.9917 (0.0136)
Time
0.0037 (0.0002)
0.2970 (0.0101)
0.0060 (0.0003)
Table 4: Mean (and standard deviation) of FDP, power, and execution time for three conformal selection methods.
25


Reviews:
[{"review_id": "uNqjmfay9Q", "reviewer": "Reviewer_3RnT", "summary": "This paper proposes Leave-One-Out Stable Conformal Prediction, a novel method to speed up full conformal using algorithmic stability without sample splitting.", "questions": "- L33: Do we require $\\mathcal{Y} \\subseteq \\mathbb{R}$? Do we require the marginal distribution $P_Y$ is continuous for the non-conformity scores to be uniformly distributed (L81)?\n- L34: Is D_test drawn from the same distribution $P_{X,Y}$ as D? Is it iid drawn? If yes, then is it equivalent to consider a single test example (e.g., Equation (1) only need to hold for one data point instead of for all $j \\in [m]$)? If not, then why all non-conformity scores are exchangeable (L78)?\n- L81: Does this hold for any alpha in [0,1]? How do we obtained this from the fact that the rank is uniformly distributed over $\\{1, \\dots, n+1\\}$? \n- L81:` $\\mathcal{Q}_{1-\\alpha}$` is not defined. Is it lower quantile function `$\\mathcal{Q}_{p}:= \\inf \\{x: F(x) \\geq p\\}$`?\n- L86 (Equation 2)\" Shouldn't $1-\\alpha$ be slightly increased to $\\frac{\\lceil (1-\\alpha)(n+1) \\rceil}{n}$ for this to hold in finite sample? See Equation (19) of https://www.stat.berkeley.edu/~ryantibs/statlearn-s23/lectures/conformal.pdf.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is clearly written and easy to follow.", "weaknesses": "- Typos and minor issues\n\t- L103: notation [1:m] is not defined\n\t- L190: the objective function (is) often highly nonconvex", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Gt5p4GtvFn", "reviewer": "Reviewer_Rbu1", "summary": "The paper proposes Leave-One-Out Stable Conformal Prediction (LOO-StabCP) to speed up full conformal using algorithmic stability without sample splitting for better balance of computational efficiency and prediction accuracy. This method is much faster in handling a large number of prediction requests compared to existing method RO-StabCP based on replace-one stability. The authors show that their method is theoretically justified and demonstrates superior numerical performance on synthetic and real-world data.", "questions": "* I think it is necessary to discuss more and carefully about applying LOO-StabCP to deep learning algorithms for reasons outlined in the weaknesses box.\n\n* As introduced in section 1, derandomization methods can address the issue of decreasing accuracy causing by randomly split but increase computational cost. I think it is better to demonstrate the performance of some derandomization method and compare it with LOO-StabCP to illustate the differences between the two in all aspects. \n\n* The authors compute stability-adjusted p-values for multiple selection in section 6. I think it is better to verify the validity of p-values in (7) and state it as a proposotion for completeness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper proposes a novel method to address the problem in conformal prediction lies in balancing computation cost with prediction accuracy.\n* Numerical results in this paper show that the proposed method achieves a competitive average coverage and a higher power compared to existing methods.", "weaknesses": "* The authors introduce leave-one-out algorithmic stability for stability correction. However, it is difficult to calculate the stability bounds $\\tau_{i,j}^{\\mathrm{LOO}}$ when a complex deep learning algorithm is chosen to fit the model. \n\n* When trying to derive the LOO stability bound of RLM and SGD described in section 3.2, similar problems are encountered as mentioned above: the conditions in Theorems 2 \\& 3 are difficult to verify. \n\n* Numerical experiments are insufficient: the covariates of synthetic data are set to be independent; the prediction algorithms used are all robust linear regression. More complex settings and algorithms should be considered and compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "sDNEuzePml", "reviewer": "Reviewer_LXUa", "summary": "This paper introduces Leave-One-Out Stable Conformal Prediction (LOO-StabCP), a novel conformal prediction approach that enhances computational efficiency for multiple predictions while ensuring coverage guarantees. LOO-StabCP builds on prior work by Ndiaye (2022), which utilized replace-one stability, by leveraging leave-one-out stability to require only a single model fit on the training data, regardless of the number of test points. This eliminates the need for computationally intensive refits for each individual test point. The authors validate LOO-StabCP with theoretical stability bounds for regularized loss minimization (RLM) and stochastic gradient descent (SGD)--methods widely used in modern machine learning. Extensive experiments on synthetic and real-world datasets show that LOO-StabCP matches or exceeds existing methods in predictive accuracy, efficiency, and computational speed.", "questions": "Here is a list of questions and minor suggestions.\n\n- *Line 34:* I think $Y_{n+j}$ should not be included in $\\mathcal{D}_{\\textrm{test}}$.\n- *Line 58:* Consider using “RO-StabCP” for clarity instead of “in Ndiaye (2022),” which is already referenced in the preceding paragraph.\n- *Line 70:* The phrase “guess $Y_{n+j}$ with $y$” may not read clearly.\n- *Line 75:* Specifying the range, e.g., by “…swapped for $i, i' \\in [n] \\cup \\{n+j\\}$” would be clearer.\n- *Line 90:* Typo: $y$ should be replaced by $i$.\n- *Line 103 (Definition 1):* (1) Define $[1:m]$ notation; (2) clarify the quantifier regarding $\\mathcal{D}$.\n- *Line 108:* “Recall” may be clearer than “Let.”\n- *Line 140:* Consider adding remarks right after Definition 2 to discuss (1) the pursuit of adaptive parameters rather than uniform bounds to obtain sharper stability estimates, (2) the practicality of assuming known parameters, and (3) how these parameters impact the accuracy and robustness of prediction intervals. Although these points are addressed in later sections, readers would benefit from a brief mention here.\n- *Line 154:* Using varied parenthesis sizes or brackets might improve readability.\n- *Line 202:* Recall the meaning of the augmented data $\\mathcal{D}^y_j$ from Line 70 for context.\n- *Line 367:* The statement “This leads to wider prediction intervals for all methods, and particularly for SplitCP, more variability in prediction interval length” is not clear to me. It suggests the prediction interval of SplitCP becomes particularly wider due to the increase $m=1 \\to m=100$.  However, SplitCP already appears to vary similarly at both $m=1$ and $m=100$, while the other methods vary more at $m=100$.\n- *Line 369:* While the authors note that derandomization (Gasparin \\& Ramdas, 2024) would incur extra computational costs, how does LOO-StabCP compare with derandomization in other aspects such as prediction accuracy, coverage, and stability?\n- *Line 465:* The comment “Compared to cfBH, our method is more powerful” could benefit from further clarification. How is this conclusion drawn from Figure 3 and Table 3?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes a contribution to conformal prediction by addressing a critical need for efficient uncertainty quantification in large-scale applications, especially when predictions are needed across multiple test points. Building on prior work that used algorithmic stability for conformal prediction, LOO-StabCP introduces a novel approach to leave-one-out stability by treating the model trained on the dataset (=training dataset $\\mathcal{D}$) as one generated by “leaving out” each test point from an augmented set (as noted in Section 3.1 following Algorithm 1). This refinement results in a significant speedup, especially valuable in scenarios with numerous predictions.\n\nThe authors provide a solid theoretical foundation to support their proposed LOO-StabCP by deriving stability bounds for Regularized Loss Minimization (RLM) and Stochastic Gradient Descent (SGD), strengthening the method’s rigor. Additionally, empirical results on both synthetic and real-world datasets effectively demonstrate LOO-StabCP’s advantages in computational speed, prediction interval size and statistical power. The comparison of computational complexity across methods (e.g., FullCP, SplitCP, RO-StabCP), summarized in Table 1, clearly showcases the efficiency gains, and the illustration of practical applications in screening tasks, described in Section 6, highlights the method’s utility.", "weaknesses": "Overall, I believe this is a well-written paper.  However, some refinements in presentation could potentially enhance clarity and completeness, even though it is already quite solid.  Here are some specific suggestions.\n\n**1. Adding Remarks & Prospects for Broader Examples/Applications:**\nAdding comments on the tightness of stability bounds for the RLM and SGD examples in Section 3.2 would improve the interpretability of results, and clarify the sharpness or looseness of the current results. \nAdditionally, while RLM and SGD are valuable examples, discussing potential extensions to other models or methods, along with conjectures or insights about the scope of the applications, would help readers better understand the broader applicability of the proposed approach. Furthermore, this is a minor point, but for improved parallelism between Sections 3.2.1 and 3.2.2, it may be worth noting that RLM and SGD are not strictly parallel choices: RLM represents a problem formulation, whereas SGD is an optimization algorithm used to solve such problems.\n\n**2. Augmenting Experiments:**\nAs one way to o assess the tightness of the proposed LOO-StabCP prediction intervals, the authors could compare the intervals obtained by LOO-StabCP against the tightest possible prediction set with coverage $1-\\alpha$ as a benchmark, which can be calculated in numerical experiments, for instance, using the $\\alpha/2$- and $(1-\\alpha/2)$-quantiles of instantiated predictions from multiple runs.  This comparison would provide further insights into the tightness of the proposed method (as well as other CP methods being considered in the study).\nAlso, broadening the simulation studies to include a wider range of model types would offer greater assurance that LOO-StabCP's performance gains are not specific to the tested settings. Expanding these results, perhaps in an Appendix, would help readers evaluate the method’s effectiveness across diverse applications.\n\n**3. Ensuring Notation Consistency and Simplification:** \nEnsuring that all notation is defined before use (e.g., $[1:n]$) would improve accessibility. Simplifying notation where possible--for instance, by fixing  $j=1$ in Section 2  to reduce complexity without sacrificing rigor--could enhance readability. While the authors may have intended to highlight the dependence on the test point index $j$, simplifying this notation in Section 2 and then generalizing back in Section 3 could make the initial section more approachable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "P7ofZrRkET", "reviewer": "Reviewer_VLB9", "summary": "This paper proposes a leave-one-out algorithm stability definition, which the authors utilize to reduce the computational burden of the full conformal prediction method. The finite-sample validity of the prediction interval is proved. The authors have provided some experimental results to show the superiority of the proposed method in computation speed.", "questions": "1. The only issue I care about is whether commonly used lightweight machine learning algorithms like the random forest or simple neural networks can satisfy the LOO stability proposed in the paper. It will be a major issue and I will be willing to raise my score with extra theoretical results.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed method does reduce the computational burden by circumventing model refitting when computing prediction intervals for distinct test points. The computational complexity is then reduced by $m$ times. This is also validated by the numerical experiments.", "weaknesses": "The method proposed by the authors is quite similar to the baseline established by Ndiaye (2022). Given this foundation, the extension presented by the authors appears somewhat straightforward, leading to a limited contribution. While the proposed method significantly reduces computational burden, it relies on the assumption that the learning algorithm adheres to the LOO stability assumption. Since conformal prediction is elegant for its wide applicability as a wrapper around any machine learning model, the examples RLM and SGD discussed in the paper are very limited. This limitation is particularly notable in the current landscape, where sophisticated deep learning models and LLMs are prevalent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)