HMC, an example of Functional Analysis applied to Algorithms in Data Mining. The convergence in L p .

Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki

Abstract: We present a proof of convergence of the Hamiltonian Monte Carlo algorithm in terms of Functional Analysis. We represent the algorithm as an operator on the density functions, and prove the convergence of iterations of this operator in $L^p$, for $1<p<\infty$, and strong convergence for $2\le p<\infty$.

Introduction

Hamiltonian Monte Carlo (HMC) has become a cornerstone of modern statistics and machine learning, particularly in the realm of Bayesian inference. While its empirical success as a "workhorse" for sampling from complex distributions is well-documented, providing a rigorous mathematical foundation for its convergence across various functional spaces has remained a challenge. Traditionally, theoretical proofs have been confined to specific probability measures or the $L^2$ Hilbert space.

This paper, published in the De Gruyter Journal, addresses this gap by applying the tools of functional analysis to HMC. By representing the algorithm as a linear operator acting on density functions, the authors provide a formal proof of convergence within $L^q$ functional spaces, offering a solid theoretical foundation for the algorithm's reliability across different mathematical norms.

The Functional Analysis Perspective

In machine learning and functional analysis, different "norms" (ways of measuring distance between functions) are critical for model selection and understanding algorithmic behavior under varying constraints. The authors shift the perspective from analyzing individual "sample paths" to analyzing the evolution of the probability density function itself.

The HMC Operator ($\mathcal{T}$)

The core of the methodology involves representing a single step of the HMC algorithm as a linear operator, $\mathcal{T}$. This operator acts on a space of integrable functions ($L^q$) through a three-stage process:

  1. Lifting: The input density is "lifted" into a higher-dimensional phase space by adding auxiliary momentum.
  2. Hamiltonian Trajectory: The system moves along a trajectory defined by Hamiltonian dynamics. This motion is crucial because it preserves both the target distribution (invariance) and the Lebesgue measure (volume).
  3. Projection: The density is projected back down to the original space.

Invariance and Self-Adjointness

The proof relies on two key physical and mathematical properties. First, the invariance of the target distribution ensures the algorithm remains stable. Second, by defining specific conditions—often involving a "momentum flip"—the authors ensure the operator $\mathcal{T}$ is self-adjoint. This property is vital as it simplifies the study of the operator's eigenvalues and spectral properties, making the convergence analysis tractable.

Key Insights: HMC as an Averaging Map

One of the most intuitive insights presented is that the HMC operator $\mathcal{T}$ acts as an "averaging map." Because the algorithm integrates over auxiliary momentum, it effectively smooths out the density function toward the target distribution with each iteration.

Using convexity arguments, the authors establish a Contraction Property (Lemma 3.2), which states that $||\mathcal{T}h||_q \le ||h||_q$. This proves that the algorithm never drifts further away from the target in terms of the $L^q$ norm; rather, it consistently moves closer to the equilibrium density.

Convergence Results

The paper's primary contribution is Theorem 1, which guarantees that for any initial density $h$ in $L^q(Q)$, the sequence of densities produced by repeated HMC iterations ($\mathcal{T}^n h$) converges to the target distribution. However, the nature of this convergence depends on the specific $L^q$ space, revealing a mathematical "phase transition" at $q=2$:

  • Strong Convergence ($2 \le q < \infty$): In these spaces, the geometry allows for strong convergence, meaning the actual distance between the functions in the $L^q$ norm goes to zero.
  • Weak Convergence ($1 < q < 2$): In these spaces, the authors guarantee weak convergence, meaning the functions "look" the same when integrated against other test functions, even if the norm distance itself is less strictly behaved.

Limitations and Future Work

While the paper provides a rigorous proof of that HMC converges, it identifies several areas where the theory must still evolve:

  1. Convergence Rate: The current work does not explicitly calculate the "spectral gap" or the speed of convergence. It remains unclear under what specific conditions the convergence becomes exponential.
  2. Irreducibility: The proof assumes "eventual coverage." If the Hamiltonian motion becomes trapped in specific regions of the state space (lacking irreducibility), the algorithm may fail to converge to a unique limit.
  3. Self-Adjointness Requirements: The strongest results require the operator to be self-adjoint. While many HMC implementations satisfy this, those that do not would require more complex analysis using composite operators.

By establishing these results, the paper provides a much-needed theoretical bridge between the practical application of HMC and the rigorous world of functional analysis.

Summary updated

Abstract

We present a proof of convergence of the Hamiltonian Monte Carlo algorithm in terms of Functional Analysis. We represent the algorithm as an operator on the density functions, and prove the convergence of iterations of this operator in $L^p$, for $1<p<\infty$, and strong convergence for $2\le p<\infty$.
BibTeX
@misc{ghosh2021hmc,
  author = {Soumyadip Ghosh and Yingdong Lu and Tomasz Nowicki},
  title = {{HMC, an example of Functional Analysis applied to Algorithms in Data Mining. The convergence in L p .}},
  year = {2021},
  eprint = {2101.08688},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.08688},
}
Figure