×

On irreversible Metropolis sampling related to Langevin dynamics. (English) Zbl 1492.65015

Summary: There has been considerable interest in designing Markov chain Monte Carlo algorithms by exploiting numerical methods for Langevin dynamics, which includes Hamiltonian dynamics as a deterministic case. A prominent approach is Hamiltonian Monte Carlo (HMC), where a leapfrog discretization of Hamiltonian dynamics is employed. We investigate a recently proposed class of irreversible sampling algorithms, called Hamiltonian assisted Metropolis sampling (HAMS), which uses an augmented target density similarly as in HMC but involves a flexible proposal scheme and a carefully formulated acceptance-rejection scheme to achieve generalized reversibility. We show that as the step size tends to 0, the HAMS proposal satisfies a class of stochastic differential equations including Langevin dynamics as a special case. We provide theoretical results for HAMS, including algebraic properties of the acceptance probability, the stationary variance from the HAMS proposal, and the expected acceptance rate under a product Gaussian target distribution and the convergence rate under standard Gaussian. From these results, we derive default choices of tuning parameters for HAMS such that only the step size needs to be tuned in applications. Various relatively recent algorithms for Langevin dynamics are also shown to fall in the class of HAMS proposals up to negligible differences. Our numerical experiments on sampling high-dimensional latent variables confirm that the HAMS algorithms consistently achieve superior performance compared with several Metropolis-adjusted algorithms based on popular integrators of Langevin dynamics.

MSC:

65C05 Monte Carlo methods
60J22 Computational methods in Markov chains

References:

