6
$\begingroup$

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.

$\endgroup$
2
+25
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ Do you have a reference for $\mathcal L(X_t) \to \exp(-h) dx$ at hand? $\endgroup$ – 0xbadf00d Dec 27 '18 at 11:40
  • $\begingroup$ In your equation for ${\rm d}\tilde V_t$, the $B_t$ is different from the previous $B_t$ isn't it? Actually it should be $\tilde B_t:=\alpha^{-1/2}B_{\alpha t}$ (which is a Brownian motion). $\endgroup$ – 0xbadf00d Dec 28 '18 at 12:11
  • $\begingroup$ And I don't get why $U_t = \tilde V_{\frac12 h(\ell) t}$. As you wrote before $U_t=V_{h(\ell)t}$. $\endgroup$ – 0xbadf00d Dec 28 '18 at 13:43
  • $\begingroup$ I'm still interested in an answer, especially for a reference for $\mathcal L(X_t) \to \exp(-h) dx$. $\endgroup$ – 0xbadf00d Jan 16 '19 at 11:19
  • $\begingroup$ @0xbadf00d, sorry for the delay. I have added some recent references. Hopefully, looking at what they cite you can find multiple references for that. $\endgroup$ – passerby51 Jan 17 '19 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.