Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation
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.
The paper studies the problem of identifying Gaussians 
      in a mixture in high dimensions when the separation between the Gaussians 
      is small. The assumption is that the Gaussians are separated along few 
      dimensions and hence by identifying these dimensions, that is, feature 
      selection, the curse of dimensionality can be bitten and the Gaussians can 
      be found. Clustering in high dimension is an open problem that 
      well deserve a study. The theoretical approach taken by the authors is 
      good step in the path towards better understanding the problem. However, I 
      have two reservations about this work. In Line 36, the authors say “there 
      appears to be no theoretical results justifying the advantage of variable 
      selection in high dimension setting”. As far as I understand, K. Chaudhuri 
      and S. Rao, ("Learning Mixtures of Product Distributions using 
      Correlations and Independence", In Proc. of Conf. on Learning Theory, 
      2008) tried to address similar problem of learning mixture models in high 
      dimension under the assumption that the separation between the components 
      is in a small, axis aligned space. While the results there are different 
      then the results here, I was missing a comparison between the results. 
      In their response to the original review, the authors have 
      addressed the differences between the current work and the work of 
      Chaudhuri and Rao. I am confident that the work here contains novel 
      results that should be published. However, I think that more careful 
      thought needs to be given to presenting the novelty and contrasting it 
      with the state of the art. The main message of the authors in their 
      response is “these methods [the methods of Chaudhuri and Rao] do not 
      explicitly provide variable selection guarantees, i.e. the methods are not 
      guaranteed to correctly identify the relevant features.” However, in the 
      paper, the authors present as the main result “In this paper, we provide 
      precise information theoretic bounds on the clustering accuracy and sample 
      complexity of learning a mixture of two isotropic Gaussians”. Therefore, 
      the main goal is the accuracy of the separation as opposed to 
      identification of relevant features. Therefore, I find the main 
      contribution of this paper to be vague. Since I believe that this paper 
      contains significant results, I think that the authors should reconsider 
      the presentation to make a clear statement about the objectives and the 
      contribution. I also had some problems following the proof of 
      Theorem 2 but the authors clarified it in their response. 
      Comments: 1. Theorem 4: The term \frac{d-1}{4}+1 could be 
      simplified to \frac{d+3}{4} 2. Lemma 1: I believe you could improve 
      the bound on M to $2^{7m/16}$ by a simple covering argument: $\Omega$ is 
      of size $2^m$. Every $\omega_i$ “covers” a ball of size $m/8$. A ball of 
      size $m/8$ contains $\sum_{i\leq m/8} \choose{m}{i}$ points from $\Omega$ 
      which can be bounded (Sauer’s Lemma) by (8e)^{m/8} which is bounded by 
      2^{9m/16}. Therefore, if we choose $M=2^{7m/16}$ we have that M balls of 
      radius $m/8$ do not cover $\Omega$ and hence there is a $m/8$ packing 
      (which is what you are looking for) of size $M$. (This is not a major 
      issue and you may decide to ignore it in favor of the simplicity of the 
      statement). 3. Lemma 2: The bound on M here is stated with 
      logarithms while the bound in Lemma 1 does not use logarithms which makes 
      it harder to follow. 4. Proposition 3: what are $\phi$ and $\Phi$? 
      5. Proof of Theorem 2, line 275: What is $\theta_\nu$, where is it 
      introduced? 6. Proof of Theorem 2, line 279: It is not clear why on 
      the r.h.s. there is $\frac{\sqrt{d-1}\espilom}{\lambda}$. Using the term 
      for the cosine of \beta and since $sin(\beta) = \sqrt{1-cos^2(\beta)$ I 
      get that $sin(\beta) = \frac{2\rho\epsilon^2}{\lambda^2} \geq 
      \frac{2(d-1)\epsilon^2}{\lambda^2}$ and this $tan{\beta} \leq 
      \frac{4(d-1)\epsilon^2}{\lambda^2}$ 8. Line 466: you use full 
      names for all references but Tsybakov’s paper.