Learning Mixtures of Gaussians Using Diffusion Models

arXiv:2404.18869v1 Announce Type: new
Abstract: We give a new algorithm for learning mixtures of $k$ Gaussians (with identity covariance in $\mathbb{R}^n$) to TV error $\varepsilon$, with quasi-polynomial ($O(n^{\text{poly log}\left(\frac{n+k}{\varepsilon}\right)})$) time and sample complexity, under a minimum weight assumption. Unlike previous approaches, most of which are algebraic in nature, our approach is analytic and relies on the framework of diffusion models. Diffusion models are a modern paradigm for generative modeling, which typically rely on learning the score function (gradient log-pdf) along …

abstract algorithm arxiv complexity covariance cs.ds cs.lg diffusion diffusion models error identity math.pr math.st minimum nature polynomial sample stat.ml stat.th text type