# Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 60 references that are in the map.
- First posted on arXiv 26 Mar 2025.

## Builds on (most cited first, 16 of 16)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences](https://mlsanity.com/paper/1609.00978/) (2016)
- [Tight bounds for learning a mixture of two gaussians](https://mlsanity.com/paper/1404.4997/) (2014)
- [Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(√n) iterations](https://mlsanity.com/paper/1908.10935/) (2019)
- [On the nonparametric maximum likelihood estimator for Gaussian location mixture densities with application to Gaussian denoising](https://mlsanity.com/paper/1712.02009/) (2017)
- [Self-regularizing Property of Nonparametric Maximum Likelihood Estimator in Mixture Models](https://mlsanity.com/paper/2008.08244/) (2020)
- [Optimal estimation of high-dimensional location Gaussian mixtures](https://mlsanity.com/paper/2002.05818/) (2020)
- [Robust Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2007.05912/) (2020)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian Mixtures](https://mlsanity.com/paper/2103.15653/) (2021)
- [A fast algorithm for maximum likelihood estimation of mixture proportions using sequential quadratic programming](https://mlsanity.com/paper/1806.01412/) (2018)
- [A Mean Field Approach to Empirical Bayes Estimation in High-dimensional Linear Regression](https://mlsanity.com/paper/2309.16843/) (2023)
- [Gradient flows for empirical Bayes in high-dimensional linear models](https://mlsanity.com/paper/2312.12708/) (2023)
- [Nonparametric Finite Mixture Models with Possible Shape Constraints: A Cubic Newton Approach](https://mlsanity.com/paper/2107.08535/) (2021)

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

- [DDPM Score Matching and Distribution Learning](https://mlsanity.com/paper/2504.05161/) (2025)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures](https://mlsanity.com/paper/2610.01088/) (2026)

## Abstract (arXiv)

We study the nonparametric maximum likelihood estimator widehatπ for Gaussian location mixtures in one dimension. It has been known since (Lindsay, 1983) that given an n-point dataset, this estimator always returns a mixture with at most n components, and more recently (Wu-Polyanskiy, 2020) gave a sharp O(log n) bound for subgaussian data. In this work we study computational aspects of widehatπ. We provide an algorithm which for small enough varepsilon>0 computes an varepsilon-approximation of widehatπ in Wasserstein distance in time K+Cnk2loglog(1/varepsilon). Here K is data-dependent but independent of varepsilon, while C is an absolute constant and k=|supp(widehatπ)|≤ n is the number of atoms in widehatπ. We also certifiably compute the exact value of |supp(widehatπ)| in finite time. These guarantees hold almost surely whenever the dataset (x1,dots,xn)∈ [-cn1/4,cn1/4] consists of independent points from a probability distribution with a density (relative to Lebesgue measure). We also show the distribution of widehatπ conditioned to be k-atomic admits a density on the associated 2k-1 dimensional parameter space for all k≤ √n/3, and almost sure locally linear convergence of the EM algorithm. One key tool is a classical Fourier analytic estimate for non-degenerate curves.