Module 8: Advanced MCMC Methods

Module 8: Advanced MCMC Methods

This module introduces advanced MCMC algorithms: Hamiltonian Monte Carlo (HMC), Langevin dynamics (MALA), the No-U-Turn Sampler (NUTS), slice sampling, and adaptive MCMC. We emphasize the measure-theoretic foundations of their invariance properties and discuss theoretical guarantees and limitations.

1. Hamiltonian Monte Carlo (HMC)

1.1 Extended State Space and Hamiltonian Dynamics

Let (^d) denote parameters of interest with target density (()). Introduce auxiliary momentum variables (p ^d) with density (N(0, M)), where (M) is a positive-definite mass matrix.

Define the Hamiltonian \[ H(\theta, p) = U(\theta) + K(p) = -\log \pi(\theta) + \tfrac12 p^\top M^{-1} p + \text{const}. \]

Hamilton’s equations are \[ \frac{d\theta}{dt} = \nabla_p H(\theta,p) = M^{-1} p, \quad \frac{dp}{dt} = -\nabla_\theta H(\theta,p) = -\nabla U(\theta). \]

Proposition 8.1 (Volume Preservation and Energy Conservation)

The exact Hamiltonian flow (_t: (,p) (_t, p_t)) is volume-preserving (Jacobian determinant 1) and conserves (H(,p)).

Proof sketch: Hamilton’s equations define a smooth vector field \[ F(\theta,p) = \begin{pmatrix} M^{-1} p \\ -\nabla U(\theta) \end{pmatrix} \] on (^{2d}). The associated flow (_t) solves the ODE (_t = F(z_t)) with (z_t = (_t, p_t)). The Jacobian matrix of (F) has zero trace because the position derivatives of the momentum update and the momentum derivatives of the position update cancel; equivalently, the Hamiltonian vector field is divergence-free. Liouville’s theorem then implies that the flow (_t) preserves Lebesgue measure, i.e., it is volume-preserving with determinant 1. Moreover, \[ \frac{d}{dt} H(\theta_t, p_t) = \nabla_\theta H(\theta_t,p_t)^\top \dot{\theta}_t + \nabla_p H(\theta_t,p_t)^\top \dot{p}_t = \nabla_\theta H^\top M^{-1} p_t - \nabla_p H^\top \nabla U(\theta_t) = 0, \] by Hamilton’s equations, so (H(_t,p_t)) is conserved along the flow. ()

1.2 HMC Transition Kernel

A typical HMC iteration:

  1. Sample (p N(0, M)) independently of current ().
  2. Approximate Hamiltonian flow for a time (L ) using a symplectic integrator (e.g., leapfrog) to obtain proposal ((‘, p’)).
  3. Accept or reject ((‘, p’)) using an MH step with acceptance probability \[ \alpha = \min\{1, \exp(-H(\theta',p') + H(\theta,p))\}. \]
  4. Return (’) if accepted, otherwise retain ().

The exact flow would preserve the joint density (e^{-H(,p)}); the Metropolis correction accounts for numerical integration error.

2. Langevin Dynamics and MALA

2.1 Overdamped Langevin Diffusion

Consider the SDE \[ d\Theta_t = \frac12 \nabla \log \pi(\Theta_t) \, dt + dB_t, \] where (B_t) is a standard Brownian motion. Under suitable conditions, () is the invariant distribution of this diffusion.

2.2 Unadjusted Langevin Algorithm (ULA)

Discretize the SDE with step size (> 0): \[ \Theta_{k+1} = \Theta_k + \frac{\epsilon}{2} \nabla \log \pi(\Theta_k) + \sqrt{\epsilon} Z_k, \] where (Z_k N(0, I_d)) i.i.d. ULA does not exactly preserve (), but can approximate it under small ().

2.3 Metropolis-Adjusted Langevin Algorithm (MALA)

