# Sample-Efficient Learning of Mixtures

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2017.

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

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [PMODE: Theoretically Grounded and Modular Mixture Modeling](https://mlsanity.com/paper/2508.21396/) (2025)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)

## Abstract (arXiv)

We consider PAC learning of probability distributions (a.k.a. density estimation), where we are given an i.i.d. sample generated from an unknown target distribution, and want to output a distribution that is close to the target in total variation distance. Let mathcal F be an arbitrary class of probability distributions, and let Fk denote the class of k-mixtures of elements of mathcal F. Assuming the existence of a method for learning mathcal F with sample complexity mF(ε), we provide a method for learning mathcal Fk with sample complexity O(klog k · mmathcal F(ε) /ε2). Our mixture learning algorithm has the property that, if the mathcal F-learner is proper/agnostic, then the mathcal Fk-learner would be proper/agnostic as well. This general result enables us to improve the best known sample complexity upper bounds for a variety of important mixture classes. First, we show that the class of mixtures of k axis-aligned Gaussians in ℝd is PAC-learnable in the agnostic setting with widetildeO(kd/ε ^ 4) samples, which is tight in k and d up to logarithmic factors. Second, we show that the class of mixtures of k Gaussians in ℝd is PAC-learnable in the agnostic setting with sample complexity widetildeO(kd2/ε ^ 4), which improves the previous known bounds of widetildeO(k3d2/ε ^ 4) and widetildeO(k4d4/ε ^ 2) in its dependence on k and d. Finally, we show that the class of mixtures of k log-concave distributions over ℝd is PAC-learnable using widetildeO(d(d+5)/2ε-(d+9)/2k) samples.