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

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

• 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. – Stan Tendijck Mar 4 '19 at 15:23
• @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 :) – Stan Tendijck Mar 4 '19 at 19:29
• 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. – Xi'an Mar 5 '19 at 5:34

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.

• Thank you a lot, I will take a look at the suggested papers! – Stan Tendijck Mar 10 '19 at 21:16

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.