## 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