Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling

Luca Martino, Jesse Read, David LuengoIEEE TSP 2015 · DOI

TL;DR

This paper introduces two novel adaptive Markov Chain Monte Carlo (MCMC) algorithms, A²RMS and IA²RMS, designed to overcome a critical limitation in existing Adaptive Rejection Metropolis Sampling (ARMS) methods. These new algorithms ensure the convergence of the proposal distribution to the target distribution and the convergence of the Markov chain to the invariant distribution, leading to more accurate and efficient Bayesian inference.

What Problem Does This Paper Address?

Bayesian inference relies heavily on MCMC methods to sample from complex probability distributions. A key challenge in MCMC is ensuring that the Markov chain converges efficiently to the target distribution. Adaptive Rejection Metropolis Sampling (ARMS) is a popular technique that improves sampling efficiency by adaptively adjusting a proposal distribution. However, a significant drawback of ARMS is its inability to add support points in regions where the proposal distribution is below the target distribution. This can lead to slow convergence or even prevent the proposal from ever matching the target, especially in multimodal distributions. This paper addresses this limitation by proposing new adaptive schemes that can incorporate information from these under-sampled regions, thereby guaranteeing convergence.

Methods

The paper introduces two enhanced ARMS algorithms:

  • A²RMS: This algorithm directly modifies the ARMS procedure by allowing the incorporation of support points in regions where the proposal is below the target. This is done with a decreasing probability as the Markov chain evolves, ensuring convergence while keeping computational costs bounded. It essentially adds an adaptive step to ARMS.
  • IA²RMS: This is an adaptive independent Metropolis-Hastings algorithm. Its key innovation is building the proposal distribution using all previously generated samples, excluding only the current state of the chain. This approach also guarantees convergence of the Markov chain to the invariant density.

Both methods aim to improve the proposal distribution's shape to better match the target, unlike other adaptive MCMC methods that only optimize specific parameters of a pre-defined proposal form. They also introduce simpler procedures for constructing the piecewise linear functions used in ARMS, reducing implementation complexity.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using a synthetic target distribution.

Key Insights and Ideas

  • The "Under-Proposal" Problem: The core insight is identifying and solving the critical limitation of ARMS where support points are not added in regions where the proposal is less than the target. This prevents ARMS from fully adapting to multimodal or complex target distributions.
  • Guaranteed Convergence: The proposed A²RMS and IA²RMS algorithms provide theoretical guarantees for the convergence of the proposal to the target and the Markov chain to the invariant distribution, a significant improvement over standard ARMS.
  • Diminishing Adaptation: A²RMS employs a "diminishing adaptation" strategy, where the probability of adding new support points decreases over time, ensuring computational cost remains bounded.
  • Independent Proposals: IA²RMS leverages past samples to create an independent proposal, which is a powerful strategy for ensuring ergodicity and convergence.
  • Simpler Proposal Construction: The paper demonstrates that the enhanced adaptive schemes allow for simpler methods to construct the proposal distribution, reducing implementation effort and computational cost.

Key Results

The paper presents simulation results comparing standard ARMS with the proposed A²RMS and IA²RMS algorithms.

  • Improved Accuracy: The proposed algorithms consistently yield a more accurate estimated mean and a significantly lower standard deviation of the estimation compared to standard ARMS. For example, in one scenario, the standard deviation was reduced from around 0.73 to 0.11 for one proposal construction method.
  • Reduced Correlation: The correlation between consecutive samples in the Markov chain is substantially lower for A²RMS and IA²RMS than for standard ARMS.
  • Better Convergence: The discrepancy between the proposal and target densities (measured by $D_{\pi|p}(t)$) is significantly reduced by the new algorithms, often by more than an order of magnitude, indicating much faster convergence to the target.
  • Computational Cost: While there's a slight increase in computational cost due to the additional adaptive step, it's moderate, and the number of support points remains bounded. The effort to code and implement the new algorithms is also comparable.
  • Proposal Construction: The paper shows that simpler procedures for building the proposal distribution (e.g., using piecewise uniform pdfs) can yield very good results, especially when combined with the enhanced adaptive schemes.

Limitations and Future Work

  • Burn-in Period: For A²RMS, the first $K$ samples (where $K$ is the adaptation stopping time) are considered auxiliary and should ideally be discarded as part of a burn-in period to ensure convergence. However, empirical results suggest that even using all samples can yield good results.
  • Theoretical Guarantees for IA²RMS: While empirical results are strong, the paper notes that it's difficult to assert whether IA²RMS with $K=N$ (full adaptation) fully satisfies the "bounded convergence" condition, suggesting setting $K < N$ might be safer in practice.
  • Multidimensional Distributions: The current work focuses on univariate distributions. Extending these methods to handle multidimensional target distributions remains a future direction.
  • Simpler Procedures: The paper proposes simpler procedures for constructing proposal densities, which could be further explored for efficiency and ease of implementation, potentially for multidimensional targets.

Summary updated

BibTeX
@article{martino2015independent,
  author = {Luca Martino and Jesse Read and David Luengo},
  title = {{Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  doi = {10.1109/tsp.2015.2420537},
}
Figure