# Exact Optimization of Conformal Predictors via Incremental and Decremental Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [Regression Conformal Prediction with Nearest Neighbours](https://mlsanity.com/paper/1401.3880/) (2014)
- [Criteria of efficiency for conformal prediction](https://mlsanity.com/paper/1603.04416/) (2016)
- [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)

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

- [Stable Conformal Prediction Sets](https://mlsanity.com/paper/2112.10224/) (2021)
- [Approximating Full Conformal Prediction at Scale via Influence Functions](https://mlsanity.com/paper/2202.01315/) (2022)
- [Towards Modeling Uncertainties of Self-explaining Neural Networks via Conformal Prediction](https://mlsanity.com/paper/2401.01549/) (2024)
- [Exact and Approximate Conformal Inference for Multi-Output Regression](https://mlsanity.com/paper/2210.17405/) (2022)
- [A novel Deep Learning approach for one-step Conformal Prediction approximation](https://mlsanity.com/paper/2207.12377/) (2022)
- [Building Conformal Prediction Intervals with Approximate Message Passing](https://mlsanity.com/paper/2410.16493/) (2024)
- [A Confidence Machine for Sparse High-Order Interaction Model](https://mlsanity.com/paper/2205.14317/) (2022)
- [Uncertainty measurement for complex event prediction in safety-critical systems](https://mlsanity.com/paper/2411.01289/) (2024)
- [Enhancing Deployment-Time Predictive Model Robustness for Code Analysis and Optimization](https://mlsanity.com/paper/2501.00298/) (2024)
- [Scaling Full Conformal Image Classifiers](https://mlsanity.com/paper/2609.37298/) (2026)

## Abstract (arXiv)

Conformal Predictors (CP) are wrappers around ML models, providing error guarantees under weak assumptions on the data distribution. They are suitable for a wide range of problems, from classification and regression to anomaly detection. Unfortunately, their very high computational complexity limits their applicability to large datasets. In this work, we show that it is possible to speed up a CP classifier considerably, by studying it in conjunction with the underlying ML method, and by exploiting incremental&decremental learning. For methods such as k-NN, KDE, and kernel LS-SVM, our approach reduces the running time by one order of magnitude, whilst producing exact solutions. With similar ideas, we also achieve a linear speed up for the harder case of bootstrapping. Finally, we extend these techniques to improve upon an optimization of k-NN CP for regression. We evaluate our findings empirically, and discuss when methods are suitable for CP optimization.