How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework

We thank the reviewer for their insightful comments and constructive feedback. Below, we address each point raised in a detailed manner.

Regarding Experimental Results

Please refer to the common response ("Regarding Empirical Validation") for our approach to incorporating empirical validation of the error bounds. We plan to conduct numerical experiments that will further substantiate our theoretical findings and illustrate their practical relevance.

Regarding the Presentation

Please refer to the common response ("Regarding the Presentation") for our comprehensive plan to improve the paper's readability and accessibility. We aim to enhance the clarity of our presentation by including more intuitive explanations and examples, making the content more approachable for readers with varying levels of familiarity with the subject matter.

Regarding the Assumptions in Theorem 4.7

We appreciate the reviewer's detailed inquiry into the assumptions underpinning Theorem 4.7. These assumptions are crucial for ensuring the robustness and applicability of our theoretical results, and we offer the following elaborations to clarify their necessity and scope:

• Assumption 4.3: (i) This assumption pertains to the well-definedness and regularity of the rate matrix $\boldsymbol Q$, which is a standard requirement and typically satisfied in scenarios like fully connected graph structures [1] or models with uniform rates [2]. (ii) It translates to the connectivity of the graph $\mathcal G(\boldsymbol Q)$, analogous to the assumptions underlying the exponential convergence of the OU process in continuous models. While often implicitly assumed, our explicit formulation provides a method to verify and quantify this convergence.
• Assumption 4.4: As justified in Remark B.3, the assumption is mainly presuming that the value of the score function $\boldsymbol{s}_t$ is at most of order $\mathcal O(t{-1})$, which is also assumed in previous work [3]. In many cases, such assumption can be relaxed to $\mathcal O(1)$ (cf. Assumption 2 [2]), e.g. by assuming the target data distribution to be both lower and upper bounded (cf. Assumption 3 [3] and Assumption 2.4 [4] for the case of continuous diffusion models). The bound on the neural network-based score function is to ensure well-posed behavior of the approximate reverse process, which can either be strictly enforced via manual truncation or implicitly imposed by regularization techniques during training. Similar assumptions are also made on the neural network approximations for the case of continuous diffusion models (cf. Assumption 3 [5], Assumption 3.3 [6] and Assumption 4.3 [7]).
• Assumption 4.5: Suppose $Q(x_{t-}, y) = \Theta(1)$, this assumption is trivially satisfied for $\gamma = 1$ given Assumption 4.3. However, we choose to introduce the parameter $\gamma\in[0, 1]$, which represents the local continuity of the score function (cf. the assumption on Lipschitz continuity of the true score function for continuous diffusion models, e.g. Assumption 2 [5], Assumption 4.2 [7], Assumption 1 [8] and Assumption 3 [9]), to investigate how the error bound scales with this continuity measure. As shown in Theorem 4.7, we can see that one may need different time discretization schemes for different levels of continuity.
• Assumption 4.6: This assumption is essentially stating that the neural network based score estimator is $\epsilon$-accurate in terms of the score entropy loss, which also appeared as Assumption 1 in [3]. In fact, this assumption can be treated as an analog of the $L^2$-accuracy assumption, which is widely adopted in related work on the theoretical analysis of continuous diffusion models (cf. Assumption 4 [5], Assumption 3.2 [6], Assumption 3 [8] and Assumption 1 [9]).

These assumptions ensure the theoretical soundness of our framework and are aligned with practical conditions often encountered in the implementation of diffusion models. We believe these conditions are reasonable and pragmatic, though future work may explore their relaxation to enhance the framework's flexibility and applicability.

We hope this response satisfactorily addresses the reviewer’s concerns and clarifies the depth and rigor of our approach. We are open to further discussions and are grateful for the opportunity to enhance our manuscript based on your feedback.

References

[1] Lou, Aaron, Chenlin Meng, and Stefano Ermon. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." Forty-first International Conference on Machine Learning.
[2] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." Advances in Neural Information Processing Systems 35 (2022): 28266-28279.
[3] Chen, Hongrui, and Lexing Ying. "Convergence analysis of discrete diffusion model: Exact implementation through uniformization." arXiv preprint arXiv:2402.08095 (2024).
[4] Oko, Kazusato, Shunta Akiyama, and Taiji Suzuki. "Diffusion models are minimax optimal distribution estimators." In International Conference on Machine Learning, pp.26517-26582. PMLR, 2024
[5] Chen, Sitan, et al. "The probability flow ode is provably fast." Advances in Neural Information Processing Systems 36 (2024).
[6] Huang, Daniel Zhengyu, Jiaoyang Huang, and Zhengjiang Lin. "Convergence analysis of probability flow ODE for score-based generative models." arXiv preprint arXiv:2404.09730 (2024).
[7] Dou, Zehao, et al. "Theory of Consistency Diffusion Models: Distribution Estimation Meets Fast Sampling." In International Conference on Machine Learning, pp.11592-11612. PMLR, 2024.
[8] Chen, Sitan, et al. "Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions." In: The Eleventh International Conference on Learning Representations. 2023.
[9] Chen, Hongrui, Holden Lee, and Jianfeng Lu. "Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions." International Conference on Machine Learning. PMLR, 2023.

