Sample-Based High-Dimensional Convexity Testing.
X. Chen and and R. Servedio and T. Sun and
21st International Workshop on Randomness and Computation (RANDOM), 2017, pp. 37:1--37:20.

Abstract:

In the problem of \emph{high-dimensional convexity testing}, there is an unknown set $\targetset \subseteq \R^n$ which is promised to be either convex or $\eps$-far from every convex body with respect to the standard multivariate normal distribution $\normal^n$. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set $\targetset$ as possible.

In this work we consider \emph{sample-based} testing algorithms, in which the testing algorithm only has access to labeled samples $(\bx,\targetset(\bx))$ where each $\bx$ is independently drawn from $\normal^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 $\eps$, 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})}$.