Polynomial Methods in Learning and Statistics

My goal in this talk is to survey some of the emerging applications of polynomial methods in both learning and in statistics. I will give two examples from my own work in which the solution to well-studied problems in learning and statistics can be best understood through the language of algebraic geometry.

I will present work on the problem of learning the parameters of a mixture of Gaussians, given random samples from the distribution. The theme here is that the method of moments can be shown to provably recover good estimates to the true parameters precisely because systems of polynomial equations are relatively stable. In fact, I will show that noisy estimates of the first six moments of a mixture of two Gaussians suffice to recover good estimates to the true mixture parameters, thus justifying an approach that dates back to Karl Pearson.

I will also present work on the problem of computing the nonnegative rank of a matrix, which is a parameter that is of fundamental importance in machine learning, combinatorics and communication complexity. Here the message will be that systems of polynomial equations are unreasonably expressive, and the nonnegative rank of a matrix can be equivalently encoded as a non-emptiness question for a semi-algebraic set with only a small number of variables. From this, we obtain the first algorithm for computing a nonnegative matrix factorization with inner-dimension $r$ (if one exists) that runs in polynomial time for any fixed $r$.

The first part of this talk is based on joint work with Adam Kalai and Greg Valiant. I will also present independent work of Mikhail Belkin and Kaushik Sinha on this same problem. The second part of this talk is based on joint work with Sanjeev Arora, Rong Ge and Ravi Kannan.