Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models. (English) Zbl 1529.60047
In this paper, the authors introduce convergence and discretization error bounds that are independent of dimensionality for the unadjusted Hamiltonian Monte Carlo algorithm when applied to high-dimensional probability distributions of mean-field type. Unlike previous approaches, their bounds necessitate a sufficiently small discretization step but do not impose the requirement of strong convexity for either unary or pairwise potential terms inherent in the mean-field model.
To address the challenges posed by high dimensionality, the proof employs a particlewise coupling strategy that exhibits contractivity in a complementary particlewise metric. This novel approach enhances the algorithm’s ability to handle high-dimensional scenarios effectively. The presented results contribute to a more comprehensive understanding of the Hamiltonian Monte Carlo algorithm’s performance in the context of mean-field distributions, especially in scenarios where traditional assumptions of strong convexity may not be applicable.
To address the challenges posed by high dimensionality, the proof employs a particlewise coupling strategy that exhibits contractivity in a complementary particlewise metric. This novel approach enhances the algorithm’s ability to handle high-dimensional scenarios effectively. The presented results contribute to a more comprehensive understanding of the Hamiltonian Monte Carlo algorithm’s performance in the context of mean-field distributions, especially in scenarios where traditional assumptions of strong convexity may not be applicable.
MSC:
| 60J05 | Discrete-time Markov processes on general state spaces |
| 65P10 | Numerical methods for Hamiltonian systems including symplectic integrators |
| 65C05 | Monte Carlo methods |
References:
| [1] | Assyr Abdulle, Gilles Vilmart, and Konstantinos C Zygalakis, High order numerical approximation of the invariant measure of ergodic sdes, SIAM Journal on Numerical Analysis 52 (2014), no. 4, 1600-1622. · Zbl 1310.65007 |
| [2] | Assyr Abdulle, Gilles Vilmart, and Konstantinos C Zygalakis, Long time accuracy of lie-trotter splitting methods for langevin dynamics, SIAM Journal on Numerical Analysis 53 (2015), no. 1, 1-16. · Zbl 1327.65015 |
| [3] | E. Akhmatskaya and S. Reich, GSHMC: An efficient method for molecular simulation, J. Comput. Phys. 227 (2008), 4937-4954. · Zbl 1148.82316 |
| [4] | M. P. Allen and D. J. Tildesley, Computer simulation of liquids, Clarendon Press, 1987. · Zbl 0703.68099 |
| [5] | Adriano Amarante, Guedmiller Oliveira, Jéssica Ierich, Richard Cunha, Luiz Freitas, Eduardo Franca, and Fabio Leite, Molecular modeling applied to nanobiosystems, pp. 179-220, 12 2017. |
| [6] | A. Beskos, N. S. Pillai, G. O. Roberts, J. M. Sanz-Serna, and A. M. Stuart, Optimal tuning of hybrid Monte-Carlo algorithm, Bernoulli 19 (2013), 1501-1534. · Zbl 1287.60090 |
| [7] | A. Beskos, F. J. Pinski, J. M. Sanz-Serna, and A. M. Stuart, Hybrid Monte-Carlo on Hilbert spaces, Stochastic Processes and their Applications 121 (2011), no. 10, 2201-2230. · Zbl 1235.60091 |
| [8] | A. Beskos, G. O. Roberts, and A. M. Stuart, Optimal scalings for local Metropolis-Hastings chains on non-product targets in high dimensions, Ann. Appl. Probab. 19 (2009), 863-898. · Zbl 1172.60328 |
| [9] | J. Bierkens, P. Fearnhead, and G. Roberts, The zig-zag process and super-efficient sampling for Bayesian analysis of big data, The Annals of Statistics 47 (2019), no. 3, 1288-1320. · Zbl 1417.65008 |
| [10] | S. Blanes, F. Casas, and J. M. Sanz-Serna, Numerical integrators for the hybrid Monte Carlo method, SIAM Journal on Scientific Computing 36 (2014), no. 4, A1556-A1580. · Zbl 1312.65209 |
| [11] | Peter G. Bolhuis, Transition path sampling on diffusive barriers, Journal of Physics: Condensed Matter 15 (2002), no. 1, S113. |
| [12] | Nawaf Bou-Rabee and Andreas Eberle, Two-scale coupling for preconditioned Hamiltonian Monte Carlo in infinite dimensions, Stoch. Partial Differ. Equ. Anal. Comput. 9 (2021), no. 1, 207-242. · Zbl 1470.60202 |
| [13] | Nawaf Bou-Rabee, Andreas Eberle, and Raphael Zimmer, Coupling and convergence for hamiltonian monte carlo, Ann. Appl. Probab. 30 (2020), no. 3, 1209-1250. · Zbl 07325608 |
| [14] | Nawaf Bou-Rabee and Houman Owhadi, Long-run accuracy of variational integrators in the stochastic context, SIAM Journal on Numerical Analysis 48 (2010), no. 1, 278-297. · Zbl 1215.65012 |
| [15] | Nawaf Bou-Rabee and J. M. Sanz-Serna, Geometric integrators and the Hamiltonian Monte Carlo method, Acta Numer. 27 (2018), 113-206. · Zbl 1431.65004 |
| [16] | Nawaf Bou-Rabee and Jesús María Sanz-Serna, Randomized Hamiltonian Monte Carlo, Ann. Appl. Probab. 27 (2017), no. 4, 2159-2194. · Zbl 1373.60129 |
| [17] | C. M. Campos and J. M. Sanz-Serna, Extra chance generalized hybrid Monte Carlo, Journal of Computational Physics 281 (2015), 365-374. · Zbl 1352.65007 |
| [18] | E. Cancés, F. Legoll, and G. Stoltz, Theoretical and numerical comparison of some sampling methods for molecular dynamics, Mathematical Modelling and Numerical Analysis 41 (2007), 351-389. · Zbl 1138.82341 |
| [19] | T. Chen, E. Fox, and C. Guestrin, Stochastic gradient Hamiltonian Monte Carlo, International conference on machine learning, 2014, pp. 1683-1691. |
| [20] | Zongchen Chen and Santosh S. Vempala, Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions, Theory Comput. 18 (2022), Paper No. 9, 18. · Zbl 07528585 |
| [21] | Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, and Michael I. Jordan, Sharp convergence rates for langevin dynamics in the nonconvex setting, arXiv preprint 1805.01648 (2018). |
| [22] | M. Dashti and A. M. Stuart, The Bayesian approach to inverse problems, Handbook of Uncertainty Quantification (2017), 311-428. |
| [23] | G. Deligiannidis, A. Bouchard-Côté, and A. Doucet, Exponential ergodicity of the bouncy particle sampler, The Annals of Statistics 47 (2019), no. 3, 1268-1287. · Zbl 1467.60057 |
| [24] | Simon Duane, A. D. Kennedy, Brian J. Pendleton, and Duncan Roweth, Hybrid Monte Carlo, Phys. Lett. B 195 (1987), no. 2, 216-222. |
| [25] | David B Dunson and JE Johndrow, The hastings algorithm at fifty, Biometrika 107 (2020), no. 1, 1-23. · Zbl 1435.62042 |
| [26] | Alain Durmus and Andreas Eberle, Asymptotic bias of inexact Markov chain monte carlo methods in high dimension, arXiv preprint 2108.00682 (2021). |
| [27] | Alain Durmus, Andreas Eberle, Arnaud Guillin, and Raphael Zimmer, An elementary approach to uniform in time propagation of chaos, Proc. Amer. Math. Soc. 148 (2020), no. 12, 5387-5398. · Zbl 1471.60123 |
| [28] | Alain Durmus, Éric Moulines, and Eero Saksman, Irreducibility and geometric ergodicity of Hamiltonian Monte Carlo, Ann. Statist. 48 (2020), no. 6, 3545-3564. · Zbl 1460.65005 |
| [29] | A. Eberle, Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions, Ann. Appl. Probab. 24 (2014), no. 1, 337-377. · Zbl 1296.60195 |
| [30] | A. Eberle, Reflection couplings and contraction rates for diffusions, Probability theory and related fields 166 (2016), no. 3-4, 851-886. · Zbl 1367.60099 |
| [31] | A. Eberle, A. Guillin, and R. Zimmer, Couplings and quantitative contraction rates for Langevin dynamics, Ann. Probab. 47 (2019), no. 4, 1982-2010. · Zbl 1466.60160 |
| [32] | Andreas Eberle, Markov processes, Lecture Notes, University of Bonn (2020). |
| [33] | E. Emmrich, Discrete versions of gronwall’s lemma and their application to the numerical analysis of parabolic problems, Preprint No. 637, Fachbereich Mathematik, TU Berlin (1999). |
| [34] | Youhan Fang, Jesus-Maria Sanz-Serna, and Robert D Skeel, Compressible generalized hybrid monte carlo, The Journal of Chemical Physics 140 (2014), no. 17, 174108. |
| [35] | D. Frenkel and B. Smit, Understanding molecular simulation: From algorithms to applications, 2nd edition, Academic Press, 2002. · Zbl 0889.65132 |
| [36] | A. Gelman, W. R. Gilks, and G. O. Roberts, Weak convergence and optimal scaling of random walk metropolis algorithms, Ann. Appl. Probab. 7 (1997), 110-120. · Zbl 0876.60015 |
| [37] | M. Girolami and B. Calderhead, Riemann manifold Langevin and Hamiltonian Monte Carlo methods, J. R. Statist. Soc. B 73 (2011), 123-214. · Zbl 1411.62071 |
| [38] | Arnaud Guillin, Wei Liu, Liming Wu, and Chaoen Zhang, The kinetic Fokker-Planck equation with mean field interaction, J. Math. Pures Appl. (9) 150 (2021), 1-23. · Zbl 1480.60235 |
| [39] | Arnaud Guillin and Pierre Monmarché, Uniform long-time and propagation of chaos estimates for mean field kinetic particles in non-convex landscapes, J. Stat. Phys. 185 (2021), no. 2, Paper No. 15, 20. · Zbl 1515.82069 |
| [40] | R. Gupta, G. W. Kilcup, and S. R. Sharpe, Tuning the hybrid Monte Carlo algorithm, Physical Review D 38 (1988), no. 4, 1278. |
| [41] | M. Hairer, A. M. Stuart, and S. J. Vollmer, Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions, Ann. Appl. Probab. 24 (2014), no. 6, 2455-2490. · Zbl 1307.65002 |
| [42] | Matthew D. Hoffman and Andrew Gelman, The no-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo, J. Mach. Learn. Res. 15 (2014), 1593-1623. · Zbl 1319.60150 |
| [43] | A. M. Horowitz, A generalized guided Monte-Carlo algorithm, Phys. Lett. B 268 (1991), 247-252. |
| [44] | Mark Kac, Foundations of kinetic theory. in proceedings of the third berkeley symposium on mathematical statistics and probability, 1954-1955, vol. III, University of California Press, Berkeley and Los Angeles, 1956. |
| [45] | R. Korol, J. L. Rosa-Raíces, N. Bou-Rabee, and T. F. Miller III, Dimension-free path-integral molecular dynamics without preconditioning, The Journal of Chemical Physics 152 (2020), no. 10, 104102. |
| [46] | S. C. Kou, Qing Zhou, and Wing Hung Wong, Equi-energy sampler with applications in statistical inference and statistical mechanics, Ann. Statist. 34 (2006), no. 4, 1581-1652, With discussions and a rejoinder by the authors. · Zbl 1246.82054 |
| [47] | Benedict Leimkuhler, Charles Matthews, and Gabriel Stoltz, The computation of averages from equilibrium and nonequilibrium langevin molecular dynamics, IMA Journal of Numerical Analysis 36 (2016), no. 1, 13-79. · Zbl 1347.65014 |
| [48] | T. Lelièvre, M. Rousset, and G. Stoltz, Free energy computations: A mathematical perspective, 1st ed., Imperial College Press, 2010. · Zbl 1227.82002 |
| [49] | Faming Liang and Wing Hung Wong, Real-parameter evolutionary Monte Carlo with applications to Bayesian mixture models, J. Amer. Statist. Assoc. 96 (2001), no. 454, 653-666. · Zbl 1017.62022 |
| [50] | Jun S. Liu, Monte Carlo strategies in scientific computing, Springer Series in Statistics, Springer-Verlag, New York, 2001. · Zbl 0991.65001 |
| [51] | Samuel Livingstone, Michael Betancourt, Simon Byrne, and Mark Girolami, On the geometric ergodicity of Hamiltonian Monte Carlo, Bernoulli 25 (2019), no. 4A, 3109-3138. · Zbl 1428.62375 |
| [52] | Paul B. Mackenzie, An improved hybrid Monte Carlo Method, Phys. Lett. B 226 (1989), 369-371. |
| [53] | O. Mangoubi and A. Smith, Rapid mixing of hamiltonian monte carlo on strongly log-concave distributions, arXiv preprint 1708.07114v1 (2017). · Zbl 1476.60112 |
| [54] | J. C. Mattingly, A. M. Stuart, and D. J. Higham, Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise, Stoch. Proc. Appl. 101 (2002), no. 2, 185-232. · Zbl 1075.60072 |
| [55] | J. C. Mattingly, A. M. Stuart, and M. V. Tretyakov, Convergence of numerical time-averaging and stationary measures via Poisson equations, SIAM J. Num. Anal. 48 (2010), no. 2, 552-577. · Zbl 1217.65014 |
| [56] | H. P. McKean, Jr., A class of Markov processes associated with nonlinear parabolic equations, Proc. Nat. Acad. Sci. U.S.A. 56 (1966), 1907-1911. · Zbl 0149.13501 |
| [57] | Sylvie Méléard, Asymptotic behaviour of some interacting particle systems; McKean-Vlasov and Boltzmann models, Probabilistic models for nonlinear partial differential equations (Montecatini Terme, 1995), Lecture Notes in Math., vol. 1627, Springer, Berlin, 1996, pp. 42-95. · Zbl 0864.60077 |
| [58] | Stéphane Mischler and Clément Mouhot, Kac’s program in kinetic theory, Invent. Math. 193 (2013), no. 1, 1-147. · Zbl 1274.82048 |
| [59] | Radford M. Neal, MCMC using Hamiltonian dynamics, Handbook of Markov chain Monte Carlo, Chapman & Hall/CRC Handb. Mod. Stat. Methods, CRC Press, Boca Raton, FL, 2011, pp. 113-162. · Zbl 1229.65018 |
| [60] | Karl Oelschlager, A martingale approach to the law of large numbers for weakly interacting stochastic processes, The Annals of Probability (1984), 458-479. · Zbl 0544.60097 |
| [61] | Jakiw Pidstrigach, Convergence of preconditioned Hamiltonian Monte Carlo on Hilbert spaces, IMA Journal of Numerical Analysis (2022), drac052. |
| [62] | F. J. Pinski and A. M. Stuart, Transition paths in molecules at finite temperature, The Journal of Chemical Physics 132 (2010), no. 18, 184104. |
| [63] | G. O. Roberts and J. S. Rosenthal, Optimal scaling of discrete approximations to Langevin diffusions, J. Roy. Statist. Soc. Ser. B 60 (1998), 255-268. · Zbl 0913.60060 |
| [64] | G. O. Roberts and R. L. Tweedie, Exponential convergence of Langevin distributions and their discrete approximations, Bernoulli 2 (1996), 341-363. · Zbl 0870.60027 |
| [65] | C. Schütte, Conformational dynamics: Modeling, theory, algorithm, and application to biomolecules, Habilitation, Free University Berlin, 1999. |
| [66] | G. Stoltz, Some mathematical methods for molecular and multiscale simulation, Ph.D. thesis, Ecole Nationale des Ponts et Chaussées, 2007. |
| [67] | Alain-Sol Sznitman, Topics in propagation of chaos, École d’Été de Probabilités de Saint-Flour XIX—1989, Lecture Notes in Math., vol. 1464, Springer, Berlin, 1991, pp. 165-251. · Zbl 0732.60114 |
| [68] | D. Talay, Stochastic Hamiltonian systems: Exponential convergence to the invariant measure, and discretization by the implicit Euler scheme, Markov Processes and Related Fields 8 (2002), 1-36. |
| [69] | Julian Tugaut et al., Convergence to the equilibria for self-stabilizing processes in double-well landscape, Annals of Probability 41 (2013), no. 3A, 1427-1460. · Zbl 1292.60060 |
| [70] | Maxime Vono, Daniel Paulin, and Arnaud Doucet, Efficient MCMC sampling with dimension-free convergence rate using ADMM-type splitting, J. Mach. Learn. Res. 23 (2022), Paper No. [25], 69. · Zbl 07625178 |
| [71] | David J. Wales, Energy landscapes of clusters bound by short-ranged potentials, ChemPhysChem 11 (2010), no. 12, 2491-2494 |
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.
