Near-Optimal-Sample Estimators for Spherical Gaussian Mixtures
Many important distributions are high dimensional, and often they can be modeled as Gaussian mixtures. We derive the first sample-efficient polynomial-time estimator for high-dimensional spherical Gaussian mixtures. Based on intuitive spectral reasoning, it approximates mixtures of k spherical Gaussians in d-dimensions to within 1 distance using O(dk
computation time. Conversely, we show that any estimator requires Ω dk 2 samples, hence the algorithm's sample complexity is nearly optimal in the dimension. The implied time-complexity factor O k, is exponential in k, but much smaller than previously known. We also construct a simple estimator for one-dimensional Gaussian mixtures that usesÕ(k 2 ) samples andÕ((k ) 3k+1 ) computation time.
This paper considers PAC learning of mixture spherical Gaussian distributions. Via exploiting the spherical structure of the data (in particular, the assumption that all covariance matrices of all components are diagonal), the authors are able to derive efficient algorithms to estimate the means and the standard deviations. The mixtures can then be derived using a modified Scheffe's method, This paper is, in general, very well written. The intuition, the proposed method, and the theoretical justifications are all stated clearly and reader-friendly. I can follow the main contents very easily. The related literature seems to be well cited (I am not an expert in this area, so not very confirmative). The results look novel, correct, and important. Overall, I enjoy reading it a lot. However, there are still some issues need to be addressed:(1) It looks like that the whole paper is focused on the setting that k, the number of components, is known. It is a little bit surprising that the authors did not discuss the situation when k is unknown. Is it trivial to estimate it? At least some heuristics are preferred. (2) By assuming sphericity on the components, The results look like quite restrictive in real applications. Some discussions on retionality of sphericity assumption, or a generalization to more general cases, are desired. (3) Technically, the bound on delta, provided in line 288, is a little bit weird. For example, if d is fixed, this delta can be as large as 1/3. Minor comments:(1) Line 47-48, rephrase the sentence.(2) line 247, S looks more like a covariance-type matrix.(3) line 270, "necessary" -> "necessarily"?