PaperlayerView exact revision on arXiv

Source-linked AI summary

The Random Walk Metropolis: Linking Theory and Practice Through a Case Study

Chris Sherlock, Paul Fearnhead, Gareth O. Roberts

arXiv:1011.6217v1stat.ME

TL;DR

Inference for MMPPs is complicated by hidden-state modes and label symmetry, motivating methods to improve RWM efficiency. The article develops and tests selected theoretical and practical techniques on MMPP datasets, finding that performance depends on the implementation and posterior shape or tails. It also presents an MMPP reparameterization that yields a near-best RWM-within-Gibbs scheme on D2.

  • Problem

    Hidden states can produce minor modes, improper-posterior risks under improper priors, and equal modes from label permutations, complicating MMPP inference.

    Source: §1 · p. 2

  • Method

    The article develops selected RWM efficiency concepts and tests algorithms on MMPP datasets, including a problem-specific reparameterization for RWM-within-Gibbs.

    Source: §1 · p. 1, §3.5.2 · p. 13

  • Results

    Across two MMPP datasets, some RWM implementations improved efficiency uniformly while others depended on posterior shape or tails; a sensibly implemented RWM was at least as good as some other available MCMC algorithms.

    Source: §5 · p. 18

  • Takeaways & Limitations

    The new D2 reparameterization made Metropolis-within-Gibbs perform nearly as well as the best scheme, the adaptive multiplicative random walk.

    Source: §5 · p. 18

    Adaptive proposals can learn from an unimportant tail or minor mode, become less efficient at finding the main posterior mass, and lose the guarantee of stationary distribution π(·).

    Source: §3.5.1 · p. 12

Abstract

from arXiv · show

The random walk Metropolis (RWM) is one of the most common Markov chain Monte Carlo algorithms in practical use today. Its theoretical properties have been extensively explored for certain classes of target, and a number of results with important practical implications have been derived. This article draws together a selection of new and existing key results and concepts and describes their implications. The impact of each new idea on algorithm efficiency is demonstrated for the practical example of the Markov modulated Poisson process (MMPP). A reparameterization of the MMPP which leads to a highly efficient RWM-within-Gibbs algorithm in certain circumstances is also presented.

1. INTRODUCTION

The article develops selected theoretical and practical ideas for improving random walk Metropolis (RWM) efficiency, using inference for the Markov modulated Poisson process (MMPP) as a demanding test case. It compares observed efficiency changes with theoretical predictions and presents an MMPP reparameterization for RWM-within-Gibbs.

1. INTRODUCTION

  • The article develops selected RWM efficiency theory and intuition, rather than a comprehensive review, and uses them to improve implementation.It includes optimal scaling and shaping, convergence, RWM-within-Gibbs, hybrid algorithms, and adaptive MCMC.Source: §1 · p. 1
  • The article uses MMPPs to model clustered point processes, including web requests, photon arrivals, and rare DNA-motif occurrences.These examples illustrate the range of applications described in the introduction.Source: §1 · pp. 1–2
  • MMPP inference is difficult because hidden states yield minor modes, improper-posterior risks under improper priors, and equal modes from state-label permutations.These features complicate inference and provide a nontrivial setting for testing efficiency improvements.Source: §1 · p. 2
  • The authors test the described algorithms on two simulated MMPP datasets and compare realized efficiency changes with theoretical predictions.The datasets have different characteristics, allowing examination of posterior shape, orientation near the mode, and tail behavior.Source: §1 · pp. 1–2

2. BACKGROUND

The background section introduces RWM and its Metropolis-within-Gibbs variation, then lays out efficiency measures and theoretical approaches. It also introduces the MMPP and the datasets used later.

2. BACKGROUND

  • The section establishes the RWM and RWM-within-Gibbs algorithms before discussing efficiency and introducing the MMPP data used later.It covers practical and theoretical approaches to algorithm efficiency.Source: §2 · p. 2

2.1 Random Walk Metropolis Algorithms

RWM proposes a symmetric random-walk jump and accepts or rejects it according to the target density. RWM-within-Gibbs extends this procedure by updating blocks in sequence.

