On the convergence of Hamiltonian Monte Carlo

Introduction

HMC algorithms have achieved many empirical successes. Recently, the theory on HMC have been addressed by many authors ; see . An in depth discussion of the HMC method and a survey of the existing results are given in .

Another important property of Hamiltonian flow is the conservation of energy. Since $J^{-1}$ is skew-symmetric, for any solution $(q(t),p(t))$ of (4)

Despite many recent advances, theoretical properties of the HMC algorithm are still not completely understood. This paper addresses two important issues in the analysis of HMC algorithm: irreducibility and geometric ergodicity.

In a second part, we establish the geometric ergodicity of the HMC sampler under the assumptions that the potential $U$ is homogeneous outside a ball (or is a perturbation of an homogeneous function) and that the level sets are convex. Our assumptions imply that the proposal kernel of HMC satisfies an ‘inwards acceptance’ property , which is essential to show that HMC (and MALA) is geometrically ergodic.

Our results complement the recent paper . This paper provides a variety of conditions under which the HMC algorithm is not geometrically ergodic. It establishes the geometric ergodicity under the abstract ’inwards acceptance’ property for which we provide verifiable sufficient conditions.

Ergodicity of the HMC algorithm

The proof is postponed to Section 5.1.1. ∎

In our next result, we relax the second order differentiability condition on $U$, and in the case $\beta<1$ we even allow for arbitrary large values of the step size $h$ and the number of iterations $T$. The result is less quantitative and the proof is more involved: we use degree theory for continuous mapping (the main notions required in the proof are recalled in Section 4).

1 $(\beta)$ for some $\beta\in\left[0,1\right)$,

The proof is postponed to Section 5.1.2. ∎

To the best of the author’s knowledge, the first results regarding the irreducibility of the HMC algorithm are established in under the assumption that $U$ and $\left\|\nabla U\right\|$ are bounded above. Note that these assumptions are in general satisfied only for compact state space. Irreducibility has also been tackled in : in this work however, the number of leapfrog steps $T$ is assumed to be random and independent of the current position and momentum. Under this setting and additional conditions which in particular imply that the number of leapfrog steps $T$ is equal to $1$ with positive probability, shows that the kernel associated with the HMC algorithm is irreducible. Under this condition, the proof is a direct consequence of the irreducibility of the MALA algorithm - a mixture of Markov kernels is irreducible as soon as one component of the mixture is irreducible; the irreducibility of MALA kernel has been established in ). Finally, [5, Proposition 3.7] shows that RHMC is irreducible under the condition that $U$ is at least quadratic. Note that Theorem 2 establishes irreducibility of HMC of sub-quadratic potential. However, leap-frog integrator is not numerically stable for lighter than Gaussian target density, therefore other kind of integrators should be used instead, see e.g. [10, Chapter VI].

(a) follows from Theorem 1 and Appendix A. (b) and (c) are straightforward applications of Theorem 2. ∎

Geometric ergodicity of HMC

The proof is postponed to Section 5.2.1. ∎

Assume 1$(1)$ and 2$(2)$. Let $\bar{S}>0$ be such that $\Theta(S)<\operatorname{A}_{1}$ for any $S\in\left(0,\bar{S}\right]$, where

The proof is postponed to Section 5.2.2 ∎

We now derive sufficient conditions under which the condition (34) of Section 3 is satisfied.

It is easily checked that under 3, the results of Section 2 can be applied, i.e. $\nabla U$ satisfies 1($m-1$); see Section 5.2.4.

Condition 2$(m)$ and 3$(m)$ are satisfied by power functions $q\mapsto c\left\|q\right\|^{m}$. More generally, they are satisfied by $m$-homogeneously quasiconvex functions with convex level sets outside a ball and by perturbations of such functions.

We say that a function $U_{0}$ is $m$-homogeneous quasi-convex outside a ball of radius $R_{1}$ if the following conditions are satisfied:

