Hypocoercivity of Piecewise Deterministic Markov Process-Monte Carlo

Introduction

which is assumed to be finite. For any $k\in\{1,\ldots,K\}$, $\lambda_{k}$ will be referred to as a jump rate and $\lambda_{\rm ref}$ as the refreshment rate.

in which case the velocity is drawn afresh from the marginal invariant distribution, while the position is left unchanged. In this scenario the informal description of the process given above carries on with $\lambda_{\rm ref}\neq 0$ added to the rate $(x,v)\mapsto\sum_{k=1}^{K}\lambda_{k}(x,v)$, $\Pi_{v}$ an additional possible update to the velocity chosen with probability proportional to $\lambda_{\rm ref}$. Another possible choice is the generator of an Ornstein-Uhlenbeck operator leaving $\nu$ invariant.

In all the paper we assume the following condition to hold for either $\mathcal{L}_{1}$ or $\mathcal{L}_{2}$, a condition satisfied by the examples covered in this manuscript.

The particular choice $K=0$ and $F_{0}=\nabla_{x}U$ corresponds to the procedure described in as a motivation for the popular hybrid Monte Carlo method. This process is also known as the Linear Boltzman/kinetic equation in the statistical physics literature or randomized Hamiltonian Monte Carlo . In this scenario the process follows the isocontours of $\mu$ for random times distributed according to an inhomogeneous Poisson law of parameter $\lambda_{\rm ref}>0$, triggering events where the velocity is sampled afresh from $\nu$.

The scenario where $K=d$, $F_{0}=0$ and for $k\in\{1,\ldots,d\}$, $x\in\mathsf{X},\ F_{k}(x)=\partial_{k}U(x)\mathbf{e}_{k}$ where $(\mathbf{e}_{k})_{k\in\{1,\ldots,d\}}$ is the canonical basis, corresponds to the Zig-Zag (ZZ) process , where the $x$ component of the process follows straight lines in the direction $v$ which remains constant between events. In this scenario, the choice of $\mathcal{B}_{k}$ to update the velocity, consists of negating its $k$-th component; see also for related ideas motivated by other applications.

The standard Bouncy Particle Sampler (BPS) of , extended by , correspond to the choice $K=1$, $F_{0}=0$ and $F_{1}=\nabla_{x}U$.

More elaborate versions of the ZZ and BPS processes, motivated by computational considerations, take advantage of the possibility to decompose the energy as $U=\sum_{k=0}^{K}U_{k}$ and corresponds to the choice $F_{k}=\nabla_{x}U_{k}$ , where in the former the sign flip operation is replaced with a component swap.

It should be clear that one can consider more general deterministic dynamics with $F_{0}\neq 0$, effectively covering the Hamiltonian Bouncy Particle Sampler, suggested in .

We remark that the well-known Langevin algorithm corresponds to $K=0$, $F_{0}=\nabla_{x}U$ and the situation where $\mathcal{R}_{v}$ is the Ornstein-Uhlenbeck process.

More general bounces involving randomization (see ) can also be considered in our framework, at the cost of additional complexity and reduced tightness of our bounds.

Main results and organization of the paper

there exists $c_{1}\geq 0$ such that, for any $x\in\mathsf{X}$, $\nabla_{x}^{2}U(x)\succeq-c_{1}\operatorname{I}_{d}$;

Further, 1-(b) also implies the existence of $c_{2}>0$ and $\varpi\geq 0$ such that for any $x\in\mathsf{X}$,

1-(b) indeed implies that the quantity considered is bounded from below, the scaling in $d$ in front of $c_{2}$ will appear natural in the sequel. We have opted for this formulation of the assumption required of the potential to favour intuition and link it to the necessary and sufficient condition for geometric convergence of Langevin diffusions, but our quantitative bounds below will be given in terms of the Poincaré constant $C_{\operatorname{P}}$ for simplicity (see [4, Section 4.2] for quantitative estimates of $C_{\operatorname{P}}$ depending on potentially further conditions on $U$). 1-(a) is realistic in most applications, can be checked in practice and has the advantage of leading to simplified developments. It is possible to replace this assumption with $\sup_{x\in\mathsf{X}}\{|\nabla_{x}^{2}U(x)|/(1+|\nabla_{x}U(x)|)\}<\infty$ and rephrase our results in terms of any finite upper bound of this quantity (see [22, Sections 2 and 3]). Finally the Poincaré inequality (14) implies by [4, Proposition 4.4.2] that there exists $s>0$ such that

for all $x\in\mathsf{X}$, $\nabla_{x}U(x)=\sum_{k=0}^{K}F_{k}(x)$;

for all $k\in\{0,\ldots,K\}$ there exists $a_{k}\geq 0$ such that for all $x\in\mathsf{X}$,

such that for any $k\in\{1,\ldots,K\}$ and $(x,v)\in\mathsf{E}$, $\lambda_{k}(x,v)=\varphi\big(v^{\top}F_{k}(x)\big)$.

