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

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.