Geometric ergodicity of the bouncy particle sampler

Introduction

From a numerical point of view, an advantage of these continuous-time processes is that, under appropriate conditions on the potential $U$, an exact simulation is possible, following a thinning strategy . Therefore, no discretization schemes are needed to approximate the continuous time trajectory, contrary to Langevin diffusions or Hamiltonian dynamics. As a consequence, no Metropolis filter is necessary to preserve the invariance of $\pi$, see and the reference therein.

This work deals with the velocity jump process introduced in . Following , we refer to it as the Bouncy Particle Sampler (BPS). The aim of this paper is to establish geometric convergence to equilibrium for the BPS in dimension larger than 1. As detailed below, we relax the conditions of , in particular we show that any constant refreshment rate is sufficient for thin tail target distributions. The paper is organized as follows. Section 2.2 presents the BPS process and our main results, which are proven in Section 3. Finally, Section 4 is devoted to a discussion on our result and approach. First, in Section 4.1, we give explicit bound for a toy model, paying a particular attention to the dependency on the dimension of the state space in the constants we get. Second, in Section 4.2, we apply our results to study the annealing algorithm based on the BPS, extending the results of . Some technical proofs are postponed to an Appendix.

Although the work is restricted to the BPS, our arguments can easily be adapted to other velocity jump processes, such as randomized variants of the BPS. In particular, the coupling argument in Section 3.3 applies as soon as the process admits a refreshment mechanism.

In the sequel, we take the convention that $\inf\emptyset=+\infty$.

Geometric convergence of the BPS

Set $S_{n+1}=S_{n}+T_{n+1}$, $(X_{t},Y_{t})=(X_{S_{n}}+tY_{S_{n}},Y_{S_{n}})$, for all $t\in[S_{n},S_{n+1})$, $X_{S_{n+1}}=X_{S_{n}}+T_{n+1}Y_{S_{n}}$ and

If $T_{n+1}=T_{n+1}^{(1)}$, we say that, at time $T_{n+1}$, the velocity has been refreshed, and we call $T_{n+1}$ a refreshment time. If $T_{n+1}=T_{n+1}^{(2)}$, we say that, at time $T_{n+1}$, the process has bounced, and we call $T_{n+1}$ a bounce time.

2. Main results

We state in this section our main results regarding the $V$-uniform geometric ergodicity of the BPS.

Our basic assumptions to prove geometric ergodicity are the following.

Consider the following alternative conditions, which will be used in the case where $\mathsf{Y}$ is bounded.

There exists $\varsigma\in\left(0,1\right)$ such that

The potential $U$ satisfies $\lim_{\left\|x\right\|\to+\infty}\left\|\nabla^{2}U(x)\right\|/\left\|\nabla U(x)\right\|=0$ and there exists $\varsigma\in\left(0,1\right)$ such that

In that case 4 is satisfied if and only if $\left[(\alpha\vee\beta)/2,\alpha\wedge\beta\right]\neq\emptyset$, while 5 is satisfied if and only if $\left[2(\alpha\vee\beta)/(1+\alpha\vee\beta),\alpha\wedge\beta\right]\neq\emptyset$, chosing in both cases $\varsigma^{-1}>1$ in the corresponding interval. In particular, if both $\alpha,\beta\geqslant 2$, then 5 is satisfied, but 4 may not (if $\alpha>2\beta$ for instance). On the contrary if, say, $\alpha=4/3$ and $\beta\in(1,8/7)$, then 4 holds while 5 does not.

Note that 3, 4 and 5 all require that $\lim_{\left\|x\right\|\to+\infty}\left\|\nabla U(x)\right\|=+\infty$. We consider now the case where $\liminf_{\left\|x\right\|\to+\infty}\left\|\nabla U(x)\right\|<+\infty$ possibly.

In the case where $\mathsf{Y}$ is unbounded, 4 must be strengthen as follow.

There exists $\varsigma\in\left(0,1\right)$ such that

7 (and therefore 4) holds when $U$ is a perturbation of an $\alpha$-homogeneous function:

This class of potentials is considered in [26, Theorem 4.6], which shows that the Random Walk Metropolis algorithm is geometrically ergodic for target distributions $\pi$ associated to a potential belonging to this class.

Finally, [11, Theorem 3.3] deals with thick tail distributions. It consists in applying smooth bijective parametrizations of the space proposed by to get geometric ergodicity of Metropolis-Hastings algorithms for thick tail distributions by transforming the target into a thin tail one. It is in fact a general trick that could also be applied in combination of our results.

