Sharp convergence rates for Langevin dynamics in the nonconvex setting

Introduction

We study the problem of sampling from a target distribution of the following form:

Our focus is on theoretical rates of convergence of sampling algorithms, including analysis of the dependence of these rates on the dimension $d$. Much of the theory of convergence of sampling—for example, sampling based on Markov chain Monte Carlo (MCMC) algorithms—has focused on asymptotic convergence, and has stopped short of providing a detailed study of dimension dependence. In the allied field of optimization algorithms, a significant new literature has emerged in recent years on nonasymptotic rates, including tight characterizations of dimension dependence. The optimization literature, however, generally stops short of the kinds of inferential and decision-theoretic computations that are addressed by sampling, in domains such as Bayesian statistics (Robert and Casella 2013), bandit algorithms (Cèsa-Bianchi and Lugosi 2006) and adversarial online learning (Bubeck 2011; Abbasi et al. 2013).

In both optimization and sampling, while the classical theory focused on convex problems, recent work focuses on the more broadly useful setting of nonconvex problems. While general nonconvex problems are infeasible, it is possible to make reasonable assumptions that allow theory to proceed while still making contact with practice.

We will consider the class of MCMC algorithms that have access to the gradients of the potential, $\nabla U(\cdot)$. A particular algorithm of this kind that has received significant recent attention from theoreticians is the overdamped Langevin MCMC algorithm (Parisi 1981; Roberts and Tweedie 1996). The underlying first-order stochastic differential equation (henceforth SDE) is given by:

The second-order generalization of the overdamped Langevin diffusion is underdamped Langevin diffusion, which can be represented by the following SDE:

where $\lambda_{1},\lambda_{2}>0$ are free parameters. This SDE can also be discretized appropriately to yield a corresponding MCMC algorithm (Algorithm 2). Second-order methods such as underdamped Langevin MCMC are particularly interesting as it has been previously observed both empirically (Neal 2011) and theoretically (Cheng et al. 2017; Mangoubi and Smith 2017) that these methods can be faster to converge than the classical first-order methods.

In this work, we show that it is possible to sample from $p^{*}$ in time polynomial in the dimension $d$ and the target accuracy $\varepsilon$ (as measured in $1$-Wasserstein distance). We also show that the convergence depends exponentially on the product $LR^{2}$. Intuitively, $LR^{2}$ is a measure of the nonconvexity of $U$. Our results establish rigorously that as long as the problem is not “too badly nonconvex,” sampling is provably tractable.

Our main results are presented in Theorem 2 and Theorem 3, and can be summarized informally as follows:

Given a potential $U$ that is $L$-smooth everywhere and strongly-convex outside a ball of radius $R$, we can output a sample from a distribution which is $\varepsilon$-close to $p^{*}(x)\propto\exp\left(-U(x)\right)$ in $W_{1}$ distance by running $\widetilde{\mathcal{O}}\left(e^{cLR^{2}}d/\varepsilon^{2}\right)$ steps of overdamped Langevin MCMC (Algorithm 1), or $\widetilde{\mathcal{O}}\left(e^{cLR^{2}}\sqrt{d}/\varepsilon\right)$ steps of underdamped Langevin MCMC (Algorithm 2). Here, $c$ is an explicit positive constant.

For the case of strongly convex $U$, it has been shown by Cheng et al. 2017 that the iteration complexity of Algorithm 2 is $\widetilde{\mathcal{O}}(\sqrt{d}/\varepsilon)$, improving quadratically upon the best known iteration complexity of $\widetilde{\mathcal{O}}(d/\varepsilon^{2})$ for Algorithm 1 (Durmus and Moulines 2016). We will find this quadratic speed-up in $d$ and $\varepsilon$ in our setting as well (see Theorem 2 versus Theorem 3).

A convergence rate for overdamped Langevin diffusion, under assumptions (A1) – (A3) (see Section 2.1) has been established by Eberle 2016, but the continuous-time diffusion studied in that paper is not implementable algorithmically. In a more algorithmic line of work, Dalalyan 2017 bounded the discretization error of overdamped Langevin MCMC, and provided the first nonasymptotic convergence rate of overdamped Langevin MCMC under log-concavity assumptions. This was followed by a sequence of papers in the strongly log-concave setting (Durmus and Moulines 2016; Cheng and Bartlett 2017; Dalalyan and Karagulyan 2017; Dwivedi et al. 2018, see, e.g.,).

Our result for overdamped Langevin MCMC is in line with this existing work; indeed, we combine the continuous-time convergence rate of Eberle 2016 with a variant of the discretization error analysis by Durmus and Moulines 2016. The final number of timesteps needed is $\widetilde{\mathcal{O}}(e^{cLR^{2}}d/\varepsilon^{2})$, which is expected, as the rate of Eberle 2016 is $\mathcal{O}(e^{-cLR^{2}})$ (for the continuous-time process) and the iteration complexity established by Durmus and Moulines 2016 is $\widetilde{\mathcal{O}}(d/\varepsilon^{2})$.

On the other hand, convergence of underdamped Langevin MCMC under (strongly) log-concave assumptions was first established by Cheng et al. 2017. Also very relevant to our results is the work of Eberle et al. 2017, who demonstrated a contraction property of the continuous-time process stated in Eq. (2). That result deals, however, with a much larger class of potential functions, and accordingly the distance to the invariant distribution scales exponentially with dimension $d$. Our analysis yields a more favorable result by combining ideas from both Eberle et al. 2017 and Cheng et al. 2017, under new assumptions; see Section 4 for a full discussion.

Also noteworthy is the fact that the problem of sampling from non-log-concave distributions has been studied by Raginsky et al. 2017, but under weaker assumptions, with a worst-case convergence rate that is exponential in $d$. In Xu et al. 2018, this technique is used to study the application of Stochastic Gradient Langevin Diffusion (and its variance-reduced version) to nonconvex optimization. Similarly, Durmus and Moulines 2017 analyze the overdamped Langevin MCMC algorithm under the assumption that $U$ is superlinear outside a ball. This is more general than our assumption of “strong convexity outside a ball”; in this setting, the authors prove a rate that is exponential in dimension. On the other hand, Ge et al. 2017 established a $poly(d,1/\varepsilon)$ convergence rate for sampling from a distribution that is close to a mixture of Gaussians, where the mixture components have the same variance (which is subsumed by our assumptions).

