Wang-Landau algorithm as stochastic optimization and its acceleration

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 another 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.

Figure 1

The computational overheads, in terms of the number of MC sweeps and the CPU time, that the AWL algorithm and the WL algorithm take to reach the first equilibration on the Ising model. Two initializations of the learning rate are tested out, including ${\eta }_0=0.05$ and ${\eta }_0=1.00$. The reported results are based on 50 independent runs of both algorithms. The dot represents the empirical mean and the error bar represents the empirical standard deviation.

Figure 2

The computational overheads, in terms of the number of MC sweeps and the CPU time, that the AWL algorithm and the WL algorithm take to reach the first equilibration on the Potts model. Two initializations of the learning rate are tested out, including ${\eta }_0=0.05$ and ${\eta }_0=1.00$. The reported results are based on 50 independent runs of both algorithms. The dot represents the empirical mean and the error bar represents the empirical standard deviation.

Figure 3

The dynamics of the estimation error $\epsilon \left(t\right)$ (on the logarithmic scale), averaging over 50 independent runs, of the AWL algorithm and the WL algorithm. Panel (a) shows the result for the Ising model, and panel (b) shows the result for the Potts model. ${\eta }_0$ denotes the initialization of the learning rate.