Timezone: »

 
Poster
Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation
Martin Azizyan · Aarti Singh · Larry Wasserman

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »

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.

[ PDF] 

Author Information

Martin Azizyan (CMU)
Aarti Singh (CMU)
Larry Wasserman (CMU)

More from the Same Authors