ISL Colloquium presents Iterative Collaborative Filtering for Sparse Noisy Tensor Estimation

Iterative Collaborative Filtering for Sparse Noisy Tensor Estimation
Thursday, October 31, 2019 - 4:30pm
Packard 101
Christina Lee Yu (Cornell University)
Abstract / Description: 

We present a generalization of the collaborative filtering algorithm for the task of tensor estimation, i.e. estimating a low-rank 3-order n-by-n-by-n tensor from noisy observations of randomly chosen entries in the sparse regime. Not only does the algorithm have desirable computational properties, it also provably achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Furthermore, our analysis results in high probability bounds on the infinity norm of the error, as opposed to the weaker MSE bounds achieved by previous approaches. Our proposed algorithm uses the matrix obtained from the ''flattened'' tensor to compute similarity with respect to a corresponding observation graph. The algorithm recovers the tensor with max entrywise error decaying to 0 with high probability as long as the entries are sampled uniformly at a density of Omega(n^{-3/2 + epsilon}) for any arbitrarily small epsilon > 0. This sample complexity threshold (nearly) matches a conjectured lower bound as well as the ''connectivity threshold'' of the corresponding observation graph used in our algorithm, providing a different angle to explain the conjectured lower bound.

The Information Systems Laboratory Colloquium (ISLC)

is typically held in Packard 101 every Thursday at 4:30 pm during the academic year. Coffee and refreshments are served at 4pm in the second floor kitchen of Packard Bldg.

The Colloquium is organized by graduate students Joachim Neu, Tavor Baharav and Kabir Chandrasekher. To suggest speakers, please contact any of the students.

To receive email notifications of seminars you can join the ISL mailing list.


Christina Lee Yu is an assistant professor at Cornell University in the Operations Research and Information Engineering Department. Prior to joining Cornell, she was a postdoc at Microsoft Research New England. She received her PhD and MS in Electrical Engineering and Computer Science from MIT in the Laboratory for Information and Decision Systems. She received her BS in Computer Science from California Institute of Technology. She is a recipient of the MIT Jacobs Presidential Fellowship, the NSF Graduate Research Fellowship, and the Claude E. Shannon Research Assistantship. Her research focuses on designing and analyzing scalable algorithms for processing social data based on principles from statistical inference.