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, and its properties were examined in detail by Gareth Roberts together with Richard Tweedie and Jeff Rosenthal. Many variations and refinements have been introduced since then, e.g. the manifold variant of Girolami and Calderhead. The method is equivalent to using the Hamiltonian Monte Carlo algorithm with only a single discrete time step.
Further details
Let denote a probability density function on, one from which it is desired to draw an ensemble of independent and identically distributed samples. We consider the overdamped Langevin Itô diffusion driven by the time derivative of a standard Brownian motion. In the limit as, this probability distribution of approaches a stationary distribution, which is also invariant under the diffusion, which we denote. It turns out that, in fact,. 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. We set and then recursively define an approximation to the true solution by where each is an independent draw from a multivariate normal distribution on with mean 0 and covariance matrixequal to the identity matrix. Note that is normally distributed with mean and covariance equal to times the identity matrix. In contrast to the Euler–Maruyama method for simulating the Langevin diffusion, which always updates according to the update rule MALA incorporates an additional step. We consider the above update rule as defining a proposal for a new state, This proposal is accepted or rejected according to the Metropolis-Hastings algorithm: set where is the transition probability density from to . Let be drawn from the continuous uniform distribution on the interval. If, then the proposal is accepted, and we set ; otherwise, the proposal is rejected, and we set. 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. Compared to naive Metropolis–Hastings, MALA has the advantage that it usually proposes moves into regions of higher probability, which are then more likely to be accepted. On the other hand, when is strongly anisotropic, it is necessary to take in order to properly capture the Langevin dynamics; the use of a positive-definite preconditioning matrix can help to alleviate this problem, by generating proposals according to so that has mean and covariance. In practical applications, the optimal acceptance rate for this algorithm is ; if it is discovered to be substantially different, should be modified accordingly.
