Timezone: »

Collaborative Filtering with Graph Information: Consistency and Scalable Methods
Nikhil Rao · Hsiang-Fu Yu · Pradeep Ravikumar · Inderjit Dhillon

Thu Dec 10 07:10 AM -- 07:40 AM (PST) @ Room 210 A

Low rank matrix completion plays a fundamental role in collaborative filtering applications, the key idea being that the variables lie in a smaller subspace than the ambient space. Often, additional information about the variables is known, and it is reasonable to assume that incorporating this information will lead to better predictions. We tackle the problem of matrix completion when pairwise relationships among variables are known, via a graph. We formulate and derive a highly efficient, conjugate gradient based alternating minimization scheme that solves optimizations with over 55 million observations up to 2 orders of magnitude faster than state-of-the-art (stochastic) gradient-descent based methods. On the theoretical front, we show that such methods generalize weighted nuclear norm formulations, and derive statistical consistency guarantees. We validate our results on both real and synthetic datasets.

Author Information

Nikhil Rao (University of Texas at Austin)
Hsiang-Fu Yu (U Texas)
Pradeep Ravikumar (University of Texas at Austin)
Inderjit Dhillon (University of Texas at Austin)

More from the Same Authors