# Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2017.

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

- [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)
- [Guaranteed Coverage Prediction Intervals with Gaussian Process Regression](https://mlsanity.com/paper/2310.15641/) (2023)
- [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)
- [Conformal Approach To Gaussian Process Surrogate Evaluation With Coverage Guarantees](https://mlsanity.com/paper/2401.07733/) (2024)
- [Conformalization of Sparse Generalized Linear Models](https://mlsanity.com/paper/2307.05109/) (2023)
- [A note on conditional PAC-efficient reasoning in large language model routing](https://mlsanity.com/paper/2512.03057/) (2025)
- [Beyond Conformal Predictors: Adaptive Conformal Inference with Confidence Predictors](https://mlsanity.com/paper/2409.15548/) (2024)
- [Building Conformal Prediction Intervals with Approximate Message Passing](https://mlsanity.com/paper/2410.16493/) (2024)
- [Interpretable Multivariate Conformal Prediction with Fast Transductive Standardization](https://mlsanity.com/paper/2512.15383/) (2025)
- [Bayesian Conformal Prediction as a Decision Risk Problem](https://mlsanity.com/paper/2602.03331/) (2026)
- [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)
- [On some practical challenges of conformal prediction](https://mlsanity.com/paper/2510.10324/) (2025)
- [Conformal prediction for full and sparse polynomial chaos expansions](https://mlsanity.com/paper/2601.16636/) (2026)
- [Elements of Conformal Prediction](https://mlsanity.com/paper/2603.23923/) (2026)
- [Scaling Full Conformal Image Classifiers](https://mlsanity.com/paper/2609.37298/) (2026)

## Abstract (arXiv)

Conformal prediction is a general method that converts almost any point predictor to a prediction set. The resulting set keeps good statistical properties of the original estimator under standard assumptions, and guarantees valid average coverage even when the model is misspecified. A main challenge in applying conformal prediction in modern applications is efficient computation, as it generally requires an exhaustive search over the entire output space. In this paper we develop an exact and computationally efficient conformalization of the Lasso and elastic net. The method makes use of a novel piecewise linear homotopy of the Lasso solution under perturbation of a single input sample point. As a by-product, we provide a simpler and better justified online Lasso algorithm, which may be of independent interest. Our derivation also reveals an interesting accuracy-stability trade-off in conformal inference, which is analogous to the bias-variance trade-off in traditional parameter estimation. The practical performance of the new algorithm is demonstrated using both synthetic and real data examples.