Near-optimal-sample estimators for spherical Gaussian mixtures

Abstract

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\left(\frac{d{\log }^{2}d}{{\epsilon }^4}\right)$ 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\left(\frac{d}{{\epsilon }^2}\right)$ 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}\left(\frac{k\log \frac{k}{\epsilon }}{{\epsilon }^2}\right)$ samples and runs in time $\tilde{\mathcal{O}}\left((\frac{k}{\epsilon }{)}^{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.

References in corpus (3)

• Polynomial Learning of Distribution Families
• Learning mixtures of structured distributions over discrete domains
• The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures

Cited by in corpus (9)

• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Differentially-Private Clustering of Easy Instances
• Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
• Sparse Solutions to Nonnegative Linear Systems and Applications
• Robust Model Selection and Nearly-Proper Learning for GMMs
• On the Sample Complexity of Learning Sum-Product Networks