Title: Non-reversible parallel tempering: An embarrassingly parallel MCMC scheme
Authors: Saifuddin Syed - University of British Columbia (Canada) [presenting]
Alexandre Bouchard - University of British Columbia (Canada)
George Deligiannidis - University of Oxford (United Kingdom)
Arnaud Doucet - University of Oxford (United Kingdom)
Abstract: MCMC methods are widely used to approximate intractable expectations with respect to high-dimensional un-normalized probability distributions. We construct a Markov chain with the desired stationary distribution to explore our sample space. In theory, the chain should accurately explore the state space asymptotically, but in practice, it can get trapped exploring local regions of high probability and suffer from poor mixing in a finite time. Parallel tempering (PT) algorithms were introduced to tackle this issue. We delegate the task of exploration to additional heated chains running in parallel with better mixing properties. They then communicate with the target chain of interest and help it discover new unexplored regions of the sample space. Since their introduction in the 90's, PT algorithms are still extensively used to improve mixing in hard sampling problems arising in statistics, physics, computational chemistry, phylogenetics, and machine learning. We will give an introduction to PT algorithms, determine their scaling behaviour, efficiency, and limitations. Consequentially, we will establish the theoretically optimal non-reversible version of PT for a general class of sampling problems, as well an efficient and easy to implement adaptive algorithm.