2.1 Random Walk Metropolis Algorithms

  • RWM proposes a jump from the current value using a prespecified symmetric density, with an overall scale parameter controlling jump size.The proposed value becomes the next state if accepted; otherwise the chain remains at its current value.Source: §2.1 · p. 2
  • The acceptance rule always accepts proposals toward a local mode and accepts proposals away from it according to their relative posterior heights.Rejecting some downhill proposals helps keep the chain in the main posterior mass.Source: §2.1 · p. 2
  • The acceptance probability makes the RWM reversible at equilibrium with the specified stationary distribution, a property that simplifies constructing chains with a prespecified target.Reversible geometrically ergodic chains also have a slightly stronger central limit theorem than nonreversible ones.Source: §2.1 · p. 2
  • RWM-within-Gibbs cycles through sub-blocks, proposing and accepting or rejecting a jump for each block in turn.The article’s simplest and most commonly used version updates each parameter component sequentially.Source: §2.1 · p. 3
  • Although each update stage is reversible, the full RWM-within-Gibbs algorithm is not; random-scan updating is a reversible variation.The random-scan version chooses one component at random at each iteration and updates it conditional on the others.Source: §2.1 · p. 3

2.2 Algorithm Efficiency

The section distinguishes convergence from mixing and accuracy, introduces practical measures of movement and autocorrelation, and presents two theoretical frameworks for RWM efficiency. Its theoretical approaches yield the same efficiency-optimization strategies under different target assumptions.

2.2.1 Convergence

  • Convergence is assessed practically by examining traceplots for all components; for geometrically ergodic reversible chains, a central limit theorem supports Monte Carlo estimates and their standard errors.The discussion assumes stationarity for subsequent efficiency analysis and treats burn-in as the discarded portion before that point.Source: §2.2.1 · pp. 3–4
  • Geometric ergodicity is a qualitative property when its rate and constants are unknown, while polynomial ergodicity is weaker and has more delicate central limit theorem conditions.These distinctions frame the section’s theoretical treatment of convergence.Source: §2.2.1 · p. 3

2.2.2 Practical measures of mixing efficiency

  • At stationarity, integrated autocorrelation time (ACT) measures dependent draws per independent equivalent, while effective sample size is n/ACT.The article estimates ACT by truncating the autocorrelation sum at the first lag whose estimate falls below 0.05; this simple estimator is intended for relative comparisons despite potentially high variance.Source: §2.2.2 · p. 4
  • When posterior variance is finite, maximizing expected squared Euclidean jump distance (ESEJD) is equivalent to minimizing a variance-weighted sum of lag-1 autocorrelations.For roughly elliptical targets with known covariance, ESJD is an alternative efficiency measure based on principal-component autocorrelations.Source: §2.2.2 · pp. 4–5

2.2.3 Assessing accuracy

  • Low ACT does not ensure an accurate posterior estimate if a chain explores an unimportant region without reaching the main posterior mass.The paper compares 10,000-iteration RWM estimates with a reference from a 100,000-iteration Gibbs run after burn-in.Source: §2.2.3 · p. 5

2.2.4 Theoretical approaches for algorithm

  • Under conditions on the first two derivatives of f(·), with E[Ci] = 1, E[C2 i] = b, and λ_d = µ/d^1/2, the process approaches a Langevin diffusion.Source: §2.2.4 · p. 5
  • The ESJD approach derives expected squared jump distance and acceptance-rate forms for unimodal elliptically symmetric targets, subject to shell and eccentricity conditions.For independent target and proposal components, the scaling uses µ = d^1/2λ_d.Source: §2.2.4 · pp. 5–7
  • The two theoretical approaches yield identical RWM efficiency-optimization strategies, although one applies to independent-component targets and the other to unimodal elliptically symmetric targets.Their agreement suggests potential robustness of the strategies across target forms.Source: §2.2.4 · p. 7

2.3 The Markov Modulated Poisson Process

The MMPP models event times from a Poisson process whose intensity varies with an unobserved continuous-time Markov chain. The article uses two simulated datasets to compare how intensity differences affect state and parameter distinguishability.

2.3 The Markov Modulated Poisson Process

  • An MMPP couples a continuous-time Markov chain to a stochastically independent Poisson process whose event intensity is set by the chain’s current state.In the two-state examples, q12 = q21 = 1, with intensities [10,30] or [10,17].Source: §2.3 · p. 7, Figure 2 · p. 7
  • The likelihood uses the time to the first event, inter-event times, and time from the last event to the observation-window end; absent further information, ν is often stationary.The initial distribution ν is over the Markov chain’s states.Source: §2.3 · p. 7
  • Because relabeling states leaves the likelihood unchanged, the article identifies state 1 as the state with the lower Poisson intensity.With an invariant prior, the posterior also has identical modes under state and parameter relabeling.Source: §2.3 · p. 7

2.3.1 MMPP data in this article

  • D1 uses intensities [10,30] and is easier than D2, with [10,17], for distinguishing the underlying state and parameter values.The estimated marginal posteriors compare ψ1 with ψ2 and ψ1 with q12 for both datasets.Source: §2.3.1 · pp. 7–8, Figure 3 · p. 8

