Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm

Introduction

where $(B_{t}^{d})_{t\geq 0}$ is a $d$-dimensional Brownian motion. It is well-known that the Markov semi-group associated with the Langevin diffusion $(Y_{t})_{t\geq 0}$ is reversible w.r.t. $\pi$. Under suitable conditions, the convergence to $\pi$ takes place at geometric rate. Precise quantitative estimates of the rate of convergence with explicit dependency on the dimension $d$ of the state space have been recently obtained using either functional inequalities such as Poincaré and log-Sobolev inequalities (see ) or by coupling techniques (see ). The Euler-Maruyama discretization scheme associated to the Langevin diffusion yields the discrete time-Markov chain given by

where $(Z_{k})_{k\geq 1}$ is an i.i.d. sequence of standard Gaussian $d$-dimensional random vectors and $(\gamma_{k})_{k\geq 1}$ is a sequence of step sizes, which can either be held constant or be chosen to decrease to . The idea of using the Markov chain $(X_{k})_{k\geq 0}$ to sample approximately from the target $\pi$ has been first introduced in the physics literature by and popularised in the computational statistics community by and . It has been studied in depth by , which proposed to use a Metropolis-Hastings step at each iteration to enforce reversibility w.r.t. $\pi$ leading to the Metropolis Adjusted Langevin Algorithm (MALA). They coin the term unadjusted Langevin algorithm (ULA) when the Metropolis-Hastings step is skipped.

The purpose of this paper is to study the convergence of the ULA algorithm. The emphasis is put on non-asymptotic computable bounds; we pay a particular attention to the way these bounds scale with the dimension $d$ and constants characterizing the smoothness and curvature of the potential $U$. Our study covers both constant and decreasing step sizes and we analyse both the ”finite horizon” (where the total number of simulations is specified before running the algorithm) and ”any-time” settings (where the algorithm can be stopped after any iteration).

When the step size $\gamma_{k}=\gamma$ is constant, under appropriate conditions (see ), the Markov chain $(X_{n})_{n\geq 0}$ is $V$-uniformly geometrically ergodic with a stationary distribution $\pi_{\gamma}$. With few exceptions, the stationary distribution $\pi_{\gamma}$ is different from the target $\pi$. If the step size $\gamma$ is small enough, then the stationary distribution of this chain is in some sense close to $\pi$. We provide non-asymptotic bounds of the $V$-total variation distance between $\pi_{\gamma}$ and $\pi$, with explicit dependence on the step size $\gamma$ and the dimension $d$. Our results complete and extend the recent works by and .

When $(\gamma_{k})_{k\geq 1}$ decreases to zero, then $(X_{k})_{k\geq 0}$ is a non-homogeneous Markov chain. If in addition $\sum_{k=1}^{\infty}\gamma_{k}=\infty$, we show that the marginal distribution of this non-homogeneous chain converges, under some mild additional conditions, to the target distribution $\pi$, and provide explicit bounds for the convergence. Compared to the related works by , , and , we establish not only the weak convergence of the weighted empirical measure of the path to the target distribution but a much stronger convergence in total variation, similarly to , where the strongly log-concave case is considered.

The paper is organized as follows. In Section 2, the main convergence results are stated under abstract assumptions. We then specialize in Section 3 these results to different classes of densities. The proofs are gathered in Section 4. Some general convergence results for diffusions based on reflection coupling, which are of independent interest, are stated in Section 5.

General conditions for the convergence of ULA

In this section, we derive a bound on the convergence of the ULA to the target distribution $\pi$ when the Langevin diffusion is geometrically ergodic and the Markov kernel associated with the EM discretization satisfies a Foster-Lyapunov drift inequality.

Consider the following assumption on the potential $U$:

By [35, Theorem 2.2], if $\mathcal{E}$ in (4) is a non-empty compact set, then the Langevin diffusion is geometrically ergodic.

Consider now the EM discretization of the diffusion (2). Let $(\gamma_{k})_{k\geq 1}$ be a sequence of positive and nonincreasing step sizes and for $0\leq n\leq p$, denote by

Note that Section 2 implies that $\sup_{k\geq 0}\{Q_{\gamma}^{k}V(x)\}\leq G(\lambda,c,\gamma_{1},V(x))$ where

To control the first term on the right hand side, we use a method introduced in and elaborated in . The second term is bounded using the convergence of the semi-group to $\pi$, see (3).

