Unified Convergence Analysis for Score-Based Diffusion Models with Deterministic Samplers

Authors: Runjia Li, Qiwei Di, Quanquan Gu
Primary area: generative models
Keywords: Diffusion Models, Probability Flow ODEs, Unified Framework, Deterministic Samplers

Abstract:
Score-based diffusion models have emerged as powerful techniques for generating samples from high-dimensional data distributions. These models involve a two-phase process: first, injecting noise to transform the data distribution into a known prior distribution, and second, sampling to recover the original data distribution from noise. Among the various sampling methods, deterministic samplers stand out for their enhanced efficiency. However, analyzing these deterministic samplers presents unique challenges, as they preclude the use of established techniques such as Girsanov's theorem, which are only applicable to stochastic samplers. Furthermore, existing analysis for deterministic samplers usually focuses on specific examples, lacking a generalized approach for general forward processes and various deterministic samplers. Our paper addresses these limitations by introducing a unified convergence analysis framework. To demonstrate the power of our framework, we analyze the variance-preserving (VP) forward process with the exponential integrator (EI) scheme, achieving iteration complexity of $\tilde{O}(d^2/\epsilon)$.
Additionally, we provide a detailed analysis of Denoising Diffusion Implicit Models (DDIM)-type samplers, which have been underexplored in previous research, achieving polynomial iteration complexity.

Decision: accept (poster)
Reviewer scores: 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730539407597

thread_type:
official_review

<thread_object>
creator: reviewer_efqa

<content>
summary:
The paper studies the error of generative models based on deterministic samplers, that is when the backward process is represented by an ODE. Error bounds are presented both for the continuous time and for the discretisation schemes, giving a general result that holds for a wide class of schemes. Several instances of samplers are then considered, giving error bounds for each case.

strengths:
The results in the paper are interesting and cover a good range of algorithms that are of practical interest in generative modelling. The results complement well with the existing literature. 

The main idea, Lemma 4.2, is to bound the derivative of the total variation distance of the laws of the true and approximate backward processes, giving an error that depends on the score and its divergence. As far as I know this is original in this literature.

The presentation is overall clear enough and the goal and results are simple to understand.

weaknesses:
The paper presents several times inconsistent notation, e.g. lines 134-137, 151-154, 349-350, repeated equations (e.g. lines 204 and 206).

Some aspects should be explained better in the paper, for instance: why is Assumption 6.1 used in the application the specific examples of samplers? Or also, can the authors give a clearer idea of what F can be in lines 345-350 for specific samplers? As it is now, the reader has to trust that this function can be found easily, while it would be much better to have one or two examples. 

Several times I had the impression that sentences could be written better, e.g. the statement of 6.5 just to name one, or several times the authors write "Lipschiz" instead of Lipschitz.

questions:
In lines 756-761, why is the TV distance equal to the integral over the entire real line? Can the authors clarify how this is obtained, and also why the absolute value is inside the integral? It cannot be that one of the two densities is larger than the other over the entire domain, else it would not integrate to 1. For this reason I am doubtful of the proof.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730559607529

thread_type:
official_review

<thread_object>
creator: reviewer_pg4x

<content>
summary:
This paper consider the convergence of score-based diffusion with deterministic sampler. The paper starts with a counter-example (using 1d OU process) to show that the problem of convergence may be subtle. The paper then shows a $O(d^2/\varepsilon)$ bound for the convergence, yet another polynomial complexity.

strengths:
The paper provides a systematic/unified study of the convergence of the score-based diffusion models using deterministic or ODE samplers (mostly, EI). The paper is generally well written, and I enjoyed reading it.

weaknesses:
There are several weaknesses of this paper:

1. There have been now a handful of papers, e.g., Chen et al, Li et al., and Huang et al,... providing the polynomial convergence of the diffusion models via ODE/deterministic sampling. It is not too clear how the results in this paper are compared to the existing literature. For presentation, the authors may provide a table to showcase.

2. The authors claimed "polynomial iteration complexity for the VE forward process with DDIM numerical scheme, both of which have been relatively underexplored in the literature. It is known that VE and VP are connected by a reparametrization. In most of cases, it suffices to derive the convergence for VP or VE. This viewpoint is highlighted in the important paper of https://arxiv.org/abs/2206.00364, which the authors fail to cite.

3. The main theorem, Theorem 5.3, basically decomposes the error into three pieces: (1) initialization error, (2) score matching error and (3) discretization error. This idea is not too novel (and of course, the analysis may be involved). The theoretical insight from this paper is not significant, and the contribution of the paper is purely technical.

4. In Theorem 5.3, the authors include a term involving the second order derivatives, which echoes Assumption 6.3. I find this assumption is somewhat too strong.

5. Out of curiosity, I wonder if the authors expect the rate derived in the paper is optimal (especially regarding the dimension $d$).

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730600249791

thread_type:
official_review

<thread_object>
creator: reviewer_ustt

<content>
summary:
This paper investigates score-based diffusion models that utilize deterministic samplers. It introduces a unified framework for convergence analysis by leveraging divergence estimation of the score function. Additionally, the analysis explores the convergence properties of variance-preserving SDEs employing the exponential integrator scheme, along with variance-exploding SDEs in conjunction with the DDIM sampler.

