Convergence of the Wang-Landau algorithm
HTML articles powered by AMS MathViewer
- by Gersende Fort, Benjamin Jourdain, Estelle Kuhn, Tony Lelièvre and Gabriel Stoltz PDF
- Math. Comp. 84 (2015), 2297-2327 Request permission
Abstract:
We analyze the convergence properties of the Wang-Landau algorithm. This sampling method belongs to the general class of adaptive importance sampling strategies which use the free energy along a chosen reaction coordinate as a bias. Such algorithms are very helpful to enhance the sampling properties of Markov Chain Monte Carlo algorithms, when the dynamics is metastable. We prove the convergence of the Wang-Landau algorithm and an associated central limit theorem.References
- Christophe Andrieu, Éric Moulines, and Pierre Priouret, Stability of stochastic approximation under verifiable conditions, SIAM J. Control Optim. 44 (2005), no. 1, 283–312. MR 2177157, DOI 10.1137/S0363012902417267
- Yves F. Atchadé and Jun S. Liu, The Wang-Landau algorithm in general state spaces: applications and convergence analysis, Statist. Sinica 20 (2010), no. 1, 209–233. MR 2640691
- V. Babin, C. Roland, and C. Sagui, Adaptively biased molecular dynamics for free energy calculations, J. Chem. Phys. 128 (2008), 134101.
- A. Benveniste, M. Métivier, and Priouret P., Adaptive Algorithms and Stochastic Approximations, Springer-Verlag, 1987.
- Luke Bornn, Pierre E. Jacob, Pierre Del Moral, and Arnaud Doucet, An adaptive interacting Wang-Landau algorithm for automatic density exploration, J. Comput. Graph. Statist. 22 (2013), no. 3, 749–773. MR 3173740, DOI 10.1080/10618600.2012.723569
- Han Fu Chen, Guo Lei, and Ai Jun Gao, Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds, Stochastic Process. Appl. 27 (1988), no. 2, 217–231. MR 931029, DOI 10.1016/0304-4149(87)90039-1
- Nicolas Chopin, Tony Lelièvre, and Gabriel Stoltz, Free energy methods for Bayesian inference: efficient exploration of univariate Gaussian mixture posteriors, Stat. Comput. 22 (2012), no. 4, 897–916. MR 2913791, DOI 10.1007/s11222-011-9257-9
- E. Darve and A. Pohorille, Calculating free energies using average force, J. Chem. Phys. 115 (2001), no. 20, 9169–9183.
- B. Dickson, F. Legoll, T. Lelièvre, G. Stoltz, and P. Fleurat-Lessard, Free energy calculations: An efficient adaptive biasing potential method, J. Phys. Chem. B 114 (2010), 5823–5830.
- G. Fort, Central Limit Theorems for Stochastic Approximation with Controlled Markov chain Dynamics, to appear in ESAIM:PS (2015).
- G. Fort, B. Jourdain, T. Lelièvre and G. Stoltz, Self-healing umbrella sampling: convergence and efficiency, http://arxiv.org/abs/1410.2109.
- G. Fort, B. Jourdain, E. Kuhn, T. Lelièvre and G. Stoltz, Efficiency of the Wang-Landau algorithm: a simple test case, Appl. Math. Res. Express AMRX 2014 (2014), no. 2, 275–311.
- G. Fort, E. Moulines, and P. Priouret, Convergence of adaptive and interacting Markov chain Monte Carlo algorithms, Ann. Statist. 39 (2011), no. 6, 3262–3289. MR 3012408, DOI 10.1214/11-AOS938
- P. Hall and C. C. Heyde, Martingale limit theory and its application, Probability and Mathematical Statistics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 624435
- W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57 (1970), 97–109.
- J. Hénin and C. Chipot, Overcoming free energy barriers using unconstrained molecular dynamics simulations, J. Chem. Phys. 121 (2004), no. 7, 2904–2914.
- Pierre E. Jacob and Robin J. Ryder, The Wang-Landau algorithm reaches the flat histogram criterion in finite time, Ann. Appl. Probab. 24 (2014), no. 1, 34–53. MR 3161640, DOI 10.1214/12-AAP913
- Benjamin Jourdain, Tony Lelièvre, and Raphaël Roux, Existence, uniqueness and convergence of a particle approximation for the adaptive biasing force process, M2AN Math. Model. Numer. Anal. 44 (2010), no. 5, 831–865. MR 2731395, DOI 10.1051/m2an/2010044
- Harold J. Kushner and G. George Yin, Stochastic approximation algorithms and applications, Applications of Mathematics (New York), vol. 35, Springer-Verlag, New York, 1997. MR 1453116, DOI 10.1007/978-1-4899-2696-8
- T. Lelièvre and K. Minoukadeh, Long-time convergence of an adaptive biasing force method: the bi-channel case, Arch. Ration. Mech. Anal. 202 (2011), no. 1, 1–34. MR 2835861, DOI 10.1007/s00205-011-0426-y
- T. Lelièvre, M. Rousset, and G. Stoltz, Computation of free energy profiles with adaptive parallel dynamics, J. Chem. Phys. 126 (2007), 134111.
- Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz, Long-time convergence of an adaptive biasing force method, Nonlinearity 21 (2008), no. 6, 1155–1181. MR 2422373, DOI 10.1088/0951-7715/21/6/001
- Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz, Free energy computations, Imperial College Press, London, 2010. A mathematical perspective. MR 2681239, DOI 10.1142/9781848162488
- Jérôme Lelong, Almost sure convergence of randomly truncated stochastic algorithms under verifiable conditions, Statist. Probab. Lett. 78 (2008), no. 16, 2632–2636. MR 2542461, DOI 10.1016/j.spl.2008.02.034
- F. Liang, A general Wang-Landau algorithm for Monte Carlo computation, J. Am. Stat. Assoc. 100 (2005), 1311–1327.
- Faming Liang, Chuanhai Liu, and Raymond J. Carroll, Stochastic approximation in Monte Carlo computation, J. Amer. Statist. Assoc. 102 (2007), no. 477, 305–320. MR 2345544, DOI 10.1198/016214506000001202
- S. Marsili, A. Barducci, R. Chelli, P. Procacci, and V. Schettino, Self-healing Umbrella Sampling: A non-equilibrium approach for quantitative free energy calculations, J. Phys. Chem. B 110 (2006), no. 29, 14011–14013.
- N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equations of state calculations by fast computing machines, J. Chem. Phys. 21 (1953), no. 6, 1087–1091.
- S. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, Cambridge, 2009.
- K. Minoukadeh, C. Chipot, and T. Lelièvre, Potential of mean force calculations: a multiple-walker adaptive biasing force approach, J. Chem. Th. Comput. 6 (2010), no. 4, 1008–1017.
- Herbert Robbins and Sutton Monro, A stochastic approximation method, Ann. Math. Statistics 22 (1951), 400–407. MR 42668, DOI 10.1214/aoms/1177729586
- F. G. 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 (2001), 056101.
- F. G. Wang and D. P. Landau, Efficient, multiple-range random walk algorithm to calculate the density of states, Phys. Rev. Lett. 86 (2001), no. 10, 2050–2053.
Additional Information
- Gersende Fort
- Affiliation: LTCI, CNRS & Telecom ParisTech, 46 rue Barrault, 75634 Paris Cedex 13, France
- Email: gersende.fort@telecom-paristech.fr
- Benjamin Jourdain
- Affiliation: Université Paris-Est, CERMICS (ENPC), INRIA, 6-8 Avenue Blaise Pascal, F-77455 Marne-la-Vallée
- Email: jourdain@cermics.enpc.fr
- Estelle Kuhn
- Affiliation: INRA Unité MIA, Domaine de Vilvert, 78352 Jouy-en-Josas Cedex, France
- Email: estelle.kuhn@jouy.inra.fr
- Tony Lelièvre
- Affiliation: Université Paris-Est, CERMICS (ENPC), INRIA, 6-8 Avenue Blaise Pascal, F-77455 Marne-la-Vallée
- Email: lelievre@cermics.enpc.fr
- Gabriel Stoltz
- Affiliation: Université Paris-Est, CERMICS (ENPC), INRIA, 6-8 Avenue Blaise Pascal, F-77455 Marne-la-Vallée
- Email: stoltz@cermics.enpc.fr
- Received by editor(s): July 30, 2012
- Received by editor(s) in revised form: September 26, 2013
- Published electronically: March 23, 2015
- Additional Notes: This work was supported by the French National Research Agency under the grants ANR-09-BLAN-0216-01 (MEGAS) and ANR-08-BLAN-0218 (BigMC)
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 2297-2327
- MSC (2010): Primary 65C05, 60J05, 82C80
- DOI: https://doi.org/10.1090/S0025-5718-2015-02952-4
- MathSciNet review: 3356027