On parallelizable Markov chain Monte Carlo algorithms with waste-recycling. (English) Zbl 1406.65008
Summary: Parallelizable Markov chain Monte Carlo (MCMC) generates multiple proposals and parallelizes the evaluations of the likelihood function on different cores at each MCMC iteration. Inspired by B. Calderhead [“A general construction for parallelizing Metropolisastings algorithms”, Proc. Natl. Acad. Sci. USA 111, No. 49, 17408–17413 (2014; doi:10.1073/pnas.1408184111)], we introduce a general ‘waste-recycling’ framework for parallelizable MCMC, under which we show that using weighted samples from waste-recycling is preferable to resampling in terms of both statistical and computational efficiencies. We also provide a simple-to-use criteria, the generalized effective sample size, for evaluating efficiencies of parallelizable MCMC algorithms, which applies to both the waste-recycling and the vanilla versions. A moment estimator of the generalized effective sample size is provided and shown to be reasonably accurate by simulations.
MSC:
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 65C05 | Monte Carlo methods |
| 60J22 | Computational methods in Markov chains |
Keywords:
weighted samples; Markov chain Monte Carlo; Rao-Blackwellization; parallel computation; effective sample size; estimation efficiencySoftware:
BayesDAReferences:
| [1] | Andrews, DWK, Heteroskedasticity and autocorrelation consistent covariance matrix estimation, Econometrica, 59, 817-858, (1991) · Zbl 0732.62052 · doi:10.2307/2938229 |
| [2] | Calderhead, B, A general construction for parallelizing metropolis-Hastings algorithms, Proc. Natl. Acad. Sci., 111, 17408-17413, (2014) · doi:10.1073/pnas.1408184111 |
| [3] | Chen, L.Y., Qin, Z., Liu, J.S.: Exploring hybrid Monte Carlo in Bayesian computation. Bayesian methods: with applications to science, policy and official statistics. In: Selected Papers from ISBA 2000, pp. 71-80 (2001) |
| [4] | Delmas, JF; Jourdain, B, Does waste recycling really improve the multi-proposal metropolis-Hastings algorithm? an analysis based on control variates, J. Appl. Probab., 46, 938-959, (2009) · Zbl 1187.60056 · doi:10.1239/jap/1261670681 |
| [5] | Douc, R; Robert, CP, A vanilla Rao-blackwellization of metropolis-Hastings algorithms, Ann. Stat., 39, 261-277, (2011) · Zbl 1209.62023 · doi:10.1214/10-AOS838 |
| [6] | Duane, S; Kennedy, AD; Pendleton, BJ; Roweth, D, Hybrid Monte Carlo, Phys. Lett. B, 195, 216-222, (1987) · doi:10.1016/0370-2693(87)91197-X |
| [7] | Frenkel, D, Speed-up of Monte Carlo simulations by sampling of rejected states, Proc. Natl. Acad. Sci., 101, 17571-17575, (2004) · doi:10.1073/pnas.0407950101 |
| [8] | Frenkel, D.: Waste-recycling Monte Carlo. In: Ferrario, M., Ciccotti, G., Binder, K. (eds.) Computer Simulations in Condensed Matter Systems: From Materials to Chemical Biology, vol. 1. Lecture Notes in Physics, vol. 703, pp. 127-137. Springer, Berlin. doi:10.1007/3-540-35273-2_4 (2006) |
| [9] | Gelman, A; Meng, X, A note on bivariate distributions that are conditionally normal, Am. Stat., 45, 125-126, (1991) |
| [10] | Gelman, A., Carlin, J., Stern, H., Dunson, D., Vehtari, A., Rubin, D.: Bayesian Data Analysis, 3rd edn. Chapman and Hall, Boca Raton (2013) · Zbl 1279.62004 |
| [11] | Hastings, W, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 97-109, (1970) · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97 |
| [12] | Kass, RE; Carlin, BP; Gelman, A; Neal, RM, Markov chain Monte Carlo in practice: a roundtable discussion, Am. Stat., 52, 93-100, (1998) |
| [13] | Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, Berlin (2001) · Zbl 0991.65001 |
| [14] | 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 · doi:10.1080/01621459.2000.10473908 |
| [15] | 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 · doi:10.1063/1.1699114 |
| [16] | Müller, UK, HAC corrections for strongly autocorrelated time series, J. Bus. Econ. Stat., 32, 311-322, (2014) · doi:10.1080/07350015.2014.931238 |
| [17] | Neal, RM, An improved acceptance procedure for the hybrid Monte Carlo algorithm, J. Comput. Phys., 111, 194-203, (1994) · Zbl 0797.65115 · doi:10.1006/jcph.1994.1054 |
| [18] | Qin, ZS; Liu, JS, Multipoint metropolis method with application to hybrid Monte Carlo, J. Comput. Phys., 172, 827-840, (2001) · Zbl 1158.65300 · doi:10.1006/jcph.2001.6860 |
| [19] | Ritter, C; Tanner, MA, Facilitating the Gibbs sampler: the Gibbs stopper and the griddy-Gibbs sampler, J. Am. Stat. Assoc., 87, 861-868, (1992) · doi:10.1080/01621459.1992.10475289 |
| [20] | Roberts, GO; Tweedie, RL, Exponential convergence of Langevin distributions and their discrete approximations, Bernoulli, 2, 341-363, (1996) · Zbl 0870.60027 · doi:10.2307/3318418 |
| [21] | Tjelmeland, H.: Using all Metropolis-Hastings proposals to estimate mean values. Technical Reports, Norwegian University of Science and Technology. Trondheim, Norway (2004) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
