# PAC Prediction Sets Under Label Shift

arXiv: https://arxiv.org/abs/2310.12964 · HTML: https://mlsanity.com/paper/2310.12964/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 50 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 25 of 25)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [ChestX-ray8: Hospital-scale Chest X-ray Database and Benchmarks on Weakly-Supervised Classification and Localization of Common Thorax Diseases](https://mlsanity.com/paper/1705.02315/) (2017)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [CheXNet: Radiologist-Level Pneumonia Detection on Chest X-Rays with Deep Learning](https://mlsanity.com/paper/1711.05225/) (2017)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [BREEDS: Benchmarks for Subpopulation Shift](https://mlsanity.com/paper/2008.04859/) (2020)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Regularized Learning for Domain Adaptation under Label Shifts](https://mlsanity.com/paper/1903.09734/) (2019)
- [A Unified View of Label Shift Estimation](https://mlsanity.com/paper/2003.07554/) (2020)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [A Conformal Prediction Approach to Explore Functional Data](https://mlsanity.com/paper/1302.6452/) (2013)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [PAC Prediction Sets Under Covariate Shift](https://mlsanity.com/paper/2106.09848/) (2021)
- [Distribution-Free Prediction Sets for Two-Layer Hierarchical Models](https://mlsanity.com/paper/1809.07441/) (2018)
- [Domain Adaptation under Open Set Label Shift](https://mlsanity.com/paper/2207.13048/) (2022)
- [RLSbench: Domain Adaptation Under Relaxed Label Shift](https://mlsanity.com/paper/2302.03020/) (2023)
- [Prediction Sets Adaptive to Unknown Covariate Shift](https://mlsanity.com/paper/2203.06126/) (2022)
- [PAC Confidence Predictions for Deep Neural Network Classifiers](https://mlsanity.com/paper/2011.00716/) (2020)
- [PAC Prediction Sets for Meta-Learning](https://mlsanity.com/paper/2207.02440/) (2022)

## Built on by (most cited first, 21 of 21)

- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Conformal Prediction with Learned Features](https://mlsanity.com/paper/2404.17487/) (2024)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [SymmPI: Predictive Inference for Data with Group Symmetries](https://mlsanity.com/paper/2312.16160/) (2023)
- [Conformal Information Pursuit for Interactively Guiding Large Language Models](https://mlsanity.com/paper/2507.03279/) (2025)
- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization](https://mlsanity.com/paper/2604.17984/) (2026)
- [Singleton-Optimized Conformal Prediction](https://mlsanity.com/paper/2509.24095/) (2025)
- [Weighted Conformal Clustering](https://mlsanity.com/paper/2606.00436/) (2026)
- [Conformal Prediction for Molecular Properties under Label Shift](https://mlsanity.com/paper/2608.17678/) (2026)
- [Elements of Conformal Prediction](https://mlsanity.com/paper/2603.23923/) (2026)
- [Conditional Predictive Inference for General Structured Data with Group Symmetries](https://mlsanity.com/paper/2605.17934/) (2026)
- [Distribution-Free Predictive Inference under Unknown Temporal Drift](https://mlsanity.com/paper/2406.06516/) (2024)
- [Fundus Image-based Visual Acuity Assessment with PAC-Guarantees](https://mlsanity.com/paper/2412.06624/) (2024)
- [Weighted Conformal Prediction Provides Adaptive and Valid Mask-Conditional Coverage for General Missing Data Mechanisms](https://mlsanity.com/paper/2512.14221/) (2025)
- [The Label Complexity of Useful Class-Conditional Prediction Sets under Distribution Shift](https://mlsanity.com/paper/2607.18088/) (2026)
- [Split Conformal Prediction with Label-Shift-Adjusted Bayesian Scores](https://mlsanity.com/paper/2609.12386/) (2026)
- [From matrix inversion to constraints: provably tighter confidence regions for importance weights in label shift](https://mlsanity.com/paper/2609.14802/) (2026)
- [CS-WCP: Robust Conformal Sets for LLM-Judge Traffic Shifts with Uncertain Group Proportions](https://mlsanity.com/paper/2609.27955/) (2026)
- [Conformal Prediction under Exponential-Tilt Joint Shift](https://mlsanity.com/paper/2609.30886/) (2026)
- [Mean Accuracy Is the Wrong Estimand for a Release Decision](https://mlsanity.com/paper/2610.16825/) (2026)

## Abstract (arXiv)

Prediction sets capture uncertainty by predicting sets of labels rather than individual labels, enabling downstream decisions to conservatively account for all plausible outcomes. Conformal inference algorithms construct prediction sets guaranteed to contain the true label with high probability. These guarantees fail to hold in the face of distribution shift, which is precisely when reliable uncertainty quantification can be most useful. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. This method estimates the predicted probabilities of the classes in a target domain, as well as the confusion matrix, then propagates uncertainty in these estimates through a Gaussian elimination algorithm to compute confidence intervals for importance weights. Finally, it uses these intervals to construct prediction sets. We evaluate our approach on five datasets: the CIFAR-10, ChestX-Ray and Entity-13 image datasets, the tabular CDC Heart dataset, and the AGNews text dataset. Our algorithm satisfies the PAC guarantee while producing smaller, more informative, prediction sets compared to several baselines.