where $\kappa,C(\delta_{x}Q_{\gamma}^{n})$ are defined in (3) and

Girsanov’s Theorem [21, Theorem 5.1, Corollary 5.16, Chapter 3] shows that $\mu_{n,p}^{y}$ and $\bar{\mu}_{n,p}^{y}$ are mutually absolutely continuous and in addition, $\bar{\mu}_{n,p}^{y}$-almost surely

$A(\gamma,x)<\infty$ and $\limsup_{n\to+\infty}C(\delta_{x}Q_{\gamma}^{n})/(-\log(\gamma_{n}))<+\infty$, where $A(\gamma,x)$ is defined in (11).

$\sum_{k=1}^{\infty}\gamma_{k}^{2}<+\infty$, $A(\gamma,x)<\infty$ and $\limsup_{n\to+\infty}\log\{C(\delta_{x}Q_{\gamma}^{n})\}/\Gamma_{n}<+\infty$.

There exists $p_{0}\geq 1$ such that for all $p\geq p_{0}$, $\kappa^{\gamma_{p}}>\gamma_{p}$ and $\kappa^{\Gamma_{p}}\leq\gamma_{1}$. Therefore, we can define for all $p\geq p_{0}$,

and $n(p)\geq 1$. We first show that $\liminf_{p\to\infty}n(p)=\infty$. The proof goes by contradiction. If $\liminf_{p\to\infty}n(p)<\infty$ we could extract a bounded subsequence $(n(p_{k}))_{k\geq 1}$. For such sequence, $(\gamma_{n(p_{k})+1})_{k\geq 1}$ is bounded away from , but $\lim_{k\to+\infty}\kappa^{\Gamma_{n(p_{k})+1,p_{k}}}=0$ which yields to a contradiction. The definition of $n(p)$ implies that $\kappa^{\Gamma_{n(p),p}}\leq\gamma_{n(p)}$, showing that

The proof follows from (10) using $\lim_{p\to\infty}\gamma_{n(p)}=0$.

which shows that the first term in the right side of (10) goes to as $p$ goes to infinity. As for the second term, since $\limsup_{n\to+\infty}\log\{C(\delta_{x}Q_{\gamma}^{n})\}/\Gamma_{n}<+\infty$, we get using that $(\gamma_{k})_{k\geq 1}$ is nonincreasing and $n(p)\leq\log(\Gamma_{p})$,

Using $\kappa<1$ and $\lim_{k\to+\infty}\Gamma_{k}=+\infty$, we have $\lim_{p\to+\infty}C(\delta_{x}Q_{\gamma}^{n(p)})\kappa^{\Gamma_{n(p),p}}=0$, which concludes the proof.

For $p>T\gamma^{-1}$, set $n=p-\left\lfloor T\gamma^{-1}\right\rfloor$. Then using the stated expressions of $\gamma$ and $T$ in (10) concludes the proof. ∎

Note that an upper bound for $\gamma$ defined in (17) is $\epsilon^{2}(L^{2}Td)^{-1}$. The dependency of $T$ on the dimension $d$ will be addressed in Section 3.

The proof is a straightforward calculation using (10). ∎

Practical conditions for geometric ergodicity of the Langevin diffusion and their consequences for ULA

Assume first that the potential is superexponential outside a ball. This is a rather weak assumption (we do not assume convexity here).

The price to pay will be constants which are exponential in the dimension. Under H 1, the potential $U$ is unbounded off compact set. Since $U$ is continuous, it has a global minimizer $x^{\star}$, which is a point at which $\nabla U(x^{\star})=0$. Without loss of generality, it is assumed that $U(x^{\star})=0$.

The elementary proof is postponed to Section 4.2. ∎

Following [35, Theorem 2.3], we first establish a drift condition for the diffusion.

The proof, adapted from [35, Theorem 2.3] and [31, Theorem 6.1], is postponed to Section 4.3. ∎

Under H 1, explicit expressions for $C_{\varsigma}$ and $\upsilon_{\varsigma}$ have been developed in the literature but these estimates are in general very conservative. We now turn to establish (6) for the Euler discretization.

where $C_{1/2}$, $\upsilon_{1/2}$ are given by Section 3.1, $F$ by (7), $V$, $\lambda$, $c$ in Section 3.1, $G$ by (8), $a_{\alpha}$ in (18).

