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

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

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.