Research map / Learning theory and algorithms / Prediction and decision losses
Volume Optimality in Conformal Prediction with Structured Prediction Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows distribution-free volume optimality is impossible for conformal prediction, then proposes conformalized dynamic programming that finds near-optimal unions of k intervals with coverage and (conditional) restricted volume optimality guarantees.
Problem
Conformal prediction sets guarantee coverage but not volume (size); distribution-free volume optimality is impossible in general, so volume guarantees are needed within a structured family of prediction sets.
Approach
Restrict prediction sets to unions of k intervals (finite VC dimension), compute nested sets via a dynamic program on the empirical distribution, and use the depth of nested sets as a conformity score within split conformal (and distributional conformal) prediction to obtain restricted volume optimality.
Key results
- On the Gaussian mixture with 80% coverage, conformalized DP with k=3 gives volume 3.1438 versus 4.4775 for conformalized KDE, against an optimal volume of 3.0178.
- On the simulated Poisson-type regression dataset at 70% target coverage, conformalized DP with k=5 achieves average volume 0.45 versus 1.29 for DCP-QR* and 1.42 for CQR, with 72.36% empirical coverage.
- On the 20-dimensional bimodal simulation, conformalized DP with k=2 gives volume 3.55 versus 3.60 for HPD-split, at roughly 69% coverage.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use conformalized dynamic programming with k=5 intervals instead of DCP-QR* | Conformal prediction on simulated data (1D features) · Simulated data (1D features) | average volume: 1.29 -> 0.45 | Helped |
| Use conformalized dynamic programming with k=2 intervals instead of HPD-split | Conformal prediction on simulated data (20D features) · Simulated data (20D features) | average volume: 3.60 -> 3.55 | Helped |
| Use k=5 instead of k=1 intervals (ablation) | Conformalized-DP on simulated data (1D features) · Simulated data (1D features) | average volume: 1.14 -> 0.45 | Helped |
| Use k=5 instead of k=1 intervals (ablation) | Conformalized-DP on simulated data (1D features) · Simulated data (1D features) | empirical coverage (%): 74.04 -> 72.36 | Hurt |
| Use k=2 instead of k=1 intervals (ablation) | Conformalized-DP on simulated data (20D features) · Simulated data (20D features) | average volume: 4.00 -> 3.55 | Helped |
| Use k=2 instead of k=1 intervals (ablation) | Conformalized-DP on simulated data (20D features) · Simulated data (20D features) | empirical coverage (%): 68.98 -> 69.42 | Helped |
| Use conformalized DP instead of conformalized KDE with bandwidth rho=0.5 | Conformal prediction on the mixture of Gaussians · Mixture of Gaussians | volume: 4.4775 -> 3.1438 | Helped |
| Use k at least 3 for the three-component Gaussian mixture rather than fewer intervals (ablation) | Conformalized-DP on the mixture of Gaussians · Mixture of Gaussians | volume | Helped |
| Increase k from 1 to 2 on censored Gaussian data (ablation) | Conformalized-DP · Censored Gaussian | volume | Helped |
| Vary the number of intervals k when k is not smaller than the number of modes (ablation) | Conformalized-DP · Multimodal distributions | volume | No clear effect |
| Vary KDE bandwidth rho (ablation) | Conformalized-KDE · Gaussian and multimodal distributions | volume | Mixed |
Surprising findings
- Distribution-free volume optimality is impossible: any distribution-free method satisfying coverage can be forced to have volume at least OPT(P, 1-alpha+epsilon) for some P.
Limitations
- Volume optimality is restricted to unions of k intervals, and the impossibility result means unrestricted guarantees are not possible.
- Conditional guarantees require a reasonable black-box estimate of the conditional CDF with error bounds.
- Computational cost of the DP is O(n^3 k / gamma) for the unsupervised case and grows with grid size in the supervised case.
Experimental setup
Datasets: synthetic Gaussian mixture synthetic Gaussian censored Gaussian ReLU-transformed Gaussian simulated heteroscedastic Poisson regression dataset 20-dimensional bimodal simulated regression dataset
Benchmarks: synthetic Gaussian mixture censored Gaussian ReLU-transformed Gaussian simulated Poisson regression data 20-dimensional bimodal simulated regression
Metrics: average volume (Lebesgue measure of prediction set) empirical coverage
Baselines: conformalized KDE CQR DCP-QR DCP-QR* CD-split HPD-split standard split conformal
Builds on: distributional conformal prediction conformalized kernel density estimation conformalized quantile regression HPD-split
Closest papers by meaning
- On Volume Minimization in Conformal Regression (ICML 2025 · similarity 0.91)
- Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (ICML 2025 · similarity 0.88)
- Co-optimization for Adaptive Conformal Prediction (NeurIPS 2026 · similarity 0.88)
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.88)
- Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shift with Unlabeled Data (NeurIPS 2025 · similarity 0.88)
- Optimal transport-based conformal prediction (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.