A fresh take on 'Barker dynamics' for MCMC

Max Hird, Samuel Livingstone, Giacomo ZanellaMCQMC 2020

TL;DR

This paper introduces and rigorously derives "Barker dynamics," a novel gradient-based Markov Chain Monte Carlo (MCMC) method. It demonstrates that Barker dynamics offers remarkable robustness to challenging target distributions, particularly those with high skewness, outperforming traditional methods like Metropolis-adjusted Langevin Algorithm (MALA) in such scenarios.

What Problem Does This Paper Address?

Markov Chain Monte Carlo (MCMC) methods are workhorses for sampling from complex probability distributions, essential in Bayesian inference and statistical modeling. Gradient-based MCMC methods, like MALA, leverage the gradient of the target distribution to propose moves, aiming for faster exploration of the state space, especially in high-dimensional problems. However, these methods can struggle when the target distribution is highly skewed. The gradient can diverge near modes, leading to proposals that are unlikely to be accepted, causing slow mixing and poor convergence. This paper addresses this limitation by presenting a new gradient-based MCMC approach, Barker dynamics, designed to be more robust to skewed distributions.

Methods

The paper provides a full derivation of Barker dynamics, placing it within the framework of continuous-time Markov jump processes. The core idea stems from modifying the standard Metropolis-Hastings acceptance probability. Instead of the typical Hastings acceptance probability, Barker's approach uses a different balancing function, $g(t) = t/(1+t)$, which leads to a modified transition kernel.

The authors then extend this to a continuous-time Markov jump process where the jump rate $\lambda(x)$ is defined as the integral of the modified transition probability $p(x, y)$. A key challenge is the intractability of this integral. The paper proposes a solution by using a first-order approximation of the ratio of target densities, $t(x, y) = \pi(y)/\pi(x)$, which simplifies the integral. This approximation, combined with the Barker balancing function, leads to a tractable jump kernel.

For multi-dimensional problems ($d > 1$), the paper discusses two ways to introduce skewness. The preferred method involves skewing each dimension individually, which offers greater flexibility and improved performance compared to a global skewing. This leads to a d-dimensional Metropolis-Hastings algorithm where the proposal step involves drawing an innovation $\xi$ from a proposal distribution $q(\cdot)$ and then constructing a candidate state $y = x + b \cdot \xi$, where $b$ is a vector of $\pm 1$ determined by the gradient of the log-target distribution.

Datasets

The paper evaluates the proposed Barker algorithm on a challenging ill-conditioned logistic regression example using the "arrythmia" dataset from the UCI machine learning repository. This dataset is noted for its imbalanced categorical covariates, which contribute to a pronounced level of skewness in the posterior distribution. The authors also use a "model problem" involving skew-normal distributions to illustrate theoretical properties.

Key Insights and Ideas

  • Robustness to Skewness: The most significant insight is that Barker dynamics is remarkably robust to skewed target distributions, a common pitfall for other gradient-based MCMC methods like MALA.
  • Theoretical Foundation: The paper provides a rigorous derivation of Barker dynamics, connecting it to continuous-time Markov jump processes and demonstrating its unique properties arising from the choice of balancing function.
  • Flexibility in High Dimensions: The d-dimensional extension of Barker dynamics, particularly the approach of skewing each dimension individually, offers significant flexibility and improved mixing compared to simpler global skewing methods.
  • Simplicity and Efficiency: Despite its sophisticated theoretical underpinnings, the Barker algorithm is presented as computationally efficient and relatively easy to implement, especially when compared to methods that require more complex tuning or second-order information.

Key Results

  • Improved Mixing in Skewed Distributions: In a model problem with skew-normal distributions, Barker dynamics maintains a stable acceptance rate as skewness increases, while MALA's acceptance rate collapses to zero.
  • Robustness in Logistic Regression: On a challenging ill-conditioned logistic regression problem with imbalanced data, Barker dynamics consistently achieves reasonable performance across various scenarios (dense/diagonal covariance, raw/standardized data). In contrast, MALA struggles to reach equilibrium in most scenarios, only performing well when the data is standardized and the covariance matrix is diagonal.
  • Asymptotic Efficiency: For suitably regular problems, Barker dynamics achieves the same $O(d^{-1/3})$ asymptotic efficiency as MALA in high-dimensional settings, but with greater robustness to tuning parameters.

Limitations and Future Work

  • Approximation Error: The derivation of the tractable jump kernel relies on a first-order approximation of $t(x, y)$. While this approximation is effective, the authors acknowledge that the resulting transition kernel may not have the target distribution $\pi$ as its exact equilibrium distribution. They suggest that in some cases, this approximation error might be small enough to be ignored, but further work is needed to quantify this.
  • Further Algorithm Development: The paper highlights that there is "much room for the development of further algorithms within the general framework" of Barker dynamics, suggesting potential for new methods building on the presented theory.
  • Choice of Proposal $q(\cdot)$: While a Gaussian $q(\cdot)$ was used in the experiments, the authors note that "ongoing work suggests that other choices may be preferable," indicating a potential area for future exploration.

Summary updated

Abstract

We study a recently introduced gradient-based Markov chain Monte Carlo method based on 'Barker dynamics'. We provide a full derivation of the method from first principles, placing it within a wider class of continuous-time Markov jump processes. We then evaluate the Barker approach numerically on a challenging ill-conditioned logistic regression example with imbalanced data, showing in particular that the algorithm is remarkably robust to irregularity (in this case a high degree of skew) in the target distribution.
BibTeX
@inproceedings{hird2020fresh,
  author = {Max Hird and Samuel Livingstone and Giacomo Zanella},
  title = {{A fresh take on 'Barker dynamics' for MCMC}},
  booktitle = {MCQMC},
  year = {2020},
}
Figure