Prediction Sets Adaptive to Unknown Covariate Shift

Hongxiang Qiu, Edgar Dobriban, Eric Tchetgen Tchetgen

TL;DR

Standard machine learning models often struggle to quantify uncertainty when the "test" data looks different from the "training" data—a problem known as covariate shift. This paper introduces PredSet-1Step, a novel method that constructs reliable prediction sets even when the nature of that shift is completely unknown, providing a rigorous "Asymptotically Probably Approximately Correct" (APAC) guarantee.

What Problem Does This Paper Address?

In high-stakes fields like medicine or autonomous driving, a single "best guess" from an AI isn't enough; we need to know how certain the model is. One way to do this is by generating prediction sets—a range of possible outcomes that is guaranteed to contain the true value most of the time (e.g., 95% of the time).

The gold standard for this is Conformal Prediction. However, most conformal methods assume that your training data and future test data come from the exact same distribution. In the real world, this rarely happens. We often face covariate shift, where the distribution of input features ($X$) changes (e.g., training a medical model on urban patients but deploying it in a rural clinic), even if the underlying relationship between features and outcomes ($P(Y|X)$) remains the same.

Existing solutions usually require you to know exactly how the distribution shifted or to have a very large amount of unlabeled data from the new population. The authors tackle the "blind" version of this problem: How do we provide statistical guarantees when we don't know the shift and have to estimate it on the fly?

Methods

The authors first prove a discouraging "negative result": if you want a finite-sample guarantee under unknown shift, your prediction sets will be so large they become useless (uninformative). Consequently, they pivot to an asymptotic approach—guarantees that hold as the sample size grows.

Their core contribution is PredSet-1Step. The method works through several sophisticated steps:

  1. Nuisance Estimation: It uses machine learning to estimate two "nuisance" components: the propensity score (the probability a data point belongs to the source vs. target population) and the conditional coverage error.
  2. Cross-Fitting: To avoid overfitting, the data is split into folds. Models are trained on one set of folds and evaluated on others.
  3. One-Step Correction: This is the "secret sauce" borrowed from semiparametric efficiency theory. Simple "plug-in" estimators are often biased. The "one-step" correction uses the influence function of the coverage error to mathematically subtract that bias, leading to much more accurate estimates of how well the prediction set is performing.
  4. Wald Confidence Upper Bounds: It calculates a statistical upper bound on the error rate and selects the smallest prediction set that stays below the allowed error threshold.

Datasets

The researchers evaluated PredSet-1Step using:

  • Synthetic Simulations: They tested the method on moderate-to-high dimensional sparse data and low-dimensional data, both with and without covariate shifts.
  • HIV Risk Prediction Data: A real-world dataset from a South African cohort study (KwaZulu-Natal). The goal was to predict HIV seroconversion. The "source" population consisted of urban and rural communities, while the "target" was a peri-urban community. This provided a natural, severe covariate shift to test the model's robustness.

Key Insights and Ideas

  • The "Uninformative" Lemma: The paper formally shows that you cannot have a tight, non-trivial prediction set with a 100% rigorous guarantee for any sample size if the shift is unknown. This justifies why we must settle for asymptotic (large-sample) guarantees.
  • Borrowing from Causal Inference: The authors cleverly apply tools from causal inference (like the EIF—Efficient Influence Function) to a pure prediction problem. They treat the population indicator (source vs. target) similarly to how a "treatment" variable is treated in clinical trials.
  • Bias vs. Variance: Standard methods under covariate shift often suffer from high bias because they don't account for the error in estimating the shift itself. The "One-Step" correction specifically targets this bias, making the coverage much more reliable in practice.

Key Results

  • Reliable Coverage: In the HIV risk study, PredSet-1Step achieved an empirical coverage of 95.98% (targeting 95%), while standard Inductive Conformal Prediction—which ignores the shift—dropped to 91.89%, failing to meet the safety requirement.
  • Efficiency: Compared to other shift-adaptive methods (like rejection sampling), PredSet-1Step produced smaller, more precise prediction sets.
  • Robustness: The method proved to be "APAC"—meaning as you get more data, the probability that your error rate exceeds your target vanishes at a predictable rate ($n^{-1/4}$ multiplied by the product of nuisance estimation rates).

Limitations and Future Work

  • Sample Size: Because the guarantees are asymptotic, the method might still struggle with very small datasets where the "one-step" correction hasn't yet stabilized.
  • Stable Relationship Assumption: The method relies on the core covariate shift assumption—that while the people might change, the biological/physical laws governing the outcome ($P(Y|X)$) do not. If the relationship itself changes (concept drift), the guarantees no longer hold.
  • Future Directions: The authors suggest exploring the asymptotic behavior of the selected thresholds and investigating if bootstrap-based methods could further improve coverage in smaller samples.

Summary updated

Abstract

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.
BibTeX
@article{qiu2023prediction,
  author = {Hongxiang Qiu and Edgar Dobriban and Eric Tchetgen Tchetgen},
  title = {{Prediction Sets Adaptive to Unknown Covariate Shift}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2023},
  doi = {10.1093/jrsssb/qkad069},
}
Figure