As noticed before, Theorem 1, Theorem 2 and Theorem 4 ensue from a more general results, which holds under the following assumption.

Conditions on $U$. The function $\bar{U}$, defined by $\bar{U}=\psi\circ U$, satisfies

Assume 1-2-8. Assume in addition that the following inequalities hold

Note that, under 8, (13) is implied by either one of the two following additional assumptions:

$\lim_{\left\|x\right\|\to+\infty}\left\|\nabla\bar{U}(x)\right\|=+\infty$;

Indeed, if (a) holds, then $c_{1}$ can be chosen as large as necessary while $c_{2},c_{4},c_{3}$ can be held fixed so that (13) is satisfied. If (b) holds, then $c_{2}$ can be chosen as small as necessary while $c_{1},c_{3},c_{4}$ can be held fixed. Finally if (c) holds, then $c_{3}$ can be chosen as large as necessary while $c_{1},c_{2},c_{4}$ can be held fixed.

Proofs of the main results

2. Foster-Lyapunov drift condition

This section is devoted to the proof of a Foster-Lyapunov drift condition for the generator $\mathcal{A}$ given by (19) and the function $V$ defined in (22).

The first step of the proof is to show that there exist $A_{1,1},A_{1,2}>0$ such that

where $\mathsf{A}_{x}\subset\mathsf{Y}$ is defined by (10). In a second step, we show that there exist $A_{2,1},A_{2,2}>0$ such that

Note that if (26) and (27) hold, then the proof is concluded.

The proof of (26) follows upon noting that $\kappa\leqslant 1$ and that $\varphi$ is bounded by $1+c$, so that $V(x,y)\leqslant(2+c)\exp(H(\left\|y\right\|))$ if $y\not\in\mathsf{A}_{x}$.

where $C_{2}$ is given by (29) and we have used for the last inequality that $\varphi$ is bounded by $1+c$. This result concludes the proof of (27) for $\left\|x\right\|\geqslant R_{1}$. It remains to consider the case $\left\|x\right\|\leqslant R_{1}$.

Let us now precise the parameters we chose in the definition of $V$. Set

Since $\varepsilon\leqslant a\wedge(c-b)$ by (35), $c-b\leqslant b-a$ by (34) and $b-a\leqslant a/3$ by (32), we have $B_{0}\leqslant 4ac_{4}/(rc_{1})$. Hence, (41) reads

where we have used (33) and (13) for the last inequality.

First, since $c-b\leqslant\delta b/4\leqslant\delta c/4$ and $a\leqslant c$ by (34) and (36), we have

where we used the definition of $\kappa$ (33) and the condition (13) for the last inequality. Combining (44) and (45) in (43), we get

From this result and the fact by (20)-(21) that $1+b+s(c-b)-\varepsilon\leqslant\varphi(s)\leqslant 1+b+s(c-b)+\varepsilon$ and \varphi^{\prime}(s)\leqslant c-b+\varepsilon\text{ fors\in\left(0,1\right)} we get that (38) reads

Therefore, since $\theta(x,y)\in\left(0,1\right)$, to show that

First (49) holds since using that $\varepsilon\leqslant(c-b)$ by (35) and that $a\leqslant c$, we have

Since $\varepsilon\leqslant 1\wedge(\kappa rc_{1}/4)$ by (35), $c-b\leqslant 1$ and $b\leqslant 2$ by (36) and (31), we get

This result, the inequality $b-a\leqslant c$ and the definition of $\kappa$ (33) implies that (51) holds.

where we have used the definition of $\kappa$ given by (33) and $\theta(x,y)\geqslant 0$ for the last inequality.

The proof follows from combining (40)-(42)-(46)-(48)-(52).

where $V$ is given by (22) and $A_{1},A_{2}$ are given by Section 3.2.

Letting $n$ go to infinity concludes the proof since it yields

3. Mirror Coupling

A set $\mathsf{C}$ that satisfies this is called a small set.

Previous works establish Section 3.3 in the case where $\mathsf{Y}=\mathsf{S}^{d}$. The proof relies on the fact that after two refreshment events the distribution of $X_{t}$ has some density w.r.t. the Lebesgue density on a ball with a radius proportional to $t$. Nevertheless, the latter strategy yields a non-explicit rate of convergence. In particular the dependence of the obtained rate in the dimension of the space is either intractable or very rough.

