Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation
This provides a theoretical foundation for methods combining feature selection and clustering in high-dimensional data analysis.
The paper establishes precise minimax bounds for clustering accuracy and sample complexity in high-dimensional Gaussian mixtures with sparse mean separation, showing that sample complexity depends only on the number of relevant dimensions and mean separation, achievable via a computationally efficient method.
While several papers have investigated computationally and statistically efficient methods for learning Gaussian mixtures, precise minimax bounds for their statistical performance as well as fundamental limits in high-dimensional settings are not well-understood. In this paper, we provide precise information theoretic bounds on the clustering accuracy and sample complexity of learning a mixture of two isotropic Gaussians in high dimensions under small mean separation. If there is a sparse subset of relevant dimensions that determine the mean separation, then the sample complexity only depends on the number of relevant dimensions and mean separation, and can be achieved by a simple computationally efficient procedure. Our results provide the first step of a theoretical basis for recent methods that combine feature selection and clustering.