3
$\begingroup$

Notation: $\pi(x)$ is the target density. $(x_n)_{n=1}^{N}$ is the chain generated by the MCMC method.

At the moment, I am doing some research in MCMC methods. Before, I was planning to dive into the recently developed non-reversible MCMC methods, I revisited some 'simple' ones and I came across MALA (Metropolis-Adjusted Langevin Algorithm).

The algorithm is generally the same as Metropolis-Hastings but instead of basing the proposal on the previous value, $x_n$, it bases the proposal on $x_n + h\cdot \nabla\log\pi(x_n)$ for a certain step-size $h$. However, in Metropolis-Hastings algorithm, they do not specify the family of the proposal density, it can generally be anything (usually centred around $x_n$ though). In the MALA algorithm, they actually do specify the family of the proposal density, namely they fix it to be Gaussian where the variance depends on the step-size $h$.

My question is: Why do we make the Gaussian assumption? Or maybe a bit more instructive, why can't we use any distribution with mean $x_n + h\cdot\nabla\log\pi(x_n)$ (where the variance may be fixed as function of $h$) as proposal for the new value $x_{n+1}$?

$\endgroup$
  • $\begingroup$ So, you are saying that it is mere a universally accepted convenience than a necessity. I am wondering though if convergence/stationarity results still hold once you take a general distribution/what are the conditions on such a general distribution for the stationarity/convergence results to hold. $\endgroup$ – Stan Tendijck Mar 4 at 15:23
  • $\begingroup$ @Xi'an can you provide me with a source where they examine MALA with a noise distribution without any constraint, that would be extremely helpful for me :) $\endgroup$ – Stan Tendijck Mar 4 at 19:29
  • 1
    $\begingroup$ I do not know of a paper that specifically analyses a non-standard MALA algorithm but generic MCMC convergence results (Tierney, 1994) apply to this case. $\endgroup$ – Xi'an Mar 5 at 5:34
2
$\begingroup$

I will elaborate on Xi'an's response.

Metropolis-Adjusted Langevin Algorithm, as its name implies, is based on the Langevin diffusion that is represented by the following stochastic differential equation (SDE):

$ d X_t = - \nabla f(X_t) dt + \sqrt{2} d B_t $,

where $B_t$ is the standard Brownian motion and the target density $\pi(x) = \exp(-f(x)) / Z$ for some $Z>0$. One can show that, under arguably mild assumptions, the solution process to this SDE, i.e. $(X_t)_{t \geq 0}$ which solves the above equation is a Markov process and admits a unique stationary distribution, which is indeed $\pi$. Under some more assumptions, we can show that $(X_t)_t$ is ergodic with $\pi$.

This means that, if we could exactly simulate the process $(X_t)_t$, the distribution of $X_t$ would converge to $\pi$, therefore, we could use the trajectories for approximating expectations with respect to $\pi$ for instance. But the issue is that we cannot simulate this process exactly (in general) since it's a continuous-time process. Then, the idea in MALA is to discretize this process by using a first-order scheme (namely the Euler-Maruyama discretization), which gives the following recursion:

$X_{n+1} = X_n - h \nabla f(X_n) + \sqrt{2h} N_{n+1}$,

where $N_{n}$ is a standard Gaussian random variable. In other words, we can view $X_{n+1}$ as a random variable that is drawn from the following distribution:

$\mathcal{N}(X_n - h \nabla f(X_n), 2h \mathbf{I})$,

where $\mathbf{I}$ denotes the identity matrix of appropriate size. However, due to discretization, this process does not target $\pi$ anymore, therefore a Metropolis-Hastings acceptance-rejection step is appended to this procedure to remove the discretization error (hence the name Metropolis 'adjusted'). This is the reason why a Gaussian proposal is used in MALA. More information can be found in the following paper, which is the standard reference for MALA:

Roberts, G. O., & Tweedie, R. L. (1996). Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, 2(4), 341-363.

On the other hand, you are not restricted to Gaussian proposals. It has been shown that heavy-tailed proposals can have their own benefits, such as

JARNER, S., & ROBERTS, G. (2007). Convergence of Heavy-tailed Monte Carlo Markov Chain Algorithms. Scandinavian Journal of Statistics, 34(4), 781-815.

Şimsekli, U. (2017, August). Fractional Langevin Monte Carlo: Exploring Lévy driven stochastic differential equations for Markov Chain Monte Carlo. In Proceedings of the 34th International Conference on Machine Learning-Volume 70 (pp. 3200-3209).

The latter doesn't have a Metropolis correction step, but still related.

$\endgroup$
  • $\begingroup$ Thank you a lot, I will take a look at the suggested papers! $\endgroup$ – Stan Tendijck Mar 10 at 21:16
2
$\begingroup$

There is no theoretical constraint in using a Gaussian random noise when looking at the discrete-time version directly, since the Metropolis-Hastings correction validates its stationary distribution as $\pi(\cdot)$ in (alnost) any case but it feels natural to use a Gaussian noise given that this is also a (Euler) time-discretisation version of the Langevin diffusion, which relies on a Brownian motion (i.e., continuous time Gaussian) random element. Ergodicity and hence convergence only requires (Tierney, 1994) the Metropolis-Hastings kernel to be irreducible.

$\endgroup$

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.