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

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

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.