Florian Maire
Universite de Montreal
Room: M3 3127
Non-reversible lifts of Metropolis-Hastings type Markov chains
Lifted samplers are a particular class of non-reversible MCMC algorithms which rely on an artificial momentum variable to avoid diffusive behaviors. While stemming from the statistical physics literature in the 90's, they have been recently, and successfully, applied in Bayesian statistics to a number of inference tasks including Model selection, Logistic regression and inference in Mixture models. These papers justify, in some sense, the general belief that ''lifting'' a reversible Markov chain leads to more efficient MCMC algorithms. However, general results supporting such a claim are lacking. In fact, we found a counter-example: lifting a particular reversible MCMC algorithm sampling from an Ising model in low temperature leads to asymptotic inefficiency.
The question our work addresses can be summarized as follows: ''to what degree of asymptotic inefficiency lifting a reversible MCMC can lead to?''. We provide an answer to this question under a very general framework, by: (i) introducing lifts based on neighborhood splitting schemes of a ''reference'' Metropolis-Hastings-type reversible Markov chain defined on an arbitrary state-space. (ii) showing that, under mild assumptions, such lifts cannot be more than twice as asymptotically inefficient as the reversible reference. Moreover, the constant 2 in our main result cannot be improved and is independent both of the observable of interest and of the target distribution. It is thus dimension free and tight.
Our work justifies that, while there is potentially a lot to gain from lifting a reversible Markov chain (as seen empirically in applications), there is not much to lose. Several illustrations (on both discrete and continuous state-spaces) will be presented. We will also discuss extension of our ideas to d-directional lifts and the search for optimal lifts.
This is joint work with Philippe Gagnon.