Leave-One-Out Stable Conformal Prediction
Conformal Prediction;Algorithmic Stability;Regularized Loss Minimization;Stochastic Gradient Descent
Yes
No ethics review needed.
- 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)?
- 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)?
- 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\}$? 
- L81:` $\mathcal{Q}_{1-\alpha}$` is not defined. Is it lower quantile function `$\mathcal{Q}_{p}:= \inf \{x: F(x) \geq p\}$`?
- 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.
This paper is clearly written and easy to follow.
This paper proposes Leave-One-Out Stable Conformal Prediction, a novel method to speed up full conformal using algorithmic stability without sample splitting.
- Typos and minor issues
	- L103: notation [1:m] is not defined
	- L190: the objective function (is) often highly nonconvex
Yes
No ethics review needed.
* 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.

* 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. 

* 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.
* The paper proposes a novel method to address the problem in conformal prediction lies in balancing computation cost with prediction accuracy.
* Numerical results in this paper show that the proposed method achieves a competitive average coverage and a higher power compared to existing methods.
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.
* 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. 

* 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. 

* 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.
Yes
No ethics review needed.
Here is a list of questions and minor suggestions.

- *Line 34:* I think $Y_{n+j}$ should not be included in $\mathcal{D}_{\textrm{test}}$.
- *Line 58:* Consider using “RO-StabCP” for clarity instead of “in Ndiaye (2022),” which is already referenced in the preceding paragraph.
- *Line 70:* The phrase “guess $Y_{n+j}$ with $y$” may not read clearly.
- *Line 75:* Specifying the range, e.g., by “…swapped for $i, i' \in [n] \cup \{n+j\}$” would be clearer.
- *Line 90:* Typo: $y$ should be replaced by $i$.
- *Line 103 (Definition 1):* (1) Define $[1:m]$ notation; (2) clarify the quantifier regarding $\mathcal{D}$.
- *Line 108:* “Recall” may be clearer than “Let.”
- *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.
- *Line 154:* Using varied parenthesis sizes or brackets might improve readability.
- *Line 202:* Recall the meaning of the augmented data $\mathcal{D}^y_j$ from Line 70 for context.
- *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$.
- *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?
- *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?
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.

The 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.
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.
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.

**1. Adding Remarks & Prospects for Broader Examples/Applications:**
Adding 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. 
Additionally, 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.

**2. Augmenting Experiments:**
As 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).
Also, 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.

**3. Ensuring Notation Consistency and Simplification:** 
Ensuring 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.
Yes
No ethics review needed.
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.
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.
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.
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.
@inproceedings{
anonymous2024leaveoneout,
title={Leave-One-Out Stable Conformal Prediction},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Bt1vnCnAVS},
note={under review}
}
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 {\bf L}eave-{\bf O}ne-{\bf O}ut {\bf Stab}le {\bf C}onformal {\bf P}rediction (\texttt{LOO-StabCP}), a novel method to speed up full conformal using algorithmic stability without sample splitting.
By leveraging \emph{leave-one-out} stability, our method is much faster in handling a large number of prediction requests compared to existing method {\tt RO-StabCP} based on \emph{replace-one} stability.
We derived stability bounds for two popular machine learning tools: regularized risk minimization (RLM) and stochastic gradient descent (SGD).
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Conformal Prediction Algorithmic Stability Regularized Loss Minimization Stochastic Gradient Descent
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/86ef23892652eb5301b5c2f1c33922eebfd56b22.pdf
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/b391dd74b3ba0ecece9b2f0c2ff678ff4a612ac0.zip
Leave-One-Out Stable Conformal Prediction
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission