Metropolis-adjusted Langevin algorithm

MALA generates proposals by simulating a discretized Langevin diffusion, using the gradient of the log-target density to guide moves toward high-probability regions. Specifically, given current state x, a proposal y is drawn from a Gaussian with mean x + (ε²/2)∇log π(x) and covariance ε²I, where ε is a step size. The proposal is then accepted or rejected with probability min(1, π(y)q(x|y)/π(x)q(y|x)), ensuring the chain converges to the target π. This Metropolis step corrects the bias introduced by the Euler–Maruyama discretization, making MALA an exact sampler.

Roberts and Rosenthal (1998) showed that for smooth target densities, MALA's computational complexity scales as O(d^{1/3}) per effective sample, compared to O(d) for random-walk Metropolis, making it more efficient in high dimensions. The optimal acceptance rate in the high-dimensional limit is 0.574, derived from diffusion approximations. For non-smooth or heavy-tailed targets, MALA can behave poorly, and adaptive step-size tuning is often required. The algorithm is a special case of Hamiltonian Monte Carlo with a single leapfrog step, linking it to broader gradient-based MCMC methods.

MALA is used in Bayesian inference for posterior sampling, particularly in spatial statistics, image analysis, and computational physics. Variants include preconditioned MALA (pMALA) which uses a mass matrix to improve conditioning, and Riemannian manifold MALA that adapts to local geometry. In machine learning, MALA underpins stochastic gradient MCMC methods like stochastic gradient Langevin dynamics (SGLD), though the latter omits the Metropolis step for speed. MALA also appears in ensemble methods and in sampling from Gibbs random fields.

MALA's origins trace to the 1980s 'Langevin algorithm' of Grenander and Miller, but the Metropolis adjustment was formalized by Besag in 1994 and later analyzed by Roberts and Tweedie. A notable edge case: for targets with discontinuous gradients, MALA can have poor acceptance rates, and a 'dynamically adjusted' step size is sometimes used. In rare-event simulation, MALA has been adapted to sample from conditional distributions. The algorithm also appears in the 'MALA-within-Gibbs' hybrid, where only some coordinates are updated via Langevin proposals. Despite its name, MALA is not a single algorithm but a family of methods with varying proposal covariances.

Langevin diffusion

A stochastic differential equation whose stationary distribution is the target distribution.

Metropolis–Hastings

A general MCMC acceptance-rejection framework.

Euler–Maruyama

A numerical method for approximating stochastic differential equations.