Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
This addresses a fundamental problem in distribution testing for high-dimensional data, with applications in statistics and machine learning, though it appears incremental as it builds on prior work on subcube conditioning.
The paper tackles the problem of testing uniformity of distributions on high-dimensional binary cubes, achieving a nearly-optimal algorithm with Õ(√n/ε²) queries to a subcube conditional sampling oracle, and also provides a nearly-optimal algorithm for mean testing with independent samples.
We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.