# On Efficient and Scalable Computation of the Nonparametric Maximum Likelihood Estimator in Mixture Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2022.

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

- [Learning Gaussian Mixtures Using the Wasserstein-Fisher-Rao Gradient Flow](https://mlsanity.com/paper/2301.01766/) (2023)
- [A New Perspective On Denoising Based On Optimal Transport](https://mlsanity.com/paper/2312.08135/) (2023)
- [When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation](https://mlsanity.com/paper/2605.05592/) (2026)
- [Model-free Estimation of Latent Structure via Multiscale Nonparametric Maximum Likelihood](https://mlsanity.com/paper/2410.22248/) (2024)
- [Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures](https://mlsanity.com/paper/2610.01088/) (2026)

## Abstract (arXiv)

In this paper we study the computation of the nonparametric maximum likelihood estimator (NPMLE) in multivariate mixture models. Our first approach discretizes this infinite dimensional convex optimization problem by fixing the support points of the NPMLE and optimizing over the mixture proportions. In this context we propose, leveraging the sparsity of the solution, an efficient and scalable semismooth Newton based augmented Lagrangian method (ALM). Our algorithm beats the state-of-the-art methods~citekoenker2017rebayes, kim2020fast and can handle n ≈ 106 data points with m ≈ 104 support points. Our second procedure, which combines the expectation-maximization (EM) algorithm with the ALM approach above, allows for joint optimization of both the support points and the probability weights. For both our algorithms we provide formal results on their (superlinear) convergence properties. The computed NPMLE can be immediately used for denoising the observations in the framework of empirical Bayes. We propose new denoising estimands in this context along with their consistent estimates. Extensive numerical experiments are conducted to illustrate the effectiveness of our methods. In particular, we employ our procedures to analyze two astronomy data sets: (i) Gaia-TGAS Catalog~citeanderson2018improving containing n ≈ 1.4 × 106 data points in two dimensions, and (ii) the d=19 dimensional data set from the APOGEE survey~citemajewski2017apache with n ≈ 2.7 × 104.