Bayesian method estimates missing matrix entries with guaranteed efficiency
Nuclear Norm-Regularized Bayesian Matrix Completion
Machine Learning
Summary
Estimating missing data in a table is important in many fields, like recommending products or analyzing data over time. The authors focus on a Bayesian way to do this that not only predicts missing values but also provides uncertainty estimates. They handle a tricky part about unknown noise with a new sampling method that is guaranteed to run efficiently for reasonably sized problems. This work shows it's possible to do Bayesian matrix completion with known performance limits, though the current method isn't yet practical for very large datasets.
What this means in practice
- •For recommender system developers: Enable uncertainty-aware predictions of missing user-item ratings when noise levels are unknown.
- •For panel data analysts: Provide methods to estimate missing entries in longitudinal data with quantified uncertainty despite unknown noise variations.
A theory result. No direct application yet.
Authors
Calvin Tolbert
Abstract
Matrix completion, the problem of estimating missing entries in a matrix from noisily observed ones, underlies a diverse array of problems such as recommender systems and counterfactual outcome estimation in panel data. Many algorithms address the problem using regularized least squares, often with the nuclear norm as a regularizer, but this method yields a point estimate with no built-in uncertainty quantification. A Bayesian formulation is a natural alternative, and if the noise variance is known, the nuclear norm-based prior yields a log-concave posterior. Unfortunately, in practice, the noise variance will not be known a priori, so for a fully Bayesian approach, a prior must be imposed on it. We give the first sampler for this model with an explicit non-asymptotic guarantee: polynomial in the matrix dimensions and in the reciprocal of the target accuracy. Our technique is to discretize the distribution of the noise precision onto a grid and build a categorical posterior via thermodynamic integration. This extension is not specific to matrix completion and may be useful in other non-log-concave sampling problems where the non-log-concavity is restricted to a single variable and the joint distribution of the remaining variables is nonsmooth. Our contribution is a feasibility result: we show that a polynomial-time Bayesian sampler for this model exists at all, and the resulting complexity, while polynomial, is not intended as a deployable algorithm at current problem scales.