Metropolis-Hastings Algorithm Variants

The standard Metropolis-Hastings (MH) algorithm provides a general framework for sampling from a target distribution, typically the posterior $p(\theta | D)$, when we can evaluate a function proportional to it (like the product of the likelihood and prior, $p(D|\theta)p(\theta)$). The core idea involves proposing a new state $\theta'$ from a proposal distribution $q(\theta' | \theta^{(t)})$ and accepting it with probability:

$$\alpha(\theta', \theta^{(t)}) = \min \left( 1, \frac{p(\theta' | D) q(\theta^{(t)} | \theta')}{p(\theta^{(t)} | D) q(\theta' | \theta^{(t)})} \right)$$

If accepted, $\theta^{(t+1)} = \theta'$. Otherwise, $\theta^{(t+1)} = \theta^{(t)}$. While powerful, the efficiency and effectiveness of the basic MH algorithm heavily depend on the choice of the proposal distribution $q$. This has led to several variants designed to improve performance in different scenarios.

Random Walk Metropolis (RWM)

Perhaps the simplest and most common variant is the Random Walk Metropolis algorithm. It uses a symmetric proposal distribution, meaning the probability of proposing $\theta'$ starting from $\theta$ is the same as proposing $\theta$ starting from $\theta'$. Formally, $q(\theta' | \theta) = q(\theta | \theta')$.

A typical choice is a Gaussian centered at the current state:

$$\theta' \sim \mathcal{N}(\theta^{(t)}, \Sigma)$$

where $\Sigma$ is a covariance matrix, often diagonal, e.g., $\sigma^2 I$. Because the proposal is symmetric, the proposal terms cancel out in the acceptance ratio:

$$q(\theta^{(t)} | \theta') = q(\theta' | \theta^{(t)})$$

This simplifies the acceptance probability to:

$$\alpha(\theta', \theta^{(t)}) = \min \left( 1, \frac{p(\theta' | D)}{p(\theta^{(t)} | D)} \right)$$

This is the original Metropolis algorithm (before the Hastings generalization).

Pros:

• Easy to implement.
• Requires no complex tuning at the proposal scale (e.g., $\sigma^2$).

Cons:

• Can be inefficient if the target distribution has complex correlations or varying scales across dimensions. The random walk behavior can lead to slow exploration of the parameter space.
• Performance is highly sensitive to the choice of proposal scale ($\sigma^2$ or $\Sigma$).

Tuning the Proposal Scale: Choosing the right scale for the random walk is important.

• Too small: Most proposals will be accepted, but the chain moves very slowly and moves through the space inefficiently, resulting in high autocorrelation between samples.
• Too large: Many proposals will land in regions of low probability and be rejected. The chain gets stuck, again leading to poor mixing.

An optimal acceptance rate is often empirically found to be around 0.234 for high-dimensional problems, or around 0.44 for one-dimensional problems, though this is a guideline, not a strict rule. Tuning often involves running pilot simulations and adjusting the proposal scale to achieve a reasonable acceptance rate.

Illustration of Random Walk Metropolis paths. Small steps lead to slow exploration, large steps lead to frequent rejections (staying in the same place, indicated by overlapping markers), while a well-tuned step size balances acceptance and movement.

Independent Metropolis-Hastings

In this variant, the proposed state $\theta'$ is drawn from a distribution $q(\theta')$ that does not depend on the current state $\theta^{(t)}$.

$$\theta' \sim q(\theta')$$

This means $q(\theta' | \theta^{(t)}) = q(\theta')$. The acceptance probability uses the full Hastings ratio because the proposal is generally not symmetric:

