Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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.
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)
  • © 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