MALA

MALA

The Metropolis-Adjusted Langevin Algorithm (MALA) is a gradient-informed Metropolis-Hastings sampler whose proposal is a discretized step of Langevin dynamics toward higher log-density. Given the current state $x\in {\mathbb{R}}^d$ and step size $\sigma >0$, the proposal is
$y=x+\frac{1}{2}{\sigma }^2\nabla \log \pi (x)+\sigma z,z\sim \mathcal{N}(0,I_d).$
The proposal density
$Q(x,y)={\left(\frac{1}{\sqrt{2\pi }\sigma }\right)}^d\exp \left(-\frac{1}{2{\sigma }^2}\Vert y-x-\frac{1}{2}{\sigma }^2\nabla \log \pi (x){\Vert }^2\right)$
is not symmetric — $Q(x,y)\ne Q(y,x)$ because the drift depends on the current position — so the Hastings correction does not drop out. The acceptance ratio is the standard MH expression
$\alpha (x,y)=\min \left(1,\frac{\pi (y)Q(y,x)}{\pi (x)Q(x,y)}\right).$
The drift term $\frac{1}{2}{\sigma }^2\nabla \log \pi (x)$ pushes every proposal uphill in $\log \pi$ before the Metropolis correction, so MALA systematically proposes moves into higher-density regions. In high dimensions this allows a much larger step size $\sigma$ than random-walk Metropolis while maintaining a reasonable acceptance rate, often $0.5$–$0.6$ (theory suggests tuning toward $0.574$ for isotropic Gaussian targets).

Mechanical interpretation. MALA can be viewed as Newton’s second law with constant acceleration $\nabla \log \pi (x)$: starting at position $x$ with random velocity $z\sim \mathcal{N}(0,I_d)$ and accelerating uniformly in the direction of steepest ascent of $\log \pi$ for time $\sigma$ gives
$x(\sigma )=x+\sigma z+\frac{1}{2}{\sigma }^2\nabla \log \pi (x),$
which is exactly the MALA proposal. This contrasts with random-walk Metropolis (free-particle, no force) and HMC (position-dependent acceleration $\nabla \log \pi (x(t))$ updated continuously along the trajectory).

Cost per iteration. One MALA step requires one gradient evaluation $\nabla \log \pi$ at $x$, one Gaussian draw $z$, one evaluation of $Q$ and $\pi$ at the proposal, and one acceptance check. Each iteration is more expensive than random-walk Metropolis but the chain mixes dramatically faster on smooth targets, giving a better effective-sample-size-per-unit-time in almost every realistic setting.

Prerequisites

• 3.11.1 Metropolis-Hastings — MALA is an instance of MH with an asymmetric, gradient-informed proposal.
• 3.11 MCMC — detailed balance, ergodic theorem, acceptance-rate tuning.
• 5.4 Reversibility — the detailed-balance condition that MALA satisfies by construction.

Intuition

Random-walk Metropolis explores $\pi$ blindly: the proposal $y=x+\sigma z$ has no idea where the high-density regions are, so it frequently wanders into low-probability areas and gets rejected. In high dimensions this is crippling. MALA fixes it by using the gradient of the log-target as a compass. The proposal still contains a Gaussian random-walk component ($\sigma z$) to maintain irreducibility and diffusion-like exploration, but a deterministic drift ($\frac{1}{2}{\sigma }^2\nabla \log \pi (x)$) nudges every proposal toward higher $\pi$. Conceptually, MALA is noisy gradient ascent on $\log \pi$ — if it were pure gradient ascent the chain would converge to the MAP rather than sampling from $\pi$; the Gaussian noise keeps the chain exploring, and the Metropolis correction ensures that the stationary distribution is exactly $\pi$.

The central design tension is between the step size and the Metropolis correction. Small $\sigma$ keeps the proposal close to $x$, making the gradient information accurate locally and the acceptance rate high — but the chain then moves slowly. Large $\sigma$ takes big steps, so the linear gradient approximation of $\log \pi$ (used implicitly in the drift) breaks down and many proposals fall into regions of low probability, pushing the acceptance rate to zero. The optimal step size scales like $d^{-1/3}$ for MALA versus $d^{-1}$ for random-walk Metropolis, which is the quantitative reason MALA outperforms RWM in high dimensions.

Properties

(Asymmetric Proposal) The drift depends on $x$, so $Q(x,y)\ne Q(y,x)$, and the full MH acceptance formula is needed.

