A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908497626529792 |
|---|---|
| author | Sanokowski, Sebastian Hochreiter, Sepp Lehner, Sebastian |
| author_facet | Sanokowski, Sebastian Hochreiter, Sepp Lehner, Sebastian |
| contents | Learning to sample from intractable distributions over discrete sets without relying on corresponding training data is a central problem in a wide range of fields, including Combinatorial Optimization. Currently, popular deep learning-based approaches rely primarily 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 like diffusion models. Our approach is conceptually based on a loss that upper bounds the reverse Kullback-Leibler divergence and evades the requirement of exact sample likelihoods. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_01661 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization Sanokowski, Sebastian Hochreiter, Sepp Lehner, Sebastian Machine Learning Artificial Intelligence Discrete Mathematics Learning to sample from intractable distributions over discrete sets without relying on corresponding training data is a central problem in a wide range of fields, including Combinatorial Optimization. Currently, popular deep learning-based approaches rely primarily 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 like diffusion models. Our approach is conceptually based on a loss that upper bounds the reverse Kullback-Leibler divergence and evades the requirement of exact sample likelihoods. 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. |
| title | A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization |
| topic | Machine Learning Artificial Intelligence Discrete Mathematics |
| url | https://arxiv.org/abs/2406.01661 |