Quantitative contraction rates for Markov chains on general state spaces

DOI10.1214/19-EJP287MaRDI QIDQ2631852zbMATH OpenOpenAlexFDO

Authors Andreas Eberle, Mateusz B. Majka

Publication date 16 May 2019

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.07033, https://projecteuclid.org/euclid.ejp/1553565777

zbMATH Keywords

Markov chainscouplingsEuler schemesWasserstein distancesmetropolis algorithmquantitative bounds

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Discrete-time Markov processes on general state spaces (60J05) Numerical solutions to stochastic differential and integral equations (65C30)

Abstract: We investigate the problem of quantifying contraction coefficients of Markov transition kernels in Kantorovich ($L^1$ Wasserstein) distances. For diffusion processes, relatively precise quantitative bounds on contraction rates have recently been derived by combining appropriate couplings with carefully designed Kantorovich distances. In this paper, we partially carry over this approach from diffusions to Markov chains. We derive quantitative lower bounds on contraction rates for Markov chains on general state spaces that are powerful if the dynamics is dominated by small local moves. For Markov chains on $mathbb{R}^d$ with isotropic transition kernels, the general bounds can be used efficiently together with a coupling that combines maximal and reflection coupling. The results are applied to Euler discretizations of stochastic differential equations with non-globally contractive drifts, and to the Metropolis adjusted Langevin algorithm for sampling from a class of probability measures on high dimensional state spaces that are not globally log-concave.

Recommendations

• Strict Kantorovich contractions for Markov chains and Euler schemes with general noise
• On contraction properties of Markov kernels
• Reflection couplings and contraction rates for diffusions
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Quantitative bounds for Markov chain convergence: Wasserstein and total variation distances

Cites work

• Analysis and geometry of Markov diffusion operators
• Application of coupling methods to the Neumann eigenvalue problem
• Asymptotic coupling and a general form of Harris' theorem with applications to stochastic delay equations
• Central limit theorem for Markov processes with spectral gap in the Wasserstein metric
• Coupling and convergence for Hamiltonian Monte Carlo
• Coupling and exponential ergodicity for stochastic differential equations driven by Lévy processes
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• Estimation of spectral gap for elliptic operators
• Estimation of the first eigenvalue of second order elliptic operators
• Exact solutions to the transportation problem on the line
• Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
• Exponential ergodicity for Markov processes with random switching
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Markov Chains and Stochastic Stability
• Mixing and concentration by Ricci curvature
• Nonasymptotic bounds for sampling algorithms without log-concavity
• Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
• Perturbation theory for Markov chains via Wasserstein distance
• Quantitative Harris-type theorems for diffusions and McKean-Vlasov processes
• Quantitative bounds of convergence for geometrically ergodic Markov chain in the Wasserstein distance with application to the Metropolis adjusted Langevin algorithm
• Refined basic couplings and Wasserstein-type distances for SDEs with Lévy noises
• Reflection coupling and Wasserstein contractivity without convexity
• Reflection couplings and contraction rates for diffusions
• Ricci curvature of Markov chains on metric spaces
• Separation cut-offs for birth and death chains
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• Spectral gaps in Wasserstein distances and the 2D stochastic Navier-Stokes equations
• Sticky couplings of multidimensional diffusions with different drifts
• Subgeometric rates of convergence in Wasserstein distance for Markov chains
• Subgeometric rates of convergence of Markov processes in the Wasserstein metric
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
• Total variation cutoff in birth-and-death chains
• Transport inequalities, gradient estimates, entropy and Ricci curvature
• Transportation inequalities for non-globally dissipative SDEs with jumps via Malliavin calculus and coupling
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Yet Another Look at Harris’ Ergodic Theorem for Markov Chains
• \(L^{p}\)-Wasserstein distance for stochastic differential equations driven by Lévy processes

Cited in

(28)

• Optimal Markovian coupling for finite activity Lévy processes
• Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions
• Efficient stochastic optimisation by unadjusted Langevin Monte Carlo. Application to maximum marginal likelihood and empirical Bayesian estimation
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• The explicit form of the rate function for semi-Markov processes and its contractions
• Approximation of heavy-tailed distributions via stable-driven SDEs
• Strict Kantorovich contractions for Markov chains and Euler schemes with general noise
• Asymptotic bias of inexact Markov chain Monte Carlo methods in high dimension
• \(L^2\)-Wasserstein contraction for Euler schemes of elliptic diffusions and interacting particle systems
• scientific article; zbMATH DE number 6807849 (Why is no real title available?)
• Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
• On the limitations of single-step drift and minorization in Markov chain convergence analysis
• Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity
• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• On contraction properties of Markov kernels
• A contractive property in finite state Markov chains
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime
• Reflection couplings and contraction rates for diffusions
• Maximum entropy methods for texture synthesis: theory and practice
• Multi-index antithetic stochastic gradient algorithm
• The forward-backward envelope for sampling with the overdamped Langevin algorithm
• Reflection coupling and Wasserstein contractivity without convexity
• Quantitative Harris-type theorems for diffusions and McKean-Vlasov processes
• Recent advances in the long-time analysis of killed degenerate processes and their particle approximation
• Wasserstein contraction and Poincaré inequalities for elliptic diffusions with high diffusivity
• Nonasymptotic bounds for sampling algorithms without log-concavity

This page was built for publication: Quantitative contraction rates for Markov chains on general state spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631852)