
We construct a new framework for accelerating Markov chain Monte Carlo in
posterior sampling problems where standard methods are limited by the
computational cost of the likelihood, or of numerical models embedded therein.
Our approach introduces local approximations of these models into the
MetropolisHastings kernel, borrowing ideas from deterministic approximation
theory, optimization, and experimental design. Previous efforts at integrating
approximate models into inference typically sacrifice either the sampler's
exactness or efficiency; our work seeks to address these limitations by
exploiting useful convergence characteristics of local approximations. We prove
the ergodicity of our approximate Markov chain, showing that it samples
asymptotically from the \emph{exact} posterior distribution of interest. We
describe variations of the algorithm that employ either local polynomial
approximations or local Gaussian process regressors. Our theoretical results
reinforce the key observation underlying this paper: when the likelihood has
some \emph{local} regularity, the number of model evaluations per MCMC step can
be greatly reduced without biasing the Monte Carlo average. Numerical
experiments demonstrate multiple orderofmagnitude reductions in the number of
forward model evaluations used in representative ODE and PDE inference
problems, with both synthetic and real data.

In this paper, we present a formal quantification of epistemic uncertainty
induced by numerical solutions of ordinary and partial differential equation
models. Numerical solutions of differential equations contain inherent
uncertainties due to the finite dimensional approximation of an unknown and
implicitly defined function. When statistically analysing models based on
differential equations describing physical, or other naturally occurring,
phenomena, it is therefore important to explicitly account for the uncertainty
introduced by the numerical method. This enables objective determination of its
importance relative to other uncertainties, such as those caused by data
contaminated with noise or model error induced by missing physical or
inadequate descriptors. To this end we show that a wide variety of existing
solvers can be randomised, inducing a probability measure over the solutions of
such differential equations. These measures exhibit contraction to a Dirac
measure around the true unknown solution, where the rates of convergence are
consistent with the underlying deterministic numerical method. Ordinary
differential equations and elliptic partial differential equations are used to
illustrate the approach to quantifying uncertainty in both the statistical
analysis of the forward and inverse problems.

Polynomial approximations of computationally intensive models are central to
uncertainty quantification. This paper describes an adaptive method for
nonintrusive pseudospectral approximation, based on Smolyak's algorithm with
generalized sparse grids. We rigorously analyze and extend the nonadaptive
method proposed in [6], and compare it to a common alternative approach for
using sparse grids to construct polynomial approximations, direct quadrature.
Analysis of direct quadrature shows that O(1) errors are an intrinsic property
of some configurations of the method, as a consequence of internal aliasing. We
provide precise conditions, based on the chosen polynomial basis and quadrature
rules, under which this aliasing error occurs. We then establish theoretical
results on the accuracy of Smolyak pseudospectral approximation, and show that
the Smolyak approximation avoids internal aliasing and makes far more effective
use of sparse function evaluations. These results are applicable to broad
choices of quadrature rule and generalized sparse grids. Exploiting this
flexibility, we introduce a greedy heuristic for adaptive refinement of the
pseudospectral approximation. We numerically demonstrate convergence of the
algorithm on the Genz test functions, and illustrate the accuracy and
efficiency of the adaptive approach on a realistic chemical kinetics problem.