New Algorithms for Nonnegative Matrix Factorization and Beyond

16 Oct
Computer Science Colloquium Series
Ankur Moitra, MIT
Thursday, October 16, 2014 -
4:00pm to 5:15pm
Maxwell Dworkin G115

Many widely successful approaches in machine learning are heuristic:  we cannot prove good bounds on either their performance or their running time except in limited settings.  This talk will focus on designing algorithms whose performance can be analyzed rigorously.  As an example of this project, I will describe my work on the nonnegative matrix factorization problem, which has important applications throughout machine learning (and theory).  As is often the case, this problem is NP-hard when considered in full generality.  However, we introduce a sub-case called separable nonnegative matrix factorization that we believe is the right notion in various contexts.  We give a polynomial time algorithm for this problem, and leverage this algorithm to efficiently learn the topics in a Latent Dirichlet Allocation model (and beyond).  This is an auspicious example where theory can lead to inherently new algorithms that have highly-practical performance on real data sets.

This is based on joint work(s) with Sanjeev Arora, Rong Ge, Yoni Halpern, Ravi Kannan, David Mimno, David Sontag, Yichen Wu and Michael Zhu.

Speaker Bio: 

Ankur Moitra is an assistant professor in the Department of Mathematics at MIT and a principal investigator in the Computer Science and Artificial Intelligence Lab(CSAIL).  Prior to that, he was an NSF CI Fellow at the Institute for Advanced Study, and also a senior postdoc in the computer science department at Princeton University.  He completed his PhD and MS at MIT in 2011 and 2009 respectively, where he was advised by Tom Leighton and was supported by a Fannie and John Hertz Foundation Fellowship.  He received a George M. Sprowls Award (best thesis) and a William A. Martin Award (best thesis) for his doctoral and master's dissertations.

Ryan Adams
Gioia Sweetland