The EM algorithm for high-dimensional Gaussian mixtures

The expectation-maximization (EM) algorithm is a computationally efficient heuristic aiming at approximating the maximum likelihood estimator (MLE) in the presence of latent variables. Curiously, despite its simplicity, widespread, and lengthy history, theoretical guarantees on its convergence radius, requierd number of iterations, and statistical accuracy have appeared only recently. Most notably, [Balakrishnan et. al 2017] provided guarantees for general models, but which are not sharp in general, while [Xu et. al 2016, Daskalakis et. al 2017, Wu and Zhou 2019] considered EM for the two-component Gaussian mixture model in which the two components have equal weight, which ultimately lead to sharp results.

In this talk, I will focus on the two-component Gaussian mixture model with non-equal weights. While the EM iteration in this model suffers from luck of symmetry, I will nonetheless show a global convergence property for its iteration. The proof is based on an indirect argument, which quantifies the intuitive observation that the EM iteration should converge faster as the lower weight tends to zero. I will also show that the EM algorithm is adaptively optimal to the separation between the two components, both in terms of the statistical accuracy, and the required number of iterations. The error rates obtained for the EM iteration span the full spectrum between the parametric error rates for the standard Gaussian location model and the error rates in the balanced two-component Gaussian mixture.

  Finally, in a different avenue, I will discuss the problem of learning data-dependent partitioning estimates to nonparametric regression functions. I will describe an alternating minimization algorithm which systematically addresses this challenge, and present convergence guarantees.

Short Bio:
Nir Weinberger is an MIT-Technion postdoctoral fellow of IDSS and LIDS at the Massachusetts Institute of Technology (MIT), hosted by Guy Bresler. He received his B.Sc. and M.Sc. degrees in Electrical Engineering from Tel-Aviv University, Israel, in 2006 and d2009, respectively, both summa cum laude, and his P.hD. in Electrical Engineering from the Technion, Israel Institute of Technology, in 2017.