Optimal testing of discrete distributions with high probability
Optimal testing of discrete distributions with high probability
复制标题
高概率离散分布的最优测试
DOI：
10.1145/3406325.3450997
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Price, Eric
中科院分区：
文献类型：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Kane, Daniel M.;Peebles, John;Price, Eric
研究了离散分布的检验问题，重点研究了高概率分布的检验问题。具体地说，给定来自一个或多个离散分布的样本、性质P和参数0<；є，δ<；1，我们希望以至少1−δ的概率来区分这些分布是否满足є-Por-远离Pin的总变异距离。大多数以前的分布检验工作研究了常置信度情形(对应于δ=Ω(1))，并为一系列属性提供了样本最优检验。虽然人们总是可以通过黑盒放大来提高任何这样的测试器的置信度，但这种通用的Boosting方法通常会导致次最优的样本界。这里我们研究以下广泛的问题：对于给定的属性P，我们能否刻画测试的样本复杂性作为所有相关问题参数的函数，包括错误概率δ？在这项工作之前，一致性检验是唯一一项其样本复杂性在这种情况下被表征的统计任务。作为我们的主要结果，我们提供了封闭性和独立性检验的第一个算法，这些算法是作为所有相关参数的函数的恒定因素下的样本最优的。我们还给出了这些问题样本复杂性的匹配信息论下界。我们的技术自然会扩展到为相关问题提供最佳的测试人员。为了说明我们方法的通用性，我们给出了测试分布集合和不等长样本的封闭性的最优算法。
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a propertyP, and parameters 0< є, δ <1, we want to distinguishwith probability at least1−δ whether these distributions satisfyPor are є-far fromPin total variation distance. Most prior work in distribution testing studied the constant confidence case (corresponding to δ = Ω(1)), and provided sample-optimal testers for a range of properties. While one can always boost the confidence probability of any such tester by black-box amplification, this generic boosting method typically leads to sub-optimal sample bounds.Here we study the following broad question: For a given propertyP, can wecharacterizethe sample complexity of testingPas a function of all relevant problem parameters, including the error probability δ? Prior to this work, uniformity testing was the only statistical task whose sample complexity had been characterized in this setting. As our main results, we provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors, as a function of all relevant parameters. We also show matching information-theoretic lower bounds on the sample complexity of these problems. Our techniques naturally extend to give optimal testers for related problems. To illustrate the generality of our methods, we give optimal algorithms for testing collections of distributions and testing closeness with unequal sized samples.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
and Automata
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Peebles, John;Price, Eric
通讯作者：
Price, Eric
测试贝叶斯网络
影响因子：
2.5
作者：
C. Canonne;Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Alistair Stewart
贝叶斯网络的 Square Hellinger 子可加性及其在身份测试中的应用
DOI：
--
发表时间：
2016
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
C. Daskalakis;Qinxuan Pan
通讯作者：
Qinxuan Pan
用于测试结构化分布的接近度的最佳算法和下界
DOI：
10.1109/focs.2015.76
发表时间：
2015
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Vladimir Nikishkin
通讯作者：
Vladimir Nikishkin
测试多维直方图的同一性
DOI：
--
发表时间：
2018
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;John Peebles
通讯作者：
John Peebles