Curvature, concentration and error estimates for Markov chain Monte Carlo

DOI10.1214/10-AOP541zbMath1207.65006arXiv0904.1312OpenAlexW3106022061MaRDI QIDQ606638

Aldéric Joulin, Yann Ollivier

Publication date: 18 November 2010

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

convergenceMarkov chain Monte Carlo methodRicci curvatureIsing modelconcentration of measureWasserstein distance\(M/M/\infty\) queueing processEuler scheme for diffusionsexplicit nonasymptotic

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Queueing theory (aspects of probability theory) (60K25) Numerical analysis or methods applied to Markov chains (65C40) Diffusion processes (60J60) Approximations to statistical distributions (nonasymptotic) (62E17) Numerical solutions to stochastic differential and integral equations (65C30) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44)

Related Items (48)

Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms ⋮ Rapid mixing of geodesic walks on manifolds with positive curvature ⋮ Quantitative contraction rates for Markov chains on general state spaces ⋮ Information geometry approach to parameter estimation in Markov chains ⋮ Strict Kantorovich contractions for Markov chains and Euler schemes with general noise ⋮ Reflection couplings and contraction rates for diffusions ⋮ Hit-and-Run for Numerical Integration ⋮ Coupling and convergence for Hamiltonian Monte Carlo ⋮ Transport-information inequalities for Markov chains ⋮ Nonasymptotic bounds for sampling algorithms without log-concavity ⋮ Optimal transportation and stationary measures for iterated function systems ⋮ Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph ⋮ Exponential inequalities for nonstationary Markov chains ⋮ On a Metropolis-Hastings importance sampling estimator ⋮ Lower bound for the coarse Ricci curvature of continuous-time pure-jump processes ⋮ Self-improvement of the Bakry-Emery criterion for Poincaré inequalities and Wasserstein contraction using variable curvature bounds ⋮ Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions ⋮ Sparse expanders have negative curvature ⋮ Exact convergence analysis for metropolis–hastings independence samplers in Wasserstein distances ⋮ Mixing and concentration by Ricci curvature ⋮ Using perturbed underdamped Langevin dynamics to efficiently sample from probability distributions ⋮ Nonasymptotic bounds on the estimation error of MCMC algorithms ⋮ The mathematics of mixing things up ⋮ Empirical measures: regularity is a counter-curse to dimensionality ⋮ Exact and asymptotic results on coarse Ricci curvature of graphs ⋮ Convergence rate and concentration inequalities for Gibbs sampling in high dimension ⋮ On the mean speed of convergence of empirical and occupation measures in Wasserstein distance ⋮ Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions ⋮ Multilevel Monte Carlo Estimation of the Expected Value of Sample Information ⋮ Function-specific mixing times and concentration away from equilibrium ⋮ Non-asymptotic Gaussian estimates for the recursive approximation of the invariant distribution of a diffusion ⋮ Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes ⋮ High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion ⋮ Normalizing constants of log-concave densities ⋮ Concentration inequalities for additive functionals: a martingale approach ⋮ Sampling the Fermi statistics and other conditional product measures ⋮ Convergence rates of symmetric scan Gibbs sampler ⋮ Measuring sample quality with diffusions ⋮ Two-scale coupling for preconditioned Hamiltonian Monte Carlo in infinite dimensions ⋮ Forward sensitivity analysis for contracting stochastic systems ⋮ Online Discrete Optimization in Social Networks in the Presence of Knightian Uncertainty ⋮ A weighted discrepancy bound of quasi-Monte Carlo importance sampling ⋮ High-dimensional Bayesian inference via the unadjusted Langevin algorithm ⋮ Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings ⋮ Computation of Expectations by Markov Chain Monte Carlo Methods ⋮ Error bounds of MCMC for functions with unbounded stationary variance ⋮ On efficient randomized algorithms for finding the PageRank vector ⋮ Convergence of a particle approximation for the quasi-stationary distribution of a diffusion process: Uniform estimates in a compact soft case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature
• Markov chains and stochastic stability
• General state space Markov chains and MCMC algorithms
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Ricci curvature of Markov chains on metric spaces
• Mécanique aléatoire
• Chernoff-type bound for finite Markov chains
• Application of coupling method to the first eigenvalue on manifold
• Weak convergence of recursions
• A deviation inequality for non-reversible Markov processes
• Transportation cost-information inequalities and applications to random dynamical systems and diffusions.
• On the convergence to equilibrium of Kac's random walk on matrices
• Transportation-information inequalities for Markov processes
• Ricci curvature of metric spaces
• Poisson-type deviation inequalities for curved continuous-time Markov chains
• Logarithmic Sobolev inequalities for finite Markov chains
• deviation bounds for additive functionals of markov processes

This page was built for publication: Curvature, concentration and error estimates for Markov chain Monte Carlo