[1] J. E. Besag, Comments on “Representations of knowledge in complex systems” by U. Grenander and M.I. Miller, J. R. Stat. Soc. Ser. B, 56 (1994), pp. 591-592.
[2] N. Bou-Rabee, Time integrators for molecular dynamics, Entropy, 16 (2014), pp. 138-162.
[3] N. Bou-Rabee and A. Eberle, Markov chain Monte Carlo methods, Lecture Notes in Hausdorff School on MCMC: Recent Developments and New Connections, 2020. · Zbl 07325608
[4] N. Bou-Rabee and A. Eberle, Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo, preprint, arXiv:2105.00887, 2021. · Zbl 1470.60202
[5] N. Bou-Rabee and Vanden-Eijnden, Pathwise accuracy and ergodicity of Metropolized integrators for SDEs, Comm. Pure Appl. Math., 63 (2010), pp. 655-696. · Zbl 1214.60031
[6] N. Bou-Rabee and E. Vanden-Eijnden, A patch that imparts unconditional stability to explicit integrators for Langevin-like equations, J. Comput. Phys., 231 (2012), pp. 2565-2580. · Zbl 1430.65003
[7] S. Brooks, A. Gelman, G. Jones, and X.-L. Meng, Handbook of Markov Chain Monte Carlo, CRC Press, Boca Raton, FL, 2011. · Zbl 1218.65001
[8] A. Brünger, C. L. Brooks, and M. Karplus, Stochastic boundary conditions for molecular dynamics simulations of ST2 water, Chem. Phys. Lett., 105 (1984), pp. 495-500.
[9] K. Burrage, I. Lenane, and G. Lythe, Numerical methods for second-order stochastic differential equations, SIAM J. Sci. Comput., 29 (2007), pp. 245-264. · Zbl 1144.65004
[10] G. Bussi and M. Parrinello, Accurate sampling using Langevin dynamics, Phys. Rev. E, 75 (2007), 056707.
[11] M. P. Calvo, D. Sanz-Alonso, and J. M. Sanz-Serna, HMC: Avoiding Rejections by Not Using Leapfrog and Some Results on the Acceptance Rate, preprint, arXiv:1912.03253, 2019. · Zbl 07505916
[12] Y. Cao, J. Lu, and L. Wang, On Explicit \(L^2\)-Convergence Rate Estimate for Underdamped Langevin Dynamics, preprint, arXiv:1908.04746, 2020.
[13] 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., 21 (2020), pp. 1-63. · Zbl 1502.62030
[14] Z. Chen, and S. S. Vempala, Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions, preprint, arXiv:1905.02313, 2019. · Zbl 07528585
[15] X. Cheng, N. S. Chatterji, P. L. Bartlett, and M. I. Jordan, Underdamped Langevin MCMC: A non-asymptotic analysis, in Proceedings of the 31st Conference On Learning Theory, Stockholm, Sweeden, 2018, volume 75, pp. 300-323.
[16] O. F. Christensen, G. O. Roberts, and J. S. Rosenthal, Scaling limits for the transient phase of local Metropolis-Hastings algorithms, J. R. Stat. Soc. Ser. B, 67 (2005), pp. 253-268. · Zbl 1075.65012
[17] A. S. Dalalyan, Theoretical guarantees for approximate sampling from smooth and log-concave densities, J. R. Stat. Soc. Ser. B, 79 (2017), pp. 651-676. · Zbl 1411.62030
[18] A. S. Dalalyan and L. Riou-Durand, On sampling from a log-concave density using kinetic Langevin diffusions, Bernoulli, 26 (2020), pp. 1956-1988. · Zbl 07193949
[19] S. Duane, A. Kennedy, B. J. Pendleton, and D. Roweth, Hybrid Monte Carlo, Phys. Lett. B, 195 (1987), pp. 216-222.
[20] A. B. Duncan, T. Lelièvre, and G. A. Pavliotis, Variance reduction using nonreversible Langevin samplers, J. Stat. Phys., 163 (2016), pp. 457-491. · Zbl 1343.82036
[21] A. Durmus and E. Moulines, High-dimensional Bayesian inference via the unadjusted Langevin algorithm, Bernoulli, 25 (2019), pp. 2854-2882. · Zbl 1428.62111
[22] R. Dwivedi, Y. Chen, M. J. Wainwright, and B. Yu, Log-concave sampling: Metropolis-Hastings algorithms are fast, J. Mach. Learn. Res., 20 (2019), pp. 1-42. · Zbl 1440.62039
[23] A. Eberle, A. Guillin, and R. Zimmer, Couplings and quantitative contraction rates for Langevin dynamics, Ann. Probab., 47 (2019), pp. 1982-2010. · Zbl 1466.60160
[24] O. Farago, Langevin thermostat for robust configurational and kinetic sampling, Phys. A, 534 (2019), 122210. · Zbl 07570689
[25] M. Girolami and B. Calderhead, Riemann manifold Langevin and Hamiltonian Monte Carlo methods, J. R. Stat. Soc. Ser. B, 73 (2011), pp. 123-214. · Zbl 1411.62071
[26] N. Goga, A. J. Rzepiela, A. H. de Vries, S. J. Marrink, and H. J. C. Berendsen, Efficient algorithms for Langevin and DPD dynamics, J. Chem. Theory Comput., 8 (2012), pp. 3637-3649.
[27] N. Grønbech-Jensen and O. Farago, A simple and effective Verlet-type algorithm for simulating Langevin dynamics, Mol. Phys., 111 (2013), pp. 983-991.
[28] A. Guillin and P. Monmarche, Optimal linear drift for the speed of convergence of an hypoelliptic diffusion, Electron. Commun. Probab., 21 (2016), pp. 1-14. · Zbl 1354.60084
[29] W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57 (1970), pp. 97-109. · Zbl 0219.65008
[30] A. M. Horowitz, A generalized guided Monte Carlo algorithm, Phys. Lett. B, 268 (1991), pp. 247-252.
[31] C.-R. Hwang, S.-Y. Hwang-Ma, and S.-J. Sheu, Accelerating Gaussian Diffusions, Ann. Appl. Probab., 3 (1993), pp. 897-913. · Zbl 0780.60074
[32] S. Kim, N. Shephard, and S. Chib, Stochastic volatility: Likelihood inference and comparison with ARCH models, Rev. Econ. Stud., 65 (1998), pp. 361-393. · Zbl 0910.90067
[33] B. Leimkuhler and C. Matthews, Rational construction of stochastic numerical methods for molecular sampling, Appl. Math. Res. Express, 2013 (2012), pp. 34-56. · Zbl 1264.82102
[34] B. Leimkuhler and C. Matthews, Robust and efficient configurational molecular sampling via Langevin dynamics, J. Chem. Phys., 138 (2013), 174102.
[35] T. Lelièvre, F. Nier, and G. A. Pavliotis, Optimal non-reversible linear drift for the convergence to equilibrium of a diffusion, J. Stat. Phys., 152 (2013), pp. 237-274. · Zbl 1276.82042
[36] Y.-A. Ma, E. Fox, T. Chen, and L. Wu, Irreversible samplers from jump and continuous Markov processes, Stat. Comput., 29 (2018), pp. 177-202. · Zbl 1430.62060
[37] O. Mangoubi and A. Smith, Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 2: Numerical integrators, in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), Naha, Japan, 2019, pp. 586-595.
[38] R. Mannella, Quasisymplectic integrators for stochastic differential equations, Phys. Rev. E, 69 (2004), 041107.
[39] S. Melchionna, Design of quasisymplectic propagators for Langevin dynamics, J. Chem. Phys., 127 (2007), 044108.
[40] 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 (1953), pp. 1087-1092. · Zbl 1431.65006
[41] R. M. Neal, MCMC using Hamiltonian dynamics, in Handbook of Markov Chain Monte Carlo, S. Brooks, A. Gelman, G. L. Jones, and X.-L. Meng, eds., CRC Press, Boca Raton, FL, 2011. · Zbl 1229.65018
[42] M. Ottobre, N. S. Pillai, F. J. Pinski, and A. M. Stuart, A function space HMC algorithm with second order Langevin diffusion limit, Bernoulli, 22 (2016), pp. 60-106. · Zbl 1346.60119
[43] M. Ottobre, N. S. Pillai, and K. Spiliopoulos, Optimal scaling of the MALA algorithm with irreversible proposals for Gaussian targets, Stoch. Partial Differ. Equ. Anal. Comput., 8 (2020), pp. 311-361. · Zbl 1447.62094
[44] L. Rey-Bellet and K. Spiliopoulos, Improving the convergence of reversible samplers, J. Stat. Phys., 164 (2016), pp. 472-494. · Zbl 1348.82046
[45] G. O. Roberts and S. K. Sahu, Updating schemes, correlation structure, blocking and parameterization for the Gibbs sampler, J. R. Stat. Soc. Ser. B, 59 (1997), pp. 291-317. · Zbl 0886.62083
[46] G. O. Roberts and R. L. Tweedie, Exponential convergence of Langevin distributions and their discrete approximations, Bernoulli, 2 (1996), pp. 341-363. · Zbl 0870.60027
[47] A. Scemama, T. Lelièvre, G. Stoltz, E. Cancès, and M. Caffarel, An efficient sampling algorithm for variational Monte Carlo, J. Chem. Phys., 125 (2006), 114105.
[48] Z. Song and Z. Tan, Hamiltonian assisted Metropolis sampling, J. Amer. Statist. Assoc., (2021), https://doi.org/10.1080/01621459.2021.1982723. · Zbl 07707232
[49] W. van Gunsteren and H. Berendsen, Algorithms for Brownian dynamics, Mol. Phys., 45 (1982), pp. 637-647.
[50] E. Vanden-Eijnden and G. Ciccotti, Second-order integrators for Langevin equations with holonomic constraints, Chem. Phys. Lett., 429 (2006), pp. 310-316.
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.