Source-linked AI summary
The pseudo-marginal approach for efficient Monte Carlo computations
Christophe Andrieu, Gareth O. Roberts
TL;DR
The paper addresses MCMC settings where the marginal density π(θ) is difficult to evaluate, while auxiliary-variable methods offer easier implementation. It develops pseudo-marginal algorithms whose joint-chain construction can preserve the exact marginal distribution, proves convergence properties for generalizations, and contrasts them with the inexact MCWM approximation.
Problem
Marginal densities or expectations can be analytically intractable or too complex to evaluate, despite the potential efficiency of sampling directly from π(θ).
Method
The paper replaces intractable marginal Metropolis–Hastings quantities with importance-sampling estimates and develops GIMH-style auxiliary-variable updates targeting a joint density.
Results
GIMH and its exact generalizations converge under stated irreducibility and aperiodicity conditions, while their finite-horizon convergence can resemble the marginal algorithm when N is sufficiently large.
Takeaways & Limitations
Pseudo-marginal constructions can combine auxiliary-scheme implementability with samples from the exact marginal π(θ), including applications to reversible-jump MCMC and model selection.
Takeaways & Limitations
The convergence rate of the exact pseudo-marginal chain cannot generally match that of the marginal chain, even when N increases.
Abstract
from arXiv · showhide
We introduce a powerful and flexible MCMC algorithm for stochastic simulation. The method builds on a pseudo-marginal method originally introduced in [Genetics 164 (2003) 1139--1160], showing how algorithms which are approximations to an idealized marginal algorithm, can share the same marginal stationary distribution as the idealized method. Theoretical results are given describing the convergence properties of the proposed method, and simple numerical examples are given to illustrate the promising empirical characteristics of the technique. Interesting comparisons with a more obvious, but inexact, Monte Carlo approximation to the marginal algorithm, are also given.
1. Introduction.
The paper develops pseudo-marginal MCMC for cases where the marginal density π(θ) is difficult to evaluate, using auxiliary simulation while preserving exact marginal sampling for suitable algorithms. It contrasts exact GIMH-style methods with MCWM, an easier approximation whose stationary distribution is generally incorrect, and establishes convergence properties for broad generalizations.
- Motivation: Auxiliary variables can make MCMC implementation easier when the marginal density π(θ) is analytically intractable or numerically difficult to evaluate.The framework includes Bayesian parameters with missing data or latent variables, including hidden Markov and mixture models.
- Pseudo-marginal construction: The paper approximates the marginal Metropolis–Hastings acceptance ratio with importance-sampling estimates based on N auxiliary draws.These estimates are plugged into the marginal acceptance ratio using an importance density qθ(z).
- MCWM and GIMH: MCWM refreshes auxiliary variables independently at every iteration, but its invariant density is typically not π(θ), so it does not generate exact marginal samples.When ergodic, its asymptotic distribution should approximate π(θ) more closely as N increases.
- MCWM and GIMH: GIMH recycles the auxiliary variables rather than drawing fresh ones, making the joint pair {θi,Zi} a Markov chain even though {θi} alone is not.Under irreducibility and aperiodicity, its limiting θ-marginal is π(θ).
- Theory and extensions: The paper generalizes GIMH to richer transitions, including possible local-adaptation schemes, and studies their finite-horizon, geometric, uniform, and MCWM-related convergence properties.The stated results include finite-horizon similarity to the marginal algorithm for sufficiently large N and uniform-ergodicity inheritance under stronger conditions.
- Applications: Applications include reversible-jump MCMC, model selection, and Bayesian variable selection, with empirical evidence suggesting considerable promise.The introduction identifies reversible-jump algorithms as a target for efficient pseudo-marginal construction.
2. Set up and notation.
The paper augments θ with auxiliary variables Z to construct pseudo-marginal algorithms when the marginal distribution π(dθ) is difficult to use directly. It defines proposal, weighting, target, and transition notation for exact and approximate variants.
- Z denotes an N-component auxiliary vector, with Z−k removing coordinate k and related notation for subvectors.
- The framework specifies measurable spaces, a joint target π(dθ,dz), its marginal π(dθ), conditional πθ(dz), and proposal distributions QNθ(dZ).
- Importance weights define γN(θ), while the pseudo-marginal construction uses the extended target ˜πN(dθ,dZ) and associated conditional distributions.
- If Z|θ follows QNθ, the estimator π(θ)γN(θ) is unbiased, so π(dθ) is the marginal of ˜πN(dθ,dZ).
- The framework includes classical importance sampling, sequential sampling, and Gibbs-sampler-type choices for generating auxiliary variables.
- MCWM refreshes auxiliary variables independently each iteration, whereas GIMH uses an MH transition on the extended space targeting ˜πN(dθ,dZ).
- The exact pseudo-marginal chain and a comparison chain are constructed on a common extended space to analyze their transition probabilities.
3. A simple convergence result for exact algorithms.
The exact pseudo-marginal chain inherits ergodicity under irreducibility, aperiodicity, and a positivity condition on its stay probabilities. The proof compares accessible sets with those of an embedded ideal chain.
- For a ψ-irreducible and aperiodic marginal chain with invariant distribution π, convergence in total variation motivates the exact-chain result.
- Theorem 1 states that, under (A1) and positive stay probabilities, the exact pseudo-marginal chain is also ψ-irreducible and aperiodic.
- The proof embeds the ideal chain on the extended space and shows that every accessible set of the comparison chain is also accessible to the exact chain.
4. Performance of the pseudo-marginal approach.
The performance analysis controls the discrepancy between an ideal extended-space chain and the exact pseudo-marginal chain. Under assumptions (A1)–(A3), sufficiently large N makes the approximation loss arbitrarily small over finite horizons.
- Assumptions and intermediate bounds: Under (A1) and (A3), sets where the log-estimator error λN(θ) is small become increasingly dominant as N grows.
- Assumptions and intermediate bounds: Assumption (A3) is central because it controls the total variation distance between the relevant extended distributions and supports the subsequent lemmas.
- Kernel comparison: The transition-kernel comparison bounds the difference between the ideal and exact chains for bounded test functions on suitable states.
- Kernel comparison: The inequality |1 ∧ exp(x) − 1 ∧ exp(y)| ≤ 1 ∧ |x − y| helps convert log-ratio discrepancies into acceptance-probability bounds.
- Finite-horizon performance: Proposition 5 establishes that the transition probabilities approach one another uniformly over bounded test functions when N is sufficiently large.
- Finite-horizon performance: Theorem 6 gives a bound on efficiency loss relative to the ideal chain that can be made arbitrarily small by increasing N.
- Finite-horizon performance: The proof decomposes error into ideal-chain convergence and approximation bias, then controls the bias through repeated kernel comparisons and Proposition 5.
5. Uniform and geometric ergodicity of exact algorithms.
The section establishes how importance-weight behavior governs ergodicity of exact pseudo-marginal algorithms. Unbounded weights can prevent geometric ergodicity, while bounded weights combined with a marginal minorization condition yield uniform ergodicity.
- A good importance sampling distribution is critical to the ergodicity properties of the exact pseudo-marginal algorithm.The section explicitly emphasizes the importance of choosing QN appropriately.
- A marginal minorization condition is inherited by the exact pseudo-marginal chain when γN* < +∞, implying uniform ergodicity.The marginal condition requires Kn0(θ,A) ≥ ε ν(A) for suitable n0, ε, and ν.
- If π(UN) > 0, then the exact pseudo-marginal chain cannot be geometrically ergodic.UN contains θ values for which the importance-weight behavior is unbounded in the stated sense.
- The exact pseudo-marginal chain need not achieve the marginal chain’s convergence rate, even when the importance weights are bounded.This is stated as a general limitation of the second theorem’s conclusion.
6. Epilogue: MCWM.
The epilogue analyzes MCWM, whose independently refreshed auxiliary variables make its analysis simpler than that of GIMH. Under uniform ergodicity and a uniform weak law for λN(θ), the paper characterizes its invariant distribution and convergence rate.
- MCWM is easier to analyze than GIMH generalizations because its auxiliary variables are independently refreshed at each iteration.The analysis therefore relies mainly on more classical arguments.
- The noisy MCWM kernel may lack an obvious invariant distribution because it is not itself a Metropolis–Hastings update.This contrasts with the exact pseudo-marginal chain, whose invariant distribution and marginal are known.
- The paper characterizes MCWM’s invariant distribution when it exists and studies its convergence rate when the marginal chain is uniformly ergodic.The rate analysis also assumes a simple uniform weak law of large numbers for λN(θ).
- For sufficiently large N, MCWM admits convergence bounds with rate parameter ˜ρ satisfying ˜ρ ∈ (ρ, ρ(1 + ǫ)] ⊂ (ρ,1).The bound holds under the assumptions of Theorem 9 for all N above a threshold depending on ε and ρ.
7. Examples: Reversible jumps.
The paper applies the pseudo-marginal approach to reversible-jump MCMC, first using a transdimensional toy distribution and then Bayesian variable selection in generalized linear models. Increasing the number of importance samples improves model-probability estimates and reliability relative to the standard N = 1 scheme.
- 7.1. Toy example: The toy target is transdimensional, defined on {1} × R ∪ {2} × R2, with exact marginal probabilities available for comparison.The application uses reversible-jump updates to sample across models.
- 7.1. Toy example: N = 1, 5, and 10 produced empirical expected acceptance probabilities of 0.0121, 0.5206, and 0.5056, respectively.The runs used 450,000, 90,000, and 45,000 iterations, giving comparable computational effort.
- 7.2. Application to variable selection in GLMs.: In Bayesian variable selection, marginal posterior model probabilities are intractable, so models are indexed by inclusion indicators for covariates and explored with reversible-jump MCMC.The algorithm uses birth/death updates for the marginal model and estimates its probabilities with importance sampling.
- 7.2. Application to variable selection in GLMs.: The N = 1 and N = 5 model-probability estimates differed substantially from N = 50, 100, and 200, whose results agreed with one another.The larger-N estimates after 20,000, 10,000, and 5,000 iterations were reported as more reliable than N = 1 after 1,000,000 iterations.
- 7.2. Application to variable selection in GLMs.: The trace of auxiliary variables and importance weights during model jumps illustrates how the pseudo-marginal approach operates for N = 100.The figure includes horizontal lines representing the true values of z∗.
- 7.2. Application to variable selection in GLMs.: Expected acceptance probabilities increased from 0.064293 at N = 1 to 0.29371 at N = 200.The reported intermediate values were 0.16569, 0.25885, and 0.28433 for N = 5, 50, and 100.
8. Conclusion.
The paper presents pseudo-marginal Monte Carlo as a versatile methodology with theoretical guarantees for GIMH and exact generalizations, alongside comparisons with an inexact MCWM-like variant.
- 8. Conclusion.: The main theoretical results establish ergodicity and uniform ergodicity for GIMH and the paper’s exact generalizations.The paper also compares these methods with an inexact variant akin to MCWM.