Missing Not at Random in Matrix Completion: The Effectiveness of
  Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption
  Matrix completion is often applied to data with entries missing not at random
(MNAR). For example, consider a recommendation system where users tend to only
reveal ratings for items they like. In this case, a matrix completion method
that relies on entries being revealed at uniformly sampled row and column
indices can yield overly optimistic predictions of unseen user ratings.
Recently, various papers have shown that we can reduce this bias in MNAR matrix
completion if we know the probabilities of different matrix entries being
missing. These probabilities are typically modeled using logistic regression or
naive Bayes, which make strong assumptions and lack guarantees on the accuracy
of the estimated probabilities. In this paper, we suggest a simple approach to
estimating these probabilities that avoids these shortcomings. Our approach
follows from the observation that missingness patterns in real data often
exhibit low nuclear norm structure. We can then estimate the missingness
probabilities by feeding the (always fully-observed) binary matrix specifying
which entries are revealed or missing to an existing nuclear-norm-constrained
matrix completion algorithm by Davenport et al. [2014]. Thus, we tackle MNAR
matrix completion by solving a different matrix completion problem first that
recovers missingness probabilities. We establish finite-sample error bounds for
how accurate these probability estimates are and how well these estimates
debias standard matrix completion losses for the original matrix to be
completed. Our experiments show that the proposed debiasing strategy can
improve a variety of existing matrix completion algorithms, and achieves
downstream matrix completion accuracy at least as good as logistic regression
and naive Bayes debiasing baselines that require additional auxiliary
information.
