The Wang-Landau Algorithm as Stochastic Optimization and Its Acceleration

Abstract

We show that the Wang-Landau algorithm can be formulated as a stochastic gradient descent algorithm minimizing a smooth and convex objective function, of which the gradient is estimated using Markov chain Monte Carlo iterations. The optimization formulation provides us a new way to establish the convergence rate of the Wang-Landau algorithm, by exploiting the fact that almost surely, the density estimates (on the logarithmic scale) remain in a compact set, upon which the objective function is strongly convex. The optimization viewpoint motivates us to improve the efficiency of the Wang-Landau algorithm using popular tools including the momentum method and the adaptive learning rate method. We demonstrate the accelerated Wang-Landau algorithm on a two-dimensional Ising model and a two-dimensional ten-state Potts model.

arXiv comment10 pages, 3 figures

References in corpus (28)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• An overview of gradient descent optimization algorithms
• An efficient, multiple range random walk algorithm to calculate the density of states
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Fast Algorithm to Calculate Density of States
• On the Wang-Landau Method for Off-Lattice Simulations in the "Uniform" Ensemble
• Understanding and Improving the Wang-Landau Algorithm
• Wang-Landau algorithm for continuous models and joint density of states
• A generic, hierarchical framework for massively parallel Wang-Landau sampling
• Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
• Sampling along reaction coordinates with the Wang-Landau method
• The density of states in gauge theories
• Transitions of tethered polymer chains: A simulation study with the bond fluctuation lattice model
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Versatile approach to access the low temperature thermodynamics of lattice polymers and proteins
• Three-dimensional antiferromagnetic q-state Potts models: application of the Wang-Landau algorithm
• Lack of self-averaging of the specific heat in the three-dimensional random-field Ising model
• Optimal Modification Factor and Convergence of the Wang-Landau Algorithm
• Wang-Landau Monte Carlo simulation of isotropic-nematic transition in liquid crystals
• Ground states and thermal states of the random field Ising model
• Combination of improved multibondic method and the Wang-Landau method
• Absence of Dipole Glass Transition for Randomly Dilute Classical Ising Dipoles
• Phase Diagram of the 3D Bimodal Random-Field Ising Model
• Dynamics of the Wang-Landau algorithm and complexity of rare events for the three-dimensional bimodal Ising spin glass
• Wang-Landau study of the critical behaviour of the bimodal 3D-Random Field Ising Model
• Overcoming the critical slowing down of flat-histogram Monte Carlo simulations: Cluster updates and optimized broad-histogram ensembles
• Sampling the two-dimensional density of states g(E,M) of a giant magnetic molecule using the Wang-Landau method

Cited by in corpus (3)

• Efficient sampling using Macrocanonical Monte Carlo and density of states mapping
• A splitting Hamiltonian Monte Carlo method for efficient sampling
• Monte Carlo Approximation of Bayes Factors via Mixing with Surrogate Distributions