Markov Chain Monte Carlo from Lagrangian Dynamics

Shiwei Lan, V. K. Stathopoulos, Babak Shahbaba, Mark Girolami

Abstract

Hamiltonian Monte Carlo (HMC) improves the computational efficiency of the Metropolis-Hastings algorithm by reducing its random walk behavior. Riemannian HMC (RHMC) further improves the performance of HMC by exploiting the geometric properties of the parameter space. However, the geometric integrator used for RHMC involves implicit equations that require fixed-point iterations. In some cases, the computational overhead for solving implicit equations undermines RHMC's benefits. In an attempt to circumvent this problem, we propose an explicit integrator that replaces the momentum variable in RHMC by velocity. We show that the resulting transformation is equivalent to transforming Riemannian Hamiltonian dynamics to Lagrangian dynamics. Experimental results suggest that our method improves RHMC's overall computational efficiency in the cases considered.

Introduction: The Challenge of Geometric Sampling

In Bayesian statistics, sampling from complex, high-dimensional posterior distributions is a fundamental challenge. Hamiltonian Monte Carlo (HMC) has become a standard tool, using gradient information to navigate distributions more effectively than traditional random walk methods.

However, standard HMC assumes a flat Euclidean geometry. When dealing with distributions that have high curvature or non-linear dependencies, such as the "banana-shaped" distribution, standard methods struggle. Riemannian Manifold HMC (RMHMC) addresses this by adapting to the local curvature using a position-specific mass matrix. While RMHMC explores these difficult geometries with high efficiency per step, its numerical integrator is implicit, requiring computationally expensive iterative fixed-point solvers to maintain mathematical rigor.

Figure 1: Sampling paths for RWM, HMC, and RMHMC on a banana-shaped distribution, illustrating the superior pathfinding of geometric methods in curved spaces.

Methodology: From Momentum to Velocity

This research proposes a shift from Momentum ($p$) to Velocity ($v$) to resolve the computational bottleneck of RMHMC. By defining the system in terms of velocity, Hamiltonian dynamics are transformed into Lagrangian dynamics.

  1. RMLMC (Semi-explicit): By switching to velocity, the implicit dependency in the position update is resolved, creating a "semi-explicit" integrator where only the velocity update requires iteration.
  2. e-RMLMC (Fully explicit): The authors further develop a completely explicit integrator using a specialized matrix construction ($\Omega$) to update velocity in a single step, removing iterative solvers entirely.
  3. Volume Correction: Since these explicit integrators are not naturally volume-preserving, a Jacobian determinant adjustment is incorporated into the Metropolis-Hastings acceptance step to ensure the sampler remains mathematically valid.

Experimental Evaluation

The methods were evaluated using Time-Normalized Effective Sample Size (ESS/s), which measures the number of independent samples generated per second of computation. The benchmarks included synthetic distributions and real-world binary classification datasets like Australian Credit, German Credit, and Heart data.

Figure 2: Performance comparison of RMHMC, RMLMC, and e-RMLMC across various real-world datasets, showing significant improvements in ESS/s.

As shown in the experimental results, the explicit method (e-RMLMC) provides substantial speedups. For instance, on the Heart dataset, e-RMLMC achieved an efficiency of 68.18 ESS/s, more than doubling the 28.57 ESS/s achieved by standard RMHMC. Similar trends were observed across other datasets, where the reduction in computational overhead per step outweighed the cost of the Jacobian determinant calculation.

Key Insights and Future Work

The "Velocity Advantage" allows for explicit position updates, making geometric sampling practical for a wider range of problems. While the current method involves $O(D^3)$ matrix inversions, it remains significantly faster than iterative RMHMC for many practical dimensions (up to $D \approx 100$).

Future research directions include exploring sparse matrix approximations to handle extremely high-dimensional problems and developing "split" integrators that could further optimize the Lagrangian dynamics for specific classes of probability models.

Summary updated

Abstract

Hamiltonian Monte Carlo (HMC) improves the computational e ciency of the Metropolis-Hastings algorithm by reducing its random walk behavior. Riemannian HMC (RHMC) further improves the performance of HMC by exploiting the geometric properties of the parameter space. However, the geometric integrator used for RHMC involves implicit equations that require fixed-point iterations. In some cases, the computational overhead for solving implicit equations undermines RHMC's benefits. In an attempt to circumvent this problem, we propose an explicit integrator that replaces the momentum variable in RHMC by velocity. We show that the resulting transformation is equivalent to transforming Riemannian Hamiltonian dynamics to Lagrangian dynamics. Experimental results suggests that our method improves RHMC's overall computational e ciency in the cases considered. All computer programs and data sets are available online (http://www.ics.uci.edu/~babaks/Site/Codes.html) in order to allow replication of the results reported in this paper.
BibTeX
@article{lan2014markov,
  author = {Shiwei Lan and V. K. Stathopoulos and Babak Shahbaba and Mark Girolami},
  title = {{Markov Chain Monte Carlo from Lagrangian Dynamics}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2014},
  doi = {10.1080/10618600.2014.902764},
}
Figure