Convergence of the Wang-Landau algorithm

Fort, Gersende; Jourdain, Benjamin; Kuhn, Estelle; Lelièvre, Tony; Stoltz, Gabriel

doi:10.1090/S0025-5718-2015-02952-4

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.