# Improving multiple-try Metropolis with local balancing

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 21 Nov 2022.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [The Barker proposal: combining robustness and efficiency in gradient-based MCMC](https://mlsanity.com/paper/1908.11812/) (2019)
- [Optimal Scaling for Locally Balanced Proposals in Discrete Spaces](https://mlsanity.com/paper/2209.08183/) (2022)
- [LSB: Local Self-Balancing MCMC in Discrete Spaces](https://mlsanity.com/paper/2109.03867/) (2021)
- [Optimal design of the Barker proposal and other locally-balanced Metropolis-Hastings algorithms](https://mlsanity.com/paper/2201.01123/) (2022)
- [A fresh take on 'Barker dynamics' for MCMC](https://mlsanity.com/paper/2012.09731/) (2020)
- [Metropolis-Hastings with Averaged Acceptance Ratios](https://mlsanity.com/paper/2101.01253/) (2020)
- [Informed reversible jump algorithms](https://mlsanity.com/paper/1911.02089/) (2019)
- [Optimal scaling of random-walk Metropolis algorithms using Bayesian large-sample asymptotics](https://mlsanity.com/paper/2104.06384/) (2021)
- [Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems](https://mlsanity.com/paper/2207.00689/) (2022)
- [An asymptotic Peskun ordering and its application to lifted samplers](https://mlsanity.com/paper/2003.05492/) (2020)
- [On the Theoretical Properties of the Exchange Algorithm](https://mlsanity.com/paper/2005.09235/) (2020)
- [Weak Convergence and Optimal Tuning of the Reversible Jump Algorithm](https://mlsanity.com/paper/1612.05653/) (2016)

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

- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)
- [Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces](https://mlsanity.com/paper/2404.03867/) (2024)
- [Importance is Important: Generalized Markov Chain Importance Sampling Methods](https://mlsanity.com/paper/2304.06251/) (2023)
- [Enhancing Gradient-based Discrete Sampling via Parallel Tempering](https://mlsanity.com/paper/2502.19240/) (2025)
- [Bayesian Nonlinear PDE Inference via Gaussian Process Collocation with Application to the Richards Equation](https://mlsanity.com/paper/2510.23550/) (2025)

## Abstract (arXiv)

Multiple-try Metropolis (MTM) is a popular Markov chain Monte Carlo method with the appealing feature of being amenable to parallel computing. At each iteration, it samples several candidates for the next state of the Markov chain and randomly selects one of them based on a weight function. The canonical weight function is proportional to the target density. We show both theoretically and empirically that this weight function induces pathological behaviours in high dimensions, especially during the convergence phase. We propose to instead use weight functions akin to the locally-balanced proposal distributions of Zanella (2020), thus yielding MTM algorithms that do not exhibit those pathological behaviours. To theoretically analyse these algorithms, we study the high-dimensional performance of ideal schemes that can be thought of as MTM algorithms which sample an infinite number of candidates at each iteration, as well as the discrepancy between such schemes and the MTM algorithms which sample a finite number of candidates. Our analysis unveils a strong distinction between the convergence and stationary phases: in the former, local balancing is crucial and effective to achieve fast convergence, while in the latter, the canonical and novel weight functions yield similar performance. Numerical experiments include an application in precision medicine involving a computationally-expensive forward model, which makes the use of parallel computing within MTM iterations beneficial.