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

DOI10.1080/01621459.2017.1294075zbMATH Open1398.60084arXiv1510.02451OpenAlexW2963561977MaRDI QIDQ144293FDOQ144293

Authors: Alexandre Bouchard-Côté, Sebastian J. Vollmer, Arnaud Doucet, Alexandre Bouchard-Côté, Arnaud Doucet, Sebastian J. Vollmer 

Publication date: 8 October 2015

Published in: Journal of the American Statistical Association (Search for Journal in Brave)

Abstract: Markov chain Monte Carlo methods have become standard tools in statistics to sample from complex probability measures. Many available techniques rely on discrete-time reversible Markov chains whose transition kernels build up over the Metropolis-Hastings algorithm. We explore and propose several original extensions of an alternative approach introduced recently in Peters and de With (2012) where the target distribution of interest is explored using a continuous-time Markov process. In the Metropolis-Hastings algorithm, a trial move to a region of lower target density, equivalently "higher energy", than the current state can be rejected with positive probability. In this alternative approach, a particle moves along straight lines continuously around the space and, when facing a high energy barrier, it is not rejected but its path is modified by bouncing against this barrier. The resulting non-reversible Markov process provides a rejection-free MCMC sampling scheme. We propose several original techniques to simulate this continuous-time process exactly in a wide range of scenarios of interest to statisticians. When the target distribution factorizes as a product of factors involving only subsets of variables, such as the posterior distribution associated to a probabilistic graphical model, it is possible to modify the original algorithm to exploit this structure and update in parallel variables within each clique. We present several extensions by proposing methods to sample mixed discrete-continuous distributions and distributions restricted to a connected smooth domain. We also show that it is possible to move the particle using a general flow instead of straight lines. We demonstrate the efficiency of this methodology through simulations on a variety of applications and show that it can outperform Hybrid Monte Carlo schemes in interesting scenarios.

Full work available at URL: https://arxiv.org/abs/1510.02451

Recommendations

• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• A flexible particle Markov chain Monte Carlo method
• Particle Markov Chain Monte Carlo Methods
• Reversible Jump, Birth-and-Death and More General Continuous Time Markov Chain Monte Carlo Samplers
• Coordinate sampler: a non-reversible Gibbs-like MCMC sampler
• A dynamic programming approach to efficient sampling from Boltzmann distributions
• Analysis of high-dimensional continuous time Markov chains using the local bouncy particle sampler
• Irreversible Monte Carlo algorithms for efficient sampling
• Without-replacement sampling for particle methods on finite state spaces
• Efficient Construction of Reversible Jump Markov Chain Monte Carlo Proposal Distributions

zbMATH Keywords

Markov chain Monte Carloinhomogeneous Poisson processpiecewise deterministic Markov processprobabilistic graphical modelsrejection-free simulation

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Bayesian inference (62F15) Multivariate analysis (62H99) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55)

Cites Work

• The no-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo
• Monte Carlo strategies in scientific computing.
• Graphical models, exponential families, and variational inference
• Title not available (Why is that?)
• Optimal scaling for various Metropolis-Hastings algorithms.
• Consistency and fluctuations for stochastic gradient Langevin dynamics
• Title not available (Why is that?)
• Markov chain Monte Carlo and irreversibility
• Riemann manifold Langevin and Hamiltonian Monte Carlo methods. With discussion and authors' reply
• Bayesian analysis of continuous time Markov chains with application to phylogenetic modelling
• Title not available (Why is that?)

Cited In (78)

