  Predicting sets of outcomes -- instead of unique outcomes -- is a promising
solution to uncertainty quantification in statistical learning. Despite a rich
literature on constructing prediction sets with statistical guarantees,
adapting to unknown covariate shift -- a prevalent issue in practice -- poses a
serious unsolved challenge. In this paper, we show that prediction sets with
finite-sample coverage guarantee are uninformative and propose a novel flexible
distribution-free method, PredSet-1Step, to efficiently construct prediction
sets with an asymptotic coverage guarantee under unknown covariate shift. We
formally show that our method is \textit{asymptotically probably approximately
correct}, having well-calibrated coverage error with high confidence for large
samples. We illustrate that it achieves nominal coverage in a number of
experiments and a data set concerning HIV risk prediction in a South African
cohort study. Our theory hinges on a new bound for the convergence rate of the
coverage of Wald confidence intervals based on general asymptotically linear
estimators.
