Adaptive, Delayed-Acceptance MCMC for Targets With Expensive Likelihoods

ABSTRACT

When conducting Bayesian inference, delayed-acceptance (DA) Metropolis–Hastings (MH) algorithms and DA pseudo-marginal MH algorithms can be applied when it is computationally expensive to calculate the true posterior or an unbiased estimate thereof, but a computationally cheap approximation is available. A first accept-reject stage is applied, with the cheap approximation substituted for the true posterior in the MH acceptance ratio. Only for those proposals that pass through the first stage is the computationally expensive true posterior (or unbiased estimate thereof) evaluated, with a second accept-reject stage ensuring that detailed balance is satisfied with respect to the intended true posterior. In some scenarios, there is no obvious computationally cheap approximation. A weighted average of previous evaluations of the computationally expensive posterior provides a generic approximation to the posterior. If only the k-nearest neighbors have nonzero weights then evaluation of the approximate posterior can be made computationally cheap provided that the points at which the posterior has been evaluated are stored in a multi-dimensional binary tree, known as a KD-tree. The contents of the KD-tree are potentially updated after every computationally intensive evaluation. The resulting adaptive, delayed-acceptance [pseudo-marginal] Metropolis–Hastings algorithm is justified both theoretically and empirically. Guidance on tuning parameters is provided and the methodology is applied to a discretely observed Markov jump process characterizing predator–prey interactions and an ODE system describing the dynamics of an autoregulatory gene network. Supplementary material for this article is available online.

KEYWORDS:

• Adaptive MCMC
• Delayed-acceptance
• KD-tree
• Pseudo-marginal MCMC
• Surrogate

Supplementary Materials

Computer Code: Cprograms.zip	Contains a generic C implementation of KD-tree storage and look-up as well as code for implementing the inference algorithms described in the article.
Appendices: supplementary.pdf	Contains appendices describing standard operations on a KD-tree, proofs of Propositions 1 and 2, the daPsMMH algorithm, proofs of Theorems 1, 2, and 3, the LNA and the construction of the corresponding marginal likelihood and additional plots from the simulation study.

Acknowledgments

The authors thank Krysztof Latuszynski for a very helpful discussion with regard to Theorem 3, and the associate editor and referee for useful suggestions that have improved the clarity of the article.