where $\log(\kappa)=-\upsilon_{1/4}$, $C_{1/4},\upsilon_{1/4},\theta_{1/2},\beta_{1/2}$ are defined in Section 3.1, $V,\lambda,c$ in Section 3.1, $G$ in (8) and

Moreover, $R_{\gamma}$ has a unique invariant distribution $\pi_{\gamma}$ and

Note that Theorem 2 implies that there exists a constant $C\geq 0$ which does not depend on $\gamma$ such that $\|\pi-\pi_{\gamma}\|_{V^{1/2}}\leq C\gamma^{1/2}$.

for some $C\geq 0$, $k\geq 1$, $\left|\pi_{\gamma}(\phi)-\pi(\phi)\right|\leq C\gamma^{\chi}$ for some constants $C\geq 0$ and $\chi\in\left(0,1/2\right)$, which does not depend on $\phi$.

This inequality implies by [9, Theorem 2.1] that for all $t\geq 0$ and any initial distribution $\mu_{0}$, such that $\mu_{0}\ll\pi$,

[2, Theorem 1.4] shows that if the Lyapunov condition (4) is satisfied, then the Poincaré inequality (21) holds with an explicit constant. Denote by

where $\mathbf{\Gamma}$ is the Gamma function and the constants $\beta_{1/2},\theta_{1/2},K_{1/2},a_{\alpha}$ are given in Section 3.1 and (18) respectively.

2 Log-concave densities

We now consider the following additional assumption.

We now derive a drift inequality for $R_{\gamma}$ under H 2.

If $U$ is convex, [5, Theorem 1.2] shows that $\pi$ satisfies a Poincaré inequality with a constant depending only on the variance of $\pi$.

The proof is postponed to Section 4.10. ∎

where $\mathbf{\Phi}$ is the cumulative distribution function of the standard Gaussian distribution and $\mathbf{\Phi}^{-1}$ is the associated quantile function. Before stating the theorem, we first show that (4) holds and provide explicit expressions for the constants which come into play. These constants will be used to obtain the explicit convergence rate of the semigroup $(P_{t})_{t\geq 0}$ to $\pi$ which is derived in Theorem 5.

The proof is adapted from [2, Corollary 1.6] and is postponed to Section 4.11. ∎

Note that the bound, we obtain is a little different from (3). The initial condition is isolated on purpose to get a better bound. A consequence of this result is the following bound on the convergence of the sequence $(\delta_{x}Q_{\gamma}^{n})_{n\geq 0}$ to $\pi$.

where $A(\gamma,x)$, $\varpi$ are given by (27) and (30a) respectively and

Finally the proof follows the same line as the one of Section 2. ∎

Note that this condition implies that the variance of $\pi$ is upper bounded by $Cd$.

3 Strongly log-concave densities

More precise bounds can be obtained in the case where $U$ is assumed to be strongly convex outside some ball; this assumption has been considered by for convergence in the Wasserstein distance; see also .

The proof is postponed to Section 4.12. ∎

Using the inequalities for all $t\in\left(0,1\right)$, $(1-t)^{-1}\leq 1+t(1-t)^{-2}$ and for all $s\in\left(0,1/2\right)$, $-\log(1-s)\leq s+2s^{2}$, we have:

4 Bounded perturbation of strongly log-concave densities

We now consider the case where $U$ is a bounded perturbation of a strongly convex potential.

The potential $U$ may be expressed as $U=U_{1}+U_{2}$, where

Denote by $x^{\star}_{1}$ the minimizer of $U_{1}$.

The proof is postponed to Section 4.13. ∎

The proof is postponed to Section 4.14. ∎

Proofs

The proof is then completed using this inequality in (34).

2 Proof of Section 3.1

On the other hand using again L 1, the Cauchy-Schwarz inequality and $\nabla U(x^{\star})=0$, for all $x\in\operatorname{B}(x^{\star},M_{\rho})$,

3 Proof of Section 3.1

4 Proof of Section 3.1

By H 1, for all $x\not\in\operatorname{B}(x^{\star},M_{\rho})$,

The proof is completed combining the last inequality and (37).

5 Proof of Theorem 1