For random-walk Metropolis, symmetry $Q(x,y)=Q(y,x)$ collapses the acceptance probability to $\min (1,\pi (y)/\pi (x))$. For MALA the drift $\frac{1}{2}{\sigma }^2\nabla \log \pi (x)$ differs from $\frac{1}{2}{\sigma }^2\nabla \log \pi (y)$, so both the forward and reverse proposal densities must be computed explicitly. The acceptance ratio becomes
$\frac{\pi (y)Q(y,x)}{\pi (x)Q(x,y)}=\exp (\log \pi (y)-\log \pi (x)-\frac{1}{2{\sigma }^2}\Vert x-y-\frac{1}{2}{\sigma }^2\nabla \log \pi (y){\Vert }^2+\frac{1}{2{\sigma }^2}\Vert y-x-\frac{1}{2}{\sigma }^2\nabla \log \pi (x){\Vert }^2).$

(Detailed Balance) The Metropolis correction makes MALA satisfy detailed balance exactly, not just approximately.

The drift was derived in the first place by requiring $\pi (x)Q(x,y)\approx \pi (y)Q(y,x)$ for $y$ close to $x$ (see Derivation), so without the Metropolis correction MALA would sample from a distribution close to — but not exactly — $\pi$ as $\sigma \to 0$. Adding the MH accept/reject step restores detailed balance exactly for any $\sigma >0$: $\pi (x)P(x,y)=\pi (y)P(y,x)$ where $P$ is the MALA transition kernel. This is the key difference between MALA and the unadjusted Langevin algorithm (ULA), which runs the same proposal without Metropolis correction and samples from a $\sigma$-biased distribution rather than $\pi$ itself.

(Optimal Step Size) For high-dimensional product targets, the optimal acceptance rate is approximately $0.574$ and $\sigma \propto d^{-1/6}$.

Roberts and Rosenthal (1998) showed that for i.i.d. target $\pi (\theta )={\prod }_{i=1}^{d}f({\theta }_i)$, the MALA chain with step size $\sigma =\ell \cdot d^{-1/6}$ converges (after rescaling) to a Langevin diffusion as $d\to \infty$. The expected squared jumping distance is maximized when the acceptance rate tends to $0.574$, giving a practical tuning target. This is markedly better than random-walk Metropolis, whose optimal step size scales like $d^{-1/2}$ with acceptance rate $0.234$: in $d$ dimensions, MALA takes steps $d^{1/3}$ times larger than RWM while accepting at a similar rate.

(Requires Gradients) MALA is inapplicable unless $\nabla \log \pi (x)$ can be computed efficiently.

This is the price paid for gradient-informed exploration. For Bayesian models where the target is the posterior $\pi (\theta \mid \text{data})\propto \text{prior}(\theta )\cdot \text{likelihood}(\theta \mid \text{data})$, the gradient is $\nabla \log \pi =\nabla \log \text{prior}+\nabla \log \text{likelihood}$, and both pieces are typically available analytically or via automatic differentiation. For models with intractable likelihoods or discrete parameters, gradients do not exist and MALA cannot be used — random-walk Metropolis or bespoke samplers are needed instead.

(Preconditioning) A mass-matrix $M$ replaces $I_d$ to match the local curvature of $\pi$.

The isotropic Gaussian noise in the basic MALA proposal is the wrong shape when the coordinates of $\theta$ live on very different scales or are strongly correlated under $\pi$. A preconditioned MALA proposal is
$y=x+\frac{1}{2}{\sigma }^2{M}^{-1}\nabla \log \pi (x)+\sigma M^{-1/2}z,$
where $M$ is a positive-definite mass matrix (typically the posterior covariance estimated from a preliminary run or from a Laplace approximation at the MAP). This rescales the proposal to match the local geometry: equal numbers of acceptable jumps in every direction. Without preconditioning, MALA on ill-scaled posteriors behaves similarly to unpreconditioned gradient descent — slow along narrow valleys, oscillatory across steep ones.

(Relation to Langevin SDE) The MALA proposal is the Euler-Maruyama discretization of the overdamped Langevin SDE.

The stochastic differential equation
$d{X}_t=\frac{1}{2}\nabla \log \pi (X_t)dt+d{B}_t,$
where $B_t$ is standard Brownian motion, has $\pi$ as its unique stationary distribution (Fokker-Planck argument). Discretizing with Euler-Maruyama at step size ${\sigma }^2$ gives exactly the proposal $y=x+\frac{1}{2}{\sigma }^2\nabla \log \pi (x)+\sigma z$. This continuous-time perspective is why MALA is often called “Langevin Monte Carlo” and why its theory borrows heavily from SDE analysis (exponential ergodicity, contraction rates, coupling arguments).