Assume that $\mathsf{V}$ and $\nu$ satisfy the following conditions.

$\nu$ has finite fourth order marginal moment and for $i\in\{1,\ldots,d\}$

and for any $i,j,k,l\in\{1,\ldots,d\}$ such that $\operatorname{card}(\{i,j,k,l\})>2$

Under the previous assumptions we can prove exponential convergence of the semigroup.

The constants $A$ and $\alpha$ are given in explicit form in (45) in Theorem 4 (Section 3), in terms of the constant appearing in 1, 2, 4, 5 and 6, where $\epsilon$ can be taken to be $\epsilon_{0}$ given in (47), $\lambda_{v}=\underline{\lambda}$, $\lambda_{x}=C_{\operatorname{P}}/(1+C_{\operatorname{P}})$ and $R_{0}=(4+2\sqrt{3})\vee(\underline{\lambda}/2^{{\nicefrac{{1}}{{2}}}})\vee\overline{R}_{0}$ where

$\kappa_{1}=(1+c_{1}/2)^{{\nicefrac{{1}}{{2}}}}$ and $\kappa_{2}^{-1}=C_{\operatorname{P}}^{-1}(1+4c_{2}d^{1+\varpi}+16C_{\operatorname{P}}^{2})^{{\nicefrac{{1}}{{2}}}}$.

The following details the expected scaling behaviour with $d$ of $A$ and $\alpha$. The proof can be found in Section 4.3.

Consider the assumptions and notation of Theorem 1. Further suppose that there exists $m_{b}>0$ satisfying

which together with $C_{\operatorname{P}},c_{1},c_{2}$ and $\left\|a\right\|_{\infty}=\sup_{k\in\{1,\ldots,K\}}a_{k}$ are independent of $d$. Then $A\leq 3^{{\nicefrac{{1}}{{2}}}}$ and there exists $C^{\alpha}(C_{\operatorname{P}},c_{1},c_{2},\left\|a\right\|_{\infty},m_{b})>0$, independent of $d,\underline{\lambda},c_{\lambda}$ and $C_{\varphi},c_{\varphi}$, such that for $d$ large enough,

Thus, if $\underline{\lambda}$, $c_{\lambda}$, $C_{\varphi}$ and $c_{\varphi}$ are fixed, we get that $\alpha^{-1}$ is in general at most of order $\mathcal{O}(m_{2}^{-{\nicefrac{{1}}{{2}}}}d^{1+\varpi}K^{2})$ if $K\geq 1$.

Now further assume that $C_{\varphi},c_{\varphi}$ and that the refreshment rate are uniformly bounded in the position $x$, implying $c_{\lambda}=0$. Then by Section 2-(30), there exists $C^{\alpha}(C_{\operatorname{P}},c_{1},c_{2},\left\|a\right\|_{\infty},m_{b},c_{\varphi},C_{\varphi})>0$ such that for $d$ sufficiently large

from which we deduce the optimal scaling of the refreshment rate, namely $C_{1}^{\underline{\lambda}}\,\big(1+K^{2}d^{1+\varpi}\big)^{\nicefrac{{1}}{{2}}}\leq\underline{\lambda}\leq C_{2}^{\underline{\lambda}}\,\big(1+K^{2}d^{1+\varpi}\big)^{\nicefrac{{1}}{{2}}}$ for $C_{1}^{\underline{\lambda}},C_{2}^{\underline{\lambda}}>0$ (which we denote $\Theta\big((1+K^{2}d^{1+\varpi})^{\nicefrac{{1}}{{2}}}\big)$ hereafter to alleviate notation). Using the description of RHMC, ZZ and BPS provided in the introduction we deduce the first three lines of Table 1, where $\alpha=\omega(s)$ is used as a short hand notation for $\alpha\geq C^{\alpha}(C_{\operatorname{P}},c_{1},c_{2},\left\|a\right\|_{\infty},m_{b},c_{\varphi},C_{\varphi})s$ for $s\to 0$. The fourth line uses our specialised results of Section 5, showing that the conclusion of Theorem 2 is not optimal for ZZ.

In scaling limits of particular functionals of the ZZ and BPS processes are studied, leading to quantitative estimates of the time required to achieve near independence at equilibrium. More specifically they consider the scenario where the target distribution is a centred normal distribution of covariance matrix $\operatorname{I}_{d}$ and focus on the angular momentum, the negative log-target density and the first coordinate of the process. Our more general results, obtained using a different argument, are in agreement after noticing that considered the scenario $m_{2}=d^{-1}$ and using our earlier remark on the dependence of our estimate of the absolute spectral gap on $m_{2}^{\nicefrac{{1}}{{2}}}$. In it is shown, again using an approach different from ours, that the RHMC has dimension free convergence rate in a scenario similar to ours.

