BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

(Quasi)-Efficiently Learning Mixtures of Gaussians at the Statistically Optimal Separation Kothari, Pravesh


Recovering a hidden signal or structure in the presence of random noise is a recurring theme in fundamental problems arising in computational complexity, cryptography, machine learning, and statistics. In the recent years, a Sum-of-Squares method, a hierarchy of generic semi-definite programming relaxations, has yielded a systematic approach for such "parameter estimation" problems. In this talk, I'll illustrate the SoS method for parameter estimation by means of a recent application of to learning mixture of gaussians with information theoretically optimal cluster-separation in quasi-polynomial time. No sub-exponential time algorithm was previously known in this regime. Based on joint works with Jacob Steinhardt and David Steurer.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International