The Barker Proposal: Combining Robustness and Efficiency in Gradient-Based MCMC

Samuel Livingstone, Giacomo Zanella

TL;DR

This paper introduces the "Barker proposal," a novel gradient-based MCMC algorithm that successfully bridges the gap between robustness and efficiency. It offers the desirable scaling properties of advanced methods while retaining the tuning robustness of simpler algorithms, making it particularly beneficial for adaptive MCMC.

What Problem Does This Paper Address?

Markov Chain Monte Carlo (MCMC) methods are crucial for computing high-dimensional integrals in statistical inference. However, a fundamental tension exists between the efficiency of sampling (how quickly it explores the target distribution) and its robustness, particularly concerning the sensitivity to tuning parameters like step-size. Sophisticated gradient-based MCMC algorithms (like Langevin and Hamiltonian Monte Carlo) are highly efficient but can be very sensitive to these parameters, especially when the target distribution is heterogeneous. This sensitivity makes them difficult to tune and can lead to poor performance if not set perfectly. Simpler methods, like Random Walk Metropolis (RWM), are more robust to tuning but less efficient, especially in high dimensions. The paper addresses this dilemma by seeking a method that combines the best of both worlds: the efficiency of gradient-based methods with the tuning robustness of simpler ones.

Methods

The authors propose a new gradient-based MCMC algorithm, the "Barker proposal," inspired by the classical Barker accept-reject rule. The core idea is to modify the standard Metropolis-Hastings framework by introducing a novel "balancing function" that allows for gradient information to be incorporated into the proposal mechanism without sacrificing robustness.

Key methodological contributions include:

  • Theoretical Analysis of Spectral Gaps: The paper analyzes how the spectral gap (a measure of how quickly an MCMC chain converges to its stationary distribution) degrades for existing algorithms (RWM, Langevin, HMC) as tuning parameters become suboptimal. They show that gradient-based methods suffer exponentially fast decay, while RWM decays polynomially.
  • The Barker Proposal Derivation: The Barker proposal is derived from a continuous-time Markov jump process framework, specifically by employing a "locally balanced" approach. The choice of a specific balancing function, $g(t) = t/(1+t)$, leads to a tractable candidate kernel.
  • Algorithm Design: A simple sampling strategy (Algorithm 1) is provided for generating proposals from the Barker distribution in one dimension, and this is extended to higher dimensions (Algorithm 2).
  • Robustness and Scaling Analysis: Extensive theoretical results are presented on the Barker proposal's robustness to tuning, geometric ergodicity, and scaling with dimension.
  • Adaptive MCMC Framework: The paper utilizes a standard adaptive MCMC framework (Algorithm 4 from Andrieu & Thoms, 2008) to empirically evaluate the performance of the Barker proposal alongside RWM and MALA.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations using synthetic target distributions.

Key Insights and Ideas

  • The Robustness-Efficiency Trade-off is Quantifiable: The paper demonstrates that the sensitivity of gradient-based MCMC to tuning parameters can be characterized by the decay rate of spectral gaps, revealing a fundamental trade-off.
  • Gradient Information Can Be Incorporated Robustly: The Barker proposal shows that it's possible to leverage gradient information for efficiency without succumbing to the extreme sensitivity to tuning that plagues other gradient-based methods.
  • The Barker Proposal Mimics RWM Robustness: Crucially, the Barker proposal exhibits robustness to tuning similar to the Random Walk Metropolis algorithm, a significant advantage in practical applications.
  • Adaptive MCMC Benefits Greatly from Robustness: The simulations highlight that algorithms with better tuning robustness (like the Barker proposal) adapt much faster and achieve better performance in challenging, heterogeneous target distributions.
  • A New Tool for Complex Models: The Barker proposal offers a promising new tool for sampling from complex, high-dimensional distributions where traditional gradient-based methods struggle due to tuning difficulties.

Key Results

  • Theoretical Robustness: The Barker proposal is shown to have polynomial decay of its spectral gap with respect to tuning parameter mismatch, similar to RWM, contrasting with the exponential decay of Langevin and HMC.
  • Efficient Scaling: The Barker proposal exhibits favorable scaling with dimension, comparable to MALA ($O(d^{-1/3})$), meaning the number of iterations per effective sample grows sub-linearly with dimension.
  • Faster Adaptation in Simulations: In adaptive MCMC settings with heterogeneous targets, the Barker proposal consistently achieved significantly faster adaptation times (e.g., 3x to 34x speed-up over RWM and MALA) and lower Mean Squared Errors (MSE) after a fixed number of iterations.
  • Superior Performance on Challenging Targets: For complex scenarios like Poisson hierarchical models with heterogeneous scales and skew-normal distributions, the Barker proposal outperformed RWM and MALA, and in some cases, even competitive with state-of-the-art HMC/NUTS implementations in terms of efficiency per gradient evaluation.

Limitations and Future Work

  • Large $\lambda$ Regime: The paper briefly discusses the $\lambda \uparrow \infty$ regime (small proposal step-size) and conjectures that all considered algorithms behave similarly, but this is left for future work.
  • High-Dimensional Scaling Rigor: While Proposition 6 suggests $O(d^{-1/3})$ scaling for Barker, rigorous proof of weak convergence for general $g$ functions in high dimensions is left for future work.
  • Optimality of $g(t)$: The paper focuses on $g(t) = t/(1+t)$ for tractability and good performance, but the question of whether this choice is generally optimal for minimizing asymptotic variances is left for future work.
  • Extensions to Barker Proposal: Future work could explore extensions to the Barker proposal that incorporate momentum (like HMC) to potentially achieve $d^{-1/4}$ scaling, or develop schemes that are exact at higher orders.
  • Exploration of Other Robustness Features: Investigating which specific features of a scheme contribute to or detract from robustness to tuning is suggested.

Summary updated

Abstract

There is a tension between robustness and efficiency when designing Markov chain Monte Carlo (MCMC) sampling algorithms. Here we focus on robustness with respect to tuning parameters, showing that more sophisticated algorithms tend to be more sensitive to the choice of step-size parameter and less robust to heterogeneity of the distribution of interest. We characterise this phenomenon by studying the behaviour of spectral gaps as an increasingly poor step-size is chosen for the algorithm. Motivated by these considerations, we propose a novel and simple gradient-based MCMC algorithm, inspired by the classical Barker accept-reject rule, with improved robustness properties. Extensive theoretical results, dealing with robustness to tuning, geometric ergodicity and scaling with dimension, suggest that the novel scheme combines the robustness of simple schemes with the efficiency of gradient-based ones. We show numerically that this type of robustness is particularly beneficial in the context of adaptive MCMC, giving examples where our proposed scheme significantly outperforms state-of-the-art alternatives.
BibTeX
@article{livingstone2022barker,
  author = {Samuel Livingstone and Giacomo Zanella},
  title = {{The Barker Proposal: Combining Robustness and Efficiency in Gradient-Based MCMC}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2022},
  doi = {10.1111/rssb.12482},
}
Figure