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

Abstract

We study the nonparametric maximum likelihood estimator $\hat{\ddot{I}}€$ 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 $\hat{\ddot{I}}€$. We provide an algorithm which for small enough $\epsilon >0$ computes an $\epsilon$-approximation of $\hat{\ddot{I}}€$ in Wasserstein distance in time $K+Cn{k}^2\log \log (1/\epsilon )$. Here $K$ is data-dependent but independent of $\epsilon$, while $C$ is an absolute constant and $k=|supp(\hat{\ddot{I}}€)|\le n$ is the number of atoms in $\hat{\ddot{I}}€$. We also certifiably compute the exact value of $|supp(\hat{\ddot{I}}€)|$ in finite time. These guarantees hold almost surely whenever the dataset $(x_1,\dots ,x_n)\in [-c{n}^{1/4},c{n}^{1/4}]$ consists of independent points from a probability distribution with a density (relative to Lebesgue measure). We also show the distribution of $\hat{\ddot{I}}€$ conditioned to be $k$-atomic admits a density on the associated $2k-1$ dimensional parameter space for all $k\le \sqrt{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.

43 pages