# Stable Conformal Prediction Sets

arXiv: https://arxiv.org/abs/2112.10224 · HTML: https://mlsanity.com/paper/2112.10224/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 19 Dec 2021.

## Builds on (most cited first, 18 of 18)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Testing for Outliers with Conformal p-values](https://mlsanity.com/paper/2104.08279/) (2021)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)
- [Few-shot Conformal Prediction with Auxiliary Tasks](https://mlsanity.com/paper/2102.08898/) (2021)
- [Conformal Uncertainty Sets for Robust Optimization](https://mlsanity.com/paper/2105.14957/) (2021)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [An Exact and Robust Conformal Inference Method for Counterfactual and Synthetic Controls](https://mlsanity.com/paper/1712.09089/) (2017)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Discriminative Jackknife: Quantifying Uncertainty in Deep Learning via Higher-Order Influence Functions](https://mlsanity.com/paper/2007.13481/) (2020)
- [Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy](https://mlsanity.com/paper/1708.00427/) (2017)
- [Computing Full Conformal Prediction Set with Approximate Homotopy](https://mlsanity.com/paper/1909.09365/) (2019)
- [Exact Optimization of Conformal Predictors via Incremental and Decremental Learning](https://mlsanity.com/paper/2102.03236/) (2021)
- [Safe Grid Search with Optimal Complexity](https://mlsanity.com/paper/1810.05471/) (2018)
- [Making learning more transparent using conformalized performance prediction](https://mlsanity.com/paper/2007.04486/) (2020)
- [Root-finding Approaches for Computing Conformal Prediction Set](https://mlsanity.com/paper/2104.06648/) (2021)

## Built on by (most cited first, 19 of 19)

- [Bayesian Optimization with Conformal Prediction Sets](https://mlsanity.com/paper/2210.12496/) (2022)
- [One-Shot Federated Conformal Prediction](https://mlsanity.com/paper/2302.06322/) (2023)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Conformal Prediction via Regression-as-Classification](https://mlsanity.com/paper/2404.08168/) (2024)
- [Approximating Full Conformal Prediction at Scale via Influence Functions](https://mlsanity.com/paper/2202.01315/) (2022)
- [Exact and Approximate Conformal Inference for Multi-Output Regression](https://mlsanity.com/paper/2210.17405/) (2022)
- [Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern](https://mlsanity.com/paper/2305.11640/) (2023)
- [Conformalization of Sparse Generalized Linear Models](https://mlsanity.com/paper/2307.05109/) (2023)
- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)
- [Leave a Window Out: Modifying the Jackknife for Predictive Inference in Time Series](https://mlsanity.com/paper/2605.30292/) (2026)
- [Leave-One-Out Stable Conformal Prediction](https://mlsanity.com/paper/2504.12189/) (2025)
- [Beyond Uncertainty Sets: Leveraging Optimal Transport to Extend Conformal Predictive Distributions to Multivariate Settings](https://mlsanity.com/paper/2511.15146/) (2025)
- [Constructing Prediction Intervals with Neural Networks: An Empirical Evaluation of Bootstrapping and Conformal Inference Methods](https://mlsanity.com/paper/2210.05354/) (2022)
- [MetaSTNet: Multimodal Meta-learning for Cellular Traffic Conformal Prediction](https://mlsanity.com/paper/2505.21553/) (2025)
- [Robust Conformal Prediction under Distribution Shift via Physics-Informed Structural Causal Model](https://mlsanity.com/paper/2403.15025/) (2024)
- [Approximating Full Conformal Prediction for Neural Network Regression with Gauss-Newton Influence](https://mlsanity.com/paper/2507.20272/) (2025)
- [Conformalised data synthesis](https://mlsanity.com/paper/2312.08999/) (2023)
- [Replicable Conformal Prediction](https://mlsanity.com/paper/2608.23638/) (2026)
- [Calibration Count Reuse: Validity Does Not Determine Efficiency](https://mlsanity.com/paper/2609.25138/) (2026)

## Abstract (arXiv)

When one observes a sequence of variables (x1, y1), ldots, (xn, yn), Conformal Prediction (CP) is a methodology that allows to estimate a confidence set for yn+1 given xn+1 by merely assuming that the distribution of the data is exchangeable. CP sets have guaranteed coverage for any finite population size n. While appealing, the computation of such a set turns out to be infeasible in general, e.g. when the unknown variable yn+1 is continuous. The bottleneck is that it is based on a procedure that readjusts a prediction model on data where we replace the unknown target by all its possible values in order to select the most probable one. This requires computing an infinite number of models, which often makes it intractable. In this paper, we combine CP techniques with classical algorithmic stability bounds to derive a prediction set computable with a single model fit. We demonstrate that our proposed confidence set does not lose any coverage guarantees while avoiding the need for data splitting as currently done in the literature. We provide some numerical experiments to illustrate the tightness of our estimation when the sample size is sufficiently large, on both synthetic and real datasets.