A Fourier Approach to Mixture Learning. (arXiv:2210.02415v2 [cs.LG] UPDATED)

We revisit the problem of learning mixtures of spherical Gaussians. Given
samples from mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(\mu_j, I_d)$, the
goal is to estimate the means $\mu_1, \mu_2, \ldots, \mu_k \in \mathbb{R}^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(\sqrt{\log
k})$ separation, the means can be learned using $\mathrm{poly}(k, d)$ samples,
whereas super-polynomially …

arxiv