The paper is organised as follows. In Section 3 we develop our framework for hypocoercivity suited to PDMP-MC processes, based on the ideas of . In addition to providing a rigorous framework we further optimize the constants involved, ultimately leading to Theorem 1. The proofs of Theorem 1 and its corollary are given in Section 4. In Section 5, we specialize our results to the case of the Zig-Zag process for which better estimates are possible, leading to attractive scaling properties with the dimension $d$. Various intermediate technical results have been moved to Appendices where, for completeness, we have also included classical facts from functional analysis.

The DMS framework for hypocoercivity

As stated above our results rely on the ideas proposed by for which a rigorous framework was subsequently given in . We derive here a novel proof, which borrows elements of but leads to a different set of conditions motivated by our application to PDMP-Monte Carlo methods. We further provide explicit and optimized estimates of the constants involved in terms of accessible characteristics of the process. We first present abstract results which form the core of all of our proofs and then establish more specific ones common to all the processes considered in this paper, implying some of the abstract conditions. More specific results relating to the Zig-Zag process are treated in Section 5.

Consider the following additional assumption to 1.

$\Pi_{v}\mathsf{C}\subset\mathsf{C}$ where $\Pi_{v}$ is defined by (8) and $\mathsf{C}$ is given in 1.

Appendix B in Appendix B justifies the definition of the operator $\mathcal{A}$,

To establish this result, we make use of classical results on unbounded operators in Hilbert spaces which for completeness, are given in Appendix B.

For any $f\in\mathsf{D}$, since $\Pi_{v}\mathcal{T}\Pi_{v}f=0$, (35) becomes

Therefore, we get for any $f\in\mathsf{D}$,

The main result of can be formulated under the following abstract assumption, which we shall assume to hold from now on, and the proof of our main theorem relies on optimized estimates of the constants involved.

Let $\mathsf{C}$ be as in 1. Assume further that it satisfies 2 and the following conditions

there exists $\lambda_{v}>0$ satisfying for any $f\in\mathsf{C}$

there exists $\lambda_{x}\in\left(0,1\right)$ satisfying for any $f\in\mathsf{C}$

there exists $R_{0}\geq 0$ satisfying for any $f\in\mathsf{C}$

for any $f\in\mathsf{C}$, $\Pi_{v}\mathcal{T}\Pi_{v}f=0$;

finally, $\operatorname{Ran}(\Pi_{v})\subset\operatorname{Ker}(\mathcal{S}^{\star})$.

so that $A(\epsilon_{0})<+\infty$ is well defined. In addition, if $R_{0}\geq 2$ then $\epsilon_{0}<3\lambda_{x}/(4\lambda_{x}+R_{0}^{2})$.

Second, using that $\Pi_{v}\overline{\mathcal{A}}=\overline{\mathcal{A}}$ by Section 3.1-(b) and (52), we have for any $g\in\mathsf{C}$,

where $\{\mathscr{F}_{i}\,:\,i\in\{1,2,3\}\}$ are defined in (50). Then by Section 3.1, we obtain that for any $t>0$,

is the smallest eigenvalue of the symmetric matrix, positive for $0\leq\varepsilon\leq 4\lambda_{x}\lambda_{v}m_{2}^{{\nicefrac{{1}}{{2}}}}/(4\lambda_{x}+R_{0}^{2})$ from Appendix A in Appendix A (as $\lambda_{x}\leq 1$ by 3-(b)). Using (49), we get

For notational simplicity we let $\epsilon=\varepsilon/(\lambda_{v}m_{2}^{\nicefrac{{1}}{{2}}})$ and note that with the definitions in (45)-(46), for $\epsilon<4\lambda_{x}/(4\lambda_{x}+R_{0}^{2})$, $\alpha(\epsilon)=\alpha_{0}(\varepsilon)>0$ and $\lambda_{v}m_{2}^{\nicefrac{{1}}{{2}}}\Lambda(\epsilon)=\Lambda_{0}(\varepsilon)>0$, and for $\epsilon\leq(2^{{\nicefrac{{1}}{{2}}}}\lambda_{v})^{-1}$ the two norms are equivalent and $A(\epsilon)=C_{0}(\varepsilon)$ is well defined. This concludes the proof of (a).

From Appendix A and associated notation in Appendix A, $\epsilon\mapsto\alpha(\epsilon)$ has a unique, but intractable, maximum, $\epsilon^{\star}\in(0,4\lambda_{x}/(4\lambda_{x}+R_{0}^{2}))$. However from Appendix A-(b) and Appendix A the unique maximum $\epsilon_{0}\in(\epsilon^{\star},4\lambda_{x}/(4\lambda_{x}+R_{0}^{2}))$ of $\epsilon\mapsto\Lambda(\epsilon)$, defined by (187), provides us with a tractable proxy such that $\alpha(\epsilon_{0})<\alpha(\epsilon^{\star})<3\alpha(\epsilon_{0})$. In addition, since $\lambda_{x}\leq 1$ and for $2^{\nicefrac{{1}}{{2}}}R_{0}\geq\lambda_{v}$ we get

