论文标题
高维身份测试与坐标条件采样的复杂性
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
论文作者
论文摘要
我们研究高维分布的身份测试问题。作为输入，明显的分配$μ$，$ \ varepsilon> 0 $，以及用于隐藏分布$π$的采样甲骨文的访问，身份测试的目标是区分两个分布$μ$和$π$是相同的还是至少是$ \ varepsilon $ -far $ farepsilon $ -far。当仅从隐藏分布$π$中访问完整样本时，众所周知，身份测试可能需要许多样本（在维度中），因此先前的工作已经研究了身份测试，并额外访问了各种“条件”采样隔离器。我们考虑了一个有条件的条件采样甲骨文，我们称之为$ \ mathsf {coortion \ oracle} $，并在此新模型中提供了身份测试问题的计算和统计表征。 We prove that if an analytic property known as approximate tensorization of entropy holds for an $n$-dimensional visible distribution $μ$, then there is an efficient identity testing algorithm for any hidden distribution $π$ using $\tilde{O}(n/\varepsilon)$ queries to the $\mathsf{Coordinate\ Oracle}$.熵的近似张力是一种相关条件，因为最近的工作已经为大量的高维分布建立了它。我们还证明了计算相过渡：对于$ n $维分布的一类，特别是稀疏的反铁磁性模型$ \ {+{+{+1，-1，-1 \}^n $，我们表明，在该政权中，除非有高效的识别量，否则均无高度的识别量， $ \ mathsf {rp} = \ mathsf {np} $。我们通过匹配的$ω（N/\ Varepsilon）$统计下限为$ \ Mathsf {coortion \ oracle} $模型中的身份测试的样本复杂度提供了补充。
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution $μ$, an $\varepsilon>0$, and access to sampling oracle(s) for a hidden distribution $π$, the goal in identity testing is to distinguish whether the two distributions $μ$ and $π$ are identical or are at least $\varepsilon$-far apart. When there is only access to full samples from the hidden distribution $π$, 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 $μ$, then there is an efficient identity testing algorithm for any hidden distribution $π$ 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 $Ω(n/\varepsilon)$ statistical lower bound for the sample complexity of identity testing in the $\mathsf{Coordinate\ Oracle}$ model.
