Skip to yearly menu bar Skip to main content


Blind Regression: Nonparametric Regression for Latent Variable Models via Collaborative Filtering

Dogyoon Song · Christina Lee · Yihua Li · Devavrat Shah

Area 5+6+7+8 #39

Keywords: [ Ranking and Preference Learning ] [ (Application) Collaborative Filtering and Recommender Systems ] [ Similarity and Distance Learning ] [ (Other) Probabilistic Models and Methods ] [ Learning Theory ]

Abstract: We introduce the framework of blind regression motivated by matrix completion for recommendation systems: given $m$ users, $n$ movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user $u$ and movie $i$ have features $x1(u)$ and $x2(i)$ respectively, and their corresponding rating $y(u,i)$ is a noisy measurement of $f(x1(u), x2(i))$ for some unknown function $f$. In contrast with classical regression, the features $x = (x1(u), x2(i))$ are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least $\max(m^{-1+\delta},n^{-1/2+\delta})$ with $\delta > 0$, we prove that the expected fraction of our estimates with error greater than $\epsilon$ is less than $\gamma^2 / \epsilon^2$ plus a polynomially decaying term, where $\gamma^2$ is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods.

Live content is unavailable. Log in and register to view live content