Research map / Learning theory and algorithms / Prediction and decision losses
Backward 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 Backward Conformal Prediction, which fixes a set-size rule and derives a data-dependent miscoverage via e-values, plus a leave-one-out estimator of the marginal miscoverage with concentration guarantees.
Problem
Standard conformal prediction fixes the coverage level and leaves conformal set sizes uncontrolled, which is problematic when large prediction sets are impractical (e.g., medical diagnosis). The paper asks how to control set size while still knowing the resulting coverage.
Approach
Invert the usual workflow: specify a size constraint rule T and choose the miscoverage alpha-tilde adaptively so the e-value-based conformal set has size at most T; use the post-hoc validity of e-value conformal sets (up to a first-order Taylor approximation) for marginal coverage, and estimate E[alpha-tilde] with a leave-one-out estimator computed from calibration data.
Key results
- On CIFAR-10 with EfficientNet-B0 (91.1% test accuracy), the leave-one-out estimator approximates E[alpha-tilde] more closely as calibration size n grows from 100 to 5000, over N=200 runs.
- On Breast Cancer Wisconsin with size constraint T=1, standard conformal at fixed alpha=0.02 yields 33 of 200 sets of size 2, whereas Backward Conformal Prediction guarantees size at most 1 with empirical coverage above 1-E[alpha-tilde].
- Theory: |alpha_LOO - E[alpha-tilde]| = O_P(1/sqrt(n)) and Var(alpha_LOO) = O(1/n) under stated assumptions on the score function and size rule.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply a fixed prediction set size constraint T=1 and choose miscoverage adaptively | Backward Conformal Prediction on Breast Cancer Wisconsin · Breast Cancer Wisconsin (Diagnostic) | maximum prediction set size: standard conformal prediction produced 33 uninformative sets of size 2 (α=0.02); Backward Conformal Prediction guarantee | Helped |
| Use standard conformal prediction with fixed miscoverage α=0.02 instead of adaptive size control | Breast Cancer Wisconsin binary classification · Breast Cancer Wisconsin (Diagnostic), 200 runs | number of uninformative prediction sets of size 2: 33 | Hurt |
| Set fixed miscoverage to α=E[tilde α] rather than adaptively controlling set size | Breast Cancer Wisconsin binary classification · Breast Cancer Wisconsin (Diagnostic), 200 runs | number of prediction sets of size 2: 4 | Hurt |
| Increase calibration size | Backward Conformal Prediction with the leave-one-out estimator · CIFAR-10 | approximation of marginal miscoverage E[tilde α] | Helped |
| Use the adaptive, data-dependent size constraint rule based on local label entropy | Backward Conformal Prediction · Image classification experiment with adaptive T | approximation of marginal miscoverage E[tilde α] | Helped |
Surprising findings
- Histograms of the adaptive miscoverage and the leave-one-out estimator can differ noticeably even though the estimator targets only the mean E[alpha-tilde].
Limitations
- Coverage guarantee holds only up to a first-order Taylor approximation and is conservative because of Markov's inequality.
- Consistency for data-dependent size rules requires a stability assumption (P3) that is not verified in general.
- Experiments are limited to classification with small label sets and two datasets.
Experimental setup
Datasets: CIFAR-10 Breast Cancer Wisconsin (Diagnostic)
Benchmarks: CIFAR-10 Breast Cancer Wisconsin (Diagnostic)
Metrics: empirical coverage leave-one-out miscoverage estimate vs. true miscoverage prediction set size
Baselines: standard split conformal prediction
Builds on: conformal e-prediction post-hoc validity with e-values
Closest papers by meaning
- Valid Selection among Conformal Sets (NeurIPS 2025 · similarity 0.91)
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.91)
- Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (ICML 2025 · similarity 0.90)
- Rectifying Conformity Scores for Better Conditional Coverage (ICML 2025 · similarity 0.90)
- Improving the Statistical Efficiency of Cross-Conformal Prediction (ICML 2025 · similarity 0.89)
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.89)
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.