Learning Mixtures of Gaussians Using Diffusion Models

Learning Mixtures of Gaussians Using Diffusion Models

March 5, 2025 | Khashayar Gatmiry, Jonathan Kelner, Holden Lee
This paper presents a new algorithm for learning mixtures of Gaussians using diffusion models. The algorithm achieves quasi-polynomial time and sample complexity in learning a mixture of k Gaussians with identity covariance in R^n, under a minimum weight assumption. The results extend to continuous mixtures of Gaussians where the mixing distribution is supported on a union of k balls of constant radius. The algorithm is based on the framework of diffusion models, which are modern generative models that rely on learning the score function (gradient of log-pdf) along a process transforming a pure noise distribution to the data distribution. The paper provides theoretical guarantees for learning nontrivial families of distributions using diffusion models, which is a novel contribution. The algorithm involves learning the score functions for a mixture of Gaussians using piecewise polynomial regression and combining this with known convergence results for diffusion models. The paper also discusses related work, including previous approaches to learning mixtures of Gaussians and the theoretical guarantees for diffusion models. The main results include a theorem that shows the algorithm can learn a distribution that is ε-close in TV distance to the actual distribution with quasi-polynomial time and sample complexity. The paper also provides a corollary that applies to the case of Gaussian convolutions of distributions on low-dimensional manifolds. The algorithm is described in detail, including the steps for learning the score functions and generating samples from the learned distribution. The paper also discusses the theoretical implications of the results, including the relationship between diffusion models and other generative models, and the potential for extending the results to other families of distributions.This paper presents a new algorithm for learning mixtures of Gaussians using diffusion models. The algorithm achieves quasi-polynomial time and sample complexity in learning a mixture of k Gaussians with identity covariance in R^n, under a minimum weight assumption. The results extend to continuous mixtures of Gaussians where the mixing distribution is supported on a union of k balls of constant radius. The algorithm is based on the framework of diffusion models, which are modern generative models that rely on learning the score function (gradient of log-pdf) along a process transforming a pure noise distribution to the data distribution. The paper provides theoretical guarantees for learning nontrivial families of distributions using diffusion models, which is a novel contribution. The algorithm involves learning the score functions for a mixture of Gaussians using piecewise polynomial regression and combining this with known convergence results for diffusion models. The paper also discusses related work, including previous approaches to learning mixtures of Gaussians and the theoretical guarantees for diffusion models. The main results include a theorem that shows the algorithm can learn a distribution that is ε-close in TV distance to the actual distribution with quasi-polynomial time and sample complexity. The paper also provides a corollary that applies to the case of Gaussian convolutions of distributions on low-dimensional manifolds. The algorithm is described in detail, including the steps for learning the score functions and generating samples from the learned distribution. The paper also discusses the theoretical implications of the results, including the relationship between diffusion models and other generative models, and the potential for extending the results to other families of distributions.
Reach us at info@study.space