Statistical and machine-learning algorithms are frequently applied to high-dimensional data. In many of these applications data is scarce, and often much more costly than computation time. We provide the first sample-efficient polynomial-time estimator for high-dimensional spherical Gaussian mixtures. For mixtures of any $k$ $d$-dimensional spherical Gaussians, we derive an intuitive spectral-estimator that uses $\mathcal{ O}_k\bigl(\frac{ d\log^2d}{ \epsilon^4}\bigr)$ samples and runs in time $\mathcal{ O}_{ k,\epsilon}(d^3\log^5 d)$, both significantly lower than previously known. The constant factor $\mathcal{ O}_k$ is polynomial for sample complexity and is exponential for the time complexity, again much smaller than what was previously known. We also show that $\Omega_k\bigl(\frac{ d}{ \epsilon^2}\bigr)$ samples are needed for any algorithm. Hence the sample complexity is near-optimal in the number of dimensions. We also derive a simple estimator for one-dimensional mixtures that uses $\mathcal{ O}\bigl(\frac{ k \log \frac{ k}{ \epsilon} }{ \epsilon^2} \bigr)$ samples and runs in time $\widetilde{ \mathcal{ O}}\left(\bigl(\frac{ k}{ \epsilon}\bigr)^{ 3k+1}\right)$. Our other technical contributions include a faster algorithm for choosing a density estimate from a set of distributions, that minimizes the $\ell_1$ distance to an unknown underlying distribution.
Categories: cs.LG cs.DS cs.IT math.IT stat.ML