which implies that $A(\epsilon_{0})$ is well defined (and the two norms equivalent). The last statement follows from Appendix A-(c) in Appendix A.

The following lemma provides us with simple estimates of $\alpha(\epsilon_{0})$ and $A(\epsilon_{0})$ defined in Theorem 4.

Let $\epsilon\mapsto\alpha(\epsilon),A(\epsilon)$ and $\epsilon_{0}$ be as in Theorem 4 and let $\lambda_{x}\in\left(0,1\right)$. Then

for any $R_{0}\geq 4+12^{{\nicefrac{{1}}{{2}}}}$,

for any $R_{0}\geq(4+12^{{\nicefrac{{1}}{{2}}}})\vee(\lambda_{v}/2^{{\nicefrac{{1}}{{2}}}})$,

2 DMS for PDMP: generic results

Using that $\sum_{k=0}^{K}F_{k}=\nabla_{x}U$ by 2-(b) and that $\lambda_{k}(x,v)-\lambda_{k}(x,-v)=v^{\top}F_{k}(x)$ for any $k\in\{1,\ldots,K\}$ and $(x,v)\in\mathsf{E}$ by 3, concludes the proof.

Note that the symmetric parts of $\mathcal{L}_{i}$ for $i\in\{1,2\}$ are the same and equal to $\mathcal{S}$.

We define the directional derivative operator

where we have used the definition of $\Pi_{v}$ (8) in the last step.

Establishing 3-(a) (referred to as microscopic coercivity in ) for the processes considered is fairly straightforward in the present framework.

The following lemma establishes equivalence between 3-(b) and the Poincaré inequality 1 , which allows one to refer to the expansive body of literature on the topic and implies dependence on the properties of the potential $U$ only.

In addition by [51, Theorem 5.1.9], $({\mathcal{D}\Pi_{v}})^{\star}\overline{\mathcal{D}\Pi_{v}}$ is a self-adjoint operator. These results and (92) imply that $\operatorname{Spec}(m_{2}^{-1}({\mathcal{D}\Pi_{v}})^{\star}\overline{\mathcal{D}\Pi_{v}})\subseteq\left[C_{\operatorname{P}},\infty\right)$ by [16, Theorem 4.3.1].

On the other hand, since by Section 3.2-(a), $\overline{\mathcal{D}\Pi_{v}}=\overline{{\mathcal{T}_{i}\Pi_{v}}}$, we have $(\mathcal{D}\Pi_{v})^{\star}=({\mathcal{T}_{i}\Pi_{v}})^{\star}$ and

In the scenarios considered here, condition 3-(c) relies on estimates of $\left\|u_{f}\right\|_{2}$, $\left\|\nabla_{x}u_{f}\right\|_{2}$ and $\left\|\nabla_{x}^{2}u_{f}\right\|_{2}$ which are obtained by noticing that by definition $u_{f}$ is solution of the following partial differential equation

In the next section, we show how general, but potentially rough, estimates can be obtained, while in Section 5 we show how tighter bounds can be obtained in specific scenarios where we can take advantage of the structure at hand, in particular when interested in the scaling properties of the algorithm with $d$.

3 Computation of R0R_{0} in the general setting

with $\mathbf{G}$ given for any $(x,v)\in\mathsf{E}$ by

We only consider the case $i=2$ since the case $i=1$ is obtained by taking $F_{0}=0$.

The proof is completed upon using the Cauchy-Schwarz inequality.

A general, but potentially rough, bound on the right hand side of (108) can be obtained as follows. From the fact that $\left\|{\rm diag}(\mathbf{M})\right\|_{2}\leq\left\|\mathbf{M}\right\|_{2}$, it holds that

Specific scenarios lead to simplifications of these bounds and the bounds in Lemma 5.1:

from Section D.1 in Section D.1, for radial distributions $m_{4}=m_{2,2}$ leading to a simplification of this bound,

further if $\nu$ is the centred normal distribution of covariance $m_{2}\operatorname{I}_{d}$, then $m_{2,2}=m_{2}^{2}$, leading to further simplifications,

if $K=0$, and hence $F_{0}=\nabla_{x}U$, the scenario considered by , then one finds that the bound depends on $\left\|\nabla_{x}^{2}u_{f}\right\|_{2}$ only.

We proceed as in the proof of Section 3.3. We only consider the case $i=2$ since the case $i=1$ is obtained by taking $F_{0}=0$.

The proof is completed upon using the Cauchy-Schwarz inequality.

(b) Notice that for any $(x,v)\in\mathsf{E}$,

Combining this result and Appendix E, we deduce

Combining Appendix B and Appendix C in Appendix C, by definition of $u_{f}$ in (97) and using 6, we obtain that

Postponed proofs

