Research map / Label-efficient and robust learning / Recognition and long-tail
PAC Prediction Sets Under Label Shift
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 PS-W, a PAC prediction set method under label shift that builds Clopper-Pearson intervals for the confusion matrix and predicted-label distribution, propagates them through Gaussian elimination to bound importance weights, and uses these bounds in a PAC threshold procedure.
Problem
Conformal and PAC prediction sets lose their coverage guarantees under label shift when importance weights must be estimated from finite data, since estimation error is not accounted for.
Approach
Construct elementwise confidence intervals for the confusion matrix and predicted-label distribution, then propagate these intervals through each step of Gaussian elimination to obtain provably valid intervals around the importance weights w* = C_P^{-1} q*, which feed a PAC prediction set algorithm.
Key results
- PS-W satisfies the PAC guarantee in all reported experiments across five datasets while producing smaller prediction sets than PS-C, the only other baseline with PAC guarantees under label shift, except when shift is small and calibration data limited.
- PS and PS-R baselines violate the PAC guarantee under label shift, while WCP targets only marginal coverage and also fails it.
- Results averaged over 100 independent repetitions with delta = 5e-4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PS-W with interval-propagated importance weights instead of PS-C's conservative loss bound | PAC prediction sets under label shift · CDC Heart, CIFAR-10, AGNews, Entity-13, ChestX-ray | average prediction set size | Mixed |
| Use PS-W to account for label shift and importance-weight uncertainty instead of PS or PS-R | PAC prediction sets under label shift · CDC Heart, CIFAR-10, Entity-13 | PAC coverage guarantee | Helped |
| Use PS-W instead of WCP, which targets marginal coverage | PAC prediction sets under label shift · Entity-13 | PAC coverage guarantee | Helped |
| Use PS-W instead of PS-C | PAC prediction sets under label shift · CIFAR-10, large label shift | average prediction set size | Helped |
| Use PS-W instead of PS-C | PAC prediction sets under label shift · CIFAR-10, small label shift with limited data | average prediction set size | No clear effect |
| Use PS-W instead of PS-C | PAC prediction sets under label shift · AGNews | average prediction set size | Helped |
| Use PS-W instead of PS-C | PAC prediction sets under label shift · ChestX-ray | average prediction set size | Helped |
| Use PS-W instead of PS-C | PAC prediction sets under label shift · Entity-13 | average prediction set size | Helped |
| Use PS-W instead of PS-LW's label-conditional PAC prediction sets | PAC prediction sets under label shift · CDC Heart, small label shift | average prediction set size | Helped |
| Use vanilla prediction sets with APS scoring | Prediction sets under label shift · CDC Heart, small label shift | PAC coverage guarantee | Hurt |
Surprising findings
- When label shift is very small and calibration data is limited, PS-W produces prediction sets similar in size to or larger than PS-C.
Limitations
- Performance degrades when the calibration dataset is small or the label shift is small, producing conservative sets.
- Assumes the confusion matrix is invertible and that interval entries stay non-negative (or positive diagonals), which requires a reasonably accurate classifier; relaxations are only sketched.
- Covers only label shift with fixed class-conditional covariate distributions.
Experimental setup
Datasets: CIFAR-10 ChestX-ray14 Entity-13 (BREEDs) CDC Heart AGNews
Benchmarks: CIFAR-10 ChestX-ray14 Entity-13 CDC Heart AGNews
Metrics: prediction set error average prediction set size
Baselines: PS WCP PS-R PS-C PS-LW LWCP APS Oracle (true weights)
Builds on: PAC prediction sets (Vovk-style training-conditional bounds) weighted conformal prediction black box shift estimation rejection sampling for covariate shift PAC prediction sets
Closest papers by meaning
- Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning (ICLR 2025 · similarity 0.85)
- Conformal Structured Prediction (ICLR 2025 · similarity 0.85)
- Exploring the Noise Robustness of Online Conformal Prediction (NeurIPS 2025 · similarity 0.85)
- An Information Theoretic Perspective on Conformal Prediction (NeurIPS 2024 · similarity 0.84)
- Multi-Source Conformal Inference Under Distribution Shift (ICML 2024 · similarity 0.84)
- Volume Optimality in Conformal Prediction with Structured Prediction Sets (ICML 2025 · similarity 0.84)
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.