Learning general Gaussian mixtures with efficient score matching

arXiv:2404.18893v1 Announce Type: cross
Abstract: We study the problem of learning mixtures of $k$ Gaussians in $d$ dimensions. We make no separation assumptions on the underlying mixture components: we only require that the covariance matrices have bounded condition number and that the means and covariances lie in a ball of bounded radius. We give an algorithm that draws $d^{\mathrm{poly}(k/\varepsilon)}$ samples from the target mixture, runs in sample-polynomial time, and constructs a sampler whose output distribution is $\varepsilon$-far from the unknown …

abstract arxiv assumptions components covariance cs.ds cs.lg dimensions general stat.ml study type