Research map / Learning theory and algorithms / Prediction and decision losses
Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage
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 Kandinsky conformal prediction, a single-quantile-regression method giving conditional coverage over overlapping and fractional groups defined on covariates and labels, with minimax-optimal finite-sample rates.
Problem
Split and Mondrian conformal prediction only guarantee coverage for disjoint groups or marginally, while existing overlapping-group methods restrict group functions to depend only on covariates. Conditional coverage is needed for overlapping, probabilistic group memberships defined jointly on covari
Approach
Conformal prediction via linear quantile regression over the span of a basis of group weight functions (indicators or fractional membership probabilities over (X,Y) or a sufficient statistic), yielding weighted coverage deviation bounds of O(sqrt(d/n)+d/n) and unifying group-conditional, class-conditional and Mondrian CP as special cases; also a test-time variant with O(d/n) expected coverage erro
Key results
- On ACSIncome (31 states), Kandinsky achieves the best group average coverage deviation and the smallest gap between max and min group miscoverage across varying group counts.
- On CivilComments, Kandinsky achieves the best group average coverage deviation when calibration has over 500 samples per group on average; class-conditional CP is best at 250 samples per group.
- On MMLU with LLaMA-13B, Kandinsky (FY) has lower per-group coverage deviation than split CP with smaller sets, and conservative CP matches its deviation only with much larger sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Kandinsky conformal prediction instead of the compared methods | ACSIncome · ACSIncome | group average coverage deviation | Helped |
| Use predictor-and-label inputs (FY) instead of covariate-and-label inputs (XY) | Kandinsky conformal prediction · ACSIncome | group average coverage deviation | Helped |
| Use Kandinsky conformal prediction instead of the compared methods | CivilComments · CivilComments, over 500 samples per group | group average coverage deviation | Helped |
| Use class-conditional conformal prediction instead of Kandinsky conformal prediction | CivilComments · CivilComments, 250 samples per group | group average coverage deviation | Helped |
| Increase calibration sample size | Class-conditional conformal prediction · CivilComments | group average coverage deviation | No clear effect |
| Use Kandinsky conformal prediction | CivilComments · CivilComments, groups with more than 2000 samples | conditional coverage calibration | Helped |
| Use Kandinsky conformal prediction instead of split conformal prediction | LLaMA-13B · MMLU multiple-choice question answering | group average coverage deviation | Helped |
| Use conservative conformal prediction instead of Kandinsky conformal prediction | MMLU multiple-choice question answering · MMLU multiple-choice question answering | prediction set size | Hurt |
Surprising findings
- Kandinsky (FY) prediction set sizes scale with the number of groups, a tradeoff against Kandinsky (XY) which stays moderate and stable.
Limitations
- Test-time variant is computationally expensive, requiring a quantile regression per test point and label.
- Fractional membership guarantees assume the conditional probabilities Phi_G are known; in experiments they must be estimated, and Kandinsky (XY) is inapplicable for text/blackbox settings.
- Guarantee requires continuity of the randomized score conditioned on the basis, and the basis dimension must be small relative to n.
Experimental setup
Datasets: ACSIncome CivilComments MMLU
Benchmarks: ACSIncome CivilComments MMLU
Metrics: group average coverage deviation group miscoverage prediction set size max-min miscoverage gap
Baselines: split conformal prediction class-conditional conformal prediction conservative conformal prediction Kandinsky (XY)
Builds on: split conformal prediction Mondrian conformal prediction conditional conformal prediction (Gibbs et al.) conformalized quantile regression multiaccuracy
Closest papers by meaning
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.91)
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.90)
- Rectifying Conformity Scores for Better Conditional Coverage (ICML 2025 · similarity 0.89)
- Wasserstein-Regularized Conformal Prediction under General Distribution Shift (ICLR 2025 · similarity 0.89)
- Conformal Classification with Equalized Coverage for Adaptively Selected Groups (NeurIPS 2024 · similarity 0.89)
- Conformal Prediction with Learned Features (ICML 2024 · 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.