On the robustness of gradient-based MCMC algorithms

Samuel Livingstone, Giacomo Zanella

Introduction

Markov Chain Monte Carlo (MCMC) methods are fundamental to modern Bayesian statistics, enabling sampling from complex, high-dimensional posterior distributions. However, practitioners often face a difficult choice between the robustness of simple algorithms and the efficiency of gradient-based ones. Simple methods, such as the Random Walk Metropolis (RWM), are easy to tune but scale poorly as dimensionality increases. Conversely, gradient-based methods like the Metropolis-Adjusted Langevin Algorithm (MALA) or Hamiltonian Monte Carlo (HMC) leverage the geometry of the target distribution to take more informed steps.

Despite their efficiency, gradient-based methods are notoriously "fussy." Their performance is highly sensitive to the choice of tuning parameters, particularly the step-size. If the step-size is even slightly too large, the gradient can "explode," pushing proposals into low-probability regions and causing the acceptance rate to crash. This fragility complicates manual tuning and can cause automated adaptive algorithms to fail or converge slowly. This paper introduces the Barker proposal, a novel gradient-based MCMC algorithm designed to combine high-dimensional efficiency with the robustness of simpler random walks.

The Barker Proposal

The Barker proposal utilizes gradient information through a "locally-balanced" jump process. Unlike MALA, which uses the gradient to shift the center of a Gaussian proposal, the Barker proposal uses the gradient to skew a symmetric distribution.

In a one-dimensional setting, the algorithm proceeds as follows:

  1. A random jump distance $z$ is drawn from a symmetric distribution.
  2. The gradient at the current position is used to calculate a probability $p$.
  3. A biased coin is flipped: the algorithm moves $+z$ with probability $p$, and $-z$ with probability $1-p$.

In high-dimensional spaces, this rule is applied to each coordinate independently. A critical advantage of this approach is that the jump distance is determined prior to evaluating the gradient. Consequently, the proposal cannot "explode" away from the target distribution, regardless of the gradient's magnitude. This structural property ensures that the algorithm remains stable even when tuning parameters are suboptimal.

Theoretical Robustness

The primary theoretical contribution of this work is the comparison of performance decay between MALA and the Barker proposal. The authors analyze the "spectral gap"—a measure of how quickly the Markov chain converges—relative to the tuning of the step-size.

The analysis reveals a stark contrast: for MALA, the spectral gap decays exponentially fast if the step-size is poorly tuned. In contrast, the Barker proposal exhibits only polynomial decay. This mathematical distinction explains why the Barker proposal is significantly more forgiving and robust in practice. In the context of adaptive MCMC, where the algorithm must explore the parameter space to learn optimal settings, Barker’s stability allows it to find these settings orders of magnitude faster than its counterparts.

Experimental Evaluation

The authors evaluated the Barker proposal across several benchmarks, ranging from synthetic distributions to complex hierarchical models:

  • Synthetic Targets: Testing on Gaussian, Laplace, and Student-t distributions demonstrated the algorithm's robustness across varying tail behaviors (heavy vs. light).
  • High-Dimensional Scaling: Experiments on isotropic targets up to $10^5$ dimensions confirmed the algorithm's ability to scale effectively.
  • Poisson Hierarchical Model: A benchmark Bayesian model (51 parameters, 250 observations) was used to compare Barker against the No-U-Turn Sampler (NUTS), the state-of-the-art default in the Stan software package.

Key Results

The empirical results underscore the algorithm's practical advantages:

  1. Tuning Stability: In 1D simulations, the Barker proposal maintained high efficiency across four orders of magnitude of step-sizes. MALA’s performance, by comparison, crashed to zero immediately after exceeding a narrow threshold.
  2. Rapid Adaptation: In 100-dimensional tests, the Barker proposal reached stable tuning in approximately 500 iterations. RWM and MALA often required more than 10,000 iterations to achieve similar stability.
  3. Efficiency Gains: On the challenging Poisson random effects model, the Barker proposal was up to 40 times more efficient than NUTS in scenarios characterized by highly heterogeneous scales.

Discussion and Limitations

While the Barker proposal represents a significant step forward in robust MCMC, it has certain limitations. Unlike HMC, the current Barker framework does not incorporate "momentum," which results in a scaling factor of $d^{-1/3}$ relative to dimension (compared to $d^{-1/4}$ for HMC). Additionally, the current derivation is a first-order method, utilizing only the gradient; future work may explore higher-order versions incorporating Hessian information.

Despite these areas for growth, the Barker proposal offers a "fuss-free" alternative for gradient-based inference. Its ability to maintain stability under poor tuning makes it an ideal candidate for automated and adaptive Bayesian inference systems where reliability is as important as speed.

Summary updated

BibTeX
@article{livingstone2022robustness,
  author = {Samuel Livingstone and Giacomo Zanella},
  title = {{On the robustness of gradient-based MCMC algorithms}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2022},
  doi = {10.1111/rssb.12482},
}
Figure