In computational statistics, the Metropolis-adjusted Langevin algorithm (MALA) or Langevin Monte Carlo (LMC) is a Markov chain Monte Carlo (MCMC) method for obtaining random samples – sequences of random observations – from a probability distribution for which direct sampling is difficult. As the name suggests, MALA uses a combination of two mechanisms to generate the states of a random walk that has the target probability distribution as an invariant measure:
Informally, the Langevin dynamics drive the random walk towards regions of high probability in the manner of a gradient flow, while the Metropolis–Hastings accept/reject mechanism improves the mixing and convergence properties of this random walk. MALA was originally proposed by Julian Besag in 1994,[1] (although the method Smart Monte Carlo was already introduced in 1978 [2]) and its properties were examined in detail by Gareth Roberts together with Richard Tweedie[3] and Jeff Rosenthal.[4] Many variations and refinements have been introduced since then, e.g. the manifold variant of Girolami and Calderhead (2011).[5] The method is equivalent to using the Hamiltonian Monte Carlo (hybrid Monte Carlo) algorithm with only a single discrete time step.
Let
\pi
Rd
X |
=\nablalog\pi(X)+\sqrt{2}
W |
W
X |
=
1 | |
2 |
\nablalog\pi(X)+
W |
,
which generates the same dynamics.) In the limit as
t\toinfty
\rho(t)
X(t)
\rhoinfty
\rhoinfty=\pi
Approximate sample paths of the Langevin diffusion can be generated by many discrete-time methods. One of the simplest is the Euler–Maruyama method with a fixed time step
\tau>0
X0:=x0
Xk
X(k\tau)
Xk:=Xk+\tau\nablalog\pi(Xk)+\sqrt{2\tau}\xik,
where each
\xik
Rd
d x d
Xk
Xk+\tau\nablalog\pi(Xk)
2\tau
d x d
In contrast to the Euler–Maruyama method for simulating the Langevin diffusion, which always updates
Xk
Xk:=Xk+\tau\nablalog\pi(Xk)+\sqrt{2\tau}\xik,
MALA incorporates an additional step. We consider the above update rule as defining a proposal
\tilde{X}k
\tilde{X}k:=Xk+\tau\nablalog\pi(Xk)+\sqrt{2\tau}\xik.
This proposal is accepted or rejected according to the Metropolis-Hastings algorithm: set
\alpha:=min\left\{1,
\pi(\tilde{X | |
k |
)q(Xk\mid\tilde{X}k)}{\pi({X}k)q(\tilde{X}k\midXk)}\right\},
where
q(x'\midx)\propto\exp\left(-
1 | |
4\tau |
\|x'-x-\tau\nablalog\pi(x)
2 | |
\| | |
2 |
\right)
is the transition probability density from
x
x'
q(x'\midx) ≠ q(x\midx')
u
[0,1]
u\leq\alpha
Xk:=\tilde{X}k
Xk:=Xk
The combined dynamics of the Langevin diffusion and the Metropolis–Hastings algorithm satisfy the detailed balance conditions necessary for the existence of a unique, invariant, stationary distribution
\rhoinfty=\pi
\pi
\pi
0<\tau\ll1
A\inRd
\tilde{X}k:=Xk+\tauA\nablalog\pi(Xk)+\sqrt{2\tauA}\xik,
\tilde{X}k
Xk+\tauA\nablalog\pi(Xk)
2\tauA
For limited classes of target distributions, the optimal acceptance rate for this algorithm can be shown to be
0.574
\tau