Accelerating Conformal Prediction via Approximate Leave-One-Out

• URL: http://arxiv.org/abs/2606.31915v1
• Date: Tue, 30 Jun 2026 16:21:48 GMT
• Title: Accelerating Conformal Prediction via Approximate Leave-One-Out
• Abstract summary: We accelerate conformal prediction by incorporating approximate leave-one-out (ALO) estimators, and establish coverage and efficiency.<n>Our proof draws on methods developed for analyzing the consistency of ALO cross-validation risk estimators in high-dimensional statistics.<n>We show that the ALO-based methods achieve coverage and efficiency comparable to the exact methods, while significantly reducing the runtime.
• Score: 14.660852843318809
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While conformal prediction provides a general framework for uncertainty quantification in predictive inference, its application is often limited by computational cost. Recent methods, including Jackknife+ and Jackknife-minmax, achieve faster computation by trading a slight loss of efficiency relative to full conformal prediction, but still requires computing leave-one-out refits for all observations. In this paper, we further accelerate conformal prediction by incorporating approximate leave-one-out (ALO) estimators, and establish asymptotic coverage and efficiency. While our proof draws on methods developed for analyzing the consistency of ALO cross-validation risk estimators in high-dimensional statistics, it requires adaptations to handle conformal prediction, where leave-$i$-out residuals are needed for predictions at $x_{n+1}$ rather than just at the training covariate $x_i$. Simulation results validate our theoretical findings, showing that the ALO-based methods achieve coverage and efficiency comparable to the exact methods, while significantly reducing the runtime.

Related papers

• A Risk Decomposition Framework for Pre-Hoc Fine-Tuning Prediction [7.112791813526235]
  High cost of fine-tuning LLMs poses a significant economic barrier; pre-hoc performance prediction offers a critical solution to substantially reduce this expense.<n>We formulate it as an estimation problem under information constraints, decomposing prediction risk into two components: an intrinsic limit (static data-model compatibility) and a reducible optimization variance.<n>We introduce a predictability phase diagram that organizes tasks into three distinct regimes: Static-Sufficient, Dynamic-Critical, and Noise-Dominant.
  arXiv  Detail & Related papers  (2026-06-16T08:07:42Z)
• Conformal prediction for full and sparse polynomial chaos expansions [0.5735035463793009]
  Polynomial Chaos Expansions (PCEs) are widely recognized for their efficient computational performance in surrogate modeling.<n>We present the integration of two conformal prediction methods, namely the full conformal and the Jackknife+ approaches, into both full and sparse PCEs.
  arXiv  Detail & Related papers  (2026-01-23T10:46:46Z)
• Fast Conformal Prediction using Conditional Interquantile Intervals [9.881784717196675]
  We introduce Conformal Interquantile Regression (CIR), a conformal regression method that constructs near-minimal prediction intervals with guaranteed coverage.<n>We also propose CIR+, which enhances CIR by incorporating a width-based selection rule for interquantile intervals.
  arXiv  Detail & Related papers  (2026-01-06T07:01:08Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• Multiply Robust Conformal Risk Control with Coarsened Data [0.0]
  Conformal Prediction (CP) has recently received a tremendous amount of interest.<n>In this paper, we consider the general problem of obtaining distribution-free valid prediction regions for an outcome given coarsened data.<n>Our principled use of semiparametric theory has the key advantage of facilitating flexible machine learning methods.
  arXiv  Detail & Related papers  (2025-08-21T12:14:44Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  We tackle average-reward infinite-horizon POMDPs with an unknown transition model.<n>We present a novel and simple estimator that overcomes this barrier.
  arXiv  Detail & Related papers  (2025-01-30T22:29:41Z)
• The Journey Matters: Average Parameter Count over Pre-training Unifies Sparse and Dense Scaling Laws [51.608402959163925]
  We present the first systematic exploration of optimal sparse pre-training configurations for large language models.<n>We find that initiating pruning at 25% of total training compute and concluding at 75% achieves near-optimal final evaluation loss.<n>We propose a new scaling law that modifies the Chinchilla scaling law to use the average parameter count over pre-training.
  arXiv  Detail & Related papers  (2025-01-21T20:23:22Z)
• Conformal Thresholded Intervals for Efficient Regression [9.559062601251464]
  Conformal Thresholded Intervals (CTI) is a novel conformal regression method that aims to produce the smallest possible prediction set with guaranteed coverage.<n>CTI constructs prediction sets by thresholding the estimated conditional interquantile intervals based on their length.<n>CTI achieves superior performance compared to state-of-the-art conformal regression methods across various datasets.
  arXiv  Detail & Related papers  (2024-07-19T17:47:08Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.