# Computing Full Conformal Prediction Set with Approximate Homotopy

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2019.

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Stable Conformal Prediction Sets](https://mlsanity.com/paper/2112.10224/) (2021)
- [Conditional Selective Inference for Robust Regression and Outlier Detection using Piecewise-Linear Homotopy Continuation](https://mlsanity.com/paper/2104.10840/) (2021)
- [JAWS: Auditing Predictive Uncertainty Under Covariate Shift](https://mlsanity.com/paper/2207.10716/) (2022)
- [Approximating Full Conformal Prediction at Scale via Influence Functions](https://mlsanity.com/paper/2202.01315/) (2022)
- [Exact Optimization of Conformal Predictors via Incremental and Decremental Learning](https://mlsanity.com/paper/2102.03236/) (2021)
- [Root-finding Approaches for Computing Conformal Prediction Set](https://mlsanity.com/paper/2104.06648/) (2021)
- [Exact and Approximate Conformal Inference for Multi-Output Regression](https://mlsanity.com/paper/2210.17405/) (2022)
- [Conformalization of Sparse Generalized Linear Models](https://mlsanity.com/paper/2307.05109/) (2023)
- [Beyond Uncertainty Sets: Leveraging Optimal Transport to Extend Conformal Predictive Distributions to Multivariate Settings](https://mlsanity.com/paper/2511.15146/) (2025)
- [Building Conformal Prediction Intervals with Approximate Message Passing](https://mlsanity.com/paper/2410.16493/) (2024)
- [CLAPS: Aleatoric-Epistemic Scaling via Last-Layer Laplace for Conformal Regression](https://mlsanity.com/paper/2512.01384/) (2025)
- [Interpretable Multivariate Conformal Prediction with Fast Transductive Standardization](https://mlsanity.com/paper/2512.15383/) (2025)
- [A Confidence Machine for Sparse High-Order Interaction Model](https://mlsanity.com/paper/2205.14317/) (2022)
- [Approximating Full Conformal Prediction for Neural Network Regression with Gauss-Newton Influence](https://mlsanity.com/paper/2507.20272/) (2025)
- [Distribution-Free Process Monitoring with Conformal Prediction](https://mlsanity.com/paper/2512.23602/) (2025)
- [Safe Distributionally Robust Feature Selection under Covariate Shift](https://mlsanity.com/paper/2603.16062/) (2026)
- [Accelerating Conformal Prediction via Approximate Leave-One-Out](https://mlsanity.com/paper/2606.31915/) (2026)
- [Though Language Models Err While They Strive: Conformal Prediction for Self-Correcting Scientific Generation](https://mlsanity.com/paper/2607.16704/) (2026)

## Abstract (arXiv)

If you are predicting the label y of a new object with hat y, how confident are you that y = hat y? Conformal prediction methods provide an elegant framework for answering such question by building a 100 (1 - α)% confidence region without assumptions on the distribution of the data. It is based on a refitting procedure that parses all the possibilities for y to select the most likely ones. Although providing strong coverage guarantees, conformal set is impractical to compute exactly for many regression problems. We propose efficient algorithms to compute conformal prediction set using approximated solution of (convex) regularized empirical risk minimization. Our approaches rely on a new homotopy continuation technique for tracking the solution path with respect to sequential changes of the observations. We also provide a detailed analysis quantifying its complexity.