{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T20:27:00Z","timestamp":1793046420805,"version":"4.5.0"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T00:00:00Z","timestamp":1742515200000},"content-version":"vor","delay-in-days":79,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,3,16]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>We study multi-proposal Markov chain Monte Carlo algorithms, such as multiple-try or generalized Metropolis\u2013Hastings 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.<\/jats:p>","DOI":"10.1093\/biomet\/asaf019","type":"journal-article","created":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T09:50:16Z","timestamp":1742723416000},"source":"Crossref","is-referenced-by-count":5,"title":["On the fundamental limitations of multi-proposal Markov chain Monte Carlo algorithms"],"prefix":"10.1093","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8109-6849","authenticated-orcid":false,"given":"F","family":"Pozza","sequence":"first","affiliation":[{"name":"Department of Decision Sciences, Bocconi University , via Roentgen 1 , Milan 20136,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G","family":"Zanella","sequence":"additional","affiliation":[{"name":"Department of Decision Sciences, Bocconi University , via Roentgen 1 , Milan 20136,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2025,3,21]]},"reference":[{"key":"2025062913120389500_asaf019-B2","first-page":"4022","article-title":"Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles","volume":"4","author":"Andrieu","year":"2024","journal-title":"Ann. Appl. Prob"},{"key":"2025062913120389500_asaf019-B1","doi-asserted-by":"crossref","first-page":"842","DOI":"10.3150\/15-BEJ785","article-title":"Uniform ergodicity of the iterated conditional SMC and geometric ergodicity of particle Gibbs samplers","volume":"24","author":"Andrieu","year":"2018","journal-title":"Bernoulli"},{"key":"2025062913120389500_asaf019-B3","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1016\/j.spa.2011.11.004","article-title":"Scaling analysis of multiple-try MCMC methods","volume":"122","author":"B\u00e9dard","year":"2012","journal-title":"Stoch. Proces. Appl"},{"key":"2025062913120389500_asaf019-B4","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s11222-016-9640-7","article-title":"The use of a single pseudo-sample in approximate Bayesian computation","volume":"27","author":"Bornn","year":"2017","journal-title":"Statist. Comp"},{"key":"2025062913120389500_asaf019-B5","doi-asserted-by":"crossref","first-page":"17408","DOI":"10.1073\/pnas.1408184111","article-title":"A general construction for parallelizing Metropolis-Hastings algorithms","volume":"111","author":"Calderhead","year":"2014","journal-title":"Proc. Nat. Acad. Sci"},{"key":"2025062913120389500_asaf019-B6","first-page":"25842","author":"Chang","year":"2022"},{"key":"2025062913120389500_asaf019-B7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s11222-006-9009-4","article-title":"Acceleration of the multiple-try Metropolis algorithm using antithetic and stratified sampling","volume":"17","author":"Craiu","year":"2007","journal-title":"Statist. Comp"},{"key":"2025062913120389500_asaf019-B8","doi-asserted-by":"crossref","first-page":"1986","DOI":"10.3150\/21-BEJ1408","article-title":"An adaptive multiple-try Metropolis algorithm","volume":"28","author":"Fontaine","year":"2022","journal-title":"Bernoulli"},{"key":"2025062913120389500_asaf019-B9","volume-title":"Understanding Molecular Simulation: from Algorithms to Applications","author":"Frenkel","year":"1996"},{"key":"2025062913120389500_asaf019-B10","first-page":"1","article-title":"Improving multiple-try Metropolis with local balancing","volume":"24","author":"Gagnon","year":"2023","journal-title":"J. Mach. Learn. Res"},{"key":"2025062913120389500_asaf019-B11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume":"57","author":"Hastings","year":"1970","journal-title":"Biometrika"},{"key":"2025062913120389500_asaf019-B12","doi-asserted-by":"crossref","first-page":"105106","DOI":"10.1016\/j.jmva.2022.105106","article-title":"Generating MCMC proposals by randomly rotating the regular simplex","volume":"194","author":"Holbrook","year":"2023","journal-title":"J. Mult. Anal"},{"key":"2025062913120389500_asaf019-B13","doi-asserted-by":"crossref","DOI":"10.1090\/mbk\/107","volume-title":"Markov Chains and Mixing Times","author":"Levin","year":"2017","edition":"2nd ed"},{"key":"2025062913120389500_asaf019-B14","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1080\/01621459.2000.10473908","article-title":"The multiple-try method and local optimization in Metropolis sampling","volume":"95","author":"Liu","year":"2000","journal-title":"J. Am. Statist. Assoc"},{"key":"2025062913120389500_asaf019-B15","first-page":"581","author":"Pandolfi","year":"2010"},{"key":"2025062913120389500_asaf019-B16","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1093\/biomet\/60.3.607","article-title":"Optimum Monte-Carlo sampling using Markov chains","volume":"60","author":"Peskun","year":"1973","journal-title":"Biometrika"},{"key":"2025062913120389500_asaf019-B17","first-page":"207","article-title":"Parallel computing and Monte Carlo algorithms","volume":"4","author":"Rosenthal","year":"2000","journal-title":"Far East J. Theor. Statist"},{"key":"2025062913120389500_asaf019-B18","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1093\/biomet\/asx031","article-title":"Pseudo-marginal Metropolis\u2013Hastings sampling using averages of unbiased estimators","volume":"104","author":"Sherlock","year":"2017","journal-title":"Biometrika"},{"key":"2025062913120389500_asaf019-B19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aoap\/1027961031","article-title":"A note on Metropolis-Hastings kernels for general state spaces","volume":"8","author":"Tierney","year":"1998","journal-title":"Ann. Appl. Prob."},{"key":"2025062913120389500_asaf019-B20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s11222-023-10241-3","article-title":"Convergence rate of multiple-try Metropolis independent sampler","volume":"33","author":"Yang","year":"2023","journal-title":"Statist. Comp"},{"key":"2025062913120389500_asaf019-B21","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1080\/01621459.2019.1585255","article-title":"Informed proposals for local MCMC in discrete spaces","volume":"115","author":"Zanella","year":"2020","journal-title":"J. Am. Statist. Assoc"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asaf019\/62520369\/asaf019.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/2\/asaf019\/62520369\/asaf019.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/112\/2\/asaf019\/62520369\/asaf019.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T17:12:10Z","timestamp":1751217130000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/doi\/10.1093\/biomet\/asaf019\/8090025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,16]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaf019","relation":{},"ISSN":["1464-3510"],"issn-type":[{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]},"article-number":"asaf019"}}