Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms

In this work, we give a poly(d,k) time and sample algorithm for efficiently learning the parameters (i.e., the means and the mixture weights) of a mixture of k spherical distributions in d dimensions. Unlike all previous methods, our techniques apply to heavy-tailed distributions and include examples that do not even have finite covariances. Our method succeeds whenever the component distributions have a characteristic function with sufficiently heavy tails. Examples of such distributions include the Laplace distribution and uniform over [−1, 1] but crucially exclude Gaussians. All previous methods for learning mixture models relied implicitly or explicitly on the low-degree method of moments. Even for the special case of Laplace distributions, we prove that any such algorithm must necessarily use a super-polynomial number of samples. Our method thus adds to the short list of techniques that circumvent the limitations of the method of moments. Somewhat surprisingly, our algorithms succeed in learning the parameters in poly(d,k) time and samples without needing any minimum separation between the component means. This is in stark contrast to the case of spherical Gaussian mixtures where a minimum ℓ2-separation is provably necessary even information-theoretically (Regev and Vijayaraghavan, 2017). Our methods compose well with existing techniques and allow obtaining “best of both worlds” guarantees for mixtures of distributions where every component either has a heavy-tailed characteristic function or has a sub-Gaussian tail with a light-tailed characteristic function. Our algorithm is based on a new approach to learning mixture models via efficient high-dimensional noisy sparse Fourier transforms. We believe that this method will find more applications to statistical estimation. As an example, we give an algorithm for consistent robust estimation of the mean of a distribution D in the presence of a constant fraction of outliers introduced by a noise-oblivious adversary. This model is practically motivated by the literature on multiple hypothesis testing, it was formally proposed in a recent Master’s thesis by one of the authors (Li, 2023), and has already inspired follow-up works.