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

arXiv: https://arxiv.org/abs/1312.1054 · HTML: https://mlsanity.com/paper/1312.1054/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2013.

## Built on by (most cited first, 20 of 20)

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective](https://mlsanity.com/paper/2405.16418/) (2024)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [A sampling-based approach for efficient clustering in large datasets](https://mlsanity.com/paper/2112.14793/) (2021)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures](https://mlsanity.com/paper/2203.15150/) (2022)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Learnability of Parameter-Bounded Bayes Nets](https://mlsanity.com/paper/2407.00927/) (2024)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Given tildeO(1/varepsilon2) samples from an unknown mixture, our algorithm outputs a mixture that is varepsilon-close in total variation distance, in time tildeO(1/varepsilon5). 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/varepsilon, 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 varepsilon-close to an unknown distribution, our algorithm outputs a candidate which is O(varepsilon)-close to the distribution. The algorithm requires O(logN/varepsilon2) samples from the unknown distribution and O(N log N/varepsilon2) time, which improves previous such results (such as the Scheff'e 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.