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

DOI10.1214/18-AOS1715zbMATH Open1417.65008arXiv1607.03188OpenAlexW3104370808WikidataQ128371771 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)

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.

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

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

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)

Cited In (86)

• 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
• Infinite dimensional piecewise deterministic Markov processes
• Informed sub-sampling MCMC: approximate Bayesian inference for large datasets
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• Spectral analysis of the zigzag process
• Analysis of stochastic gradient descent in continuous time
• Gradient-Based Markov Chain Monte Carlo for Bayesian Inference With Non-differentiable Priors
• Efficient real-time monitoring of an emerging influenza pandemic: how feasible?
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• Piecewise deterministic Markov processes for scalable Monte Carlo on restricted domains
• Hamiltonian Monte Carlo with energy conserving subsampling
• Regeneration-enriched Markov processes with application to Monte Carlo
• Zig-Zag Sampling for Discrete Structures and Nonreversible Phylogenetic MCMC
• 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
• Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains
• Hypocoercivity of piecewise deterministic Markov process-Monte Carlo
• Stochastic gradient Markov chain Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Couplings for Andersen dynamics
• 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
• Probabilistic analysis of systems alternating for state-dependent dichotomous noise
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient
• The Block-Poisson Estimator for Optimally Tuned Exact Subsampling MCMC
• Highly Scalable Bayesian Geostatistical Modeling via Meshed Gaussian Processes on Partitioned Domains
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• Stochastic gradient Langevin dynamics with adaptive drifts
• Irreversible samplers from jump and continuous Markov processes
• Some results on generalized accelerated motions driven by the telegraph process
• 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
• A Benchmark for the Bayesian Inversion of Coefficients in Partial Differential Equations
• Control variates for stochastic gradient MCMC
• A note on the polynomial ergodicity of the one-dimensional Zig-Zag process
• 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
• Rayleigh random flights on the Poisson line SIRSN
• On the convergence time of some non-reversible Markov chain Monte Carlo methods
• Title not available (Why is that?)
• 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
• Conservative random walk
• 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
• Divide-and-conquer Metropolis-Hastings samplers with matched samples
• Speed up Zig-Zag
• Generalizing Parallel Replica Dynamics: Trajectory Fragments, Asynchronous Computing, and PDMPs
• Strong convergence to two-dimensional alternating Brownian motion processes
• Transport Monte Carlo: High-Accuracy Posterior Approximation via Random Transport
• Gradient flows and randomised thresholding: sparse inversion and classification
• Reversible Jump PDMP Samplers for Variable Selection
• 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
• Mini-Batch Metropolis–Hastings With Reversible SGLD Proposal
• Sampling constrained continuous probability distributions: a review
• Concave-Convex PDMP-based Sampling
• Speeding up the zig-zag process
• Randomized time Riemannian manifold Hamiltonian Monte Carlo
• Bayesian Inference in Common Microeconometric Models With Massive Datasets by Double Marginalized Subsampling
• Super-efficient exact Hamiltonian Monte Carlo for the von Mises distribution
• 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
• Computing Bayes: from then `til now
• 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

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)