CURVATURE, CONCENTRATION AND ERROR ESTIMATES FOR MARKOV CHAIN MONTE CARLO

By A. Joulin, Yann Ollivier. 2009

154 citations recorded by the source corpus.

We provide explicit nonasymptotic estimates for the rate of convergence of empirical means of Markov chains, together with a Gaussian or exponential control on the deviations of empirical means. These estimates hold under a "positive curvature" assumption expressing a kind of metric ergodicity, which generalizes the Ricci curvature from differential geometry and, on finite graphs, amounts to contraction under path coupling.

Subfields: Applied Mathematics, Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ca05e6a389f89b771cf0e6422dc95f1792769971

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Quantitative contraction rates for Markov chains on general state spaces (2018, methodology): “In the terminology of Joulin and Ollivier [29], (2.”
On Some non Asymptotic Bounds for the Euler Scheme (2010, result): “s. Their goal was in some sense diﬀerent than ours since they were mainly interested in ergodic simulations. In that framework we also mention the recent work of Joulin and Ollivier for Markov chains [JO09]. Our strategy is here diﬀerent. We are interested in the approximation of Q(t,x),t6 Twhere T&”
Curvature and transport inequalities for Markov chains in discrete spaces (2015, methodology): “Applications to error estimates for Markov Chain Monte Carlo were studied in [25].”
Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator (2011, background): “By now, there exist many notions of generalized curvature, and several of them have found important applications, see Sturm [20, 21], Lott-Villani [16], Ollivier [18], Ohta [17], Bonciocat-Sturm [2], Joulin-Ollivier [12] and the references therein.”
Spectral gaps for a Metropolis–Hastings algorithm in infinite dimensions (2011, methodology): “Uniform contraction in a Wasserstein distance was first applied to MCMC in Joulin and Ollivier (2010) in order to get bounds on the variance and bias of the sample average of Lipschitz functionals.”
On the mean speed of convergence of empirical and occupation measures in Wasserstein distance (2011, background): “5 in [10] as well as to [4,20] in the W1 case.”
Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes (2016, background): “rem 6.15]. Thus if there is a constant K > 0 such that |x|p ≤ K V (x) holds for all x ∈ Rd, then Corollary 2.1 also implies exponential convergence in Lp-Wasserstein distance. Following ideas from [34, 35, 21], we show that Theorem 2.1 can be used to control the bias and the variance of ergodic a”
Cutoff for non-negatively curved Markov chains (2021, background): “, [24, 41, 61] and the references therein), their application to cutoff seems new and promising.”
Measuring Sample Quality with Diffusions (2016, methodology): “The Stein factor bounds of Theorem 5 can also be used, in the manner of [62, 45, 38], to characterize the error of numerical discretizations of diffusions.”
Concentration inequalities for Markov chains by Marton couplings and spectral methods (2012, background): “pect to d, under π. Such inequalities are also proven in Ollivier (2010) and Ollivier (2009), with constants in the exponents depending on the Ricci curvature of the chain, and the typical step size. Joulin and Ollivier (2010) proves a concentration inequality for empirical averages of Lipschitz fun”