Asymptotically Exact MCMC Algorithms via Local Approximations of Computationally Intensive Models

Patrick R. Conrad, Youssef Marzouk, Natesh S. Pillai, Aaron SmitharXiv 2014 · arXiv

Abstract

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 Metropolis-Hastings 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 exact posterior distribution of interest. Numerical experiments demonstrate multiple order-of-magnitude reductions in the number of forward model evaluations used in representative ODE and PDE inference problems, with both synthetic and real data.

Introduction

In Bayesian inference, characterizing a posterior distribution—the updated belief about model parameters after observing data—is a fundamental task. This is typically achieved using Markov chain Monte Carlo (MCMC) methods. However, a significant computational bottleneck arises when the likelihood function depends on an expensive "forward model," such as complex systems of differential equations (ODEs or PDEs) common in geophysics, biology, and engineering. In these scenarios, a single model evaluation can take minutes, making standard MCMC chains that require tens of thousands of steps practically infeasible.

While researchers often turn to "surrogates" or emulators to replace these expensive evaluations, traditional approaches usually introduce a permanent bias (global surrogates) or fail to provide significant speedups (delayed-acceptance methods). This paper introduces a framework that uses local surrogates to achieve both speed and asymptotic exactness.

The Local Surrogate Framework

The proposed method avoids building a massive global emulator for the entire parameter space. Instead, it constructs and refines cheap, local models—such as linear, quadratic, or Gaussian Process regressors—near the current and proposed states of the MCMC chain.

Comparison of prior-based sparse grid samples (a) and the proposed posterior-adapted samples (b). The adapted approach focuses computational effort where the posterior probability is high.

Key Components

  • Refinement Triggers: The algorithm intelligently decides when to run the expensive "true" model. It uses a combination of a random probability (to ensure infinite refinement in the limit) and a cross-validation error indicator. This indicator measures the potential impact of the approximation error on the Metropolis-Hastings acceptance probability ($\alpha$), focusing refinement where it matters most for the chain's movement.
  • Sequential Experimental Design: When the surrogate requires more data, the algorithm employs a space-filling heuristic to select new points near the current state. This ensures the local model remains stable and "$\lambda$-poised."
  • Asymptotic Exactness: A core contribution is the rigorous proof that as the chain explores, the local approximations become increasingly accurate in high-probability regions. Consequently, the chain converges to the true posterior distribution, effectively eliminating the bias associated with traditional surrogate methods.

Experimental Evaluation

The framework was tested on three challenging problems:

  1. Genetic Toggle Switch: An ODE model of a synthetic gene circuit in E. coli using real experimental data, demonstrating robustness to biological noise.
  2. FitzHugh-Nagumo ODE: A synthetic dataset for neuron activation dynamics, used to compare linear, quadratic, and GP surrogate types.
  3. Elliptic PDE Inverse Problem: A high-dimensional synthetic problem involving the inference of a diffusivity field, representing a highly computationally demanding scenario.

Key Insights and Results

The primary insight of this work is that while a model may be globally complex, it often exhibits significant local regularity. By exploiting this local smoothness, the algorithm can decouple the number of expensive model evaluations from the total length of the MCMC chain.

Performance gains were substantial across all benchmarks:

  • PDE Problem: The "indirect quadratic" approximation achieved a 400-fold reduction in computational effort, requiring only 600 true model evaluations compared to 240,000 for standard MCMC.
  • FitzHugh-Nagumo: Surrogates reduced model evaluations by over two orders of magnitude with no loss in posterior accuracy.
  • Robustness: Theoretical predictions were confirmed; even with decaying refinement rates, the chains remained ergodic and converged to the correct target distributions.

Limitations and Future Work

While highly effective in low-to-moderate dimensions (up to 6 parameters in this study), local polynomial regression faces challenges as dimensionality increases. Additionally, the computational overhead of constructing local surrogates (e.g., solving least-squares problems) may become significant in very high-dimensional spaces.

Future research directions include integrating this framework with gradient-based methods like Hamiltonian Monte Carlo (HMC) by using surrogates to provide cheap gradients. The authors also suggest "shared" surrogates, where multiple parallel MCMC chains contribute to a common pool of model evaluations to further enhance efficiency.

Summary updated

Abstract

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 Metropolis-Hastings 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 order-of-magnitude reductions in the number of forward model evaluations used in representative ODE and PDE inference problems, with both synthetic and real data.
BibTeX
@misc{conrad2014asymptotically,
  author = {Patrick R. Conrad and Youssef Marzouk and Natesh S. Pillai and Aaron Smith},
  title = {{Asymptotically Exact MCMC Algorithms via Local Approximations of Computationally Intensive Models}},
  year = {2014},
  eprint = {1402.1694},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.1694},
}

Loading related content...

Figure