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

期望最大化（EM）算法是统计推断中最流行的算法之一。尽管在统计学和机器学习方面有广泛的成功应用，但很少有有限样本理论分析来解释EM及其变体的有效性。近年来，在EM算法的全局收敛性保证方面取得了一些令人鼓舞的成功，但往往是在不现实和不切实际的假设下。PI将整合深度学习中最近成功的超参数化与EM，以克服上述限制。本项目的研究将通过提供全局收敛性和统计最优性的保证，显著推进统计学和机器学习中著名的算法，包括EM、平均场变分推理和吉布斯抽样。该研究将有助于解决一系列重要和经典统计模型的非凸优化挑战，并阐明最近深度学习的成功。EM的广泛应用，平均场变分推理，吉布斯抽样和聚类的重要性确保了我们朝着我们的目标所取得的进展将对包括神经科学和医学在内的广泛的科学界产生重大影响。该项目的研究成果将通过研究文章、讲习班和系列研讨会传播给其他学科的研究人员。该项目将通过教授专题课程和组织讲习班和研讨会来整合研究和教育，以支持研究生和博士后，特别是妇女、代表性不足的少数民族、国内学生和年轻研究人员研究这一主题。PI将开发在可能最弱的假设下获得具有未知簇数的一般类别潜在变量模型估计的全局收敛性的方法。PI将解决以下问题：1)我们能否证明过度参数化的EM全局收敛于真实参数，而不需要任何分离条件，也不需要知道一定距离下的簇数和簇大小（如Wasserstein）？2)算法收敛速度有多快？3)参数估计和聚类错误率是什么？它们与最优统计精度相比如何？4)如果统计上不是最优的，我们可以通过添加由过参数化EM的输出初始化的第二阶段EM来实现最优性吗？有三个目标，以发展一个全面的理论来分析超参数化电磁，并超越：1)研究高斯混合模型的参数估计和潜在聚类恢复的过参数化EM的全局收敛性以及两阶段EM的统计最优性；2)将两阶段EM扩展到其变体，包括两阶段平均场变分推理和Gibbs抽样，并考虑对一类过参数化算法进行统一分析；3)将高斯混合的分析扩展到一般位置混合模型和随机块模型，并可能建立一个统一的潜在变量模型框架。此外，PI将与耶鲁大学儿童研究中心和耶鲁大学治疗放射学系密切合作，探索适合神经科学、自闭症谱系障碍和癌症风险分层的EM算法及其变体。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.