Property Testing of Joint Distributions using Conditional Samples
Property Testing of Joint Distributions using Conditional Samples
复制标题
使用条件样本的联合分布的属性测试
DOI：
10.1145/3241377
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sourav Chakraborty
中科院分区：
文献类型：
--
作者：
Rishiraj Bhattacharyya;Sourav Chakraborty
在这篇文章中，我们考虑了条件抽样框架下的联合分布的性质的测试问题。在标准抽样模型中，联合分布性质检验的样本复杂度在维数上是指数级的，导致实际应用中的算法效率低下。虽然最近的结果实现了有效的算法，产品分布的样本复杂性显着较小，没有有效的算法时，边际是不独立的。
在这篇文章中，我们初步研究了多维背景下的条件抽样。我们提出了一个子立方体条件抽样模型，测试人员可以条件（自适应）选择的子立方体的域。由于其简单性，该模型在许多实际应用中是潜在可实现的，特别是当分布是针对某个集合的联合分布时。
我们提出了算法的各种基本性质的分布在子立方体条件模型，并证明了样本的复杂性是多项式的维数n（而不是指数在传统的模型）。我们提出了一个算法测试同一性的一个已知的分布使用的n（n2）-子立方体条件样本，一个算法测试两个未知的分布之间的同一性使用的n（n5）-子立方体条件样本和一个算法测试同一性的产品分布使用的n（n5）-子立方体条件样本。
我们技术的中心概念涉及一个优雅的链式规则，可以使用概率论的基本技术来证明，但它足够强大，可以避免维度灾难。
In this article, we consider the problem of testing properties of joint distributions under the Conditional Sampling framework. In the standard sampling model, sample complexity of testing properties of joint distributions are exponential in the dimension, resulting in inefficient algorithms for practical use. While recent results achieve efficient algorithms for product distributions with significantly smaller sample complexity, no efficient algorithm is expected when the marginals are not independent.
In this article, we initialize the study of conditional sampling in the multidimensional setting. We propose a subcube conditional sampling model where the tester can condition on a (adaptively) chosen subcube of the domain. Due to its simplicity, this model is potentially implementable in many practical applications, particularly when the distribution is a joint distribution over Σn for some set Σ.
We present algorithms for various fundamental properties of distributions in the subcube-conditioning model and prove that the sample complexity is polynomial in the dimension n (and not exponential as in the traditional model). We present an algorithm for testing identity to a known distribution using Õ(n2)-subcube-conditional samples, an algorithm for testing identity between two unknown distributions using Õ(n5)-subcube-conditional samples and an algorithm for testing identity to a product distribution using Õ(n5)-subcube-conditional samples.
The central concept of our technique involves an elegant chain rule, which can be proved using basic techniques of probability theory, yet it is powerful enough to avoid the curse of dimensionality.