Nonasymptotic bounds on the estimation error of MCMC algorithms

DOI10.3150/12-BEJ442MaRDI QIDQ2435233zbMATH OpenOpenAlexWikidataFDO

Authors Krzysztof Łatuszyński, Błażej Miasojedow, Wojciech Niemiro

Publication date 4 February 2014

Published in Bernoulli (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic variancemean square errorregenerationgeometric ergodicitycomputable boundsconfidence estimationpolynomial ergodicitydrift conditions

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Bayesian inference (62F15) Monte Carlo methods (65C05)

Abstract: We address the problem of upper bounding the mean square error of MCMC estimators. Our analysis is nonasymptotic. We first establish a general result valid for essentially all ergodic Markov chains encountered in Bayesian computation and a possibly unbounded target function $f$. The bound is sharp in the sense that the leading term is exactly $sigm{a}_{mathrmas}^2(P,f)/n$, where $sigm{a}_{mathrmas}^2(P,f)$ is the CLT asymptotic variance. Next, we proceed to specific additional assumptions and give explicit computable bounds for geometrically and polynomially ergodic Markov chains under quantitative drift conditions. As a corollary, we provide results on confidence estimation.

Recommendations

• Error bounds of MCMC for functions with unbounded stationary variance
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Explicit error bounds for Markov chain Monte Carlo
• Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
• Explicit error bounds for lazy reversible Markov chain Monte Carlo

Cites work

• scientific article; zbMATH DE number 5520724 (Why is no real title available?)
• A Chernoff Bound for Random Walks on Expander Graphs
• A New Approach to the Limit Theory of Recurrent Markov Chains
• A measure concentration inequality for contracting Markov chains
• A regeneration proof of the central limit theorem for uniformly ergodic Markov chains
• A splitting technique for Harris recurrent Markov chains
• A tail inequality for suprema of unbounded empirical processes with applications to Markov chains
• Bounds on regeneration times and convergence rates for Markov chains
• Bounds on regeneration times and limit theorems for subgeometric Markov chains
• Computable bounds for geometric convergence rates of Markov chains
• Computable convergence rates for sub-geometric ergodic Markov chains
• Concentration inequalities for dependent random variables via the martingale method
• Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes.
• Convergence of the Monte Carlo expectation maximization for curved exponential families.
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Fixed Precision MCMC Estimation by Median of Products of Averages
• Fixed-Width Output Analysis for Markov Chain Monte Carlo
• General state space Markov chains and MCMC algorithms
• Geometric Convergence Rates for Stochastically Ordered Markov Chains
• Geometric Ergodicity of van Dyk and Meng's Algorithm for the Multivariate Student'stModel
• Geometric ergodicity of Gibbs and block Gibbs samplers for a hierarchical random effects model
• Gibbs sampling for a Bayesian hierarchical general linear model
• Hoeffding's inequality for uniformly ergodic Markov chains
• Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
• MC's for MCMC'ists
• Markov chains and stochastic stability
• Markov chains for exploring posterior distributions. (With discussion)
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• Moment and probability inequalities for sums of bounded additive functionals of regular Markov chains via the Nummelin splitting technique
• Necessary conditions for geometric and polynomial ergodicity of random-walk-type Markov chains
• Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
• On Excess Over the Boundary
• On Monte Carlo methods for Bayesian multivariate regression models with heavy-tailed errors
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• On the geometric ergodicity of hybrid samplers
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Polynomial convergence rates of Markov chains
• Polynomial ergodicity of Markov transition kernels.
• Practical drift conditions for subgeometric rates of convergence.
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Quantitative convergence rates of Markov chains: A simple account
• Quantitative non-geometric convergence bounds for independence samplers
• Random generation of combinatorial structures from a uniform distribution
• Rates of convergence for Gibbs sampling for variance component models
• Regeneration in Markov Chain Samplers
• Renewal theory and computable convergence rates for geometrically erdgodic Markov chains
• Rigorous confidence bounds for MCMC under a geometric drift condition
• SMALL AND PSEUDO-SMALL SETS FOR MARKOV CHAINS
• Sampling-Based Approaches to Calculating Marginal Densities
• Sharp bounds for the tails of functionals of Markov chains
• Simple Monte Carlo and the Metropolis algorithm
• Stability of the Gibbs sampler for Bayesian hierarchical models
• Sufficient burn-in for Gibbs samplers for a hierarchical random effects model.
• \(V\)-subgeometric ergodicity for a Hastings-Metropolis algorithm

Cited in

(29)

• Multilevel Monte Carlo estimation of the expected value of sample information
• scientific article; zbMATH DE number 7415082 (Why is no real title available?)
• On a Metropolis-Hastings importance sampling estimator
• Spectral gaps and error estimates for infinite-dimensional Metropolis-Hastings with non-Gaussian priors
• Error bounds of MCMC for functions with unbounded stationary variance
• Rare Event Simulation Using Reversible Shaking Transformations
• Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms
• Markov chain Monte Carlo confidence intervals
• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Orlicz Integrability of Additive Functionals of Harris Ergodic Markov Chains
• Computation of expectations by Markov chain Monte Carlo methods
• Exponential concentration inequalities for additive functionals of Markov chains
• Complexity results for MCMC derived from quantitative bounds
• Geometric ergodicity of a more efficient conditional Metropolis-Hastings algorithm
• Hit-and-run for numerical integration
• Convergence complexity analysis of Albert and Chib's algorithm for Bayesian probit regression
• Analysis of a Class of Multilevel Markov Chain Monte Carlo Algorithms Based on Independent Metropolis–Hastings
• Information geometry approach to parameter estimation in Markov chains
• Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms
• Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings
• Error bounds for computing the expectation by Markov chain Monte Carlo
• A hybrid scan Gibbs sampler for Bayesian models with latent variables
• Convergence analysis of a collapsed Gibbs sampler for Bayesian vector autoregressions
• Dimension‐independent Markov chain Monte Carlo on the sphere
• Markov chain Monte Carlo estimation of quantiles
• Nonasymptotic bounds on the mean square error for MCMC estimates via renewal techniques
• On the convergence time of some non-reversible Markov chain Monte Carlo methods
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Markov Kernels Local Aggregation for Noise Vanishing Distribution Sampling

This page was built for publication: Nonasymptotic bounds on the estimation error of MCMC algorithms

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