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

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.)