Collision-based Testers are Optimal for Uniformity and Closeness
Collision-based Testers are Optimal for Uniformity and Closeness
复制标题
基于碰撞的测试仪最适合均匀性和紧密度
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Eric Price
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Themis Gouleakis;John Peebles;Eric Price
我们研究了（i）离散分布的均匀性测试的基本问题，以及（ii）具有有限的$ ell_2 $ norm之间的两个离散分布之间的紧密测试。这些问题已在分布测试中进行了广泛的研究，样品最佳估计量已知〜Cite {Paninski：08，CDVV14，VV14，DKN：15}。
在这项工作中，我们表明针对这些问题提出的原始基于碰撞的测试仪〜Cite {grdist：00，bfr+：00}是最佳的样本，最多可达到恒定因素。先前的分析表明，这些测试仪的样本复杂度上限是最佳的，它们是域尺寸$ n $的函数，但在误差参数$ epsilon $中，多项式因子次优。我们的主要贡献是一项新的严格分析，确定这些基于碰撞的测试人员在理论上是信息的最佳信息，最不变的因素，无论是在$ n $的依赖和依赖$ epsilon $的依赖中。
We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded $ell_2$-norm. These problems have been extensively studied in distribution testing and sample-optimal estimators are known for them~cite{Paninski:08, CDVV14, VV14, DKN:15}.
In this work, we show that the original collision-based testers proposed for these problems ~cite{GRdist:00, BFR+:00} are sample-optimal, up to constant factors. Previous analyses showed sample complexity upper bounds for these testers that are optimal as a function of the domain size $n$, but suboptimal by polynomial factors in the error parameter $epsilon$. Our main contribution is a new tight analysis establishing that these collision-based testers are information-theoretically optimal, up to constant factors, both in the dependence on $n$ and in the dependence on $epsilon$.