×

Connecting the dots: numerical randomized Hamiltonian Monte Carlo with state-dependent event rates. (English) Zbl 07633317

Summary: Numerical generalized randomized Hamiltonian Monte Carlo is introduced, as a robust, easy to use and computationally fast alternative to conventional Markov chain Monte Carlo methods for continuous target distributions. A wide class of piecewise deterministic Markov processes generalizing Randomized HMC (Bou-Rabee and Sanz-Serna) by allowing for state-dependent event rates is defined. Under very mild restrictions, such processes will have the desired target distribution as an invariant distribution. Second, the numerical implementation of such processes, based on adaptive numerical integration of second order ordinary differential equations (ODEs) is considered. The numerical implementation yields an approximate, yet highly robust algorithm that, unlike conventional Hamiltonian Monte Carlo, enables the exploitation of the complete Hamiltonian trajectories (hence, the title). The proposed algorithm may yield large speedups and improvements in stability relative to relevant benchmarks, while incurring numerical biases that are negligible relative to the overall Monte Carlo errors. Granted access to a high-quality ODE code, the proposed methodology is both easy to implement and use, even for highly challenging and high-dimensional target distributions. Supplementary materials for this article are available online.

MSC:

62-XX Statistics

Software:

Stan; NUTS; BayesDA; tmg; Gromacs

References:

