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 multidimensional version of the Zig-Zag process of [Ann. Appl. Probab. 27 (2017) 846–882], 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 nonreversible 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, that is, 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 preprocessing step, essentially independent samples from the posterior distribution are obtained at a computational cost which does not depend on the size of the data.@en

The zigzag process is a piecewise deterministic Markov process which can be used in aMCMC framework to sample from a given target distribution. We prove the convergence of this process to its target under very weak assumptions, and establish a central limit theorem for empirical averages under stronger assumptions on the decay of the target measure.We use the classical "Meyn-Tweedie" approach (Markov Chains and Stochastic Stability (2009) Cambridge Univ. Press; Adv. in Appl. Probab. 25 (1993) 487-517). The main difficulty turns out to be the proof that the process can indeed reach all the points in the space, even if we consider the minimal switching rates.@en

Recently, there have been conceptually new developments in Monte Carlo methods through the introduction of new MCMC and sequential Monte Carlo (SMC) algorithms which are based on continuous-time, rather than discrete-time, Markov processes. This has led to some fundamentally new Monte Carlo algorithms which can be used to sample from, say, a posterior distribution. Interestingly, continuous-time algorithms seem particularly well suited to Bayesian analysis in big-data settings as they need only access a small sub-set of data points at each iteration, and yet are still guaranteed to target the true posterior distribution. Whilst continuous-time MCMC and SMC methods have been developed independently we show here that they are related by the fact that both involve simulating a piecewise deterministic Markov process. Furthermore, we show that the methods developed to date are just specific cases of a potentially much wider class of continuous-time Monte Carlo algorithms.We give an informal introduction to piecewise deterministic Markov processes, covering the aspects relevant to these new Monte Carlo algorithms, with a view to making the development of new continuoustime Monte Carlo more accessible. We focus on how and why sub-sampling ideas can be used with these algorithms, and aim to give insight into how these new algorithms can be implemented, and what are some of the issues that affect their efficiency.

@en

Piecewise Deterministic Monte Carlo algorithms enable simulation from a posterior distribution, whilst only needing to access a sub-sample of data at each iteration. We show how they can be implemented in settings where the parameters live on a restricted domain.

@en

In Turitsyn, Chertkov and Vucelja [Phys. D 240 (2011) 410-414] a nonreversible Markov Chain Monte Carlo (MCMC) method on an augmented state space was introduced, here referred to as Lifted Metropolis-Hastings (LMH). A scaling limit of the magnetization process in the Curie-Weiss model is derived for LMH, as well as for Metropolis-Hastings (MH). The required jump rate in the high (supercritical) temperature regime equals n^1/2 for LMH, which should be compared to n for MH. At the critical temperature, the required jump rate equals n^3/4 for LMH and n^3/2 for MH, in agreement with experimental results of Turitsyn, Chertkov and Vucelja (2011). The scaling limit of LMH turns out to be a nonreversible piecewise deterministic exponentially ergodic "zig-zag" Markov process.

@en