Finally, there is a large class of sampling algorithms known as Hamiltonian Monte Carlo (HMC), which involve Hamiltonian dynamics in some form. We refer to Ma et al. 2015 for a survey of the results in this area. Among these, the variant studied in this paper (Algorithm 2), based on the discretization of the SDE in Eq. (2), has a natural physical interpretation as the evolution of a particle’s dynamics under a viscous force field. This model was first studied by Kramers 1940 in the context of chemical reactions. The continuous-time process has been studied extensively (Hérau 2002; Villani 2009; Eberle et al. 2017; Gorham et al. 2016; Baudoin 2016; Bolley et al. 2010; Calogero 2012; Dolbeault et al. 2015; Mischler and Mouhot 2014). Four recent papers—Mangoubi and Smith 2017, Lee and Vempala 2017, Mangoubi and Vishnoi 2018 and Deligiannidis et al. 2018—study the convergence rate of (variants of) HMC under log-concavity assumptions. In Eberle et al. 2019, the authors study the convergence of HMC on general metric state spaces. Bou-Rabee et al. 2018 study the convergence of HMC under assumptions similar to ours, and prove a convergence rate that depends on $e^{cLR^{2}}$ for some constant $c$. We remark that the algorithm studied in this case is different from the underdamped Langevin MCMC algorithm, because of the incorporation of an accept-reject step.

Notation, definitions and assumptions

We make the following assumptions on the potential function $U$:

The function has a stationary point at zero:

2 Coupling and Wasserstein distance

Overdamped Langevin diffusion

In this section, we study overdamped Langevin diffusion, given by the following stochastic differential equation (SDE):

It can be readily verified that the invariant distribution of the SDE is $p^{*}(y)\propto e^{-U(y)}$, which ensures that the marginal along $y$ is the distribution that we are interested in. Based on Eq. (3), we define the discretized overdamped Langevin diffusion as

where $\delta$ is the step-size of the discretization and $\lfloor\cdot\rfloor$ denotes the floor function.

Our first result, stated as Theorem 2, establishes the rate at which the distribution of the solution of Eq. (4) converges to $p^{*}$. The SDE in Eq. (4) is implementable as Algorithm 1.

It can be verified that $x_{i\delta}$ in Algorithm 1 and the solution to the SDE in Eq. (4) at time $t=i\delta$ have the same distribution. The following theorem establishes a convergence rate for Algorithm 1.

Assume that $m\geq\frac{\exp{\left(-LR^{2}/2\right)}}{R^{2}}$, and let $0<\varepsilon\leq\frac{dR^{2}}{\sqrt{d/m+R^{2}}}$ be the desired accuracy. Also let the initial point $x^{(0)}$ be such that $\lVert x^{(0)}\rVert_{2}\leq R$. Then if the step size scales as:

where $p_{n\delta}$ is the distribution of $x_{n\delta}$ in Algorithm 1 and the distribution $p^{*}(y)\propto e^{-U(y)}$.

For potentials where $LR^{2}$ is a constant, the number of iterations taken by overdamped MCMC scales as $\widetilde{\Omega}(d/\varepsilon^{2})$. This matches the rate obtained in the strongly log-concave setting by Durmus and Moulines 2016.

Intuitively, $LR^{2}$ measures the extent of nonconvexity. When this quantity is large, it is possible for $U$ to contain numerous local minima that are deep. It is therefore reasonable that the runtime of the algorithm should be exponential in this quantity.

The assumption on the strong convexity parameter, $m$, is made to simplify the presentation of the theorem. Note that this assumption is without loss of generality, since we can always take the radius $R$ to be sufficiently large in Assumption (A3). Similarly, our assumption on the target accuracy can also be easily removed, but we make this assumption in the interest of clarity.

The proof of Theorem 2 is relegated to Appendix C. The proof follows by carefully combining the continuous-time argument of Eberle 2016 together with the discretization bound of Durmus and Moulines 2016.

Underdamped Langevin diffusion

In this section, we present our results for underdamped Langevin diffusion. The underdamped Langevin diffusion is a second-order stochastic process described by the following SDE:

where $\kappa=L/m$ is the condition number. Similar to the case of overdamped Langevin diffusion, it can be verified that the invariant distribution of the SDE is $p^{*}(y,v)\propto e^{-U(y)-\frac{L}{2c_{\kappa}}\|v\|_{2}^{2}}$. This ensures that the marginal along $y$ is the distribution that we are interested in. Based on the SDE in Eq. (5), we define the discretized underdamped Langevin diffusion as:

where $\delta$ is the step size of discretization. The SDE in Eq. (7) is implementable as the following algorithm:

We show that the iterates at round $i$ of Algorithm 2 and the solution to the SDE in Eq. (7) at time $t=i\delta$ have the same distribution (see Lemma 40 in Appendix H).

In Theorem 3, we establish a bound on the rate at which the distribution of the iterates produced by this algorithm converge to the target distribution $p^{*}$.

Assume that $m\geq\frac{\exp{\left(-6LR^{2}\right)}}{64R^{2}}$ and let $0<\varepsilon\leq\frac{dR^{2}}{\sqrt{d/m+R^{2}}}$ be the desired accuracy. Also let the initial point $x^{(0)}$ be such that $\lVert x^{(0)}\rVert_{2}\leq R$. Assume also that $e^{72LR^{2}}\geq 2$.

where $p_{n\delta}$ is the distribution of $x_{n\delta}$ and we have $p^{*}(y)\propto e^{-U(y)}$.

If we consider potentials for which $LR^{2}$ is a constant, the iteration complexity of underdamped Langevin MCMC grows as $\widetilde{\mathcal{O}}(\sqrt{d}/\varepsilon)$, which is a quadratic improvement over the first-order overdamped Langevin MCMC algorithm. Again, the iteration complexity grows exponentially in $LR^{2}$ which is to be expected. As before, the condition on the strong convexity parameter and the target accuracy is made in the interest of clarity and can be removed.

The heart of the proof of this theorem is a somewhat intricate coupling argument. We begin by defining two processes, $(x_{t},u_{t})$ and $(y_{t},v_{t})$, and then couple them appropriately. The first set of variables, $(x_{t},u_{t})$, represent a solution to the discretized SDE in Eq. (7). On the other hand, the variables $(y_{t},v_{t})$ represent a solution of the continuous-time SDE in Eq. (5) with the initial conditions being $(y_{0},v_{0})\sim p^{*}(y,v)$. Thus the variables $(y_{t},v_{t})$ evolve according to the invariant distribution for all $t>0$. The noise that underlies both processes is coupled, and with an appropriate choice of a Lyapunov function we are able to demonstrate that the distributions of these variables converge in $1$-Wasserstein distance.

