Machine learning is a vibrant field with many rich techniques.
However, these approaches are often 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.
I will also briefly describe some of my other work on learning,
including mixtures of Gaussians and robust linear regression, as well
as promising directions for future work.
Ankur Moitra is 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. He received a
George M. Sprowls Award (best thesis) and a William A. Martin Award
(best thesis) for his doctoral and master's dissertations. He has
worked in numerous areas of algorithms, including approximation
algorithms, metric embeddings, combinatorics and smoothed analysis,
but lately has been working at the intersection of algorithms and
learning.
