A Fourier Approach to Mixture Learning

We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture frac1ksumj=1kN(μj, Id), the goal is to estimate the means μ1, μ2, ldots, μk ∈ ℝd up to a small error. The hardness of this learning problem can be measured by the separation Delta defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with Delta = Omega(√log k) separation, the means can be learned using poly(k, d) samples, whereas super-polynomially many samples are required if Delta = o(√log k) and d = Omega(log k). This leaves open the low-dimensional regime where d = o(log k). In this work, we give an algorithm that efficiently learns the means in d = O(log k/loglog k) dimensions under separation d/√log k (modulo doubly logarithmic factors). This separation is strictly smaller than √log k, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time poly(k)· f(d, Delta, ε), and is thus fixed-parameter tractable in parameters d, Delta and ε. Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.