About the Courses

The Method of Moments in Computer Science and Beyond
(Ankur Moitra)

In this course we will introduce the method of moments in its various incarnations, and will use it to design algorithms with provable guarantees for some of the fundamental problems in machine learning.

The method of moments has a long and storied history. It was introduced in the seminal work of Karl Pearson (1896) with the goal of fitting a mixture model to data. Provable guarantees for these sorts of applications came only much later, by understanding the constraints imposed on the parameters as a system of polynomial equations, and leveraging their stability properties.

In recent years, there has been a groundswell of work on applying related techniques called tensor decompositions to other problems in machine learning, including learning topic models, learning hidden markov models and community detection. We will introduce some of the basic algorithms in this space, and chronicle the curious history of how (and why) they were rediscovered numerous times across many communities. We will then leverage them to give algorithms for learning the parameters of various latent variable models.

Finally, we will cover some emerging directions where the method of moments has been particularly fruitful. We use it to give provably robust algorithms for estimating the mean and covariance of well-behaved high-dimensional distributions. And we will survey applications in the sciences where symmetries play a key role, and connections to invariant theory.

Polyhedral Techniques in Combinatorial Optimization
(Ola Svensson)

In this course, we introduce and use polyhedral techniques to devise new algorithms for central problems in combinatorial optimization. In particular, we introduce techniques for using linear programming formulations, even exponential-sized ones, to extract structure from problem instances that guides the design of our algorithms.

Somewhat surprisingly, similar polyhedral techniques can be harnessed to design new algorithms for seemingly disparate problems. The course will focus on two such results: a constant-factor approximation algorithm for the asymmetric traveling salesman problem and a deterministic parallel algorithm for the perfect matching problem. The so-called laminar structure of the considered linear programming formulations plays a central role in both these results.

Finally, we discuss several intriguing research directions and open questions related to these problems.