Quantitative contraction rates for Markov chains on general state spaces

DOI10.1214/19-EJP287zbMATH Open1466.60137arXiv1808.07033OpenAlexW2962732064MaRDI QIDQ2631852FDOQ2631852

Authors: Andreas Eberle, Mateusz B. Majka 

Publication date: 16 May 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1808.07033

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

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)

Cites Work

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

Cited In (26)

• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions
• On contraction properties of Markov kernels
• Optimal Markovian coupling for finite activity Lévy processes
• Reflection coupling and Wasserstein contractivity without convexity
• The explicit form of the rate function for semi-Markov processes and its contractions
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime
• Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity
• Multi-index antithetic stochastic gradient algorithm
• Maximum Entropy Methods for Texture Synthesis: Theory and Practice
• Wasserstein contraction and Poincaré inequalities for elliptic diffusions with high diffusivity
• Approximation of heavy-tailed distributions via stable-driven SDEs
• Strict Kantorovich contractions for Markov chains and Euler schemes with general noise
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Nonasymptotic bounds for sampling algorithms without log-concavity
• Efficient stochastic optimisation by unadjusted Langevin Monte Carlo. Application to maximum marginal likelihood and empirical Bayesian estimation
• The forward-backward envelope for sampling with the overdamped Langevin algorithm
• \(L^2\)-Wasserstein contraction for Euler schemes of elliptic diffusions and interacting particle systems
• 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
• Asymptotic bias of inexact Markov chain Monte Carlo methods in high dimension
• A contractive property in finite state Markov chains
• Recent advances in the long-time analysis of killed degenerate processes and their particle approximation
• Title not available (Why is that?)
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm

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)