3. IMPLEMENTATIONS OF THE RWM: THEORY AND PRACTICE

The section connects RWM theory and practice by describing how scale tuning, proposal geometry and tails, adaptive updates, and problem-specific knowledge inform efficiency, with guidance shaped by target structure. For the two-dimensional MMPP, it discusses reparameterization and Metropolis-within-Gibbs variants, including a final variant with Cauchy proposals for β.

3.1 Optimal Scaling of the RWM

  • Large-dimensional theory motivates a proposal acceptance rate near 0.234, but finite-dimensional optima can differ and a broad range may remain nearly optimal.For example, the optimal rate is 0.44 for a one-dimensional Gaussian target and proposal, while rates between 0.2 and 0.3 are nearly optimal in several cases for d ≥ 6.Source: §3.1 · pp. 8–9

3.2 Optimal Scaling of the RWM-Within-Gibbs

  • Metropolis-within-Gibbs can outperform block updates when grouped parameters have different scales, though its maximum gain assumes orthogonal blocks; the implementation tunes each update to 0.4–0.45.When components share a scale, larger within-Gibbs jumps are offset by their lower update frequency, yielding no limiting efficiency difference from block updates.Source: §3.2 · pp. 9–10

3.3 Tailoring the Shape of a Block Proposal

  • Matching a block proposal’s shape to an elliptical target improves relative exploration when target scales differ, and the paper estimates covariance from an earlier block-RWM run.The pilot uses iterations 1000–2000 of each corresponding Algorithm 1 replicate to estimate the covariance matrix.Source: §3.3 · pp. 10–11

3.4 Improving Tail Exploration

  • Heavy-tailed posteriors can make random walks lose directional information, motivating Cauchy proposals and log-space multiplicative walks, whose logarithmic transformation applies only to positive parameters.The source also notes that polynomially tailed posteriors may require proposals with at least as heavy tails for polynomial ergodicity, and that a log transform can create a heavy left tail when mass lies near zero.Source: §3.4 · p. 11

3.5.1 Adaptive MCMC

  • Adaptive MCMC can reinforce learning from a minor mode or tail and lose the intended stationary distribution; convergence requires diminishing adaptation and containment.The described adaptive scheme updates its covariance from past samples, with changes of O(1/n), and adjusts scale toward an equilibrium acceptance rate of about 30%.Source: §3.5.1 · pp. 12–13

3.5.2 Utilizing problem-specific knowledge

  • For MMPP cases with ψ1≈ψ2, the data are informative about average intensity but less informative about the intensity difference, motivating a problem-specific reparameterization.Source: §3.5.2 · p. 13
  • When event intensities are similar and δ is small, a Taylor expansion motivates a reparameterization in which ψ, q, α, and β capture decreasing amounts of log-likelihood variation.The transformation is from (ψ1, ψ2, q12, q21) to (ψ, q, α, β), suggesting different scalings for the parameters.Source: §3.5.2 · p. 13
  • MwGRep updates (ψ, q, α, β) with multiplicative random walks for the first three positive parameters and additive updates for β.The four proposal scalings were chosen to yield acceptance rates between 0.4 and 0.45.Source: §3.5.2 · p. 13
  • MwGRepCau, the final algorithm, differs from MwGRep by proposing additive β updates from a Cauchy distribution.Its Cauchy scaling was optimized for the best ACT over the first 1000 iterations.Source: §3.5.2 · p. 13

4. RESULTS

Across the two simulated MMPP datasets, block proposals with an approximately correct covariance shape and adaptive multiplicative updates improve RWM efficiency, while results depend on posterior shape and dataset. The reparameterized Metropolis-within-Gibbs algorithm performs at least as well as the adaptive multiplicative random walk on D2, but is less effective for some D1 parameters.