$U_{0}$ is $m$-homogeneously quasiconvex outside a ball of radius $R_{1}$ and $\lim_{\left\|q\right\|\to+\infty}U_{0}(q)=\infty$.

For $k=2,3$, $\lim_{\left\|q\right\|\to+\infty}\left\|D^{k}G(q)\right\|/\left\|q\right\|^{m-k}=0$.

The proof is postponed to Section 5.2.3. ∎

To show that the condition (34) of Section 3 is satisfied under 3$(m)$, we rely on the following important result which implies that the probability of accepting a move goes to 1 as $\left\|q\right\|\to\infty$.

Assume 3$(m)$ for some $m\in\left(1,2\right]$. Let $\gamma\in\left(0,m-1\right)$.

The proof is postponed to Section 5.2.4. ∎

However, in the case $m=2$, Section 3-(b) only implies that the HMC proposal is inward only if the step size $h$ is sufficiently small with respect to the number of leapfrog step $T$, i.e. is of order $\mathcal{O}(T^{-3/2})$. To relax this condition, we strengthen 3($2$) by assuming that $U$ is a smooth perturbation of a quadratic function.

Note that it is straightforward to check that under 4, the conditions 1$(1)$ and 2$(2)$ hold.

The proof is postponed to Section 5.2.5. ∎

We now can establish the geometric ergodicity of the HMC sampler.

We finally consider the case where the number of leapfrog steps is a random variable independent of the current state.

Compared to , which establishes geometric ergodicity of the HMC kernel under an implicit assumption on the behaviour of the acceptance rate, our conditions are directly verifiable on the potential $U$.

where $\tau>0$ is the duration parameter of the RHMC algorithm. Note that these conditions assumed that the target density is lighter than Gaussian. In comparison, our results can be applied to sub-quadratic potentials. In addition, it can be shown that HMC is not geometrically ergodic under (46) on the following example associated with the potential defined by (49) below.

The main difference with the setting of is that HMC has a acceptance/rejection step and the integrated acceptance ratio

Irreducibility for a class of iterative models

The claim follows from the differentiation theorem for measures, see [25, Theorem 7.14]. ∎

The following Corollary is a straightforward consequence of Theorem 12.

In the next proposition, we give examples of functions $f$ which satisfy 2.

We have now all the necessary results to prove Section 4.

Since $f^{g}(x,z)=bz+g(x,z)$ and $g(x,\cdot)$ is Lipschitz with a Lipschitz constant which is uniformly bounded over the ball $\operatorname{B}(0,R)$, $f^{g}_{x}$ is Lipschitz with bounded Lipschitz constant over this ball. Hence 2($R,0,M$)-(i) holds.

Proofs

We prefaces the proofs of our main results by useful bounds on the position and the momentum in the intermediate steps of the leap-frog integration.

where $(q_{k},p_{k})=\Phi_{h}^{\circ(k)}(q_{0},p_{0})$, $(x_{k},v_{k})=\Phi_{h}^{\circ(k)}(x_{0},v_{0})$ and $\Phi_{h}^{\circ(k)}$ and $\vartheta_{1}$ are defined by (12) and (19), respectively.

Second, similarly using (67), we have that

where we have used (71) for the last inequality. Summing up (71) and (72), we get the desired result for $k=1$. ∎

Let $\beta\in\left[0,1\right]$ and assume 1$(\beta)$-(ii).

where $(q_{k},p_{k})=\Phi^{\circ k}_{h}(q_{0},p_{0})$ and $\Phi^{\circ k}_{h}$ is defined by (12).

where $\vartheta_{1}$ is defined by (19) and

Therefore, (80) is satisfied which concludes the induction and the proof.

Second, similarly using (67), we get that

By a straightforward induction, we obtain that

where $\vartheta_{2}$ is defined in (78).

where $\vartheta_{1}$ is defined by (19).

For $T\geq 2$ and $h>0$, by Section 5-(ii), we have

