Tuesday, February 17, 2015 - 3:00pm
209 W. Eighteenth Ave. (EA), Room 170
Statistical and Computational Guarantees for the EM Algorithm
Sivaraman Balakrishnan, University of California, Berkeley
The expectation-maximization (EM) algorithm is an iterative method for finding maximum-likelihood estimates of parameters in statistical models with unobserved latent variables. Along with Markov Chain Monte Carlo (MCMC), it is one of the two computational workhorses that provided much impetus for statistics in entering its modern “computation-intensive” phase. Much is known about the EM algorithm, its convergence properties, and its susceptibility to local optima. However, despite the existence of multiple fixed points, on a variety of statistical problems the EM algorithm has been observed empirically to perform well given either a reasonable initialization or with several random starts.
In this talk, I will introduce novel techniques to theoretically characterize some of the empirically observed behavior of the EM algorithm and give conditions under which the EM algorithm converges to near globally optimal parameter estimates. In particular, I will show the surprising result that for several canonical latent variable models there are large regions of the parameter space over which every fixed point of the EM algorithm is close to a population global optimum. I will conclude with a discussion of some of my other research interests, presenting a few vignettes from my work on clustering and topological data analysis.