Ten Steps of EM Suffice for Mixtures of Two Gaussians

Presented on March 6, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E.Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. His research interests lie in theoretical computer science and its interface with economics and probability.Runtime: 63:35 minutesThe Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for mixtures of two Gaussians with known covariance matrices. We show that EM converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1% error estimation of the means. (Joint work with Christos Tzamos and Manolis Zampetakis.