where we have used that $\left\|\nabla_{x}^{2}u_{f}\right\|_{2}\leq m_{2}^{-1}\kappa_{1}\left\|\Pi_{v}f\right\|_{2}$ by Appendix C in Appendix C and Section 3.3, with $\kappa_{1}$ and $\kappa_{2}$ given in (226) and (233) respectively. The proof of 3-(c) is then completed using Section 3.3-(a) and Section 3.3-(a).

2 Proof of Section 3.1

Using that $t\mapsto(1+t)/\big[(1+t)^{2}+R_{0}^{2}\big]$ is nondecreasing on $\left(0,1\right)$ since $R_{0}\geq 4$, we obtain that for any $R_{0}\geq 4+2\sqrt{3}$, (64) is satisfied.

Since for any $a>0$, $s\mapsto(s+a)/(s-a)$ for $s>a$ is nonincreasing, we deduce from above that for $R_{0}\geq(4+2\sqrt{3})\vee(\lambda_{v}/2^{{\nicefrac{{1}}{{2}}}})$,

For the second part of the statement, first note that

where $b_{\Lambda}(\epsilon)=\big[4\lambda_{x}(1-\epsilon)-\epsilon R_{0}^{2}\big]/[1-\epsilon(1-\lambda_{x})]^{2}\in\left[0,\epsilon^{-1}\right]$ for $\epsilon\leq(2^{\nicefrac{{1}}{{2}}}\lambda_{v})^{-1}\wedge\{4\lambda_{x}/(4\lambda_{x}+R_{0}^{2})\}$. Using that for any $a\in\left[0,1\right]$, $a/2\leq 1-(1-a)^{1/2}\leq a$ we deduce that for $\epsilon\leq(2^{\nicefrac{{1}}{{2}}}\lambda_{v})^{-1}\wedge\{4\lambda_{x}/(4\lambda_{x}+R_{0}^{2})\}$,

Further for $R_{0}\geq(4+2\sqrt{3})\vee(\lambda_{v}/2^{{\nicefrac{{1}}{{2}}}})$ we have $\epsilon_{0}\leq(2^{\nicefrac{{1}}{{2}}}\lambda_{v})^{-1}\wedge\{3\lambda_{x}/(4\lambda_{x}+R_{0}^{2})\}$ from Theorem 4-(b), leading to

where we have used that $\lambda_{x}\leq 1$ for the last inequality. Finally we note that from (64)

where the leftmost inequality follows from the fact that for $2^{\nicefrac{{1}}{{2}}}R_{0}\geq\lambda_{v}$

3 Proof of Theorem 2

Since $\lambda_{v}=\underline{\lambda}$ and $R_{0}\geq(4+2\sqrt{3})\vee(\underline{\lambda}/2^{{\nicefrac{{1}}{{2}}}})$ by Theorem 1, from Theorem 4 and Section 3.1, $A<3^{{\nicefrac{{1}}{{2}}}}$ while with $\lambda_{x}=C_{\operatorname{P}}/(1+C_{\operatorname{P}})$

By (27), if $c_{1},c_{2},\left\|a\right\|_{\infty},m_{b}$ are fixed, there exist $C^{R}_{1}(C_{\operatorname{P}},c_{1},c_{2},\left\|a\right\|_{\infty},m_{b})>0$, independent of $d,\underline{\lambda}$, $c_{\lambda}$, $C_{\varphi}$ and $c_{\varphi}$ such that

where $\overline{R}_{1}=c_{\varphi}K+(1+C_{\varphi})d^{(1+\varpi)/2}K+\underline{\lambda}(1+c_{\lambda}d^{(1+\varpi)/2})$. Combining this bound with (132) concludes the proof. ∎

The Zig-Zag sampler–optimization

In the next two subsections we first consider general velocity distributions and then show how our results can be specialized to the scenario where $\mathsf{V}=\{-m_{2}^{\nicefrac{{1}}{{2}}},+m_{2}^{\nicefrac{{1}}{{2}}}\}^{d}$ for $m_{2}>0$ and $\nu$ is the uniform distribution on $\mathsf{V}$.

Then, Theorem 4 holds with $\lambda_{x}$ as in (90), $\lambda_{v}=\underline{\lambda}$ and

which is itself implied by $\overline{c}_{1}\operatorname{Id}\succeq{\rm diag}(\nabla_{x}^{2}U(x))$ for all $x\in\mathsf{X}$, since the matrix ${\rm diag}(\nabla_{x}^{2}U(x))$ is symmetric. Note that this is the case when for all $x\in\mathsf{X}$, $|{\rm diag}(\nabla_{x}^{2}U(x))|\leq\overline{c}_{1}$ or $|\nabla_{x}^{2}U(x)|\leq\overline{c}_{1}$, for example.

The proof is very similar to that of Theorem 1 and follows from the application of Theorem 4 and the following lemmas whose proofs can be found in Section 5.3.

The proof is then completed by Section 3.3-(a) and Section 3.3-(a). ∎

