Statistical and Computational Guarantees of Three Siblings: Expectation-Maximization, Mean-Field Variational Inference, and Gibbs Sampling

三个兄弟算法，期望最大化（EM），平均场变分推理和吉布斯抽样，是统计推断中最流行的算法。这些迭代算法是密切相关的：每一个都可以被看作是另一个的变体。尽管在统计学和机器学习方面有广泛的成功应用，但很少有理论分析解释这些算法对高维和复杂模型的有效性。本项目提出的研究将通过揭示统计和计算保证以及统计推断的潜在陷阱，显著推进对这些迭代算法的理论理解。EM、平均场变分推理和吉布斯抽样的广泛应用确保了我们朝着目标所取得的进展将对包括神经科学和社会科学在内的广泛科学界产生巨大影响。该项目的研究成果将通过研究文章、讲习班和研讨会系列传播给其他学科的研究人员。该项目将通过教授专题课程和组织讲习班和研讨会来整合研究和教育，以帮助研究生和博士后，特别是少数民族、妇女、国内学生和年轻研究人员研究这一主题。此外，PI将与耶鲁儿童研究中心和耶鲁网络科学研究所密切合作，探索神经科学、自闭症谱系障碍、社会科学和数据科学教育的适当和严格的算法。PI通过解决以下问题来研究这些迭代算法：1)算法实现全局收敛到最优统计精度的尖锐（几乎是充分必要的）初始化条件是什么？2)算法收敛速度有多快？3)什么是保证全局收敛的尖锐分离条件或信号强度？4)估计错误率和聚类错误率是什么？它们与最优统计精度相比如何？发展一个综合的分析迭代算法的理论有三个阶段：1)研究高斯混合的EM对全局参数估计和潜在聚类恢复的统计和计算保证；2)将EM扩展到平均场变分推理和吉布斯抽样，并考虑对一类迭代算法的统一分析；3)将高斯混合和随机块模型扩展到潜在变量模型的统一框架。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Three sibling algorithms, expectation-maximization (EM), mean-field variational inference, and Gibbs sampling, are among the most popular algorithms for statistical inference. These iterative algorithms are closely related: each can be seen as a variant of the others. Despite a wide range of successful applications in both statistics and machine learning, there is little theoretical analysis explaining the effectiveness of these algorithms for high-dimensional and complex models. The research presented in this project will significantly advance the theoretical understanding of those iterative algorithms by unveiling the statistical and computational guarantees as well as potential pitfalls for statistical inference. The wide range of applications of EM, mean-field variational inference, and Gibbs sampling ensure that the progress we make towards our objectives will have a great impact in the broad scientific community which includes neuroscience and social sciences. 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 help graduate students and postdocs, particularly minority, women, and domestic students and young researchers, work on this topic. In addition, the PI will work closely with the Yale Child Study Center and the Yale Institute for Network Science to explore appropriate and rigorous algorithms for neuroscience, autism spectrum disorder, social sciences, and data science education.The PI studies these iterative algorithms by addressing the following questions: 1) what is the sharp (nearly necessary and sufficient) initialization condition for the algorithm to achieve global convergence to optimal statistical accuracy? 2) how fast does the algorithm converge? 3) what are sharp separation conditions or signal strengths to guarantee global convergence? 4) what are the estimation and clustering error rates and how do they compare to the optimal statistical accuracy? There are three stages to developing a comprehensive theory for analyzing iterative algorithms: 1) studying statistical and computational guarantees of EM for Gaussian mixtures for both global parameter estimation and latent cluster recovery, 2) extending EM to mean-field variational inference and Gibbs sampling, and considering a unified analysis for a class of iterative algorithms, 3) extending Gaussian mixtures and Stochastic Block Models to a unified framework of latent variable models.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.