This is clearly implied by Section 3.3. However, in order to get good explicit rates of convergence, it may be more efficient to establish directly a coupling condition, which can then be directly used to obtain quantitative estimates (see for instance Theorem 24 in Appendix B and the exemple in Section 4.1) .

Before stating our main result, we need the following lemma concerning the reflexion coupling (see , and references therein) between two $d$ standard Gaussian random variables with different means.

By the Markov property of the Brownian motion $(W_{t}^{(1)})_{t\geqslant 0}$, since $T_{c}$ is a $(\mathcal{F}^{W}_{t})_{t\geqslant 0}$-stopping time, where $\mathcal{F}^{W}_{t}=\sigma(W^{(1)}_{s},s\leqslant t)$, $W^{(2)}_{t}$ is a Brownian motion. Therefore, $G^{(1)}$ and $G^{(2)}$ are $d$-dimensional standard Gaussian random variables.

and $E_{1},E_{2},E_{3}$ are three independent exponential random variables with parameter $1$.

Before proceeding to its precise definition, let us give a brief and informal description of this coupling (see Figure 1, Figure 2 and Figure 3). We couple both processes to have the same two first refreshment times $H_{1}$ and $H_{2}$. At time $H_{1}$, the Gaussian velocities are chosen according to Section 3.3 so that, in the absence of bounces in the meanwhile, with positive probability, the processes will reach the same position at time $H_{2}$. At time $H_{2}$, both velocities are refreshed with the same Gaussian variable. Hence, with positive probability, at time $H_{2}$, the processes have the same position and same velocity, in which case we can keep them equal for all times $t\geqslant H_{2}$.

Otherwise set $N_{n+2}=N_{n+1}$, $H_{n+2}=H_{n+1}-T_{n+1}$ and

Otherwise set $N_{n+2}=N_{n+1}$, $H_{n+2}=H_{n+1}-T_{n+1}$ and

where $\mathsf{A}=\mathsf{A}_{1}\cap\mathsf{A}_{2}$,

Combining this result with (56) concludes the proof. ∎

Finally, let us detail Section 3.3, in prevision of the low-temperature study of Section 4.2.

4. Proof of Theorem 5

The proof follows from Section 3.2 and Section 3.3, and an application of [35, Theorem 6.1]. However, [35, Theorem 6.1] is non quantitative and for the proofs of Section 4.2 need explicit bounds for the convergence of $(P_{t})_{t\geqslant 0}$ to $\pi$. To this end, we give a quantitative version of Theorem 5 in Appendix B. Quantitative contraction rates for Markov chains based on [24, Theorem 1.2].

5. Proofs of Theorem 1

6. Proof of Theorem 2

7. Proof of Theorem 4

for some $C>0$, hence is bounded. Then, the proof follows the same lines as the proof of Theorem 1 under 4, and is omitted.

Miscellaneous

Following carefully the proofs of Theorem 5, it is possible to get explicit bounds on the values of $C,\rho>0$ such that (5) holds. Nevertheless, the obtained bounds are not sharp. In particular, in Section 3.3, when we try to couple two processes, we do not make any use of the potential $U$. In fact, at this step, $U$ only plays the role of an hindrance in the minorization condition given by Section 3.3 based on Section 3.3-Section 3.3. We try to couple the processes using only the refreshment jumps, and hope that, during this attempt, no bounce occurs. We now illustrate on a toy model how an analysis which is model specific can circumvent this flaw. It shows that the explicit bounds we obtain in Section 3.3 may be far from optimality for some problems.

Note that $\mathsf{D}$ has no boundary and therefore no reflexion has to be take care of but it is worthwhile to mention that by a deterministic transformation of this process from $\mathsf{D}$ to $\left[0,1\right]\times\left[0,\eta\right]^{d-1}$, we end up with the reflected PDMP process targeting the uniform distribution on $\left[0,1\right]\times\left[0,\eta\right]^{d-1}$ described in .

The process that we consider in this section can be seen as a toy model for convex potentials. If $\eta$ is small, which is the analogous of multi-scales problems, then the proof of Theorem 5 would yield a mixing time of order $\eta^{d}$. Indeed, in Section 3.3, the coupling is considered a failure as soon as one of the processes bounce (or, here, is reflected at the boundary). Hence, a successful coupling would need that, at the first refreshment time, the new Gaussian velocity is directed mainly according to the first dimension, which is unlikely. As we will see, this is a too pessimistic bound.

The proof then follows from a straightforward computation. ∎

