A Splitting Hamiltonian Monte Carlo Method for Efficient Sampling

Abstract

We propose a splitting Hamiltonian Monte Carlo (SHMC) algorithm, which can be computationally efficient when combined with the random mini-batch strategy. By splitting the potential energy into numerically nonstiff and stiff parts, one makes a proposal using the nonstiff part of U, followed by a Metropolis rejection step using the stiff part that is often easy to compute. The splitting allows efficient sampling from systems with singular potentials (or distributions with degenerate points) and/or with multiple potential barriers. In our SHMC algorithm, the proposal only based on the nonstiff part in the splitting is generated by the Hamiltonian dynamics, which can be potentially more efficient than the overdamped Langevin dynamics. We also use random batch strategies to reduce the computational cost to $\mathcal{O}$(1) per time step in generating the proposals for problems arising from many-body systems and Bayesian inference, and prove that the errors of the Hamiltonian induced by the random batch approximation is $\mathcal{O}\left(\sqrt{\mathrm{\Delta }t}\right)$ in the strong and $\mathcal{O}\left(\mathrm{\Delta }t\right)$ in the weak sense, where $\mathrm{\Delta }t$ is the time step. Numerical experiments are conducted to verify the theoretical results and the computational efficiency of the proposed algorithms in practice.

Keywords

Markov chain Monte Carlo / potential splitting / random-batch method / many body systems / Bayesian inference

References

[1] M. P. Allen and D. J. Tildesley, Computer Simulation of Liquids, Oxford University Press, 1987.

[2] S. Banerjee, B. P. Carlin, and A. E. Gelfand, Hierarchical Modeling and Analysis for Spatial Data, CRC Press, 2014.

[3] A. Barbu and S.-C. Zhu, Hamiltonian and Langevin Monte Carlo, In: Monte Carlo Methods, Springer, 281-325, 2020.

[4] G. Benettin and A. Giorgilli, On the Hamiltonian interpolation of near-to-the identity symplectic mappings with application to symplectic integration algorithms, J. Stat. Phys., 74(5-6):1117-1143, 1994.

[5] J. E. Besag, Comments on "Representations of knowledge in complex systems" by U. Grenander and M. I. Miller, J. R. Stat. Soc. Series B Stat. Methodol., 56(4):549-581, 1994.

[6] A. Beskos, N. Pillai, G. Roberts, J.-M. Sanz-Serna, and A. Stuart, Optimal tuning of the hybrid Monte Carlo algorithm, Bernoulli, 19(5A):1501-1534, 2013.

[7] M. Betancourt,A conceptual introduction to Hamiltonian Monte Carlo, arXiv:1701.02434.

[8] L. Bottou, On-line Learning and Stochastic Approximations, In: On-Line Learning in Neural Networks (Publications of the Newton Institute), Cambridge University Press, 9-42, 1999.

[9] S. Bubeck, Convex optimization: Algorithms and complexity, Found. Trends Mach. Learn., 8(3-4):231-357, 2015.

[10] T. Chen, E. Fox, and C. Guestrin, Stochastic gradient Hamiltonian Monte Carlo, In: International Conference on Machine Learning, PMLR, 1683-1691, 2014.

[11] Y. Chen, R. Dwivedi, M. J. Wainwright, and B. Yu, Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients, J. Mach. Learn. Res., 2020.

[12] C. Dai and J. S. Liu, Wang-Landau algorithm as stochastic optimization and its acceleration, Phys. Rev. E, 101(3):033301, 2020.

[13] A. S. Dalalyan,Theoretical guarantees for approximate sampling from smooth and log-concave densities, J. R. Stat. Soc. Series B Stat. Methodol., 79(3):651-676, 2017.

[14] A. S. Dalalyan and A. Karagulyan, User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient, Stoch. Process Their Appl., 129(12):5278-5311, 2019.

[15] Z. Ding, Q. Li, J. Lu, and S. Wright, Random coordinate underdamped Langevin Monte Carlo, In: International Conference on Artificial Intelligence and Statistics, PMLR, 2701-2709, 2021.

[16] S. Duane, A. D. Kennedy, B. J. Pendleton, and D. Roweth, Hybrid Monte Carlo, Phys. Lett. B, 195(2):216-222, 1987.

[17] R. Durrett, Probability: Theory and Examples, Vol. 49, Cambridge University Press, 2019.

[18] F. J. Dyson, A Brownian-motion model for the eigenvalues of a random matrix, J. Math. Phys., 3(6):1191-1198, 1962.

[19] L. Erdos and H.-T. Yau, A Dynamical Approach to Random Matrix Theory, Courant Lecture Notes in Mathematics, 28, 2017.

[20] C. Fraley and A. E. Raftery, Model-based clustering, discriminant analysis, and density estimation, J. Am. Stat. Assoc., 97(458):611-631, 2002.

[21] D. Frenkel and B. Smit, Understanding Molecular Simulation: From Algorithms to Applications, Vol. 1, Elsevier, 2001.

[22] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6:721-741, 1984.

[23] C. J. Geyer,Markov Chain Monte Carlo maximum likelihood, In:Computing Science and Statistics: Proceedings of 23rd Symposium on the Interface Interface Foundation,156-163, 1991.

[24] M. Giordano and R. Nickl, Consistency of Bayesian inference with Gaussian process priors in an elliptic inverse problem, Inverse Probl., 36(8):085001, 2020.

[25] P. J. Green, Reversible jump Markov chain Monte Carlo computation and Bayesian model determination, Biometrika, 82(4):711-732, 1995.

[26] E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Vol. 31, Springer Science & Business Media, 2006.

[27] W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57(1):97, 1970.

