# Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC

arXiv: https://arxiv.org/abs/2102.02374 · HTML: https://mlsanity.com/paper/2102.02374/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 4 Feb 2021.

## Builds on (most cited first, 9 of 9)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [A note on the evaluation of generative models](https://mlsanity.com/paper/1511.01844/) (2015)
- [Flow++: Improving Flow-Based Generative Models with Variational Dequantization and Architecture Design](https://mlsanity.com/paper/1902.00275/) (2019)
- [Flow-based generative models for Markov chain Monte Carlo in lattice field theory](https://mlsanity.com/paper/1904.12072/) (2019)
- [NeuTra-lizing Bad Geometry in Hamiltonian Monte Carlo Using Neural Transport](https://mlsanity.com/paper/1903.03704/) (2019)
- [SurVAE Flows: Surjections to Bridge the Gap between VAEs and Flows](https://mlsanity.com/paper/2007.02731/) (2020)
- [RNADE: The real-valued neural autoregressive density-estimator](https://mlsanity.com/paper/1306.0186/) (2013)
- [The Hamming Ball Sampler](https://mlsanity.com/paper/1504.08133/) (2015)

## Built on by (most cited first, 7 of 7)

- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Jointly Learning Consistent Causal Abstractions Over Multiple Interventional Distributions](https://mlsanity.com/paper/2301.05893/) (2023)
- [Learning Equivariant Energy Based Models with Equivariant Stein Variational Gradient Descent](https://mlsanity.com/paper/2106.07832/) (2021)
- [Enhanced gradient-based MCMC in discrete spaces](https://mlsanity.com/paper/2208.00040/) (2022)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)

## Abstract (arXiv)

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.