$$\alpha(\theta', \theta^{(t)}) = \min \left( 1, \frac{p(\theta' | D) q(\theta^{(t)})}{p(\theta^{(t)} | D) q(\theta')} \right)$$

Requirements: For this to work well, the proposal distribution $q(\theta')$ should ideally be a good approximation of the target posterior $p(\theta | D)$. Common choices include a multivariate Gaussian or Student's t-distribution fitted to the posterior mode (found via optimization) or based on an initial approximation (like a Laplace approximation).

Pros:

• If $q(\theta')$ is a good approximation of $p(\theta | D)$, the sampler can make large jumps across the parameter space, potentially leading to much faster mixing than RWM.
• Can be effective if a reasonable approximation of the posterior is available.

Cons:

• Finding a good proposal distribution $q(\theta')$ can be challenging.
• If $q(\theta')$ is a poor approximation, especially if its tails are lighter than the target posterior $p(\theta | D)$, the sampler may rarely accept proposals in important regions of the state space, leading to very poor performance. The requirement $p(\theta|D) > 0 \implies q(\theta) > 0$ must hold.
• Acceptance rates can be very low if $q$ is dissimilar to $p$.

Metropolis-Adjusted Langevin Algorithm (MALA)

MALA incorporates gradient information from the target distribution to propose moves more intelligently, pushing the samples towards regions of higher probability. This is particularly useful in high-dimensional spaces where random walks are inefficient.

The proposal mechanism is based on Langevin dynamics, which involves a drift term based on the gradient of the log-posterior and a random noise term. A discrete-time approximation leads to the proposal:

$$\theta' \sim \mathcal{N}\left( \theta^{(t)} + \frac{\epsilon^2}{2} \nabla \log p(\theta^{(t)} | D), \epsilon^2 I \right)$$

Here, $\epsilon$ is a step size parameter, and $\nabla \log p(\theta | D)$ is the gradient of the log target density (log-likelihood + log-prior). This proposal pushes $\theta'$ "uphill" towards higher density regions.

Because the proposal depends on the gradient at the current point $\theta^{(t)}$, it is not symmetric. The proposal density is:

$$q(\theta' | \theta^{(t)}) = \mathcal{N}\left(\theta' \mid \mu(\theta^{(t)}), \epsilon^2 I\right)$$

where $\mu(\theta^{(t)}) = \theta^{(t)} + \frac{\epsilon^2}{2} \nabla \log p(\theta^{(t)} | D)$. The full Hastings acceptance ratio must be used:

$$\alpha(\theta', \theta^{(t)}) = \min \left( 1, \frac{p(\theta' | D) q(\theta^{(t)} | \theta')}{p(\theta^{(t)} | D) q(\theta' | \theta^{(t)})} \right)$$

Pros:

• Often examines the parameter space much more efficiently than RWM, especially in higher dimensions, by using gradient information.
• Can handle complex posterior geometries better than simple random walks.

Cons:

• Requires the computation of the gradient $\nabla \log p(\theta | D)$, which may not be available analytically or computationally feasible for all models. Automatic differentiation tools can help here.
• Requires tuning the step size $\epsilon$. Similar to RWM, $\epsilon$ needs to be balanced for good acceptance rates and exploration. Optimal acceptance rates for MALA are often suggested to be around 0.574.
• The discrete-time approximation can still lead to inefficiencies if $\epsilon$ is too large.

MALA forms a bridge to Hamiltonian Monte Carlo (HMC), which uses gradient information even more effectively by introducing auxiliary momentum variables and simulating Hamiltonian dynamics.

Other Variants

• Adaptive MCMC: These algorithms automatically tune proposal parameters (like the covariance matrix $\Sigma$ in RWM or the step size $\epsilon$ in MALA) during the simulation, often during an initial "burn-in" or "warm-up" phase. While powerful, care must be taken to ensure adaptation stops or diminishes over time to maintain the correct stationary distribution guarantees of the Markov chain.
• Component-wise Metropolis-Hastings: Instead of updating all parameters $\theta = (\theta_1, ..., \theta_d)$ at once, update one parameter or a block of parameters at a time, conditional on the current values of the others. This is closely related to Gibbs sampling, which is discussed in the next section.

Choosing the right Metropolis-Hastings variant involves trade-offs between implementation complexity, computational cost (especially gradients), tuning effort, and sampling efficiency for the specific problem structure. For complex, high-dimensional posteriors, methods incorporating gradient information like MALA (and later, HMC/NUTS) are often significantly more effective than basic Random Walk Metropolis.