Accelerating pseudo-marginal Metropolis-Hastings by correlating auxiliary variables

Johan Dahlin, Fredrik Lindsten, Joel Kronander, Thomas B. SchönarXiv 2015 · DOI · arXiv

Abstract

Pseudo-marginal Metropolis-Hastings (pmMH) is a powerful method for Bayesian inference in models where the posterior distribution is analytically intractable or computationally costly to evaluate directly. It operates by introducing additional auxiliary variables into the model to form an extended target distribution, which can then be evaluated point-wise. In many cases, standard Metropolis-Hastings is applied to sample from the extended target, and the sought posterior is obtained by marginalization. However, in some implementations, this approach suffers from poor mixing as the auxiliary variables are sampled from an independent proposal. We propose a modification to the pmMH algorithm in which a Crank-Nicolson (CN) proposal is used instead. This introduces a positive correlation in the auxiliary variables. We investigate how to tune the CN proposal and its impact on the mixing of the resulting pmMH sampler. The conclusion is that the proposed modification can have a beneficial effect on both the mixing of the Markov chain and the computational cost for each iteration of the pmMH algorithm.

Introduction

Bayesian inference for complex models, such as non-linear state-space models, often requires sampling from a posterior distribution where the likelihood function is intractable. The pseudo-marginal Metropolis-Hastings (pmMH) algorithm provides a solution by replacing the exact likelihood with an unbiased estimate, typically generated via importance sampling or a particle filter.

To achieve this, the algorithm introduces auxiliary variables ($u$)—the underlying random noise used to generate the likelihood estimate. While theoretically sound, the standard pmMH implementation often suffers from "stickiness." If the algorithm generates a likelihood estimate that is significantly higher than the true value, the Markov chain tends to get stuck at that point for many iterations. This occurs because it is statistically unlikely for a subsequent independent set of random numbers to produce an equally high estimate. Traditionally, practitioners have mitigated this by increasing the number of particles ($N_u$), which significantly increases the computational burden.

Methodology: The Crank-Nicolson Proposal

This paper proposes a modification to the proposal distribution of the auxiliary variables. Rather than sampling $u$ independently at each step, we introduce a positive correlation between consecutive iterations using a Crank-Nicolson (CN) proposal.

The CN proposal is defined as: $$u' = \sqrt{1 - \sigma_u^2}u + \sigma_u \epsilon$$ where $\epsilon$ is fresh Gaussian noise and $\sigma_u$ is a step-size parameter. This approach offers several distinct advantages over standard random walk proposals:

  1. Dimension Independence: The CN proposal scales effectively even when the number of auxiliary variables is large, a common scenario in high-dimensional particle filtering.
  2. Stationarity: It naturally preserves the standard Gaussian distribution of the auxiliary variables, ensuring the "exact-approximation" property of pmMH remains intact.
  3. Smooth Likelihood Estimates: By making small, correlated changes to the random numbers, the resulting likelihood estimates change smoothly. This prevents the drastic jumps that lead to the chain becoming stuck.

Furthermore, the authors develop a theoretical framework using state-space discretization to determine the optimal tuning for the step-size $\sigma_u$.

Experimental Setup

The efficacy of the correlated pmMH algorithm was evaluated on two distinct setups:

  • Synthetic Gaussian IID Model: A controlled environment used to analyze the relationship between correlation and log-likelihood variance, validating the theoretical tuning results.
  • NASDAQ OMXS30 Index: Real-world financial data consisting of daily log-returns from 2011 to 2014. This was used to perform inference on a Stochastic Volatility (SV) model with leverage, a challenging non-linear state-space model where the likelihood must be estimated.

Key Insights and Results

The Power of Correlation

The central finding is that the independence of auxiliary variables—often assumed to be a requirement—is actually a primary cause of inefficiency. Introducing correlation does not break the validity of the sampler but significantly improves its mobility. In the Stochastic Volatility model, the correlated CN proposal improved mixing (measured by Integrated Autocorrelation Time, or IACT) by approximately 1.5x compared to the standard independent approach.

Optimal Acceptance Rates

In standard MCMC, practitioners often target an acceptance rate of approximately 23.4%. However, this research demonstrates that for the auxiliary variables in a correlated setup, the optimal acceptance rate is much higher—typically between 75% and 85%. This high acceptance rate ensures that the likelihood estimate moves frequently, preventing the "sticky" behavior associated with independent proposals.

Computational Efficiency

Because the correlated chain mixes more efficiently, the same level of posterior accuracy can be achieved using fewer particles ($N_u$). This reduction in the number of required particles translates directly into a lower computational cost per iteration, making the overall inference process significantly faster.

Conclusion and Future Work

The use of a Crank-Nicolson proposal to correlate auxiliary variables provides a robust and easily tunable improvement to the pseudo-marginal Metropolis-Hastings algorithm. A step size of $\sigma_u \approx 0.5$ was found to be a reliable starting point for various settings.

Future research directions include the development of adaptive tuning mechanisms to automatically determine $\sigma_u$ during the burn-in phase. Additionally, the authors suggest exploring the use of auxiliary variables to estimate the gradient and Hessian of the log-posterior, which could lead to more advanced "Manifold" versions of the correlated pmMH algorithm.

Summary updated

Abstract

Pseudo-marginal Metropolis-Hastings (pmMH) is a powerful method for Bayesian inference in models where the posterior distribution is analytical intractable or computationally costly to evaluate directly. It operates by introducing additional auxiliary variables into the model and form an extended target distribution, which then can be evaluated point-wise. In many cases, the standard Metropolis-Hastings is then applied to sample from the extended target and the sought posterior can be obtained by marginalisation. However, in some implementations this approach suffers from poor mixing as the auxiliary variables are sampled from an independent proposal. We propose a modification to the pmMH algorithm in which a Crank-Nicolson (CN) proposal is used instead. This results in that we introduce a positive correlation in the auxiliary variables. We investigate how to tune the CN proposal and its impact on the mixing of the resulting pmMH sampler. The conclusion is that the proposed modification can have a beneficial effect on both the mixing of the Markov chain and the computational cost for each iteration of the pmMH algorithm.
BibTeX
@misc{dahlin2015accelerating,
  author = {Johan Dahlin and Fredrik Lindsten and Joel Kronander and Thomas B. Schön},
  title = {{Accelerating pseudo-marginal Metropolis-Hastings by correlating auxiliary variables}},
  year = {2015},
  eprint = {1511.05483},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1511.05483},
}
Figure