We present the coupling construction and a proof sketch in the subsequent sections. We relegate most of the technical details to the appendix.

Additionally, let $\nu=1/poly(L,1/m,d,R,1/{C_{m}})$ be another small constant (see proof of Theorem 3 for the exact value). In designing our coupling, we ensure that certain values are only updated at intervals of size $\nu$. These are needed to ensure that the stochastic process that we work with is sufficiently regular.

We then choose $\nu$ to be such that $\frac{{T_{sync}}}{\nu}$ is a positive integer, and define the constant

This constant ${C_{m}}$ will be the rate at which our Lyapunov function contracts.

With these definitions in place we are ready to define a coupling between variables $(x_{t},u_{t})$ that evolve according to the discretized process described in Eq. (11), and variables $(y_{t},v_{t})$ that evolve according to the SDE in Eq. (13).

Let the initial conditions for these processes be given by,

Define a variable $\tau_{t}$ that will be useful in determining how the noise underlying the processes is coupled. We initialize this variable as follows: $\tau_{0}=0$, if $\sqrt{{\left\|x_{0}-y_{0}\right\|}_{2}^{2}+{\left\|x_{0}-y_{0}+u_{0}-w_{0}\right\|}_{2}^{2}}\geq\sqrt{5}R$, and $\tau_{0}=-{T_{sync}}$ otherwise.

Let $A_{t}$ and $B_{t}$ denote independent $d$-dimensional Brownian motions. We then let the complete set of variables ${\left(x_{t},u_{t},y_{t},v_{t},\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}}\right)}$ evolve according to the following stochastic dynamics:

where the functions $\mathcal{M}$, $\gamma_{t}$ and $\bar{\gamma}_{t}$ are defined as follows:

and where for convenience we have defined

Second, when this indicator is equal to one, the processes are evolved by the same Brownian motion in the directions perpendicular to $z_{t}+w_{t}$, and (roughly) by the reflected Brownian motion along the direction $z_{t}+w_{t}$. This is called a reflection coupling between the two processes.

In the following lemma, we show that the variables $(y_{t},v_{t})$ have the same marginal distributions as the solution to the SDE defined in Eq. (13).

The dynamics in defined by Eq. (13) and Eq. (14) is distributionally equivalent to the dynamics defined by Eq. (5).

We give the proof in Appendix H. It is easy to verify that $(x_{t},u_{t})$ have the same marginal distribution as the solution to the SDE defined in Eq. (11) so we omit the proof.

From the dynamics in Eq. (14), we see that $\tau_{k}$ is used for determining whether $(x_{t},y_{t},u_{t},v_{t})$ evolves by synchronous or reflection coupling over the interval $t\in[k\nu,(k+1)\nu)$. From its definition in Eq. (17), we see that, roughly speaking, $\tau_{k}$ is “the last time (up to $k\nu$) that $(z_{t},w_{t})$ ends up outside the ball $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}=\sqrt{5}R$,” but with a caveat: we do not update the value of $\tau_{k}$ more than once in a ${T_{sync}}$ interval of time.

Let ${\left(\Omega,\mathcal{F}_{t},P\right)}$ be the probability space, where $\mathcal{F}_{t}$ is the $\sigma$-algebra generated by $(y_{0},v_{0})$, $B_{s}$ and $A_{s}$ for all $s\in[0,t)$. In the following Lemma, we prove that ${\left(x_{t},u_{t},v_{t},y_{t},\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}}\right)}$ has a unique strong solution $(x_{t},u_{t},y_{t},v_{t},\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}})(\omega)$ ($\omega\in\Omega$), which is adapted to the filtration $\mathcal{F}_{t}$. Furthermore, with probability one, $(x_{t},u_{t},y_{t},v_{t})(\omega)$ is $t$-continuous:

Let $B_{t}$ and $A_{t}$ be two independent Brownian motions, and let $\mathcal{F}_{t}$ be the $\sigma$-algebra generated by $B_{s}$, $A_{s}$; $s\leq t$, and $(x_{0},u_{0},y_{0},v_{0})$.

For all $t\geq 0$, the stochastic process $(x_{t},u_{t},y_{t},v_{t},\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}})(\omega)$ defined in Eqs. (11)–(17) has a unique solution such that $(x_{s},u_{s},y_{s},v_{s})$ is $t$-continuous with probability one, and satisfies the following, for all $s\geq 0$,

$(x_{s},u_{s},y_{s},v_{s},\tau_{{\left\lfloor\frac{s}{\nu}\right\rfloor}})$ is adapted to the filtration $\mathcal{F}_{s}$.

We defer the proof of this lemma to Appendix G.

As described above, when $\mu_{k}=0$ the processes are synchronously coupled, and when $\mu_{k}=1$ they are coupled via reflection coupling. Roughly, $r_{t}$ corresponds to the sum of $\lVert z_{t}\rVert_{2}$ and $\lVert z_{t}+w_{t}\rVert_{2}$. $\nabla_{t}$ is the difference of the gradients of $U$ at $x_{t}$ and $y_{t}$, while $\Delta_{t}$ is the difference of the gradients at $x_{{\left\lfloor\frac{t}{\delta}\right\rfloor}\delta}$ and $x_{t}$.

2 Lyapunov Function

In this section, we define a Lyapunov function that will be useful in demonstrating that the distributions of $(x_{t},u_{t})$ and $(y_{t},v_{t})$ converge in 1-Wasserstein distance.

We follow Eberle 2016 in our specification of the distance function $f$ that is used in the definition of our Lyapunov function. We define two constants,

Let us summarize some important properties of the functions $\psi$ and $g$:

$\psi$ is decreasing, $\psi(0)=1$, and $\psi(r)=\psi(2\mathcal{R}_{f})$ for any $r>2\mathcal{R}_{f}$.

$g$ is decreasing, $g(0)=1$, and $g(r)=\frac{1}{2}$ for any $r>2\mathcal{R}_{f}$.

In Lemma 31 in Appendix E, we state and prove various several useful properties of the distance function $f$.

Additionally define the stochastic processes:

