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

Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki

Abstract

This paper establishes $L^q$ convergence for Hamiltonian Monte Carlo (HMC) algorithms. Under mild conditions regarding the associated Hamiltonian motion, we demonstrate that the outputs of these algorithms converge to the desired target distribution. Specifically, we prove strong convergence for $2 \le q < \infty$ and weak convergence for $1 < q < 2$. By extending the analysis from standard Hilbert spaces ($L^2$) to more general reflexive Banach spaces ($L^q$), this work provides a rigorous mathematical foundation for the stability and flexibility of HMC in modern statistical applications.

Introduction

Hamiltonian Monte Carlo (HMC) has become a cornerstone of modern Bayesian inference and machine learning. It is a "workhorse" algorithm used to generate samples from complex, high-dimensional probability distributions where the density is typically known only up to a normalizing constant. While HMC's empirical success is well-documented, providing formal proofs of its convergence in various mathematical contexts is essential for understanding its reliability.

Previous theoretical research has largely focused on convergence within $L^2$ Hilbert spaces. However, practical machine learning often involves scenarios—such as specific model selection criteria or handling non-Gaussian noise—where different norms (like $L^1$ or $L^\infty$) offer better flexibility. This paper fills a critical gap by applying functional analysis to prove convergence within the broader class of $L^q$ spaces.

The Operator-Theoretic Framework

Rather than analyzing HMC as a sequence of individual points, this study treats the algorithm as a linear operator $T$ acting on a space of probability densities. The HMC step is defined as a transformation $T(h)$ that maps an initial distribution $h$ to a subsequent one through three distinct phases: lifting the state to phase space, applying Hamiltonian motion, and projecting back to the original space.

To measure the "distance" between the evolving distribution and the target density $f$, the authors utilize weighted $L^q$ norms. This approach allows for a mathematically tractable way to track the algorithm's progress toward the target state.

The Role of Symmetry and Self-Adjointness

A central finding of this research is the importance of the "adjoint" of the HMC operator. The authors prove that if the auxiliary momentum distribution (commonly a Gaussian) is symmetric, the HMC operator $T$ is self-adjoint ($T = T^\dagger$). This symmetry is the mathematical "key" that unlocks the use of powerful theorems from functional analysis to establish convergence.

Furthermore, the HMC operator is shown to function as an "averaging map." Due to the convexity of the function $x \to x^q$, this averaging property ensures that the $L^q$ norm of the distribution—representing its distance from the target—never increases. Lemma 3.2 formally establishes this norm reduction ($||Th||_q \le ||h||_q$), confirming that each iteration of the algorithm acts as a contraction toward the target state.

Convergence Results

The paper provides a nuanced classification of convergence based on the properties of the $L^q$ space:

  • Strong Convergence ($2 \le q < \infty$): In these "larger" spaces, the sequence of distributions $T^n h$ converges strongly, meaning the functions themselves directly approach the target density.
  • Weak Convergence ($1 < q < 2$): In these "smaller" spaces, the sequence converges weakly, meaning the averages of the functions against test functions approach the target values.

In both cases, the target distribution $f$ is established as the unique fixed point (eigenvalue 1) of the operator, provided the "coverage property" (irreducibility) holds. This ensures the algorithm does not become trapped in a sub-optimal distribution.

Discussion and Limitations

While this work provides a rigorous proof of that HMC converges, it leaves open the question of how fast it converges. The authors note that the specific rates of convergence (e.g., geometric vs. sub-geometric) remain a subject for future research. Additionally, the current results rely heavily on the assumption of self-adjointness. While the authors suggest that non-self-adjoint operators could be handled by analyzing the composite operator $S = T^\dagger \circ T$, this adds practical complexity to the implementation.

Finally, the proofs assume a "coverage property" where the Hamiltonian motion can eventually reach all parts of the state space. Future theoretical refinements may look to weaken this requirement to a more general "eventual coverage" statement, further broadening the applicability of these convergence proofs.

Summary updated

Abstract

We establish $L_q$ convergence for Hamiltonian Monte Carlo algorithms. More specifically, under mild conditions for the associated Hamiltonian motion, we show that the outputs of the algorithms converge (strongly for $2\le q<\infty$ and weakly for $1<q<2$) to the desired target distribution.
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 Lp}},
  year = {2021},
  eprint = {2101.08688},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.08688},
}
Figure