Learning Mixtures of Gaussians Using the DDPM Objective
Authors: Kulin Shah
Sitan Chen
Adam Klivans
Venue: NeurIPS 2023 poster (2023)
Keywords: Mixtures of Gaussians
score-based generative models
provable learning of score
Expectation-Maximization
DDPM generative model
TL;DR: We prove that gradient descent based on the Denoising Diffusion Probabilistic Model (DDPM) objective can efficiently learn the accurate score function of Mixtures of Gaussians.

Abstract: 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 for one of the most fundamental distribution families, Gaussian mixture models.
We prove that GD 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 GD with random initialization learns mixtures of two spherical Gaussians in $d$ dimensions with $1/\text{poly}(d)$-separated centers.
2. We show GD 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, EM and spectral methods.

Learning Mixtures of Gaussians Using the DDPM Objective
Kulin Shah UT Austin kul sulinshhhutexas.co
Sitan Chen Harvard University tan@neeas... harvard.
Adam Klivans UT Austin klivans@cs utexas.
Abstract
Recent works have shown that diffusion models can learn essentially any distribu- tion provided one can perform score estimation. Yet it remains poorly understood under what settings score estimation possible, let alone when practical gradient- based algorithms for this task can provably succeed.
In this work, give the first provably efficient results along these lines for the most fundamental distribution families, Gaussian mixture models. We prove that gradient descent 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/poly (d) -separaad centers.
2. We show gradient descent with warm start learns mixtures of K spherical Gaussians with 22( /log( min K, -separatd centers.
A key ingredient in our proofs is new connection between score-based methods and two other approaches distribution learning, the iopectationmmaximzzaiin (EM) algorithm and spectral methods.
Introduction
In recent years diffusion models [SSDK*20, SDWMG15, SE19] have emerged as powerful frame- work for generative modeling and now form the backbone of notable image generation systems like DALL-E 2 [RDN+22], Imagen +SC,+222, and Stable Diffusion [RBL+22]. At the heart of this framework is a reduction from distribution learning to denoising or score estimation. That is, in order to generate new samples from a data distribution q given collection of independent samples, suffices to learn the score function, i.c., the gradient of the log-density of the data distribution when convolved with varying levels of noise (see Section 1.3). popular and well-studied objective for score matching is the denoising diffusion probabilistic model (DDPM) objective due to [HJA20]. Optimizing this objective amounts solving the following type problem: given a noisy observation I of a sample from estimate the mean of the posterior distribution over æ
While number of theoretical works [DBTHD21, BMR22, CLL22, DB22, LLT22, LWYL22, Pid22, WY22, CCb+ CDD23, LLT23, 23a, LWCC23, BDD23] have established rigorous con- the data distribution, these
vergence guarantees for diffusion models under mild assumptions works assume the existence of an oracle for score estimation and Ieave open whether one can actually provably implement such an oracle for interesting families of data distributions. In practice, the algorithm of choice for score estimation is simply to train student network via gradient descent (GD) to fit set of examples (x. F). We thus ask:
Are there natural data distributions under which GD provably achieves accurate score estimation?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work, we consider the setting where is given by a mixture of Gaussians. Concretely, we assume that there exist centers pi, ................................ KK I2 such that
1 K Σ Id).
q
We answer the above question in the affirmative for this class of distributions:
Theorem 1 (Informal, see Theorems 7 and 13). Gradient descent the DDPM objective with random initialization efficiently learns the parameters of an unknown mixture of two spherical Gaussians with 1/ h/ppoy(d)=sppariiie centers.
Theorem 2 (Informal, see Theorem 16). When there is a warm start of the centers, gradient descent on the DDPM objective efficiently learns the parameters an unknown mixture of K spherical Gaussians with Q) Vloo/oogmiin (ong(min(H)) K -Separrated centers.
The DDPM objective is described in Algorithm 1. The term "efficiently" above means that both the running time and sample complexity of our algorithm is polynomial in the dimension d, the inverse accuracy 1/e, and the number of components K. In the informal discussion, we often work with population gradients for simplicity, but our proofs show that empirical estimates of the gradient suffice (full details can be found in the Appendix).
Algorithm 1: GMMDENOISER((. {uz ( H)
Input: Noise scale I, initialization {uy (0) J number of gradient descent steps H
Initialize the parameters for the score estimate at 0 = {u J (see Eq. (9) for how the estimate 8p depends on the parameters and Eq. (8) for the definition of (4,)) (0)
2 Run gradient descent on the DDPM objective L, (s0.)) for steps where
(80,)) = E [||00, (Xx) + V1 exp( 26)
Ze
( 3 return 00 = {ML 1a where th denotes the parameters after H steps of GD.
We refer to Section 1.3 for formal description of the quantities used in Algorithm Note that there are by now host of different algorithms for provably learning mixtures of Gaussians (see Section 1.1). For instance, quantitative guarantees of Theorems 1 and 2 [DTZ17, XHM16, KC20, SN21], and in fact even stronger guarantees are known via the method of moments. Unlike works based on the method of moments however, our algorithm is practical. And unlike works based on EM, it is based on an approach which empirically successful for wide range of realistic data distributions. Furthermore, as we discuss in Section 1.2, the analysis of Algorithm leverages an intriguing and, to our knowledge, novel connection from score estimation to EM, as well as to another notable approach for learning mixture models, namely spectral methods. Roughly speaking, at large noise levels, the gradient updates in Algorithm are essentially performing a type of power iteration, while at small noise levels, the gradient updates are performing the "M" step in the EM algorithm.
already known that expectation- -naitiinnmmiimmzattionn (EM) achieves the
1.1 Related work
Theory for diffusion models. number of works have given convergence guarantees for DDPMs and variants [DBTHD21, BMR22, CLL22, DB22, LLT22, LWYL22, Pid22, WY22, CCb, CDD23, LLT23, LWCC23, BDD23, CCL+ These results show that, given an oracle for accurate score estimation, diffusion models can learn essentially any distribution over Idd (e.g. [CCL* 23b, LLT23, CLL22] show this for arbitrary compactly supported distributions). Additionally, two recent works [EAMS22, MW23] have used Eldan's 's stochastic localization [Eld13, Eld20], which is reparametrization in time and space of the reverse SDE for DDPMs, to give sampling algorithms for certain distributions arising in statistical physics. As we discuss next, these works are end-to-end in that they also give provable algorithms for score estimation via approximate message passing, though the statistical task they address is not distribution learning.

---

Provable score estimation. There is rich literature giving Bayes-optimal algorithms for various natural denoising problems via methods inspired by statistical physics, like approximate message passing (AMP) (e.g. [MV21, CFM21, BM11, Kab03, DMM09, DMM101) and natural gradient descent (NGD) on the TAP free energy [CFM21, HAMS22, Ce122]. The abovementioned works [EAMS22, MW23] (see also [Cel22]) build on these techniques to give algorithms for the denoising problems that arise in their implementation of stochastic localization. These works on denoising via AMP or NGD are themselves part of broader literature on variational inference, a suitable literature review would be beyond the scope of this work, see e.g. [BKM17, WJ+ MM09].
We are not aware of any provable algorithms for score estimation explicitly in the context of distribu- tion learning. That said, may be possible to extract a distribution learning result from [EAMS22]. While their algorithm was for sampling from the Sherrington- Kirtiton-iikaktiiick. (SK) model given the Hamiltonian rather than training examples as input, if one is instead given training examples drawn from the SK measure, then at sufficiently high temperature one can approximately recover the Hamil- tonian [AG22]. In this case, a suitable modification [EAMS22] should be able to yield an algorithm for approximately generating fresh samples from the SK model given training examples.
Learning mixtures of Gaussians. The literature on provable algorithms for learning Gaussian mixture models is vast, dating back to the pioneering work of Pearson [Pea94], and we cannot do justice it here. We mention only works whose quantitative guarantees are closest in spirit to ours and refer to the introduction of [I.1222] for a comprehensive overview of recent works in this direction. For mixtures of identity- covariicce Gaussians in high dimensions, the strongest existing guarantee is polynomial-time algorithm [LL.22] for learning the centers as long as their pairwise separation slightly exceeds 12( (oylog K) based on a sophisticated instantiation of method of moments inspired by the muasipolynomial-tin [RV17]. this is essentially optimal. In contrast, our Theorem only applies given one initializes in neighborhood of the true parameters of the mixture. We also note the exponential-time spectral algorithm of [S0AJ14] and quasipolynomial -ime tensor-based algorithm of [DK20], which achieve density estimation even in the regime where the centers are arbitrarily closely spaced and learning the centers is information- theoretically impossible.
algorithms of [DKSI8, HL18, KSS18J. By the lower bound in
A separate line of work has investigated the "texthook" algorithm for learning Gaussian mixtures, namely the EM algorithm [BWY17, DS07, DTZ17,, XHM16, YYS17, ZLS20, KC20, SN21]. No- tably, for balanced mixtures of two Gaussians with the same covariance, [DTZ17] showed that finite-sample EM with random initialization converges exponentially quickly to the true centers. For mixtures of K Gaussians with identity covariance, [KC20, SN21] showed that from an initialization sufficiently close to the true centers, finite-sample EM converges exponentially quickly to the true centers as long as their pairwise separation is 22( Vlog K). In particular, [SN21] establish this local convergence as long as every center estimate is initialized at distance at most A/2 away from the corresponding true center, where A is the minimum separation between any pair of true centers; this radius of convergence is provably best possible for EM.
Lastly, we note that there are many works giving parameter recovery algorithms mixtures of Gaussians with general mixing weights and covariances, all of which are based on method of moments [KMV10 10, HP15, 1an21, BS15, MV10, LM23, BDJ 22, DHKK20J. Unfortunately, for general mixtures of K Gaussians, these algorithms run in time at least do(K) and there is strong evidence [DKS17, BRST21] that this unavoidable for computationally efficient algorithms.
1.2 Technical overview
We begin by describing in greater detail the algorithm we analyze in this work. For the sake of intuition, in this overview will focus on the case of mixtures of two Gaussians (K = 2) where the centers are well-separated and symmetric about the origin, that is, the data distribution is given by
1
q= 5 N(nx Id) + 5 N(-=" Id).
(1)
At the end of the overview, we briefly discuss the key challenges for handling smaller separation and general K.
Loss function, architecture of the score function and student network. The algorithmic task at the heart of score estimation is that of denoising. Formally, for some noise level t >> O, we are given
3

---

noisy sample
=
11-(exp(22t))
where Xo is clean sample drawn from the data distribution q, and Ze ~ (O. Conditioning on X₁ induces some posterior distribution over the noise Z₁ and our goal is form an estimate s for the mean of this posterior which achieves small eπror on average over the randomness of Xo and Z.. That is, we would like to minimize the DDPM objective, which up to rescaling given by!
(x(s) = Ex ||x(X,) Zel1"-
As discussed in the introduction, the algorithm of choice for minimizing this objective in practice is gradient descent some student network. To motivate our choice of architecture, note that when the data distribution is given by (1), the true minimizer of 4g is, up to scaling,
tanh((p 2)) - I, where μ - p exp(-t).
(2)
See Appendix A for the derivation. Notably, Eq. (2) is exactly a two-layer neural network with tanh activation. As a result, we use the same architecture for our student network when running gradient descent. That is, given weights je E Rd, our student network is given by (x) - tanh(j" z)μu x. The exact gradient updates on jr given in Lemma C.2.
As we discuss next, depending on whether the noise level t is large or small, this update closely approximates the update in one of two well-studied algorithms for learning mixtures of Gaussians: power method and EM respectively.
Learning mixtures of two Gaussians. We first provide brief overview of the analysis and then go into the details of the analysis. We start with mixtures of two Gaussians of the form (1) where || Il is (2).). In this case, analyze the following two-stage algorithm. We first use gradient descent on the DDPM objective with large t starting from random initialization. We show that gradient descent in this "high noise" regime resembles type of power iteration and gives μ that has a nontrivial correlation with 14. Starting from this jr, we then run gradient descent with small t. We show that the gradient descent in this "small noise" regime corresponds to the EM algorithm and converges exponentially quickly to the ground truth.
Large noise level: connection to power iteration. When t is large, we show that gradient descent on the DDPM objective is closely approximated by power iteration. More precisely, in this regime, the negative gradient of T., (sp) is well-approximated by
-VpLe(s)) (2 rId) p.
where r is a scalar that depends on μ (See Lemma 8). So the result of a single gradient update with step size 7) starting from z is given by
H ( xo ((1 - 17) Id 2n p4 )(.
(3)
This shows that each gradient step can be approximated by one step of power iteration (without normalization) on the matrix (1 - 77r) Id + 2m/4 TT It is know that running enough iterations of the latter from a random initialization will converge in angular distance to the top eigenvector, which in this case is given by pī- This suggests that if we can keep the approximation error in (3) under control, then gradient descent i will also allow us converge truth. We implement this strategy in Lemma 10. Next, we argue that once we are in a neighborhood of the ground truth, we can run GD on the DDPM objective at low noise level to refine our estimate.
neighborhood of the ground
Low noise level: connection to the EM algorithm. When t is small, we show that gradient descent on the DDPM objective is closely approximated by EM. Here, our analysis uses the fact that μ²' is sufficiently large and requires that we initialize μ to have sufficiently large correlation with the true direction nz. We can achieve the latter using the large-/ analysis in the previous section.
Provided we have this, when t is small it turns out that the negative gradient is well-approximated by
V F Le (sp) z Ex~N(a; ad) [tanh( (j,, X]) n.
'The real DDPM objective is slightly different, see (5). The latter is what we actually consider in this paper. but this distinction is unimportant for the intuition in this overview.

---

Note that the expectation is precisely the step in the EM algorithm for learning mixtures of two Gaussians (see e.g. Eq. (2.2) of [DTZ17]). We conclude that single gradient update with step size n) starting from y is given by mixing the old weights μ with the result of the "te' in EM:
n' 7. (LL())))) v (1 (1-1)) + +1x [x~NN(2
.d) (tanb( (1, X))X
"M" step in EM algorithm
[XHM16] and [DTZZ17] showed that EM converges exponentially quickly to the ground truth lr from warm start, and we leverage ingredients from their analysis to prove the same guarantee for gradient descent on the DDPM objective at small noise level (see Lemma 12).
Extending to small separation. Next, suppose we instead only assume that ||"²"| || is 2(1/poly(()) i.e. the two components in the mixture may have small separation. The above analysis breaks down for the following reason: while it is always possible show that gradient descent at large noise level converges in angular distance to the ground truth, if ||~||| is small, then we cannot translate this to convergence in Euclidean distance.
We circumvent this as follows. Extending the connection between gradient descent at large t and power iteration, we show that similar analysis where instead run projected gradient descent over the ball of radius ||~* yields a solution arbitrarily close to the ground truth, even without the EM step. The projection step be thought of as mimicking the normalization step in power iteration.
might appear to the reader that this projected gradient-based approach is strictly superior to the two-stage algorithm described at the outset. However, in addition to obviating the need for projection step when separation is large, our analysis for the two-stage algorithm has the advantage of giving much more favorable statistical rates. Indeed, can show that the sample complexity of the two-stage algorithm has optimal dependence on the target error (1/=²), whereas we can only show suboptimal dependence (I/s*) ) for the single-stage algorithm.
Extending to general K. The connection between gradient descent on the DDPM objective at small & and the EM algorithm is sufficiently robust that for general K, our analysis for K 2 can generalize once we replace the ingredients from [XHM16] and [DTZ17] with the analogous ingredients in existing analyses for EM with K Gaussians. For the latter, it is known that if the centers of the Gaussians have separation 22 (Volo min (K, d)), then EM will converge from warm start [KC20, SN21]. By carefully tracking the error in approximating the negative gradient with the "M"-step in EM, we able show that gradient descent on the DDPM objective small achieves the same guarantee.
1.3 Preliminaries
Diffusion models. Throughout the paper, we use either & go to denote the data distribution and X or Xo to denote the corresponding random variable on IRd, The two main components in diffusion models are the forward process and the reverse process. The forward process transforms samples from the data distribution into noise, for instance via the Monstein-Uhlenber (OU) process:
dX, = -x, di + V2dW, with Xo 40
where (Wz) is standard Brownian motion in Rdd, We use q: to denote the law of the OU process time f. Note that for X, ~ lt.
X, = exp( exxp(tt)X- VI- with Xo ~ go. Z, 2~~ N(0,
The reverse process then transforms noise into samples, thus performing generative modeling. Ideally, this could achieved by running the following stochastic differential equation for some choice of terminal time T:
dxt== (X: + 2V, In + v2dW, with X ~ qr
where W, is the reversed Brownian motion. In this reverse process, the iterate X; is distributed acccording to - for every t E [0, 7' so that the final iterate X; is distributed according to the
Note that although μ² is unknown, can estimate its norm from samples.
5

---

data distribution go. The function v In ge is called the score function, and because it depends on which is unknown, in practice one estimates it by minimizing the score matching loss
min Ex Ex |, (X,) - V, (X.))
(4)
standard calculation (see e.g. Appendix of [CCL -3bb) shows that this equivalent to minimiz- ing the DDPM objective in which one wants to predict the noise Z₁ from the noisy observation X, i.e.
(x())) Exo.2, (x
Ze
min St
(5)
V1
exp(-2t) 2t)
While we have provided background on diffusion models for context, in this work we focus specifically on the optimization problem (5).
Mixtures of Gaussians. sians:
We consider the case of learning mixtures of K equally weighted Gaus-
K Σ 1=1
q - 90
K NR ((f,Id))
(6)
where μi denotes the mean of the 7th Gaussian component. We define 0- = {ug MS. .5..., . ..kk For the mixtures of two Gaussians, we can simplify the data distribution as
4o 2 N((" Id) +
2 -N(x""
Note that distribution in Eq. (7) equivalent to the distribution Eq. (6) with = 2 because shifting the latter by its mean will give the former distribution, and furthermore the necessary shift can be estimated from samples. The following is immediate:
Lemma 3. If go is mixture of K Gaussians as in Eq. (6), then for any & > O, qi is the mixture of K Gaussians given by
1 E [N( where ph 2 μū exp(-t).
(8)
See Appendix A for a proof of this fact. We can see that the means of ai get rescaled according to the noise level l. We also define P..... Lemma 4. The score function for distribution qu for any > 0, is given by
K
exp( || 11,,112/22
V (n) E
(x)
- where (x) Σ expl -112 15 112/2)
1=1
For a mixture of two Guussians, the score fanction simplifies to Va logogg (x) = tanh(j x)p - x, where
ue _ n¹ exp(-1)
See Appendix A for the calculation.
Recall that V v log q: (x) is the minimizer for the score-matching objective given in Eq. (4). Therefore, we parametrize our student network architecture similarly to the optimal score function. Our student architecture for mixtures of K Gaussians is
(i,((x) A exp( ||
14i 11,,e11/22)
s0, (x)
Wi, wi (2)Pu,)) - x, where
(9)
Σ exp(- 1
F4. μ4 exp(-t).
where 0r = [11,0 M2,0s ... PK,}} denotes the set of parameters at the noise scale For mixtures of two Gaussians, we simplify the student architecture as follows:
se. (z) = tanh(H: x =) x, where He è pexp(-t).
As Og only depends on pt in the case of mixtures of two Gaussians, we simplify the notation of the
score function from 80, (x) to (x) in that case. We use fi, and juğ to denote the unit vector along the direction of ju, and μr, respectively. Note that we often use μa, (or 0,) to denote the current iterate of gradient descent on the DDPM objective and μ to denote the iterate after taking gradient descent step from Mr-

---

Sopeectation-Maiiiizzini (EM) algorithm. The EM algorithm is composed of two steps: the E-step and the M-step. For mixtures of Gaussians, the E-step computes the expected oog-iiklihood based on the current mean parameters and the M-step maximizes this expectation to find new estimate of the parameters.
Fact 5 (See e.g., [DTZ17, YYS17, KC20] for more details). When X is the mixture of K Gaussian and (/1, .2,.... ... px)
are current estimates of the means, the population EM update for all E (1,2 2........ K is given by
p4 = Ex (X)x
where (x(X) exp( - (1.11112)
Ex Ww (X)]
ΣØ= expl - |X - pyl12/2)
The EM update for mixtures of two Gaussians given in Eq. (7) simplifies to
Il Ex~N(p Id) [tannh(u X)X].
An analogous version of the EM algorithm, called the gradient EM algorithm, takes gradient step in the direction of the M-step instead of optimizing the objective in the M-step fully.
Fact (See e.g., [YYS17, SN21] for more details). For all i E ,1. K}. update for mixtures of K Gaussian is given by
the gradient EM-
14 = + n (x) - -++),
where 1) is the learning rate.
2 Warmup: mixtures of two Gaussians with constant separation
In this section, we formally state our result for learning mixtures of two Gaussians with constant separation. This case highlights the main proof techniques, namely viewing gradient descent on the DDPM objective as power iteration and as the EM algorithm.
2.1 Result and algorithm
Theorem 7. There is an absolute constant such that the following holds. Suppose a mixture of two Gaussians with the mean parameter p* satisfies ||p*|| > Then, for any > 0, there is procedure that calls Algorithm with high probability. Moreover, the algorithm has time and sumple complexity poly(d)/e² (see Theorem C.I for more precise quantitatiie bounds).
two disferent noise scales and outputs j such that || - 1²" S
Algorithm. The algorithm has two stages. In the first stage we run gradient descent on the DDPM objective described in Algorithm from a random Gaussian initialization and noise scale t for a fixed number of iterations H where I O(log d) ("high noise") and H poly 1/e). In the second stage, the procedure uses the output of the first step as initialization and runs Algorithm at a "low noise" scale of l2 (1).
2.2 Proof outline of Theorem 7
We provide proof sketch of correctness of the above algorithm and summarize the main technical lemmas here. All proofs of the following lemmas can be found Appendix
Part I: Analysis of high noise regime and connection to power iteration. We show that in the
large noise regime, the negative gradient -V Lx,,ss is well-approximated by 2ptn 14 pell μe- Recall that this result the key to showing the resemblance between gradient descent and power iteration. Concretely,
show the following lemma:
Lemma 8 (See Lemma C.3 for more details). Fort = O(log)) d), the gradient descent update on the DDPM objective Le() can be approximated with 2nīni" μr -31l pe:
(- (L)())))) - (2HiHō me - 30-31lel1l (1)) poly(1/d).
7

---

From Lemma 8, it immediately follows that yt', the result of taking single gradient step starting from Mr, well-approximated by the result of taking a single step of power iteration for matrix whose leading eigenvector is J
14 - 14 1 (s))s = (Id(1 3 2 1
The second key element is to show that as a consequence of the above power iteration update, the gradient descent converges in angular distance to the leading eigenvector. Concretely, show the following lemma:
Lemma 9 (Informal, see Lemma C.5 for more details). Suppose plg is the iterate after one step of grudient descent on the DDPM objective from Pt. Denote the angle between Pr. and μi to be 0 and between 1lg and ji to be 0'. this case, we show that
tan 0' = max (K1 tan 0, 82).
where and R2 S 1/poly(d).
Note tan 0' < tan implies that 0' or equivalently (4) > (fte (it). Thus, the above lemma shows that by taking gradient step in the DDPM objective, the angle between f4 and μi decreases. By iterating this, we obtain the following lemma:
Lemma 10 (Informal, see Lemma C.6 for more details). Rumning gradient descent from random initialization on the DDPM objective Lı(s,) for = Ollog d) gives μa for which (De, Pi) is (1(1).
Note that we cannot keep running gradient descent at this high noise scale and hope achieve such that || - 1z" (e). This because Lemma 9 can only guarantee that the angle between μe and in is Os)), but this does not imply || μ²1 is (s). Instead, described in Part II, will proceed with a smaller noise scale.
Part II: Analysis of low noise regime and connection to EM. In the low noise regime, we run Algorithm using output from Part as our initialization. Our analysis here shows that whenever the initialization dr satisfies the condition of (ūt, (4)) being S2(1), ll,., wi'l contracts after every gradient step. To start with, we show that the result of a population gradient step on the DDPM objective (s(s)) results in the following:
14 = (1 n)p + Ea Ja) [tanh(u, x)x] + r)G()e,)
where 14 is the parameter after a gradient step, 17 is the learning rate, and function is given by
G(u, n() = Er-N((a -لاl= tanh"(p (T)TT)))l I x + tanh (μ æ)μ² xx tanh' (n x)p].
Note use the population gradient here only for simplicity; in the Appendix we show that empirical estimates of the gradient suffice. After some calculation, we can show that
114 - 16-1+11 S (1 - 1) 1p: 14 + 1 BellB- .dy [tanb(u) x)x] μ + G pi) .10))
Using Fact 5, we know that EE Ia) [tanh(p) x)æ] is precisely the result of one step of EM starting from Nt,, and it is known [DTZ17] that the EM update contracts the distance between μr and μ4 as follows:
| Id) [tanh(4, x)x] HIll S A1llm -4.ll for some A
(11)
remains to control the second term in Eq. (10), for which we prove the following:
Lemma 11 (Informal, Lemma C.9 for more details). When paaeelpp"|| 2(1) and the noise scale
f == (1), then for every l with (p,, ji*) being Q(1), the following inequality holds:
||G( |el S A2llpe- pilll for some X2 < 1.
Combining Eq. (11) and Lemma 11 with Eq. (10), we have
1 pi S (1 17(1 A >2) --1l1-
(12)
We can set parameters to ensure that A + X2 < 1 and therefore that || wi'l contracts with each gradient step. Applying Lemma 11 and Eq. (12), we obtain the following lemma summarizing the behavior of gradient descent the DDPM objective in the low noise regime.

---

Lemma 12 (Informal). For any 0 and for the noise scale = (1)), starting from an initialization Hr, for which (ie, (G) = ((1), rumning gradient descent on the DDPM objective L,(s,) will give us mean parameter such that I| - n²ll - O(e)
Combining Lemma 10 and Lemma 12, we obtain our first main result, Theorem 7, for learning mixtures of two Gaussians with constant separation. For the full technical details, see Appendix C.
3 Extensions: small separation and more components
3.1 Mixtures of two Gaussians with small separation
In this section, we briefly sketch how the ideas from Section 2 can be extended to give our second main result, namely on learning mixtures of two Gaussians even with small separation. We defer the full technical details to Appendix D.
Theorem 13. Suppose mixture of two Gaussians has mean parameter μº that satisfies ||="
O 1
poly(ay) ). Then, for any & > O, there exists a modification of Algorithm I that provides an estimate such that l| 1² < O(e) with high probability. Moreover. the algorithm has time and sample complexity poly(d)/E* (see Theorem D.1 1 for more precise quantitative bounds).
Algorithm modification. The algorithm that we analyze runs projected gradient descent on the DDPM objective but only in the high noise scale regime where (log d). At each step, we project the iterate μ to the ball of radius R, where R is an empirical estimate for || obtained by
drawing samples T1,..., Zn from the data distribution and forming R & ( Σm= ||| d)1/2
Proof sketch. Lemma and Lemma 10 apply even when the components of the mixture have small separation, and they show that running gradient descent on the DDPM objective results in μr and l being (1) close in angular distance. Although our analysis can be extended show that gradient descent can achieve ((E) angular distance, this does not guarantee that || p ll is O If in addition to being (z) close in angular distance, we also have that |||||| s || ||. then it is easy to see that 1| Mill is indeed (c))
Observe that if R is approximately equal to || ll. then the projection step in our algorithm ensures that our final estimate μ4 satisfies this additional condition of][ Il & [|[][]] It is not hard to show that R² is an unbiased estimate of I|" so standard concentration shows that taking poly (d, ) suffices to ensure that sufficiently close to || ||.
3.2 Mixtures of K Gaussians, from warm start
In this section, we state our third main result, namely for learning mixtures of K Gaussians given by Eq. (6) from a warm start, and provide an overview of how the ideas from Section 2 can be extended to obtain this result.
Assumption 14. (Separation) For a mixture of K Gaussians given by Eq. (6), for every pair of components i,j E 21.2....., K} with + j. we assume that the separation between their means ||n -151 2 C CoToo(min(K K, d)) for sufficiently large absolute constant C >>0 O.
Assumption 15. (Initialization) For each component i 21, we have an initialization " with the property that !! pfll S C" (ooolommin( K, d)) for sufficiently small absolute constant C' 0.
Theorem 16. Suppose a mixture of Gaussians satisfies Assumption 14. Then, for any ((L/polydd)) running gradient descent on the DDPM objective (Algorithm 1) at low noise scale t 0(1) and with initialization satisfying Assumption 15 results in mean parameters {m: such that with high probability, the mean parameters satisfy || # S O(e) for each E (1,2.... K). Additionally, the runtime and sample complexity of the algorithm is poly (d, 1/E) (see Theorem E.1 for more precise quantitative bounds).
We provide brief overview of the proof here. The full proof can be found in Appendix E.

---

Proof sketch. For learning mixtures of two Gaussians, we have already established the connection between gradient descent on the DDPM objective and the EM algorithm. For mixtures of K Gaussians, however, in local neighborhood around the ground truth parameters 0*, we show an equivalence between gradient EM (recall gradient EM performs one-step of gradient descent on the "M" step objective) and gradient descent on the DDPM objective. In particular, our main technical lemma (Lemma E,4) shows that for noise scale = @(1) and for any μi that satisties || - Alll & O(yloo(min(H d.)). we have
-V,,, (s0.) = Ex, -c,)))
-
Therefore, the iterate p4,, resulting from single gradient step on the DDPM objective Ly(so.) with learnigg rate 77 is given by
Lí. M1,t - V/ pr L((s),) = M1,:
+ |1, Ex,
p1,1)l
(13)
Comparing Fact with Eq. (13), we see the correspondence in this regime between gradient descent on the DDPM objective to gradient EM. Using this connection and existing local convergence guarantee from the gradient EM literature (SN21, KC20), we obtain our main theorem for mixtures of K Gaussians. Full details can be found Appendix E.
Acknowledgments
SC would like to thank Sinho Chewi, Khashayar Gatmiry, Frederic Koehler, and Holden Lee for enlightening discussions on sampling and score estimation. KS and AK are supported by the NSF AI Institute for Foundations of Machine Learning (IFML). SC is supported by NSF Award 2103300.
References
[AG22] Ahmed El Alaoui and Jason Gaitonde. Bounds on the covariance matrix of the sherrington Sherrigtoonkkirpparrekk -irkpatrikk model. arXiv preprint arXiv:2212.02445. 2022.
[BDD23] Joe Benton, George Deligiannidis, and Arnaud Doucet. Error bounds for flow matching methods. arXiv preprint arXiv:2305.16860. 2023.
[BDI+222 Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh Vempala. Robustly learning mixtures of k arbitrary gaussians. In Proceed- ings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1234-1244 2022.
[BKM17] David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 112(518):559-87 2017.
[BM11] Mohsen Bayati and Andrea Montanari. The dynamics of message passing dense graphs, with applications to compressed sensing. IEEE Transactions on Information 1'eeory 57(2):764-7855 2011.
[BMR22] Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative modeling with denoising auto-encoders and Langevin sampling. arXiv preprint 2002.00107, 2022.
[BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous Iwe. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694-707, 2021.
[BS15] Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. SIAM Journal on Computing, 44(4):889 911, 2015.
[WWY17]
Sivaraman Balakrishnan, Martin Wainwright, and Bin Yu. Statistical guarantees for the em algorithm: From population to sample-based analysis. 2017.
[CCI.+23l Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast. arXiv preprint 1XXX::2305.11990 2023.
10

---

[CCL [3b]] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023.
[CDD23] Sitan Chen, Giannis Daras, and Alexandros Dimakis. Restoration- -etgraationn beyond linear diffusions: A non-asymptotic analysis for ddim-type samplers. arXiv preprint arXiv:2303.033: 2023.
[Cel22] Michael Celentano. Sudakov-femique post-amp, and a new proof of the local convexity of the tap free energy. arXiv preprini arXiv:2208.09555 2022.
[CFM21] Michael Celentano, Zhou Fan, and Song Mei. Local convexity of the tap free energy and amp convergence for 22-synchronization. arXiv preprint arXiv:2106. 11221006114488 11428, 2021.
[CLL22] Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: user-friendly bounds under minimal smoothness assumptions. arXiv preprint arXiv:2211.01911 2022.
[DB22] Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions Machine Learning Research, 2022.
[DBTHD21] Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion Schrödinger bridge with applications to score-based generative modeling. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 17695-17709. Curran Associates, Inc., 2021.
[DHKK20] Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar. Robustly learning any clusterable mixture of gaussians. arXiv preprint arXiv:2005.064/ 2020.
[DK20) Ilias Diakonikolas and Daniel M Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In 2020 IEEE 6/ Annual Symposium on Foundations of Computer Science (FOCS), pages 184-195. IEEE, 2020.
[DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017.
[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047-1060, 2018.
[DMM09] David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algo- rithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914-19) 18919, 2009.
[DMM10] David L Donoho, Arian Maleki, and Andrea Montanari. Message passing algorithms for compressed sensing: I. motivation and construction. In 2010 JEEE information theory workshop on information theory (ITW 2010, Cairo), pages 1-5. IEEE, 2010.
[DS07] Sanjoy Dasgupta and Leonard J Schulman. A probabilistic analysis of em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research, 8:203-224 2007.
[TTZ77] Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. Ten steps of em suffice for mixtures of two gaussians. In Conference on Learning Theory, pages 704-710. PMLR, 2017.
[EAMS22] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the sherrington- kirkpatrick gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323-334. IEEE, 2022.
11

---

[Eld13] Ronen Eldan. Thin shell implies spectral gap up to polylog via a stochastic localization scheme. Geometric and Functional Analysis, 23(2):322-569 2013.
[Eld20] Ronen Eldan.
Taming correlations through entropy-eeffcient measure decompositions with applications to mean-field approximation. Probability Theory and Related Fields, 176(3-4)7377-55, 2020.
[HJA20] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[HL18] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034, 2018.
[HP15] Moritz Hardt and Eric Price. Tight bounds for learning mixture of two gaussians. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 753-760, 2015.
[Kab03] Yoshiyuki Kabashima. edma multiuser detection algorithm on the basis of belief propagation. Journal of Physics A: Mathematical and General, 36(43): 2003,
[Kan21] Daniel M Kane. Robust learning of mixtures of gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1246-1258. SIAM, 2021.
[KC20] Jeongyeol Kwon and Constantine Caramanis. The em algorithm gives sample- optimality for learning mixtures of well-separated gaussians. In Conference Learning Theory, pages 2425-2455 2287. PMLR, 2020.
[KMV10] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two gaussians. Proceedings of the forty-second ACM symposium on Theory of computing, pages 353-562,77 2010.
[KSS18) Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035-1046, 2018
[LL22] Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polyno- mial time. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1248-1261, 2022.
[LLT22] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[LLT23] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023,
[LM23] Allen Liu and Ankur Moitra. Robustly learning general mixtures of gaussians. Journal of the ACM, 2023.
[LWCC23] Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion-bain based generative models. arXiv preprint arXiv:2306.09255 092551, 2023.
[LWYLL22] Xingchao Liu, Lemeng Wu, Mao Ye, and Qiang Liu. Let build bridges: under- standing and extending diffusion generative models. arXiv preprint arXiv:2208. /4699, 2022.
[MM09] Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
12

---

[MV10] Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 93-102. IEEE, 2010.
[MV21] Andrea Montanari and Ramji Venkataramanan. Estimation of low-rank matrices via approximate message passing. The Annals of Statistics, 19(1), 2021.
[MW23] Andrea Montanari and Yuchen Wu. Posterior sampling from the spiked models via diffusion processes. arXiv preprint arXiv:2304.1144, 2023.
[Pea94] Karl Pearson. Contributions the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185:71-110, 1894.
[Pid22] Jakiw Pidstrigach. basee generative models detect manifolds. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 35852-35865. Curran Associates, Inc., 2022.
[2] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10685-10695, 2022.
[RDN+22] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint NXiv:22044001/55, 2022.
[RV17] Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. 20/7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 85-96. IEEE, 2017.
22] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang. Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gon- tijo Lopes, et al. Photorealistic text-to-image diffusion models with deep language understanding. arXiv preprint arXiv:2205.11488) 2022.
[SDWMG15] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Con- ference on Machine Leurning, pages 2256-2265. PMLR, 2015.
[SE19] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
[SN21] Nimrod Segol and Boaz Nadler. Improved convergence guarantees for learning gaussian mixture models by em and gradient em. Electronic journal of statistics, 15(2):451044544, 2021.
[SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimallsample estimators for spherical gaussian mixtures. Advances in Neural Information Processing Systems, 27, 2014.
[S] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Er- mon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13450 2020.
[Ver] Roman Vershynin. High- fiigh-Dimensioal Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
[VW04] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-88) 2004. Special Issue on FOCS 2002.
13

---

[W]+08] Martin Wainwright, Michael Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1- 305, 2008
[WY22] Andre Wibisono and Kaylee Y. Yang. Convergence in KL divergence of the inexact Langevin algorithm with application to score-based generative models. arXiv preprint 2211.01512 2022.
[XHM16] Ji Xu, Daniel J Hsu, and Arian Maleki. Global analysis of expectation maximization for mixtures of two gaussians. Advances in Neural Information Processing Systems, 29, 2016.
[YYS17] Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence analysis of gradient em for multi-component gaussian mixture. arXiv preprint arXiv: 2017.
[ZLS200] Ruofei Zhao, Yuanzhi Li, and Yuekai Sun. Statistical convergence of the em algorithm on gaussian mixture models. 2020.
14


Reviews:
[{"review_id": "ozLenwfi24", "reviewer": "Reviewer_Egk5", "summary": "Proofs are given for showing that the true mean parameters of Gaussian mixture models (GMMs) with identity covariance matrices can be recovered when using gradient descent to optimize the DDPM objective. It is argued that it is not well understood if score-based models can provably estimate the parameters of the data distributions, which is the objective of this submission. The findings and results are connected to the EM algorithm.", "questions": "* In Sec. 1.2, it would be nice to see a discussion or explanation of why the covariance matrices Id and not $\\sigma^2$I_d. That is, the variance elements would not necessarily equal to one, but the Gaussians would still be spherical. Would your results still hold for this setting? Otherwise, shouldn't the setting itemized in the abstract specify that your results apply to unit-spherical Gaussians?", "limitations": "I had some questions on the assumptions of the parameters of the Gaussians in the GMMs. Otherwise I believe the limitations were addressed.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper attempts contribute with fundamental understanding of diffusion models, focusing on an important class data distributions, GMMs. Diffusion models are clearly of high interest to the NeurIPS community and theoretical results of the type provided in the submission could be significant, or of interest to researchers in the field. \n\nThe literature review is thorough and it appears that the topic of the paper is original, in the sense that the theoretical results do not exist in the literature. It is good that the results are connected to other well-studied algorithms, like the EM algorithm.\n\nThe clarity of the purpose of the submission benefits from the bullet list in the abstract.", "weaknesses": "The structure of the submission is unfortunately not very strong, which makes the arguments in the submission tedious to follow. I am missing sufficient background to the power method and the EM algorithm, a background of the former is not provided, and there is no conclusion section or discussion. Such sections would help the reader to understand the contributions of the submission in terms of the lingo and terminology introduced in the paper. Also, it would give the paper a more concise ending, as it now ends with a proof sketch. \n\nMy score of the paper is mainly based on the structure and quality (presentation) of the paper, which I believe is below acceptable for a NeurIPS paper. However, my confidence level is relatively low as theoretical results for diffusion/score-based models is slightly outside my area of expertise. That is, am not sure how significant the results in the submission are--hopefully other reviewers can aid to evaluate this part. Nonetheless, as it stands, my opinion is that the inadequate presentation of the work outweighs (my understanding of) the significance of the results in the presented work.\n\nTo help the authors in the revision of the paper, I below enumerate some suggestions on how to improve the structure and some of my concerns. I hope they are helpful.\n\n* GD is frequently used to denote gradient descent. But it is not defined as an acronym in the abstract nor in the paper. I inferred the definition of GD only after reading quite a bit of the paper. This confused me, as I did not know what GD referred to. I suggest introducing the acronym in the abstract and write gradient descent (GD) in line 35 where GD is first used.\n\n* In line 35, what is the meaning of a \"natural\" data distribution? I could find an explanation of it and I could not derive what it ought to specify. Is \"natural\" an important distinction?\n\n* Sentences like \"we use this as our student network architecture when running gradient descent.\" (line 146) gives me expectation that some experiments have been carried out where these architectures have been used. As there are no experiments in the paper, this confused me. A potential reformulation could be \"one could use\" as you have in fact not used it. Similar confusion arouse at line 162 \"we run projected gradient descent\".\n\n* Related to the previous bullet, why not run experiments to validate the results on synthetic data? \n\n* Is the heading in line 164 supposed to be a paragraph or a section? Now it is an empty paragraph.\n\n* I am not familiar with the power method and no background or explanation of it is given in the paper. I think this needs to be included to make the paper more stand alone.\n\n* Projected gradient descent is introduced after the background section without proper explanation. Is projected gradient descent typically used to train diffusion models?\n\n* The EM algorithm is central to the findings in the paper. As such, I think it should be more carefully explained. Especially, including a Background section earlier than Sec 1.3 would strengthen the paper and make it easier to follow the arguments made in the earlier sections. For instance, \"We show that the gradient descent in this \"small noise\" regime corresponds to the EM algorithm\" in line 158 would become easier to understand.\n\n* In the setting where $K=2$, is there an additional, consistent assumption that the means of the Gaussian are centered around the origin? I.e. the means are $-\\mu^*$ and $\\mu^*$? I read the section above Eq. (2) as this being an example of a GMM \"for the sake of intuition\". But then this parameter setting is specified again in Eq. (13). Does this mean that the results in the paper are constrained to Gaussians centered around the origin? If so, this should be specified in the relating theorems? I.e. Thm 1 and 2 and their formal counterparts.\n\n**Minor issues** \n* line 46: the flow if the sentence could be improved by using punctuation after \"$d$, the dimension.\"\n* The acronym EM is most often used without definition. Although this is more clear what it refers to, \"expectation-maximization\" is spelled out in other parts of the paper. I suggest introducing the definition and sticking to it throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful suggestions. We will make sure to include a discussion/conclusion section in the revision. Here we address their other points one-by-one. Given that it is straightforward to fix all of these concerns in a single round of cosmetic edits, and given that the only non-expository weakness mentioned stems from a misunderstanding about the generality of the origin-centering assumption, we don’t think that such a low score is appropriate and respectfully urge the reviewer to reconsider.\n\n**Weaknesses:**\n\n- *Confusion on GD:* In the updated draft, we will clarify that GD stands for gradient descent.\n- *The meaning of a \"natural\" data distribution:* The question in line 35 is intended to be informal, and in ML theory, “natural” is a commonly used term to signify a generative assumption which is “simple” and “non-contrived.” Given that Gaussian mixtures are one of the most studied distributions in the literature for provable algorithms for distribution learning, “natural” is a reasonable term in this context.\n- *Expectations about the experiments on the student network:* We are happy to incorporate the reviewer’s suggestions to avoid this confusion, but note that in theoretical works, it is standard to say “we perform algorithm X to solve task Y” without the literal implication that experiments will be done. For instance, if a paper says “we will maintain the following data structure while processing the edges of graph G,” it need not mean that they will carry out an experiment in which they implement said data structure.\n- *Experiments*: see below for a summary of the experiments we performed for the rebuttal, as well as a separate discussion on the role of experiments in theoretical works\n- *Is the heading in line 164 a paragraph or a section?:* It is a paragraph as intended. We will reformat the bolded subheaders beneath it as underlined or italicized subheaders to minimize confusion.\n- *Background on power method:* The power method is taught in introductory algorithms and linear algebra classes. We will add a paragraph reminding the reader of the simple intuition (to compute the top eigenvector of a matrix, repeatedly multiply a vector by the matrix, and the result will converge in angular distance to the top eigenvector).\n- *Background on projected gradient descent:* It is very common in deep learning to optimize with an L1/L2 regularizer on parameters, which implicitly plays the role, in a sense that can be made formal, of a projection step. Given that regularized gradient descent is thus a standard algorithm not just in diffusion modeling but in machine learning more broadly, and furthermore given that we explicitly state in Line 162 the set that we are projecting to, it is unclear what other aspects of projected gradient descent should be explained at that point in the text.\n- *Additional background on EM algorithm:* EM for Gaussian mixtures is taught in introductory machine learning at the undergraduate level. We will add some additional details to the paragraph starting in Line 58. Namely, we will include a centered equation reminding the reader of the form of the “M” step in the EM algorithm, and then elaborate on what we mean when we say that the gradient updates when minimizing the DDPM objective are performing this M step.\n- *Origin-centered mixtures of Gaussian:* We refer the reviewer to Eq. (13) where we make this assumption clear (When we said “For the sake of intuition” in Section 1.2, we meant that we focus on *K = 2* for the sake of intuition, not that we focus on origin-centered means). We stress that the origin-centered mean assumption is not a “constraint”, it is actually without loss of generality as mentioned in Line 192, 193 (just after Eq.(13)). One can always estimate the overall mean of the data distribution to high accuracy from samples and then recenter the dataset accordingly; one can check that the steps of our proof are robust to the error in estimating this mean. \n\n**Minor issues:**\n\n- We will use the suggested punctuation\n- We will make clear early on that EM stands for expectation-maximization\n\n**Questions:**\n- Yes, our results still hold for this setting. The reason is that if you scale the dataset by a factor of 1/sigma, you reduce it to the unit-spherical case. It is however true that if the covariance matrices have different variances across the different mixture components, then our analysis does not yet apply. Note however this should not be viewed as a weakness per se: it is common for works to focus on the equal covariance setting (see e.g. the state-of-the-art works of [Segol-Nadler ‘21] and [Liu-Li ‘22]). We will make this clear in the revision and reword the abstract accordingly.\n\n**Experiments:**\n- We have performed a set of numerical experiments to validate our theory, as part of the rebuttal. Specifically, it shows that the constant factors in our analysis are benign so that our convergence guarantees are practical, and it demonstrates the utility of training using the DDPM objective in both high- and low-noise regimes.\n- That being said, we would like to make a broader point. Please note that this is a theory paper. The main contributions are a set of mathematical theorems.  Experiments are orthogonal to the thrust of our work, and indeed orthogonal to the thrust of recent *theoretical* developments for diffusion models. The field of diffusion generative modeling is inundated with experimental works, and it is well-known that the algorithms used in this field are empirically successful. In the context of our work, there is not much to validate experimentally that would add to the empirical literature. \nIn contrast, our theoretical understanding of diffusion models is seriously lacking, apart from a handful of works written over the last year which we have cited in Section 1.1. The whole point of our work is to give a rigorous theoretical justification for why these existing algorithms are effective.\n"}, {"review_id": "RPz8mfNe46", "reviewer": "Reviewer_R4kZ", "summary": "This paper presents a new approach to learning Gaussian mixture models using the denoising diffusion probabilistic model (DDPM) objective. The authors provide a 2-part algorithm that allows one to reconstruct the parameters of a mixture of Gaussians. The first part of the algorithm uses gradient descent with \"high nose\" scale of $t$ and random initialization to learn parameter, correlated to the true ones, while the second step refines these parameters, using those obtained in the previous step as a \"warm start\" and using the small $t$ mode.", "questions": "1. Have you performed numerical experiments to check the convergence of the method and compare it with other approaches?\n\n2. In reality, for some model numerical parameter values, how many iterations are needed for power iteration described in (6)--(7) to converge?\n\n3. line 246: (Sec. 2.1 with Formal statements) What is \"high probability\"?\n\n\nMinor\n\nWhat authors mean by \"well-separated\" (line 131)\n\nWhat authors mean by _student_ network (line 142)", "limitations": "1. Only rough asymptotic estimates are given. Real constants, which can be in practical experiments are not given, however, they can be large. \n2. The proof for the case of large $t$ (the relation of DDPM to power iteration) is based on an approximate, not exact, formula (6) and thus it is not conclusive.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper gives the relation between gradient descent with loss from denoising diffusion probabilistic model and a) power iteration in case of large $t$ and b) Expectation-Maximization algorithm in case of not large $t$.\n\nSome number of theorems and lemmas are proved.", "weaknesses": "1. The presentation of the results is weak. The article is poorly structured, with no \"conclusions\" or \"discussion\" section. A lot of fuzzy language. Such wording may be acceptable in informal descriptions of results, but even in the section with formal descriptions phrases like \"with high probability\" are used. The main text of the article in the main pdf file differs from the version in the file with the Appendix.\n\n2. The matrix $(1-\\eta r)I +2\\eta \\mu^*_t {\\mu^*_t}^T$ has eigenvalues close to one. The largest of them (for which the eigenvector in power iteration (6) is sought) differs only by an additional term proportional to $e^{-2t}\\eta$. This term is very small, since by definition $t$ in this case is large, and the learning rate $\\eta$ is usually chosen very small ($\\sim10^{-2}-10^{-4}$). In such a situation power iteration can converge to an arbitrary vector. Moreover, as expression (6) is an approximation, this convergence is even more uncertain.\n\n3. There are no numerical experiments, even for the simplest cases. However, the real convergence of power iterations with the matrix (7) is not obvious.\n\n 4. There is no separate  comparison with other, including state-of-the-art, approaches to recovering Gaussian mixture parameters. Although paper has rather large literature review section.\n\n\nMinor:\n\nline 156 typo: \"poweri iteration\"\n\n\"EM\" abbreviation is deciphered only on page 6, but widely used starting from the abstract.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and we address all the points raised by the reviewer. As the main weakness mentioned by the reviewer on the convergence of power method seems to be due to some misunderstanding and is thoroughly addressed both through theory and experiments that we performed for the rebuttal, we ask the reviewer to reconsider their score. \n\n- **Fuzzy language with informal phrases like \"with high probability\":** It is completely standard in the literature of learning theory to use “with high probability” to denote “with failure probability inverse polynomial in d” (for example, see Daskalakis et al. 2017, Diakonikolas et al. 2020, Liu-Li ‘22). The reviewer has not provided any other instance of “fuzzy” language, and we disagree that aspects of the paper are “fuzzy”. We will also make sure to include a conclusions section, but apart from this, we respectfully disagree that the presentation of the results is “weak” or “poorly structured.”\n- **power iteration can converge to an arbitrary vector** We strongly disagree that the convergence is uncertain. If a matrix’s top eigenvalue is larger than the others by some multiplicative $1+\\tau$, then in $O(1/\\tau)$ power iterations we will converge to the top eigenvector (see e.g. https://en.wikipedia.org/wiki/Power_iteration). So even if $\\tau$ is small, as long as $\\tau$ is inverse polynomial in the relevant parameters (which is the case for our $\\tau = e^{-2t}\\eta$, as $t$ is only logarithmic and $\\eta$ is inverse polynomial), the complexity of power iteration is still polynomial. Furthermore, in Lemma 9 (page 7) and in Lemma B.3, we make completely precise the approximation error in (6) and rigorously show that this error is sufficiently low order that it does not affect convergence. We, therefore, encourage the reviewer to seriously reconsider their view that our proof is “inconclusive.”\n- **Numerical experiments and numerical convergence of power iterations:** \n   - We have performed a set of numerical experiments to validate our theory, as part of the rebuttal. Specifically, it shows that the constant factors in our analysis are benign so that our convergence guarantees are practical, and it demonstrates the utility of training using the DDPM objective in both high- and low-noise regimes. \n   - That being said, we would like to make a broader point. Please note that this is a theory paper. The main contributions are a set of mathematical theorems.  Experiments are orthogonal to the thrust of our work, and indeed orthogonal to the thrust of recent *theoretical* developments for diffusion models. The field of diffusion generative modeling is inundated with experimental works, and it is well-known that the algorithms used in this field are empirically successful. In the context of our work, there is not much to validate experimentally that would add to the empirical literature. In contrast, our theoretical understanding of diffusion models is seriously lacking, apart from a handful of works written over the last year which we have cited in Section 1.1. The whole point of our work is to give a rigorous theoretical justification for why these existing algorithms are effective.\n- **Comparison of results with other state-of-the-art approaches:** We make a comparison to the most relevant state-of-the-art approaches in the introduction section in Lines 52-55 and in the Related Work section in Lines 104-105. We also state the state-of-the-art EM guarantee of Segol and Nadler which clearly matches our guarantee, though we will add some words in the revision making this clear. In the last paragraph of Related Work, we also mention works on “general mixing weights and covariances” which is clearly more general than our setting. Again, we will add some words in the revision to make this clear.\n- **Asymptotic analysis and constant factors:** Please recall this is a theory paper where it is standard to use asymptotic analysis and suppress constant factors. Even the prior theoretical works on the diffusion models use asymptotic analysis (e.g., Lee et al. 2023, Chen et al. 2023a, b). And as the experiments we performed for the rebuttal make clear, the constant factors are benign.\n\n**Minor comments:**\n- By well-separated we mean that the means are separated by some absolute constant. We also handle the case of inverse polynomial separation.\n- Student network refers to the network that we train. This “student-teacher” terminology is standard in the deep learning theory literature, where the “teacher” is the ground truth network generating the examples (in our case, it is the true score function), and the “student” is the network whose parameters are optimized via gradient descent to minimize some training objective.\n"}, {"review_id": "fFyYihyMqL", "reviewer": "Reviewer_NKbJ", "summary": "This paper shows that the diffusion model can be used to learn mixtures of Gaussians. In particular, they show that GD on the DDPM objective can efficiently recover the ground truth parameters for both mixtures of two spherical Gaussians and mixtures of $K$ spherical Gaussians under different assumptions. The key ingredient in their analysis is the observation that there is an inherent connection between score-based models and EM, spectral methods.", "questions": "Please see the weakness part.", "limitations": "Please see the weakness part.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a very interesting paper and can be served as a starting point to further explore the power of DDPM from the optimization perspective. Firstly, mixtures of Gaussians are one of the most important and fundamental distribution families of interest, and showing DDPM works for mixtures of Gaussians can be very strong support for its solidness. On the other hand, different from prior work, this work does not require the existence of an oracle for score estimation. Instead, they show that empirical estimation suffices. Lastly, the connection between DDPM and the classic algorithms in this field, i.e., EM and spectral methods can be of independent interest. This might be used to show the effectiveness of DDPM.", "weaknesses": "My main concern is that the model and algorithm are a little bit artificial.\n\n- First, the model used for mixtures of two Gaussians is $s_{\\theta_t}(x)=\\tanh \\left(\\mu_t^{\\top} x\\right) \\mu_t-x$. Here $-x$ can be understood as the residual connection and $\\tanh(\\cdot)$ is also a reasonable activation. However, using the same weight $\\mu_t$ for both layers is a little bit restrictive. A far more general model is $s_{\\theta_t}(x)=\\tanh \\left(u_t^{\\top} x\\right) v_t-x$. My conjecture is that it is not hard to extend the current result to this \"asymmetric\" version. The reason is that there might exist some kind of balanceness between $u_t$ and $v_t$ so that they are roughly the same. \n\n- Second, the authors consider two noise regimes: first they use a large noise and run several iterations of GD, then they switch to the small noise regime. This mimics the practical noise regime. However, in practice,  people decrease the noise level in a continuous manner, like exponentially decaying. Is it possible to adapt the current analysis to a more realistic noise-decaying regime?\n\nSome technical issues: \n- When claiming high noise regime, only the upper bound is provided, see line 252. I think there should be also a lower bound for $t_1$. \n\nLast question: The result in this paper only show that DDPM is as good as EM and spectral methods. A far more important question is why empirically DDPM outperforms these methods. Can DDPM outperforms the existing methods for the mixtures of Gaussians in some aspects like computational time?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging words and for finding our paper very interesting. Here we address the questions raised, one of our main points being that while the points raised are indeed great directions for future work, we would like to underscore that prior to our work, there were no provable score estimation results in the theoretical literature on distribution learning. We thus encourage the reviewer to reconsider their score and the significance of our contributions in this context.\n\n**Decoupling the two layers' weight in the score function**\n\nIt’s an interesting question. It should not be hard to show some kind of layerwise training guarantee at least: if the output layer weights are fixed at random initialization and the input layer weights are trained, one should be able to show that the input layer weights converge to the ground truth because of similar power iteration / EM - like considerations, after which if we train the output layer weights, then this is simply a linear problem and we will likewise converge to the ground truth. Extending this beyond layerwise training will require more work. Nevertheless, we find that the novelty of showing that *any* gradient-based algorithm can be used for provable score estimation in a nontrivial high-dimensional distribution learning context perhaps outweighs the strengths of specific architectural choices, unless if the architecture is chosen to be much more generic, e.g. a general feedforward O(1)-layer network. This would, however, be outside the scope of our work.\n\n**Continuously decaying the noise**\n\nThe reviewer is correct that our two-stage algorithm is a little different from how DDPMs are trained in practice, but the objective used in practice is actually a little different from what the reviewer describes, and we feel that understanding the former, while of great interest, is also well out of the scope of what is currently possible in the literature on provable score estimation.\n\nFor context, in diffusion models, one trains a score network $s(x_t,t)$ which accepts as input (an embedding of) a noise level parameter $t$ and an image $x_t$ at noise level $t$, and outputs a denoised image. To sample an image, one then starts with a fully noisy, e.g. Gaussian, seed and runs a discretization of a suitable reverse SDE/ODE that iteratively applies the score network along some noise schedule as the reviewer suggests.\n\nWe caution that this should *not* be confused with the following: train the score network by running GD with respect to the DDPM objective at noise level t_1, then with respect to the DPPM objective at noise level t_2, etc.\n\nInstead, how one trains $s(x_t,t)$ is by running GD on a DDPM objective which is averaged across DDPM objectives at different noise levels. See e.g. Eq. (8) in https://arxiv.org/pdf/2206.00364.pdf. There is flexibility in how to choose the distribution D over noise levels. Perhaps what the reviewer had in mind is that D in practice is a continuous distribution over noise levels, whereas our analysis, as written, pertains to D which is discrete. We agree that the former is a very interesting and practically relevant direction for study. It would however require first defining a suitable architecture which incorporates a time embedding. This already takes us quite far from the domain of settings where we can hope for an end-to-end analysis of gradient-based methods, and given that nothing was known about provable score estimation for distribution learning prior to our work, we think it is fair to regard this as a topic much further down the line in terms of things that we can currently analyze.\n\t\n**Lower bound for $t_1$** \n\nYes, this is a typo that we will fix in the revision. The noise scale t_1 should be $\\Theta (log d)$. The lower bound on noise scale $t_1$ is used for obtaining equivalence between the power method and Gradient Descent on the diffusion model (See Lemma B.3) because the approximation error between gradient descent on the DDPM objective and power method depends polynomially on \\norm{\\mu_t} and \\norm{\\mu_t^*}. Additionally, the parameters at a noise scale t is $\\mu_t = \\mu \\exp(-t)$ and when t is $\\Omega (\\log d)$, then $\\| \\mu_t \\|$ is $O(1 / \\mathrm{poly}(d))$. Similarly, we also obtain $\\|\\mu_t^*\\|$ to be $O(1 / \\mathrm{poly}(d))$ for $t = \\Omega (\\log d)$. Therefore, the approximation error between the power method and Gradient Descent on the DDPM objective becomes small $O(1/poly(d))$. \n\n**Outperforming other methods:**\n\nWhile we think it is already a compelling contribution to even be able to analyze gradient descent on the DDPM objective, we stress that one of the key takeaways of our work is precisely that our algorithm gets the best of both worlds of power method and EM. Note that the main limitation of EM is that it does requires a warm initialization in order to converge, and the main limitation of power method is that while it can converge from random initialization, it does not converge very quickly even when it is in a neighborhood of the ground truth. In contrast, we have shown that by varying the noise level with which one defines the DDPM objective, we get the advantages of both algorithms: 1) the large noise regime gives us the global convergence properties of power method, and 2) the small noise regime gives us the fast local convergence properties of EM. In fact we see precisely this phenomenon in our second set of experiments."}, {"review_id": "x9IApWflP3", "reviewer": "Reviewer_6LCQ", "summary": "The authors propose to leverage the DDPM objective to learn Mixtures of Gaussians and prove that gradient descent on the DDPM objective can efficiently recover the ground truth parameters of the mixture model under certain assumptions.", "questions": "Please address the questions in the above ``Weaknesses.''\n\nMinor.\n\n(1) \"poweri\" in Line 156 is a typo.\n\n(2) \"Gaussian\"  in Line 214 is a typo.", "limitations": "N/A", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "Several interesting insights are revealed, such as those associated with Eq. (5) and those related to large/low noise levels.", "weaknesses": "(1) The novelties of the proposed method over existing works are not clearly stated. For example, in Line 52, it's stated that ``EM achieves the quantitative guarantees of Theorems 1 and 2 Daskalakis et al. (2017); Xu et al. (2016);...'' So what are the advantages of using the DDPM objective?\n\n(2) It's not clear how practical the proposed method is for general Mixtures of Gaussians with $K\\ge 3$ components, where a global optimum is generally impossible for maximizing the loglikelihood [1]. Note that a contradiction between the presented paper and [1] might emerge here, because minimizing the DDPM objective is equivalent to maximizing a hierarchically constructed lower bound of the loglikelihood [2]. \n\n(3) No empirical experiments are given.\n\n[1] Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J Wainwright, and Michael I Jordan. Local maxima in the likelihood of Gaussian mixture models: Structural results and algorithmic consequences. Advances in neural information processing systems, 29, 2016.\n\n[2] Calvin Luo. Understanding Diffusion Models: A Unified Perspective. Arxiv, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address them point-by-point. We believe that the criticisms stem from misunderstandings about the scope of what is known in this literature and its relation to our work. We have also provided numerical experiments in the rebuttal, though we also clarify below a broader point about the role of experiments in theoretical works. Given that the stated concerns can all be addressed, we strongly urge the reviewer to reconsider their score.\n\n**EM vs DDPM:**\n- Our work already points to one sense in which DDPMs outperforms EM. The latter is known to suffer from poor global convergence, and provable guarantees for $K > 2$ require a warm start. In contrast, our theory suggests that the different noise regimes of DDPM inherently allow for a two-stage algorithm in which the high-noise regime leads to a spectral initialization close to the true parameters, and the low-noise regime mimics EM from this warm start. **Furthermore, we see this advantage borne out in the numerical experiments performed for the rebuttal.**\n- That said, note that the question of what advantages DDPM affords over EM is very much outside of the scope of our work. We re-emphasize that prior to our work, there were *no known end-to-end* provable guarantees for using the DDPM objective for distribution learning, and one of the key conceptual contributions in our paper is to establish a formal connection between minimizing the DDPM objective and running EM. This connection is highly nontrivial, and given the significant attention that EM has received in the last five decades and the significant recent attention that DDPMs have received, we believe this will be of strong interest to the statistics and generative modeling theory communities moving forward.\n\n**Maximizing log likelihood:**\n- We believe the reviewer may be somewhat confused. The result of Jin et al. says that 1) there are bad local maxima for the log likelihood, and 2) EM with *random* initialization will converge to bad critical points with high probability for $K > 2$ components. 1) is irrelevant to our paper, and 2) does not contradict anything in our paper, because in the $K > 2$ case, we only consider EM initialized in a neighborhood of the true parameters. In fact, as discussed above, we expect that a more sophisticated analysis of DDPMs in which we combine both high- and low-noise regimes will allow us to obtain a (non-EM-based) initialization close to the true parameters via the connection to power method in the high-noise regime, and then use EM-like updates in the low-noise regime to refine our estimate. \n\n- In any case, whether or not DDPMs exhibit global convergence for $K > 2$ is well outside the scope of our paper: we are giving the *first ever* provable guarantees for DDPMs for Gaussian mixtures. In contrast, it is a major open problem in the distribution learning literature to show that *any* algorithm not based on method of moments can learn for $K > 2$ without a warm start.\n\n**Experiments:**\n\n- We have performed a set of numerical experiments to validate our theory, as part of the rebuttal. Specifically, it shows that the constant factors in our analysis are benign so that our convergence guarantees are practical, and it demonstrates the utility of training using the DDPM objective in both high- and low-noise regimes.\n- That being said, we would like to make a broader point. Please note that this is a theory paper. The main contributions are a set of mathematical theorems.  Experiments are orthogonal to the thrust of our work, and indeed orthogonal to the thrust of recent *theoretical* developments for diffusion models. The field of diffusion generative modeling is inundated with experimental works, and it is well-known that the algorithms used in this field are empirically successful. In the context of our work, there is not much to validate experimentally that would add to the empirical literature. \n- In contrast, our theoretical understanding of diffusion models is seriously lacking, apart from a handful of works written over the last year which we have cited in Section 1.1. The whole point of our work is to give a rigorous theoretical justification for why these existing algorithms are effective."}]

Author rebuttal:
We thank the reviewers for their comments, which we have responded to individually. Here we note that we also performed numerical experiments (see attached pdf) to demonstrate that 1) the **constant factors in our analysis are quite benign**, and 2) as predicted by our theory, **training with the DDPM objective at different noise scales has a tangible benefit over power iteration and EM**, namely it gets the best of both worlds of power iteration and EM: global convergence from random initialization for the former and fast local convergence for the latter. 

*In our individual responses to reviews, we also included some broader comments on the role of experiments in theory, especially in the theory of generative modeling where there is a wealth of empirical works and dearth of theoretical understanding.*

Meta-review: The decision on this paper runs contrary to the the majority of the reviewers comments, after a discussion between AC and SAC. 

The AC's opinion is that the paper is clearly above the bar for NeurIPS. It shows a very nice connection between the optimization dynamics for DDPM (Denoising Diffusion Probabilistic Models) and EM/power method (in different regimes for the amount of noise), when the underlying data distribution is a mixture of Gaussians in the well-separated regime. 

Of course, the well-separated regime of mixture of Gaussians is the "easy" regime for the parameter learning problem, and classical strategies like EM + spectral initialization are long known to work. The purpose of the paper isn't to give new algorithms for this problem. Instead, the goal is to understand training dynamics of popular score-based/diffusion-based objectives. 

While there's been a recent flurry of work trying to understanding the required discretization and training accuracy to achieve a good sampling quality (e.g. Block et al '22, Chen et al '23, Lee et al '23), as well as statistical properties of score-based losses (Koehler et al '23, Pabbaraju et al '23, Qin et al '23), training dynamics are challenging to analyze in the presence of non-convexity for any loss, and diffusion/score-based methods are very new territory. As such, the paper will be interesting to a large part of the theory of diffusion models community.
Decision: Accept (poster)