These processes essentially track the discretization error arising due to a finite step size $\delta$ and $\nu$. We refer to Lemma 38 in Appendix G for a proof of existence of $\phi_{t}$.

Then following stochastic process $\mathcal{L}_{t}$ acts as our Lyapunov function:

where $k:={\left\lfloor\frac{t}{\nu}\right\rfloor}$. Note that $\mathcal{L}_{t}$ (the Lyapunov function at time $t$) depends on $r_{\tau_{k}}$ (at time $\tau_{k}$). In Lemma 26, we demonstrate that this function contracts at a rate of $e^{-{C_{m}}t}$. The convergence bound then follows by showing that the convergence of this Lyapunov function implies convergence of the distributions in $1$-Wasserstein distance.

3 Proof Sketch

We present a full proof of Theorem 3 in Appendix D. In this section we provide a high-level sketch of our proof.

The proof proceeds by a path-wise analysis of the evolution of the Lyapunov function. In Figure 1(b), we illustrate a sample path of the process.

First, let us highlight the features of the figure.

The red circle represents the set $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}=\sqrt{5}R$. It affects the updates of $\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}}$, which, in turn, dictates how the processes are coupled.

The orange circle represents $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}=\frac{23}{50}\cdot\sqrt{5}R$. In relation to the red circle, it represents the contraction of $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}$ when evolved according to synchronous coupling.

The dark green diamond represents $(1+2c_{\kappa}){\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}=\sqrt{5}R$. It is a lower bound on $(1+2c_{\kappa}){\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}=\sqrt{5}R$ when $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}=\sqrt{5}R$.

The light green diamond represents $2{\left((1+2c_{\kappa}){\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}\right)}=2\cdot\frac{23}{50}\sqrt{5}R$. It represents an upper bound on $(1+2c_{\kappa}){\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}=\sqrt{5}R$ when $\sqrt{{\left\|z_{t}\right\|}_{2}^{2}+{\left\|z_{t}+w_{t}\right\|}_{2}^{2}}=\frac{23}{50}\cdot\sqrt{5}R$.

It is not drawn, but note that the red circle is contained in $(1+2c_{\kappa}){\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}\leq\sqrt{12}R$, which is the radius used for defining $f$ in Eq. (21).

The brown squiggly lines ($t_{0}\to t_{1}$) and ($t_{2}\to t_{3}$) represent the evolution of the process under reflection coupling.

The black line $t_{1}\to t_{2}$ represents the evolution of the process under synchronous coupling.

Below, we describe how $(z_{t},w_{t})$ evolves over $t\in[t_{0},t_{3}]$, and illustrate the main ideas behind the proof. To simplify matters, assume that

$k_{i}:=t_{i}/\nu$ are integers, for $i=0,1,2,3$.

$\xi_{t}=\sigma_{t}=0$ as these terms correspond to discretization errors.

$r_{t}\approx{\left\|z_{t}\right\|}_{2}+(1+2c_{\kappa}){\left\|z_{t}+w_{t}\right\|}_{2}$.

From $t_{0}\to t_{1}$: Suppose that the process starts somewhere inside the red circle and stays inside for until time $t_{1}$, then $\tau_{{\left\lfloor\frac{t}{\nu}\right\rfloor}}=t_{0}$ and $\mu_{{\left\lfloor\frac{t}{\nu}\right\rfloor}}=1$ for $t\in[t_{0},t_{1})$, and the process $(z_{t},w_{t})$ undergoes reflection coupling.

In this case, we can show that when $r_{t}\leq\sqrt{12}R$ then $f(r_{t})-\phi_{t}$ contracts at a rate of $\exp(-{C_{m}}t)$ with probability one (see Lemma 9). This in turn implies that our Lyapunov function $\mathcal{L}_{t}$ also contracts at the same rate with probability one (see Lemma 29 and Lemma 30).

From $t_{1}\to t_{2}$: At $t=t_{1}$, we update $\tau_{k_{1}}$ so that $\tau_{k_{1}}=t_{1}$. Thus $\mu_{s}=0$ for all $s\in[t_{1},t_{2})$. During this period, $(z_{t},w_{t})$ evolves under synchronous coupling. In Lemma 13, we show that $\sqrt{{\left\|z_{t_{2}}\right\|}_{2}^{2}+{\left\|z_{t_{2}}+w_{t_{2}}\right\|}_{2}^{2}}\leq\frac{23}{50}\sqrt{{\left\|z_{t_{1}}\right\|}_{2}^{2}+{\left\|z_{t_{1}}+w_{t_{1}}\right\|}_{2}^{2}}$. This implies that $f(r_{t_{2}})\leq e^{-{C_{m}}(t_{2}-t_{1})}f(r_{t_{1}})$ (Lemma 10). Again, this contraction is with probability one. Intuitively, we use synchronous coupling because when the value of ${\left\|z_{t}\right\|}_{2}+{\left\|z_{t}+w_{t}\right\|}_{2}$ is large, Assumption (A3) guarantees contraction even in the absence of noise.

This contraction in $f$ consequently results in a contraction of the Lyapunov function (see Lemma 28).

After a duration ${T_{sync}}$ of synchronous coupling, we have $\mu_{k_{2}}=1$ and we resume reflection coupling over $[t_{2},t_{3}]$. Note that at $t=t_{2}$, the Lyapunov function $\mathcal{L}_{t}$, undergoes a jump in value, from $\exp{\left(-{C_{m}}(t_{2}-t_{1})\right)}f(r_{t_{1}})$ to $f(r_{t_{2}})$ (see (4.2)). We show in Lemma 27 that this jump is negative with probability one.

Discussion

In this paper, we study algorithms for sampling from distributions which satisfy a more general structural assumption than log-concavity, in time polynomial in dimension and accuracy. We also demonstrate that when using underdamped dynamics the runtime can be improved, mirroring the strongly convex case.

There are a few natural questions that we hope to answer in further investigation of non-log-concave sampling problems. First, it would be interesting to determine other structural assumptions that may be imposed on the target distribution that are more general than log-concavity but still admit tractable sampling guarantees; for example, we would like to uncover assumptions that may alleviate the exponential dependence on $LR^{2}$. Conversely, existing guarantees may be extended to weaker assumptions, such as weak convexity outside a ball. Secondly, one might also wish to consider algorithms which have access to more than a gradient oracle, such as the Metropolis Hastings filter, or discretizations which use higher-order information.

Acknowledgements

This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.

References

Appendix A Index of notation