where $V(x)=\exp(U(x)/2)$. Using that for all $t\geq 0$, $\phi_{\alpha}^{-1}(t)\leq(A_{\alpha}^{-1}\log(t))^{2/\alpha}$ and Section 2, we get

Eq. (19) follows from Section 3.1, Section 3.1 and Section 2.

6 Proof of Theorem 2

Using (38) and the Cauchy-Schwarz inequality in the previous inequality concludes the proof. ∎

First note that by the triangle inequality and Section 3.1, for all $p\geq 1$

Finally, $A$ can be bounded along the same lines. ∎

7 Proof of Theorem 3

where $\sigma_{\gamma,n}=\sum_{i=1}^{n}2\gamma_{i}(1-L\gamma_{i})^{-1}$.

Then, the proof of the claimed inequality is by induction. By (43), the inequality holds for $n=1$. Now assume that it holds for $n\geq 1$. By induction hypothesis and (43) applied for $\gamma=\gamma_{n+1}$, we have

Rearranging terms in the last inequality concludes the proof. ∎

Then the proof is concluded by a straightforward calculation. ∎

We bound the two terms of the right hand side of (10). The first term is dealt with the same reasoning as for the proof of Theorem 1. Regarding the second term, by [2, Theorem 1.4], $\pi$ satisfies a Poincaré inequality with constant $\log^{-1}(\kappa)$. Then, the claimed bound follows from (22) and Section 4.7. ∎

8 Proof of Section 3.2

9 Proof of Section 3.2

The proof is then completed using Section 3.2, Section 2 and that $\phi$ is one-to-one with for all $t\geq 1$, $\phi^{-1}(t)\leq\left(4\eta^{-1}\log(t)\right)^{2}$. ∎

Using $\nabla U(x^{\star})=0$, L 1 and Section 4.9, we have for all $k\geq 0$,

10 Proof of Theorem 4

Then the proof is concluded using the spherical coordinates. ∎

By [5, Theorem 1.2], $\pi$ satisfies a Poincaré inequality with constant $\log^{-1}(\kappa)$. Therefore, the second term in (10) is dealt as in the proof of Theorem 3 using (22), Section 4.10 and Section 4.7. ∎

11 Proof of Section 3.2

12 Proof of Section 3.3

13 Proof of Section 3.4

Using this inequality and $\nabla U_{1}(x^{\star}_{1})=0$ in (49) concludes the proof. ∎

Consider the second term in the right hand side of (50). Since $\gamma_{1}\leq 2/(m+L_{1})$, $m\leq L_{1}$ and $(\gamma_{k})_{k\geq 1}$ is nonincreasing, $\max_{k\geq 1}\gamma_{k}\leq\varpi^{-1}$ and therefore:

14 Proof of Theorem 7

We preface the proof of the Theorem by a preliminary lemma.

Plugging this bound in (51) gives the desired result. ∎

Quantitative convergence bounds in total variation for diffusions

In this part, we derived quantitative convergence results in total variation norm for $d$-dimensional SDEs of the form

with $e(z)=z/\left\|z\right\|$ for $z\not=0$ and $e(0)=0$ otherwise. Define the coupling time

For $t<\tau_{c}$, $\mathbf{X}_{t}-\mathbf{Y}_{t}$ is the solution of the SDE

where we have used the reflection principle in the last identity. ∎

For $j\geq 2$, define recursively the $j$-th return time to $G$ delayed by $t$ by

Then by the Dynkin formula (see e.g. [32, Eq. (8)]) the process

The result then follows from this inequality and the strong Markov property. ∎

For the second term, using Section 5 and the Markov inequality, we get

More precise bounds can be obtained under more stringent assumption on the drift $b$; see and .

Consider the sequence of increasing stopping time

is a positive supermartingale and by the optional stopping theorem, we get

For the second term, using Section 5-(b) and the Markov inequality, we get

By applying Theorem 9 with $\epsilon=1/2$, the triangle inequality and using that $\pi$ is invariant for $(P_{t})_{t\geq 0}$, we have

Acknowledgements

The authors are indebted to Arnaud Guillin for sharing his knowledge of Poincaré and log-Sobolev inequalities. The authors are grateful to Andreas Eberle for very careful readings and many useful comments. The author thank the anonymous referees for their constructive feedback. The work of A.D. and E.M. is supported by the Agence Nationale de la Recherche, under grant ANR-14-CE23-0012 (COSMOS).

References