Discrete Markov Bridge
Authors: name: Hengli Li, name: Yuxuan Wang, name: Song-Chun Zhu, name: Ying Nian Wu, name: Zilong Zheng

Discrete diffusion has recently emerged as a promising paradigm in discrete
data modeling. However, existing methods typically rely on a fixed rate
transition matrix during training, which not only limits the expressiveness of
latent representations, a fundamental strength of variational methods, but also
constrains the overall design space. To address these limitations, we propose
Discrete Markov Bridge, a novel framework specifically designed for discrete
representation learning. Our approach is built upon two key components: Matrix
Learning and Score Learning. We conduct a rigorous theoretical analysis,
establishing formal performance guarantees for Matrix Learning and proving the
convergence of the overall framework. Furthermore, we analyze the space
complexity of our method, addressing practical constraints identified in prior
studies. Extensive empirical evaluations validate the effectiveness of the
proposed Discrete Markov Bridge, which achieves an Evidence Lower Bound (ELBO)
of 1.38 on the Text8 dataset, outperforming established baselines. Moreover,
the proposed model demonstrates competitive performance on the CIFAR-10
dataset, achieving results comparable to those obtained by image-specific
generation approaches.