# Building Conformal Prediction Intervals with Approximate Message Passing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 21 Oct 2024.

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification](https://mlsanity.com/paper/2102.07856/) (2021)
- [Conformal Bayesian Computation](https://mlsanity.com/paper/2106.06137/) (2021)
- [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)
- [Theoretical characterization of uncertainty in high-dimensional linear classification](https://mlsanity.com/paper/2202.03295/) (2022)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [Exact Optimization of Conformal Predictors via Incremental and Decremental Learning](https://mlsanity.com/paper/2102.03236/) (2021)
- [Understanding the Under-Coverage Bias in Uncertainty Estimation](https://mlsanity.com/paper/2106.05515/) (2021)
- [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024)
- [A replica analysis of under-bagging](https://mlsanity.com/paper/2404.09779/) (2024)
- [An Approximate Message Passing Algorithm for Rapid Parameter-Free Compressed Sensing MRI](https://mlsanity.com/paper/1911.01234/) (2019)

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

- [Distributed Conformal Prediction via Message Passing](https://mlsanity.com/paper/2501.14544/) (2025)
- [Accelerating Conformal Prediction via Approximate Leave-One-Out](https://mlsanity.com/paper/2606.31915/) (2026)

## Abstract (arXiv)

Conformal prediction has emerged as a powerful tool for building prediction intervals that are valid in a distribution-free way. However, its evaluation may be computationally costly, especially in the high-dimensional setting where the dimensionality and sample sizes are both large and of comparable magnitudes. To address this challenge in the context of generalized linear regression, we propose a novel algorithm based on Approximate Message Passing (AMP) to accelerate the computation of prediction intervals using full conformal prediction, by approximating the computation of conformity scores. Our work bridges a gap between modern uncertainty quantification techniques and tools for high-dimensional problems involving the AMP algorithm. We evaluate our method on both synthetic and real data, and show that it produces prediction intervals that are close to the baseline methods, while being orders of magnitude faster. Additionally, in the high-dimensional limit and under assumptions on the data distribution, the conformity scores computed by AMP converge to the one computed exactly, which allows theoretical study and benchmarking of conformal methods in high dimensions.