Research map / Learning theory and algorithms / Prediction and decision losses
Improving the Statistical Efficiency of Cross-Conformal Prediction
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.
Proposes four variants of (modified) cross-conformal prediction that use exchangeable and/or randomized combinations of K fold p-values to produce smaller prediction sets while keeping the 1-2α marginal coverage guarantee.
Problem
Cross-conformal prediction gives smaller sets than split conformal, but its marginal coverage guarantee (about 1-2α) is weak and the resulting sets can still be wider than needed; the goal is to shrink cross-conformal prediction sets without weakening the worst-case miscoverage guarantee.
Approach
Uses recent results on combining exchangeable and randomized p-values: a min over prefix means of the K cross-conformal p-values (e-mod-cross), a uniform randomization factor 1/(2-U) on the average (u-mod-cross), and their combination (eu-mod-cross). These give subsets of modified cross-conformal sets while preserving 1-2α coverage, and replacing α with α' = α+(1-α)(K-1)/(K+n) improves standard cr
Key results
- On the simulation with n=100, alpha=0.1, K=5, eu-mod-cross yields smaller sets than cross-conformal in most settings and its coverage lies between 1-2α and 1-α, while standard cross-conformal is often over-conservative.
- On Boston Housing (OLS, K=5), eu-mod-cross has mean set size 13.370 versus 15.753 for cross-conformal and 16.357 for split, with coverage 0.855 (guarantee 0.80).
- On UPDRS with random forest, eu-mod-cross has mean size 13.718 versus 17.015 for cross-conformal, but split conformal at level 2α is smaller (14.550) and has coverage 0.802.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exchangeable p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction · Boston Housing | mean set size: 17.303 -> 14.920 | Helped |
| Use randomized p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction · Boston Housing | mean set size: 17.303 -> 14.143 | Helped |
| Use exchangeable and randomized p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction · Boston Housing | mean set size: 17.303 -> 13.370 | Helped |
| Use exchangeable and randomized p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction with random forest · UPDRS | mean set size: 17.180 -> 13.718 | Helped |
| Use exchangeable and randomized p-value combination instead of cross-conformal prediction | Cross-conformal prediction with random forest · Abalone (K=5) | mean set size: 6.864 -> 5.477 | Helped |
| Use split conformal prediction at miscoverage rate 2α instead of eu-mod-cross | Conformal prediction with OLS · Boston Housing | mean set size | Hurt |
| Use split conformal prediction at miscoverage rate 2α instead of eu-mod-cross | Conformal prediction with lasso · UPDRS | mean set size: 26.252 vs 23.773 | Hurt |
| Use eu-mod-cross instead of split conformal prediction at miscoverage rate 2α | Cross-conformal prediction with random forest · UPDRS | mean set size: 14.550 -> 13.718 | Helped |
| Use split conformal prediction at miscoverage rate 2α instead of eu-cross | Cross-conformal prediction with random forest · Abalone (K=5) | mean set size: 5.477 vs 4.617 | Hurt |
| Use exchangeable p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction with lasso · UPDRS | coverage: 0.904 -> 0.892 | Hurt |
| Use randomized p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction with lasso · UPDRS | coverage: 0.904 -> 0.854 | Hurt |
| Use exchangeable and randomized p-value combination instead of modified cross-conformal prediction | Cross-conformal prediction with random forest · UPDRS | coverage: 0.931 -> 0.846 | Hurt |
Surprising findings
- Split conformal trained at level 2α often yields smaller sets than the proposed methods on real datasets, despite the same nominal 1-2α guarantee.
- Randomized variants show higher variability in set size and coverage, and eu-mod-cross can have coverage near 1-2α on some datasets, showing a size/coverage tradeoff.
Limitations
- Randomized variants add external randomness that can hurt reproducibility and produce higher variability in set size and coverage.
- Improvements do not hold for leave-one-out (K=n) and rely on n/K being an integer for exchangeability results.
- Asymmetric min-over-prefix combination does not preserve exchangeability guarantees for varying fold sizes; only the randomized variant remains valid there.
Experimental setup
Datasets: Online News Popularity Communities and Crime Boston Housing UPDRS (Parkinson's telemonitoring) Abalone
Benchmarks: simulated linear regression Online News Popularity Communities and Crime Boston Housing UPDRS Abalone
Metrics: average prediction set size empirical marginal coverage
Baselines: cross-conformal prediction modified cross-conformal prediction split conformal prediction full conformal prediction jackknife+
Builds on: cross-conformal prediction modified cross-conformal prediction CV+ jackknife+
Closest papers by meaning
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.89)
- Conformal Predictions under Markovian Data (ICML 2024 · similarity 0.89)
- Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shift with Unlabeled Data (NeurIPS 2025 · similarity 0.88)
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.88)
- Rectifying Conformity Scores for Better Conditional Coverage (ICML 2025 · similarity 0.88)
- Co-optimization for Adaptive Conformal Prediction (NeurIPS 2026 · similarity 0.87)
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.