Why is the proposal in the MALA algorithm always normally distributed?

Question

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}$?

Answer 1

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.

Answer 2

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 (almost) 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.