Archive for Annals of Applied Probability

explicit convergence bounds for Metropolis

Posted in Books, Statistics, University life with tags , , , , , , , , on March 2, 2026 by xi'an

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.

Leave a comment »