Nonasymptotic mixing of the MALA algorithm

DOI10.1093/IMANUM/DRS003zbMATH Open1305.65012arXiv1008.3514OpenAlexW2963964450MaRDI QIDQ4907962FDOQ4907962

Martin Hairer, Nawaf Bou-Rabee

Publication date: 27 February 2013

Published in: IMA Journal of Numerical Analysis (Search for Journal in Brave)

Abstract: The Metropolis-Adjusted Langevin Algorithm (MALA), originally introduced to sample exactly the invariant measure of certain stochastic differential equations (SDE) on infinitely long time intervals, can also be used to approximate pathwise the solution of these SDEs on finite time intervals. However, when applied to an SDE with a nonglobally Lipschitz drift coefficient, the algorithm may not have a spectral gap even when the SDE does. This paper reconciles MALA's lack of a spectral gap with its ergodicity to the invariant measure of the SDE and finite time accuracy. In particular, the paper shows that its convergence to equilibrium happens at exponential rate up to terms exponentially small in time-stepsize. This quantification relies on MALA's ability to exactly preserve the SDE's invariant measure and accurately represent the SDE's transition probability on finite time intervals.

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

Recommendations

• Non-stationary phase of the MALA algorithm
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions
• Nonasymptotic convergence analysis for the unadjusted Langevin algorithm

zbMATH Keywords

Metropolis-Hastings algorithmconvergence rateinvariant measuresstochastic differential equationsspectral gapgeometric ergodicitytransition probabilityMetropolis-adjusted Langevin algorithmconvergence to equilibriumfinite-time transition probabilityweak accuracy

Mathematics Subject Classification ID

Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Ordinary differential equations and systems with randomness (34F05) Generation, random and stochastic difference and differential equations (37H10) Applications of stochastic analysis (to PDEs, etc.) (60H30) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Numerical solutions to stochastic differential and integral equations (65C30)

Cited In (31)

• Metropolis Integration Schemes for Self-Adjoint Diffusions
• Continuous-time Random Walks for the Numerical Solution of Stochastic Differential Equations
• Convergence of the likelihood ratio method for linear response of non-equilibrium stationary states
• Improving dynamical properties of metropolized discretizations of overdamped Langevin dynamics
• Error analysis of the transport properties of Metropolized schemes
• SPECTRWM: Spectral Random Walk Method for the Numerical Solution of Stochastic Partial Differential Equations
• Ensemble Kalman Sampler: Mean-field Limit and Convergence Analysis
• Title not available (Why is that?)
• On the geometric ergodicity of Hamiltonian Monte Carlo
• On a generalization of the preconditioned Crank-Nicolson metropolis algorithm
• Reflection couplings and contraction rates for diffusions
• On a perturbation theory and on strong convergence rates for stochastic ordinary and partial differential equations with nonglobally monotone coefficients
• The tamed unadjusted Langevin algorithm
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime
• Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity
• Oracle lower bounds for stochastic gradient sampling algorithms
• Bayesian computation: a summary of the current state, and samples backwards and forwards
• Exponential moments for numerical approximations of stochastic partial differential equations
• Langevin Dynamics With General Kinetic Energies
• Exponential integrability properties of numerical approximation processes for nonlinear stochastic differential equations
• Scaling Limit of the Stein Variational Gradient Descent: The Mean Field Regime
• Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions
• Partial differential equations and stochastic methods in molecular dynamics
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Convergence rates of Metropolis-Hastings algorithms
• More on the long time stability of Feynman-Kac semigroups
• Geometric integrators and the Hamiltonian Monte Carlo method
• Complexity results for MCMC derived from quantitative bounds
• On sampling from a log-concave density using kinetic Langevin diffusions
• Numerical approximations of stochastic differential equations with non-globally Lipschitz continuous coefficients
• Dimension-Independent MCMC Sampling for Inverse Problems with Non-Gaussian Priors

This page was built for publication: Nonasymptotic mixing of the MALA algorithm

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