We thank the reviewer for their constructive feedback and for highlighting both the strengths and areas for improvement in our work. We address the concerns raised below.

Regarding the Experimental Evaluation

Please refer to the common response ("Regarding Empirical Validation") for our detailed response to the request for numerical experiments. In brief, while this work focuses on theoretical contributions, we acknowledge the value of empirical validation and plan to explore numerical experiments to assess the practical accuracy of our error bounds and algorithmic performance in future work.

Regarding the Presentation

Please refer to the common response ("Regarding the Presentation") for our detailed plan to improve the readability and accessibility of the paper. In summary, we will enhance the explanations, include illustrative examples, and reorganize sections to make the content more intuitive and approachable for a broader audience.

Regarding the Assumption of Symmetry for $\boldsymbol Q$

We appreciate the reviewer’s insightful question about the role of the symmetry assumption for $\boldsymbol Q$ in our analysis. Below, we provide a detailed clarification:

• Applicability in Practice: The assumption of $\boldsymbol Q$ being symmetric is consistent with a wide range of discrete diffusion model designs commonly used in practice, such as models with fully connected graph structures [1] or uniform rates [2].
• Assumption-Specific Dependencies:
  • Assumptions 4.3(i), 4.5, and 4.6 are independent of the symmetry of $\boldsymbol Q$.
  • Assumption 4.3(ii), concerning the lower bound on the modified log-Sobolev constant $\rho(\boldsymbol Q)$, is generally related to the connectivity and structural properties of the graph $\mathcal G(\boldsymbol Q)$ but not directly related to symmetry.
  • Assumption 4.4 leverages symmetry in our proof (see Remark B.3), as it simplifies certain derivations. However, these arguments can be extended to non-symmetric $\boldsymbol Q$ by introducing additional spectral assumptions on $\boldsymbol Q$. We will discuss this extension in the revised version of the paper.
• General Applicability of Our Framework: Our core theoretical contributions, including the stochastic integral formulation (Propositions 3.2, 4.1, 4.2) and the change of measure arguments (Theorem 3.3, Corollary 3.5), are independent of the symmetry assumption for $\boldsymbol Q$. This ensures that the foundation of our error analysis holds for non-symmetric $\boldsymbol Q$ as well. The assumption of $\boldsymbol Q$ being symmetric only simplifies the proof of the discretization error (Proposition C.5).

We strongly believe that our error bounds can be extended to non-symmetric $\boldsymbol Q$ under appropriate assumptions, including cases involving absorbing states [1, 3]. This represents an interesting direction for future work, and we are excited to explore these generalizations further.

We once again thank the reviewer for their thoughtful comments, which have helped us refine and clarify our work. We hope our responses address the concerns raised, and we are happy to provide further clarifications or explanations as needed.

References

[1] Lou, Aaron, Chenlin Meng, and Stefano Ermon. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." Forty-first International Conference on Machine Learning.
[2] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." Advances in Neural Information Processing Systems 35 (2022): 28266-28279.
[3] Ou, Jingyang, et al. "Your Absorbing Discrete Diffusion Secretly Models the Conditional Distributions of Clean Data." arXiv preprint arXiv:2406.03736 (2024).

We sincerely thank the reviewer for their positive feedback and insightful questions, which have provided valuable opportunities to clarify and expand upon key aspects of our work. We address the comments point by point below.

Regarding Empirical Validation of Error Bounds

We appreciate the reviewers’ concerns about empirical validation and refer to the common response ("Regarding Empirical Validation") for detailed plans to incorporate numerical experiments that validate our theoretical error bounds and compare algorithmic performance in future work.

Regarding Runtime and Memory Complexity Comparisons

We appreciate the reviewer's interest in runtime and memory complexity comparisons. In the current version of the paper, we provide a runtime comparison following Theorem 4.9, highlighting a potential advantage of the uniformization algorithm in reducing computational cost. This analysis underscores how our theoretical framework can guide practitioners in selecting more efficient algorithms for simulating the backward process.

As for memory complexity, if the reviewer is referring to the memory required to store the neural network used for approximating the score function, the memory complexities of the $\tau$-leaping and uniformization algorithms are identical. If a different aspect of memory complexity is intended, we would be glad to investigate and address it in further detail.

Regarding Other Potential Stochastic Frameworks