We discuss in the following the dependence on the dimension of the convergence rate $\alpha(\epsilon_{0})$ and the constant $A(\epsilon_{0})$ given by Theorem 4 based on the constant provided by Theorem 17. Similarly to the general case, we need to impose some conditions on $m_{2}$ and $m_{4}$. Here, we assume that $m_{4}^{1/2}/m_{2}$ does not depend on $d$, which holds in the case where $\nu$ is the uniform distribution on $\mathsf{V}=\{-1,1\}^{d}$ or the $d$-dimensional zero-mean Gaussian distribution with covariance matrix $\operatorname{I}_{d}$.

Consider now the case where the potential $U$ is strongly convex and gradient Lipschitz, i.e. there exist $m,L>0$ such that $m\operatorname{I}_{d}\preceq\nabla_{x}^{2}U(x)\preceq L\operatorname{I}_{d}$ for any $x\in\mathsf{X}$. Then, since for any $i\in\{1,\ldots,d\}$ and $x\in\mathsf{X}$, $\partial_{x_{i},x_{i}}U(x)=\mathbf{e}_{i}^{\top}\nabla_{x}^{2}U(x)\mathbf{e}_{i}\leq L$ by assumption, Section 5.1 implies that (136) holds for $c_{3}=L-m$. In addition, 1 holds with $c_{1}=0$ and $c_{2}=L$ and by [4, Proposition 5.1.3, Corollary 5.7.2], $U$ satisfies (14) with $C_{\operatorname{P}}=m$. Then, the convergence rate $\alpha(\varepsilon_{0})$ and the constant $A(\varepsilon_{0})$ in Theorem 4 do not depend on the dimension but only on $L$, $m$, $\underline{\lambda}$ and $\overline{\lambda}$. In addition, we observe that the larger $L-m$ is, the larger $R_{0}$ given in (137) is, which in turn make the convergence rate $\alpha(\varepsilon_{0})$ worse since it is of order $\mathcal{O}(1/R_{0}^{2})$ as $R_{0}\to+\infty$ by Section 3.1. This result is expected in the Gaussian case $U(x)=x^{\top}\Sigma x$ for any $x\in\mathsf{X}$, since $L-m$ is the diameter of the set of eigenvalues of $\Sigma$ which is a characterization of the conditioning of the problem.

2 dd-dimensional Radmacher distribution

We now consider the case $\mathsf{V}=\{-m_{2}^{{\nicefrac{{1}}{{2}}}},+m_{2}^{{\nicefrac{{1}}{{2}}}}\}^{d}$ and $\nu$ is the uniform distribution on $\mathsf{V}$ which corresponds to the original setting of the Zig-Zag process. This process has been proved to be ergodic even in the absence of refreshment, that is $\lambda_{\rm ref}=0$. We note that in this scenario $m_{4}=m_{2}^{2}/3$ and $m_{2,2}=m_{2}^{2}$ which leads to simplified expressions for the bounds in Section 5.1 and Section 5.1 upon revisiting their proofs. However this has no qualitative impact. In this section we show that hypocoercivity holds with our techniques for $\lambda_{\rm ref}(x)=0$ for “most of $\mathsf{X}$” for a particular type of partial refreshment update.

In other words 3-(a) holds if for any $\varepsilon>0$, for all $k\in\{1,\ldots,d\}$, $\lambda_{{\rm ref},k}$ vanishes everywhere, except on $\{x\in\mathsf{X}\,:\,\exists k\in\{1,\ldots,d\}\mid|\partial_{x_{k}}U|(x)<\varepsilon\}$. We also note that a similar result holds for the case where $\mathcal{R}_{v}=\Pi_{v}-\operatorname{Id}$, that is 3-(a) holds whenever $\lambda_{\rm ref}$ vanishes everywhere, except on $\{x\in\mathsf{X}\,:\,\exists k\in\{1,\ldots,d\},\,\mid|\partial_{x_{k}}U|(x)<\varepsilon\}$ for $\varepsilon>0$.

3 Postponed proofs

To bound the sum we note that for $k\in\{1,\ldots,d\}$ $\partial_{x_{k}}U\partial_{x_{k}}u_{f}=\partial_{x_{k}}^{2}u_{f}+\partial_{x_{k}}^{*}\partial_{x_{k}}u_{f}$ by Appendix C-(a), which together with the fact $(a+b)^{2}\leq 2(a^{2}+b^{2})$ leads to

Then, using that for $a,b\geq 0$ $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ twice and (176), we deduce

Then combining (164) and (166) completes the proof by Section 3.3-(b). ∎

Since $\left\|\mathbf{M}\right\|_{2}^{2}=\left\|{\rm diag}(\mathbf{M})\right\|_{2}^{2}+\left\|\mathbf{M}-{\rm diag}(\mathbf{M})\right\|_{2}^{2}$, we obtain

