Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Abstract

We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Given $\tilde{O}(1/{\epsilon }^2)$ samples from an unknown mixture, our algorithm outputs a mixture that is $\epsilon$-close in total variation distance, in time $\tilde{O}(1/{\epsilon }^5)$. Our sample complexity is optimal up to logarithmic factors, and significantly improves upon both Kalai et al., whose algorithm has a prohibitive dependence on $1/\epsilon$, and Feldman et al., whose algorithm requires bounds on the mixture parameters and depends pseudo-polynomially in these parameters. One of our main contributions is an improved and generalized algorithm for selecting a good candidate distribution from among competing hypotheses. Namely, given a collection of $N$ hypotheses containing at least one candidate that is $\epsilon$-close to an unknown distribution, our algorithm outputs a candidate which is $O(\epsilon )$-close to the distribution. The algorithm requires $O(\log N/{\epsilon }^2)$ samples from the unknown distribution and $O(N\log N/{\epsilon }^2)$ time, which improves previous such results (such as the Scheffé estimator) from a quadratic dependence of the running time on $N$ to quasilinear. Given the wide use of such results for the purpose of hypothesis selection, our improved algorithm implies immediate improvements to any such use.

31 pages, to appear in COLT 2014

References in corpus (2)

• Polynomial Learning of Distribution Families
• Learning mixtures of structured distributions over discrete domains

Cited by in corpus (20)

• Being Robust (in High Dimensions) Can Be Practical
• Private Mean Estimation of Heavy-Tailed Distributions
• Ten Steps of EM Suffice for Mixtures of Two Gaussians
• A Size-Free CLT for Poisson Multinomials and its Applications
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
• Robustly Learning any Clusterable Mixture of Gaussians
• Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
• Locally Private Hypothesis Selection
• Monotone probability distributions over the Boolean cube can be learned with sublinear samples
• A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• Differentially Private Assouad, Fano, and Le Cam
• Robust quantum minimum finding with an application to hypothesis selection
• Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
• Sparse Solutions to Nonnegative Linear Systems and Applications
• Robust hypothesis testing and distribution estimation in Hellinger distance
• Robust Model Selection and Nearly-Proper Learning for GMMs
• Splintering with distributions: A stochastic decoy scheme for private computation
• On the Sample Complexity of Learning Sum-Product Networks