[28] B. Hetenyi, K. Bernacki, and B. J. Berne, Multiple "time step" Monte Carlo, J. Chem. Phys., 117(18):8203-8207, 2002.

[29] A. Jasra, C. C. Holmes, and D. A. Stephens, Markov Chain Monte Carlo methods and the label switching problem in Bayesian mixture modeling, Stat. Sci., 20(1):50-67, 2005.

[30] S. Jin and L. Li, Random batch methods for classical and quantum interacting particle systems and statistical samplings, arXiv:2104.04337.

[31] S. Jin, L. Li, and J.-G. Liu, Random batch methods (RBM) for interacting particle systems, J. Comput. Phys., 400(1):108877, 2020.

[32] S. Jin, L. Li, and J.-G. Liu, Convergence of the random batch method for interacting particles with disparate species and weights, SIAM J. Numer. Anal., 59(2):746-768, 2021.

[33] S. Jin, L. Li, and Y. Sun, On the random batch method for second order interacting particle systems, arXiv:2011.10778.

[34] S. Jin, L. Li, Z. Xu, and Y. Zhao, A random batch Ewald method for particle systems with Coulomb interactions, arXiv:2010.01559.

[35] S. Jin and X. Li, Random batch algorithms for quantum Monte Carlo simulations, arXiv:2008. 12990.

[36] J. K. Johnson, J. A. Zollweg, and K. E. Gubbins, The Lennard-Jones equation of state revisited, Mol. Phys., 78(3):591-618, 1993.

[37] A. Laio and M. Parrinello,Escaping free-energy minima, Proc. Natl. Acad. Sci., 99(20):1256212566, 2002.

[38] S. Lan, J. Streets, and B. Shahbaba,Wormhole Hamiltonian Monte Carlo, In:Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 28, 2014.

[39] Y. T. Lee and S. S. Vempala,Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation, In:Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,1115-1121, 2018.

[40] B. Leimkuhler and S. Reich, Simulating Hamiltonian dynamics, Vol. 14, Cambridge University Press, 2004.

[41] L. Li, Y. Li, J.-G. Liu, Z. Liu, and J. Lu, A stochastic version of Stein variational gradient descent for efficient sampling, Comm. App. Math. Comp. Sci., 15(1):37-63, 2020.

[42] L. Li, Z. Xu, and Y. Zhao, A random-batch Monte Carlo method for many-body systems with singular kernels, SIAM J. Sci. Comput., 42(3):A1486-A1509, 2020.

[43] L. Lovász and M. Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms, 4(4):359-412, 1993.

[44] O. Mangoubi, N. S. Pillai, and A. Smith, Does Hamiltonian Monte Carlo mix faster than a random walk on multimodal densities? arXiv:1808.03230.

[45] E. Marinari and G. Parisi, Simulated tempering: a new Monte Carlo scheme, EPL, 19(6):451, 1992.

[46] P. A. Markowich and C. Villani, On the trend to equilibrium for the Fokker-Planck equation: An interplay between physics and functional analysis, Math. Contemp., 19:1-31, 2000.

[47] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys., 21(6):1087-1092, 1953.

[48] B. Miasojedow, E. Moulines, and M. Vihola, An adaptive parallel tempering algorithm, J. Comput. Graph. Stat., 22(3):649-664, 2013.

[49] R. M. Neal, MCMC using Hamiltonian dynamics, Handbook of Markov Chain Monte Carlo, 2(11):2, 2011.

[50] R. Nickl and S. Wang, On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms, arXiv:2009.05298.

[51] M. Raginsky, A. Rakhlin, and M. Telgarsky, Non-convex learning via stochastic gradient Langevin dynamics:A nonasymptotic analysis, In: Conference on Learning Theory, PMLR, 1674-1703, 2017.

[52] H. Robbins and S. Monro, A stochastic approximation method Ann. Math. Stat., 22(3):400-407, 1951.

[53] G. O. Roberts and J. S. Rosenthal, General state space Markov chains and MCMC algorithms, Probab. Surv., 1:20-71, 2004.

[54] G. O. Roberts and R. L. Tweedie, Exponential convergence of Langevin distributions and their discrete approximations, Bernoulli, 2(4):341-363, 1996.

[55] J. C. Sexton and D. H. Weingarten, Hamiltonian evolution for the hybrid Monte Carlo algorithm, Nucl. Phys. B, 380(3):665-677, 1992.

[56] B. Shahbaba, S. Lan, W. O. Johnson, and R. M. Neal, Split Hamiltonian Monte Carlo, Stat. Comput., 24(3):339-349, 2014.

[57] A. Smith, Sequential Monte Carlo Methods in Practice, Springer Science & Business Media, 2013.

[58] R. H. Swendsen and J.-S. Wang, Replica Monte Carlo simulation of spin-glasses, Phys. Rev. Lett., 57(21):2607, 1986.

[59] T. Tao, Topics in Random Matrix Theory, Vol. 132, AMS, 2012.

[60] F. Wang and D. P. Landau, Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram, Phys. Rev. E, 64(5):056101, 2001.

[61] F. Wang and D. P. Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Phys. Rev. Lett., 86(10):2050, 2001.

[62] G. Wanner and E. Hairer, Solving Ordinary Differential Equations II, Vol. 375, Springer, 1996.

[63] M. Welling and Y. W. Teh,Bayesian learning via stochastic gradient Langevin dynamics, In:Proceedings of the 28th International Conference on Machine Learning (ICML-11), 681-688, 2011.

[64] X. Ye and Z. Zhou, Efficient sampling of thermal averages of interacting quantum particle systems with random batches, J. Chem. Phys., 154(20):204106, 2021.