explicit convergence bounds for Metropolis

$C\,L\, d\,\sigma^{2}\, e^{-2\, L\, d\,\sigma^{2}}\,\frac{m}{L}\,\frac{1}{d}\leqslant\gamma_{P}\leqslant\min\left\{ \frac{1}{2}\, L\,\sigma^{2},\left(1+m\,\sigma^{2}\right)^{-d/2}\right\}$

Last week, our MCMC reading group in PariSanté started reading Explicit convergence bounds for Metropolis Markov chains by my friends Christophe Andrieu, Anthony Lee, Sam Power, and Andi Wang (University of Warwick), recently published in the Annals of Applied Probability. The paper is centred on the bound above. Which may sound cryptic but gives a non-asymptotic explicit bound on the spectral gap γ, when the potential of the target is L-smooth, m-strongly convex and twice continuously differentiable, in dimension d, with a proposal being the Gaussian random walk with scale σ. With C = 1.972 10⁻⁴. if “possibly a few orders of magnitude larger”. This characterisation of the spectral gap leads to a sharper identification of d⁻¹ as the proper rate for σ². Other consequences are finding the order of the number of simulations to reach a χ² distance of ε,

$e^{2\,\varsigma}\,\varsigma\,\kappa\, d\,\left\{ \log d+\log\kappa-\log\varepsilon\right\}$

when κ is the condition number L/m and

$\sigma^2=\varsigma\, L^{-1}\, d^{-1}$

And a bound on the ergodic averages

${\rm var} (Pf )\leqslant10141\,\varsigma\,e^{2\,\varsigma}\,\kappa\, d\,\left\Vert f\right\Vert _{2}^{2}$

The technicity of the proof is quite involved, with a special kind of coupling, to the point the authors provide a roadmap, as reproduced left.

This entry was posted on March 2, 2026 at 12:26 am and is filed under Books, Statistics, University life with tags Annals of Applied Probability, coupling, isoperimetric inequalities, optimal scaling, random walk Metropolis algorithm, roadmap, spectral gap, University of Bristol, University of Warwick. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Xi'an's Og