As a conclusion, for the considered toy model, we get that the rate of convergence scales only as $d^{1/2}$. Note that this result is optimal since the process has unit constant speed and the diameter of $\mathsf{D}$ is $d^{1/2}$.

2. The metastable regime and annealing

Set $S^{(\beta)}_{n+1}=S^{(\beta)}_{n}+T^{(\beta)}_{n+1}$, $(X^{(\beta)}_{t},Y^{(\beta)}_{t})=(X^{(\beta)}_{S^{(\beta)}_{n}}+tY^{(\beta)}_{S^{(\beta)}_{n}},Y^{(\beta)}_{S^{(\beta)}_{n}})$, for all $t\in[S^{(\beta)}_{n},S^{(\beta)}_{n+1})$, $X^{(\beta)}_{S^{(\beta)}_{n+1}}=X^{(\beta)}_{S^{(\beta)}_{n}}+T^{(\beta)}_{n+1}Y^{(\beta)}_{S^{(\beta)}_{n}}$ and

The function $t\mapsto\beta(t)$ is increasing, satisfies $\lim_{t\to+\infty}\beta(t)=+\infty$, $\beta(0)\geqslant 1$ and there exist $s_{0},D_{1},D_{2}>0$ with $D_{1}\geqslant D_{2}$ such that for all $t$ large enough, $\beta(t)\geqslant D_{2}\ln t$ and $\beta(t+s_{0})-\beta(t)\leqslant D_{1}/t$.

where $p=(1-\theta D_{1})\wedge(D_{2}\eta^{\prime})>0$ and $(X^{(\beta)}_{t},Y_{t}^{(\beta)})$ is the annealed BPS process starting from $(x,y)$.

Acknowledgements

Alain Durmus acknowledges support from Chaire BayeScale “P. Laffitte”. Pierre Monmarché acknowledges support from the French ANR project ANR-12-JS01-0006 - PIECE and the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement number 614492. Arnaud Guillin and Pierre Monmarché acknowledge support from the French ANR-17-CE40-0030 - EFI - Entropy, flows, inequalities.

References

Appendix A. Postponed proofs

Since the $U_{1}$ is assumed to be twice continuously differentiable, the proof is finished.

Proof of Theorem 17

First, we establish a Foster-Lyapunov drift condition for $\mathcal{A}_{\beta}$ uniformly on $\beta\geqslant 1$.

Let $V_{1}$ be the function defined by (22). According to Section 3.2, there exist $A_{1},A_{2}>0$ such that

Now, for $\beta\geqslant\beta_{*}$, keeping the notations of Section 3.2,

and for all $t\geqslant 0$ such that $\beta(t)\geqslant\beta_{*}$,

The proof follows the same line as the proof of Section 3.2, using Proof of and $V_{1}/V_{2}$ is bounded above and below by positive constants. ∎

The arguments are exactly those of the proof of Section 3.3, hence of [38, Theorem 5.1], so that we only give a sketch of proof. First, considering the case $\beta=0$, we have already shown in Section 3.3 that, starting from two different points in a given compact $\mathsf{K}$, it is possible to merge two processes in a time $s_{1}>0$ while staying in a compact $\mathsf{K}^{\prime}$, with some probability $\chi>0$. Call $\mathsf{E}$ this event. Then, considering the case $\beta>0$, we follow the same coupling up to the first bounce time. The processes have merged if this first bounce happens after time $s_{1}$, which occurs with probability

where $M=\sup_{(w,z)\in\mathsf{K}^{\prime}}\left\|z\right\|$. ∎

where $Q_{0}$ is the identity kernel and for $k\in\{1,\ldots,n(t)\}$, we set

It is a direct application to $Q_{k}$ for all $k$ of Theorem 24 based on Proof of and Proof of . ∎

For a fixed $\beta\geqslant 0$, let $(P_{t}^{(\beta)})_{t\geqslant 0}$ be the semi-group of the BPS sampler associated with the potential $x\mapsto\beta U(x)$ and, for $t\geqslant t_{0}$ and $k\in\{0,\ldots,\mathbf{n}(t)\}$, let

where for ease of notation simplicity we denote

From (70), for any $t\geqslant t_{0}$, $k\in\{1,\ldots,\mathbf{n}(t)\}$

Assume that the conditions of Theorem 17 hold. Then, there exists $A_{6}>0$ such that for all $t\geqslant t_{0}$, all $k\in\{1,\ldots,\mathbf{n}(t)\}$ and $l\geqslant 1$, there exists $A_{l}>0$ such that

