  Matrix completion aims to estimate missing entries in a data matrix, using
the assumption of a low-complexity structure (e.g., low rank) so that
imputation is possible. While many effective estimation algorithms exist in the
literature, uncertainty quantification for this problem has proved to be
challenging, and existing methods are extremely sensitive to model
misspecification. In this work, we propose a distribution-free method for
predictive inference in the matrix completion problem. Our method adapts the
framework of conformal prediction, which provides confidence intervals with
guaranteed distribution-free validity in the setting of regression, to the
problem of matrix completion. Our resulting method, conformalized matrix
completion (cmc), offers provable predictive coverage regardless of the
accuracy of the low-rank model. Empirical results on simulated and real data
demonstrate that cmc is robust to model misspecification while matching the
performance of existing model-based methods when the model is correct.
