Timezone: »

 
Poster
Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation
Christian Borgs · Jennifer Chayes · Christina Lee · Devavrat Shah

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #72
in Posters Wed »
The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering-style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to $0$ at the rate of $O(d^2 (pn)^{-2/5})$ as long as $\omega(d^5 n)$ random entries from a total of $n^2$ entries of $Y$ are observed (uniformly sampled), $\E[Y]$ has rank $d$, and the entries of $Y$ have bounded support. The maximum squared error across all entries converges to $0$ with high probability as long as we observe a little more, $\Omega(d^5 n \ln^5(n))$ entries. Our results are the best known sample complexity results in this generality.
Keywords: Matrix and Tensor Factorization · Network Analysis · Collaborative Filtering

Author Information

Christian Borgs (Microsoft Research New England)
Jennifer Chayes (Microsoft Research)

Jennifer Chayes is Technical Fellow and Managing Director of Microsoft Research New England, New York City, and Montreal. She was for many years Professor of Mathematics at UCLA. She is author of over 140 academic papers and inventor of over 30 patents. Her research areas include phase transitions in computer science, structural and dynamical properties of networks, graph theory, graph algorithms, and computational biology. She is one of the inventors of the field of graphons, which are now widely used in the machine learning of massive networks. Chayes’ recent work focuses on machine learning, broadly defined. Chayes holds a BA in physics and biology from Wesleyan, where she graduated first in her class, and a PhD in physics from Princeton. She was a postdoctoral fellow at Harvard and Cornell. She is the recipient of the NSF Postdoc Fellowship, the Sloan Fellowship, the UCLA Distinguished Teaching Award, and the Anita Borg Institute Women of Leadership Vision Award. She has twice been a member of the Institute for Advanced Study in Princeton. Chayes is Fellow of the American Association for the Advancement of Science, the Fields Institute, the Association for Computing Machinery, and the American Mathematical Society, and the American Academy of Arts and Sciences. She is the winner of the 2015 John von Neumann Lecture Award, the highest honor of the Society of Industrial and Applied Mathematics. In 2016, she received an Honorary Doctorate from Leiden University. Chayes serves on numerous scientific boards and committees. She is a past VP of the American Mathematical Society, past Chair of Mathematics for the Association for the Advancement of Science, and past Chair of the Turing Award Selection Committee. She is also committed to diversity in the science and technology, and serves on many boards to increase representation of women and minorities in STEM.

Christina Lee (Microsoft Research)
Devavrat Shah (Massachusetts Institute of Technology)

Devavrat Shah is a professor of Electrical Engineering & Computer Science and Director of Statistics and Data Science at MIT. He received PhD in Computer Science from Stanford. He received Erlang Prize from Applied Probability Society of INFORMS in 2010 and NeuIPS best paper award in 2008.

More from the Same Authors