We thank the reviewer for their astute observation regarding alternative stochastic frameworks for discrete diffusion models. For Markov processes, two main formulations exist: the distribution-based and the path-based (e.g., forward and backward processes represented by state distributions or by state trajectories over time). In continuous diffusion models, the path-based formulation using stochastic differential equations (SDEs [3]) is favored for its intuitive interpretation and utility in both implementation and theoretical analysis.

In contrast, current analyses of discrete diffusion models predominantly use the continuous-time Markov chain (CTMC) framework [1, 2]. While effective, this approach is less intuitive for theoretical analysis and lacks a clear connection to continuous diffusion models. Our work introduces a path-based formulation for discrete diffusion models through Lévy-type stochastic integrals, which parallels the SDE framework in continuous diffusion. This formulation not only bridges the theoretical gap between discrete and continuous diffusion models but also facilitates unified error analysis for algorithms like $\tau$-leaping and uniformization.

Moreover, Lévy processes, characterized by infinite divisibility and the Lévy-Khintchine theorem, encompass a drift, Brownian motion, and jump process, allowing for broad applicability [4]. In discrete state spaces, where drifts and Brownian motions are not applicable, Lévy-type integrals simplify to stochastic integrals with respect to Poisson random measures. This makes our framework both general and well-suited for discrete diffusion models. Potential alternatives could include removing Markov assumptions, a direction we believe holds promise for future research. Additionally, exploring how diffusion models based on different Markov processes perform across various tasks would be an intriguing area of practical investigation [5, 6, 7].

In conclusion, we once again thank the reviewer for their thoughtful feedback and questions, which have greatly helped in clarifying the scope and implications of our work. We hope our responses have addressed all concerns and are happy to provide further clarifications or elaborations if needed.

References

[1] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." Advances in Neural Information Processing Systems 35 (2022): 28266-28279.
[2] Chen, Hongrui, and Lexing Ying. "Convergence analysis of discrete diffusion model: Exact implementation through uniformization." arXiv preprint arXiv:2402.08095 (2024).
[3] Song, Yang, et al. "Score-based generative modeling through stochastic differential equations." arXiv preprint arXiv:2011.13456 (2020).
[4] Benton, Joe, et al. "From denoising diffusions to denoising Markov models." Journal of the Royal Statistical Society Series B: Statistical Methodology 86.2 (2024): 286-301.
[5] Yoon, Eun Bi, et al. "Score-based generative models with Lévy processes." Advances in Neural Information Processing Systems 36 (2023): 40694-40707.
[6] Chen, Yifan, et al. "Probabilistic Forecasting with Stochastic Interpolants and F" ollmer Processes." In International Conference on Machine Learning, pp.6728-6756. PMLR, 2024.
[7] Winkler, Ludwig, Lorenz Richter, and Manfred Opper. "Bridging discrete and continuous state spaces: Exploring the Ehrenfest process in time-continuous diffusion models." In International Conference on Machine Learning, pp.53017-53038. PMLR, 2024.

Regarding the Presentation

We acknowledge the concerns about the paper's dense writing and technical detail. Please refer to our common response ("Regarding the Presentation") for specific plans to enhance the paper's accessibility, including the addition of intuitive explanations, examples, and proof outlines to aid understanding.

In conclusion, we sincerely thank the reviewer for their detailed comments and questions, which have greatly helped us identify areas for improvement. We will incorporate these suggestions into the revised version of the paper. Should there be further questions or concerns, we would be happy to address them.

References

[1] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.
[2] Sun, Haoran, et al. "Score-based continuous-time discrete diffusion models." arXiv preprint arXiv:2211.16750 (2022).
[3] Lou, Aaron, Chenlin Meng, and Stefano Ermon. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." Forty-first International Conference on Machine Learning.
[4] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." Advances in Neural Information Processing Systems 35 (2022): 28266-28279.
[5] Chen, Hongrui, and Lexing Ying. "Convergence analysis of discrete diffusion model: Exact implementation through uniformization." arXiv preprint arXiv:2402.08095 (2024).
[6] Benton, Joe, et al. "From denoising diffusions to denoising markov models." arXiv preprint arXiv:2211.03595 (2022).
[7] Chen, Sitan, et al. "Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions." In: The Eleventh International Conference on Learning Representations. 2023.
[8] Chen, Hongrui, Holden Lee, and Jianfeng Lu. "Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions." International Conference on Machine Learning. PMLR, 2023.
[9] Benton, Joe, et al. "Linear convergence bounds for diffusion models via stochastic localization." In: The Eleventh International Conference on Learning Representations. 2024.
[10] Chen, Sitan, et al. "The probability flow ode is provably fast." Advances in Neural Information Processing Systems 36 (2024).
[11] Huang, Daniel Zhengyu, Jiaoyang Huang, and Zhengjiang Lin. "Convergence analysis of probability flow ODE for score-based generative models." arXiv preprint arXiv:2404.09730 (2024).

