Expectation-Maximization, Power Iteration, and Non-convex Optimization in Learning and Statistics

Monday, September 25, 2017 - 4:00pm to Tuesday, September 26, 2017 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Constantinos Daskalakis



Building and Room number



The 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. The broader theme of our talk are non-convex methods in learning and statistics. We discuss an analytical approach towards establishing convergence guarantees for these methods based on a converse to Banach's fixed point theorem. (Based on joint work with Christos Tzamos and Manolis Zampetakis.)


Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and its interface with economics and probability. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, the 2012 Microsoft Research Faculty Fellowship, and the 2015 Research and Development Award by the Vatican Giuseppe Sciacca Foundation. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.