The Complexity of Testing Distributions

在各种各样的计算环境中，数据最自然地被视为来自分布，确定基础分布是否满足各种属性通常是至关重要的。这些属性的例子包括两个分布在统计距离上是近还是远，联合分布是否独立，以及分布是否具有高熵。对于大多数这样的属性，近似分布的标准统计技术导致使用在域大小上几乎是线性的许多样本的算法。直到最近，大范围分布的线性样本复杂性可能令人望而生畏，但令人惊讶的是，很少受到关注。然而，对这些问题的新兴趣来自许多方向，包括数据挖掘、物理和机器学习在神经生物学中的应用。最近的结果表明，对于大区域的情况，人们可以获得比标准技术显著更有效的结果。这项研究的智力价值将导致对识别概率分布的各种自然属性所需的样本、时间和空间复杂性的理解。拟议的研究将集中于确定哪些属性可以通过一些在域大小中次线性的样本来理解，并将导致对特定于这些约束的算法设计方面的理解。将考虑的问题包括：考虑测试以前未研究的性质的复杂性、找到适用于分布测试问题类别的一般技术、调查分布测试的新模型、了解可在次线性时间内解决的测试问题的结构方面，以及进一步了解计算复杂性与样本复杂性之间的关系。这项建议的更广泛影响包括教育和劳动力发展部分。这项提议的教育部分涉及设计适合各级学生的测试分布的算法的课程材料。已经收集了足够的材料来开发一门研究生课程，突出这一领域出现的技术主体。最近的一些进展非常适合向本科生传达随机算法背后的基本思想。国际学生联合会因其在本科教育方面的努力而被授予两项教学奖。PI将继续努力成为本科生、研究生和博士后研究人员的顾问和导师，其中包括几位在研究生涯中取得成功的女性。国际和平研究所目前正在共同组织一次关于次线性算法的达格斯图尔研讨会。重点是邀请和支持有兴趣在该地区工作的研究生。最后，还将利用网络、研讨会、讲习班和会议介绍、期刊文章和针对更广泛受众的调查文章来传播这些想法。

In a wide variety of computational settings, where the data is most naturally viewed as coming from a distribution, it is often crucial to determine whether the underlying distribution satisfies various properties. Examples of such properties include whether two distributions are close or far in statistical distance, whether a joint distribution is independent, and whether a distribution has high entropy. For most such properties, standard statistical techniques which approximate the distribution lead to algorithms which use a number of samples that is nearly linear in the domain size. Until very recently, distributions over large domains, for which linear sample complexity can be daunting, have received surprisingly little attention. However, new interest in these questions comes from many directions, including data mining, Physics and machine learning applications in Neurobiology. Recent results have shown that one can achieve results which are significantly more efficient than the standard techniques for the case of large domains.The intellectual merit of this research will lead to an understanding of the sample, time and space complexity required to identify various natural properties of a probability distribution. The proposed research will focus on determining which properties can be understood with a number of samples that is sublinear in the domain size, and will lead to an understanding of the aspects of algorithm design that are specific to these constraints. The questions that will be considered range from considering the complexity of testing previously unstudied properties, finding general techniques which apply to classes of distribution testing problems, investigating new models of distribution testing, understanding structural aspects of the testing problems that can be solved in sublinear time, and further understanding the relationship between the computational complexity and sample complexity.The broader impact of this proposal includes educational and workforce development components. The educational component of this proposal involves designing course material on algorithms for testing distributions that would be appropriate for students at all levels. Enough material has been collected to develop a graduate course that highlights the body of techniques that have emerged in this field. Some of the recent advances are a perfect fit for conveying fundamental ideas behind randomized algorithms to undergraduates. The PI has been awarded two teaching awards for her efforts at undergraduate education. The PI will continue her efforts as an advisor and mentor to undergraduates, graduate students and postdoctoral researchers, which in the past have included several women who have gone on to successful research careers. The PI is currently co-organizing a Dagstuhl workshop on Sublinear Algorithms. A priority has been placed on inviting and supporting graduate students interested in working in the area. Finally, the ideas will also be disseminated through the use of the web, seminar, workshop and conference presentations, journal articles and survey articles aimed at a wider audience.