Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Convergence of the Wang-Landau algorithm


Authors: Gersende Fort, Benjamin Jourdain, Estelle Kuhn, Tony Lelièvre and Gabriel Stoltz
Journal: Math. Comp. 84 (2015), 2297-2327
MSC (2010): Primary 65C05, 60J05, 82C80
DOI: https://doi.org/10.1090/S0025-5718-2015-02952-4
Published electronically: March 23, 2015
MathSciNet review: 3356027
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0304-4149%2887%2990039-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 https://doi.org/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 https://doi.org/10.1214/11-AOS938
  • P. Hall and C. C. Heyde, Martingale limit theory and its application, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Probability and Mathematical Statistics. 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 https://doi.org/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 https://doi.org/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
  • 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 https://doi.org/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 https://doi.org/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
  • 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 https://doi.org/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 https://doi.org/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 https://doi.org/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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65C05, 60J05, 82C80

Retrieve articles in all journals with MSC (2010): 65C05, 60J05, 82C80


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)
Article copyright: © Copyright 2015 American Mathematical Society