Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics

• URL: http://arxiv.org/abs/2502.08696v2
• Date: Mon, 17 Feb 2025 08:41:58 GMT
• Title: Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
• Authors: Sebastian Sanokowski, Wilhelm Berghammer, Martin Ennemoser, Haoyu Peter Wang, Sepp Hochreiter, Sebastian Lehner,
• Abstract summary: We introduce two novel training methods for discrete diffusion samplers. These methods yield memory-efficient training and achieve state-of-the-art results in unsupervised optimization. We introduce adaptations of SN-NIS and Neural Chain Monte Carlo that enable for the first time the application of discrete diffusion models to this problem.
• Score: 7.873510219469276
• License:
• Abstract: 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.

Related papers

• Accelerated Diffusion Models via Speculative Sampling [89.43940130493233]
  Speculative sampling is a popular technique for accelerating inference in Large Language Models. We extend speculative sampling to diffusion models, which generate samples via continuous, vector-valued Markov chains. We propose various drafting strategies, including a simple and effective approach that does not require training a draft model.
  arXiv  Detail & Related papers  (2025-01-09T16:50:16Z)
• Training-free Diffusion Model Alignment with Sampling Demons [15.400553977713914]
  We propose an optimization approach, dubbed Demon, to guide the denoising process at inference time without backpropagation through reward functions or model retraining. Our approach works by controlling noise distribution in denoising steps to concentrate density on regions corresponding to high rewards through optimization. To the best of our knowledge, the proposed approach is the first inference-time, backpropagation-free preference alignment method for diffusion models.
  arXiv  Detail & Related papers  (2024-10-08T07:33:49Z)
• Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding [84.3224556294803]
  Diffusion models excel at capturing the natural design spaces of images, molecules, DNA, RNA, and protein sequences. We aim to optimize downstream reward functions while preserving the naturalness of these design spaces. Our algorithm integrates soft value functions, which looks ahead to how intermediate noisy states lead to high rewards in the future.
  arXiv  Detail & Related papers  (2024-08-15T16:47:59Z)
• Understanding Reinforcement Learning-Based Fine-Tuning of Diffusion Models: A Tutorial and Review [63.31328039424469]
  This tutorial provides a comprehensive survey of methods for fine-tuning diffusion models to optimize downstream reward functions. We explain the application of various RL algorithms, including PPO, differentiable optimization, reward-weighted MLE, value-weighted sampling, and path consistency learning.
  arXiv  Detail & Related papers  (2024-07-18T17:35:32Z)
• A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization [7.378582040635655]
  Current deep learning approaches rely on generative models that yield exact sample likelihoods. This work introduces a method that lifts this restriction and opens the possibility to employ highly expressive latent variable models. We experimentally validate our approach in data-free Combinatorial Optimization and demonstrate that our method achieves a new state-of-the-art on a wide range of benchmark problems.
  arXiv  Detail & Related papers  (2024-06-03T17:55:02Z)
• Neural Flow Diffusion Models: Learnable Forward Process for Improved Diffusion Modelling [2.1779479916071067]
  We introduce a novel framework that enhances diffusion models by supporting a broader range of forward processes. We also propose a novel parameterization technique for learning the forward process. Results underscore NFDM's versatility and its potential for a wide range of applications.
  arXiv  Detail & Related papers  (2024-04-19T15:10:54Z)
• Improved off-policy training of diffusion samplers [93.66433483772055]
  We study the problem of training diffusion models to sample from a distribution with an unnormalized density or energy function. We benchmark several diffusion-structured inference methods, including simulation-based variational approaches and off-policy methods. Our results shed light on the relative advantages of existing algorithms while bringing into question some claims from past work.
  arXiv  Detail & Related papers  (2024-02-07T18:51:49Z)
• Metropolis Sampling for Constrained Diffusion Models [11.488860260925504]
  Denoising diffusion models have recently emerged as the predominant paradigm for generative modelling on image domains. We introduce an alternative, simple noretisation scheme based on the reflected Brownian motion.
  arXiv  Detail & Related papers  (2023-07-11T17:05:23Z)
• Protein Design with Guided Discrete Diffusion [67.06148688398677]
  A popular approach to protein design is to combine a generative model with a discriminative model for conditional sampling. We propose diffusioN Optimized Sampling (NOS), a guidance method for discrete diffusion models. NOS makes it possible to perform design directly in sequence space, circumventing significant limitations of structure-based methods.
  arXiv  Detail & Related papers  (2023-05-31T16:31:24Z)
• Towards Controllable Diffusion Models via Reward-Guided Exploration [15.857464051475294]
  We propose a novel framework that guides the training-phase of diffusion models via reinforcement learning (RL) RL enables calculating policy gradients via samples from a pay-off distribution proportional to exponential scaled rewards, rather than from policies themselves. Experiments on 3D shape and molecule generation tasks show significant improvements over existing conditional diffusion models.
  arXiv  Detail & Related papers  (2023-04-14T13:51:26Z)
• A Survey on Generative Diffusion Model [75.93774014861978]
  Diffusion models are an emerging class of deep generative models. They have certain limitations, including a time-consuming iterative generation process and confinement to high-dimensional Euclidean space. This survey presents a plethora of advanced techniques aimed at enhancing diffusion models.
  arXiv  Detail & Related papers  (2022-09-06T16:56:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.