Sample-Based High-Dimensional Convexity Testing
Sample-Based High-Dimensional Convexity Testing
复制标题
基于样本的高维凸性测试
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Timothy Sun
中科院分区：
文献类型：
--
作者：
Xi Chen;Adam Freilich;R. Servedio;Timothy Sun
在高维凸性测试问题中，存在一个未知集 $S \subseteq \mathbb{R}^n$，它被承诺为凸集或 $\varepsilon$ - 相对于标准多元正态分布 $\mathcal{N}(0, 1)^n$ 远离每个凸体。测试算法的工作就是区分这两种情况，同时对集合 $S$ 进行尽可能少的检查。
在这项工作中，我们考虑基于样本的测试算法，其中测试算法只能访问标记样本 $(\boldsymbol{x},S(\boldsymbol{x}))$，其中每个 $\boldsymbol{x}$ 独立地从 $\mathcal{N}(0, 1)^n$ 中提取。我们为该框架中的单侧和两侧凸性测试算法给出了几乎匹配的样本复杂性上限和下限。对于常数 $\varepsilon$，我们的结果表明，单侧凸性测试的样本复杂度为 $2^{\tilde{\Theta}(n)}$ 个样本，而两侧凸性测试的样本复杂度为 $2^{\tilde{\Theta}(\sqrt{n})}$。
In the problem of high-dimensional convexity testing, there is an unknown set $S \subseteq \mathbb{R}^n$ which is promised to be either convex or $\varepsilon$-far from every convex body with respect to the standard multivariate normal distribution $\mathcal{N}(0, 1)^n$. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set $S$ as possible.
In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples $(\boldsymbol{x},S(\boldsymbol{x}))$ where each $\boldsymbol{x}$ is independently drawn from $\mathcal{N}(0, 1)^n$. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant $\varepsilon$, our results show that the sample complexity of one-sided convexity testing is $2^{\tilde{\Theta}(n)}$ samples, while for two-sided convexity testing it is $2^{\tilde{\Theta}(\sqrt{n})}$.