Testing Identity of Multidimensional Histograms
Testing Identity of Multidimensional Histograms
复制标题
测试多维直方图的同一性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
John Peebles
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;John Peebles
我们研究多维直方图分布的同一性检验问题。一个分布$p：D \rightarrow \mathbb{R}_+$，其中$D \subseteq \mathbb{R}^d$，被称为$k$-直方图，如果存在一个域划分为$k$轴对齐的矩形，使得$p$在每个这样的矩形内是恒定的。直方图是最基本的非参数分布族之一，在计算机科学和统计学中得到了广泛的研究。我们给这个问题的第一个身份测试{\em子学习}样本复杂性在任何固定的维度和一个接近匹配的样本复杂性下界。
更详细地说，让$q$是一个未知的$d$维$k$-直方图分布在固定的维度$d$，和$p$是一个明确给定的$d$维$k$-直方图。我们希望正确区分p = q和p-1 geq之间的差别，其概率至少为2/3。我们为这个假设检验问题设计了一个算法，其样本复杂度为O（（\sqrt{k}/\epsilon ^2）2^{d/2} \log^{2.5 d}（k/\epsilon））$，在样本多项式时间内运行。我们的算法对模型误指定是鲁棒的，即，成功，即使$q$仅承诺接近$k$直方图。此外，对于$k = 2^{\Omega（d）}$，我们证明了当$d\geq 2$时，样本复杂度的下界为$（\sqrt{k}/\epsilon^2）\cdot \Omega（\log（k）/d）^{d-1}$。也就是说，对于任何固定的维数d，我们的上界和下界几乎匹配。在我们的工作之前，$d=1$情况下的样本复杂度是很好理解的，但没有已知的子学习样本复杂度的算法，即使是$d=2$。我们的新的上限和下限有有趣的概念意义上的学习和测试之间的关系，在这种情况下。
We investigate the problem of identity testing for multidimensional histogram distributions. A distribution $p: D \rightarrow \mathbb{R}_+$, where $D \subseteq \mathbb{R}^d$, is called a $k$-histogram if there exists a partition of the domain into $k$ axis-aligned rectangles such that $p$ is constant within each such rectangle. Histograms are one of the most fundamental nonparametric families of distributions and have been extensively studied in computer science and statistics. We give the first identity tester for this problem with {\em sub-learning} sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound.
In more detail, let $q$ be an unknown $d$-dimensional $k$-histogram distribution in fixed dimension $d$, and $p$ be an explicitly given $d$-dimensional $k$-histogram. We want to correctly distinguish, with probability at least $2/3$, between the case that $p = q$ versus $\|p-q\|_1 \geq \epsilon$. We design an algorithm for this hypothesis testing problem with sample complexity $O((\sqrt{k}/\epsilon^2) 2^{d/2} \log^{2.5 d}(k/\epsilon))$ that runs in sample-polynomial time. Our algorithm is robust to model misspecification, i.e., succeeds even if $q$ is only promised to be {\em close} to a $k$-histogram. Moreover, for $k = 2^{\Omega(d)}$, we show a sample complexity lower bound of $(\sqrt{k}/\epsilon^2) \cdot \Omega(\log(k)/d)^{d-1}$ when $d\geq 2$. That is, for any fixed dimension $d$, our upper and lower bounds are nearly matching. Prior to our work, the sample complexity of the $d=1$ case was well-understood, but no algorithm with sub-learning sample complexity was known, even for $d=2$. Our new upper and lower bounds have interesting conceptual implications regarding the relation between learning and testing in this setting.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
and Automata
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Peebles, John;Price, Eric
通讯作者：
Price, Eric
用于学习多维直方图的快速和样本近最优算法
DOI：
--
发表时间：
2018
期刊：
PMLR
影响因子：
--
作者：
Diakonikolas, Ilias;Li, Jerry;Schmidt, Ludwig
通讯作者：
Schmidt, Ludwig
广义均匀性测试的尖锐界限
DOI：
--
发表时间：
2018
期刊：
NeurIPS 2018
影响因子：
--
作者：
Diakonikolas, Ilias;Kane, Daniel M.;Stewart, Alistair
通讯作者：
Stewart, Alistair
DOI：
--
发表时间：
2016-06
期刊：
ArXiv
影响因子：
--
作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
通讯作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
DOI：
10.48550/arxiv.1706.05738
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Canonne C
通讯作者：
Canonne C