  Predictive uncertainty quantification is crucial in decision-making problems.
We investigate how to adequately quantify predictive uncertainty with missing
covariates. A bottleneck is that missing values induce heteroskedasticity on
the response's predictive distribution given the observed covariates. Thus, we
focus on building predictive sets for the response that are valid conditionally
to the missing values pattern. We show that this goal is impossible to achieve
informatively in a distribution-free fashion, and we propose useful
restrictions on the distribution class. Motivated by these hardness results, we
characterize how missing values and predictive uncertainty intertwine.
Particularly, we rigorously formalize the idea that the more missing values,
the higher the predictive uncertainty. Then, we introduce a generalized
framework, coined CP-MDA-Nested*, outputting predictive sets in both regression
and classification. Under independence between the missing value pattern and
both the features and the response (an assumption justified by our hardness
results), these predictive sets are valid conditionally to any pattern of
missing values. Moreover, it provides great flexibility in the trade-off
between statistical variability and efficiency. Finally, we experimentally
assess the performances of CP-MDA-Nested* beyond its scope of theoretical
validity, demonstrating promising outcomes in more challenging configurations
than independence.
