Learning Mixtures of Gaussians Using the DDPM Objective
Kulin Shah Sitan Chen Adam Klivans
Recent works have shown that diffusion models can learn essentially any
distribution provided one can perform score estimation. Yet it remains poorly
understood under what settings score estimation is possible, let alone when
practical gradient-based algorithms for this task can provably succeed.
  In this work, we give the first provably efficient results along these lines
for one of the most fundamental distribution families, Gaussian mixture models.
We prove that gradient descent on the denoising diffusion probabilistic model
(DDPM) objective can efficiently recover the ground truth parameters of the
mixture model in the following two settings: 1) We show gradient descent with
random initialization learns mixtures of two spherical Gaussians in $d$
dimensions with $1/\text{poly}(d)$-separated centers. 2) We show gradient
descent with a warm start learns mixtures of $K$ spherical Gaussians with
$\Omega(\sqrt{\log(\min(K,d))})$-separated centers. A key ingredient in our
proofs is a new connection between score-based methods and two other approaches
to distribution learning, the EM algorithm and spectral methods.