Loading [MathJax]/jax/output/HTML-CSS/config.js
Volume 4, Issue 2
Convergence Analysis of Discrete Diffusion Model: Exact Implementation Through Uniformization

Hongrui Chen & Lexing Ying

J. Mach. Learn. , 4 (2025), pp. 108-127.

Published online: 2025-06

[An open-access article; the PDF is free to any online user.]

Export citation
  • Abstract

Diffusion models have achieved huge empirical success in data generation tasks. Recently, some efforts have been made to adapt the framework of diffusion models to discrete state space, providing a more natural approach for modeling intrinsically discrete data, such as language and graphs. This is achieved by formulating both the forward noising process and the corresponding reversed process as continuous time Markov chains. In this paper, we investigate the theoretical properties of the discrete diffusion model. Specifically, we introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Under reasonable assumptions on the learning of the discrete score function, we derive total variation distance and Kullback–Leibler divergence guarantees for sampling from any distribution on a hypercube. Our results align with state-of-the-art achievements for diffusion models in $\mathbb{R}^d$ and further underscore the advantages of discrete diffusion models in comparison to the $\mathbb{R}^d$ setting.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JML-4-108, author = {Chen , Hongrui and Ying , Lexing}, title = {Convergence Analysis of Discrete Diffusion Model: Exact Implementation Through Uniformization}, journal = {Journal of Machine Learning}, year = {2025}, volume = {4}, number = {2}, pages = {108--127}, abstract = {

Diffusion models have achieved huge empirical success in data generation tasks. Recently, some efforts have been made to adapt the framework of diffusion models to discrete state space, providing a more natural approach for modeling intrinsically discrete data, such as language and graphs. This is achieved by formulating both the forward noising process and the corresponding reversed process as continuous time Markov chains. In this paper, we investigate the theoretical properties of the discrete diffusion model. Specifically, we introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Under reasonable assumptions on the learning of the discrete score function, we derive total variation distance and Kullback–Leibler divergence guarantees for sampling from any distribution on a hypercube. Our results align with state-of-the-art achievements for diffusion models in $\mathbb{R}^d$ and further underscore the advantages of discrete diffusion models in comparison to the $\mathbb{R}^d$ setting.

}, issn = {2790-2048}, doi = {https://doi.org/10.4208/jml.240812}, url = {http://global-sci.org/intro/article_detail/jml/24144.html} }
TY - JOUR T1 - Convergence Analysis of Discrete Diffusion Model: Exact Implementation Through Uniformization AU - Chen , Hongrui AU - Ying , Lexing JO - Journal of Machine Learning VL - 2 SP - 108 EP - 127 PY - 2025 DA - 2025/06 SN - 4 DO - http://doi.org/10.4208/jml.240812 UR - https://global-sci.org/intro/article_detail/jml/24144.html KW - Diffusion model, Sampling, Machine learning theory. AB -

Diffusion models have achieved huge empirical success in data generation tasks. Recently, some efforts have been made to adapt the framework of diffusion models to discrete state space, providing a more natural approach for modeling intrinsically discrete data, such as language and graphs. This is achieved by formulating both the forward noising process and the corresponding reversed process as continuous time Markov chains. In this paper, we investigate the theoretical properties of the discrete diffusion model. Specifically, we introduce an algorithm leveraging the uniformization of continuous Markov chains, implementing transitions on random time points. Under reasonable assumptions on the learning of the discrete score function, we derive total variation distance and Kullback–Leibler divergence guarantees for sampling from any distribution on a hypercube. Our results align with state-of-the-art achievements for diffusion models in $\mathbb{R}^d$ and further underscore the advantages of discrete diffusion models in comparison to the $\mathbb{R}^d$ setting.

Chen , Hongrui and Ying , Lexing. (2025). Convergence Analysis of Discrete Diffusion Model: Exact Implementation Through Uniformization. Journal of Machine Learning. 4 (2). 108-127. doi:10.4208/jml.240812
Copy to clipboard
The citation has been copied to your clipboard