Source-linked AI summary
Noisy Monte Carlo: Convergence of Markov chains with approximate transition kernels
P. Alquier, N. Friel, R. Everitt, A. Boland
TL;DR
The paper studies how to perform MCMC when an ideal transition kernel cannot be simulated because likelihood calculations are computationally infeasible or intractable. It develops stability-based bounds for noisy kernels under ergodicity assumptions and applies them to Gibbs random fields and related models. The results quantify total-variation differences between ideal and noisy chains, while highlighting trade-offs between approximation bias, efficiency, and statistical effectiveness.
Problem
MCMC may require a transition kernel that is computationally infeasible to simulate, especially for large datasets or intractable likelihood models.
Method
The paper develops stability-based bounds comparing noisy approximate kernels with ideal kernels under uniform or geometric ergodicity.
Results
The results bound total-variation distance between ideal and noisy chains and cover noisy Exchange and Langevin algorithms applied to intractable likelihood problems.
Takeaways & Limitations
Noisy MCMC can provide useful approximate inference when exact algorithms are impractical, with a trade-off between bias and efficiency.
Takeaways & Limitations
The theoretical results rely on ergodicity assumptions, and the statistical efficiency of estimators based on noisy-chain averages remains an important open question.
Abstract
from arXiv · showhide
Monte Carlo algorithms often aim to draw from a distribution $π$ by simulating a Markov chain with transition kernel $P$ such that $π$ is invariant under $P$. However, there are many situations for which it is impractical or impossible to draw from the transition kernel $P$. For instance, this is the case with massive datasets, where is it prohibitively expensive to calculate the likelihood and is also the case for intractable likelihood models arising from, for example, Gibbs random fields, such as those found in spatial statistics and network analysis. A natural approach in these cases is to replace $P$ by an approximation $\hat{P}$. Using theory from the stability of Markov chains we explore a variety of situations where it is possible to quantify how 'close' the chain given by the transition kernel $\hat{P}$ is to the chain given by $P$. We apply these results to several examples from spatial statistics and network analysis.
1 Introduction
The paper addresses statistical inference when large datasets, high-dimensional spaces, or intractable likelihoods make standard estimators and MCMC procedures computationally impractical. It develops noisy MCMC theory to quantify how approximate kernels compare with ideal chains and applies the results to spatial and network models.
- Intractable likelihoods arise in applications including spatial statistics, social network analysis, statistical genetics, and finance.
- Large datasets and high-dimensional parameter spaces can make theoretically efficient estimators computationally unavailable in practice.Examples include genomic datasets and weather-prediction state spaces with sizes around 10^9.
- Approximate Bayesian computation replaces an impractical MCMC transition or acceptance calculation with an estimate or approximation.This perspective includes prior work on intractable likelihoods and excessively large sample sizes.
- The paper proposes noisy or inexact MCMC and uses Markov-chain stability theory to justify approximate algorithms under uniform or geometric ergodicity.The analysis bounds total-variation distance between an ideal chain and its noisy approximation.
- The results cover noisy Exchange algorithms and discretized Langevin Monte Carlo, with applications to intractable likelihood problems.
2 Noisy MCMC algorithms
Noisy MCMC replaces an infeasible transition kernel with an approximation and uses Markov-chain stability to bound the resulting discrepancy. The framework covers noisy Metropolis–Hastings, Langevin methods, and pseudo-marginal-related algorithms under ergodicity conditions.
- Motivation: MCMC targets π through a kernel P satisfying πP = π, but computational constraints can make transitions from P infeasible.The paper motivates replacing P with an approximate kernel when exact simulation is unavailable.
- Stability framework: Markov-chain stability bounds the total variation distance between chains generated by P and an approximate kernel ˆP.The main result applies under uniform ergodicity, with an extension to geometric ergodicity.
- Stability framework: The bound between chains with the same initial state is at most a constant times the kernel distance and is independent of the number of steps n.This provides a theoretical basis for using sufficiently accurate approximate kernels.
- Noisy Metropolis–Hastings: Noisy Metropolis–Hastings replaces an intractable acceptance ratio with a randomized estimate whose error must be small.Under suitable conditions, the resulting chain approximates the target chain, with a bound determined by the approximation error.
- Noisy Langevin Monte Carlo: Finite-step Langevin methods generally target a distribution πΣ close to π rather than preserving π exactly, while noisy Langevin uses an approximate transition kernel.The paper establishes convergence of stochastic-gradient Langevin dynamics to the corresponding discrete-time Langevin diffusion.
- Pseudo-marginal connection: The framework includes MCWM as a special case and can sometimes provide an approximation rate in terms of N, the number of auxiliary variables.This extends related pseudo-marginal results to a broader noisy acceptance-probability setting.
3 Examples
The paper applies noisy-kernel convergence theory to Gibbs random fields, developing noisy exchange and Langevin-based algorithms for intractable likelihoods and gradients. Bounds and convergence results describe how approximation improves with Monte Carlo effort under stated assumptions.
- 3.1 Gibbs Random Fields: Gibbs random fields have intractable normalising constants, making direct inference on their parameters problematic.The normalising constant sums over all possible field realisations and is computationally infeasible except in trivial cases.
- 3.1 Gibbs Random Fields: Composite likelihoods offer an accessible approximation, but can produce unreliable parameter estimates.The pseudo-likelihood is formed from products of full-conditional distributions.
- 3.2 Exchange Algorithm: The exchange algorithm cancels normalising constants by augmenting the chain with an auxiliary draw, although resulting Markov random field chains may mix poorly.Its acceptance ratio replaces the normalising-constant ratio, but implementation requires sampling from the likelihood model.
- 3.3 Noisy exchange algorithm: The noisy exchange algorithm estimates normalising-constant ratios using multiple auxiliary simulations, interpolating between exchange and standard Metropolis-Hastings.N = 1 gives the exchange algorithm, while N →∞ gives standard Metropolis-Hastings; finite 1 < N < ∞ is not guaranteed to target the posterior exactly.
- 3.3 Noisy exchange algorithm: Under boundedness and variance assumptions, noisy exchange converges toward the target as N increases, with explicit approximation bounds.The paper states that the approximation rate is explicitly available in contrast to related work that only establishes existence of a sufficiently large N.
- 3.4 Noisy Langevin algorithms: For Gibbs random fields, Monte Carlo gradient estimates enable noisy discretized Langevin methods, whose convergence is established under conditions on N and the prior.A MALA correction can ensure the correct posterior target, while stochastic gradients guide proposals toward higher-density regions.
4 Experiments
The experiments compare exact and noisy exchange, Langevin, and MALA-based algorithms on Ising and network models, finding improved mixing for noisy methods alongside approximation-related bias and variance underestimation.
- Experimental setup: The experiments evaluate noisy exchange and MALA-exchange algorithms on an Ising model and two network datasets.The network examples are the Florentine family business graph and a 20-node molecule graph.
- 4.1 Ising study: The Ising study uses 20 simulated 16 × 16 grids, with exact normalising constants providing a gold standard for comparison.Each algorithm ran for 30 seconds per dataset, with 1000 auxiliary iterations and N = 100 additional draws for noisy methods.
- 4.1 Ising study: The noisy exchange and Langevin algorithms have much smaller posterior-mean bias than the two exchange algorithms, reflecting a bias–efficiency trade-off.The authors attribute the improved performance of approximate algorithms to better mixing, while noting that decreasing step size reduces both efficiency and bias.
- Network studies: The noisy exchange improves mean estimates over exchange, and MALA exchange improves on noisy Langevin in the Florentine and molecule analyses.For the molecule dataset, Noisy MALA further improves on MALA exchange according to the reported posterior summaries.
- Network studies: In the Florentine and molecule studies, noisy algorithms mix better than exchange, while most methods estimate the mode well but underestimate posterior standard deviations.The noisy Langevin algorithm performs poorly on the molecule model, failing to estimate the mean or standard deviations well.
- Limitations: Noisy Langevin involves two approximation levels because it approximates Langevin diffusion while also using an approximate gradient, leaving more room for error.The paper identifies this layered approximation as a limitation of the method.
2 Star
This section presents molecule-example density and autocorrelation plots for four parameters, alongside algorithm labels including noisy and exchange variants.
- The displayed algorithm labels include BERGM Exchange, Noisy Exch, Noisy Lang, MALA Exch, and Noisy MALA Exch.
- The molecule example includes density plots for four parameters.
- The molecule example includes autocorrelation plots for four parameters.
5 Conclusion
The conclusion reports total-variation bounds for noisy MCMC while identifying statistical-efficiency analysis and broader ergodicity conditions as future work.
- The paper gives total-variation bounds between noisy MCMC chains and chains with the desired target distribution.
- Future work should study the asymptotic variance of estimators from noisy MCMC to assess combined statistical and computational efficiency.
- Additional variance from noisy MCMC should be considered alongside the bias introduced by approximation.
- The results currently rely on uniform ergodicity of the ideal non-noisy chain, a property that does not hold in many cases.
A Proofs
The proofs establish conditions for convergence and approximation bounds for noisy Markov-chain kernels, including geometric ergodicity arguments and limits as randomization increases.
- The proofs apply Theorem 2.1 and verify assumptions for convergence results involving noisy kernels.
- The proofs establish small-set and drift-related conditions used to verify geometric ergodicity.
- A bound involving δ/2 tends to 0 as N tends to infinity, supporting convergence of the approximate kernel.
- Under stated conditions, the transition kernel P_Σ is geometrically ergodic with a specified function V.
- The resulting approximate stationary distribution converges to the target under the theorem's assumptions.