We now bound $\left\|{\rm diag}(\mathbf{M})\right\|_{2}^{2}$. First, we apply the triangle inequality and use Appendix C-(a), to deduce that

These identities and the condition (136) imply

From this inequality, (169) and Section 3.3-(b), we deduce

since for $a,b,c\geq 0$, $a^{2}+b^{2}+c^{2}\leq(a+b+c)^{2}$. ∎

Discussion and link to earlier work

An advantage of our approach is that it provides explicit and relatively simple bounds in terms of interpretable quantities which, we show, are informative, and is in contrast with those on minorization and drift conditions in most scenarios. One exception is the study of BPS on the torus carried out in for $U=0$, using an appropriate coupling argument, which leads to a rate of convergence for the total variation distance with a favourable $\Theta(d^{1/2})$ scaling. Although we have shown that for the Zig-Zag sampler with Rademacher distribution $\lambda_{\rm ref}$ is not required to be bounded away from zero on $\mathsf{X}$, the results of hold with $\lambda_{\rm ref}=0$. It would be interesting to further investigate whether our results can be specialized to consider the scenario $\lambda_{\rm ref}=0$.

Appendix A Optimization and estimates of the rate of convergence α⁡(ϵ)\alpha(\epsilon)

$\Lambda(\epsilon)\geq 0$ for $\epsilon\in\left[0,4\lambda_{x}/(4\lambda_{x}+R_{0}^{2})\right]$ and $\Lambda(0)=0$.

From (46) we see that $\Lambda(\epsilon)\geq 0$ requires

where the equality follows from $\lambda_{x}>0$, which completes the proof of (a). The proof of (b) is a simple calculation and is omitted. We now show (c). If we set $\Lambda^{\prime}(\epsilon)=0$, it implies that $\epsilon>0$ satisfies

and imposes the condition $(1+\lambda_{x})-\epsilon R_{1}^{2}\geq 0$ so

Squaring both sides of (189) implies the following sequence of equalities using (182)

where the inequality follows from $\lambda_{x}>0$ and $R_{0}>0$. Further

and since $\lambda_{x}\leq 1$, this yields the simplified expression for the two roots

From the conditions on $\epsilon$ given by (a) and (190), and the fact that $\lambda_{x}\leq 1$, we retain $\epsilon_{0}=\epsilon_{-}$ only. The last statement follows from the second statement and the fact that $\Lambda^{\prime}$ is continuous. ∎

The following lemma establishes in particular that $\epsilon_{0}$ is a global maximum.

for any $\epsilon>0$, $\Lambda^{\prime\prime}(\epsilon)<0$ (implying concavity),

$\Lambda$ is maximized at $\epsilon_{0}$ defined by (187) and $0<\epsilon_{0}\leq(4\lambda_{x})/(4\lambda_{x}+R_{0}^{2})$.

If in addition $R_{0}\geq 2$, $\epsilon_{0}\leq 3\lambda_{x}/(4\lambda_{x}+R_{0}^{2})$.

We differentiate $\epsilon\mapsto-2\Lambda(\epsilon)=-[1-\epsilon(1-\lambda_{x})]+R^{{\nicefrac{{1}}{{2}}}}(\epsilon)$ twice, yielding the first order derivative

Now from (182), $R(\epsilon)=a\psi(\epsilon)$ with $\psi(\epsilon)=(\epsilon-b)^{2}+c$ with all constants $b,c$ non-negative. Further $\psi^{\prime}(\epsilon)=2(\epsilon-b)$ and $\psi^{\prime\prime}(\epsilon)=2$ and therefore

which implies that $\Lambda^{\prime\prime}(\epsilon)\leq 0$ for any $\epsilon\geq 0$.

From the concavity we deduce that $\epsilon_{0}$ is a maximum, and the inequality on $\epsilon_{0}$ follows from the fact that this is required for $\Lambda(\epsilon_{0})\geq 0$.

Using that for any $s\geq 0$, $(1+s)^{{\nicefrac{{1}}{{2}}}}\leq 1+s/2$, and $4\lambda_{x}\leq(1+\lambda_{x})^{2}$, we get that

The assumption $R_{0}\geq 2$ completes the proof.

First note that for any $\epsilon\geq 0$,

Then from Appendix A, for any $\epsilon\geq 0$

Now if we use $2^{\nicefrac{{1}}{{2}}}R_{0}\geq\lambda_{v}$ we have by (187) that

Appendix B Some results on closed operators on Hilbert spaces

In this section we gather classical results concerning densely defined closed operators on a Hilbert space to which we repeatedly refer throughout the manuscript.

We start this section with a well-know result regarding the closure of anti-symmetric operators, for which a proof is given for completeness.

Let $\mathcal{B}$ be a closed and densely defined operator on a Hilbert space $\mathsf{H}$ of inner product $\left\langle\cdot,\cdot\right\rangle$, induced norm $\left\|\cdot\right\|$ and operator norm \left\vvvert\cdot\right\vvvert.

