×

zbMATH — the first resource for mathematics

Markov chain Monte Carlo algorithms with sequential proposals. (English) Zbl 07270190
Summary: We explore a general framework in Markov chain Monte Carlo (MCMC) sampling where sequential proposals are tried as a candidate for the next state of the Markov chain. This sequential-proposal framework can be applied to various existing MCMC methods, including Metropolis-Hastings algorithms using random proposals and methods that use deterministic proposals such as Hamiltonian Monte Carlo (HMC) or the bouncy particle sampler. Sequential-proposal MCMC methods construct the same Markov chains as those constructed by the delayed rejection method under certain circumstances. In the context of HMC, the sequential-proposal approach has been proposed as extra chance generalized hybrid Monte Carlo (XCGHMC). We develop two novel methods in which the trajectories leading to proposals in HMC are automatically tuned to avoid doubling back, as in the No-U-Turn sampler (NUTS). The numerical efficiency of these new methods compare favorably to the NUTS. We additionally show that the sequential-proposal bouncy particle sampler enables the constructed Markov chain to pass through regions of low target density and thus facilitates better mixing of the chain when the target density is multimodal.
MSC:
62L12 Sequential estimation
65C05 Monte Carlo methods
Software:
CODA; mcmcse; R; Stan; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrieu, C.; Atchade, Y., On the efficiency of adaptive MCMC algorithms, Electron. Commun. Probab., 12, 336-349 (2007) · Zbl 1129.65006
[2] Andrieu, C., Livingstone, S.: Peskun-Tierney ordering for Markov chain and process Monte Carlo: beyond the reversible scenario. (2019). arXiv preprint arXiv:1906.06197
[3] Andrieu, C.; Moulines, É., On the ergodicity properties of some adaptive MCMC algorithms, Ann. Appl. Probab., 16, 1462-1505 (2006) · Zbl 1114.65001
[4] Andrieu, C.; Thoms, J., A tutorial on adaptive MCMC, Stat. Comput., 18, 343-373 (2008)
[5] Atchadé, Y.; Fort, G., Limit theorems for some adaptive MCMC algorithms with subgeometric kernels, Bernoulli, 16, 116-154 (2010) · Zbl 1215.60046
[6] Atchadé, YF; Fort, G., Limit theorems for some adaptive MCMC algorithms with subgeometric kernels: Part II, Bernoulli, 18, 975-1001 (2012) · Zbl 1244.60072
[7] Atchadé, YF; Rosenthal, JS, On adaptive Markov chain Monte Carlo algorithms, Bernoulli, 11, 815-828 (2005) · Zbl 1085.62097
[8] Beskos, A.; Pillai, N.; Roberts, G.; Sanz-Serna, J-M; Stuart, A., Optimal tuning of the hybrid Monte Carlo algorithm, Bernoulli, 19, 1501-1534 (2013) · Zbl 1287.60090
[9] Betancourt, M.: A conceptual introduction to Hamiltonian Monte Carlo. (2017). arXiv preprint arXiv:1701.02434
[10] Bouchard-Côté, A.; Vollmer, SJ; Doucet, A., The bouncy particle sampler: a nonreversible rejection-free Markov chain Monte Carlo method, J. Am. Stat. Assoc., 113, 855-867 (2018) · Zbl 1398.60084
[11] Calderhead, B., A general construction for parallelizing Metropolis-Hastings algorithms, Proc. Natl. Acad. Sci., 111, 17408-17413 (2014)
[12] Campos, CM; Sanz-Serna, J., Extra chance generalized hybrid Monte Carlo, J. Comput. Phys., 281, 365-374 (2015) · Zbl 1352.65007
[13] Carpenter, B.; Gelman, A.; Hoffman, MD; Lee, D.; Goodrich, B.; Betancourt, M.; Brubaker, M.; Guo, J.; Li, P.; Riddell, A., Stan: a probabilistic programming language, J. Stat. Softw., 76, 1 (2017)
[14] Dua, D., Graff, C.: UCI machine learning repository. (2017). http://archive.ics.uci.edu/ml. Accessed 17 Jan 2020
[15] Duane, S.; Kennedy, AD; Pendleton, BJ; Roweth, D., Hybrid Monte Carlo, Phys. Lett. B, 195, 216-222 (1987)
[16] Fang, Y.; Sanz-Serna, JM; Skeel, RD, Compressible generalized hybrid Monte Carlo, J. Chem. Phys., 140, 174108 (2014)
[17] Flegal, J.M., Hughes, J., Vats, D., Dai, N.: mcmcse: Monte Carlo Standard Errors for MCMC. Riverside, CA, Denver, CO, Coventry, UK, and Minneapolis, MN. R package version 1.3-2 (2017)
[18] Geyer, C.J.: Markov chain Monte Carlo maximum likelihood. Retrieved from the University of Minnesota Digital Conservancy, Interface Foundation of North America (1991)
[19] Goodman, J.; Weare, J., Ensemble samplers with affine invariance, Commun. Appl. Math. Comput. Sci., 5, 65-80 (2010) · Zbl 1189.65014
[20] Green, PJ; Mira, A., Delayed rejection in reversible jump Metropolis-Hastings, Biometrika, 88, 1035-1053 (2001) · Zbl 1099.60508
[21] Gupta, S.; Irbäc, A.; Karsch, F.; Petersson, B., The acceptance probability in the hybrid Monte Carlo method, Phys. Lett. B, 242, 437-443 (1990)
[22] Haario, H.; Saksman, E.; Tamminen, J., An adaptive Metropolis algorithm, Bernoulli, 7, 223-242 (2001) · Zbl 0989.65004
[23] Hastings, WK, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 97-109 (1970) · Zbl 0219.65008
[24] Hoffman, MD; Gelman, A., The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo, J. Mach. Learn. Res., 15, 1593-1623 (2014) · Zbl 1319.60150
[25] Horowitz, AM, A generalized guided Monte Carlo algorithm, Phys. Lett. B, 268, 247-252 (1991)
[26] Hukushima, K.; Nemoto, K., Exchange Monte Carlo method and application to spin glass simulations, J. Phys. Soc. Jpn., 65, 1604-1608 (1996)
[27] Kou, S.; Zhou, Q.; Wong, WH, Equi-energy sampler with applications in statistical inference and statistical mechanics, Ann. Stat., 34, 1581-1619 (2006) · Zbl 1246.82054
[28] Leimkuhler, B.; Reich, S., Simulating Hamiltonian dynamics (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1069.65139
[29] Liouville, J., Note on the theory of the variation of arbitrary constants, Journal de Mathématiques Pures et Appliquées, 3, 342-349 (1838)
[30] Liu, JS; Liang, F.; Wong, WH, The multiple-try method and local optimization in Metropolis sampling, J. Am. Stat. Assoc., 95, 121-134 (2000) · Zbl 1072.65505
[31] Marinari, E.; Parisi, G., Simulated tempering: a new Monte Carlo scheme, EPL (Europhys. Lett.), 19, 451 (1992)
[32] Metropolis, N.; Rosenbluth, AW; Rosenbluth, MN; Teller, AH; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[33] Mira, A., On metropolis-hastings algorithms with delayed rejection, Metron, 59, 231-241 (2001) · Zbl 0998.65502
[34] Mira, A., Møller, J., Roberts, G.O.: Perfect slice samplers. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 63, 593-606 (2001) · Zbl 0993.65015
[35] Neal, RM, An improved acceptance procedure for the hybrid Monte Carlo algorithm, J. Comput. Phys., 111, 194-203 (1994) · Zbl 0797.65115
[36] Neal, RM, Slice sampling, Ann. Stat., 31, 705-767 (2003) · Zbl 1051.65007
[37] Neal, R.M.: MCMC using Hamiltonian dynamics. In: Brooks, S., Gelman, A., Jones, G., Meng, X.-L. (eds.) Handbook of Markov chain Monte Carlo, pp. 113-162. CRC press (2011)
[38] Peskun, PH, Optimum Monte-Carlo sampling using markov chains, Biometrika, 60, 607-612 (1973) · Zbl 0271.62041
[39] Peters, EA, Rejection-free Monte Carlo sampling for general potentials, Phys. Rev. E, 85, 026703 (2012)
[40] Plummer, M.; Best, N.; Cowles, K.; Vines, K., CODA: convergence diagnosis and output analysis for MCMC, R News, 6, 7-11 (2006)
[41] R Core Team.: R: a Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna (2018). https://www.R-project.org/
[42] Roberts, GO; Rosenthal, JS, Optimal scaling of discrete approximations to Langevin diffusions, J. R. Stat. Soc. Ser. B (Stat. Methodol.), 60, 255-268 (1998) · Zbl 0913.60060
[43] Roberts, GO; Rosenthal, JS, Convergence of slice sampler Markov chains, J. R. Stat. Soc. Ser. B (Stat. Methodol.), 61, 643-660 (1999) · Zbl 0929.62098
[44] Roberts, GO; Rosenthal, JS, Coupling and ergodicity of adaptive Markov chain Monte Carlo algorithms, J. Appl. Probab., 44, 458-475 (2007) · Zbl 1137.62015
[45] Roberts, GO; Gelman, A.; Gilks, WR, Weak convergence and optimal scaling of random walk Metropolis algorithms, Ann. Appl. Probab., 7, 110-120 (1997) · Zbl 0876.60015
[46] Sexton, J.; Weingarten, D., Hamiltonian evolution for the hybrid Monte Carlo algorithm, Nucl. Phys. B, 380, 665-677 (1992)
[47] Sherlock, C.; Fearnhead, P.; Roberts, GO, The random walk Metropolis: Linking theory and practice through a case study, Stat. Sci., 25, 172-190 (2010) · Zbl 1328.60177
[48] Sohl-Dickstein, J., Mudigonda, M., DeWeese, M.R.: Hamiltonian Monte Carlo without detailed balance. (2014). arXiv preprint arXiv:1409.5191
[49] Tierney, L., A note on Metropolis-Hastings kernels for general state spaces, Ann. Appl. Probab., 8, 1-9 (1998) · Zbl 0935.60053
[50] Tierney, L.; Mira, A., Some adaptive Monte Carlo methods for Bayesian inference, Stat. Med., 18, 2507-2515 (1999)
[51] Vanetti, P., Bouchard-Côté, A., Deligiannidis, G., Doucet, A.: Piecewise deterministic Markov chain Monte Carlo. (2017) arXiv preprint arXiv:1707.05296
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.