Source-linked AI summary
Perturbation theory for Markov chains via Wasserstein distance
Daniel Rudolf, Nikolaus Schweizer
TL;DR
The paper asks how transition differences affect the distributions of Markov chains, particularly for approximate MCMC. It develops Wasserstein perturbation bounds using Lyapunov functions, and shows the autoregressive bound cannot be improved in general while providing quantitative estimates for approximate MCMC algorithms.
Problem
The paper asks how small transition differences between Markov chains affect differences between their distributions, a question motivated by approximate MCMC methods.
Source: §1 · p. 1Method
The paper derives Wasserstein perturbation bounds under Wasserstein ergodicity, using Lyapunov functions to obtain estimates for geometrically ergodic chains.
Source: §1 · p. 2, §3.1 · pp. 6–7Results
The autoregressive example shows the upper bound cannot be improved in general, and the paper provides quantitative estimates for approximate Metropolis-Hastings and noisy Langevin algorithms.
Source: §1 · p. 2, §4.1 · p. 17Takeaways & Limitations
The bounds provide quantitative estimates of approximate MCMC bias and can be combined with existing convergence results for MCMC algorithms.
Source: §1 · p. 2For the noisy Langevin estimates, the assumptions match [2, Theorem 3.2], but the constants ρ and C are not stated in terms of model parameters.
Source: §4.3 · p. 28
Abstract
from arXiv · showhide
Perturbation theory for Markov chains addresses the question how small differences in the transitions of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the $n$th step distributions of two Markov chains when one of them satisfies a Wasserstein ergodicity condition. Our work is motivated by the recent interest in approximate Markov chain Monte Carlo (MCMC) methods in the analysis of big data sets. By using an approach based on Lyapunov functions, we provide estimates for geometrically ergodic Markov chains under weak assumptions. In an autoregressive model, our bounds cannot be improved in general. We illustrate our theory by showing quantitative estimates for approximate versions of two prominent MCMC algorithms, the Metropolis-Hastings and stochastic Langevin algorithms.
1. Introduction
The paper develops Wasserstein-based perturbation bounds to quantify how differences in Markov-chain transitions affect their distributions, with approximate MCMC as a motivating application. It extends the analysis to geometrically ergodic chains and uses Lyapunov-type stability conditions to address non-compact state spaces.
1. Introduction
- Approximate MCMC can reduce the cost of evaluating target densities on large data sets, but approximating those densities induces bias and can change algorithm properties.The paper motivates a need for theoretical estimates of these biases.Source: §1 · pp. 1–2
- The Wasserstein perturbation bound controls the distance between nth-step distributions using the one-step transition difference, and the autoregressive example shows the bound cannot be improved in general.The bounds also yield estimates for geometrically ergodic chains and are applied to approximate Metropolis-Hastings and noisy Langevin algorithms.Source: §1 · p. 2
1.1. Related literature
- For geometrically ergodic chains, the bounds require control only of one-step transition errors and use Lyapunov-type stability conditions.The paper contrasts this flexibility with, which requires control of iterated transition kernels in a weaker sense.Source: §1.1 · pp. 2–3
- Unlike bounds in [35] that restrict attention to subsets and involve exit probabilities, this approach uses Lyapunov-type stability conditions for the approximate algorithm.The paper also emphasizes nonasymptotic estimates with explicit constants compared with the qualitative focus of.Source: §1.1 · p. 3
2. Wasserstein ergodicity
This section introduces Wasserstein distance and an ergodicity coefficient, then relates contractivity under a Markov transition to convergence toward stationarity.
2. Wasserstein ergodicity
- Wasserstein distance compares probability measures through couplings, and it is a metric but need not be finite.The underlying state-space metric is assumed lower semicontinuous; point masses satisfy W(δx, δy) = d(x, y).Source: §2 · p. 3
- The generalized ergodicity coefficient is linked to Wasserstein contraction, while the trivial metric recovers total variation distance.The coefficient is also described as a generalized Dobrushin coefficient and provides a lower bound on coarse Ricci curvature.Source: §2 · pp. 4–5
- For the trivial metric, the Wasserstein distance equals total variation; with an atom-free stationary distribution, the section gives a related coefficient bound.The assumption of uniform ergodicity is also introduced in this section.Source: §2 · p. 5
- Wasserstein ergodicity assumes exponential decay of the transition kernel's ergodicity coefficient, yielding convergence toward stationarity under the stated condition.The section motivates this condition through submultiplicativity and contractivity of the coefficient.Source: §2 · p. 5
4. Applications
This section applies the perturbation theory to autoregressive processes and approximate Metropolis-Hastings and noisy Langevin algorithms, providing quantitative bounds and describing their assumptions, conditions, and limitations.
4.1. Autoregressive process
- For the autoregressive process, sufficiently close parameters give an explicit bound on the distance between nth-step distributions, and its stationary-distribution dependence on |α − eα| cannot generally be improved.The lower bound establishing sharpness is non-trivial when E Z1 ≠ 0.Source: §4.1 · p. 17
- With a density h that is weakly unimodal and bounded above, the autoregressive analysis obtains a new quantitative estimate for small |α − eα|, where an earlier corollary could not quantify closeness.The estimate assumes equal initial distributions and hmax ≤ 1.Source: §4.1 · p. 18
4.2. Approximate Metropolis-Hastings algorithms
- The Wasserstein distance between Metropolis-Hastings transition kernels is controlled by integrating d(x, y)|α(x, y) − eα(x, y)| against the proposal kernel.This kernel estimate feeds into a perturbation bound for the approximate algorithm.Source: §4.2 · p. 20
- For a local perturbation set eG, a non-trivial Lyapunov function yields a bias bound that becomes small when µ(eG) is small.With the trivial Lyapunov function, the resulting bound can remain bounded away from zero regardless of eG.Source: §4.2 · p. 22
- Approximate Metropolis-Hastings bounds cover geometrically ergodic chains without requiring uniform ergodicity, extending a result of Bardenet et al..Corollary 4.2 gives a bound when the uniform acceptance-probability error s is below (1 − δ)/λ.Source: §4.2 · pp. 19, 22, 23
4.3. Noisy Langevin algorithm for Gibbs random fields
- The noisy method replaces the unavailable exact likelihood-gradient expectation with a Monte Carlo estimate based on N samples; approximate Langevin methods include.This section provides a quantitative version of [2, Section 3.4] and [2, Theorem 3.2].Source: §4.3 · pp. 24–25
- Under finite ∥s∥∞ and σ² < 4σ_p², V(θ) = 1 + |θ| is a Lyapunov function, and Pσ and Pσ,N are V-uniformly ergodic with stationary distributions.The drift inequalities use common δ and L constants for the exact and noisy kernels.Source: §4.3 · pp. 26–27
- Using facts collected in the previous proposition, the authors apply the perturbation bound of Theorem 3.2 to obtain a quantitative perturbation bound for the noisy Langevin algorithm.Source: §4.3 · p. 28
- The assumptions match [2, Theorem 3.2], but the authors provide an explicit estimate rather than an asymptotic result; its constants are not stated in model parameters.The constants can in principle be derived from the drift condition using [5, Theorem 1.1].Source: §4.3 · p. 28