Multi-Marginal Couplings for Metropolis–Hastings
Buu Phan, Gergely Flamich, Ashish Khisti, Shahab Asoodeh · 2026
Read Multi-Marginal Couplings for Metropolis–Hastings by Buu Phan, Gergely Flamich, Ashish Khisti, Shahab Asoodeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12807.txt.
Introduction
Phan, Flamich, Khisti and Asoodeh address a practical problem in Markov chain Monte Carlo sampling: judging when several chains have settled. They couple multiple Metropolis-Hastings chains using multi-marginal coupling, then build a shared-randomness Poisson Monte Carlo construction with an adaptive update rule that avoids a dimension-linked slowdown. In tests their approach joins chains sooner, cutting meeting times by up to half.
Catalog record
| CREATOR | Buu Phan, Gergely Flamich, Ashish Khisti, Shahab Asoodeh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90060 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12807
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Marginal Couplings for Metropolis–Hastings Buu Phan, Gergely Flamich, Ashish Khisti, Shahab Asoodeh Abstract Convergence diagnosis for Markov chain Monte Carlo is a matter of fundamental importance in computational statistics: it determines the resources allocated to a particular sampling problem and influences the practitioner’s view of the quality of estimates obtained from a Markov chain. Motivated by this, we contribute to the emerging class of coupling-based convergence diagnostic algorithms. Concretely, we study coupling multiple Metropolis–Hastings chains using multi-marginal coupling. We introduce a natural objective for this setting and establish lower and upper bounds by drawing connections to list-level distribution coupling and distributed pairwise-matching problems. This analysis ultimately leads to a shared-randomness Poisson Monte Carlo construction for coupling multiple Markov chains. In this process, we avoid a key dimension-dependent bottleneck in the runtime complexity of classical Poisson Monte Carlo by developing an adaptive rule for updating the point process, yielding significant gains in high-dimensional settings. Experiments on grand couplings of Markov chains show that our methods improve coalescence rates across dimensions, reducing meeting times by up to 50 % 50\% compared with existing baselines. 1 Introduction Markov chain Monte Carlo (MCMC) is a central methodology for sampling from complex probability distributions when exact simulation techniques are computationally intractable. It proceeds by constructing a Markov chain whose stationary distribution matches a target distribution of interest, allowing expectations under the target law to be approximated from the chain trajectory. Because of its broad applicability in Bayesian inference, statistical physics, and machine learning, MCMC has become one of the most widely used tools for high-dimensional probabilistic computation. A fundamental challenge in MCMC is convergence diagnosis: determining whether the chain has run long enough for its distribution to be sufficiently close to stationarity. Classical approaches often rely on running multiple independent chains with different initializations and comparing their behavior, as in the Gelman–Rubin diagnostic and its extensions [ 3 , 11 ] . Coupling provides another principled alternative by jointly evolving chains from different initializations and using their meeting behavior as a diagnostic signal, where a meeting occurs when two or more chains coalesce in the same state [ 2 , 4 ] . As the effectiveness of such diagnostics depends on how quickly coalescence occurs, several studies have examined the design of efficient couplings, with a primary focus on two chains [ 29 ] . By comparison, the multi-chain coupling setting has received relatively limited attention, despite the existence of convergence diagnostics based on grand couplings, which jointly evolve chains from multiple initial states until they coalesce [ 16 ] . Coupling multiple chains is not as simple as pairwise coupling. A natural first strategy is to construct a multi-chain coupling using pairwise coupling as a building block. For example, we could have a “server-client” topology, in which we couple each chain to a distinguished reference chain; alternatively, we could randomly choose coupling partners at each transition [ 29 , 2 ] . Such approaches, however, can be highly suboptimal: they may spend effort attempting to couple chains whose states are far apart, and thus whose coalescence is unlikely. A more effective strategy should preferentially match chains that are close under the transition kernel, but identifying such pairs is challenging in high-dimensional settings. In this work, we develop adaptive coupling strategies in which the joint construction itself determines which chains should meet by connecting the multi-marginal setting to list-level coupling and distributed matching. This strategy avoids committing to fixed partners, promotes coalescence among compatible chains, and leads to a kernel-coupling construction with effective meeting behavior and favorable runtime scaling in high-dimensional multi-chain settings. In particular, our contributions are: 1. In Section 2 , we study multi-chain coupling from a multi-marginal perspective and analyze theoretical properties of the resulting meeting behavior through list-level coupling (membership inclusion), and distributed matching formulations. 2. In Section 3 , we introduce an efficient Poisson-matching scheme for coupling multiple Metropolis–Hastings kernels. The scheme uses a flexible adaptive proposal update that yields runtime scaling primarily with the number of chains rather than the dimension. 3. In Section 4 , we show experimentally that our method outperforms natural grand-coupling baselines, substantially reducing coalescence times in high-dimensional settings when using many chains. 2 Algorithms for Multi-Marginals Coupling Before discussing the multi-marginal formulation, we recall the pairwise case. For probability measures P and Q , the largest possible agreement probability over all couplings, \Pr(X^{P}=X^{Q}), is 1-d_{\mathrm{TV}}(P,Q) , where d_{\mathrm{TV}}(P,Q) is the total-variation distance. A coupling attaining this value is called a maximal coupling [ 19 ] ; we review its achievability in Appendix A.1 . When there are more than two marginals, there is no canonical notion of agreement. Consider C random variables X^{1},\dots,X^{C} with marginals X^{i}\sim P^{i} . Natural objectives could be to maximize the probability of full coalescence or the probability of at least one pairwise match, as studied in the multi-marginal coupling setting of 1 : \Pr(X^{1}=X^{2}=\cdots=X^{C})\qquad\text{or}\qquad\Pr(\exists\,i\neq j:X^{i}=X^{j}). For coupling multiple Markov chains, coalescence is expected to occur progressively over iterations. Therefore, full coalescence is often too stringent, especially as C grows. In contrast, the existence of a single pairwise match does not distinguish between a coupling that merges two variables and one that merges many. These observations motivate the following measure of partial coalescence. Problem setup. To quantify partial coalescence, we consider the optimization problem \mathbf{G}^{*}=\inf_{\gamma\in\Gamma(P^{1},\dots,P^{C})}\mathbb{E}_{\gamma}[G],\qquad G\triangleq\bigl|\{\text{unique values among }X^{1},\dots,X^{C}\}\bigr|, (1) where \Gamma(P^{1},\dots,P^{C}) is the set of all couplings of P^{1},\dots,P^{C} and G is the number of distinct realized values among the C variables. It directly measures progressive coalescence: G{=}C corresponds to complete separation, G{=}1 to full coalescence, and intermediate values to partial merges. The structure of an optimal coupling for equation 1 , and how to construct one, are not immediately clear. A natural first attempt is to extend maximal coupling by selecting one variable as an anchor and coupling all other variables to it. However, this construction is asymmetric and designed to maximize agreement with the chosen anchor, rather than directly minimize the number of distinct realized values. This section will show that this objective admits the following informative lower and upper bounds, shown Theorem 2.1 . Theorem 2.1 . Given probability measures P^{1},\dots,P^{C} , and a permutation \sigma over C elements, define \bar{\nu}^{\sigma(k)}(\mathrm{d}x)\coloneqq\frac{1}{C-k}\sum_{j=k+1}^{C}P^{\sigma(j)}(\mathrm{d}x),\qquad k=1,\dots,C-1. Moreover, let E_{m}(P\|Q)=\int\max\{P(x)-mQ(x),0\}\,\mathrm{d}x denote the Hockey-Stick divergence [ 26 ] with m\geq 1 . Then, the optimal value \mathbf{G}^{*} in equation 1 satisfies 1+\sup_{\sigma}\sum_{k=1}^{C-1}E_{C-k}\!\left(P^{\sigma(k)}\middle\|\bar{\nu}^{\sigma(k)}\right)\leq\mathbf{G}^{*}\leq\frac{1+\sqrt{1+8\sum_{1\leq i<j\leq C}\frac{2\,d_{\mathrm{TV}}(P^{i},P^{j})}{1+d_{\mathrm{TV}}(P^{i},P^{j})}}}{2}. (2) Both the lower and upper bounds are tight at the two extreme configurations. If X^{1}=\cdots=X^{C} almost surely, then d_{\mathrm{TV}}(P^{i},P^{j})=0 for all i\neq j and G=1 , so both bounds hold with equality. Conversely, if X^{i}\neq X^{j} almost surely for all i\neq j , then G=C , and both bounds are again tight. Beyond these extremes, the lower bound is tight when C=2 , in which case the problem reduces to the maximal coupling of two variables, and in certain other special cases; see Example 1 and Appendix C . We now establish Theorem 2.1 and develop coupling constructions motivated by the structure of these bounds. 2.1 Lower Bound with List-Level Coupling To establish the lower bound in Theorem 2.1 , we first rewrite the expected cluster count in terms of list-level inclusion probabilities. Fixing any ordering \sigma(1),\dots,\sigma(C)