(MALA vs. RWM in High Dimensions) MALA scales much better with dimension $d$ for smooth targets.

For random-walk Metropolis, the step size must shrink as $\sigma \propto d^{-1/2}$ to keep acceptance away from zero, and the number of iterations to reach stationarity scales as $d$. For MALA, $\sigma \propto d^{-1/6}$ and the mixing time scales as $d^{1/3}$. For HMC (the next step up in sophistication), $\sigma \propto d^{-1/4}$ and mixing scales as $d^{1/4}$. The practical consequence: as $d$ grows from tens to hundreds to thousands, RWM becomes unusable while MALA remains workable, and HMC is workable even beyond.

(Failure Modes) MALA fails when $\pi$ has heavy tails or the gradient is expensive.

For targets with sub-Gaussian tails, the drift $\frac{1}{2}{\sigma }^2\nabla \log \pi (x)$ can be very large in the tails, leading to proposals that overshoot into the opposite tail and are rejected. Chains can get stuck in tail regions where the gradient points back toward the mode but the $\sigma z$ noise is too small to escape. Heavy-tailed targets (e.g., Cauchy) require truncated or tamed variants of the drift. Separately, if each gradient evaluation is expensive (large dataset, implicit model), the per-iteration cost may offset the per-iteration improvement in mixing — stochastic-gradient MALA (SGLD, SGLD-type) addresses this by subsampling the data at each step.

Examples

MALA on a 2D Gaussian target

Let $\pi (x)=\mathcal{N}(x;0,\Sigma )$ with $\Sigma =\left(\begin{array}{cc}1& 0.9\\ 0.9& 1\end{array}\right)$, a highly correlated bivariate Gaussian.

The log-density and its gradient are
$\log \pi (x)=-\frac{1}{2}{x}^{\top }{\Sigma }^{-1}x+\text{const},\nabla \log \pi (x)=-{\Sigma }^{-1}x.$
The MALA proposal with step size $\sigma$ is
$y=x-\frac{1}{2}{\sigma }^2{\Sigma }^{-1}x+\sigma z=(I-\frac{1}{2}{\sigma }^2{\Sigma }^{-1})x+\sigma z.$

For this target, random-walk Metropolis with $\sigma =0.5$ achieves an effective sample size of about $10\%$ of the nominal $N$, because the strong correlation forces the chain to wind slowly along the ridge. MALA with $\sigma =0.5$ instead uses the gradient $-{\Sigma }^{-1}x$ to drift along the ridge itself, achieving an effective sample size closer to $60\%$. With preconditioning $M=\Sigma$ the chain becomes equivalent to MALA on a standard Gaussian and mixes even faster.

Comparison on a Poisson regression posterior

For the Poisson regression posterior $\pi (\beta \mid \text{data})\propto \exp ({\sum }_i(y_i{x}_i^{\top }\beta -e^{x_i^{\top }\beta }))$, the log-target and gradient are
$\log \pi (\beta )={\sum }_{i=1}^n(y_i{x}_i^{\top }\beta -e^{x_i^{\top }\beta })+\text{const},\nabla \log \pi (\beta )={\sum }_{i=1}^n(y_i-e^{x_i^{\top }\beta })x_i.$
Each MALA step computes one gradient vector. With $n=10,000$ observations and $p=20$ covariates, this costs $\mathcal{O}(np)=2\cdot 10^5$ operations — negligible. Running $10,000$ MALA iterations with a step size tuned to $55\%$ acceptance gives roughly $2000$–$3000$ effectively independent samples, compared to $\sim 500$ for random-walk Metropolis with Laplace-approximation covariance, on the same compute budget.

Why the drift term appears at exactly $\frac{1}{2}{\sigma }^2$

Suppose we add a generic drift $g(x)$ to the proposal: $y=x+g(x)+\sigma z$. For this to satisfy detailed balance approximately when $y$ is close to $x$, we need
$\log \pi (y)-\log \pi (x)\approx \log Q(x,y)-\log Q(y,x).$
Expanding $\log \pi (y)-\log \pi (x)\approx ⟨y-x,\nabla \log \pi (x)⟩$ via Taylor and computing $\log Q(x,y)-\log Q(y,x)=\frac{2}{{\sigma }^2}⟨y-x,g(x)⟩$ via direct algebra (see Derivation), balance requires $g(x)=\frac{1}{2}{\sigma }^2\nabla \log \pi (x)$. The coefficient $\frac{1}{2}$ is not a free parameter — any other choice would break detailed balance to leading order.

Derivation

