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

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

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.