This is joint work with Paul Jenkins, Murray Pollock and Gareth Roberts
Abstract
Blocking is a generic modification technique that may be applied to any diffusion bridge-sampling algorithm so as to reduce its overall computational cost. The method is widely used within the context of Bayesian inference for diffusion processes, where imputation of unobserved segments of diffusion paths constitutes an essential algorithmic step. Briefly, a path—instead of being sampled in full—is first split into overlapping segments, and then, the original algorithm is cast as a Gibbs sampler: segments are cycled through and updated in turn. This means that diffusion bridges of shorter duration need to be sampled—which for many algorithms means lower computational cost of each individual update—however, a new dependence structure on the past draws is introduced, which, in turn, necessitates a greater total number of Gibbs sweeps. These two opposite effects give rise to a non-trivial trade-off of costs and, to the best of our knowledge, to this date there have been no accounts of any formal attempts at quantifying this cost balance. In this article we show that such an analysis can be conducted under a simplifying assumption of the diffusion law being given by the Brownian motion or the Ornstein–Uhlenbeck process, and we demonstrate that asymptotically the computational cost of rejection sampler on a path space modified by blocking scales at most as $\mathcal{O}(T^{3+\chi})$ for any $\chi>0$, with $T$ denoting the duration of the bridges—a reduction from an exponential scaling of the unmodified algorithm. The numerical experiments suggest applicability of our results beyond the class of linear diffusions.
Additional info
The paper will appear on arXiv shortly.