Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
复制标题
DOI：
--
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Antonio Blanca;Zongchen Chen;Daniel Stefankovic;Eric Vigoda
中科院分区：
文献类型：
--
作者：
Antonio Blanca;Zongchen Chen;Daniel Stefankovic;Eric Vigoda
研究了高维分布的恒等式检验问题。给定一个显式分布$\mu$、一个$\vareps>0$作为输入，并访问一个隐藏分布$\pi$的采样oracle，身份测试的目标是区分两个分布$\mu$和$\pi$是相同的还是至少相距$\vareps $-远。当只能访问隐藏分布$\pi$中的完整样本时，众所周知，身份测试可能需要指数级多的样本（在维度上），因此之前的工作已经研究了通过额外访问各种“条件”的身份测试采样预言机。我们认为一个显着较弱的条件抽样甲骨文，我们称之为$\mathsf{坐标\ Oracle}$，并提供了一个计算和统计特性的身份测试问题，在这个新的模型。我们证明，如果一个分析性质称为近似张量熵持有$n$维可见分布$\mu$，那么有一个有效的身份测试算法的任何隐藏的分布$\pi$使用$\tilde{O}（n/\vareptide）$查询的$\mathsf{坐标\ Oracle}$。熵的近似张量化是一个相关的条件，因为最近的工作已经为一大类高维分布建立了它。我们还证明了一个计算相变：一个良好的研究类的$n$维分布，特别是稀疏反铁磁伊辛模型在$\{+1，-1\}^n$，我们表明，在政权的熵近似张量化失败，有没有有效的身份测试算法，除非$\mathsf{RP}=\mathsf{NP}$。我们补充我们的结果与匹配的$\Omega（n/\varepaly）$统计下限的样本复杂性的身份测试中的$\mathsf{Coordinate\ Oracle}$模型。
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution $\mu$, an $\varepsilon>0$, and access to sampling oracle(s) for a hidden distribution $\pi$, the goal in identity testing is to distinguish whether the two distributions $\mu$ and $\pi$ are identical or are at least $\varepsilon$-far apart. When there is only access to full samples from the hidden distribution $\pi$, it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various"conditional"sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the $\mathsf{Coordinate\ Oracle}$, and provide a computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for an $n$-dimensional visible distribution $\mu$, then there is an efficient identity testing algorithm for any hidden distribution $\pi$ using $\tilde{O}(n/\varepsilon)$ queries to the $\mathsf{Coordinate\ Oracle}$. Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: for a well-studied class of $n$-dimensional distributions, specifically sparse antiferromagnetic Ising models over $\{+1,-1\}^n$, we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless $\mathsf{RP}=\mathsf{NP}$. We complement our results with a matching $\Omega(n/\varepsilon)$ statistical lower bound for the sample complexity of identity testing in the $\mathsf{Coordinate\ Oracle}$ model.