论文标题
测试产品分布：仔细观察
Testing Product Distributions: A Closer Look
论文作者
论文摘要
我们研究了$ n $维产品分布的身份和紧密测试的问题。 Canonne，Diakonikolas，Kane和Stewart（Colt 2017）以及Daskalakis and Pan（Colt 2017）的先前作品已经建立了对二进制字母的不耐受性测试的紧密样本复杂性界限：给定两个产品分布$ P $和$ Q $在bnopher的情况下，区分bphep $ p = q $ p = q q = q q = q q = q q = q q = q q = q q = q q = q q = q Q $ $ d _ {\ mathrm {tv}}（p，q）>ε$。我们以这项先前的工作为基础，以更全面地绘制产品分布测试的复杂性，通过研究有关几种自然距离测量和任意字母的耐受性测试。我们的研究对耐受性测试的样本复杂性如何随乘积分布的距离度量而变化，从而有很好的了解。此外，我们还将产品分布的上限之一扩展到有限的贝叶斯网。
We study the problems of identity and closeness testing of $n$-dimensional product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions $P$ and $Q$ over a binary alphabet, distinguish between the cases $P = Q$ and $d_{\mathrm{TV}}(P, Q) > ε$. We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.