$\mathcal{B}^{\star}\mathcal{B}(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}$ is a bounded operator on $\mathsf{H}$ which satisfies

Note that under the condition of Appendix B, we get that $(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}\mathcal{B}^{\star}$ can be extended to a bounded operator and

(a) and (b) follow from [51, Theorem 5.1.9] and inspection of the proof. We now show (c).

First note that $(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B}-\operatorname{Id})(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}=\operatorname{Id}-(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}$, from which we deduce that it is a self-adjoint and bounded operator by the triangle inequality with norm less or equal than $2$. To prove the tighter upper bound we use [51, Proposition 3.2.27 p. 99] (twice), the identity for any $h\in\mathsf{H}$

that $(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}$ is positive and $\vvvert(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}\vvvert\leq 1$ from the first statement.

which implies that $\{(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}\mathcal{B}^{\star}\}^{\star}=\mathcal{B}(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}$. Therefore, the operator $\{(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}\mathcal{B}^{\star}\}^{**}$ is bounded on $\mathsf{H}$. The proof then follows by [51, Theorem 5.1.5] which implies that $(\operatorname{Id}+\mathcal{B}^{\star}\mathcal{B})^{-1}\mathcal{B}^{\star}$ is closable and

A similar result can be obtained by using that $\mathcal{B}$ is closable only, as a consequence of the following lemma.

This result is a just a consequence of [51, Theorem 5.1.5] which implies that $\mathcal{B}^{\star}$ is densely defined, $\overline{\mathcal{B}}=(\mathcal{B}^{\star})^{\star}$ and $\mathcal{B}^{\star}=\overline{\mathcal{B}}^{\,\star}$. ∎

We conclude this section by the following results which can be found in .

Appendix C Elliptic regularity estimates

The proof just follows by integration by parts. ∎

From the definition of $u$, using Appendix B and 1-(a) we conclude that

From this result and (236), it follows that

Rearranging terms and setting $\varepsilon=1/4$ completes the proof. The last statement is a direct consequence of the first one using the definition of $W$ in (231). ∎

Putting this with Proposition C, this implies the following.

where $a_{k}$, $W$, $\kappa_{1}$ and $\kappa_{2}$ are defined by (17), (231), (226) and (233) respectively.

Therefore using Appendix C and Appendix C successively, we obtain

Appendix D Supplementary material

We use the polar parametrization of the multivariate normal distribution. Let

$\phi\in[0,\uppi]^{d-2}\times[0,2\uppi]$. The probability distribution for $\phi$ ensuring uniformity of $v(\phi)$ on the surface of the $d$-sphere has density

and the latter term vanishes when the leftmost term does. We also deduce that

Appendix E Expectation of quadratic forms of the velocity

This section provides expressions for second order moments of quadratic forms of $v$ for a large class of distributions for which we could not find adequate references.

whenever $\operatorname{card}(\{i,j,k,l\})>2$.

where $\odot$ denotes the Hadamard product.

Using that $M$ is symmetric, and the expectation symbol for expectations with respect to $\nu$,

Assume that the potential $U$ is defined for any $x\in\mathsf{X}$ by $U(x)=\sum_{i=1}^{d}\big(1+x_{i}^{2}\big)^{\beta}/2$, for $\beta\geq 1$. Then $U$ is strongly convex and there exists $c_{2}>0$, dependent on $\beta$ only, such that (15) is satisfied with $\varpi=0$.

We have for $i,j\in\{1,\ldots,d\}$ and $x\in\mathsf{X}$,

which with $c\geq(2\beta^{-{\nicefrac{{1}}{{2}}}})\vee 2^{1/\beta}$ completes the proof.

Assume that the potential $U$ is defined for any $x\in\mathsf{X}$ by $U(x)=(1+|x|^{2})^{\beta}$ with $\beta\geq 1$. Then $U$ is strongly convex and there exists $c_{2}>0$, dependent on $\beta$ only, such that (15) is satisfied with $\varpi=1-1/\beta$.

from which we conclude that for any $x\in\mathsf{X}$, $\nabla_{x}^{2}U(x)\succeq 2\beta\operatorname{I}_{d}$. It remains to show that (15) holds. First we have for any $x\in\mathsf{X}$,

where we used in the last step which completes the proof, that $(a+b)^{\beta-1}\leq 2^{\beta-2}(a^{\beta-1}+b^{\beta-1})$ for any $a,b\geq 0$, applying Hölder inequality, since $\beta\geq 1$. ∎

Acknowledgments

JR would like to thank Pierre Monmarché for showing him how ZZ and BPS fall under a general framework. CA acknowledges support from EPSRC “Intractable Likelihood: New Challenges from Modern Applications (ILike)” (EP/K014463/1). All the authors acknowledge the support of the Institute for Statistical Science in Bristol. AD acknowledges support from the Chaire BayeScale “P. Laffitte”.

References