The Bouncy Particle Sampler: A Nonreversible Rejection-Free Markov Chain Monte Carlo Method

By Alexandre Bouchard-Cot'e, Sandra Jeanne Vollmer, Arnaud Doucet. 2015

258 citations recorded by the source corpus.

ABSTRACT Many Markov chain Monte Carlo techniques currently available rely on discrete-time reversible Markov processes whose transition kernels are variations of the Metropolis–Hastings algorithm. We explore and generalize an alternative scheme recently introduced in the physics literature (Peters and de With 2012) where the target distribution is explored using a continuous-time nonreversible piecewise-deterministic Markov process. In the Metropolis–Hastings algorithm, a trial move to a region of lower target density, equivalently of higher “energy,” than the current state can be rejected with positive probability. In this alternative approach, a particle moves along straight lines around the space and, when facing a high energy barrier, it is not rejected but its path is modified by bouncing against this barrier. By reformulating this algorithm using inhomogeneous Poisson processes, we exploit standard sampling techniques to simulate exactly this Markov process in a wide range of scenarios of interest. Additionally, when the target distribution is given by a product of factors dependent only on subsets of the state variables, such as the posterior distribution associated with a probabilistic graphical model, this method can be modified to take advantage of this structure by allowing computationally cheaper “local” bounces, which only involve the state variables associated with a factor, while the other state variables keep on evolving. In this context, by leveraging techniques from chemical kinetics, we propose several computationally efficient implementations. Experimentally, this new class of Markov chain Monte Carlo schemes compares favorably to state-of-the-art methods on various Bayesian inference tasks, including for high-dimensional models and large datasets. Supplementary materials for this article are available online.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fa089768cfdd726e4309478687c26ebab74416a9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Efficient posterior sampling for high-dimensional imbalanced logistic regression. (2019, methodology): “This construction is related to ideas in [10].”
Exponential ergodicity of the bouncy particle sampler (2017, methodology): “It has been shown in [6] that BPS without refreshment is not ergodic as the process can remain forever outside a ball of positive radius.”
Ergodicity of the zigzag process (2017, background): “of the stationary probability distribution of (Xt,Θt) is equal to a prescribed density function π. Other variants of PDMPs with similar properties exist, for example the Bouncy Particle Sampler (BPS, [10]) which selects its direction from Rd or the unit sphere in Rd. In order for a Markov process to”
Posterior Computation with the Gibbs Zig-Zag Sampler (2020, methodology): “In terms of its construction, the coordinate sampler falls into the same framework as other popular PDMP processes such as the ZZ sampler (Bierkens et al., 2019a) and the BPS (Bouchard-Cˆot´e et al., 2018), and unlike the GZZ process, it does not allow the incorporation of MH-updates.”
Geometric ergodicity of the Bouncy Particle Sampler (2018, methodology): “Following [8], we refer to it as the Bouncy Particle Sampler (BPS).”
On Markov chain Monte Carlo methods for tall data (2015, methodology): “First, for subsampling to preserve the invariant distribution, the statistical model under consideration needs to satisfy strong regularity conditions, which have only been established for logistic regression; see (Bouchard-Côté et al., 2015) and (Bierkens et al.”
Piecewise deterministic Markov processes and their invariant measures (2018, background): “For the BPS process, λ is not in C 1 ( M ) so that we cannot apply the previous theory.”