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

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?)

  • [1] 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 (2006f:62074), https://doi.org/10.1137/S0363012902417267
  • [2] 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 (2011g:62216)
  • [3] V. Babin, C. Roland, and C. Sagui, Adaptively biased molecular dynamics for free energy calculations, J. Chem. Phys. 128 (2008), 134101.
  • [4] A. Benveniste, M. Métivier, and Priouret P., Adaptive Algorithms and Stochastic Approximations, Springer-Verlag, 1987.
  • [5] 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, https://doi.org/10.1080/10618600.2012.723569
  • [6] 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 (89b:62180), https://doi.org/10.1016/0304-4149(87)90039-1
  • [7] 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, https://doi.org/10.1007/s11222-011-9257-9
  • [8] E. Darve and A. Pohorille, Calculating free energies using average force, J. Chem. Phys. 115 (2001), no. 20, 9169-9183.
  • [9] 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.
  • [10] G. Fort, Central Limit Theorems for Stochastic Approximation with Controlled Markov chain Dynamics, to appear in ESAIM:PS (2015).
  • [11] G. Fort, B. Jourdain, T. Lelièvre and G. Stoltz, Self-healing umbrella sampling: convergence and efficiency, http://arxiv.org/abs/1410.2109.
  • [12] 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.
  • [13] 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, https://doi.org/10.1214/11-AOS938
  • [14] 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 (83a:60001)
  • [15] W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57 (1970), 97-109.
  • [16] J. Hénin and C. Chipot, Overcoming free energy barriers using unconstrained molecular dynamics simulations, J. Chem. Phys. 121 (2004), no. 7, 2904-2914.
  • [17] 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, https://doi.org/10.1214/12-AAP913
  • [18] 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 (2012a:82066), https://doi.org/10.1051/m2an/2010044
  • [19] 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 (98h:62125)
  • [20] 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, https://doi.org/10.1007/s00205-011-0426-y
  • [21] T. Lelièvre, M. Rousset, and G. Stoltz, Computation of free energy profiles with adaptive parallel dynamics, J. Chem. Phys. 126 (2007), 134111.
  • [22] 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 (2010d:60220), https://doi.org/10.1088/0951-7715/21/6/001
  • [23] Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz, Free Energy Computations, Imperial College Press, London, 2010. A mathematical perspective. MR 2681239 (2012c:82068)
  • [24] Jérôme Lelong, Almost sure convergence for randomly truncated stochastic algorithms under verifiable conditions, Statist. Probab. Lett. 78 (2008), no. 16, 2632-2636. MR 2542461, https://doi.org/10.1016/j.spl.2008.02.034
  • [25] F. Liang, A general Wang-Landau algorithm for Monte Carlo computation, J. Am. Stat. Assoc. 100 (2005), 1311-1327.
  • [26] 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, https://doi.org/10.1198/016214506000001202
  • [27] 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.
  • [28] 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.
  • [29] S. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, Cambridge, 2009.
  • [30] 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.
  • [31] Herbert Robbins and Sutton Monro, A stochastic approximation method, Ann. Math. Statistics 22 (1951), 400-407. MR 0042668 (13,144j)
  • [32] 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.
  • [33] 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

DOI: https://doi.org/10.1090/S0025-5718-2015-02952-4
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

American Mathematical Society