The Statistics Seminar speaker for Wednesday, March 6, 2019, is Christina Lee Yu, an Assistant Professor in Operations Research and Information Engineering (ORIE) at Cornell University. Prior to joining ORIE, Prof. Yu was a postdoc at Microsoft Research New England. She received her PhD and MS in Electrical Engineering and Computer Science from the Laboratory for Information and Decision Systems at Massachusetts Institute of Technology. She received her B.S. in Computer Science from California Institute of Technology. Prof. Yu 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.
Talk: Iterative Collaborative Filtering for Sparse Noisy Tensor Estimation
Abstract:
We consider the task of tensor estimation, i.e. estimating a low-rank 3-order n x n x n tensor from noisy observations of randomly chosen entries in the sparse regime. In the context of matrix (2-order tensor) estimation, a variety of algorithms have been proposed and analyzed in the literature including the popular collaborative filtering algorithm that is extremely well utilized in practice. However, in the context of tensor estimation, there is limited progress. No natural extensions of collaborative filtering are known beyond "flattening" the tensor into a matrix and applying standard collaborative filtering.
As the main contribution of this work, we introduce a generalization of the collaborative filtering algorithm for the setting of tensor estimation and argue that it achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Interestingly, our generalization uses the matrix obtained from the "flattened" tensor to compute similarity as in the classical collaborative filtering but by defining a novel "graph" using it. The algorithm recovers the tensor with mean-squared-error (MSE) decaying to 0 as long as each entry is observed independently with probability p = Omega(n^{-3/2 + \epsilon}) for any arbitrarily small epsilon > 0. It turns out that p = Omega(n^{-3/2}) is the conjectured lower bound as well as "connectivity threshold" of graph considered to compute similarity in our algorithm.