• Subsampling MCMC -- an introduction for the survey statistician
• On explicit \(L^2\)-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Automatic zig-zag sampling in practice
• Sticky PDMP samplers for sparse and local inference problems
• Collective proposal distributions for nonlinear MCMC samplers: mean-field theory and fast implementation
• Infinite dimensional piecewise deterministic Markov processes
• Spectral analysis of the zigzag process
• Markov chain simulation for multilevel Monte Carlo
• Gradient-Based Markov Chain Monte Carlo for Bayesian Inference With Non-differentiable Priors
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• Piecewise deterministic Markov processes for continuous-time Monte Carlo
• Piecewise deterministic Markov processes for scalable Monte Carlo on restricted domains
• Efficient Simulation of Sparse Graphs of Point Processes
• Reversible and non-reversible Markov chain Monte Carlo algorithms for reservoir simulation problems
• Regeneration-enriched Markov processes with application to Monte Carlo
• Coordinate sampler: a non-reversible Gibbs-like MCMC sampler
• Polynomial convergence rates of piecewise deterministic Markov processes
• Low-lying eigenvalues and convergence to the equilibrium of some piecewise deterministic Markov processes generators in the small temperature regime
• Statistical challenges in tracking the evolution of SARS-CoV-2
• Bayesian nonparametric clustering for large data sets
• Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains
• Large-scale inference of correlation among mixed-type biological traits with phylogenetic multivariate probit models
• Hypocoercivity of piecewise deterministic Markov process-Monte Carlo
• Modified Hamiltonian Monte Carlo for Bayesian inference
• Stochastic gradient Markov chain Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Geometric ergodicity of the bouncy particle sampler
• Is there an analog of Nesterov acceleration for gradient-based MCMC?
• Subgeometric hypocoercivity for piecewise-deterministic Markov process Monte Carlo methods
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient
• The Block-Poisson Estimator for Optimally Tuned Exact Subsampling MCMC
• Stochastic gradient Langevin dynamics with adaptive drifts
• Irreversible samplers from jump and continuous Markov processes
• Adaptive schemes for piecewise deterministic Monte Carlo algorithms
• Peskun-Tierney ordering for Markovian Monte Carlo: beyond the reversible scenario
• Spatiotemporal blocking of the bouncy particle sampler for efficient inference in state-space models
• Markov chain Monte Carlo algorithms with sequential proposals
• Kinetic walks for sampling
• A piecewise deterministic Monte Carlo method for diffusion bridges
• Non-reversible guided Metropolis kernel
• Piecewise deterministic Markov processes and their invariant measures
• Large deviations for the empirical measure of the zig-zag process
• Hamiltonian-Assisted Metropolis Sampling
• On the convergence time of some non-reversible Markov chain Monte Carlo methods
• Title not available (Why is that?)
• Advanced Multilevel Monte Carlo Methods
• RZigZag
• Cores for piecewise-deterministic Markov processes used in Markov chain Monte Carlo
• Comment: A brief survey of the current state of play for Bayesian computation in data science at big-data scale
• Ergodicity of the zigzag process
• Optimal scaling of the MALA algorithm with irreversible proposals for Gaussian targets
• Simulating Coulomb and log-gases with hybrid Monte Carlo algorithms
• Sparse hard-disk packings and local Markov chains
• Approximations of piecewise deterministic Markov processes and their convergence properties
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Limit theorems for the zig-zag process
• A langevinized ensemble Kalman filter for large-scale dynamic learning
• Speed up Zig-Zag
• On the accept-reject mechanism for Metropolis-Hastings algorithms
• Generalizing Parallel Replica Dynamics: Trajectory Fragments, Asynchronous Computing, and PDMPs
• Transport Monte Carlo: High-Accuracy Posterior Approximation via Random Transport
• Reversible Jump PDMP Samplers for Variable Selection
• A fresh Take on ‘Barker Dynamics’ for MCMC
• Title not available (Why is that?)
• Constructing sampling schemes via coupling: Markov semigroups and optimal transport
• Birth–death dynamics for sampling: global convergence, approximations and their asymptotics
• Concave-Convex PDMP-based Sampling
• Speeding up the zig-zag process
• Randomized time Riemannian manifold Hamiltonian Monte Carlo
• Sampling using adaptive regenerative processes
• Strong invariance principles for ergodic Markov processes
• Posterior computation with the Gibbs zig-zag sampler
• Transport map accelerated adaptive importance sampling, and application to inverse problems arising from multiscale stochastic reaction networks
• Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Rates
• PDMP characterisation of event-chain Monte Carlo algorithms for particle systems
• Contraction rate estimates of stochastic gradient kinetic Langevin integrators
• Sampling algorithms in statistical physics: a guide for statistics and machine learning
• Adaptive Importance Sampling Based on Fault Tree Analysis for Piecewise Deterministic Markov Process

Uses Software

• MrBayes
• mcmcse
• NUTS

This page was built for publication: The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q144293)