Ergodicity and excess switching rate of the Zig-Zag process

Markov Chain Monte Carlo (MCMC) has emerged as the main computational powerhouse of Bayesian inference over the last few decades. There has been - fuelled by the constant evolution of computational standards, and necessitated by the advent of internet and globalization, which has lead to a massive influx of data and increased complexity of Bayesian models - a tremendous growth, both methodological and theoretical, in MCMC literature focused on constructing efficient algorithms to deal with problems of intractability, high dimensionality and big data. Traditional MCMC algorithms focus on constructing a reversible, discrete-time Markov chain admitting a desired invariant measure. However, more recently, continuous-time, non-reversible methods have aroused much interest in the MCMC community as efficient and scalable alternative to standard Metropolis-Hastings algorithms (Hastings, 1970). In particular, the Zig-Zag process (Bierkens et al., 2019) offers much promise for the construction of more efficient samplers. This is partly due to its non-reversible nature and the possibility of being simulated exactly unlike other diffusion based sampling methods. And partly because of its ability to reduce computational burden in big data settings by admitting a sub-sampling strategy and still target the desired invariant measure making it scalable.

Under some situations, sub-sampling with Zig-Zag, together with a control variate idea, has been shown empirically to achieve super-efficiency: generating essentially independent samples at a computational cost that does not increase with the data-size. The caveat, however, is that sub-sampling induces more diffusivity in the process by introducing an excess switching rate. This causes the process to flip its velocity more frequently, slowing down its mixing. For example, a canonical Zig-Zag started out in tails comes straight to the centre before its first flip. However, with an excess switching rate, it would flip more than once before reaching the centre and consequently will take more time to explore the target measure. As a result, the algorithm needs to be run for a longer time, even though at a reduced cost per iteration. Thus the overall efficiency, as measured heuristically by the total of algorithmic efficiency and its cost of implementation might reduce. This challenges the promise of Zig-Zag as
a scalable alternative to standard MCMC methods.

The aim of this project is to study and quantify the effect of sub-sampling on the speed of the process. This effect would vary for different target distributions. And by doing so, comment on its usefulness for Bayesian computation. The current direction is to investigate the behaviour of Zig-Zag for large datasets and to look at the limiting process as the data-size goes to infinity. This problem, to our knowledge, has not been studied theoretically yet in the literature. We believe it to be an interesting problem that will have lots of practical implications in Bayesian community. For situations where the slowing down of the process due to sub-sampling is found to be insignificant, Zig-Zag can provide with a highly scalable and a super-efficient sampling algorithm. The project is motivated by its possible implications in Bayesian computation and will be carried out using tools of applied probability. Overall, it falls within the remit of Research council which covers engineering and physical sciences.

References:
Bierkens, J., Fearnhead, P., and Roberts, G. O. (2019). The zig-zag process and super-efficient sampling for Bayesian analysis of big data. The Annals of Statistics, 47(3):1288-1320.

Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97-109.