Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC
This work provides a novel method for researchers and practitioners who need to sample from complex discrete distributions, extending the applicability of powerful MCMC techniques.
This paper addresses the challenge of applying Hybrid Monte Carlo (HMC) to discrete domains by introducing SurVAE Flow Augmented MCMC. The method learns a continuous embedding of the discrete space and a bijective transformation to a Gaussian latent variable, allowing MCMC chains to be simulated in the latent space and mapped back to the discrete target space. The authors demonstrate improved efficacy across examples in statistics, computational physics, and machine learning.
Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. However, a major limitation of HMC is its inability to be applied to discrete domains due to the lack of gradient signal. In this work, we introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions using a combination of neural transport methods like normalizing flows and variational dequantization, and the Metropolis-Hastings rule. Our method first learns a continuous embedding of the discrete space using a surjective map and subsequently learns a bijective transformation from the continuous space to an approximately Gaussian distributed latent variable. Sampling proceeds by simulating MCMC chains in the latent space and mapping these samples to the target discrete space via the learned transformations. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.