Positive Curvature and Hamiltonian Monte Carlo

Christof Seiler, Simon Rubinstein-Salzedo, Susan P. Holmes

Overview

This paper bridges the gap between physics-inspired sampling and differential geometry by showing that Hamiltonian Monte Carlo (HMC) can be viewed as a geodesic flow on a Riemannian manifold. By calculating the sectional curvature of this manifold, the authors prove that HMC often operates in spaces of positive curvature—especially in high dimensions. This geometric perspective explains HMC's remarkable ability to concentrate measure and provide accurate estimates quickly, even in complex, high-dimensional spaces.

The Challenge of High-Dimensional Sampling

Sampling from high-dimensional probability distributions is a fundamental challenge in statistics and machine learning. Standard Markov Chain Monte Carlo (MCMC) methods often fall victim to the "curse of dimensionality," where the number of steps required to explore the space grows exponentially with the number of dimensions.

Hamiltonian Monte Carlo (HMC) is a known exception that scales much better, but its theoretical foundations have remained somewhat under-explored. While we know HMC works well for complex tasks like computational anatomy (e.g., sampling deformations of 3D medical images with millions of voxels), we haven't had a rigorous geometric way to quantify why it converges so efficiently or exactly how many samples are needed for a given level of accuracy.

Geometric Methods

The authors employ a clever trick from mathematical physics to recast the sampling problem:

  1. HMC as Geometry: They reframe the movement of an HMC sampler—which usually involves potential and kinetic energy—as a "geodesic" (the shortest path) on a Riemannian manifold.
  2. The Jacobi Metric: They define a specific metric ($g_h$) that distorts space based on the target probability distribution. In this view, regions of high probability are "stretched" and regions of low probability are "shrunk," naturally guiding the sampler.
  3. Sectional Curvature: The core of the paper involves calculating the sectional curvature of this HMC manifold. Curvature dictates how paths behave: in positive curvature (like on a sphere), paths tend to converge; in negative curvature (like a saddle), they diverge.
  4. Coarse Ricci Curvature ($\kappa$): Using modern tools from Markov chain theory, they link this geometric curvature to a "mixing rate," allowing them to derive new concentration inequalities—mathematical bounds on the error of the sample mean.

Key Insights: High Dimension is a Feature, Not a Bug

One of the most striking findings is that as the number of dimensions ($d$) increases, the sectional curvature of the HMC manifold for a Gaussian distribution becomes more consistently positive.

Sectional curvature distributions across varying dimensions.

Positive curvature acts as the "secret sauce" for HMC. Just as most of the surface area of a high-dimensional sphere lies near its equator, positive curvature ensures that the sampler stays concentrated in the "important" parts of the distribution. The authors provide a concrete formula for sectional curvature in terms of the potential energy (the log-density of the distribution), allowing researchers to check the "geometric health" of their sampling problem.

Key Results and Error Bounds

The authors mathematically prove that for a $d$-dimensional Gaussian, the sectional curvature is positive with very high probability as $d$ grows. Furthermore, they provide a new concentration inequality that quantifies the probability of the sample mean deviating from the true integral.

HMC sample means bounded by theoretical error limits.

When comparing simulation to theory, the empirical results are even more promising. In a 100-dimensional test, the actual simulations converged much faster than the theoretical bounds predicted. While the theory suggested $e^{19}$ steps for a specific error bound, the simulation reached that level of accuracy in roughly $e^{10}$ steps. This suggests that HMC is even more robust in practice than current worst-case mathematical bounds can strictly prove.

Limitations and Future Work

  • Conservative Bounds: The theoretical bounds derived are quite pessimistic. The authors acknowledge a significant gap between their mathematical "worst-case" guarantees and the "average-case" performance seen in actual simulations.
  • Rare Negative Curvature: Even in generally well-behaved distributions, localized "bad" spots with negative curvature can exist. The current theory assumes these rare spots don't ruin overall convergence, but more work is needed to quantify how HMC recovers when it traverses these regions.
  • Beyond Gaussians: This foundational paper focuses heavily on Gaussian distributions. Extending these geometric proofs to more complex, multi-modal, or heavy-tailed distributions (like the multivariate $t$-distribution) is the next frontier for this research.

Summary updated

Abstract

The Jacobi metric introduced in mathematical physics can be used to analyze Hamiltonian Monte Carlo (HMC). In a geometrical setting, each step of HMC corresponds to a geodesic on a Riemannian manifold with a Jacobi metric. Our calculation of the sectional curvature of this HMC manifold allows us to see that it is positive in cases such as sampling from a high dimensional multivariate Gaussian. We show that positive curvature can be used to prove theoretical concentration results for HMC Markov chains.
BibTeX
@inproceedings{seiler2014positive,
  author = {Christof Seiler and Simon Rubinstein-Salzedo and Susan P. Holmes},
  title = {{Positive Curvature and Hamiltonian Monte Carlo}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure