MCMC using $\textit{bouncy}$ Hamiltonian dynamics: A unifying framework for Hamiltonian Monte Carlo and piecewise deterministic Markov process samplers

This paper introduces a unifying framework based on bouncy Hamiltonian dynamics that rigorously connects Hamiltonian Monte Carlo and piecewise deterministic Markov process samplers, enabling the construction of rejection-free, competitive samplers that bridge the gap between these two major Bayesian inference paradigms.

The Gist

Here is an explanation of the paper "MCMC using bouncy Hamiltonian dynamics," translated into simple, everyday language with creative analogies.

The Big Picture: Two Rival Ways to Explore a Maze

Imagine you are trying to find the best spots in a giant, foggy maze (this maze represents complex data in statistics). You want to visit the most interesting areas (the "high probability" zones) without getting stuck in a corner or wandering aimlessly.

For a long time, statisticians have had two main ways to do this:

1. The "HMC" Method (Hamiltonian Monte Carlo): Think of this as a skier. The skier has momentum. They glide down the slopes, using the shape of the terrain to guide them. They move fast and cover a lot of ground. However, if they hit a wall or a bad patch of ice, they have to stop, check if they made a mistake, and sometimes turn back. It's efficient, but that "checking and turning back" slows them down.
2. The "PDMP" Method (Piecewise Deterministic Markov Process): Think of this as a bouncy ball or a zig-zag runner. This runner moves in a straight line until they hit an invisible wall, at which point they instantly bounce off and change direction. They never stop to "check" if they made a mistake; they just keep moving. This is great for speed, but it can be tricky to tune so they don't get stuck bouncing in the same small circle.

The Problem: These two methods have been like rival sports teams. They use different rules, different math, and rarely talk to each other.

The Solution: This paper introduces a new hybrid athlete called the Hamiltonian Bouncy Particle Sampler (HBPS). It combines the best of both worlds: the smooth, powerful momentum of the skier and the instant, no-stopping bounces of the runner.

---

The Secret Ingredient: The "Inertia Battery"

How did they build this hybrid? They invented a new concept called Inertia.

Imagine the skier (HMC) is carrying a battery that powers their momentum.

• In standard skiing, if the terrain changes, the skier might crash or have to stop to check their map.
• In this new system, the skier has a battery that drains as they move.
• The Rule: As long as the battery has charge, the skier glides smoothly.
• The Bounce: The moment the battery hits zero, the skier doesn't stop. Instead, they hit a "bounce" mechanism. They instantly reflect off an invisible wall and keep going, but now with a fresh battery.

This "battery" (called inertia in the paper) is the magic glue. It allows the system to move deterministically (like a machine) but bounce exactly when needed to stay on the right path, without ever needing to stop and ask, "Did I make a mistake?"

Why is this a Big Deal?

1. No More "Stop and Check"

In the old HMC method, the computer often has to simulate a path, check if it's valid, and if it's not, throw it away and try again. This is like driving a car, stopping at every intersection to check a map, and then reversing if you took a wrong turn. It wastes time.
The new HBPS method is like a self-driving car that never stops. If it hits a wall, it bounces. It never rejects a move; it just adjusts its path instantly. This makes it much faster.

2. It's the "Universal Translator"

The paper proves that the "Skier" (HMC) and the "Bouncy Ball" (PDMP) are actually the same thing, just viewed from different angles.

• If you let the "battery" run out very slowly, the HBPS looks like a Skier.
• If you recharge the battery constantly and randomly, the HBPS turns into a Bouncy Ball.
  This unification means that ideas invented for one method can now be used to improve the other.

3. Real-World Superpowers

The authors tested this new method on two massive, real-world problems:

• Medical Study: Analyzing data from nearly 73,000 patients to see which blood thinner is safer. This involved millions of variables.
• Virus Evolution: Tracking how HIV mutations spread across different populations.

In both cases, the new HBPS method was significantly faster and more accurate than the current best methods. It handled the "foggy maze" of high-dimensional data better than anyone else, finding the answers in less time.

The Takeaway

Think of this paper as inventing a new type of vehicle for exploring complex data landscapes.

• Old vehicles (HMC) were fast but stopped too often to check maps.
• Other vehicles (PDMP) kept moving but were hard to steer.
• The new HBPS vehicle has a smart battery that lets it glide smoothly and bounce instantly when needed, never stopping, never wasting time.

This breakthrough doesn't just give statisticians a faster tool; it proves that the two biggest schools of thought in Bayesian statistics are actually part of the same family, opening the door for even more innovations in the future.

Technical Summary

Here is a detailed technical summary of the paper "MCMC using bouncy Hamiltonian dynamics: A unifying framework for Hamiltonian Monte Carlo and piecewise deterministic Markov process samplers" by Andrew Chin and Akihiko Nishimura.

1. Problem Statement

Bayesian computation relies heavily on Markov Chain Monte Carlo (MCMC) methods. Two dominant paradigms have emerged:

• Hamiltonian Monte Carlo (HMC): Uses deterministic Hamiltonian dynamics to propose moves, offering superior mixing in high dimensions compared to random walks. However, it relies on an acceptance-rejection step (Metropolis-Hastings) which can lead to high rejection rates if the proposal deviates significantly from the target, and it requires tuning of step sizes and trajectory lengths.
• Piecewise-Deterministic Markov Process (PDMP) Samplers: Examples include the Bouncy Particle Sampler (BPS) and Zig-Zag sampler. These are continuous-time, rejection-free samplers that use an auxiliary velocity variable. They switch velocities stochastically (via Poisson processes) to maintain the target distribution. While efficient, they are often viewed as distinct from HMC, and their theoretical connection to HMC has been limited to specific high-dimensional limits or univariate marginals.

The Gap: There is a lack of a unified theoretical framework connecting these two paradigms. Specifically, it is unclear how the deterministic proposal mechanism of HMC relates to the stochastic velocity switching of PDMPs, and whether HMC can be adapted to be rejection-free without losing its Hamiltonian structure.

2. Methodology: Bouncy Hamiltonian Dynamics

The authors propose a new class of dynamics called Bouncy Hamiltonian Dynamics that unifies these approaches. The core methodology involves three key components:

A. Surrogate Dynamics and Inertia

Instead of using the true target potential $U_{tar}(x) = -\log \pi(x)$ directly for the dynamics, the method starts with a surrogate potential $U_{sur}(x)$. The system evolves according to standard Hamiltonian dynamics defined by $U_{sur}$ and a kinetic energy $K(v)$.

• To correct for the discrepancy between the surrogate and the true target ($U_{dif} = U_{tar} - U_{sur}$), the authors introduce an auxiliary inertia variable $\iota \geq 0$.
• The inertia evolves deterministically: $\iota_t = \iota_0 - \int_0^t v_s^\top \nabla U_{dif}(x_s) ds$.
• This variable acts as a "budget" for the energy discrepancy.

B. Deterministic Bounces

When the inertia runs out ($\iota_t = 0$), a deterministic bounce occurs. The velocity $v$ is reflected instantaneously across the hyperplane orthogonal to $\nabla U_{dif}(x)$:
$$v_{new} = v_{old} - 2 \frac{v_{old}^\top \nabla U_{dif}(x)}{\|\nabla U_{dif}(x)\|^2} \nabla U_{dif}(x)$$
This reflection ensures that the joint distribution $\pi(x, v, \iota) \propto \exp(-(U_{tar}(x) + K(v) + \iota))$ is preserved. Crucially, this process is rejection-free; the trajectory is modified deterministically to stay on the target manifold rather than being rejected.

C. The Hamiltonian Bouncy Particle Sampler (HBPS)

The authors focus on a specific instantiation where $U_{sur} = 0$ (constant potential).

• Dynamics: The position moves linearly ($x_t = x_0 + tv_0$) until a bounce.
• Bounce Condition: The bounce time $t^*$ is determined by solving $U_{tar}(x_0 + t^*v_0) - U_{tar}(x_0) = \iota_0$.
• Advantage: For log-concave targets, finding $t^*$ reduces to a convex optimization problem (root finding), which is computationally cheaper than the BPS, which requires minimizing a directional derivative before root finding.

3. Key Contributions

1. Unifying Framework: The paper establishes that HMC and PDMPs are not disjoint paradigms. Bouncy Hamiltonian dynamics serves as a bridge:

   • It generalizes HMC by allowing arbitrary surrogate potentials and introducing deterministic bounces to handle the target discrepancy.
   • It converges to PDMPs (specifically BPS and Zig-Zag) in the limit of frequent inertia refreshment.

2. Theoretical Convergence:

   • Theorem 3.2 & 3.3: The authors prove that if the inertia variable $\iota$ is periodically refreshed from its marginal distribution at intervals $\Delta t$, the Bouncy Hamiltonian dynamics converges strongly to the corresponding PDMP as $\Delta t \to 0$. This rigorously links the deterministic bounce mechanism to the stochastic Poisson switching of PDMPs.

3. Novelty of Dynamics:

   • Theorem S.3: The authors prove that for dimensions $d \geq 3$, the HBPS dynamics cannot be represented as a classical or even discontinuous Hamiltonian dynamics with a standard momentum distribution. This confirms that the proposed method is a fundamentally new proposal mechanism, not merely a re-parameterization of existing HMC.

4. Efficiency on Log-Concave Targets:

   • Theorem 4.1: The HBPS is proven to dominate the Random Walk Metropolis (RWM) in asymptotic efficiency.
   • The deterministic bounce mechanism is shown to be a continuous-time analogue of the delayed-rejection scheme, guaranteeing efficiency gains via Peskun-Tierney ordering.

5. Practical Implementation:

   • The HBPS allows for exact simulation on log-concave targets without data augmentation (unlike Pólya-Gamma augmentation for logistic regression).
   • It can be combined with the No-U-Turn (NUTS) algorithm for automatic tuning of trajectory lengths, reducing user burden.

4. Results and Empirical Performance

The authors tested the HBPS on two high-dimensional real-world datasets:

1. Bayesian Sparse Logistic Regression (22,174 parameters):

   • Task: Estimating propensity scores for a study on blood anti-coagulants.
   • Comparison: HBPS (with NUTS and manual tuning) vs. BPS (manually tuned) vs. Pólya-Gamma augmented Gibbs sampler.
   • Outcome: The manually tuned HBPS achieved 4x higher effective sample size (ESS) per time compared to the optimally tuned BPS. The NUTS-HBPS was also superior to BPS and required minimal tuning. The Pólya-Gamma sampler was the slowest.

2. Phylogenetic Probit Model (11,235 parameters):

   • Task: Modeling HIV viral traits with phylogenetic correlation.
   • Comparison: HBPS (conditional and joint updates via operator splitting) vs. BPS.
   • Outcome: While conditional updates showed similar performance, the joint update scheme using operator splitting allowed HBPS to achieve a 2.8x speedup over BPS for partial correlation parameters. This highlights the flexibility of HBPS to handle complex joint updates that are difficult for standard HMC (due to matrix inversion costs) or BPS.

5. Significance and Implications

• Cross-Pollination of Paradigms: The unifying theory suggests that performance differences between HMC and PDMPs may stem from implementation details (e.g., momentum distribution sensitivity to tails) rather than fundamental theoretical inefficiencies. Insights from one field can now be applied to the other.
• Robustness: The framework offers a path to more robust HMC variants. For instance, if standard HMC struggles with tail behavior, the HBPS (or PDMP limits) offers a rejection-free alternative that is less sensitive to these issues.
• Scalability: By enabling exact simulation on log-concave targets without augmentation and supporting operator splitting for joint updates, HBPS provides a scalable tool for modern probabilistic programming languages (like Stan or PyMC), potentially replacing or augmenting current HMC implementations in high-dimensional, constrained, or complex posterior settings.
• Generalization: The framework extends to local PDMPs (factorized targets) and coordinate-wise schemes, subsuming the Hamiltonian Zig-Zag sampler as a special case.

In summary, this paper provides a rigorous mathematical foundation that bridges the gap between deterministic HMC and stochastic PDMP samplers, introducing a new, highly efficient, and tunable sampler (HBPS) that outperforms current state-of-the-art methods on challenging high-dimensional Bayesian inference problems.