Archive for parallel tempering

A convective replica-exchange method for sampling new energy basins

Posted in Books, Statistics, University life with tags , , , , , , , , on September 18, 2013 by xi'an

I was recently asked to referee a PhD thesis at Institut Pasteur, written by Yannick Spill, in Bioinformatics which essentially focus on statistical and computational aspects. (Hence the request. The defence itself was today.) Among the several papers included in the thesis, there was this post-worthy paper called A convective replica-exchange method for sampling new energy basins written by Spill, Bouvier and Nilges and published in the Journal of Computational Chemistry, paper that extends the usual multiple tempering algorithm in a method called the convective replica exchange algorithm. Rather than selecting the chain to exchange at random, it forces a given chain to go through all temperature steps in a cyclic manner and only moves to another chain when the cycle is over. There is a delayed rejection flavour therein in that the method does not let go: it keeps proposing moves to the next level until one is accepted (hence earning from me the nickname of the pit-bull algorithm!). While the thesis includes a (corrected) proof of ergodicity of the method, I wonder if the proof could have been directly derived from a presentation of the algorithm as a reversible jump MCMC type algorithm (Green, 1995). The experiments presented in the paper are quite worthwhile in that they allayed my worries that this new version of replica exchange could be much slower than the original one, because of the constraint of moving a given chain to a given neighbouring level rather than picking those two entities at random. (Obviously, the performances would get worse with a sparser collection of inverse temperatures.) I am still uncertain however as to why compelling the exchange to take place in this heavily constrained way induces better dynamics for moving around the sampling space, my reasoning being that the proposals remain the same. However during the defence I realised that waiting for a switch would induce visiting more of the tails…

ABC-MCMC for parallel tempering

Posted in Mountains, pictures, Statistics, Travel, University life with tags , , , , , , , , , , , on February 9, 2012 by xi'an

In this paper a new algorithm combining population-based MCMC methods with ABC requirements is proposed, using an analogy with the Parallel Tempering algorithm (Geyer, 1991).

Another of those arXiv papers that had sat on my to-read pile for way too long: Likelihood-free parallel tempering by Meïli Baragtti, Agnès Grimaud, and Denys Pommeret, from Luminy, Marseilles. The paper mentions our population Monte Carlo (PMC) algorithm (Beaumont et al., 2009) and other ABC-SMC algorithms, but opts instead for an ABC-MCMC basis. The purpose is to build a parallel tempering method. Tolerances and temperatures evolve simultaneously. I however fail to see where the tempering occurs in the algorithm (page 7): there is a set of temperatures T1,….,TN, but they do not appear within the algorithm. My first idea of a tempering mechanism in a likelihood-free setting was to replicate our SAME algorithm (Doucet, Godsill, and Robert, 2004), by creating Tj copies of the [pseudo-]observations to mimic the likelihood taken to the power Tj. But this is annealing, not tempering, and I cannot think of the opposite of copies of the data. Unless of course a power of the likelihood can be simulated (and even then, what would the equivalent be for the data…?) Maybe a natural solution would be to operate some kind of data-attrition, e.g. by subsampling the original vector of observations.

Discussing the issue with Jean-Michel Marin, during a visit to Montpellier today, I realised that the true tempering came from the tolerances εi, while the temperatures Tj were there to calibrate the proposal distributions. And that the major innovation contained in the thesis (if not so clearly in the paper) was to boost exchanges between different tolerances, improving upon the regular ABC-MCMC sampler by an equi-energy move.