Misc,
The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data
(2016)arxiv:1607.03188.
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, 2016), a continuous time piecewise deterministic Markov
process. While traditional MCMC methods are reversible by construction the
Zig-Zag process offers a flexible non-reversible alternative. The dynamics of
the Zig-Zag process correspond to a constant velocity model, with the velocity
of the process switching at events from a point process. The rate of this point
process can be related to the invariant distribution of the process. If we wish
to target a given posterior distribution, then rates need to be set equal to
the gradient of the log of the posterior. Unlike traditional MCMC, 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. That is, if we replace the true gradient of the log
posterior with an unbiased estimator, obtained by sub-sampling, then 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 both heuristic arguments and empirical
observations show that Zig-Zag 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.
