The Barker proposal: combining robustness and efficiency in\n gradient-based MCMC

Samuel Livingstone, Giacomo Zanella

This blog-style summary breaks down the research paper "The Barker proposal: combining robustness and efficiency in gradient-based MCMC" for a technically literate audience.

TL;DR

The authors introduce the Barker proposal, a novel gradient-based MCMC algorithm that bridges the gap between simple, robust samplers and complex, efficient ones. It matches the high-dimensional efficiency of state-of-the-art methods like MALA while inheriting the "forgiveness" of random walk schemes when tuning parameters are poorly chosen.

What Problem Does This Paper Address?

Markov chain Monte Carlo (MCMC) is the workhorse of Bayesian inference, but it faces a persistent "tension" between robustness and efficiency.

Simple algorithms like Random Walk Metropolis (RWM) are robust—they work reasonably well even if you don't tune their step-size perfectly. However, they scale poorly as the number of dimensions ($d$) increases. To fix this, researchers use gradient-based methods like the Metropolis-adjusted Langevin algorithm (MALA) or Hamiltonian Monte Carlo (HMC). These are highly efficient in high dimensions but are notoriously fragile. If the step-size is slightly too large, or if the target distribution is "heterogeneous" (having very different scales in different directions), these algorithms can fail completely, with acceptance rates dropping to zero.

The authors aim to create a "best of both worlds" sampler: one that uses gradients to navigate high-dimensional spaces efficiently but doesn't break when the tuning isn't perfect.

Methods

The core innovation is the Barker proposal. Unlike MALA, which uses the gradient to "shift" the proposal distribution toward high-density regions, the Barker proposal uses the gradient to skew a symmetric distribution.

  1. The 1D Case: To propose a move from $x$ to $y$, you first draw a symmetric jump $z$. You then decide whether to move to $x+z$ or $x-z$ using a probability based on the gradient at $x$. This probability follows a logistic-style rule inspired by the classical Barker accept-reject rule.
  2. The Multi-dimensional Case: For $d > 1$, the algorithm applies this logic to each coordinate independently to generate a candidate vector, followed by a standard global Metropolis-Hastings (MH) step to ensure the correct target distribution is sampled.
  3. Locally-Balanced Proposals: The authors derive this scheme from a framework of "locally-balanced" jump processes, showing that the Barker rule is the unique choice that results in a specific type of "skew-symmetric" proposal distribution.

Datasets

As is standard for MCMC research, the authors evaluate their method on a variety of challenging target distributions rather than static datasets:

  • Synthetic Targets: Gaussian, Laplace, Student-t, and "ridged" distributions designed to test robustness to heterogeneity and heavy/light tails.
  • Poisson Hierarchical Model: A 51-dimensional random effects model used to test the algorithm on a realistic, non-symmetric posterior distribution with varying scales.

Key Insights and Ideas

  • Polynomial vs. Exponential Decay: The "aha moment" comes from analyzing the spectral gap (a measure of how fast the chain mixes). For MALA/HMC, the spectral gap decays exponentially fast as the tuning mismatch increases. For the Barker proposal, it decays only polynomially, just like the robust (but slow) RWM.
  • Handling Light Tails: MALA often fails on distributions with "light tails" (where the gradient grows very fast) because it proposes jumps far into the tails that are always rejected. The Barker proposal is naturally "capped"—the skewing probability can never exceed 1, so it remains stable even when gradients are massive.
  • Synergy with Adaptation: In adaptive MCMC, the algorithm "learns" the best tuning parameters on the fly. Because the Barker proposal works well even with bad initial parameters, it explores the space faster, which in turn helps the adaptation mechanism learn the good parameters much more quickly than MALA or HMC.

Key Results

  • Scaling: Theoretically and numerically, the Barker proposal achieves $d^{-1/3}$ scaling, matching MALA's efficiency in high dimensions and significantly outperforming RWM's $d^{-1}$ scaling.
  • Robustness: In 1D simulations, when the step-size was 100x larger than optimal, MALA's efficiency dropped to near zero, while Barker remained functional, mirroring the robustness of RWM.
  • Performance vs. NUTS: On the Poisson hierarchical model, the Barker proposal often outperformed NUTS (the state-of-the-art HMC variant used in Stan). In one challenging scenario, Barker was 40 times more efficient than NUTS in terms of Effective Sample Size (ESS) per gradient evaluation.

Limitations and Future Work

  • Coordinate-wise limitation: The current Barker proposal treats coordinates independently. While this works well, the authors suggest that incorporating momentum (similar to HMC) could potentially improve scaling from $d^{-1/3}$ to $d^{-1/4}$.
  • Higher-order info: The current version is a "first-order" method (using only the gradient). Exploring "second-order" versions that use Hessian information could further improve performance for highly curved distributions.
  • Theoretical Gaps: While the "small step-size" regime is well-understood, the authors note that more rigorous proof is needed for the "large step-size" regime to fully characterize the decay of the spectral gap.

Summary updated

Abstract

There is a tension between robustness and efficiency when designing Markov\nchain Monte Carlo (MCMC) sampling algorithms. Here we focus on robustness with\nrespect to tuning parameters, showing that more sophisticated algorithms tend\nto be more sensitive to the choice of step-size parameter and less robust to\nheterogeneity of the distribution of interest. We characterise this phenomenon\nby studying the behaviour of spectral gaps as an increasingly poor step-size is\nchosen for the algorithm. Motivated by these considerations, we propose a novel\nand simple gradient-based MCMC algorithm, inspired by the classical Barker\naccept-reject rule, with improved robustness properties. Extensive theoretical\nresults, dealing with robustness to tuning, geometric ergodicity and scaling\nwith dimension, suggest that the novel scheme combines the robustness of simple\nschemes with the efficiency of gradient-based ones. We show numerically that\nthis type of robustness is particularly beneficial in the context of adaptive\nMCMC, giving examples where our proposed scheme significantly outperforms\nstate-of-the-art alternatives.\n
BibTeX
@article{livingstone2022barker,
  author = {Samuel Livingstone and Giacomo Zanella},
  title = {{The Barker proposal: combining robustness and efficiency in\textbackslash\{\}n gradient-based MCMC}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2022},
  doi = {10.1111/rssb.12482},
}

Loading related content...

Figure