Research map / Learning theory and algorithms / Prediction and decision losses
Valid Selection among Conformal 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.
Proposes a stability-based randomized selection framework (MinSE, AdaMinSE, derandomized and recalibrated variants) that lets one pick the smallest among multiple valid conformal sets while preserving marginal coverage, extended to online settings via AdaCOMA.
Problem
Selecting the smallest (or otherwise most desirable) among multiple valid conformal prediction sets generally invalidates their coverage guarantees because selection depends on the data.
Approach
Use an algorithmically stable randomized selection mechanism (via indistinguishability from a reference distribution) so that individual coverage transfers to the selected set with an inflation factor alpha*e^eta + tau; a linear program (MinSE) gives the minimum-expected-size stable selector, with adaptive, derandomized, and split-conformal rank-recalibration variants.
Key results
- Recal (recalibrated split conformal after stable selection) consistently gives the smallest average interval length on synthetic and real heterogeneous settings while achieving target coverage 0.9.
- MinSE and AdaMinSE overcover on synthetic and real data but are competitive with baselines on Abalone and California Housing, and produce larger sets on Bike Sharing.
- In the toy regression example, stable selection reduces average set size versus individual predictors (which are about 30% wider) while keeping the same coverage.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Recal (effective-rank post-selection recalibration) instead of the compared selection methods | Synthetic regression and real regression datasets · Synthetic regression; Abalone; California Housing; Bike Sharing | average interval length | Helped |
| Use MinSE or AdaMinSE instead of the baselines | Real regression datasets · Abalone; California Housing | average interval length | No clear effect |
| Use MinSE or AdaMinSE instead of the baselines | Real regression datasets · Bike Sharing | average interval length | Hurt |
| Use YK-Base, which selects the best-on-average predictor without coverage guarantees | Synthetic regression · Synthetic regression | coverage | Hurt |
| Use YK-Adjust, MinSE, or AdaMinSE | Selection methods · Synthetic regression; real regression datasets | coverage | Mixed |
| Use Recal instead of stability-based methods | Batch conformal selection · Homogeneous synthetic and real-data settings | average interval length | Mixed |
| Use Recal instead of other selection methods | Batch conformal selection · Heterogeneous real-data experiments | average interval length | Helped |
| Use stability-based approaches instead of Recal or baselines | Batch conformal selection · Homogeneous setting | average interval length | Hurt |
Surprising findings
- Stability-based bounds can be conservative: in homogeneous settings, MinSE and AdaMinSE produce larger sets than baselines, and naive selection with inflated sets is sometimes necessary to restore coverage.
- Coverage after selection in the coin-flip example is almost exactly 1-alpha, showing the inflation factor is necessary even when oracles are independent.
Limitations
- Stability-based coverage bound (alpha*e^eta + tau) is conservative and overcovers in many settings.
- Recal requires an auxiliary split of the calibration data, reducing data for calibration.
- Experiments are limited to simple regression and small-scale online settings.
Experimental setup
Datasets: Abalone California Housing Bike Sharing Synthetic regression ELEC ARMA(1,1) synthetic
Benchmarks: Abalone California Housing Bike Sharing Synthetic regression ELEC ARMA(1,1) synthetic
Metrics: marginal coverage average interval length
Baselines: YK-Adjust YK-Base ModSel COMA
Builds on: Split conformal prediction Conformal Online Model Aggregation (COMA) Adaptive Conformal Inference (ACI) Exponential mechanism Yang-Kuchibhotla selection method
Closest papers by meaning
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.91)
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.90)
- Conformal Prediction with Learned Features (ICML 2024 · similarity 0.89)
- Generative Conformal Prediction with Optimized Coverage Allocation (NeurIPS 2026 · similarity 0.89)
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.88)
- Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (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.