The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data

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.

References in corpus (3)

• The pseudo-marginal approach for efficient Monte Carlo computations
• Irreversible Langevin samplers and variance reduction: a large deviation approach
• Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo

Cited by in corpus (35)

• A newcomer's guide to deep learning for inverse design in nano-photonics
• Ergodicity of the zigzag process
• Highly Scalable Bayesian Geostatistical Modeling via Meshed Gaussian Processes on Partitioned Domains
• Speedups in nonequilibrium thermal relaxation: Mpemba and related effects
• Analysis of Stochastic Gradient Descent in Continuous Time
• A practical guide to pseudo-marginal methods for computational inference in systems biology
• Bayesian Mechanics for Stationary Processes
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• A piecewise deterministic Monte Carlo method for diffusion bridges
• On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Regeneration-enriched Markov processes with application to Monte Carlo
• Couplings for Andersen Dynamics
• PDMP characterisation of event-chain Monte Carlo algorithms for particle systems
• Birth-death dynamics for sampling: Global convergence, approximations and their asymptotics
• Hard-disk dipoles and non-reversible Markov chains
• Computing Bayes: From Then 'Til Now'
• Subgeometric hypocoercivity for piecewise-deterministic Markov process Monte Carlo methods
• Concepts in Monte Carlo sampling
• Sticky PDMP samplers for sparse and local inference problems
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents
• Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains
• Cores for Piecewise-Deterministic Markov Processes used in Markov Chain Monte Carlo
• Zig-zag sampling for discrete structures and non-reversible phylogenetic MCMC
• Non-reversible lifts of reversible diffusion processes and relaxation times
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Sampling Constrained Continuous Probability Distributions: A Review
• Sampling algorithms in statistical physics: a guide for statistics and machine learning
• Velocity Jumps for Molecular Dynamics
• Extending JumpProcess.jl for fast point process simulation with time-varying intensities
• Super-Efficient Exact Hamiltonian Monte Carlo for the von Mises Distribution
• Perturbation theory for killed Markov processes and quasi-stationary distributions
• Gradient flows and randomised thresholding: sparse inversion and classification
• Hypocoercivity meets lifts
• Theoretical guarantees for lifted samplers
• Generalizing Parallel Replica Dynamics: Trajectory Fragments, Asynchronous Computing, and PDMPs