III: Small: RUI: Scalable and Iterative Statistical Testing of Multiple Hypotheses on Massive Datasets

现代科学实践植根于对数据假设的统计检验。为了限制错误发现的风险，测试必须提供严格的统计保证。这项任务非常具有挑战性，因为今天有大量丰富的数据，而且科学家们想要在相同的数据上测试的复杂假设越来越多。为了使科学进步，从而促进社会和人类福祉，最重要的是科学家获得克服这些挑战的工具。该项目将设计用于统计假设检验的新计算方法，通过将现代统计结果与知识发现和数据挖掘领域的最新方法相结合来解决上述所有挑战，数据挖掘是计算机科学领域处理数据的有效分析。作为教育活动的一部分，该项目将为大学课程编写材料，以确保下一代科学家和计算机科学家掌握知识和实践知识，确保通过使用和扩展该项目开发的方法，对数据进行可靠的分析和假设检验。一个多元化的本科生群体将参与该项目的研究和教育部分。该项目的研究人员团队将设计和数学分析算法，使统计假设检验沿着沿着多个维度迭代和可扩展。当在中等规模的数据集上测试单个假设时，许多现有的统计程序已经在计算上很昂贵，并且随着数据量或假设数量的增加变得更加低效。沿着数据复杂性的维度，可用的测试通常缺乏可伸缩性，因为限于简单类型的数据（例如，二进制表），而较少的方法可用于丰富的数据，如属性图或面板时间序列。缺乏可扩展的方法可能部分是由于假设检验满足严格的统计保证的要求（例如，全族错误率（FWER）和错误发现率（FDR）），以确保连续推断是合理的。此外，数据分析实践的迭代方面在统计检验中被忽略了，但考虑到这一点对于确保满足这些保证至关重要。该项目将开发算法，用于在大量丰富的数据集上对多个复杂假设进行可扩展和迭代的统计测试，同时仅对数据生成过程施加弱假设，并控制FWER和FDR。这些结果将通过将计算机科学研究的两个领域结合起来来实现，到目前为止，这两个领域的接触点非常有限：统计学习理论和数据挖掘。在这个项目中开发的新方法将使用来自前者的概念，如（局部）Rademacher平均值，覆盖数和伪维数，以利用被测试的假设类的结构，并实现更好的样本复杂性界限，这转化为更高的统计能力和改进的FWER/FDR控制，即使在迭代数据分析设置。这些概念将适用于统计假设检验，并加强以充分利用其实际用途，特别是在丰富的数据集和数据点之间存在依赖关系的情况下。项目团队将使用模式挖掘的知识发现任务中的技术来有效地探索假设空间，以过滤掉那些肯定不重要的假设。为了实现这一目标，项目团队将为不同测试的p值函数开发新的界限，并将这些技术应用于丰富的数据集，如属性图。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern scientific practice is rooted on statistical testing of hypotheses on data. To limit the risk of false discoveries, the tests must offer strict statistical guarantees. The task is very challenging due to the sheer amount of rich data available today, and to the ever-increasing number of complex hypotheses that scientists want to test on the same data. In order for science to advance, and therefore advance society and human well-being, it is of the foremost importance that scientists are given tools that overcome these challenges. This project will design novel computational methods for statistical hypothesis testing that tackle all the above challenges by combining modern statistical results with recent approaches from the area of knowledge discovery and data mining, a field of computer science dealing with the efficient analysis of data. As part of the educational activities, this project will develop materials for college-level courses to ensure that the next generation of scientists and computer scientists posses the intellectual and practical knowledge to ensure a statistically-sound analysis of data and testing of hypotheses by using and extending the methods developed in the project. A diverse cohort of undergraduate students will be involved in the research and educational components of the project.The team of researchers in this project will design and mathematically analyze algorithms to make statistical hypothesis testing iterative and scalable along multiple dimensions. Many existing statistical procedures are already computationally expensive when testing a single hypothesis on moderate-size datasets, and become even more inefficient as the amount of data or the number of hypotheses grows. Along the dimension of data complexity, available tests often lack scalability because limited to simple types of data (e.g., binary tables), while fewer methods are available for rich data such as attributed graphs or panel time-series. The lack of scalable methods may be due in part to the requirement that hypothesis tests satisfy stringent statistical guarantees (e.g., the Family-Wise Error Rate (FWER) and the False Discovery Rate (FDR)) to ensure that the successive inference is sound. Additionally, the iterative aspect of the practice of data analysis has been ignored for statistical tests, but considering it is crucial in order to ensure that these guarantees are satisfied. This project will develop algorithms for the scalable and iterative statistical testing of multiple complex hypotheses on massive rich datasets, while imposing only weak assumptions on the data generation process, and controlling the FWER and the FDR. These results will be achieved by bringing together two areas of computer science research that had, until now, only very limited points of contact: statistical learning theory and data mining. The novel methods developed in this project will use concepts from the former, such as (local) Rademacher averages, covering numbers, and pseudodimension, to exploit the structure of the class of hypotheses being tested and achieve better sample complexity bounds, which translate to higher statistical power and improved control of the FWER/FDR, even in an iterative data analysis setting. These concepts will be adapted to statistical hypothesis testing and strengthen to fully exploit their practical usefulness, especially on rich datasets and in the presence of dependencies between the data points. The project team will use techniques from the knowledge discovery task of pattern mining to efficiently explore the space of hypotheses to filter out those that are definitively not significant. To reach this goal, the project team will develop novel bounds for the p-value functions of different tests and adapt these techniques to rich datasets such as attributed graphs.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.