Home > Research > Publications & Outputs > The Zig-Zag Process and Super-Efficient Samplin...

Electronic data

  • zigzagRev4

    Accepted author manuscript, 912 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License


Text available via DOI:

View graph of relations

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

Research output: Contribution to journalJournal articlepeer-review

<mark>Journal publication date</mark>13/02/2019
<mark>Journal</mark>Annals of Statistics
Issue number3
Number of pages33
Pages (from-to)1288-1320
Publication StatusPublished
<mark>Original language</mark>English


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 and Roberts (2015), 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 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.