4. RESULTS

  • D1 generally supports more efficient exploration than D2 because its data contain more parameter information and its posterior has lighter tails.The simulation comparisons used two datasets, three replicates per dataset and algorithm, and 11,000 iterations per run with a 1,000-iteration burn-in.Source: §4 · pp. 13–14
  • Block proposals with approximately the correct Gaussian shape improve performance enormously over identity-scaled block proposals on both datasets.Identity-scaled proposals tune to the smallest-variance transition intensities, so they explore the Poisson intensities less efficiently.Source: §4 · p. 14
  • Metropolis-within-Gibbs efficiency falls between identity-scaled and shaped block updates, with a larger improvement over identity-scaled blocks on D1 than D2.D1 parameters are more nearly independent, so coordinate-wise updates align more closely with the posterior ellipse's principal axes.Source: §4 · p. 15
  • Cauchy-shaped block proposals are slightly less efficient than Gaussian-shaped proposals on both datasets, despite expectations for heavy-tailed D2.The authors suggest that negative-parameter proposals are rejected and some large Cauchy jumps leave the main posterior mass, which may not represent the tail shape well.Source: §4 · pp. 15–16
  • Multiplicative updates make little difference on D1 but improve on shaped block updates for heavy-tailed D2, with adaptive multiplicative updates slightly more efficient still.The adaptive algorithm refines its estimated covariance matrix and overall scaling throughout the run.Source: §4 · p. 16
  • The nonadaptive algorithms are geometrically ergodic under the exponential-prior setup, yet multiplicative random walks are more efficient where D2's initial posterior-tail decay is slower than exponential.The authors note that the polynomially ergodic tail-exploration theory does not strictly apply under these priors.Source: §4 · pp. 14, 16
  • On D2, the reparameterized Metropolis-within-Gibbs algorithm is at least as efficient as the adaptive multiplicative random walk, but D1 exploration of q12 and q21 is less efficient than with the original parameterization.For D1, ψ and β are strongly positively correlated (ρ ≈ 0.8), and both are strongly negatively correlated with α (ρ ≈ −0.65); D2 correlations are small (|ρ| < 0.3), as are D1 correlations involving q.Source: §4 · p. 17
  • D2's independence-sampler posterior sample may be inaccurate, while the Gibbs sampler is more efficient than the best RWM algorithms on D1 but not D2.The authors link the D2 concern to a possible minor mode or ridge away from the distribution's center.Source: §4 · pp. 17–18

5. DISCUSSION

The discussion compares RWM efficiency strategies on two MMPP datasets, finding that posterior shape and tails matter alongside scale. Adaptive multiplicative RWM and a reparameterized Metropolis-within-Gibbs scheme perform well, while adaptation becomes more demanding as dimension grows.

5. DISCUSSION

  • RWM remained very inefficient after acceptance-rate tuning alone, but efficiency increased enormously when proposals used an estimate of posterior variance for their shape.For Algorithms 3, 4, and 5, variance estimates came from the first 1,000 post-burn-in iterations of Algorithm 1.Source: §5 · p. 18
  • The multiplicative random walk improved efficiency most noticeably on the heavier-tailed posterior, whereas an additive Cauchy proposal was no more efficient than a Gaussian and took longer to tune.Simple acceptance-rate criteria could not be used to tune Cauchy proposals.Source: §5 · p. 18
  • The adaptive multiplicative random walk learned shape and scale from its history and was arguably the most efficient RWM on both datasets.In a three-dimensional MMPP, a variant took longer to discover near-optimal adaptive parameters.Source: §5 · p. 18
  • Metropolis-within-Gibbs performed better when parameters were nearly orthogonal, and a new D2 reparameterization performed nearly as well as the adaptive multiplicative random walk.The reparameterization was designed for the two-dimensional MMPP with parameter orthogonality in mind.Source: §5 · p. 18
  • Adaptive schemes move toward automation, but learning a posterior variance matrix with O(d^2) components takes increasingly long as dimension grows.The paper recommends using available problem-specific knowledge to start high-dimensional algorithms efficiently.Source: §5 · p. 18

APPENDIX: RUNS WITH HIGHLY VARIABLE ACTS

The appendix reports replicate-level ACTs for selected algorithms and datasets because some combinations had considerable variation.

APPENDIX: RUNS WITH HIGHLY VARIABLE ACTS

  • ACTs varied considerably for certain algorithm–dataset combinations, so Table 3 gives the full replicate-level estimates.The preceding summary reports means across three independent replicates for each dataset and algorithm.Source: APPENDIX: RUNS WITH HIGHLY VARIABLE ACTS · p. 18, Table 3 · p. 19
  • The mean ACTs in Table 2 summarize three replicates, while Table 3 provides individual estimates for the combinations with considerable variation.The appendix therefore exposes variation that can be obscured by reporting means alone.Source: APPENDIX: RUNS WITH HIGHLY VARIABLE ACTS · p. 18, Table 3 · p. 19
  • Table 3 covers four parameters across three replicates, with Blk and BlkShpCau on D1 and Blk, BlkShp, BlkShpCau, and BlkShpMul on D2.Its estimates let readers inspect replicate variation for those selected combinations.Source: Table 3 · p. 19
Loading 1011.6217v1…