Appendix B Two Small Constants

We define a function $q(r)$ in (31), which is a smoothed approximation of $|r|$, such that it has continuous second derivatives everywhere. Specifically, for $r\leq\beta/2$, $q(r)$ is a cubic spline.

This allows us to define a smoothed version of ${\left\|x\right\|}_{2}$, which has continuous second derivatives everywhere:

On $\nu$: In order to demonstrate the existence of a strong solution to the coupling presented in Section 4.1 (Lemma 5), we switch between synchronous and reflection coupling at deterministic, finite intervals of width $\nu$.

This is not necessary strictly speaking, as there are results that ensure the existence of solutions of an SDE when the diffusion and drift coefficients are discontinuous but have finite variation. However, we choose to use a discretized coupling as the existence of its solution can be verified by using standard results.

This discretized coupling scheme adds an error term $\sigma_{t}$ (see Eq. (28)). We show in Lemma 18 that this is $o(\nu^{2})$.

When reading the proofs, it helps to think of $\nu=0$ and $\sigma_{t}=0$, as we can take $\nu$ to be arbitrarily small without additional computation costs. In the proof, it suffices to let $\nu=1/poly(L,1/m,d,R)$. See the proof and Theorem 3 for the exact value of $\nu$.

Note that $\nu$ is distinct from (and unrelated to) $\delta$, which is the step-size of the underdamped Langevin MCMC algorithm (Algorithm 2). $\delta$, and the corresponding discretization error $\xi_{t}$, cannot be made arbitrarily small without additional computation costs.

This is just chain rule, together with Lemma 7.1, which guarantees the existence of $q^{\prime\prime}({\left\|x\right\|}_{2})/{\left\|x\right\|}_{2}^{2}$ for all $x$.

Existence and continuity follow from Lemma 7.

Let $\beta$ be any positive real. Let ${q}(r)$ be defined as in (31), reproduced below for ease of reference:

${q}(r)$, ${q}^{\prime}(r)/r$ and ${q}^{\prime\prime}(r)/r^{2}$ exist for all $r$, and are continuous.

For all $r$, $q(r)$ satisfies $\beta/3\leq{q}(r)$ and ${\left|r-{q}(r)\right|}\leq\beta/3$. In addition, ${q}(r)=r$ for $r\geq\beta/2$.

${q}^{\prime}(r)$ is monotonically nondecreasing, ${q}^{\prime}(r)=1$ for $r\geq\beta/2$, and ${q}^{\prime}(r)=0$ for $r=0$.

${q}^{\prime\prime}(r)=0$ for all $r\geq\beta/2$.

All the claims can then be verified algebraically. ∎

Appendix C Proofs for overdamped Langevin Monte Carlo

We begin by establishing the convergence of the continuous-time process in Eq. (1) to the invariant distribution. Similar to Eberle 2016, we construct a coupling between the SDEs described by Eq. (3) and Eq. (4). We initialize the coupling at

and evolve the pair $(x_{t},y_{t})$ according to the dynamics

where the terms $\gamma_{t}$ and $\bar{\gamma}_{t}$ are defined as:

In the following Lemma, we show that $y_{t}$ evolved according to Eq. (34) has the same marginal distributions as $y_{t}$ evolved according to the SDE in Eq. (3).

The dynamics in Eq. (34) is distributionally equivalent to the dynamics defined in Eq. (3).

Finally, we construct the Lyapunov function that we will use to show convergence. Let $f(r_{t})$ be as defined in Eq. (26), with

and finally, define two stochastic processes

With these definitions, the following stochastic process $\mathcal{L}_{t}$ acts as our Lyapunov function:

C.2 Proof of Theorem 2

We note that the technique in establishing Step 1 is essentially taken from Eberle 2016.

where $(i)$ is by the Cauchy-Schwarz inequality, along with the fact that ${\left|f^{\prime}(r)\right|}\leq 1$ (see (F2) of Lemma 31), and Lemma 7.3. The inequality in $(ii)$ can be verified by considering three disjoint events. When ${\left\|z_{t}\right\|}_{2}\in[0,\beta]$, the bound follows by Cauchy-Schwarz, (F2) of Lemma 31, combined with Lemma 7.3. While when ${\left\|z_{t}\right\|}_{2}\in[R,\infty]$ the bound follows from Assumption (A3). When ${\left\|z_{t}\right\|}_{2}\in[\beta,R]$, we bound the term using Cauchy-Schwarz, Assumption (A1), and Lemma 7.3.

Alternatively, when ${\left\|z_{t}\right\|}_{2}\neq 0$,

Exapanding using the definition of $\heartsuit$,

Before proceeding, we verify by definition of $\gamma_{t}$ and $\bar{\gamma}_{t}$ in Eq. (15) that

where the inequality $(i)$ is because $f^{\prime\prime}(r)\geq 0$ for all $r>0$ (by Lemma 31.(F5)), $q^{\prime}(r)\geq 0$ for all $r$ (by Lemma 7.3) and $q^{\prime}(r)=1$ for all $r\geq\beta/2$ (Lemma 7.3). The equality in $(ii)$ is because $\gamma_{t}=1$ for ${\left\|z_{t}\right\|}_{2}\geq\beta$ (by its definition in Eq. (35)).

Next, using Eq. (42), we can immediately verify that $\heartsuit_{2}=0$.

where we use the fact that $q^{\prime\prime}({\left\|z_{t}\right\|}_{2})=0$ if ${\left\|z_{t}\right\|}_{2}\geq\beta/2$ (by Lemma 7.4) and $\gamma_{t}=\bar{\gamma}_{t}=0$ if ${\left\|z_{t}\right\|}_{2}\leq\beta/2$ (by its definition in Eq. (35)).

Putting together the bounds on $\heartsuit_{1}$, $\heartsuit_{2}$ and $\heartsuit_{3}$, we can upper bound $\heartsuit$ as

Combining the upper bounds on $\spadesuit$ and $\heartsuit$,

Let us now focus on $\clubsuit$. By Lemma 31,

where the second line is by Lemma 6.1 and 31.(F3), and by $m\leq L$.

The second inequality uses the definition of $\Delta_{t}$ in Eq. (36) and Assumption (A1).

Step 2: If we consider the evolution of the Lyapunov function $\mathcal{L}_{t}$ (defined in Eq. (41)), we can verify that

