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 $Ω(\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.
Paper
Similar papers
Peer review
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.
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? (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]. (3) No empirical experiments are given. [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. [2] Calvin Luo. Understanding Diffusion Models: A Unified Perspective. Arxiv, 2022.
Questions
Please address the questions in the above ``Weaknesses.'' Minor. (1) "poweri" in Line 156 is a typo. (2) "Gaussian" in Line 214 is a typo.
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
1 poor
Presentation
3 good
Contribution
2 fair
Limitations
N/A
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.
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. - 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. - 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? Some technical issues: - 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$. Last 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?
Questions
Please see the weakness part.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Please see the weakness part.
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.
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$. Some 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. 2. 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. 3. There are no numerical experiments, even for the simplest cases. However, the real convergence of power iterations with the matrix (7) is not obvious. 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. Minor: line 156 typo: "poweri iteration" "EM" abbreviation is deciphered only on page 6, but widely used starting from the abstract.
Questions
1. Have you performed numerical experiments to check the convergence of the method and compare it with other approaches? 2. In reality, for some model numerical parameter values, how many iterations are needed for power iteration described in (6)--(7) to converge? 3. line 246: (Sec. 2.1 with Formal statements) What is "high probability"? Minor What authors mean by "well-separated" (line 131) What authors mean by _student_ network (line 142)
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
1 poor
Contribution
2 fair
Limitations
1. Only rough asymptotic estimates are given. Real constants, which can be in practical experiments are not given, however, they can be large. 2. 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.
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.
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. The 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. The 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. My 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. To 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. * 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. * 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? * 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". * Related to the previous bullet, why not run experiments to validate the results on synthetic data? * Is the heading in line 164 supposed to be a paragraph or a section? Now it is an empty paragraph. * 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. * Projected gradient descent is introduced after the background section without proper explanation. Is projected gradient descent typically used to train diffusion models? * 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. * 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. **Minor issues** * line 46: the flow if the sentence could be improved by using punctuation after "$d$, the dimension." * 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.
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?
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
1 poor
Contribution
3 good
Limitations
I had some questions on the assumptions of the parameters of the Gaussians in the GMMs. Otherwise I believe the limitations were addressed.
Response to rebuttal
First, I want to thank the authors for their rebuttal, they have clearly worked hard to address my comments. I also acknowledge that I have taken part of the submitted pdf, thanks for the complementary experiments. However, I disagree that the presentation edits are "straightforward" and adding one or two sections cannot be regarded as a "single round of cosmetic edits". To use the terminology of the NeurIPS reviewer guidelines (https://neurips.cc/Conferences/2023/ReviewerGuidelines#:~:text=well%2Dwritten%20summary.-,Strengths%20and%20Weaknesses,-%3A%20Please%20provide) *Quality: Is this a complete piece of work or work in progress?* I still think this is a work in progress, a view I appear to share with the other reviewers. *Clarity: Is the submission clearly written? Is it well organized? Does it adequately inform the reader?* I am sorry to conclude that these criteria are not met. Even if the promised revisions will certainly improve the clarity of the paper, I cannot increase my score to an acceptance level before reading the revised version of the paper with the added section(s). Instead I will increase my score to 4, displaying my appreciation of the efforts put in during the rebuttal, will keeping my low confidence score. I hope the authors will understand my reasoning. I want to be clear that I appreciate the improvements of the submission that have been made during the rebuttal period, and I applaud the authors for their efforts. By incorporating the feedback provided by the reviewers, a resubmission of the work will be competitive for acceptance in a future conference proceeding.
I thank the authors for their answers and for additional experiments. **1. About the style of the paper.** The article is missing sections such as "Background", "Problem Statement", "Conclusion", "Discussions", comparison with other algorithms, etc. Of course, they don't all have to be at the same time. But the presented structure of the article is extremely difficult to understand the main ideas (which are quite simple). To correct the structure, to introduce correct definitions, to correct holes in the proofs, etc., requires substantial revisions that go far beyond the minor revisions allowed at this stage of reviewing the paper. **2 About the convergence of power iteration:** > (see e.g. https://en.wikipedia.org/wiki/Power_iteration). a. The Wikipedia article you quoted says > If we assume $A$ has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector $b_0$ has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence $(b_k)$ converges to an eigenvector associated with the dominant eigenvalue. Without the two assumptions above, the sequence $(b_k)$ does not necessarily converge. Your paper is positioned as a theoretical paper, but you have not checked these two conditions given, which are necessary to prove the convergence of power iteration. The check of the second condition (about the non-zero component) can be omitted, since it is always possible to take several random vectors as an initial approximation. But the condition that the first eigenvalue must be much larger than the others is crucial. The argument about asymptotics here cannot replace a rigorous study, since the numerical coefficients in this asymptotics are not known in advance, and it may turn out that the first eigenvalue is not sufficiently different from the others for convergence of power iteration. > If a matrix’s top eigenvalue is larger than the others by some multiplicative $1 + \tau$, then in power iterations we will converge to the top eigenvector b. Moreover, you don't just have $1 + \tau$. You have $1 + \tau + \epsilon$, where $\epsilon$ appears due to approximate equalities (6)--(7). Is it possible that $\epsilon < 0$, and furthermore that $1 + \tau + \epsilon<1$? Theoretically, it is possible, and in this situation the convergence of power iteration will be to an arbitrary vector. The authors do not prove that this situation is excluded as there is no explicit comparison of these two values in the __main text__ of the paper. (Lemma 9, which turned into Lemma 8 in supplementary file, contains only the expression $poly(\frac1d)$ in the right-hand side, which can be arbitrary large when $d$ is fixed.) **Minor:** >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. Although the paper is positioned as theoretical, it describes a practical algorithm. If it turns out that in practice the number of iterations of such an algorithm will be equal to $10^9$ at real parameter values, but it will be "asymptotically small", the practical value of such an algorithm is insignificant >By well-separated we mean that the means are separated by some absolute constant. It's still not clear how "well-separated" differs from just "separated" (or "poor separated", etc.). > Student network refers to the network that we train. This “student-teacher” terminology is standard in the deep learning theory literature The concept of "student network" is connected with the concept of "teacher network". You answered that you do not have a teacher network as a network. Moreover, the words "teacher network" do not even appear in the paper. Thus, the concept of "student network" is misleading. **Conclusion.** I think, that each of my two arguments above (about the structure of the paper and about the lack of justification for the convergence of power iteration) is separately a reason to reject the paper.
Response to Reviewer's Comment on the Rebuttal
> you have not checked these two conditions given The first condition directly follows from the eigenvalues of the matrix $Id (1 - 3 \eta || \mu_t ||^2 ) + 2 \eta \mu_t^* \mu_t^{\ast T}$ and is written in Lemma B.5. The first eigenvalue (corresponding to $\mu_t^*$) is $(1 - 3 \eta || \mu_t ||^2 ) + 2 \eta || \mu_t^* ||^2$, and the rest of the eigenvalues are $(1 - 3 \eta || \mu_t ||^2 )$. The second condition (written in Lemma B.4) is a direct consequence of the anti-concentration of the Gaussian random variable and does not require taking several random vectors as an initial approximation as mentioned by the reviewer. > Is it possible that $\epsilon < 0$, and furthermore that $1 + \tau + \epsilon < 0$? Theoretically, it is possible, and in this situation the convergence of power iteration will be to an arbitrary vector. No, $\epsilon$ is the approximation error when comparing gradient descent on the DDPM objective to the power method and it cannot be negative. We have also proved in Lemma B.5 and Lemma B.6 that the approximation error is sufficiently small such that it does not disturb the convergence of the power method. It is simply incorrect to say we do not carefully keep track of these issues. > contains only the expression $poly(\frac{1}{d})$ in the right-hand side, which can be arbitrarily large when $d$ is fixed. The parameter $d$ is never fixed. For decades, $d$ has been the key asymptotic parameter of interest when learning mixtures of Gaussians. For example, if the failure probability of an event is $O(\frac{1}{d})$, then the failure probability of that event is treated as small (See cited literature Daskalakis et al. 2017, Diakonikolas et al. 2020, Kwon et al. 2020, Liu-Li ‘22). The reason is that in the regime where $d$ is a fixed constant, all of the learning problems considered are trivial: in this case because $d = O(1)$, brute-force enumeration over an epsilon-net suffices. > It's still not clear how ‘well-separated’ differs from just ‘separated’. We consider two regimes of separation in the paper for mixtures of two Gaussians. 1) the centers are separated by absolute constant or 2) the centers are separated by $poly(1/d)$. By well-separated centers, we mean the centers separated by an absolute constant and by poorly-separated centers, we mean the other case. To summarize, we strongly disagree with the reviewer’s repeated claims that there are “holes in the proof”, “the proof is based on an approximate formula” and “is not conclusive”. We have answered all the questions raised by the reviewers and are happy to discuss in further detail.
> No, $\epsilon$ is the approximation error when comparing gradient descent on the DDPM objective to the power method and it cannot be negative. This doesn't follow from anywhere in the text of the article. I'm not sure it is true. There is no clear justification for this fact. >We have also proved in Lemma B.5 and Lemma B.6 There are not even references to these Lemmas in the text of the main article. It is difficult for the reader to understand which lemma in the extensive appendix to look for in order to prove this or that fact. > we strongly disagree with the reviewer’s repeated claims that there are “holes in the proof” By holes in the proof, I meant that, for example, the inequality under discussion $1+\tau+\epsilon > 1$ is not explicitly stated or proved in the text of the paper (which is necessary to prove convergence of power iteration). I admit that it is true, but only asymptotically, i.e. at some combination of parameters $d$, $t$ etc. The specific conditions under which this inequality is true are not specified. Thus, this paper does not meet the criteria of rigor required for theoretical papers and requires additional research.
> I'm not sure it is true. There is no clear justification for this fact: The reviewer appears to be worried about whether the power iteration matrix with eigengap $\tau$ still has an eigengap after we replace it with an approximate version. This is definitely not an issue in our proof because we prove that the approximation error is always significantly smaller than the eigengap when $t=O(\log d)$ (See lines 576 and 583 of Lemma B.5). > the inequality under discussion $1 + \tau + \epsilon > 1$ is not explicitly stated…. The existence of the eigengap of the power iteration matrix with the approximation can not be made precise by just proving $1 + \tau + \epsilon > 1$ because $1 + \tau$ is the *ratio* of first and second eigenvalues and on high level, both eigenvalues will be replaced with an approximate version. The actual steps needed to make precise that the eigengap is preserved are exactly made precise in lines 576 and 583 of Lemma B.5. > at some combination of parameters $d,t$ etc. The specific conditions under which this inequality is true are not specified. The condition under which the approximate power iteration has eigengap is $t = O(\log d)$ because when $t = O(\log d)$, the approximation error is significantly smaller than the eigengap and it has been repeatedly mentioned in section 2.2 (Part 1). If instead the reviewer is concerned that we have not stated the exact constant factors in our big-O notation, we do not agree that this equates to lack of rigor as this asymptotic language is the standard practice in learning theory and theoretical computer science more broadly. If the reviewer’s concern with big-O is instead purely practical, note that our experiments demonstrate that the constant factors in our proofs are not an issue. In summary, we believe that we have addressed all of the primary limitations and weaknesses mentioned by the reviewer in the original review (e.g., no experiments, the proof for the case of large $t$ is based on an approximate formula eq.(6)). We thus respectfully urge the reviewer to reconsider the original score.
Decision
Accept (poster)