where $\beta_{k}$, $\mathbf{n}$ and $t_{0}$ are defined by (72), (67) and (66) respectively.

Let $t\geqslant t_{0}$, $k\in\{1,\ldots,\mathbf{n}(t)\}$ and $l\geqslant 1$. In the proof, $C$ stands for a constant which may change from line to line but does not depend on $k$, $l$ and $\beta$. We bound

where we used for the two last inequalities that

Similarly, for the second term of (76) we obtain

Combining this bound and (77) in (76), we get that there exists $A_{l,1}\geqslant 0$ such that

where $E$ is a standard exponential random variable independent of $Z$.

Next using Proof of and the Markov property, we get

The proof is concluded combining this result and (79) in (75). ∎

Let $l\geqslant 1$, $t\geqslant t_{0}$ and $k\in\{1,\ldots\mathbf{n}(t)\}$. In the proof, $C$ stands for a constant which may change from line to line but does not depend on $k$, $l$ and $\beta$. Denoting $d_{0}=0$ and $d_{k}=\kappa_{k}d_{k-1}+e_{k}$, (74) reads

with the convention that $\prod_{j=k}^{k-1}\kappa_{j}=1$. From Proof of applied with $l=1/D_{2}$, and bounding

with $q=1-\theta D_{1}/2\in\left(1/2,1\right)$ by assumption. Thus, combining this result and (84) in (83), we get

for all $k_{0}\geqslant 1$. In particular, for $k_{0}\geqslant(2/C)^{1/(1-q)}$, this means $I(k)\leqslant Ck^{1/2-q}$.

Finally, from the first part Proof of , $u_{0}\leqslant CV_{1}(x,y)$. ∎

Let $t>t_{0}$, $n=\mathbf{n}(t)$, $\eta>\eta^{\prime}>0$. In the proof, $C$ stands for a constant which may change from line to line but does not depend on $n$, $\eta,\eta^{\prime},t$ and $\beta$. First,

We conclude, with Proof of and the first part of Proof of , by

Appendix B. Quantitative contraction rates for Markov chains

and consider the weighted $V$-norm on $\mathcal{P}_{V}(\mathsf{M})=\{\mu\in\mathcal{P}(\mathsf{M})\,:\,\mu(V)<\infty\}$, defined for $\mu_{1},\mu_{2}\in\mathcal{P}_{V}(\mathsf{M})$ by

Suppose that there exist $\alpha,\gamma\in(0,1)$, $C_{1}>0$ and $C_{2}>2C_{1}$ such that for all $x,y,z\in\mathsf{M}$, $V(x)+V(y)\leqslant C_{2}$,

Then there exists $\zeta>0$ and $\kappa\in\left(0,1\right)$ such that for all $\mu_{1},\mu_{2}\in\mathcal{P}_{V}(\mathsf{M})$,

where $\rho_{\zeta}$ is defined by (85). More precisely, if $C_{2}=4C_{1}$, then this holds with

where $\rho_{\zeta}$ is defined by (69) and

Let $\varphi$ be a measurable function such that $|\varphi|_{\zeta}=\|\varphi\|_{\zeta,V}=1$. We aim to show that $|Q\varphi|_{\zeta}\leqslant\kappa$ or, in other words, that

First, consider the case where $V(x)+V(y)\geqslant C_{2}$. For $\zeta>0$, set $\kappa_{1}=\gamma+(1-\gamma)\frac{1+\zeta C_{1}}{1+\zeta C_{2}/2}$. Note that $\gamma<\kappa_{1}<1$, and

Second, consider the case where $V(x)+V(y)\leqslant C_{2}$. Let $(Z_{x},Z_{y})$ be an optimal coupling of $Q(x,\cdot)$ and $Q(y,\cdot)$. Then, writing $\kappa_{2}=(1-\alpha+\zeta C_{1}(1-\gamma)/2)\vee\gamma$ (which is smaller than 1 for $\zeta$ small enough),

For $C_{2}=4C_{1}$, we chose $\zeta=\frac{\alpha}{(1-\gamma)C_{1}}$, so that $\kappa_{2}=1-\alpha/2$ and

Remark that, under the same assumptions that Theorem 24 but with $\alpha=0$, the same proof yields, for all $\zeta>0$ and all $\mu_{1},\mu_{2}\in\mathcal{P}_{V}(\mathsf{M})$,