Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions
This work addresses the problem of discrete generative modeling for researchers and practitioners in the field of machine learning and artificial intelligence, providing an incremental yet significant improvement.
The authors tackled the problem of discrete data generation with a novel discrete diffusion algorithm, achieving competitive performance in generating discrete structures with convergence bounds under minimal assumptions, and demonstrating results on low-dimensional Bernoulli-distributed datasets and high-dimensional binary MNIST data. The algorithm shows robustness and efficiency with sharp convergence bounds.
This paper introduces Discrete Markov Probabilistic Models (DMPMs), a novel discrete diffusion algorithm for discrete data generation. The algorithm operates in discrete bit space, where the noising process is a continuous-time Markov chain that flips labels uniformly at random. The time-reversal process, like the forward noise process, is a jump process with its intensity governed by a discrete analogue of the classical score function. Crucially, this intensity is proven to be the conditional expectation of a function of the forward process, underlining theoretical alignment with score-based generative models. We establish convergence bounds for the algorithm under minimal assumptions, ensuring robustness and efficiency, which we demonstrate through experiments on low-dimensional Bernoulli-distributed datasets and high-dimensional binary MNIST data. The results highlight competitive performance in generating discrete structures compared to the state-of-the-art. This work bridges theoretical foundations and practical applications, advancing the development of effective and theoretically grounded discrete generative modeling.