This paper focuses on sampling learning from complex irregular distributions in the discrete domain, showing potential applications in various fields such as statistical physics, variational inference, and combinatorial optimization. Conventional discrete diffusion models have a limited number of diffusion steps due to the memory scaling problem. In this paper, we propose two new training methods, which utilize policy gradient theorem and self-normalizing neural importance sampling (SN-NIS), to achieve memory-efficient training and state-of-the-art results in unsupervised combinatorial optimization. In addition, by applying SN-NIS and neural Markov chain Monte Carlo (MCMC), we apply the discrete diffusion model to uniform sampling problems for the first time, and show that it outperforms conventional autoregressive approaches through the Ising model benchmark.
