Machine learning is a flourishing field with a plethora of algorithmic techniques. In almost all cases, we have no provable guarantees on the performance of these algorithms/heuristics ---neither on their running time, nor on the quality of solutions they return. In fact in many settings, the underlying algorithmic problems are provably intractable (e.g., NP-hard or worse)! This talk will argue that this seeming intractability may arise because many models used in machine learning are more general than they need to be.
This point will be illustrated using our recent results on designing provable algorithms for nonnegative matrix factorization (NMF), a well-known NP-hard problem that is popular in many areas of machine learning. We present the first algorithms that can find factorizations of rank $r$ in polynomial time (in the matrix size, not $r$). We also introduce a natural new subcase of NMF called "separable NMF" which we think is the proper notion to use in many contexts. We give fully polynomial-time algorithms for separable NMF. We go on to use these algorithms for more general problems involving learning of topic models (such as the wellknown Latent Dirichlet Allocation of Blei et al).
Joint work with Rong Ge, Ravi Kannan, Ankur Moitra.
