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

DOI10.1017/APR.2019.40MaRDI QIDQ5203974zbMATH OpenOpenAlexWikidataFDO

Authors Aleksandar Mijatović, Jure Vogrinc

Publication date 9 December 2019

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

Full work available at URL https://arxiv.org/abs/1707.08510, http://wrap.warwick.ac.uk/119123/1/WRAP-asymptotic-variance-random-walk-metropolis-chains-high-dimensions-Vogrinc-2019.pdf

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)

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.

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

Cites work

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

Cited in

(8)

• Convergence rates for a class of estimators based on Stein's method
• Asymptotic analysis of the random walk metropolis algorithm on ridged densities
• A Riemann-Stein kernel method
• 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)