Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918085674401792 |
|---|---|
| author | Sanokowski, Sebastian Berghammer, Wilhelm Ennemoser, Martin Wang, Haoyu Peter Hochreiter, Sepp Lehner, Sebastian |
| author_facet | Sanokowski, Sebastian Berghammer, Wilhelm Ennemoser, Martin Wang, Haoyu Peter Hochreiter, Sepp Lehner, Sebastian |
| contents | Learning to sample from complex unnormalized distributions over discrete domains emerged as a promising research direction with applications in statistical physics, variational inference, and combinatorial optimization. Recent work has demonstrated the potential of diffusion models in this domain. However, existing methods face limitations in memory scaling and thus the number of attainable diffusion steps since they require backpropagation through the entire generative process. To overcome these limitations we introduce two novel training methods for discrete diffusion samplers, one grounded in the policy gradient theorem and the other one leveraging Self-Normalized Neural Importance Sampling (SN-NIS). These methods yield memory-efficient training and achieve state-of-the-art results in unsupervised combinatorial optimization. Numerous scientific applications additionally require the ability of unbiased sampling. We introduce adaptations of SN-NIS and Neural Markov Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem. We validate our methods on Ising model benchmarks and find that they outperform popular autoregressive approaches. Our work opens new avenues for applying diffusion models to a wide range of scientific applications in discrete domains that were hitherto restricted to exact likelihood models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08696 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics Sanokowski, Sebastian Berghammer, Wilhelm Ennemoser, Martin Wang, Haoyu Peter Hochreiter, Sepp Lehner, Sebastian Machine Learning Statistical Mechanics Artificial Intelligence Computational Physics Learning to sample from complex unnormalized distributions over discrete domains emerged as a promising research direction with applications in statistical physics, variational inference, and combinatorial optimization. Recent work has demonstrated the potential of diffusion models in this domain. However, existing methods face limitations in memory scaling and thus the number of attainable diffusion steps since they require backpropagation through the entire generative process. To overcome these limitations we introduce two novel training methods for discrete diffusion samplers, one grounded in the policy gradient theorem and the other one leveraging Self-Normalized Neural Importance Sampling (SN-NIS). These methods yield memory-efficient training and achieve state-of-the-art results in unsupervised combinatorial optimization. Numerous scientific applications additionally require the ability of unbiased sampling. We introduce adaptations of SN-NIS and Neural Markov Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem. We validate our methods on Ising model benchmarks and find that they outperform popular autoregressive approaches. Our work opens new avenues for applying diffusion models to a wide range of scientific applications in discrete domains that were hitherto restricted to exact likelihood models. |
| title | Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics |
| topic | Machine Learning Statistical Mechanics Artificial Intelligence Computational Physics |
| url | https://arxiv.org/abs/2502.08696 |