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})}$.
Categories: cs.CC