Goal. Derive the MALA drift $g(x)=\frac{{\sigma }^2}{2}\nabla \log \pi (x)$ from the requirement that detailed balance hold approximately to leading order in $\sigma$, then check that the Metropolis correction restores detailed balance exactly.

Consider a proposal of the form $y=x+g(x)+\sigma z$ with $z\sim \mathcal{N}(0,I_d)$, where $g:{\mathbb{R}}^d\to {\mathbb{R}}^d$ is a drift to be determined. The forward proposal density is
$Q(x,y)={\left(\frac{1}{\sqrt{2\pi }\sigma }\right)}^d\exp \left(-\frac{1}{2{\sigma }^2}\Vert y-x-g(x){\Vert }^2\right).$
Compute the log-ratio:
$\log \frac{Q(y,x)}{Q(x,y)}=-\frac{1}{2{\sigma }^2}(\Vert x-y-g(y){\Vert }^2-\Vert y-x-g(x){\Vert }^2).$
Expanding the squared norms and cancelling $\Vert y-x{\Vert }^2$ terms,
$\log \frac{Q(y,x)}{Q(x,y)}=-\frac{1}{{\sigma }^2}⟨y-x,g(x)+g(y)⟩+\frac{1}{2{\sigma }^2}(\Vert g(x){\Vert }^2-\Vert g(y){\Vert }^2).$

Combine with the target ratio:
$\log \frac{\pi (y)Q(y,x)}{\pi (x)Q(x,y)}=(\log \pi (y)-\log \pi (x))+\log \frac{Q(y,x)}{Q(x,y)}.$

Leading-order expansion. When $y$ is close to $x$ (small $\sigma$, so $y-x=g(x)+\sigma z$ is of size $\mathcal{O}(\sigma )$), Taylor-expand:
$\log \pi (y)-\log \pi (x)\approx ⟨y-x,\nabla \log \pi (x)⟩.$
For the $Q$ ratio, the dominant term is $-\frac{1}{{\sigma }^2}⟨y-x,g(x)+g(y)⟩\approx -\frac{2}{{\sigma }^2}⟨y-x,g(x)⟩$ since $g(y)\approx g(x)$ to leading order; the $\Vert g{\Vert }^2$ difference is $\mathcal{O}(\Vert y-x\Vert )$ and drops.

Summing,
$\log \frac{\pi (y)Q(y,x)}{\pi (x)Q(x,y)}\approx ⟨y-x,\nabla \log \pi (x)⟩-\frac{2}{{\sigma }^2}⟨y-x,g(x)⟩=⟨y-x,\nabla \log \pi (x)-\frac{2g(x)}{{\sigma }^2}⟩.$

For this to be $o(\Vert y-x\Vert )$ — the condition for approximate detailed balance — the bracketed vector must vanish:
$g(x)=\frac{{\sigma }^2}{2}\nabla \log \pi (x).$
This is the MALA drift. Plugging back into the proposal gives
$y=x+\frac{1}{2}{\sigma }^2\nabla \log \pi (x)+\sigma z.$

Exact detailed balance via Metropolis correction. The drift is derived for approximate balance; the MH acceptance step
$\alpha (x,y)=\min \left(1,\frac{\pi (y)Q(y,x)}{\pi (x)Q(x,y)}\right)$
repairs the remaining imbalance exactly. Computing $\pi (x)P(x,y)=\pi (x)Q(x,y)\alpha (x,y)=\min (\pi (x)Q(x,y),\pi (y)Q(y,x))$, which is symmetric in $(x,y)$, gives $\pi (x)P(x,y)=\pi (y)P(y,x)$ as required. The construction is the general MH argument; see 3.11.1 Metropolis-Hastings for details.

Why the expansion works. When $\sigma$ is small the Taylor expansion of $\log \pi$ is accurate, and the leading-order approximate detailed balance gives an acceptance probability $\alpha \approx 1$. As $\sigma$ grows, the linear expansion degrades and $\alpha$ drops; the optimal $\sigma$ (corresponding to $\approx 0.574$ acceptance in high dimensions) is the one that balances step size against acceptance rate.

See Also

• 3.11.1 Metropolis-Hastings — MALA is an asymmetric-proposal instance of MH.
• 3.11.4 Hamiltonian Monte Carlo — next step up: position-dependent acceleration replaces MALA’s constant acceleration.
• 3.11.2 Gibbs Sampling — alternative MCMC route when full conditionals are tractable.
• 3.11 MCMC — parent index: acceptance-rate tuning, trace plots, effective sample size.
• 4.6 Brownian Motion — MALA is the Euler-Maruyama discretization of a Brownian-driven SDE.
• 3.9 Laplace Approximation — standard source of preconditioning matrix $M$.