We thank the reviewer for their thoughtful and constructive feedback, which has provided valuable insights into improving the clarity, positioning, and contributions of our work. We address the points raised below in detail.

Regarding the Positioning and Motivation of the Work

We appreciate the reviewer's concerns about the positioning and motivation of our work. As highlighted in the introduction, the primary motivation stems from the lack of a systematic and rigorous theoretical framework for discrete diffusion models, compared to the well-established literature on continuous diffusion models. Our contributions build on the following works:

• Methodology: Construction of forward and backward processes in discrete state spaces [1, 2], ratio matching [3], score entropy loss [4, 6], denoising score entropy loss [3].
• Error Analysis for Discrete Diffusion: CTMC-based error analysis for $\tau$-leaping in TV distance [4], Feller process-based analysis for general denoising Markov models [6], and recent work on uniformization algorithms for $\mathbb{X} = \\{ 0,1 \\}^d$ [5].
• Error Analysis for Continuous Diffusion: Sampling guarantees in KL divergence [7, 8, 9] and TV distance [10, 11].

By consolidating and extending these works, we aim to establish a comprehensive theoretical framework for discrete diffusion models, addressing the fragmented nature of the current literature.

Regarding the Related Works

We recognize the reviewer's point about the organization of related works. Given the scarcity of theoretical works on discrete diffusion models, we focused our discussion on two key references [4, 5] within the introduction to motivate and contextualize our contributions. However, we acknowledge that this organization may have diluted the clarity of positioning. In the revised manuscript, we will reorganize the introduction and related works sections to better articulate our contributions and how they relate to prior literature.

Regarding the Contributions

We acknowledge the reviewer's concerns regarding the clarity of the contributions, especially as claimed in the third bullet point of Section 1.1 (Contributions). We agree with the reviewer that the contributions should be more clearly and explicitly articulated. Below, we elaborate on the novel contributions of our work:

• Technique Advancement: We introduce Poisson random measures with evolving intensities, formulating discrete diffusion models as stochastic integrals. This approach, supported by a novel Girsanov's theorem, provides a fresh perspective on analyzing discrete diffusion models.
• Unified and Fortified Error Analysis: Our methodology is capable of deriving error bounds and thus unifying the error analysis for both the $\tau$-leaping [4] and uniformization algorithms [5], under relaxed assumptions. Importantly, we establish the first theoretical guarantees for the $\tau$-leaping algorithm in KL divergence, a significant improvement over prior work in TV distance.
• Bridging Discrete and Continuous Models: Our framework connects the error analysis of discrete and continuous diffusion models, facilitating the transfer of theoretical and practical insights between these domains. This thus sheds light on establishing convergence guarantees for a broader range of discrete diffusion models.

We will rewrite the contributions section in the revised manuscript to incorporate these points more explicitly, addressing the feedback from the reviewer.

Regarding the Implications for Practical Usage

We thank the reviewer for pointing out the need to better highlight the practical implications of our work. While our paper is primarily theoretical, we analyze the $\tau$-leaping and uniformization algorithms, two widely used methods for inference in discrete diffusion models. Our error analysis provides key insights into the convergence properties and computational complexity of these algorithms. To clarify these implications, we will:

• Expand the discussion following Theorem 4.9 to explicitly compare the runtime of the $\tau$-leaping and uniformization algorithms.
• Emphasize how our theoretical framework can guide the design and analysis of new algorithms for training and inference in discrete diffusion models.

In summary, we believe our work provides a unified framework to analyze and compare the time complexity of algorithms used for simulating the backward process, with potential to inform future advancements in the field.

Regarding Empirical Validation (Reviewers Se7m, 5nb2, 5uy7)

We thank the reviewers for emphasizing the importance of numerical experiments to complement our theoretical findings. While this paper primarily focuses on developing a mathematical framework and error analysis for discrete diffusion models, we agree that empirical validation would provide valuable insights into the practical implications of our results. We acknowledge that empirical studies, such as those by Austin et al. [1], Lou et al. [2], and Campbell et al. [3], have significantly advanced the practical aspects of diffusion models. In contrast, our work focuses on providing theoretical foundations that could inform and guide empirical research.

Adding numerical experiments to compare the $\tau$-leaping and uniformization algorithms in simulating the backward continuous-time Markov chain with a fixed (pretrained) score function would be a logical next step. If time permits, we plan to include such numerical experiments in the revised version of the paper to strengthen the connection between our theoretical results and practical performance. In future research, we also aim to study the broader implications of our framework on algorithm design and analysis, potentially addressing practical concerns such as computational efficiency and algorithmic robustness.

References

[1] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.
[2] Lou, Aaron, Chenlin Meng, and Stefano Ermon. "Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution." Forty-first International Conference on Machine Learning.
[3] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." Advances in Neural Information Processing Systems 35 (2022): 28266-28279.