AF: SMALL: Extending the Reach of Distribution Testing via Structure

我们被大量的可用数据淹没，其中大部分自然地被视为来自大型离散领域的概率分布的样本。由于通常没有对分布的明确描述，为了有效地利用数据，必须开发有效的方法来确定基础分布持有哪些显著属性。这样的分布测试任务是科学分析的基础，近年来，我们对如何设计这样的算法的理解有了飞跃。然而，成功完成这些任务所需的样本数据量可能大得令人望而却步。该项目旨在开发利用数据中的已知结构的算法，以便给出明显更有效的解决方案。此外，该项目将开发样本效率高的方法，以确定数据是否确实具有所声称的结构。该项目将包括组织一次关于地方算法的年度讲习班(WOLA)，并将根据目前的研究编制公开提供的教育材料。该项目还将包括共同主持一个博士后项目，专门旨在扩大参与和其他指导活动。该项目将通过演讲和在咨询委员会中的服务来吸引当地公立学校的高中生。该项目研究结构在分布测试中的作用。这项研究将产生工具，用于理解测试分布特性所需的样本复杂性与对被测试分布做出的先验假设的强度之间的权衡。在第一个推力中，将开发利用样本数据中已知(或假设)现有结构属性的算法，以给出更有效的解决方案，以估计信息论数量并确定数据是否另外满足其他结构属性。在第二个推力中，将开发新的技术来设计算法，以确定数据实际上是否具有假定的结构属性。不幸的是，对于许多自然结构属性，测试数据是否满足这些结构属性的任务可能代价高昂。幸运的是，在许多重要的设置中，测试精确的结构属性是否成立可能是不必要的。因此，在第三个重点中，本项目将考虑绕过结构测试困难的技术，只测试数据具有足够的结构，使其适合在数据预期的设置中使用。具体地说，这种方法允许人们安全地使用不可知学习算法(可能是修改后的版本)，这些算法依赖于对数据的较弱分布假设。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

We are inundated with a multitude of available data, much of which is naturally viewed as samples from a probability distribution over a large discrete domain. As there is typically no explicit description of the distribution, in order to make effective use of the data, one must develop efficient methods of determining which salient properties are held by the underlying distribution. Such distribution testing tasks are fundamental to scientific analysis, and recent years have seen a leap in our understanding of how to design such algorithms. However, the amount of sample data needed to successfully achieve many of these tasks can be prohibitively large. This project aims to develop algorithms which capitalize on known structures in the data in order to give significantly more efficient solutions. In addition, this project will develop sample-efficient methods of ascertaining whether the data indeed has the claimed structure. This project will include the organization of an annual Workshop on Local Algorithms (WOLA) and will produce publicly available educational material based on current research. The project will also include co-chairing a postdoctoral program specifically aimed at broadening participation and other mentoring activities. The project will engage with high school students in local public schools by giving presentations and serving on advisory committees.This project studies the role of structure in distribution testing. This research will lead to tools for understanding the tradeoffs between the sample complexity required to test properties of distributions and the strength of the assumptions made a priori on the distributions being tested. In a first thrust, algorithms will be developed which capitalize on known (or assumed) existing structural properties in the sample data to give significantly more efficient solutions for estimating information-theoretic quantities and determining whether the data additionally satisfies other structural properties. In a second thrust, new techniques will be developed for designing algorithms to determine whether the data in fact has the assumed structural properties. Unfortunately, for many natural structural properties, the task of testing whether data satisfies these structural properties can be expensive. Fortunately, in many important settings, it can be the case that testing whether the precise structural properties hold is unnecessary. Thus, in a third thrust, this project will consider techniques that bypass the difficulty of testing for structure by testing only that the data has enough structure to make it amenable for use in the settings for which the data is intended. Specifically, such methods allow one to safely use (possibly modified versions of) agnostic learning algorithms that depend on a weaker distributional assumption on the data.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.