Combinatorial Inference: Statistical Uncertainty Assessment for Discrete Structures

离散结构，如网络、集群和排名，在许多现实生活中的应用中都可以观察到，包括大脑网络、蛋白质集群和投资组合选择。该项目将开发一个统一的统计框架，用于从生物学、神经科学和金融领域的大规模数据集中推断这些未知的离散结构。关于科学发现的统计推断是否可信的可复制性危机已经引起了科学界和公众的关注。PI开发了一个新领域“组合推理”，旨在填补各种现有方法之间的空白，这些方法设计用于连续量，而缺乏对离散量的有效可重复性评估。该项目还将培养下一代数据科学家掌握大规模科学数据分析的统计和计算技能。该项目旨在开发一个统一的推理框架来评估不确定性（例如，构建置信区间，测试假设和控制错误发现率），当推断离散结构包括网络，超图，聚类和排名时。将考虑三种类型的问题：(1)检验离散结构具有某些组合性质的假设（例如，网络是连通的，或者图是无三角形的）；(2)构造覆盖具有给定显著性水平的离散量的置信集（例如，图的最大程度，元素属于同一聚类，top k排序项）；(3)用错误发现率控制筛选感兴趣的离散结构（例如，图中的循环、枢纽和派系）。经典推理主要侧重于对连续参数进行假设检验和构造置信区间，在此过程中可以直接应用分析方法和理论。另一方面，现有统计模型中离散结构的研究主要集中在估计上，缺乏系统的不确定性评估推理方法。本项目寻求在四个方向上推进现代统计推断的前沿：(a)方法论：开发有效的假设检验、置信区间构建和错误发现控制程序的方法；(b)理论：发展新的概率工具，包括非渐近集中不等式和组合随机量的极限理论和普遍性现象；(c)计算：采用计算效率高的算法来执行大规模统计模型的组合推理方法；(d)基本限制：发展新的组合信息论下限，以证明所建议的推理方法的最佳性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Discrete structures like networks, clusters and ranking are observed in many real-life applications including brain networks, protein clusters, and portfolio selection. This project will develop a unified statistical framework for inferring these unknown discrete structures from large-scale datasets in biology, neuroscience, and finance. The replicability crisis on whether statistical inference for scientific discoveries can be trusted has drawn attention from both the scientific community and the public. A new field, "combinatorial inference", developed by the PI aims to fill the gap between various existing methods designed for continuous quantities and the lack of valid reproducibility assessment for discrete ones. This project will also train the next generation of data scientists to acquire statistical and computational skills for large-scale scientific data analysis. This project aims to develop a unified inference framework to assess uncertainty (e.g. constructing confidence intervals, testing hypotheses and controlling the false discovery rates) when inferring discrete structures include networks, hypergraphs, clustering and ranking. Three types of problems will be considered: (1) Testing the hypothesis that the discrete structure has certain combinatorial properties (e.g., the network is connected, or the graph is triangle-free); (2) Constructing confidence sets covering the discrete quantities with given significance level (e.g., the maximum degree of a graph, the elements belong to a same cluster, top k ranking items); (3) Screening discrete structures of interest (e.g., the cycles, hubs and cliques in a graph) with the false discovery rate control. Classical inference mainly focuses on testing hypotheses and constructing confidence intervals for continuous parameters where analytical methods and theory can be directly applied. On the other hand, exiting research on discrete structures in statistical models mainly focuses on estimation and lacks systematic inferential methods for uncertainty assessment. This project seeks to advance the frontiers of modern statistical inference in four directions: (a) Methodology: Developing efficient methods for hypothesis testing, confidence interval construction, and false discovery controlling procedures; (b) Theory: Developing new probabilistic tools including non-asymptotic concentration inequalities and limiting theory and universality phenomena for combinatorial random quantities; (c) Computation: Computationally efficient algorithms to implement the combinatorial inferential methods for large-scale statistical models; and (d) Fundamental limits: Developing new combinatorial information-theoretic lower bounds to justify the optimality of the proposed inferential methods.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.