# Near-optimal-sample estimators for spherical Gaussian mixtures

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2014.

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

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation](https://mlsanity.com/paper/2307.01646/) (2023)
- [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)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (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)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [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)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [On the Role of Channel Capacity in Learning Gaussian Mixture Models](https://mlsanity.com/paper/2202.07707/) (2022)
- [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)
- [Multimodal Scientific Learning Beyond Diffusions and Flows](https://mlsanity.com/paper/2602.00960/) (2026)
- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)
- [On Learning Parallel Pancakes with Mostly Uniform Weights](https://mlsanity.com/paper/2504.15251/) (2025)
- [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)

## Abstract (arXiv)

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 Okbigl(fracdlog2dε4bigr) samples and runs in time Ok,ε(d3log5 d), both significantly lower than previously known. The constant factor Ok is polynomial for sample complexity and is exponential for the time complexity, again much smaller than what was previously known. We also show that Omegakbigl(fracdε2bigr) 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 Obigl(frack log frackε ε2 bigr) samples and runs in time widetildeOleft(bigl(frackεbigr)3k+1right). Our other technical contributions include a faster algorithm for choosing a density estimate from a set of distributions, that minimizes the ℓ1 distance to an unknown underlying distribution.