On the fundamental limitations of multi-proposal Markov chain Monte Carlo algorithms

Summary We study multi-proposal Markov chain Monte Carlo algorithms, such as multiple-try or generalized Metropolis–Hastings schemes, which have recently received renewed attention due to their amenability to parallel computing. First, we prove that no multi-proposal 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 common serial multi-proposal implementations are less efficient than single-proposal ones. Second, 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 multi-proposal implementations are fundamentally limited in the computational gain they can offer. Crucially, our results apply to arbitrary multi-proposal schemes and purely rely on the two-step structure of the associated kernels: first generate K candidate points, then select one among those. Our theoretical findings are validated through numerical simulations.