Use the ULA proposal within MH:

  • Proposal density: \[ q(\theta, \theta') = N\left( \theta + \frac{\epsilon}{2} \nabla \log \pi(\theta),\; \epsilon I_d \right). \]
  • Acceptance probability as in MH to correct discretization bias.

Under regularity conditions, MALA is reversible with invariant distribution ().

3. NUTS and Adaptive Path Length

The No-U-Turn Sampler (NUTS) adaptively selects trajectory lengths in HMC to avoid wasteful backtracking.

  • Conceptually explores forward and backward along the Hamiltonian trajectory until a “U-turn” criterion is met.
  • Maintains reversibility and detailed balance through careful construction of a binary tree of candidate states and a symmetric selection rule.

Rigorous convergence analyses are more involved but build on the invariance of the joint ((,p)) measure and conditions on step-size adaptation.

4. Slice Sampling

4.1 Basic Idea

Given target density (()), introduce an auxiliary variable (u (0, ())). The joint density is \[ f(\theta,u) \propto \mathbf{1}\{0 < u < \pi(\theta)\}. \]

Gibbs sampling in ((,u)) space:

  1. Sample (u (0, ())).
  2. Sample (u) uniformly from the “slice” ({: () > u}).

The marginal of () is (), making slice sampling an exact MCMC method.

4.2 Practical Implementations

Exact sampling from slices is often impossible; one uses interval expansion and shrinking procedures (e.g., stepping-out and shrinkage) that maintain invariance if constructed carefully.

5. Adaptive MCMC

5.1 Time-Inhomogeneous Chains

Adaptive MCMC updates the transition kernel over time, e.g., adjusting proposal covariance in MH. The resulting chain is no longer Markov with a fixed kernel, complicating convergence analysis.

5.2 Diminishing Adaptation and Containment

A common set of sufficient conditions for convergence to ():

  1. Diminishing adaptation: The difference between successive kernels goes to zero: \[ \sup_x \| K_{n+1}(x, \cdot) - K_n(x, \cdot) \|_{\text{TV}} \to 0. \]
  2. Containment: A uniform bound on convergence times across the adaptive sequence.

Theorem 8.2 (Convergence of Adaptive MCMC, Informal)

If the family of kernels ({K_n}) used in the adaptive algorithm all admit () as invariant distribution, and if diminishing adaptation and a suitable containment condition hold, then the adaptive chain converges to () in distribution.

Idea of proof: Write the adaptive chain as using, at iteration (n), a kernel (K_n) chosen based on the past. Diminishing adaptation ensures that successive kernels become close in total variation, so the algorithm behaves asymptotically like a time-homogeneous Markov chain. Containment provides uniform control of convergence times across the family ({K_n}): with high probability, the chain does not spend long periods in regions where convergence is arbitrarily slow. One then constructs a coupling between the adaptive chain and a reference Markov chain with kernel close to (K_n) for large (n), and uses perturbation bounds on Markov operators along with regeneration or drift/minorization techniques to show that the adaptive chain inherits convergence to ().

6. Problem Set 8 (Representative Problems)

  1. HMC Invariance. Using Proposition @prop-hmc-volume-energy, show that the exact Hamiltonian flow preserves the extended density (e^{-H(,p)}). Then argue carefully why the Metropolis correction step yields a Markov chain with invariant distribution (()).

  2. MALA Detailed Balance. Derive the MALA acceptance probability and verify detailed balance with respect to () in the general case, making explicit use of the Gaussian proposal density and the MH ratio.

  3. Slice Sampling Correctness. Prove that the basic slice sampling scheme with exact slice sampling has () as invariant distribution by viewing it as a Gibbs sampler on the joint density and marginalizing out the auxiliary variable.

  4. Adaptive MH Example. Consider an adaptive random-walk MH algorithm that updates the proposal covariance based on the empirical covariance of past samples. Discuss conditions under which diminishing adaptation holds and potential violations of containment, and interpret these conditions in the light of Theorem ?@thm-adaptive-mcmc.

  5. HMC Step-Size Tuning. Discuss how step size and number of leapfrog steps in HMC affect acceptance rates, energy error, and effective exploration, relating your discussion to the theory of symplectic integrators and to the optimal-scaling result Theorem ?@thm-mh-optimal-scaling from Module 6.