Optimal scaling of the Random Walk Metroplis-Hastings algorithm and the speed measure of the limiting diffusion

Question

Let

• $d\in\mathbb N$ with $d>1$
• $\ell>0$
• $\sigma_d^2:=\frac{\ell^2}{d-1}$
• $f\in C^2(\mathbb R)$ be positive with $$\int f(x)\:{\rm d}x=1$$ and $g:=\ln f$
• $Q_d$ be a Markov kernel on $(\mathbb R^d,\mathcal B(\mathbb R^d))$ with $$Q_d(x,\;\cdot\;)=\mathcal N_d(x,\sigma_dI_d)\;\;\;\text{for all }x\in\mathbb R^d,$$ where $I_d$ denotes the $d$-dimensional unit matrix

Now, let $$\pi_d(x):=\prod_{i=1}^df(x_i)\;\;\;\text{for }x\in\mathbb R^d$$ and $\left(X^{(d)}_n\right)_{n\in\mathbb N_0}$ denote the Markov chain generated by the Metropolis-Hastings algorithm with proposal kernel $Q_d$ and target density $\pi_d$ (with respect to the $d$-dimensional Lebesuge measure $\lambda^d$). Moreover, let $$U^{(d)}_t:=\left(X^{(d)}_{\lfloor dt\rfloor}\right)_1\;\;\;\text{for }t\ge0.$$ In the paper Weak convergence and optimal scaling of random walk Metropolis algorithms, the authors show (assuming that $g$ is Lipschitz continuous and satisfies some moment conditions) that $U^{(d)}$ converges (in the Skorohod topology) as $d\to\infty$ to the solution $U$ of $${\rm d}U_t=\frac{h(\ell)}2g'(U_t){\rm d}t+\sqrt{h(\ell)}{\rm d}W_t,$$ where $W$ is a standard Brownian motion, with $U_0\sim f\lambda^1$.

Now, they conclude that the "optimal choice" for $\ell$ is obtained by maximizing $$h(\ell):=2\ell^2\Phi\left(-\frac{\ell\sqrt I}2\right),$$ where $\Phi$ denotes the cumulative distribution function of the standard normal distribution and $$I:=\int\left|g'\right|^2\:{\rm d}(f\lambda^1)<\infty.$$ Why? In which sense (e.g. total variation distance or variance) does this optimize the Metropolis-Hastings algorithm?

I've read that $h(\ell)$ is called the "speed function/measure" of the diffusion $U$ ... Would be very happy about a reference for that topic.

Answer 1

The Langevin diffusion is a process $(X_t)_{t \ge 0}$ satisfying the SDE: \begin{align*} d X_t = -\nabla h(X_t) + \sqrt{2} dW_t \end{align*}
where $(W_t)_{t \ge 0}$ is the standard Brownian motion in $\mathbb R^d$. Under mild conditions on $h$, the above has a unique solution which is a Markov process. Also, the distribution of $X_t$ can be shown to converge to to a distribution with density $\pi(x) \propto \exp(-h(x))$ as $t \to \infty$. I am going to write this as $\mathcal L(X_t) \to \exp(-h) dx$

In the paper you consider, they have the 1-d dynamic: \begin{align*} d V_t = d B_t + \frac{f'(V_t)}{2 f(V_t)} dt = d B_t + \frac12 g'(V_t) dt \end{align*} where $g = \log f$. Let us define $\tilde V_t = V_{\alpha t}$. Then, \begin{align*} d \tilde V_t &= \alpha^{1/2} \, d B_{t} + \frac\alpha 2 g'(\tilde V_{t}) dt \end{align*} (This is using the fact that $(B_{\alpha t})$ has the same distribution as $(\sqrt{\alpha} B_t.)$ Taking $\alpha = 2$, we have that $\tilde V_t$ satisfies the standard Langevin dynamics with $h = -g$, hence $$\mathcal L(\tilde V_t) \to \exp(g) dx = f dx \quad \text{as} \quad t \to \infty.$$

Now, as they argue in the paper $U_t = V_{h(\ell) t}$. This is easy to see by the same argument as above: basically setting $\alpha = h(\ell)$ shows that $U_t$ satisfies the desired SDE.

In short $U_t = \tilde V_{\frac12 h(\ell) t}$ and $\tilde V_t$ is converging in distribution to the desired law. So $\frac12 h(\ell)$ looks like a step size. The larger it is, the faster you move along the process $\tilde V_t$ for a unit step in time (say $\Delta t = 1)$.

EDIT: There is a lot of interesting recent activity on the convergence of Langevin dynamics and MH algorithm. I will try to cite them once I get a chance.

EDIT2: Some recent developments:

• Reflection couplings and contraction rates for diffusions
• Theoretical guarantees for approximate sampling from smooth and log-concave densities
• Log-concave sampling: Metropolis-Hastings algorithms are fast!
• Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting