The Complexity of Testing Distributions

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

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.