where the simplification in inequality $(i)$ can be verified by taking time derivatives of stochastic processes $\phi_{t}$ and $\xi_{t}$ defined in Eq. (40) and Eq. (39).

Using the definition of $\mathcal{L}_{t}$ in Eq. (41) we get,

Taking expectations with respect to the Brownian motion yields:

where $(i)$ is because $x^{(}0)=0$ in Eq. (33), $(ii)$ is by Lemma 31.(F3), $(iii)$ is by Lemma 6.1, and finally $(iv)$ is by Lemma 37.

Let $n$ be the number of time steps, so that $t=n\delta$. Substituting into the inequality in Eq. (43), we get

where for the second inequality, it suffices to let $\beta=\delta d/6$

For a given $\varepsilon$, the first term is less than $\varepsilon/2$ if

The second term is less than $\varepsilon/2$ if

By the definition of ${C_{o}}$ in Eq. (38),

where the equality is by our assumption on the strong convexity parameter $m$ in the theorem statement. Recall that we also assume that $\varepsilon\leq\frac{dR^{2}}{\sqrt{d/m+R^{2}}}$. Thus we can verify that

Appendix D Proofs for Underadmped Langevin Monte Carlo

The main idea behind the proof is to show that $\mathcal{L}_{t}$ contracts with probability one by a factor of $e^{-{C_{m}}\nu}$, going from $t=(k-1)\nu$ to $t=k\nu$. The result can be found in Lemma 26 in Section D.5. The proof considers four cases:

$\mu_{k-1}=1,\mu_{k}=1$. In Lemma 29 in Section D.5, we show that $\mathcal{L}_{k\nu}\leq e^{-{C_{m}}\nu}\mathcal{L}_{(k-1)\nu}$. The proof of this result in turn uses Lemma 9 in Section D.2, which shows that $\mathcal{L}_{t}$ contracts at a rate of $-{C_{m}}$ over the interval $t\in[(k-1)\nu,k\nu]$.

$\mu_{k-1}=1,\mu_{k}=0$. In Lemma 30 in Section D.5, we show that $\mathcal{L}_{k\nu}\leq e^{-{C_{m}}\nu}\mathcal{L}_{(k-1)\nu}$. The proof of this result is almost identical to the preceding case $\mu_{k-1}=1,\mu_{k}=1$. (In particular, $\mathcal{L}_{t}$ undergoes no jump in value at $t=k\nu$, in spite in the change in value from $\mu_{k-1}=1$ to $\mu_{k}=0$. See proof for details.)

$\mu_{k-1}=0,\mu_{k}=0$. In Lemma 28 in Section D.5, we show that $\mathcal{L}_{k\nu}\leq e^{-{C_{m}}\nu}\mathcal{L}_{(k-1)\nu}$. The proof of this result is mainly based on the definition of $\mathcal{L}_{t}$.

$\mu_{k-1}=0,\mu_{k}=1$. In Lemma 27 in Section D.5, we show that $\mathcal{L}_{k\nu}\leq e^{-{C_{m}}\nu}\mathcal{L}_{(k-1)\nu}$. This case is somewhat tricky, as $\mathcal{L}_{t}$ undergoes a jump in value at $t=k\nu$. Specifically, $\mathcal{L}_{t}$ jumps from $e^{-{C_{m}}{T_{sync}}}{\left(f(r_{\tau_{k-1}})-\xi_{\tau_{k-1}}\right)}-{\left(\sigma_{k\nu}+\phi_{k\nu}\right)}$ to $f(r_{k\nu})-\xi_{k\nu}-{\left(\sigma_{k\nu}+\phi_{k\nu}\right)}$. We prove that this jump is always negative (Lemma 10, Section D.3). The proof of Lemma 12 in turn relies on a contraction result in Lemma 13.

D.2 Contraction under Reflection Coupling

Our main result is stated as Lemma 9. It shows that $\mu_{k}f(r_{t})$ contracts at a rate of $\exp(-{C_{m}}t)$, plus some discretization error terms.

For any positive integer $k$, with probability one we have,

If $\mu_{k}=0$, both sides of the inequality are identically zero. To simplify notation, we leave out the factor of $\mu_{k}$ in subsequent expressions and assume that $\mu_{k}=1$ unless otherwise stated.

For the rest of this proof, we will consider time $s\in[k\nu,(k+1)\nu)$ for some $k$.

Let us first establish some useful derivatives of the function $f$:

where $(i)$ follows from Itô’s Lemma, and $(ii)$ follows from Eqs. (11) - (14), and the definition of $\nabla_{t}$ and $\Delta_{t}$ in Eq. (20).

In the sequel, we upper bound the terms $\spadesuit,\heartsuit,\clubsuit$ separately. Before we proceed, we verify the following inequalities:

where $(i)$ is again by Cauchy-Schwarz and $(ii)$ is by Cauchy-Schwarz combined with Assumption (A1). Finally:

where the inequality above is by Cauchy-Schwarz along with the fact that $q^{\prime}(r)\geq 0$ for all $r$ from Lemma 7.

Bounding $\spadesuit$: From Eqs. (45) and (44):

We again highlight the fact that $q^{\prime}({\left\|z\right\|}_{2})\frac{z}{{\left\|z\right\|}_{2}}$ is defined for all $z$, particularly at ${\left\|z\right\|}_{2}=0$, as $q(r)=o(r^{2})$ near zero (see Lemma 7).

Substituting the inequality in Eq. (46) into $\spadesuit_{1}$:

where the inequality uses Cauchy-Schwarz and (F2) of Lemma 31.

Now consider a few cases. We will use the expression for $q^{\prime}(r)$ from Eq. (7) a number of times:

If ${\left\|z_{s}\right\|}_{2}\in[\beta,\infty),{\left\|z_{s}+w_{s}\right\|}_{2}\in[\beta,\infty)$, then $q^{\prime}({\left\|z_{s}\right\|}_{2})=q^{\prime}({\left\|z_{s}+w_{s}\right\|}_{2})=1$, so that

where we use the definition of $r_{t}$ defined in Eq. (19) and Lemma 6.1.

If ${\left\|z_{s}\right\|}_{2}\in[0,\beta),{\left\|z_{s}+w_{s}\right\|}_{2}\in[\beta,\infty)$, then $q^{\prime}({\left\|z_{s}\right\|}_{2})\in$ and $q^{\prime}({\left\|z_{s}+w_{s}\right\|}_{2})=1$, so that

