A splitting Hamiltonian Monte Carlo method for efficient sampling

Lei Li, Lin Liu, Yuzhou Peng

TL;DR

This paper introduces a novel "Splitting Hamiltonian Monte Carlo" (SHMC) algorithm that efficiently samples from complex probability distributions. By splitting the potential energy into "smooth" and "stiff" parts, SHMC uses Hamiltonian dynamics for efficient proposal generation and a Metropolis step to correct for the stiff components, enabling faster exploration of multimodal and singular distributions. When combined with a random mini-batch strategy, SHMC achieves near-constant computational cost per time step, making it highly scalable for large-scale problems.

What Problem Does This Paper Address?

Sampling from complex probability distributions is a fundamental challenge in many scientific fields, including statistical physics and Bayesian inference. Traditional Markov Chain Monte Carlo (MCMC) methods, like Hamiltonian Monte Carlo (HMC), can struggle with distributions that have:

  • Singular potentials: These arise in systems with interactions like Coulomb or Lennard-Jones potentials, where the force becomes infinitely strong at short distances, making standard numerical integration unstable.
  • Multiple potential barriers (multimodality): When a distribution has several distinct peaks (modes), MCMC algorithms can get stuck in one mode, failing to explore the entire probability space and leading to biased samples. This is common in Bayesian inference with mixture models due to parameter non-identifiability (label switching).
  • High computational cost: For systems with many interacting particles, calculating the total potential energy and its gradient can be computationally prohibitive, scaling poorly with the number of particles (N).

The paper aims to develop an MCMC method that can efficiently and accurately sample from such challenging distributions while also being computationally scalable.

Methods

The core innovation is the Splitting Hamiltonian Monte Carlo (SHMC) method. It builds upon the general framework of splitting Monte Carlo methods, which involves:

  1. Splitting the potential energy (U): The total potential energy $U$ is decomposed into two parts: $U = U_1 + U_2$.
  2. $U_1$ is chosen to be numerically "non-stiff" or "smooth."
    • $U_2$ contains the "stiff" or numerically problematic parts of the potential.
  3. Proposal generation using $U_1$: Hamiltonian dynamics are used to propose a new state based only on the non-stiff part $U_1$. This leverages the efficiency and desirable properties of Hamiltonian dynamics (e.g., momentum conservation) for the smooth part.
  4. Metropolis rejection step using $U_2$: A Metropolis-Hastings rejection step is then performed, using only the stiff part $U_2$ to determine acceptance. This is computationally efficient because $U_2$ is often easier to compute or involves localized interactions.

This splitting allows the algorithm to use the strengths of Hamiltonian dynamics for exploration while effectively handling the difficult parts of the potential through a computationally tractable rejection step.

To further address computational cost, the authors incorporate the random mini-batch strategy. This is particularly useful for problems involving large summations (e.g., many-body interactions or large datasets in Bayesian inference). Instead of summing over all terms, a small, randomly selected subset of terms is used to approximate the full sum. This reduces the computational cost per time step to $O(1)$, making the algorithm highly scalable.

The paper also provides theoretical analysis of the error introduced by the random batch approximation, showing it is $O(\sqrt{\Delta t})$ in the strong sense and $O(\Delta t)$ in the weak sense, where $\Delta t$ is the time step.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on synthetic models and established problem types (interacting particle systems, Bayesian inference).

Key Insights and Ideas

  • Splitting for "stiffness" and "multimodality": The core idea of splitting the potential energy into non-stiff and stiff parts is a powerful way to handle distributions that are problematic for standard HMC. $U_1$ can be designed to have a "flatter" landscape, facilitating movement between modes, while $U_2$ handles the challenging interactions.
  • Hamiltonian dynamics for smooth parts: Using Hamiltonian dynamics for the non-stiff component $U_1$ is more efficient than overdamped Langevin dynamics for exploring the state space, potentially leading to shorter mixing times.
  • Random mini-batch for scalability: Applying random mini-batches to the summation terms in the potential significantly reduces computational cost, making the method applicable to large-scale problems where full summation is intractable.
  • Theoretical guarantees for random batch: The paper provides error bounds for the random batch approximation, offering confidence in its use and guiding parameter choices.
  • Adaptive strategies: The experiments suggest that adaptive strategies for the number of leapfrog steps ($L_n$) can further improve efficiency, using more steps initially for faster exploration and fewer later for accuracy.

