The zig-zag process and super-efficient sampling for Bayesian analysis of big data

DOI10.1214/18-AOS1715zbMATH Open1417.65008OpenAlexW3104370808WikidataQ128371771 ScholiaQ128371771MaRDI QIDQ144289FDOQ144289

Authors Joris Bierkens, Paul Fearnhead, Gareth Roberts, Joris Bierkens, Paul Fearnhead, Gareth O. Roberts

Publication date 11 July 2016

Published in The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

MCMCexact samplingnonreversible Markov processpiecewise deterministic Markov processstochastic gradient Langevin dynamicssub-sampling

Mathematics Subject Classification ID

Bayesian inference (62F15) Monte Carlo methods (65C05) Continuous-time Markov processes on general state spaces (60J25)

Abstract: Standard MCMC methods can scale poorly to big data settings due to the need to evaluate the likelihood at each iteration. There have been a number of approximate MCMC algorithms that use sub-sampling ideas to reduce this computational burden, but with the drawback that these algorithms no longer target the true posterior distribution. We introduce a new family of Monte Carlo methods based upon a multi-dimensional version of the Zig-Zag process of (Bierkens, Roberts, 2017), a continuous time piecewise deterministic Markov process. While traditional MCMC methods are reversible by construction (a property which is known to inhibit rapid convergence) the Zig-Zag process offers a flexible non-reversible alternative which we observe to often have favourable convergence properties. We show how the Zig-Zag process can be simulated without discretisation error, and give conditions for the process to be ergodic. Most importantly, we introduce a sub-sampling version of the Zig-Zag process that is an example of an {em exact approximate scheme}, i.e. the resulting approximate process still has the posterior as its stationary distribution. Furthermore, if we use a control-variate idea to reduce the variance of our unbiased estimator, then the Zig-Zag process can be super-efficient: after an initial pre-processing step, essentially independent samples from the posterior distribution are obtained at a computational cost which does not depend on the size of the data.

Recommendations

• Automatic zig-zag sampling in practice
• Limit theorems for the zig-zag process
• Speeding Up MCMC by Efficient Data Subsampling
• Piecewise deterministic Markov processes for continuous-time Monte Carlo
• Ergodicity of the zigzag process

Cited in

(87)

• Bayesian Inference in Common Microeconometric Models With Massive Datasets by Double Marginalized Subsampling
• Super-efficient exact Hamiltonian Monte Carlo for the von Mises distribution
• Mini-Batch Metropolis–Hastings With Reversible SGLD Proposal
• Gradient flows and randomised thresholding: sparse inversion and classification
• Transport map accelerated adaptive importance sampling, and application to inverse problems arising from multiscale stochastic reaction networks
• Concave-Convex PDMP-based Sampling
• A langevinized ensemble Kalman filter for large-scale dynamic learning
• Reversible Jump PDMP Samplers for Variable Selection
• scientific article; zbMATH DE number 7387626 (Why is no real title available?)
• NuZZ: numerical Zig-Zag sampling for general models
• Sampling constrained continuous probability distributions: a review
• Strong invariance principles for ergodic Markov processes
• Speeding up the zig-zag process
• Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Rates
• Strong convergence to two-dimensional alternating Brownian motion processes
• Computing Bayes: from then `til now
• Sampling algorithms in statistical physics: a guide for statistics and machine learning
• Constructing sampling schemes via coupling: Markov semigroups and optimal transport
• Divide-and-conquer Metropolis-Hastings samplers with matched samples
• Speed up Zig-Zag
• Transport Monte Carlo: High-Accuracy Posterior Approximation via Random Transport
• Adaptive Importance Sampling Based on Fault Tree Analysis for Piecewise Deterministic Markov Process
• Posterior computation with the Gibbs zig-zag sampler
• Sampling using adaptive regenerative processes
• PDMP characterisation of event-chain Monte Carlo algorithms for particle systems
• Randomized time Riemannian manifold Hamiltonian Monte Carlo
• Birth–death dynamics for sampling: global convergence, approximations and their asymptotics
• Contraction rate estimates of stochastic gradient kinetic Langevin integrators
• Generalizing Parallel Replica Dynamics: Trajectory Fragments, Asynchronous Computing, and PDMPs
• Approximations of piecewise deterministic Markov processes and their convergence properties
• High-dimensional scaling limits of piecewise deterministic sampling algorithms
• Control variates for stochastic gradient MCMC
• scientific article; zbMATH DE number 7370608 (Why is no real title available?)
• Spatiotemporal blocking of the bouncy particle sampler for efficient inference in state-space models
• Some results on generalized accelerated motions driven by the telegraph process
• Is there an analog of Nesterov acceleration for gradient-based MCMC?
• Hypocoercivity of piecewise deterministic Markov process-Monte Carlo
• Subgeometric hypocoercivity for piecewise-deterministic Markov process Monte Carlo methods
• Low-lying eigenvalues and convergence to the equilibrium of some piecewise deterministic Markov processes generators in the small temperature regime
• Probabilistic analysis of systems alternating for state-dependent dichotomous noise
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient
• Rayleigh random flights on the Poisson line SIRSN
• Stochastic gradient Markov chain Monte Carlo
• Conservative random walk
• Adaptive schemes for piecewise deterministic Monte Carlo algorithms
• A piecewise deterministic Monte Carlo method for diffusion bridges
• The Block-Poisson Estimator for Optimally Tuned Exact Subsampling MCMC
• Peskun-Tierney ordering for Markovian Monte Carlo: beyond the reversible scenario
• A note on the polynomial ergodicity of the one-dimensional Zig-Zag process
• Piecewise deterministic Markov processes for scalable Monte Carlo on restricted domains
• Regeneration-enriched Markov processes with application to Monte Carlo
• Non-reversible guided Metropolis kernel
• Cores for piecewise-deterministic Markov processes used in Markov chain Monte Carlo
• Subsampling MCMC -- an introduction for the survey statistician
• On explicit \(L^2\)-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Limit theorems for the zig-zag process
• Couplings for Andersen dynamics
• Piecewise deterministic Markov processes and their invariant measures
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• Geometric ergodicity of the bouncy particle sampler
• Kinetic walks for sampling
• A Benchmark for the Bayesian Inversion of Coefficients in Partial Differential Equations
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• Gradient-Based Markov Chain Monte Carlo for Bayesian Inference With Non-differentiable Priors
• Stochastic gradient Langevin dynamics with adaptive drifts
• Irreversible samplers from jump and continuous Markov processes
• Zig-Zag Sampling for Discrete Structures and Nonreversible Phylogenetic MCMC
• Spectral analysis of the zigzag process
• Polynomial convergence rates of piecewise deterministic Markov processes
• Hamiltonian Monte Carlo with energy conserving subsampling
• Large deviations for the empirical measure of the zig-zag process
• Analysis of stochastic gradient descent in continuous time
• Informed sub-sampling MCMC: approximate Bayesian inference for large datasets
• Automatic zig-zag sampling in practice
• Sticky PDMP samplers for sparse and local inference problems
• Hamiltonian-Assisted Metropolis Sampling
• Infinite dimensional piecewise deterministic Markov processes
• RZigZag
• Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains
• Efficient real-time monitoring of an emerging influenza pandemic: how feasible?
• Highly Scalable Bayesian Geostatistical Modeling via Meshed Gaussian Processes on Partitioned Domains
• Coordinate sampler: a non-reversible Gibbs-like MCMC sampler
• On the convergence time of some non-reversible Markov chain Monte Carlo methods
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• 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

This page was built for publication: The zig-zag process and super-efficient sampling for Bayesian analysis of big data

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