标题： 测试凸截断 显示英文标题

标题： Testing Convex Truncation

摘要： 我们研究了测试正态分布的$n$维数据是否被截断的基本统计问题，即通过仅保留位于某个未知截断集$S \subseteq \mathbb{R}^n$中的点来改变数据。作为我们的主要算法结果， (1) 我们给出一个计算高效的$O(n)$样本算法，该算法可以区分标准正态分布$N(0,I_n)$与在某个未知且任意的凸集$S$条件下的分布$N(0,I_n)$。 (2) 我们给出一种不同的计算高效的$O(n)$-样本算法，该算法可以在未知且任意的对称凸集混合条件下区分$N(0,I_n)$与$N(0,I_n)$。 这些结果与在正态分布下学习或测试凸体或学习凸截断正态分布的已知结果形成鲜明对比，其中最先进的算法本质上需要$n^{\sqrt{n}}$个样本。 一个简单的论证表明，没有有限数量的样本足以区分$N(0,I_n)$与未知且任意的一般（不一定对称）凸集的混合，因此无法对上述结果(1)和(2)进行共同的推广。 我们还证明，任何算法（无论计算上是否高效）在未知对称凸集的条件下，若能区分$N(0,I_n)$和$N(0,I_n)$，则必须使用$\Omega(n)$个样本。 这表明我们每个算法的样本复杂度至多相差一个常数因子是最佳的。 显示英文摘要

摘要： We study the basic statistical problem of testing whether normally distributed $n$-dimensional data has been truncated, i.e. altered by only retaining points that lie in some unknown truncation set $S \subseteq \mathbb{R}^n$. As our main algorithmic results, (1) We give a computationally efficient $O(n)$-sample algorithm that can distinguish the standard normal distribution $N(0,I_n)$ from $N(0,I_n)$ conditioned on an unknown and arbitrary convex set $S$. (2) We give a different computationally efficient $O(n)$-sample algorithm that can distinguish $N(0,I_n)$ from $N(0,I_n)$ conditioned on an unknown and arbitrary mixture of symmetric convex sets. These results stand in sharp contrast with known results for learning or testing convex bodies with respect to the normal distribution or learning convex-truncated normal distributions, where state-of-the-art algorithms require essentially $n^{\sqrt{n}}$ samples. An easy argument shows that no finite number of samples suffices to distinguish $N(0,I_n)$ from an unknown and arbitrary mixture of general (not necessarily symmetric) convex sets, so no common generalization of results (1) and (2) above is possible. We also prove that any algorithm (computationally efficient or otherwise) that can distinguish $N(0,I_n)$ from $N(0,I_n)$ conditioned on an unknown symmetric convex set must use $\Omega(n)$ samples. This shows that the sample complexity of each of our algorithms is optimal up to a constant factor.