Oops I Took A Gradient: Scalable Sampling for Discrete Distributions

2021/02/08 by Grathwohl, Will, Swersky, Kevin, Hashemi, Milad +2 · 6 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2102.04509

Abstract

We propose a general and scalable approximate sampling strategy for probabilistic models with discrete variables. Our approach uses gradients of the likelihood function with respect to its discrete inputs to propose updates in a Metropolis-Hastings sampler. We show empirically that this approach outperforms generic samplers in a number of difficult settings including Ising models, Potts models, restricted Boltzmann machines, and factorial hidden Markov models. We also demonstrate the use of our improved sampler for training deep energy-based models on high dimensional discrete data. This approach outperforms variational auto-encoders and existing energy-based models. Finally, we give bounds showing that our approach is near-optimal in the class of samplers which propose local updates.

Cited by

• A new class of Markov random fields enabling lightweight sampling
• FlowQ-Net: A Generative Framework for Automated Quantum Circuit Design
• Sampling from Energy distributions with Target Concrete Score Identity
• CANDI: Hybrid Discrete-Continuous Diffusion Models
• Diffusion Alignment as Variational Expectation-Maximization
• Preconditioned Discrete-HAMS: A Second-order Irreversible Discrete Sampler

Related

• A Langevin-like Sampler for Discrete Distributions
• Discrete Sampling using Semigradient-based Product Mixtures
• Scalable Discrete Sampling as a Multi-Armed Bandit Problem
• A Latent Slice Sampling Algorithm
• Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics