Overparameterization, Global Convergence of the Expectation-Maximization Algorithm, and Beyond

The expectation-maximization (EM) algorithm is among the most popular algorithms for statistical inference. Despite a wide range of successful applications in both statistics and machine learning, there is little finite-sample theoretical analysis explaining the effectiveness of EM and its variants. Recently, there have been some encouraging successes on the global convergence guarantee of the EM algorithm, but often under unrealistic and impractical assumptions.

The PI will integrate the recent success of overparametrization in deep learning with EM to overcome the aforementioned limitations. The research presented in this project will significantly advance the celebrated algorithms in statistics and machine learning including EM, mean-field variational inference, and Gibbs sampling by providing guarantees of global convergence and statistical optimalities.

The research will help address the non-convex optimization challenges for a range of important and classical statistical models and shed light on the recent successes of deep learning. The wide range of applications of EM, mean-field variational inference, and Gibbs sampling and the importance of clustering ensure that the progress we make towards our objectives will have a great impact on the broad scientific community which includes neuroscience and medicine.

Research results from this project will be disseminated through research articles, workshops, and seminar series to researchers in other disciplines. The project will integrate research and education by teaching monograph courses and organizing workshops and seminars to support graduate students and postdocs, particularly women, underrepresented minorities, domestic students, and young researchers, to work on this topic.

The PI will develop methods for obtaining global convergence under possibly the weakest assumptions for a general class of latent variable models’ estimation with an unknown number of clusters. The PI will address the following questions: 1) can we show that the overparameterized EM converges globally to the true parameters without any separation condition and any knowledge of the number of clusters and cluster sizes under a certain distance (such as Wasserstein)? 2) how fast does the algorithm converge? 3) what are the parameter estimation and clustering error rates and how do they compare to the optimal statistical accuracy? and 4) if not optimal statistically, can we achieve the optimality by adding a second stage EM initialized by the output of the overparameterized EM?

There are three aims to develop a comprehensive theory to analyze the overparameterized EM and go beyond: 1) studying the global convergence of overparameterized EM for Gaussian Mixtures for both parameter estimation and latent cluster recovery and statistical optimality of the two-stage EM, 2) extending the two-stage EM to its variants including two-stage mean-field variational inference and Gibbs sampling and considering a unified analysis for a class of overparameterized algorithms, and 3) extending the analysis for Gaussian mixtures to general location mixture models and Stochastic Block Models and possibly a unified framework of latent variable models. In addition, the PI will work closely with the Yale Child Study Center and Yale Therapeutic Radiology Department to explore the appropriate EM algorithm and its variants for neuroscience, autism spectrum disorder, and cancer risk stratification.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.