It is a well known fact (see for example [9, Exercise 3.26]) that if

which implies by (109) and Section 5 that there exists $C\geq 0$ satisfying

with the convention $0\times+\infty=0$ and

1.2 Proof of Theorem 2

which implies that the condition Section 4-(i) is satisfied. To check that condition Section 4-(ii) holds, we consider separately the two cases: $\beta<1$ and $\beta=1$.

showing that condition (ii) of Section 4 is satisfied.

2 Proofs of Section 3

Note that by definition (32) of $\mathscr{R}(q)$ and $\mathscr{B}(q)$

The proof then follows from combining this result and (122) since they imply

2.2 Proof of Section 3

Combining (136) and (141), and using that $m<2$, we finally obtain that (134) holds.

which implies using Section 5, $\vartheta_{1}(s)\geq 1$ for any $s\geq 0$, and the dominated convergence theorem that

Then, Section 5 and the Fatou Lemma imply that

where $\Theta$ is defined in (38). The proof follows.

2.3 Proof of Section 3

Finally using 1, we get that the set $\mathsf{L}_{M}$ is convex.

To show 3-(ii), we check first that it is sufficient to prove that

Using (155) again and since $\partial\mathsf{L}_{M}$ is compact, we get that there exists $R_{2}\geq 0$ such that $t_{q}\left\|q\right\|\in\left[R_{1},R_{2}\right]$. Hence by (158), we have

Thus 3-(ii) holds for $U_{0}$. Finally 2 implies that the function $U=U_{0}+G$ satisfies 3-(ii) as well.

First consider $q\in\Pi$. We next argue by contradiction that

Indeed assume that $U_{0}(q)<M$. Then by continuity of $U_{0}$, we get that $q\in\mathsf{L}_{M}^{\circ}$. But since $\mathsf{L}_{M}\subset\Pi^{-}$, we get $q\in(\Pi^{-})^{\circ}$ which is impossible since $q\in\Pi=\partial\Pi^{-}=\overline{\Pi^{-}}\setminus(\Pi^{-})^{\circ}$.

Then $uq\in\Pi$ and by (163), $U_{0}(uq)\geq M$. If $u\geq 1$, using 1 and (160), we get

In turn, if $u<1$, since $\left\|q-x\right\|\leq\epsilon_{0}$, by (161) and 1, $U_{0}(q)=u^{-1}U_{0}(uq)$ and (165) still holds.

2.4 Proof of Section 3

We preface the proof by several technical preliminary Lemmas.

Plugging this result in (168) concludes the proof.

Assume 1$(\beta)$ for $\beta\in\left(0,1\right]$. Let $\gamma\in\left(0,\beta\right)$.

where $\vartheta_{1}$ is defined in (19).

where $\vartheta_{1}$, $\vartheta_{2}$ and $\vartheta_{3}$ are defined in (19) and (78) respectively.

The proof is concluded by taking $\delta$ sufficiently small and $R_{0}$ sufficiently large. ∎

where $\Phi_{h}^{\circ(1)}$ is defined in (12), $(q_{1},p_{1})=\Phi_{h}^{\circ(1)}(q_{0},p_{0})$, and $q_{t}=q_{0}+t(q_{1}-q_{0})$ for $t\in\left[0,1\right]$.

Using the definition of $H(q,p)=\frac{1}{2}\left\|p\right\|^{2}+U(q)$, we get

First, Taylor’s formula with exact remainder enables us to write

Using that $q_{1}=\widetilde{\Phi}_{h}^{\circ(1)}(p_{0},q_{0})$, with $\widetilde{\Phi}_{h}^{\circ(1)}$ defined by (13), in (192) and (193), we get

Summing these equalities up and observing appropriate cancellations yields

By using $q_{1}=\widetilde{\Phi}_{h}^{\circ(1)}(p_{0},q_{0})$ again in the definition of each $I_{j}$ we obtain successively

Gathering all these equalities in (199) concludes the proof. ∎

