Research map / Learning theory and algorithms / Prediction and decision losses
Leave-One-Out Stable Conformal Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LOO-StabCP, a conformal prediction method using leave-one-out algorithmic stability that fits one model on the training data for all test points, avoiding per-test-point refits of RO-StabCP and sample splitting.
Problem
Full conformal prediction is accurate but slow, split conformal loses accuracy and is variable, and replace-one stable conformal prediction (RO-StabCP) requires refitting the model for each test point when predicting many test points.
Approach
Use leave-one-out stability: compare the model fit on training data alone with the model fit on training data plus one augmented test point (X_{n+j}, y). Since the correction no longer depends on the test-point predictor, a single model fit on D suffices for all m predictions, with stability bounds derived for RLM, SGD, kernel methods, neural networks and bagging.
Key results
- LOO-StabCP computes at roughly the speed of SplitCP and is clearly faster than FullCP and RO-StabCP when predicting many test points (m=100), while maintaining coverage in the synthetic and real-data experiments.
- In the screening application on recruitment data, LOO-cfBH achieves valid FDP control for all tested FDR levels q in {0.1, 0.2, 0.3} and is more powerful than split-based cfBH and faster than RO-cfBH.
- The derived LOO stability bound for SGD is half the RO bound (R eta gamma nu rho vs 2 R eta gamma nu rho), giving tighter intervals than RO-StabCP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LOO-StabCP instead of RO-StabCP for many prediction requests | Stable conformal prediction · Synthetic and real-world data; multiple predictions | computation time | Helped |
| Use LOO-StabCP instead of SplitCP | Conformal prediction · Synthetic and real-world data | prediction interval length | Helped |
| Use LOO-StabCP instead of FullCP, OracleCP, or RO-StabCP | Conformal prediction · Synthetic data | prediction interval length | No clear effect |
| Use LOO-StabCP instead of SplitCP | Conformal prediction · Synthetic and real-world data | coverage probability | No clear effect |
| Use LOO-cfBH instead of cfBH | Conformalized screening · Recruitment data | test power | Helped |
| Use LOO-cfBH instead of RO-cfBH | Conformalized screening · Recruitment data | test power | Helped |
| Use LOO-cfBH instead of RO-cfBH | Conformalized screening · Recruitment data | computation time | Helped |
| Use the RBF or polynomial kernel rather than the linear setting | LOO-StabCP · Synthetic data | prediction interval length | Helped |
| Use MM-SplitCP or EM-SplitCP rather than SplitCP | Derandomized conformal prediction · Synthetic and real-world data | coverage and interval-length variability | Helped |
| Use MM-SplitCP or EM-SplitCP rather than LOO-StabCP | Conformal prediction · Synthetic and real-world data | computation time | Hurt |
Surprising findings
- For SGD the LOO stability bound is exactly half the replace-one bound, because leaving out a point removes one update rather than changing one update's direction.
Limitations
- Stability bounds for nonconvex models such as neural networks are worst-case conservative and the paper uses approximate heuristic bounds in experiments.
- Theory is developed for continuous responses; extension to classification is left open.
Experimental setup
Datasets: synthetic Gaussian AR(1) data Boston Housing Diabetes recruitment data
Benchmarks: synthetic regression simulation Boston Housing Diabetes recruitment screening
Metrics: coverage probability prediction interval length computation time FDP test power
Baselines: FullCP SplitCP RO-StabCP OracleCP MM-SplitCP EM-SplitCP cfBH RO-cfBH
Builds on: full conformal prediction replace-one stable conformal prediction split conformal prediction Benjamini-Hochberg procedure Jackknife+
Closest papers by meaning
- Exploring the Noise Robustness of Online Conformal Prediction (NeurIPS 2025 · similarity 0.88)
- Verifiably Robust Conformal Prediction (NeurIPS 2024 · similarity 0.88)
- Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shift with Unlabeled Data (NeurIPS 2025 · similarity 0.88)
- Reliable Uncertainty Quantification in Machine Learning via Conformal Prediction (AAAI 2025 · similarity 0.88)
- Valid Selection among Conformal Sets (NeurIPS 2025 · similarity 0.88)
- Provably Robust Conformal Prediction with Improved Efficiency (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.