Diffusion models have achieved great success in generating high-dimensional samples across various applications. While the theoretical guarantees for continuous-state diffusion models have been extensively studied, the convergence analysis of the discrete-state counterparts remains under-explored. In this paper, we study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]^d$ that utilizes score estimators at predefined time points. We derive convergence bounds for the Kullback-Leibler (KL) divergence and total variation (TV) distance between the generated sample distribution and the data distribution, considering both scenarios with and without early stopping under specific assumptions. Notably, our KL divergence bounds are nearly linear in dimension $d$, aligning with state-of-the-art results for diffusion models. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function, which are essential for characterizing the discrete-time sampling process.

本研究解决了离散状态扩散模型收敛性分析的不足之处，提出了一种基于连续时间马尔可夫链框架的离散时间采样算法。研究表明，在特定假设下，生成的样本分布与数据分布之间的Kullback-Leibler散度和总变差距离的收敛边界几乎线性依赖于维度d，具有重要的理论价值和实用意义。

分数基础离散扩散模型的收敛性：离散时间分析