On an adaptive preconditioned Crank-Nicolson MCMC algorithm for infinite dimensional Bayesian inference

Zixi Hu, Zhewei Yao, Jinglai LiJournal of Computational Physics 2017 · DOI

TL;DR

This paper introduces an adaptive Markov Chain Monte Carlo (MCMC) algorithm, called adaptive preconditioned Crank-Nicolson (ApCN), designed to efficiently sample from posterior distributions in infinite-dimensional Bayesian inverse problems. By adaptively adjusting the proposal distribution based on sampling history, the ApCN algorithm significantly improves simulation efficiency compared to existing methods, particularly for complex problems where derivative information is unavailable.

What Problem Does This Paper Address?

Many scientific and engineering problems involve inferring unknown functions from data, which are often modeled as infinite-dimensional Bayesian inverse problems. Traditional MCMC methods, when applied to these problems after discretization, become prohibitively slow as the dimension of the problem increases (dimension-dependent). While preconditioned Crank-Nicolson (pCN) methods offer a dimension-independent alternative by working directly in function spaces, their sampling efficiency can still be a bottleneck. This paper addresses the challenge of improving the efficiency of pCN methods, especially in scenarios where the likelihood function is a black box and derivative information is hard to obtain.

Methods

The core of this work is the development of an adaptive preconditioned Crank-Nicolson (ApCN) algorithm. The standard pCN algorithm, derived from a stochastic partial differential equation (SPDE), provides a dimension-independent proposal. The ApCN algorithm enhances this by adaptively adjusting the covariance operator of the pCN proposal based on the history of samples drawn from the target distribution.

Key methodological aspects include:

  • Adaptive Covariance Operator: The algorithm learns and updates a specific component of the proposal's covariance operator. This adaptation is guided by the observed sampling history, aiming to make the proposal better match the posterior distribution.
  • Finite-Dimensional Reduction: To make the adaptation computationally feasible, the algorithm focuses on adapting only the first $J$ eigenvalues of the covariance operator, while the remaining eigenvalues are kept fixed. This is motivated by the assumption that data typically informs only a finite number of modes (represented by the first few eigenvalues) of the posterior.
  • Common Eigenfunctions: The adaptive operator is designed to share eigenfunctions with the prior covariance operator, ensuring it commutes with the prior and maintaining desirable properties.
  • Ergodicity Analysis: The paper provides theoretical guarantees, showing that the proposed ApCN algorithm satisfies important ergodicity conditions, ensuring convergence to the true posterior distribution under mild assumptions. A minor modification to the likelihood function is introduced to simplify the proof of the Diminishing Adaptation (DA) condition.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated from known "true" coefficients for two inverse problems:

  1. Ordinary Differential Equation (ODE) Example: A forward model governed by an ODE is used to generate data. The true coefficient is drawn from a Matérn covariance prior.
  2. Heat Conduction Equation Example: A one-dimensional heat conduction equation with Robin boundary conditions is used to generate data. The true Robin coefficient is drawn from a prior distribution.

These examples serve as benchmarks to evaluate the performance of the proposed ApCN algorithm against the standard pCN algorithm.

Key Insights and Ideas

  • Adaptive Proposals for Infinite Dimensions: The paper demonstrates that adaptive MCMC techniques, commonly used in finite dimensions, can be effectively extended to infinite-dimensional Bayesian inference problems, leading to significant efficiency gains.
  • Data Informs Finite Modes: A crucial insight is that observational data typically only provides information about a finite number of dominant modes (eigenfunctions) of the posterior distribution. This justifies the finite-dimensional reduction approach for adaptation, where only the first $J$ eigenvalues are adapted.
  • Balancing Adaptation and Stability: The algorithm balances adapting the proposal to better match the posterior with maintaining the dimension-independent properties of the pCN method. The adaptation is designed to be stable and ensure convergence.
  • Black-Box Compatibility: The ApCN algorithm is particularly valuable because it does not require explicit derivative information of the likelihood function, making it suitable for "black-box" models where only function evaluations are possible.

Key Results

The paper presents numerical results from two inverse problems that demonstrate the effectiveness of the ApCN algorithm:

  • Improved Sampling Efficiency: In both the ODE and heat conduction examples, the ApCN algorithm consistently shows significantly better sampling efficiency than the standard pCN algorithm. This is evidenced by:
  • Lower Autocorrelation Functions (ACF): The ACF of samples generated by ApCN decays much faster, indicating that consecutive samples are less correlated.
  • Higher Effective Sample Size (ESS): The ESS, a measure of independent samples, is substantially higher for ApCN across grid points.
  • Convergence of Adapted Parameters: The plots of the adapted eigenvalues over iterations show that they converge to stable values, supporting the idea that the adaptation process stabilizes.
  • Acceptance Probability: While the standard pCN can suffer from low acceptance probabilities with small step sizes, the ApCN algorithm, even with a fixed step size, achieves a more favorable acceptance rate due to its adaptive nature.

Limitations and Future Work

  • Step-size Restriction: A major limitation acknowledged is that the step-size $\beta$ in the pCN algorithm (and thus ApCN) is ultimately restricted to be less than 1 to ensure the acceptance probability is well-defined. In many practical problems, larger step-sizes might be desirable for better exploration, leading to potentially high acceptance probabilities with the current ApCN formulation.
  • Future Work: The authors plan to address this limitation by making improvements to the present algorithm in future work, likely focusing on strategies to handle larger step-sizes or alternative adaptation mechanisms. They also suggest that the algorithm's simplicity and black-box compatibility make it suitable for a wide range of practical problems.

Summary updated

BibTeX
@article{hu2017adaptive,
  author = {Zixi Hu and Zhewei Yao and Jinglai Li},
  title = {{On an adaptive preconditioned Crank-Nicolson MCMC algorithm for infinite dimensional Bayesian inference}},
  journal = {Journal of Computational Physics},
  year = {2017},
  doi = {10.1016/j.jcp.2016.11.024},
}
Figure