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

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

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.