Key Results

  • Efficient sampling of multimodal distributions: SHMC successfully samples from distributions with multiple potential barriers, avoiding the trapping issues seen with standard HMC (demonstrated in the double-well potential and Gaussian mixture model examples).
  • Handling singular potentials: The method effectively samples from systems with singular interactions (e.g., Lennard-Jones fluids, Dyson Brownian motion), where standard HMC would fail.
  • Computational speedup: RB-SHMC (Random Batch SHMC) shows significant computational advantages, achieving near $O(1)$ cost per time step and outperforming standard HMC and RBMC in terms of CPU time and convergence speed. For instance, in the Gaussian mixture model example, RB-SHMC's sampling time was less than 40% of SHMC's.
  • Accuracy: Despite the random batch approximation, the method maintains good accuracy, with theoretical error bounds and empirical results showing convergence to the target distributions.
  • Influence of leapfrog steps ($L_n$): Experiments show that a larger number of leapfrog steps ($L_n$) leads to faster convergence to equilibrium, especially in the initial stages, while smaller $L_n$ can be used later for more accurate sampling.

Limitations and Future Work

  • Design of $U_1$ and $U_2$: The effectiveness of SHMC relies on a good choice of the splitting, which might require domain knowledge or further research into automated splitting strategies. The paper mentions that for multimodal distributions, $U_1$ can be constructed by "computational sand" or by reducing barrier heights, and for singular potentials, by truncating interactions.
  • "Numerical heating" from random batch: The paper acknowledges that random batch can introduce extra noise, potentially leading to "numerical heating" and inaccurate long-term simulations. However, they argue this is less critical for SHMC as Hamiltonian dynamics are only run for short durations.
  • Adaptive strategy justification: While an adaptive strategy for $L_n$ is suggested and shown to be beneficial, a formal theoretical justification for this adaptive approach is left for future work.
  • Theoretical justification for "computational sand": The paper notes that the theoretical justification for using "computational sand" to flatten landscapes for multimodal distributions is left for future work.
  • Trade-off between computational cost and accuracy: The authors suggest that random batch is best suited for problems where computational cost is high and accuracy demands are relatively lower. Further research into this trade-off is an interesting direction.

Summary updated

Abstract

We propose a splitting Hamiltonian Monte Carlo (SHMC) algorithm, which can be computationally efficient when combined with the random mini-batch strategy. By splitting the potential energy into numerically nonstiff and stiff parts, one makes a proposal using the nonstiff part of $U$, followed by a Metropolis rejection step using the stiff part that is often easy to compute. The splitting allows efficient sampling from systems with singular potentials (or distributions with degenerate points) and/or with multiple potential barriers. In our SHMC algorithm, the proposal only based on the nonstiff part in the splitting is generated by the Hamiltonian dynamics, which can be potentially more efficient than the overdamped Langevin dynamics. We also use random batch strategies to reduce the computational cost to $O (1)$ per time step in generating the proposals for problems arising from many-body systems and Bayesian inference, and prove that the errors of the Hamiltonian induced by the random batch approximation is $O (\sqrt{\Delta t})$ in the strong and $O (\Delta t)$ in the weak sense, where $\Delta t$ is the time step. Numerical experiments are conducted to verify the theoretical results and the computational efficiency of the proposed algorithms in practice.
BibTeX
@misc{li2021splitting,
  author = {Lei Li and Lin Liu and Yuzhou Peng},
  title = {{A splitting Hamiltonian Monte Carlo method for efficient sampling}},
  year = {2021},
  eprint = {2105.14406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14406},
}
Figure