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

过度参数化、期望最大化算法的全局收敛及其他

• 批准号: 2112918
• 负责人: Huibin Zhou
• 金额: $ 37万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2112918&HistoricalAwards=false
• 关键词: Overparameterization; Global; Convergence; Expectation; Maximization

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.

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

项目成果

Optimal estimation of high-dimensional Gaussian location mixtures

• DOI: 10.1214/22-aos2207
• 发表时间: 2020-02
• 期刊: The Annals of Statistics
• 作者: Natalie Doss;Yihong Wu;Pengkun Yang;Harrison H. Zhou