Research map / Probabilistic and scientific modeling / Variational and generative sampling
Multi-Marginal Couplings for Metropolis--Hastings
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies multi-marginal coupling of C Metropolis-Hastings chains via a cluster-count objective, proposing list-level coupling and an adaptive Poisson-matching grand coupling whose cost scales with chain count rather than dimension.
Problem
Coupling-based MCMC convergence diagnostics need efficient grand couplings of multiple chains so they coalesce quickly; pairwise star or random-pair couplings are suboptimal and Poisson matching is expensive in high dimensions.
Approach
Formulates multi-marginal coupling as minimizing expected number of distinct values, derives bounds via list-level coupling and pairwise matching, and makes Poisson Monte Carlo practical by using the uniform mixture of target kernels as a shared proposal so the density ratio is bounded by C, giving dimension-independent runtime.
Key results
- Adaptive Poisson matching coupling of MH chains reduces meeting times relative to star-coupling baselines, with up to 50% reduction claimed in the abstract.
- Runtime of the mixture-barycenter proposal stays nearly constant across dimensions 2^0 to 2^9 for C=32, whereas a single-Gaussian proposal grows rapidly.
- For shifted exponential targets, Poisson matching attains the optimal G* = C - (C-1)e^{-1}.
Surprising findings
- The augmented (proposal-acceptance) lifted construction gives a higher meeting probability than direct coupling of the MH kernel.
- A fixed reference chain works best for the baseline pairwise couplings, whereas the multi-marginal setting benefits from changing matches across iterations.
Limitations
- Greedy list-level strategy does not attain the lower bound in general.
- Poisson matching does not generally maximize all pairwise matches simultaneously; list-level coupling outperforms it for small C on sparse discrete examples.
- Experiments are limited to synthetic targets (Gaussian, Cauchy, discrete, exponential) and random-walk MH.
Experimental setup
Datasets: randomly generated sparse discrete distributions (|X|=60, support 5) synthetic Gaussian and Student-t targets
Benchmarks: synthetic discrete multi-marginal coupling shifted exponential multi-marginal coupling RWMH on Gaussian target in d dimensions RWMH on Cauchy target with Student-t proposal
Metrics: expected number of distinct values E[G] average meeting time runtime vs dimension
Baselines: star coupling with maximal coupling (two-step) star coupling with maximal coupling (one-step) random anchor random sequence single-Gaussian proposal Poisson Monte Carlo
Builds on: maximal coupling Poisson Monte Carlo Poisson matching lemma grand coupling convergence diagnostics optimal scaling for random-walk Metropolis
Closest papers by meaning
- Estimating Convergence of Markov chains with L-Lag Couplings (NeurIPS 2019 · similarity 0.93)
- Scalable Metropolis-Hastings for Exact Bayesian Inference with Large Datasets (ICML 2019 · similarity 0.90)
- Stochastic Quasi-Newton Langevin Monte Carlo (ICML 2016 · similarity 0.88)
- Multi-fidelity Monte Carlo: a pseudo-marginal approach (NeurIPS 2022 · similarity 0.88)
- Large-Scale Stochastic Sampling from the Probability Simplex (NeurIPS 2018 · similarity 0.88)
- Parallelizing MCMC Across the Sequence Length (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.