where (i) uses ${\left\|z_{s}+w_{s}\right\|}_{2}-{\left\|z_{s}\right\|}_{2}\leq{\left\|w_{s}\right\|}_{2}$, $(ii)$ uses ${\left\|w_{s}\right\|}_{2}-{\left\|z_{s}+w_{s}\right\|}_{2}\leq{\left\|z)s\right\|}_{2}$, $(iii)$ uses our upper bound in ${\left\|z_{s}\right\|}_{2}$ and $(iv)$ uses the definition of $r_{t}$ in Eq. (19) and Lemma 6.1.

If ${\left\|z_{s}\right\|}_{2}\in[\beta,\infty),{\left\|z_{s}+w_{s}\right\|}_{2}\in[0,\beta)$, then $q^{\prime}({\left\|z_{s}\right\|}_{2})=1$ and $q^{\prime}({\left\|z_{s}+w_{s}\right\|}_{2})\in$, so that

where $(i)$ uses our expression for $q^{\prime}(\cdot)$, and $(ii)$ uses the expression for $r_{t}$ in Eq. (19), the fact that $c_{\kappa}\leq 1/1000$ and Lemma 6.1.

Finally, if ${\left\|z_{s}\right\|}_{2}\in[0,\beta),{\left\|z_{s}+w_{s}\right\|}_{2}\in[0,\beta)$, then $q^{\prime}({\left\|z_{s}\right\|}_{2})\in$ and $q^{\prime}({\left\|z_{s}+w_{s}\right\|}_{2})\in$, so that

where we again use the expression for $r_{s}$ in Eq. (19) and Lemma 6.1.

Combining the four cases above we find that,

where we use Lemma 31.(F2), Lemma 6.1 and Eq. (18).

where $(i)$ is by Eq. (44), $(ii)$ is by Lemma 44 and $(iii)$ is because \bm{\left\langle}\gamma_{s},\frac{z_{s}+w_{s}}{{\left\|z_{s}+w_{s}\right\|}_{2}}\bm{}={\left\|\gamma_{s}\right\|}_{2} and \bm{\left\langle}\bar{\gamma}_{s},\frac{z_{s}+w_{s}}{{\left\|z_{s}+w_{s}\right\|}_{2}}\bm{}={\left\|\bar{\gamma}_{s}\right\|}_{2} (see Eq. (15)).

From Lemma 7.4, $q^{\prime\prime}({\left\|z_{s}+w_{s}\right\|}_{2})=0$ for ${\left\|z_{s}+w_{s}\right\|}_{2}\geq\beta/2$ and from Eq. (15), $\gamma_{s}=\bar{\gamma}_{s}=0$ for ${\left\|z_{s}+w_{s}\right\|}_{2}\leq\beta/2$. Thus the above simplifies to

Combining our upper bounds on $\spadesuit$ and $\heartsuit$ from Eq. (48) and Eq. (49),

where $(i)$ and $(ii)$ follow from algebraic manipulations. Continuing forward we find that,

where $(i)$ is by Lemma 31 (F4) combined with the choice of $\alpha_{f}$ and $\mathcal{R}_{f}$, third line is by Lemma 31 (F2) and Lemma 31 (F3). $(ii)$ follows immediately from the definition of ${C_{m}}$ in (9). $(iii)$ can be verified from algebra, and finally $(iv)$ is from the fact that ${C_{m}}\leq 1$ and $f(r)\leq r$ for all $r$ (Lemma 31 (F3)).

Thus, by combining the bounds on $\spadesuit$ and $\heartsuit$ in Eqs. (50) back into Eq. (45),

By taking the time derivative of Eq. (27)-(29), we can verify that for $s\in[k\nu,(k+1)\nu)$,

An application of Grönwall’s Lemma over the interval $s\in[k\nu,(k+1)\nu)$ gives us the claimed result:

D.3 Main results for synchronous coupling

Our main result in this section is Lemma 10, which shows that over a period of ${T_{sync}}$, $f(r_{s})$ contracts by an amount $\exp{\left(-{C_{m}}{T_{sync}}\right)}$ with probability one. Note that this is weaker than showing a contraction rate of $\exp(-{C_{m}}t)$ for all $t$, but is sufficient for our purposes.

Assume that $e^{72LR^{2}}\geq 2$. With probability one, for all $k$,

From our definition of $c_{\kappa}$ in Eq. (6), $r_{t}$ in Eq. (19), and from Lemma 6.1, it can be verified that

On the other hand, by ${\left\|\cdot\right\|}_{1}\geq{\left\|\cdot\right\|}_{2}$ and by Lemma 6,

Combining the inequality in the display above with the statement of Lemma 13 gives:

Combining the above with (F2), (F3) and (F6) of Lemma 31, and by using the definition of $f$ in Eq. (21),

where the first line in $(i)$ follows from the definition of ${T_{sync}}$ and ${C_{m}}$ in Eq. (8) and Eq. (9) along with the fact that $(1-\sqrt{47/50})/4\geq 1/200$. The second line in $(i)$ is because ${C_{m}}\leq\frac{c_{\kappa}^{2}}{3}$ from Eq. (9).

By subtracting the left and the right hand sides of Eq. (53) and Eq. (52) thus gives us that,

We now state and prove several auxillary lemmas which are required for the proof of Lemma 10.

If ${\left\|z_{s}\right\|}_{2}^{2}+{\left\|z_{s}+w_{s}\right\|}_{2}^{2}\geq 2.2R^{2}$, then

We begin by expanding the differentials $d{\left\|z_{s}\right\|}_{2}^{2}+d{\left\|z_{s}+w_{s}\right\|}_{2}^{2}$:

Case 1: (${\left\|z_{s}\right\|}_{2}\leq R$) By Young’s inequality,

Furthermore, by our assumption that ${\left\|z_{s}\right\|}_{2}^{2}+{\left\|z_{s}+w_{s}\right\|}_{2}^{2}\geq 2.2R^{2}$,

With this implication $\spadesuit$ can now be upper bounded by

where $(i)$ is by Assumption (A1) and Cauchy-Schwarz, and $(ii)$ is because $c_{\kappa}:=\frac{1}{1000\kappa}\leq\frac{1}{1000}$. The inequality $(iii)$ is by the implication in Eq. (55), which gives $3c_{\kappa}{\left\|z_{s}\right\|}_{2}^{2}\leq\frac{1000c_{\kappa}}{3}{\left\|w_{s}\right\|}_{2}^{2}\leq\frac{1}{3}{\left\|w_{s}\right\|}_{2}^{2}$. Finally, $(iv)$ can be verified as follows:

