Ai-Sampler: Adversarial Learning of Markov kernels with involutive maps

Evgenii Egorov, Riccardo Valperga, Efstratios Gavves

Abstract

Sampling from complex, high-dimensional probability distributions is a fundamental challenge in Bayesian statistics. Traditional Markov Chain Monte Carlo (MCMC) methods often struggle with poor mixing in multimodal landscapes, where high-energy barriers prevent efficient exploration. We introduce Ai-Sampler, a novel framework that trains MCMC transition kernels via adversarial learning. By utilizing time-reversible neural networks and a discriminator constrained by geometric symmetries, Ai-Sampler learns to navigate low-density regions and jump between modes effectively. Our results demonstrate significant improvements in Effective Sample Size (ESS) and computational efficiency compared to standard Hamiltonian Monte Carlo (HMC) on both synthetic and real-world Bayesian inference tasks.

Introduction

MCMC is a gold-standard tool for sampling, yet it faces two primary hurdles: mixing issues in multimodal distributions and the lack of a straightforward objective function for optimization. Traditional samplers like HMC often fail to explore the entire distribution when modes are separated by vast "valleys" of near-zero density. Ai-Sampler addresses these by treating the transition kernel as a generative model, optimized through an adversarial game to "learn" effective jumps between modes.

Methodology

The core of Ai-Sampler is a trainable transition kernel designed as an involutive map. To maintain the validity of the Markov chain (specifically detailed balance), the authors employ time-reversible neural networks.

Construction of the involutive kernel using a composition of maps to ensure reversibility.

The proposal map is constructed such that it is an involution by design, removing the need for complex penalty terms to enforce reversibility. Training is conducted through an adversarial objective where a discriminator distinguishes between target samples and those proposed by the kernel. A key theoretical insight is the enforcement of $C_2$-equivariance in the discriminator's architecture, which stabilizes training by restricting the function space to respect the inherent symmetries of the MCMC process.

Experimental Setup

The framework was evaluated on two main fronts:

  1. Synthetic 2D Densities: Challenging multimodal distributions including mixtures of Gaussians (mog2, mog6) and concentric rings (ring, ring5).
  2. Bayesian Logistic Regression: High-dimensional real-world tasks using the Heart, German, and Australian datasets.

Results and Discussion

Ai-Sampler exhibits superior mixing capabilities, particularly in multimodal settings where traditional methods fail. On the mog2 and mog6 tasks, it achieved the maximum possible Effective Sample Size (ESS) of 1000, while HMC remained trapped in local modes with scores as low as 0.8.

Ai-Sampler trajectories (red) demonstrating efficient mode-jumping across multimodal Gaussian mixtures.

Quantitatively, Ai-Sampler outperformed HMC by orders of magnitude in ESS per second (ESS/s). For instance, on the mog2 dataset, it reached ~1052 ESS/s compared to HMC’s 0.4. In Bayesian logistic regression, it matched HMC's accuracy while providing significantly higher throughput, especially on the Australian dataset where it was nearly 10x faster. Notably, once trained, Ai-Sampler is gradient-free and highly parallelizable on GPU hardware, allowing for near-linear scaling when running thousands of chains.

Conclusion and Future Work

Ai-Sampler successfully bridges the gap between deep generative modeling and MCMC. While it requires an initial training overhead (typically 2–10 minutes on an A100 GPU), its sampling efficiency makes it ideal for large-scale or repeated sampling tasks. Future work may involve integrating these local transition kernels into global generative models like Normalizing Flows to better capture complex global structures through local movements.

Summary updated

Abstract

Markov chain Monte Carlo methods have become popular in statistics as versatile techniques to sample from complicated probability distributions. In this work, we propose a method to parameterize and train transition kernels of Markov chains to achieve efficient sampling and good mixing. This training procedure minimizes the total variation distance between the stationary distribution of the chain and the empirical distribution of the data. Our approach leverages involutive Metropolis-Hastings kernels constructed from reversible neural networks that ensure detailed balance by construction. We find that reversibility also implies $C_2$-equivariance of the discriminator function which can be used to restrict its function space.
BibTeX
@inproceedings{egorov2024ai,
  author = {Evgenii Egorov and Riccardo Valperga and Efstratios Gavves},
  title = {{Ai-Sampler: Adversarial Learning of Markov kernels with involutive maps}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=xFCA2yWVs4},
}
Figure