  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 \emph{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.
