the Wang-Landau algorithm reaches the flat histogram in finite time
Pierre Jacob and Robin Ryder (from Paris-Dauphine, CREST, and Statisfaction) have just arXived (and submitted to the Annals of Applied Probability) a neat result on the Wang-Landau algorithm. (This algorithm, which modifies the target in a sort of reweighted partioned sampling to achieve faster convergence, has always been perplexing to me.) They show that some variations of the Wang-Landau algorithm meet the flat histogram criterion in finite time, and, just as importantly that other variations do not reach this criterion. The proof uses elegant Markov chain arguments and I hope the paper makes it through, as there are very few theoretical results on this algorithm. (Pierre also wrote recently a paper with Luke Bornn, Arnaud Doucet, and Pierre Del Moral, on An Adaptive Interacting Wang-Landau Algorithm for Automatic Density Exploration last week, with an associated R package. Not yet on CRAN.)
January 25, 2012 at 12:12 am
[…] Today, I am attending a workshop on the use of graphics processing units in Statistics in Warwick, supported by CRiSM, presenting our recent works with Randal Douc, Pierre Jacob and Murray Smith. (I will use the same slides as in Telecom two months ago, hopefully avoiding the loss of integral and summation signs this time!) Pierre Jacob will talk about Wang-Landau. […]
October 20, 2011 at 12:16 pm
[…] Xi'an's Og an attempt at bloggin, from scratch… « the Wang-Landau algorithm reaches the flat histogram in finite time […]
October 20, 2011 at 12:22 am
Cheers for the advertisement. Robin blogged about it earlier today:
http://robinryder.wordpress.com/
and we’ll post something on statisfaction too.
The R package for the adaptive Wang-Landau should be submitted to CRAN soon.