Volume Optimality in Conformal Prediction with Structured Prediction Sets

2025-02-23 · Chao GAO, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan

Conformal Prediction is a widely studied technique to construct prediction sets of future observations. Most conformal prediction methods focus on achieving the necessary coverage guarantees, but do not provide formal guarantees on the size (volume) of the prediction sets. We first prove an impossibility of volume optimality where any distribution-free method can only find a trivial solution. We then introduce a new notion of volume optimality by restricting the prediction sets to belong to a set family (of finite VC-dimension), specifically a union of $k$-intervals. Our main contribution is an efficient distribution-free algorithm based on dynamic programming (DP) to find a union of $k$-intervals that is guaranteed for any distribution to have near-optimal volume among all unions of $k$-intervals satisfying the desired coverage property. By adopting the framework of distributional conformal prediction (Chernozhukov et al., 2021), the new DP based conformity score can also be applied to achieve approximate conditional coverage and conditional restricted volume optimality, as long as a reasonable estimator of the conditional CDF is available. While the theoretical results already establish volume-optimality guarantees, they are complemented by experiments that demonstrate that our method can significantly outperform existing methods in many settings.

📄 PDF Abstract BibTeX arXiv:2502.16658

Code (0)

등록된 구현이 없습니다.

Tasks

Conformal PredictionPrediction Structured Prediction

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Focus 설명 없음

Hierarchical Conformal Classification

2025-08-18 · Floris den Hengst, Inès Blin, Majid Mohammadi, Syed Ihtesham Hussain Shah 외 arxiv

Conformal prediction (CP) is a powerful framework for quantifying uncertainty in machine learning models, offering reliable predictions with finite-sample coverage guarantees. When applied to classification, CP produces …

Conformal Structured Prediction

2024-10-08 · Botong Zhang, Shuo Li, Osbert Bastani

Conformal prediction has recently emerged as a promising strategy for quantifying the uncertainty of a predictive model; these algorithms modify the model to output sets of labels that are guaranteed to contain the true …

Conformal Prediction image-classification Image Classification Prediction+2

Minimum Volume Conformal Sets for Multivariate Regression

2025-03-24 · Sacha Braun, Liviu Aolaritei, Michael I. Jordan, Francis Bach

Conformal prediction provides a principled framework for constructing predictive sets with finite-sample validity. While much of the focus has been on univariate response variables, existing multivariate methods either i…

Conformal Prediction Prediction regression valid

Conformalized Deep Splines for Optimal and Efficient Prediction Sets

2023-11-01 · Nathaniel Diamant, Ehsan Hajiramezanali, Tommaso Biancalani, Gabriele Scalia

Uncertainty estimation is critical in high-stakes machine learning applications. One effective way to estimate uncertainty is conformal prediction, which can provide predictive inference with statistical coverage guarant…

Conformal Prediction Prediction Prediction Intervals

Conformal Graph Prediction with Z-Gromov-Wasserstein Distances

2026-03-02 · Gabriel Melo, Thibaut de Saivre, Anna Calissano, Florence d'Alché-Buc arxiv

Supervised graph prediction addresses regression problems where the outputs are structured graphs. Although several approaches exist for graph-valued prediction, principled uncertainty quantification remains limited. We …