The Boomerang Sampler

Joris Bierkens, Sebastiano Grazzi, Kengo Kamatani, Gareth RobertsICML 2020

Overview

The Boomerang Sampler introduces a novel class of non-reversible Markov Chain Monte Carlo (MCMC) algorithms that navigate target distributions using piecewise elliptical paths rather than traditional straight lines. By leveraging a Gaussian reference measure, this approach achieves superior scaling in high-dimensional spaces and supports "exact subsampling." This allows the sampler to process massive datasets with the same computational cost as small ones, entirely avoiding the introduction of bias.

The Challenge with Standard MCMC

MCMC is widely considered the gold standard for Bayesian inference, but it faces significant hurdles when applied to modern problems involving massive datasets and high-dimensional models.

Standard MCMC algorithms require evaluating the entire dataset at every step, which becomes prohibitively slow for big data. While "subsampling"—using a small random batch of data—can accelerate the process, it typically introduces a bias, preventing the algorithm from converging to the true target distribution.

Recent "Piecewise Deterministic Markov Processes" (PDMPs), such as the Bouncy Particle Sampler (BPS) and the Zig-Zag (ZZ) sampler, successfully addressed the bias problem through exact subsampling. However, these methods move in straight lines at a constant velocity. In high dimensions, straight-line trajectories often require frequent, computationally expensive "reflections" to remain within high-probability regions, severely limiting their efficiency.

The Boomerang Sampler Approach

The authors introduce the Boomerang Sampler, which fundamentally alters the physics of the sampler's movement to overcome the limitations of straight-line PDMPs.

  • Elliptical Trajectories: Instead of moving at a constant velocity, the sampler follows a Hamiltonian-inspired differential equation ($dx/dt = v, dv/dt = -x$). This generates elliptical orbits that naturally curve back toward the center of a Gaussian reference measure—giving the algorithm its "Boomerang" name.
  • Gaussian Reference Preconditioning: The method represents the target density relative to a Gaussian measure. This acts as a form of preconditioning, making the sampler highly efficient when the target distribution roughly resembles a normal distribution.
  • Exact Subsampling with Control Variates: By employing a "control variate" gradient estimator, the algorithm can use just a single data point (or a small batch) at each step. Crucially, it remains mathematically guaranteed to target the correct distribution without bias.
  • Factorised Boomerang Sampler (FBS): The authors also propose a variation where different dimensions of the velocity change independently. This is tailored for models with sparse dependencies, such as spatial statistics or signal processing.

Key Insights

  • Curvature as Preconditioning: Moving in ellipses allows the sampler to stay in the important, high-probability parts of the state space for longer durations. This drastically reduces the number of required "switching events" (reflections), particularly as dimensionality increases.
  • $O(1)$ Dimensional Scaling: Under specific conditions, the number of reflections per unit of time remains constant even as the dimension $d$ grows. This is a substantial improvement over the Zig-Zag sampler, where costs typically scale linearly with $d$.
  • "Free" Subsampling: Because the elliptical path inherently accounts for the Gaussian part of the target, subsampling only needs to address the deviation from that Gaussian. For large datasets with well-behaved posteriors, the sampler's "jump rate" actually decreases as the number of observations $n$ increases, making it exceptionally efficient for big data.

Experimental Results

The paper evaluates the algorithm using simulated logistic regression (to test scaling with observations and dimensions) and diffusion bridges (to test the FBS in complex, sparse, infinite-dimensional settings).

Efficiency vs. Data Size

In logistic regression tests, the Boomerang Sampler demonstrated remarkable resilience to dataset size. When utilizing subsampling, it maintained a nearly constant Effective Sample Size (ESS) per second as the dataset size $n$ grew from 100 to 100,000. In contrast, methods without subsampling saw their performance degrade linearly ($O(1/n)$).

Average ESS per second vs. number of observations

Dimensional Performance

When scaling the number of dimensions up to 32, the Boomerang Sampler significantly outperformed both BPS and the Zig-Zag sampler. While the Metropolis-Adjusted Langevin Algorithm (MALA) exhibited better scaling in very high dimensions, it required substantially more careful tuning than the Boomerang approach.

Average ESS per second vs. number of dimensions

Diffusion Bridge Success

The Factorised Boomerang Sampler successfully simulated diffusion bridges in a space with over 4,000 dimensions. It required fewer reflections than the Zig-Zag sampler to achieve high-resolution path reconstruction, proving its viability for complex, sparse problems.

Limitations and Future Work

While powerful, the Boomerang Sampler has a few limitations:

  • Choice of Reference Measure: Performance is highly sensitive to the chosen Gaussian reference measure (its center $x_*$ and covariance $\Sigma$). A poor fit for the target distribution significantly reduces efficiency.
  • Computational Bounds: Implementing the "thinning" required for random switching times relies on finding an upper bound for the event rate. Current bounds can be loose, leading to many "shadow events" (rejected proposed moves) that waste computational resources.

Future work will focus on developing tighter, more adaptive computational bounds and exploring methods to automatically tune the reference measure dynamically during the sampling run.

Summary updated

BibTeX
@inproceedings{bierkens2020boomerang,
  author = {Joris Bierkens and Sebastiano Grazzi and Kengo Kamatani and Gareth Roberts},
  title = {{The Boomerang Sampler}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
}
Figure