CAREER: Statistical Inference on Large Domains and Large Networks: Fundamental Limits and Efficient Algorithms

职业：大型域和大型网络的统计推断：基本限制和高效算法

• 批准号: 1651588
• 负责人: Yihong Wu
• 金额: $ 57.1万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-03-01 至 2023-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1651588&HistoricalAwards=false
• 关键词: CAREER; Statistical; Inference; Large; Domains

The emergence of data science has brought about new perspectives on age-old statistical questions. Driven by contemporary applications such as neuroscience, functional genomics and social networks, an emerging research thread in high-dimensional statistics deals with new problems of a combinatorial nature, most importantly, inference on large domains and large graphs, such as entropy estimation on large alphabets, detecting community structures in networks, all of which rely on exploiting the intrinsic or extrinsic low-dimensionality of the problem. On the other hand, an important element absent from the classical statistical paradigm is the computational complexity of inference procedures, which is becoming increasingly relevant dealing with large-scale noisy datasets. The PI has detailed plans for mentoring both undergraduate and graduate students, targeting specifically at members of the under-represented communities.Combining both statistical and computational perspectives, this research develops an interdisciplinary program aiming to advance the understanding of the fundamental inferential and algorithmic limits of statistical estimation on large domains and large networks, including functional estimation on large alphabets, learning graph properties with network sampling, extrapolating unseen species. These objectives come with a set of theoretical and practical challenges, which can be effectively addressed by a new combination of insights and techniques from information theory, high-dimensional statistics, approximation theory, random graphs and matrices, and optimization. In addition to determining the statistical limits and designing efficient and scalable procedures, which provide key enabling technologies for such high-impact applications of data science as neuroscience, gene association networks, and social network analysis, a major innovation lies in rigorously identifying the optimal statistical performance under complexity constraints and, complementarity, understanding the inferential power and limitations of important classes of algorithms such as spectral methods, relaxation hierarchies, and message-passing algorithms.

数据科学的出现为古老的统计问题带来了新的视角。在神经科学、功能基因组学和社交网络等当代应用的推动下，高维统计学中的一个新兴研究思路涉及组合性质的新问题，最重要的是，大域和大图上的推理，如大字母表上的熵估计，检测网络中的社区结构，所有这些都依赖于利用问题的内在或外在低维性。另一方面，经典统计范式中缺少的一个重要元素是推理过程的计算复杂性，这在处理大规模噪声数据集时变得越来越重要。PI对本科生和研究生都有详细的指导计划，特别针对代表性不足的社区成员。结合统计和计算的观点，这项研究开发了一个跨学科的项目，旨在促进对大域和大网络上统计估计的基本推理和算法限制的理解，包括大字母表上的功能估计，通过网络采样学习图形属性，推断未知物种。这些目标带来了一系列理论和实践挑战，这些挑战可以通过信息论，高维统计，近似理论，随机图和矩阵以及优化的见解和技术的新组合来有效解决。除了确定统计限制和设计有效和可扩展的程序，为神经科学，基因关联网络和社交网络分析等数据科学的高影响力应用提供关键的使能技术之外，一个主要的创新在于严格识别复杂性约束下的最佳统计性能，互补性，理解推理能力和算法的重要类别，如谱方法，松弛层次和消息传递算法的局限性。

项目成果

Sample complexity of the distinct elements problem

不同元素问题的样本复杂度

• DOI: 10.4171/msl/1-1-2
• 发表时间: 2018
• 期刊: Mathematical Statistics and Learning
• 作者: Wu, Yihong;Yang, Pengkun
• 通讯作者: Yang, Pengkun

Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis

• DOI: 10.1007/s10208-022-09570-y
• 发表时间: 2022-06
• 期刊: Foundations of Computational Mathematics
• 影响因子: 3
• 作者: Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu

Random Graph Matching at Otter’s Threshold via Counting Chandeliers

通过计数枝形吊灯在水獭阈值上进行随机图匹配

• 发表时间: 2023
• 期刊: Proceedings of the annual ACM Symposium on Theory of Computing
• 作者: Mao, Cheng;Wu, Yihong;Xu, Jiaming;Yu, Sophie H.
• 通讯作者: Yu, Sophie H.

Random Graph Matching in Geometric Models: the Case of Complete Graphs

• 发表时间: 2022-02
• 作者: Haoyu Wang;Yihong Wu;Jiaming Xu;Israel Yolou

Statistical and computational limits for sparse matrix detection

稀疏矩阵检测的统计和计算限制

• DOI: 10.1214/19-aos1860
• 发表时间: 2020
• 期刊: Annals of Statistics
• 影响因子: 4.5
• 作者: Cai, T. Tony;Wu, Yihong
• 通讯作者: Wu, Yihong