The Complexity of Testing Distributions

在各种各样的计算环境中，数据最自然地被视为来自分布，确定底层分布是否满足各种属性通常是至关重要的。这些属性的例子包括两个分布在统计距离上是近还是远，联合分布是否独立，以及分布是否具有高熵。对于大多数这样的属性，近似分布的标准统计技术导致使用在域大小上接近线性的多个样本的算法。直到最近，分布在大型域，线性样本的复杂性可能是令人生畏的，已经收到了令人惊讶的关注。然而，对这些问题的新兴趣来自许多方向，包括数据挖掘，物理学和机器学习在神经生物学中的应用。最近的研究结果表明，人们可以实现的结果是显着更有效的比标准技术的情况下，大domain.The智力的优点，这项研究将导致理解的样本，时间和空间的复杂性，需要确定各种自然属性的概率分布。拟议的研究将集中在确定哪些属性可以理解的一些样本是次线性域的大小，并将导致理解的算法设计的方面，是特定于这些约束。将被考虑的问题范围从考虑测试以前未研究的属性的复杂性，找到适用于分布测试问题的类的一般技术，调查分布测试的新模型，理解可以在次线性时间内解决的测试问题的结构方面，以及进一步理解计算复杂性和样本复杂性之间的关系。该提案的更广泛影响包括教育和劳动力发展组成部分。该提案的教育部分涉及设计适用于各级学生的测试分布算法的课程材料。已经收集了足够的材料来开发一个研究生课程，突出了这一领域出现的技术。最近的一些进展非常适合向本科生传达随机算法背后的基本思想。PI因其在本科教育方面的努力而获得两项教学奖。PI将继续她的努力，作为本科生，研究生和博士后研究人员的顾问和导师，在过去，其中包括几位已经成功从事研究工作的女性。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.