On the fundamental limitations of multi-proposal Markov chain Monte Carlo algorithms
成果类型：
Article
署名作者：
Pozza, F.; Zanella, G.
署名单位：
Bocconi University
刊物名称：
BIOMETRIKA
ISSN/ISSBN：
0006-3444
DOI：
10.1093/biomet/asaf019
发表日期：
2025
关键词：
摘要：
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.