A correlated pseudo-marginal approach to doubly intractable problems

Yu Yang, Matias Quiroz, Robert Kohn, Scott A. SissonarXiv 2022 · DOI · arXiv

TL;DR

This paper introduces a high-performance Bayesian inference method for "doubly intractable" models—complex systems where the likelihood function itself is impossible to calculate exactly. By combining a novel block-Poisson estimator with correlated MCMC updates, the authors achieve up to a 140x speedup over previous state-of-the-art methods while providing new theoretical guarantees for stability and accuracy.

What Problem Does This Paper Address?

In Bayesian statistics, we usually want to sample from a "posterior distribution." Standard Markov chain Monte Carlo (MCMC) methods are great at this because they don't require knowing the normalizing constant (the denominator) of the posterior.

However, some models are doubly intractable. This happens when the likelihood function—the core component of the model—contains its own normalizing function $Z(\theta)$ that depends on the parameters and cannot be computed. This is common in social network analysis (Exponential Random Graph Models), ecology, and physics (the Ising model). Because $Z(\theta)$ doesn't cancel out in the MCMC acceptance ratio, standard algorithms get stuck.

Existing solutions like the "Exchange Algorithm" require "perfect sampling" (generating exact data from the model), which is often computationally prohibitive. Other "pseudo-marginal" methods use unbiased estimators like "Russian Roulette" (RR), but these are notoriously difficult to tune, hard to parallelize, and can produce unstable results if the estimator's sign fluctuates too much.

Methods

The authors propose a Signed Block-Poisson (BP) Pseudo-Marginal Metropolis-Hastings algorithm. Here are the three pillars of their approach:

  1. The Block-Poisson Estimator: Instead of the complex, nested structure of Russian Roulette estimators, the BP estimator uses a simpler product of "blocks." This estimator provides an unbiased estimate of the reciprocal of the normalizing function.
  2. Correlation: One of the biggest innovations is the use of correlated pseudo-marginal updates. By "blocking" the random numbers used in the estimator and only updating a portion of them at each MCMC step, the authors ensure that the estimated likelihoods at the current and proposed parameter values are highly correlated. This dramatically reduces the variance of the MCMC acceptance ratio, leading to much better "mixing" (the chain moves through the parameter space more efficiently).
  3. The "Signed" Approach: Because unbiased estimators of $1/Z(\theta)$ can sometimes be negative, the algorithm targets the absolute value of the posterior and then uses importance sampling to reweight the results. To prevent the "pathological case" where the importance sampling denominator hits zero, the authors derive a new finite-sample concentration inequality (Theorem 1) to guarantee stability.

Datasets

The authors evaluated their method on both simulated and real-world benchmarks:

  • The Ising Model: The classic "gold standard" for doubly intractable problems, used to model spatial data on a grid.
  • The Kent Distribution: A complex distribution for directional data on a sphere (where the normalizing function is an infinite sum).
  • Real-World Spherical Data: They applied the Kent model to four datasets:
  • Palaeomagnetic: Pole positions from Tasmania.
  • Magnetic: Remanence measurements from Mesozoic Dolerite.
  • Sandstone: Natural remanent magnetization in rocks from Wales.
  • Stone: Orientations of tabular stones on a slope in Scotland.

Key Insights and Ideas

  • Parallelization is the Secret Sauce: The BP estimator’s independent product structure is "SIMD-friendly" (Single Instruction, Multiple Data). Unlike Russian Roulette, which is sequential and nested, the BP estimator can be easily vectorised and parallelized on modern CPUs and GPUs.
  • Correlation Beats Raw Accuracy: Even if an individual estimate of the likelihood is noisy, if that noise is correlated between MCMC steps, the algorithm performs much better. This is a counter-intuitive but powerful principle in modern MCMC.
  • Tuning Guidelines: The authors provide the first clear heuristic guidelines for tuning the hyperparameters of these types of estimators, based on the variance of the log-likelihood. This moves the method from a theoretical curiosity to a practical tool.

Key Results

  • Massive Efficiency Gains: In the Ising model benchmark, the BP approach was 14x more efficient (in terms of Effective Sample Size per second) than the standard Russian Roulette method.
  • Scalability: For the Kent distribution with 1,000 observations, the BP method outperformed Russian Roulette variants by factors of 70x to 140x.
  • Robustness: While previous methods (like RR-aux) frequently "got stuck" or failed to converge on difficult parameters (like the Ising model at $\theta = 0.43$), the BP method remained stable and provided accurate posterior estimates.

Limitations and Future Work

  • Computational Overhead: While much faster than previous "exact" methods, the approach is still significantly more expensive than "approximate" methods like Variational Bayes. It is best suited for cases where high accuracy is non-negotiable.
  • Normality Assumption: The current tuning guidelines assume that the estimator of the normalizing function follows a normal distribution. The authors note that this might not hold for all models and suggest exploring non-normal cases in future research.
  • Tighter Theoretical Bounds: The authors aim to refine their concentration inequalities using more advanced mathematical tools (like iterated Poincaré inequalities) to provide even stricter guarantees for importance sampling stability.

Summary updated

Abstract

Doubly intractable models are encountered in a number of fields, e.g. social networks, ecology and epidemiology. Inference for such models requires the evaluation of a likelihood function, whose normalising factor depends on the model parameters and is assumed to be computationally intractable. The normalising constant of the posterior distribution and the additional normalising factor of the likelihood function result in a so-called doubly intractable posterior, for which it is difficult to directly apply Markov chain Monte Carlo methods. We propose a signed pseudo-marginal Metropolis-Hastings algorithm with an unbiased block-Poisson estimator to sample from the posterior distribution of doubly intractable models. As the estimator can be negative, the algorithm targets the absolute value of the estimated posterior and uses an importance sampling estimator to ensure simulation-consistent estimates of the posterior mean of a function of the parameters. The importance sampling estimator can perform poorly when its denominator is close to zero. We derive a finite-sample concentration inequality that ensures, with high probability, that this pathological case does not occur. Our estimator for doubly intractable problems has three advantages over existing estimators. First, the estimator is well-suited for efficient parallelisation and vectorisation. Second, its structure is ideal for correlated pseudo-marginal methods, which are well known to dramatically increase sampling efficiency. Third, the estimator enables the derivation of heuristic guidelines for tuning its hyperparameters under simplifying assumptions. We demonstrate the superior performance of our method in the standard benchmark example that models correlated spatial data using the Ising model, as well as the Kent distribution model for spherical data.
BibTeX
@misc{yang2022correlated,
  author = {Yu Yang and Matias Quiroz and Robert Kohn and Scott A. Sisson},
  title = {{A correlated pseudo-marginal approach to doubly intractable problems}},
  year = {2022},
  eprint = {2210.02734},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.02734},
}
Figure