strengths:
The paper is clearly written and presents a novel unified convergence analysis of ODE flows that integrates divergence estimation of the score function. Furthermore, this framework provides fresh insights into the convergence analysis of variance-preserving forward processes employing the exponential integrator scheme, as well as variance-exploding forward processes utilizing the DDIM sampler.

weaknesses:
There are a few typos and missing definitions. Additionally, regarding the assumption of divergence—particularly the assumption of the divergence estimation error—are there any studies that provide estimators for divergence that support the validity of this assumption? How can practitioners verify assumptions like those in Section 6.3 in real-world applications? 

Further details can be found in the Questions section.

questions:
1. **Typos and Missing Definitions**  
   a. Line 176: What is the definition of $q_{\delta}$, and how does the distance between $q_{\delta}$ and $q_0$ depend on $\delta$?  
   b. Assumption 4.1: What is the definition of $Q$?  
   c. Theorem 4.4: What is the definition of $X_{\delta}$, and what is the total variation distance between $X_{\delta}$ and $q_0$?  
   d. Equation (5.2): The definition of the step size $\eta_k$ is missing.  
   e. Line 334: Should $\eta$ be $\eta_k$?  
   f. Line 349:  Should $F$ be $F_t$?

2. **Corollary 6.7**: The paper states, "assuming sufficiently small score estimation error and divergence error." Could you quantify how small $\epsilon_{\text{score}}$ and $\epsilon_{\text{divergence}}$ should be in relation to the target error level $\epsilon$?

3. **Effectiveness of the Framework**: In Section 3, the author discusses results from Section 6.1, suggesting that the dimension dependence is worse than that of the state of the art. Does this arise from limitations within the proposed framework, weaker assumptions, or other factors? Furthermore, the results in Section 6.2 indicate a slow decay for the variance-exploding SDE. Is this limitation due to the proof technique, or does it stem from other reasons? Given these considerations, despite the generality of the proposed framework, could the author provide additional evidence to demonstrate its effectiveness? Specifically, can this framework achieve a sharp convergence rate or match the state-of-the-art convergence rates?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730729761738

thread_type:
official_review

<thread_object>
creator: reviewer_hjsc

<content>
summary:
The paper addresses a previously unexplored question: bounding the total variation between the true distribution and the distribution generated by an ODE sampler of a diffusion model. The contributions are twofold: 1) Identifying that standard assumptions are insufficient for constructing tight bounds; 2) Laying out an intuitive framework that builds the bound under sufficiently strong assumptions, accounting for both approximation errors in learning and the ODE solver.

strengths:
The paper tackles a fundamental question regarding ODE solvers for probability flow ODE, starting with a strong motivation by cleverly constructing a counterexample that demonstrates the insufficiency of assumptions on score estimation error to prove a tight bound on total variation. Adding an extra divergence approximation error, the proposed analytical direction is clear and intuitive, resulting in a three-step procedure:

1. Bound the total variation between two ODEs.
2. Define an extended ODE that aligns with the discretization scheme used in an ODE solver.
3. Bound the difference between the extended ODE and the true ODE.

Additionally, the paper showcases the instantiation of this framework through VP-SDE with an exponential integrator and VE-SDE with a DDIM integrator, providing a very natural path to follow in defining the extended ODE for other diffusion models or samplers.

weaknesses:
While the paper is well-written, it would benefit from a discussion of potential applications for this bound. The main extra assumption required is a bound on divergence, which results in an additive term in the resulting bound. However, divergence is not typically controlled during training, so exploring whether this can be managed would be interesting.

Minor Remark:

I am uncertain about the claim that Lemma 4.2 serves as an ODE version of the Girsanov Theorem, as the Girsanov Theorem concerns the Radon-Nikodym derivative. The use of a time derivative of the divergence of the marginal distributions of an ODE is also common (as seen in the proof of Lemma 2.21 in [1]). Although such a bound may not be practical within the context of this paper, it might be worthwhile to cite or discuss these bounds.

questions:
The dependency on the time schedule appears to manifest solely through Equation (3.6) in various Lemma in Appendix F and G. While it may be due to my limited understanding of prior work, are there other schedules that could fulfil the condition? Can a similarly concise bound be proven with a different time schedule?

The construction of the counterexample is pivotal in motivating the paper. Would it be beneficial to discuss how one might construct such a counterexample within the main text?

[1] Albergo, M. S., Boffi, N. M., & Vanden-Eijnden, E. (2023, March 15). Stochastic Interpolants: A Unifying Framework for Flows and Diffusions. arXiv.org. https://arxiv.org/abs/2303.08797
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a unified framework that analyzed several existing first-order ODE-based samplers, leading to an iteration complexity of $O(d^2/\epsilon)$. The unified analysis may benefit future development of convergence rates in a modular manner, and hence received positive evaluation from the reviewers. Nonetheless, the developed bound is not sharp in view of existing results, e.g., "A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models" by Li et al that offers a rate of $d/\epsilon$.