  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.
