Asymptotic variance for random walk Metropolis chains in high dimensions: logarithmic growth via the Poisson equation

DOI10.1017/APR.2019.40zbMATH Open1427.60146arXiv1707.08510OpenAlexW2984713686WikidataQ126808212 ScholiaQ126808212MaRDI QIDQ5203974FDOQ5203974

Authors: Aleksandar Mijatović, Jure Vogrinc 

Publication date: 9 December 2019

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: There are two ways of speeding up MCMC algorithms: (1) construct more complex samplers that use gradient and higher order information about the target and (2) design a control variate to reduce the asymptotic variance. While the efficiency of (1) as a function of dimension has been studied extensively, this paper provides first rigorous results linking the growth of the asymptotic variance in (2) with dimension. Specifically, we construct a control variate for a $d$-dimensional Random walk Metropolis chain with an IID target using the solution of the Poisson equation for the scaling limit in the seminal paper "Weak convergence and optimal scaling of random walk Metropolis algorithms" of Gelman, Gilks and Roberts. We prove that the asymptotic variance of the corresponding estimator is bounded above by a multiple of $logd/d$ over the spectral gap of the chain. The proof hinges on large deviations theory, optimal Young's inequality and Berry-Esseen type bounds. Extensions of the result to non-product targets are discussed.

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

Recommendations

• Variance reduction for Metropolis-Hastings samplers
• Random walk Metropolis algorithm in high dimension with non-Gaussian target distributions
• Fast Langevin based algorithm for MCMC in high dimensions
• Weak convergence and optimal scaling of random walk Metropolis algorithms
• On the Poisson equation for Metropolis-Hastings chains

zbMATH Keywords

Berry-Esseen boundvariance reductionlarge deviationsasymptotic varianceoptimal Young's inequalityPoisson equation for diffusionsscaling limits of Metropolis-Hastings chain

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Large deviations (60F10) Central limit and other weak theorems (60F05) Discrete-time Markov processes on general state spaces (60J05) Transition functions, generators and resolvents (60J35)

Cites Work

• Weak convergence and optimal scaling of random walk Metropolis algorithms
• Markov chains for exploring posterior distributions. (With discussion)
• Markov Chains and Stochastic Stability
• Handbook of Markov Chain Monte Carlo
• Optimal scaling for various Metropolis-Hastings algorithms.
• Geometric ergodicity of Metropolis algorithms
• Optimal Scaling of Discrete Approximations to Langevin Diffusions
• Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions
• Geometric ergodicity and hybrid Markov chains
• Probability with Martingales
• Series approximation methods in statistics.
• Control Functionals for Monte Carlo Integration
• Moderate Deviations for I.I.D. Random Variables
• Optimal scalings for local Metropolis-Hastings chains on nonproduct targets in high dimensions
• Variance reduction using nonreversible Langevin samplers
• Control Variates for Estimation Based on Reversible Markov Chain Monte Carlo Samplers
• Control Techniques for Complex Networks
• Optimal tuning of the hybrid Monte Carlo algorithm
• Optimal Young's inequality and its converse: A simple proof
• Weak convergence of Metropolis algorithms for non-I.I.D. target distributions
• Optimal scaling of Metropolis algorithms: Heading toward general target distributions
• Diffusion limits of the random walk Metropolis algorithm in high dimensions
• Optimal scaling and diffusion limits for the Langevin algorithm in high dimensions
• Optimal scaling for the transient phase of the random walk Metropolis algorithm: the mean-field limit
• Zero variance differential geometric Markov chain Monte Carlo algorithms
• Fast Langevin based algorithm for MCMC in high dimensions
• A piecewise deterministic scaling limit of lifted Metropolis-Hastings in the Curie-Weiss model
• On the Poisson equation for Metropolis-Hastings chains

Cited In (8)

• Convergence rates for a class of estimators based on Stein's method
• A Riemann-Stein kernel method
• Asymptotic analysis of the random walk metropolis algorithm on ridged densities
• Counterexamples for optimal scaling of Metropolis-Hastings chains with rough target densities
• On the Poisson equation for Metropolis-Hastings chains
• Matrix-Analytic Methods for Solving Poisson’s Equation with Applications to Markov Chains of GI/G/1-Type
• Asymptotic bias of inexact Markov chain Monte Carlo methods in high dimension
• Variance reduction for Metropolis-Hastings samplers

This page was built for publication: Asymptotic variance for random walk Metropolis chains in high dimensions: logarithmic growth via the Poisson equation

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