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

我们被大量可用的数据淹没，其中大部分自然被视为大离散域上概率分布的样本。由于通常没有对分布的明确描述，为了有效地利用数据，必须开发有效的方法来确定底层分布具有哪些显著特性。这种分布测试任务是科学分析的基础，近年来我们对如何设计这种算法的理解有了飞跃。然而，成功实现这些任务中的许多任务所需的样本数据量可能非常大。该项目旨在开发利用数据中已知结构的算法，以提供更有效的解决方案。此外，该项目还将开发样本有效的方法来确定数据是否确实具有所声称的结构。该项目将包括组织一次关于局部算法的年度研讨会，并将根据目前的研究制作公开的教育材料。该项目还将包括共同主持一个专门旨在扩大参与和其他指导活动的博士后项目。该项目将通过演讲和咨询委员会的服务与当地公立学校的高中生接触。该项目研究结构在分布测试中的作用。这项研究将导致工具，了解样本的复杂性，以测试属性的分布和强度的假设被测试的分布先验之间的权衡。在第一个推力，算法将开发利用已知的（或假设的）现有的结构特性的样本数据，以提供更有效的解决方案，估计信息理论的数量，并确定数据是否还满足其他结构特性。在第二个推力中，将开发新的技术来设计算法，以确定数据实际上是否具有假定的结构特性。不幸的是，对于许多自然结构属性，测试数据是否满足这些结构属性的任务可能是昂贵的。幸运的是，在许多重要的环境中，测试精确的结构特性是否保持是不必要的。因此，在第三个目标中，本项目将考虑通过测试数据具有足够的结构以使其适用于数据预期的设置来绕过结构测试的困难的技术。具体来说，这种方法允许人们安全地使用（可能是修改版本的）不可知学习算法，这些算法依赖于对数据的较弱分布假设。该奖项反映了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.