where $(i)$ is by Young’s inequality, $(ii)$ is by Eq. (55), and $(iii)$ is by $c_{\kappa}\leq\frac{1}{1000}$.

Case 2: (${\left\|z_{s}\right\|}_{2}\geq R$) We have,

where $(i)$ is by Assumption (A3) and $(ii)$ is because

Hence, we have proved the result under both cases. ∎

When $\mu_{k}=1$, the inequality holds trivially ($0=0$), so for the rest of this proof, we consider the case $\mu_{k}=0$. To simplify notation, we leave out the multiplier $(1-\mu_{k})$ in all subsequent expressions.

We can verify from Eqs. (11)-(14) and Eq. (18) that when $\mu_{k}=0$, for any $s\in[k\nu,(k+1)\nu)$,

where $(i)$ is by the expression for $dz_{s}$ and $dw_{s}$ established above, and $(ii)$ is by Lemma 11 and Cauchy-Schwarz, the last two inequalities follow by algebraic manipulations.

Dividing throughout by ${\left(\sqrt{\|z_{s}\|_{2}^{2}+\|z_{s}+w_{s}\|_{2}^{2}}-\sqrt{2.2}R\right)}_{+}$ gives us that

We can verify that the inequality implies that

This proves the statement of the Lemma. ∎

Assume that $e^{72LR^{2}}\geq 2$. With probability one, for all positive integers $k$,

By our choice $\nu$ we know that ${T_{sync}}/\nu$ is an integer, thus we have,

where $S_{k-1}:=\left\{\frac{\tau_{k-1}}{\nu},\frac{\tau_{k-1}}{\nu}+1,...,k-1\right\}$ (as defined in Lemma 14). Above, $(i)$ is because $k\nu=\tau_{k-1}+{T_{sync}}\Rightarrow(k-1)\nu<\tau_{k-1}+{T_{sync}}$, $(ii)$ is because $(k-1)\nu<\tau_{k-1}+{T_{sync}}\Rightarrow\mu_{k-1}=0$ (see Eq. (18)) and $(iii)$ is by Part 2 of Lemma 14.

where the last inequality uses the fact that $\nu\cdot(k-\tau_{k-1})={T_{sync}}$ in the definition of $\alpha$.

where $(i)$ is by Eq. (56), $(ii)$ is by Eq. (57), $(iii)$ is by Eq. (56) again, and $(iv)$ is by the definition ${T_{sync}}=\frac{3}{c_{\kappa}^{2}}\log(100)$.

Let $j:=\tau_{k-1}/\nu$. Then by the first part of Lemma 14, we know that $\tau_{j}=\tau_{k-1}=j\nu$. From the update rule for $\tau_{k}$, Eq. (17), this must imply that

where $(i)$ is by an algebraic manipulation, $(ii)$ is by Eq. (58), $(iii)$ is by Eq. (59) and $(iv)$ is because $1/100+\sqrt{22/50}\leq\sqrt{23/50}$. ∎

Let $j=\tau_{k}/\nu$. Then for all $i\in\left\{j,j+1,...,k\right\}$, $\tau_{i}=\tau_{k}=j\nu$.

If $\mu_{k}=0$, then $\mu_{i}=0$ for all $i\in\left\{\tau_{k}/\nu...k\right\}$, $\mu_{i}=0$. Equivalently,

where $S_{k}:=\left\{\frac{\tau_{k}}{\nu},...,k\right\}$.

For the first claim: By definition of the update for $\tau_{k}$, if $j=\tau_{k}/\nu$ for any $k$, then $j\nu=\tau_{j}=\tau_{k}$. Note that $\tau_{i}$ is nondecreasing with $i$, so that $j=\tau_{k}\leq k$, which implies that $\tau_{j}\leq\tau_{j+1}\leq...\leq\tau_{j}$. Since $\tau_{j}=\tau_{k}$, the inequalities must hold with equality.

For the second claim: By the definition of $\mu_{k}$; $\mu_{k}=0$ implies that $k\nu<\tau_{k}+{T_{sync}}$. From the first claim, we know that for all $i\in\left\{\tau_{k}/\nu...k\right\}$, $\tau_{i}=\tau_{k}$. Thus $i\nu\leq k\nu<\tau_{k}+{T_{sync}}=\tau_{i}+{T_{sync}}$. ∎

D.4 Discretization Error Bound

This follows directly by combining the results of Lemma 32 and Lemma 17. ∎

Suppose that the step size $\delta\leq\frac{1}{1000}$. Then for all $t\in[{\left\lfloor\frac{t}{\delta}\right\rfloor}\delta,({\left\lfloor\frac{t}{\delta}\right\rfloor}+1)\delta]$,

where for the last inequality, we use Lemma 34.

For $\beta\leq 0.0001R$. There exists a $C_{5}=poly(L,1/m,d,R,\frac{1}{{C_{m}}})$ and $C_{3}=1/poly(L,1/m,d,R)$, such that for all $\nu\leq C_{3}$, for all positive integers $k$, and for all $t\geq 0$,

By the definition of $\sigma_{t}$ in Eq. (28),

where $(i)$ is by Lemma 32 and Lemma 33. ∎

For every $\beta\leq 0.0001R$, there exists a $C_{2}=poly(L,1/m,d,R)$, $C_{3}=1/poly(L,1/m,d,R)$, such that for all $\nu\leq C_{3}$, for all positive integers $k$, and for all $s\in[k\nu,(k+1)\nu]$,

By definition of $\mu_{k}$ in Eq. (18), we know that $\mu_{k}=1$ implies that $k\nu-\tau_{k}\geq{T_{sync}}$ which further implies that $\tau_{k}=\tau_{k-1}$ (otherwise $\tau_{k}$ must equal $k\nu$ by the definition of $\tau_{t}$, in which case $k\nu-\tau_{k}=0<{T_{sync}}$). This then implies that $k\nu-\tau_{k-1}\geq{T_{sync}}$. It must thus be the case that $\sqrt{{\left\|z_{k\nu}\right\|}_{2}^{2}+{\left\|z_{k\nu}+w_{k\nu}\right\|}_{2}^{2}}<\sqrt{5}R$, because otherwise $\tau_{k}=k\nu$, which contradicts $\mu_{k}=1$. Thus,