# On the fundamental limitations of multiproposal Markov chain Monte Carlo algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2024.

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

- [Variational predictive resampling](https://mlsanity.com/paper/2605.11168/) (2026)

## Abstract (arXiv)

We study multiproposal Markov chain Monte Carlo algorithms, such as Multiple-try or generalised Metropolis-Hastings schemes, which have recently received renewed attention due to their amenability to parallel computing. First, we prove that no multiproposal scheme can speed-up convergence relative to the corresponding single proposal scheme by more than a factor of K, where K denotes the number of proposals at each iteration. This result applies to arbitrary target distributions and it implies that serial multiproposal implementations are always less efficient than single proposal ones. Secondly, we consider log-concave distributions over Euclidean spaces, proving that, in this case, the speed-up is at most logarithmic in K, which implies that even parallel multiproposal implementations are fundamentally limited in the computational gain they can offer. Crucially, our results apply to arbitrary multiproposal schemes and purely rely on the two-step structure of the associated kernels (i.e. first generate K candidate points, then select one among those). Our theoretical findings are validated through numerical simulations.