# PAC Prediction Sets Under Covariate Shift

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 74 references that are in the map.
- First posted on arXiv 17 Jun 2021.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [Moment Matching for Multi-Source Domain Adaptation](https://mlsanity.com/paper/1812.01754/) (2018)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Accurate Uncertainties for Deep Learning Using Calibrated Regression](https://mlsanity.com/paper/1807.00263/) (2018)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Verified Uncertainty Calibration](https://mlsanity.com/paper/1909.10155/) (2019)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Conformal Inference of Counterfactuals and Individual Treatment Effects](https://mlsanity.com/paper/2006.06138/) (2020)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [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)
- [advertorch v0.1: An Adversarial Robustness Toolbox based on PyTorch](https://mlsanity.com/paper/1902.07623/) (2019)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Adaptive, Distribution-Free Prediction Intervals for Deep Networks](https://mlsanity.com/paper/1905.10634/) (2019)
- [Few-shot Conformal Prediction with Auxiliary Tasks](https://mlsanity.com/paper/2102.08898/) (2021)
- [Conformalized Survival Analysis](https://mlsanity.com/paper/2103.09763/) (2021)
- [With Malice Towards None: Assessing Uncertainty via Equalized Coverage](https://mlsanity.com/paper/1908.05428/) (2019)
- [Calibrated Prediction with Covariate Shift via Unsupervised Domain Adaptation](https://mlsanity.com/paper/2003.00343/) (2020)
- [Transferable Calibration with Lower Bias and Variance in Domain Adaptation](https://mlsanity.com/paper/2007.08259/) (2020)

## Built on by (most cited first, 30 of 45)

- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Robust Calibration with Multi-domain Temperature Scaling](https://mlsanity.com/paper/2206.02757/) (2022)
- [Calibrated Selective Classification](https://mlsanity.com/paper/2208.12084/) (2022)
- [Conformal Prediction with Temporal Quantile Adjustments](https://mlsanity.com/paper/2205.09940/) (2022)
- [TRAQ: Trustworthy Retrieval Augmented Question Answering via Conformal Prediction](https://mlsanity.com/paper/2307.04642/) (2023)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [PAC Prediction Sets Under Label Shift](https://mlsanity.com/paper/2310.12964/) (2023)
- [Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models](https://mlsanity.com/paper/2311.13628/) (2023)
- [PAC Prediction Sets for Meta-Learning](https://mlsanity.com/paper/2207.02440/) (2022)
- [Selective Generation for Controllable Language Models](https://mlsanity.com/paper/2307.09254/) (2023)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (2021)
- [Semi-Supervised Risk Control via Prediction-Powered Inference](https://mlsanity.com/paper/2412.11174/) (2024)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [Conformal Frequency Estimation using Discrete Sketched Data with Coverage for Distinct Queries](https://mlsanity.com/paper/2211.04612/) (2022)
- [Synthetic-Powered Predictive Inference](https://mlsanity.com/paper/2505.13432/) (2025)
- [SymmPI: Predictive Inference for Data with Group Symmetries](https://mlsanity.com/paper/2312.16160/) (2023)
- [Conformal Risk Control for Ordinal Classification](https://mlsanity.com/paper/2405.00417/) (2024)
- [Conformal Information Pursuit for Interactively Guiding Large Language Models](https://mlsanity.com/paper/2507.03279/) (2025)
- [PASC: Pipeline-Aware Conformal Prediction with Joint Coverage Guarantees for Multi-Stage NLP and LLM Pipelines](https://mlsanity.com/paper/2605.18812/) (2026)
- [Conformal prediction set for time-series](https://mlsanity.com/paper/2206.07851/) (2022)
- [Efficient and Multiply Robust Risk Estimation under General Forms of Dataset Shift](https://mlsanity.com/paper/2306.16406/) (2023)
- [Distribution-Free Finite-Sample Guarantees and Split Conformal Prediction](https://mlsanity.com/paper/2210.14735/) (2022)
- [Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction](https://mlsanity.com/paper/2405.15912/) (2024)
- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [Optimal Decision-Making Based on Prediction Sets](https://mlsanity.com/paper/2602.00989/) (2026)
- [Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization](https://mlsanity.com/paper/2604.17984/) (2026)
- [Weight Clipping for Robust Conformal Inference under Unbounded Covariate Shifts](https://mlsanity.com/paper/2605.02072/) (2026)
- [Test-time Recalibration of Conformal Predictors Under Distribution Shift Based on Unlabeled Examples](https://mlsanity.com/paper/2210.04166/) (2022)
- [ACon2: Adaptive Conformal Consensus for Provable Blockchain Oracles](https://mlsanity.com/paper/2211.09330/) (2022)

## Abstract (arXiv)

An important challenge facing modern machine learning is how to rigorously quantify the uncertainty of model predictions. Conveying uncertainty is especially important when there are changes to the underlying data distribution that might invalidate the predictive model. Yet, most existing uncertainty quantification algorithms break down in the presence of such shifts. We propose a novel approach that addresses this challenge by constructing probably approximately correct (PAC) prediction sets in the presence of covariate shift. Our approach focuses on the setting where there is a covariate shift from the source distribution (where we have labeled training examples) to the target distribution (for which we want to quantify uncertainty). Our algorithm assumes given importance weights that encode how the probabilities of the training examples change under the covariate shift. In practice, importance weights typically need to be estimated; thus, we extend our algorithm to the setting where we are given confidence intervals for the importance weights. We demonstrate the effectiveness of our approach on covariate shifts based on DomainNet and ImageNet. Our algorithm satisfies the PAC constraint, and gives prediction sets with the smallest average normalized size among approaches that always satisfy the PAC constraint.