  The complexity of the Metropolis-Hastings (MH) algorithm arises from the
requirement of a likelihood evaluation for the full data set in each iteration.
Payne and Mallick (2015) propose to speed up the algorithm by a delayed
acceptance approach where the acceptance decision proceeds in two stages. In
the first stage, an estimate of the likelihood based on a random subsample
determines if it is likely that the draw will be accepted and, if so, the
second stage uses the full data likelihood to decide upon final acceptance.
Evaluating the full data likelihood is thus avoided for draws that are unlikely
to be accepted. We propose a more precise likelihood estimator which
incorporates auxiliary information about the full data likelihood while only
operating on a sparse set of the data. We prove that the resulting delayed
acceptance MH is more efficient compared to that of Payne and Mallick (2015).
The caveat of this approach is that the full data set needs to be evaluated in
the second stage. We therefore propose to substitute this evaluation by an
estimate and construct a state-dependent approximation thereof to use in the
first stage. This results in an algorithm that (i) can use a smaller subsample
m by leveraging on recent advances in Pseudo-Marginal MH (PMMH) and (ii) is
provably within $O(m^{-2})$ of the true posterior.
