Archive for random walk Metropolis algorithm

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 »

proximal sampler

Posted in Books, pictures, R, Statistics, Travel, University life with tags , , , , , , , , , , , , on April 28, 2025 by xi'an

At the Columbia workshop last week, Andre Wibisono presented work related with a recent arXival on the exponentially fast convergence of both unadjusted Langevin and  proximal sampler algorithms under strong [definitely strong] log-concavity assumptions. The idea behind the proximal sampler is to target the demarginalised density

g(x,y) \propto \exp\{\log f(x) - ||x-y||^2/2\eta\}\quad\eta>0

by introducing an auxiliary Gaussian vector y, which preserves f(x) as the marginal distribution on the first component vector X. While the auxiliary Y is (obviously) conditionally Gaussian, the conditional of X is at least as challenging as simulating from f. Unless η is chosen small enough to regularize log g(x) into a strongly log-concave function, since

\log g(x,y) \le \log g(x^\star,y) -\beta||x-x^\star||^2

when x*=x*(y) is the maximiser of log g(x,y) (for a given value y) and β>0 is the appropriate log-concavity constant. This inequality means that an accept-reject can be implemented to simulate from the conditional of X given Y but it requires both the factor β and the derivation of x*(y), hence a pretty good understanding and a rather high regularity of the actual target f(x). Besides, the regularization term ||x-y||² means that y is approximately the previous value of the (sub)chain X, hence it creates a rappel force that slows down the exploration of the target.

Since the arXival does not contain numerical comparisons, I attempted one using the (2D) banana shaped distribution,

target=function(x,sig,B,mu)-x[1]^2/2/sig-(x[2]+B*x[1]^2-mu)^2/2

with μ=σ=B=10. Comparing with a vanilla random walk Metropolis with three potential scales, chosen randomly at each iteration. Since I did not want to check whether or not the target was log-concave (and derive the corresponding β), I used the Normal distribution centred at proposal x*(y) of a Metropolis step, again with several scales. The following is the representation of the samples (sienna for MCMC, navy blue for proximal with β=50, dark green for β=5), with a lesser rate of tail exploration for the proximal samplers. It is thus unclear to me the theoretical characterisations of the method translate into practical efficiency beyond the most regular cases.

1 Comment »

control variates [seminar]

Posted in pictures, Statistics, Travel, University life with tags , , , , , , , , , , , , , , on November 5, 2021 by xi'an

Today, Petros Dellaportas (whom I have know since the early days of MCMC, when we met in CIRM) gave a seminar at the Warwick algorithm seminar on control variates for MCMC, reminding me of his 2012 JRSS paper. Based on the Poisson equation and using a second control variate to stabilise the Monte Carlo approximation do the first control variate. The difference with usual control variates is finding a first approximate G(x)-q(y|x)G(Y) to F-πF. And the first Poisson equation is using α(x,y)q(y|x) rather than π. Then the second expands log α(x,y)q(y|x) to achieve a manageable term.

Abstract: We provide a general methodology to construct control variates for any discrete time random walk Metropolis and Metropolis-adjusted Langevin algorithm Markov chains that can achieve, in a post-processing manner and with a negligible additional computational cost, impressive variance reduction when compared to the standard MCMC ergodic averages. Our proposed estimators are based on an approximate solution of the Poisson equation for a multivariate Gaussian target densities of any dimension.

I wonder if there were a neural network version that would first build G from scratch and later optimise it towards solving the Poisson equation. As in this recent arXival I haven’t read (yet).

Leave a comment »