[1] Abraham, M. J.; Murtola, T.; Schulz, R.; Páll, S.; Smith, J. C.; Hess, B.; Lindahl, E., “GROMACS: High Performance Molecular Simulations Through Multi-Level Parallelism from Laptops to Supercomputers, SoftwareX, 1-2, 19-25 (2015) · doi:10.1016/j.softx.2015.06.001
[2] Andersen, H. C., “Molecular Dynamics Simulations at Constant Pressure and/or Temperature, The Journal of Chemical Physics, 72, 2384-2393 (1980) · doi:10.1063/1.439486
[3] Bierkens, J.; Fearnhead, P.; Roberts, G., “The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data, The Annals of Statistics, 47, 1288-1320 (2019) · Zbl 1417.65008 · doi:10.1214/18-AOS1715
[4] Bierkens, J.; Grazzi, S.; Kamatani, K.; Roberts, G., The Boomerang Sampler, arXiv:2006.13777 (2020)
[5] Bou-Rabee, N.; Eberle, A., Couplings for Andersen Dynamics, arXiv:2009.14239 (2020) · Zbl 1492.37079
[6] Bou-Rabee, N.; Eberle, A., Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo, arXiv:2105.00887 (2021) · Zbl 07634385
[7] Bou-Rabee, N.; Sanz-Serna, J. M., “Randomized Hamiltonian Monte Carlo,”, Annals of Applied Probability, 27, 2159-2194 (2017) · Zbl 1373.60129
[8] Bou-Rabee, N.; Sanz-Serna, J. M., “Geometric Integrators and the Hamiltonian Monte Carlo Method, Acta Numerica, 27, 113-206 (2018) · Zbl 1431.65004
[9] Bou-Rabee, N.; Schuh, K., Convergence of Unadjusted Hamiltonian Monte Carlo for Mean-Field Models, arXiv:2009.08735 (2020) · Zbl 1529.60047
[10] Bouchard-Côté, A.; Vollmer, S. J.; Doucet, A., “The Bouncy Particle Sampler: A Nonreversible Rejection-Free Markov Chain Monte Carlo Method, Journal of the American Statistical Association, 113, 855-867 (2018) · Zbl 1398.60084 · doi:10.1080/01621459.2017.1294075
[11] Cambanis, S.; Huang, S.; Simons, G., “On the Theory of Elliptically Contoured Distributions, Journal of Multivariate Analysis, 11, 368-385 (1981) · Zbl 0469.60019 · doi:10.1016/0047-259X(81)90082-8
[12] Cances, E.; Legoll, F.; Stoltz, G., “Theoretical and Numerical Comparison of Some Sampling Methods for Molecular Dynamics, ESAIM: Mathematical Modelling and Numerical Analysis, 41, 351-389 (2007) · Zbl 1138.82341 · doi:10.1051/m2an:2007014
[13] Carpenter, B.; Gelman, A.; Hoffman, M.; Lee, D.; Goodrich, B.; Betancourt, M.; Brubaker, M.; Guo, J.; Li, P.; Riddell, A., “Stan: A Probabilistic Programming Language, Journal of Statistical Software, 76, 1-32 (2017) · doi:10.18637/jss.v076.i01
[14] Chen, Z.; Vempala, S. S.; Achlioptas, D.; Végh, L. A., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, 145, Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions, 64:1-64:12 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik · Zbl 07650131
[15] Cheng, X.; Chatterji, N. S.; Bartlett, P. L.; Jordan, M. I.; Bubeck, S.; Perchet, V.; Rigollet, P., Proceedings of the 31st Conference On Learning Theory, Volume 75 of Proceedings of Machine Learning Research, Underdamped Langevin mcmc: A Non-asymptotic Analysis, 300-323 (2018), PMLR
[16] Chopin, N.; Ridgway, J., “Leave Pima Indians Alone: Binary Regression as a Benchmark for Bayesian Computation, Statistical Science, 32, 64-87 (2017) · Zbl 1442.62007 · doi:10.1214/16-STS581
[17] Cotter, S.; House, T.; Pagani, F., The NuZZ: Numerical ZigZag Sampling for General Models, arXiv:2003.03636 (2020)
[18] Davis, M. H. A., “Piecewise-Deterministic Markov Processes: A General Class of Non-diffusion Stochastic Models, Journal of the Royal Statistical Society, Series B, 46, 353-376 (1984) · Zbl 0565.60070 · doi:10.1111/j.2517-6161.1984.tb01308.x
[19] Davis, M. H. A., Markov Models and Optimization (1993), London: Chapman & Hall, London · Zbl 0780.60002
[20] Deligiannidis, G.; Paulin, D.; Bouchard-Côté, A.; Doucet, A., Randomized Hamiltonian Monte Carlo as Scaling Limit of the Bouncy Particle Sampler and Dimension-Free Convergence Rates, arXiv:1808.04299 (2018) · Zbl 1484.65004
[21] Dormand, J.; Prince, P., “Runge-Kutta-Nystrom Triples,”, Computers & Mathematics with Applications, 13, 937-949 (1987) · Zbl 0633.65061
[22] Fang, Y.; Sanz-Serna, J. M.; Skeel, R. D., “Compressible Generalized Hybrid Monte Carlo, The Journal of Chemical Physics, 140, 174108 (2014) · doi:10.1063/1.4874000
[23] Fearnhead, P.; Bierkens, J.; Pollock, M.; Roberts, G. O., “Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo, Statistical Science, 33, 386-412 (2018) · Zbl 1403.62148 · doi:10.1214/18-STS648
[24] Gelman, A.; Carlin, J. B.; Stern, H. S.; Dunson, D. B.; Vehtari, A.; Rubin, D., Bayesian Data Analysis (2014), Boca Raton, FL: CRC Press, Boca Raton, FL · Zbl 1279.62004
[25] Geyer, C. J., “Practical Markov chain Monte Carlo, Statistical Science, 7, 473-483 (1992) · Zbl 0085.18501 · doi:10.1214/ss/1177011137
[26] Giles, M. B., “Multilevel Monte Carlo Methods, Acta Numerica, 24, 259-328 (2015) · Zbl 1316.65010 · doi:10.1017/S096249291500001X
[27] Girolami, M.; Calderhead, B., “Riemann Manifold Langevin and Hamiltonian Monte Carlo Methods, Journal of the Royal Statistical Society, Series B, 73, 123-214 (2011) · Zbl 1411.62071 · doi:10.1111/j.1467-9868.2010.00765.x
[28] Goldstein, H.; Poole, C.; Safko, J., Classical Mechanics (2002), Boston: Addison Wesley, Boston
[29] Golosnoy, V.; Gribisch, B.; Liesenfeld, R., “The Conditional Autoregressive Wishart Model for Multivariate Stock Market Volatility, Journal of Econometrics, 167, 211-223 (2012) · Zbl 1441.62705 · doi:10.1016/j.jeconom.2011.11.004
[30] Grothe, O.; Kleppe, T. S.; Liesenfeld, R., “The Gibbs Sampler with Particle Efficient Importance Sampling for State-Space Models, Econometric Reviews, 38, 1152-1175 (2019) · Zbl 1490.62080 · doi:10.1080/07474938.2018.1536098
[31] Hairer, E.; Nørsett, S. P.; Wanner, G., Solving Ordinary Differential Equations I (2nd Rev. Ed.): Nonstiff Problems (1993), Berlin, Heidelberg: Springer-Verlag, Berlin, Heidelberg · Zbl 0789.65048
[32] Hoffman, M. D.; Gelman, A., “The no-u-turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo,”, Journal of Machine Learning Research, 15, 1593-1623 (2014) · Zbl 1319.60150
[33] Horowitz, A. M., “A Generalized Guided Monte Carlo Algorithm, Physics Letters B, 268, 247-252 (1991) · doi:10.1016/0370-2693(91)90812-5
[34] Kleppe, T. S., “Adaptive Step Size Selection for Hessian-based Manifold Langevin Samplers, Scandinavian Journal of Statistics, 43, 788-805 (2016) · Zbl 1468.62435 · doi:10.1111/sjos.12204
[35] Lee, Y. T.; Song, Z.; Vempala, S. S., Algorithmic Theory of ODEs and Sampling from Well-Conditioned Logconcave Densities, arXiv:1812.06243 (2018)
[36] Leimkuhler, B.; Matthews, C., Molecular Dynamics With Deterministic and Stochastic Numerical Methods (2015), New York: Springer, New York · Zbl 1351.82001
[37] Leimkuhler, B.; Reich, S., Simulating Hamiltonian Dynamics (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1069.65139
[38] Li, D., “On the Rate of Convergence to Equilibrium of the Andersen Thermostat in Molecular Dynamics, Journal of Statistical Physics, 129, 265-287 (2007) · Zbl 1128.82014 · doi:10.1007/s10955-007-9391-0
[39] Livingstone, S.; Faulkner, M. F.; Roberts, G. O., “Kinetic Energy Choice in Hamiltonian/Hybrid Monte Carlo, Biometrika, 106, 303-319 (2019) · Zbl 1439.60070 · doi:10.1093/biomet/asz013
[40] Lu, J.; Wang, L., On Explicit l^2-convergence Rate Estimate for Piecewise Deterministic Markov Processes in MCMC Algorithms, arXiv:2007.14927 (2020)
[41] Mackenze, P. B., “An Improved Hybrid Monte Carlo Method, Physics Letters B, 226, 369-371 (1989) · doi:10.1016/0370-2693(89)91212-4
[42] Mangoubi, O.; Smith, A., Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions, arXiv:1708.07114 (2017)
[43] Mangoubi, O.; Smith, A.; Chaudhuri, K.; Sugiyama, M., Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, Volume 89 of Proceedings of Machine Learning Research, Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions 2: Numerical Integrators, 586-595 (2019), PMLR
[44] Michie, D.; Spiegelhalter, D. J.; Taylor, C. C., Machine Learning, Neural and Statistical Classification. Series in Artificial Intelligence (1994), Hemel Hempstead, Hertfordshire: Ellis Horwood, Hemel Hempstead, Hertfordshire · Zbl 0827.68094
[45] Neal, R. M., “Slice Sampling, The Annals of Statistics, 31, 705-767 (2003) · Zbl 1051.65007 · doi:10.1214/aos/1056562461
[46] Neal, R. M.; Brooks, S.; Gelman, A.; Jones, G.; Meng, X.-L., Handbook of Markov chain Monte Carlo, MCMC using Hamiltonian Dynamics,”, 113-162 (2010), Boca Raton, FL: CRC Press, Boca Raton, FL
[47] Nishimura, A.; Dunson, D., “Recycling Intermediate Steps to Improve Hamiltonian Monte Carlo, Bayesian Analysis, 15, 1087-1108 (2020) · Zbl 1480.62060 · doi:10.1214/19-BA1171
[48] Osmundsen, K. K.; Kleppe, T. S.; Liesenfeld, R., “Importance Sampling-Based Transport Map Hamiltonian Monte Carlo for Bayesian Hierarchical Models, Journal of Computational and Graphical Statistics (2021) · Zbl 07499926 · doi:10.1080/10618600.2021.1923519
[49] Pakman, A.; Paninski, L., “Exact Hamiltonian Monte Carlo for Truncated Multivariate Gaussians, Journal of Computational and Graphical Statistics, 23, 518-542 (2014) · doi:10.1080/10618600.2013.788448
[50] Robert, C. P.; Casella, G., Monte Carlo Statistical Methods (2004), New York: Springer, New York · Zbl 1096.62003
[51] Roberts, G. O.; Rosenthal, J. S., “Optimal Scaling of Discrete Approximations to Langevin Diffusions, Journal of the Royal Statistical Society, Series B, 60, 255-268 (1998) · Zbl 0913.60060 · doi:10.1111/1467-9868.00123
[52] Rudolf, D.; Schweizer, N., “Perturbation Theory for Markov Chains via Wasserstein Distance, Bernoulli, 24, 2610-2639 (2018) · Zbl 1465.60065 · doi:10.3150/17-BEJ938
[53] Sanz-Serna, J.; Calvo, M., Numerical Hamiltonian Problems (1994), New York: Dover Publications Inc, New York · Zbl 0816.65042
[54] Stan Development Team. (2017), “Stan Modeling Language Users Guide and Reference Manual version 2.17.0.”
[55] Vanetti, P.; Bouchard-Côté, A.; Deligiannidis, G.; Doucet, A., Piecewise-Deterministic Markov chain Monte Carlo, arXiv:1707.05296v2 (2018)
[56] Weinan, E.; Li, D., “The Andersen Thermostat in Molecular Dynamics, Communications on Pure and Applied Mathematics, 61, 96-136 (2008) · Zbl 1148.82019 · doi:10.1002/cpa.20198
[57] Welling, M.; Teh, Y. W., Proceedings of the 28th International Conference on International Conference on Machine Learning, Bayesian Learning via Stochastic Gradient Langevin Dynamics, 681-688 (2011), Madison, WI, USA: Omnipress, Madison, WI, USA
[58] Wu, C.; Stoehr, J.; Robert, C. P., Faster Hamiltonian Monte Carlo by Learning Leapfrog Scale, arXiv:1810.04449 (2018)
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.