Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics

Diffusion models for continuous state spaces based on Gaussian noising processes are now relatively well understood, as many works have focused on their theoretical analysis. In contrast, results for diffusion models on discrete state spaces remain limited and pose significant challenges, particularly due to their combinatorial structure and their more recent introduction in generative modelling. In this work, we establish new and sharp convergence guarantees for three popular discrete diffusion models (DDMs). Two of these models are designed for finite state spaces and are based respectively on the random walk and the masking process. The third DDM we consider is defined on the countably infinite space $\mathbb{N}^d$ and uses a drifted random walk as its forward process. For each of these models, the backward process can be characterized by a discrete score function that can, in principle, be estimated. However, even with perfect access to these scores, simulating the exact backward process is infeasible, and one must rely on approximations. In this work, we study Euler-type approximations and establish convergence bounds in both Kullback-Leibler divergence and total variation distance for the resulting models, under minimal assumptions on the data distribution. In particular, we show that the computational complexity of each method scales linearly in the dimension, up to logarithmic factors. Furthermore, to the best of our knowledge, this study provides the first non-asymptotic convergence guarantees for these noising processes that do not rely on boundedness assumptions on the estimated score.