We show that each term in the sum in the right hand side of this equation is nonpositive if $\left\|q_{0}\right\|$ is large enough and $\left\|p_{0}\right\|\leq\left\|q_{0}\right\|^{\gamma}$. By Section 5.2.4, we have

where, setting $q_{t,k}=q_{k}+t(q_{k+1}-q_{k})$ for $t\in\left[0,1\right]$,

Hence, $\limsup_{\left\|q_{0}\right\|\to+\infty}\sup_{\left\|p_{0}\right\|\leq\left\|q_{0}\right\|^{\gamma}}\left\{A_{k}/\left\|q_{0}\right\|^{3m-4}\right\}>0$. We now bound $B_{k}$. Using 3-(i), Section 5.2.4 and (222), we get by (215) that

Combining 3-(i), Section 5.2.4 and (222) again, we get by crude estimate that there exists $C\geq 0$ such that

We finally bound the two terms $C_{k,1}$ and $C_{k,2}$. First, using the same reasoning as for $B_{k}$, we get that

Arguing like in (223), we get that $\limsup_{\left\|q_{0}\right\|\to+\infty}\sup_{\left\|p_{0}\right\|\leq\left\|q_{0}\right\|^{\gamma}}\left\{C_{k,3}/\left\|q_{0}\right\|^{3m-4}\right\}<0$. Gathering all these results and using that $3m-4\geq\max(4m-6,2m-3+\gamma)$ for $m\in\left(1,2\right)$ and $\gamma\in\left(0,m-1\right)$, we get that for all $k\in\{0,\ldots,T-1\}$,

Finally, arguing like in (231), we get that

Combining (231)-(232)-(233)-(234) and (235) in (208), and using that $2\geq 1+\gamma$ for $\gamma\in\left(0,1\right)$, we get that for all $k\in\{0,\ldots,T-1\}$,

2.5 Proof of Section 3

The proof is concluded by using that $\boldsymbol{\Sigma}$ is definite positive and taking $\delta$ sufficiently small and $R_{1}$ sufficiently large. ∎

We show below that there exists $\bar{S}<\bar{S}_{1}$ such that, for all $h\geq 0$ and $T\geq 0$ satisfying $hT\leq\bar{S}$,

Using that for $k\in\{1,\ldots,T\}$, $p_{k}=p_{0}-(h/2)\{\nabla U(q_{0})+\nabla U(q_{k})\}-h\sum_{i=1}^{k-1}\nabla U(q_{i})$ and (243), we obtain that for any $k\in\{1,\ldots,T\}$ and $q_{0},p_{0}$, $\left\|q_{0}\right\|\geq\max(1,R_{1})$, $\left\|p_{0}\right\|\geq\left\|q_{0}\right\|^{\gamma}$,

Then, if $Th\leq\bar{S_{2}}$ for any $q_{0},p_{0}$, $\left\|q_{0}\right\|\geq\max(1,R_{1})$, $\left\|p_{0}\right\|\geq\left\|q_{0}\right\|^{\gamma}$, we get that

Similarly using that $\boldsymbol{\Sigma}$ is definite positive, we obtain that there exist $\operatorname{B}_{2}>0$ and $\bar{S}_{3}\in\left(0,\bar{S}_{1}\right]$ such that if $hT\leq\bar{S}_{3}$, for any $q_{0},p_{0}$, $\left\|q_{0}\right\|\geq\max(1,R_{1})$, $\left\|p_{0}\right\|\geq\left\|q_{0}\right\|^{\gamma}$, we get that

Combining (247)-(253)-(259)-(261) and (262) in (254), we obtain that (245) holds with $\bar{S}=\min(\bar{S}_{2},\bar{S}_{3})$ since (243) implies that $\left\|q_{k}\right\|\geq\left\|q_{0}\right\|/2$. ∎

Appendix A Harris recurrence for mixture of Metropolis-Hastings type Markov kernels

References