Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics

## Abstract

Abstract Geometric tempering is a popular approach to sampling from challenging multi-modal probability distributions by instead sampling from a sequence of distributions which interpolate, using the geometric mean, between an easier proposal distribution and the target distribution. In this paper, we theoretically investigate the soundness of this approach when the sampling algorithm is Langevin dynamics, proving both upper and lower bounds. Our upper bounds are the first analysis in the literature under functional inequalities. They assert the convergence of tempered Langevin in continuous and discrete-time, and their minimization leads to closed-form optimal tempering schedules for some pairs of proposal and target distributions. Our lower bounds demonstrate a simple case where the geometric tempering takes exponential time, and further reveal that the geometric tempering can suffer from poor functional inequalities and slow convergence, even when the target distribution is well-conditioned. Overall, our results indicate that geometric tempering may not help, and can even be harmful for convergence.

## 1 Introduction

Sampling from a target distribution $\pi$ whose density is known up to a normalizing constant is a challenging problem in statistics and machine learning, and is currently the subject of intense interest due to applications in Bayesian statistics [] and energy-based models in deep learning [], among other areas. In these settings, the normalizing constant of the target distribution $\pi$ is typically intractable, and Markov Chain Monte Carlo (MCMC) algorithms [, ] are commonly used to generate Markov chains in the ambient space, whose law eventually approximates the target distribution.

Among MCMC algorithms, the Unadjusted Langevin Algorithm (ULA), which corresponds to a time discretization of a Langevin diffusion process, has attracted considerable attention due to its simplicity, theoretical grounding, and utility in practice [, , , ]. For example, ULA can be proven to converge quickly when the target distribution $\pi$ is smooth and strongly log-concave []. However, many cases in practice require to sample from distributions which are not log-concave, and indeed potentially even multi-modal [, ]. In such settings, the convergence of ULA is governed by functional inequalities which effectively quantify the convexity, or lack thereof, of the target distribution []. Nonetheless, truly multi-modal target distributions generally have poor functional inequalities, thus leading to weak convergence guarantees for ULA. This phenomenon is not merely a theoretical artifact, and it is well-known amongst practitioners that when sampling from multi-modal distributions, algorithms based on ULA can get stuck in local modes and suffer from slow convergence [].

*Tempering* or *annealing* is a popular technique [, , ] to overcome the deficiencies of ULA and other MCMC methods in the multi-modal setting. Rather than sample directly from the target distribution $\pi$, tempering samples from a sequence of distributions that interpolate between an easier, unimodal proposal distribution $\nu$ and the more challenging $\pi$. Intuitively, tempering may help escape local modes and explore the entire target distribution []. Many possible interpolating paths for tempering exist, but to be practically useful the path must be implementable with the chosen MCMC scheme, and should improve convergence when compared the latter run directly against the target $\pi$.

One of the most popular choices for the tempering path is the geometric tempering [, ], where the intermediate distributions are defined to be the geometric averages $\mu_{\lambda}\propto\nu^{1-\lambda}\pi^{\lambda}$ with $\lambda\in[0,1]$ the (inverse) temperature parameter. At a “hot” temperature, $\lambda$ is close to 0 0 and the distribution $\mu_{\lambda}$ is close to the proposal which can be chosen with large variance for better exploration, and when the temperature is gradually “cooled” to $\lambda=1$, $\mu_{\lambda}$ recovers the original target $\pi$. In practice, the geometric tempering does not require access to the normalizing constants, and has accordingly been widely applied to various MCMC methods [, ]. However, theoretical understanding of the geometric tempering is limited. This includes identifying situations where it improves upon standard sampling procedures as well as offering guidance for the selection of the temperature schedule, a crucial question in practice where a number of heuristics have been proposed [, , , ].

#### Contributions.

In this paper, we develop theoretical understanding of geometric tempering combined with Langevin dynamics: we refer to this as tempered Langevin dynamics. We make three main contributions:

- 1.
We provide in Theorems 1 and 3 the first convergence result for tempered Langevin dynamics in Kullback-Leibler divergence (KL).
Our results here are for general tempering
schedules and
depend on the functional inequalities (log-Sobolev)
of the intermediate distributions along the tempering
sequence.
In Proposition 6
we derive the optimal tempering schedule
for our continuous time upper bound in
the strongly log-concave setting.
- 2.
To go beyond the strongly-log concave
setting, we must understand the behavior of
functional inequalities
along the geometric tempering.
Our result here, Theorem 4,
is negative, and shows that, surprisingly, even when the proposal and target have favorable functional inequalities, the geometric tempering can exponentially worsen these inequalities.
- 3.
Although the poor functional inequalities in Theorem 4 are a worrying sign for the geometric tempering, they do not yet rule out fast convergence since functional inequalities only govern
worst-case convergence. We thus analyze a simple bi-modal example where we show in Theorem 8 that the geometric path takes exponential time to converge in total variation (TV), and then show
in Theorem 9 that, surprisingly, similar results even hold for a uni-modal target with favorable functional inequalities.

In sum, our results establish sufficient
conditions for the tempered Langevin dynamics
to converge in KL divergence. We find some limited situations where these improve
upon the rates
of standard Langevin dynamics, but we also find that the geometric tempering
can worsen functional inequalities and suffer from slow convergence,
both in the setting of multi-modal target and even for
uni-modal targets with reasonable functional inequalities.

#### Organization.

This paper is organized as follows.
In the remainder of this section we discuss
related work and describe our notation.
In section 2, we discuss background
about ULA
and geometric tempering.
In section 3,
we state our upper bounds in KL on the convergence of the geometric
tempering with Langevin dynamics under functional inequalities,
both in continuous and discrete time.
In section 4, we
show that the geometric path can have poor
functional inequalities even when the proposal and target do not;
yet, in the strongly-concave case, we derive explicit results from our upper bounds
and highlight situations where tempering may be beneficial.
In section 5,
we describe two examples where geometric tempering with ULA
provably has slow convergence in TV.
Proofs and additional numerical validations are collected in the Appendix.

#### Related work.

Given the empirical success of ULA with a sequence of tempered target distributions it is desirable to obtain theoretical guarantees on the convergence of the scheme,
and especially to understand when and why certain sequences of moving targets can guide or misguide
the sampling process towards the final target.
Closely related to our setting, Tang et al., [] also study the convergence of tempered Langevin dynamics for the geometric sequence. However, they focus on the simulated annealing setting. In this case the geometric sequence is taken as $\pi^{\lambda}$, that degenerates to a target distribution which is a Dirac located at the global maximum of the log density of $\pi$
as $\lambda$ goes to infinity, so that sampling actually becomes an optimization task [, ]. Using an explicit temperature
schedule, they measure convergence in probability.
For another sequence of intermediate targets obtained by convolving the target and proposal distributions, and using an explicit schedule, Lee et al., [] prove fast convergence in TV.
Finally, for a general sequence of intermediate targets,  Guo et al., [] very recently obtained a rate of convergence that depends on Wasserstein metric derivative along the path of distributions: their result suggests that an optimal path can be obtained as a Wasserstein geodesic between the initial and target distributions. A modification of tempered Langevin dynamics, called Sequential Monte Carlo, that importantly includes resampling of particles, has been shown to achieve fast convergence in TV [, , , ]. These results apply to different sampling processes and rely on strong assumptions, effectively modeling far-away modes by disjoint sets [, ], using a specific path that interpolates between a uniform and target distribution by increasing the number of components that follow the target’s law Paulin et al., [], or assuming uniformly bounded consecutive distributions along the path []. In contrast, our results are specific to the geometric sequence, but we obtain upper and lower bounds on convergence that explicitly depend on the time.

The tempered iterates defined by the geometric path are also at the basis of simulated or parallel tempering schemes [, , , ], which are MCMC algorithms where the temperature is a random variable instead of a monotonic function of time. Both schemes produce samples at all temperatures and involve swapping particles between hotter and colder temperatures. In that setting, some works have investigated the spectral gap of these methods, which is related to the rate of convergence in
$\mathop{\mathrm{TV}}\nolimits$ distance [, , ].
When that rate is polynomially (resp. exponentially) decreasing in the problem size,
convergence is said to be fast (resp. ‘torpid’). These rates are studied for arbitrary target distributions, using lower and upper bounds. Namely, Woodard et al., 2009b [], Woodard et al., 2009a [] show that for target distributions which have modes with different weights or shapes, convergence can be slow, and that symmetric modes are required for fast convergence. This generalizes previous findings that for specific targets with two symmetric and equally weighted modes, convergence is fast [], whereas for another specific target with three asymmetric modes, convergence is slow for any schedule [].  Ge et al., [] also prove fast convergence when the target is a Gaussian mixture.
More recently, Chen et al., [] study the Poincaré constant in parallel tempering, which governs the rate of convergence in
$\chi^{2}$ divergence: they show it improves upon standard Langevin, and relate this improvement to the exchange rate of particles between different temperatures.
Our work differs in several important ways: we study a different sampling algorithm (Unadjusted Langevin algorithm), obtain upper and lower bounds directly in time rather than on the spectral gap, and prove explicit rates of convergence,
as well as lower bounds, for simple choices of proposal and target distributions.

#### Notation.

$\mathcal{C}_{c}^{\infty}(\mathbb{R}^{d})$ denotes the set of infinitely differentiable functions with compact support. $\mathcal{P}(\mathbb{R}^{d})$ denotes the set of probability measures $p$ on $\mathbb{R}^{d}$. For $p\in\mathcal{P}(\mathbb{R}^{d})$, we denote that $p$ is absolutely continuous w.r.t. $q$ using $p\ll q$ and we use $dp/dq$ to denote the Radon-Nikodym derivative. The set of probability measures which are absolutely continuous with respect to the Lebesgue measure is written $\mathcal{P}_{\rm ac}(\mathbb{R}^{d})$. The Total Variation (TV) distance is defined as $\mathrm{TV}(p,q):=\sup_{A\subset\mathbb{R}^{d}}|p(A)-q(A)|$, where the supremum runs over all Borel sets. For any $p\in\mathcal{P}(\mathbb{R}^{d})$, $L^{2}(p)$ is the space of functions $f:\mathbb{R}^{d}\to\mathbb{R}$ such that $\int\|f\|^{2}dp<\infty$. We denote by $\|\cdot\|_{L^{2}(p)}$ and $\langle\cdot,\cdot\rangle_{L^{2}(p)}$ respectively the norm and the inner product of the Hilbert space $L^{2}(p)$. For $p\ll q$, the Kullback-Leibler (KL) divergence is defined as $\mathop{\mathrm{KL}}\nolimits(p,q)=\int\log\big(\frac{dp}{dq}\big{missing})dp$, the $\chi^{2}$-divergence as $\chi^{2}(p,q):=\int\big{(}\frac{dp}{dq}-1\big{)}^{2}\mathrm{d}q$ and the Fisher-divergence as $\mathop{\mathrm{FD}}\nolimits(p,q)=\big{\|}\nabla\log\big(\frac{dp}{d\pi}\big{
missing})\big{\|}^{2}_{L^{2}(p)}$, and $+\infty$ otherwise. For a measurable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ we define the variance $\mathrm{Var}_{p}(f):=\mathbb{E}_{p}[(f-\mathbb{E}_{p}[f])^{2}]$ for $p\in\mathcal{P}(\mathbb{R}^{d})$. We write the standard Gaussian on $\mathbb{R}$ with mean $a$ and variance $\sigma^{2}$ as $\mathcal{N}(a,\sigma^{2})$, and the uniform measure on a Borel set $A\subset\mathbb{R}^{d}$ with finite and positive Lebesgue measure as $\mathrm{unif}_{A}$.
Given a closed set $A\subset\mathbb{R}^{d}$ we define $d(x,A):=\inf_{y\in A}\|x-y\|$ for all $x\in\mathbb{R}^{d}$.
Finally, we define the error function
by $\erf(z):=\frac{2}{\sqrt{\pi}}\int_{0}^{z}e^{-x^{2}}\mathrm{d}x$.

## 2 Background

In this section, we provide some background on functional inequalities,
Langevin dynamics, and geometric tempering.

#### Functional inequalities.

Let $q\in\mathcal{P}_{\rm ac}(\mathbb{R}^{d})$. We say that $q$ satisfies the Poincaré inequality with constant $C_{P}\geq 0$ if for all $f\in\mathcal{C}_{c}^{\infty}(\mathbb{R}^{d}),$

$$ $\mathrm{Var}_{q}(f)\leq C_{P}\|\nabla f\|^{2}_{L^{2}(q)},$ (1) $$

and let $C_{P}(q)$ be the best constant in Eq. 1, or $+\infty$ if it does not exist. We say that $q$ satisfies the log-Sobolev inequality with constant $C_{LS}$ if for all $f\in\mathcal{C}_{c}^{\infty}(\mathbb{R}^{d})$,

$$ $\mathrm{ent}_{q}(f^{2}):=\mathbb{E}_{q}\Big{[}f^{2}\ln\Big(\frac{f^{2}}{ \mathbb{E}_{q}[f^{2}]}\Big{missing})\Big{]}\leq 2C_{LS}\|\nabla f\|^{2}_{L^{2} (q)},$ (2) $$

and let $C_{LS}(q)$ be the best constant in Eq. 2, or $+\infty$ if it does not exist. Note that log-Sobolev implies Poincaré with the same constant [], so that $C_{LS}(q)\geq C_{P}(q)$. If $q\propto e^{-V}$ and the potential $V$
is $\alpha_{q}$-strongly convex, then $q$ satisfies Eq. 2 with constant $\frac{1}{\alpha_{q}}$. However, the latter is more general,
including for instance distributions $q$ whose potential are bounded perturbations of a strongly convex potential [, ].

#### Langevin dynamics.

Let $\pi\in\mathcal{P}_{\rm ac}(\mathbb{R}^{d}).$ The Unadjusted Langevin Algorithm (ULA) [, ] consists in sampling a target distribution $\pi$ using noisy gradient ascent

$$ $\displaystyle X_{k+1}=X_{k}+h_{k}\nabla\log\pi(X_{k})+\sqrt{2h_{k}}\epsilon_{k },\quad\epsilon_{k}\sim\mathcal{N}(0,\mathrm{I}_{d})$ (3) $$

with step size $h_{k}>0$ at iteration $k\in\mathbb{N}$. Setting time as $t=h_{k}k$ and taking the continuous limit obtained as $h\rightarrow 0$, Eq. 3 defines a continuous process known as the Langevin diffusion. The convergence of the law of the Langevin diffusion to the equilibrium measure $\pi$ is then governed by the Poincaré and log-Sobolev inequalities. In particular, if we denote the law of the Langevin diffusion at time $t$ by $p_{t}$, then $p_{t}$ converges to $\pi$ in KL with exponential rate determined by the log-Sobolev constant
of $\pi$ [, Theorem 2], namely

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)\leq e^{-2C_{LS}(\pi)^{-1 }t}\mathop{\mathrm{KL}}\nolimits(p_{0},\pi).$ (4) $$

However, for multi-modal distributions such as Gaussian mixtures, the log-Sobolev constant can grow exponentially with the distance between modes []. Nevertheless, ULA remains a popular choice, due to its computational simplicity: simulating Eq. 3 only requires access to the score $\nabla\log\pi$ which does not depend on the target’s normalizing constant.

#### Langevin with moving targets.

Many heuristics broadly known as annealing or tempering consist in using ULA to sample a path, or sequence of distributions $(\mu_{t})_{t\in\mathbb{R}_{+}}$ instead of the single target $\pi$. The hope is that this sequence of intermediate distributions will improve the convergence of the ULA sampler. Different tempering algorithms sample the path sequentially in time [, , ], back-and-forth in time [, , ], or at all times jointly [, ]. This paper deals with the first case, i.e.,

$$ $\displaystyle X_{k+1}=X_{k}+h_{k}\nabla\log\mu_{k}(X_{k})+\sqrt{2h_{k}} \epsilon_{k},\quad\epsilon_{k}\sim\mathcal{N}(0,1)$ (5) $$

where the target now is updated (“moved”) at each iteration. This generic sampling method has been used in high-dimensional spaces [, , , ] and has achieved state-of-the-art results for sampling images, where it is sometimes known by the names Annealed Langevin Dynamics [] or the “corrector” sampler []. It is therefore of interest to find moving targets whose geometry is well-suited to ULA’s convergence properties.
A number of paths $(\mu_{t})_{t\in\mathbb{R}_{+}}$ can be used to guide the process toward the final target $\pi$. Many of them interpolate between a proposal distribution $\nu$ that is easy to sample and the target distribution $\pi$, for example by taking their convolution [, , ], their geometric mean [], or following the gradient flow of a loss from proposal to target [, , ].
The path obtained by convolving the two distributions is the default choice for sampling from so-called “diffusion models”, yet the scores $\nabla\log\mu_{t}$ along that path are not analytically tractable in our setting when the density of $\pi$ is known up to a normalization constant, and estimating them is the subject of current research [, , , ].

#### Geometric tempering.

The path obtained by taking the geometric mean of the proposal and target distributions has distinguished itself in the sampling literature [, ]. It is written as

$$ $\displaystyle\mu_{t}(x)$ $\displaystyle=c_{\lambda_{t}}\nu(x)^{1-\lambda_{t}}\pi(x)^{\lambda_{t}},\quad t \in\mathbb{R}_{+},$ (6) $$

where $c_{\lambda_{t}}$ is a normalizing factor, $\nu\in\mathcal{P}_{ac}(\mathbb{R}^{d})$ is a proposal distribution and $\lambda(\cdot):\mathbb{R}_{+}\rightarrow[0,1]$ is an increasing function called the tempering schedule. It has recently been shown
that the geometric path can be identified to a time-discretized gradient flow of the Kullback-Leibler divergence to the target, with respect to the Fisher-Rao distance [, ]. Its main advantage is its computational tractability, since the score of $\nabla\log\mu_{t}=(1-\lambda_{t})\nabla\log\nu+\lambda_{t}\nabla\log\pi$ is known in closed-form. This path is a default in some sampling libraries [] and remains a popular choice in recent sampling literature [, , ] and
applications [, , , ].
A special case of the geometric path is especially popular, choosing a “uniform” $\nu$: $\pi_{t}(x)=c_{t}\pi_{1}(x)^{\lambda_{t}}$;
this choice is
commonly used in practice to sample from un-normalized distributions parameterized by a deep neural network [, , , ] or for global optimization []. Otherwise, $\nu$ is often chosen as a simple distribution, such as a Gaussian [, , ].

## 3 Convergence rate
for tempered Langevin dynamics

Throughout, we take as given proposal and target distributions $\nu$ and $\pi$, as well as a temperature schedule $\lambda\colon\mathbb{R}_{+}\to[0,1]$, which we assume satisfy the following conditions.

###### Assumption 1 (Regularity of proposal, target, and tempering)

The proposal $\nu$ and the target $\pi$ have densities with respect to Lebesgue, which we write $\nu\propto e^{-V_{\nu}}$ and $\pi\propto e^{-V_{\pi}}$. The tempering schedule $(\lambda_{t})_{t\geq 0}$ is such that $\lambda\colon\mathbb{R}_{+}\to[0,1]$ and $\lambda_{t}$ is non-decreasing in $t$ and weakly differentiable.

In addition to this basic regularity, we also make the following
quantitative assumptions on the negative log densities.

###### Assumption 2 (Lipschitz gradients and dissipativity)

The negative log densities $V_{\nu}$, $V_{\pi}$ have Lipschitz continuous gradients on all of $\mathbb{R}^{d}$, with Lipschitz constants $L_{\nu},L_{\pi}$, respectively. In addition, $V_{\nu}$ and $V_{\pi}$ satisfy the dissipativity inequalities

$$ $\langle\nabla V_{\nu}(x),x\rangle\geq a_{\nu}\|x\|^{2}-b_{\nu},\quad\quad \langle\nabla V_{\pi}(x),x\rangle\geq a_{\pi}\|x\|^{2}-b_{\pi},$ (7) $$

with constants $a_{\nu},a_{\pi},b_{\nu},b_{\pi}>0$.

The Lipschitz assumption is used both for
our discrete time results as well
as in
guaranteeing existence and uniqueness of the continuous time dynamics;
see Appendix A.1 for more discussion
on this latter point.
The dissipativity condition is common in the sampling literature [, ]
as it implies
a finite log-Sobolev constant under Lipschitz gradients [].
Our only quantitative use of the dissipativity condition
will be to get control on the second moments
of the tempering dynamics,
but it is also convenient to ensure
the log-Sobolev constants remain finite along
the tempering path.
Indeed,
dissipativity of both $V_{\nu}$ and $V_{\pi}$ implies
dissipativity of $\mu_{t}$ from Eq. 6,
so $C_{LS}(\mu_{t})<\infty$. Our results will
crucially rely on the size of the inverse of these log-Sobolev
constants, so we define the notation

$$ $\alpha_{t}:=C_{LS}(\mu_{t})^{-1}>0,\quad\quad\forall t\geq 0.$ (8) $$

As a simple example, notice that if $V_{\nu},V_{\pi}$ are $\alpha_{\nu},\alpha_{\pi}$
strongly convex, then $\alpha_{t}\geq(1-t)\alpha_{\nu}+t\alpha_{\pi}$.
In section 4.1,
we investigate how $\alpha_{t}$ depends on the log-Sobolev
constants of $\nu$ and $\pi$, and here proceed with the statement
of our convergence results.

Given the proposal $\nu$ and target $\pi$, as well
as a tempering schedule $(\lambda_{t})_{t\geq 0}$,
we are interested in the tempered Langevin dynamics,
where the moving target is
the geometric path $\mu_{t}$, as defined in Eq. 6.
In continuous time, this is the stochastic differential equation

$$ $\displaystyle dX_{t}$ $\displaystyle=-\big{(}(1-\lambda_{t})\nabla V_{\nu}+\lambda_{t}\nabla V_{\pi} \big{)}\mathrm{d}t+\sqrt{2}\mathrm{d}W_{t},$ (9) $$

with initialization $X_{0}\sim p_{0}$ for some $p_{0}\in\mathcal{P}(\mathbb{R}^{d})$, and where $W_{t}$ is a standard $d$-dimensional Brownian motion. We denote by $p_{t}$ the density of $X_{t}$ given by the continuous time dynamics Eq. 9.
Our main upper bound in continuous time follows.

###### Theorem 1 (Continuous time)

Suppose Assumption 1 and 2
hold,
and let $(\alpha_{t})_{t\geq 0}$ be the inverse log-Sobolev constants as in Eq. 8,
assumed to be integrable.
Let $p_{t}$ be the law of Eq. 9 with initialization $p_{0}$ and denote by $\dot{\lambda}_{t}$ the weak time derivative of the tempering schedule.
Then, for all $t\geq 0$:

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)$ $\displaystyle\leq\exp(-2\int_{0}^{t}\alpha_{s}ds)\mathop{\mathrm{KL}}\nolimits (p_{0},\mu_{0})+A(1-\lambda_{t})+A\int_{0}^{t}\dot{\lambda}_{s}\exp(-2\int_{s} ^{t}\alpha_{v}dv)ds$ (10) $$

where $A=2(L_{\pi}+L_{\nu})(\frac{2(d+b_{\nu}+b_{\pi})}{a_{\nu}\land a_{\pi}}+\mathbb
{E}_{p_{0}}[\|x\|^{2}])$
depends on the
constants from Assumption 2,
the second moment of the initial distribution $p_{0}$,
and linearly on the dimension $d$.

The proof of Theorem 1 can be found in Section A.2.
To the best of our knowledge, Theorem 1
is the first convergence analysis of Tempered Langevin dynamics, namely Eq. 9,
in the literature.
The first two terms of the upper bound
deal with the start and end of the tempering: the first one measures the convergence rate to the first tempered distribution $\mu_{0}$
and the second one
measures how far the current tempered distribution is from the target.
The first term is set to zero when the schedule starts with
$\lambda_{t}=0$ and the sampling process Eq. 9 is initialized with the proposal $p_{0}=\nu$. The second term is null when $\lambda_{t}=1$ at the time when convergence is evaluated. The last term in the upper bound involves the tempering speed $\dot{\lambda}$, as well as the geometry of the moving targets $\mu_{t}$ via their inverse log-Sobolev constants $\alpha_{t}$ between inverse temperatures $\lambda_{0}$ and $\lambda_{t}$,
and, in particular, is null
when the annealing schedule is constant.
Note that, in Appendix A.3,
we translate Theorem 1
to give sufficient conditions for convergence to the target at precision $\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)<{\epsilon}$.

###### Remark 2 (Recovering standard upper bound for Langevin dynamics without tempering)

Notice that Eq. 9
recovers standard Langevin dynamics when we
set $\lambda_{t}\equiv 1$ for all $t\in\mathbb{R}_{+}$.
In this case, only the first term in the upper bound
is non-zero, and the bound recovers the standard continuous-time upper bound for Langevin dynamics,
as recalled in Eq. 4.

Next, we analyze the Euler-Maruyama discretization
of the continuous time Tempered Langevin Dynamics Eq. 9.
Namely, we take $X_{0}\sim p_{0}$ and then,
for a tempering sequence $(\lambda_{k})_{k\geq 0}$ and
a sequence of step-sizes $(h_{k})_{k\geq 0}$,
we follow the iteration

$$ $X_{k+1}=X_{k}-h_{k+1}((1-\lambda_{k+1})\nabla V_{\nu}+\lambda_{k+1}\nabla V_{ \pi})+\sqrt{2h_{k+1}}{\epsilon}_{k+1},$ (11) $$

where ${\epsilon}_{k+1}$ is
independent standard Gaussian noise.
In other words, at each iteration $k$ we take
a Langevin step of size $h_{k+1}$ towards $\mu_{k+1}:=c_{k+1}\nu^{1-\lambda_{k+1}}\pi^{\lambda_{k+1}}$.

###### Theorem 3 (Discrete time)

Suppose Assumptions 1 and 2 hold, and
let $(\alpha_{k})_{k\geq 1}$ be the inverse log-Sobolev constants as in Eq. 8.
Define the smoothness constant of the tempered path
to be $L_{k}:=(1-\lambda_{k})L_{\nu}+\lambda_{k}L_{\pi}$, and let $p_{k}$ be the law of Eq. 5 with initialization $p_{0}$. Then, so long as

$$ $h_{k}\leq\min(\frac{\alpha_{k}}{4L_{k}^{2}},\frac{a_{\pi}\land a_{\nu}}{2(L_{ \pi}+L_{\nu})^{2}},1)$ $$

for all $k$, we have

$$ $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)\leq\exp\Big(-\sum_{j=1}^{k}\alpha_{j} h_{j}\Big{missing})\mathop{\mathrm{KL}}\nolimits(p_{0},\mu_{0})+A^{\prime}(1- \lambda_{k})\\ +(\lambda_{i}-\lambda_{i-1})\exp\Big(-\sum_{j=i}^{k}\alpha_{j}h_{j}\Big{ missing})+6\sum_{i=1}^{k}h_{k}^{2}dL_{k}^{2}\exp\Big(-\sum_{j=i+1}^{k}\alpha_{ j}h_{j}\Big{missing})$ (12) $$

where $A^{\prime}=2(L_{\pi}+L_{\nu})\big{(}\max\big{(}\mathbb{E}_{p_{0}}[\|x\|^{2}],
\frac{2(3(b_{\pi}+b_{\nu})/2+d)}{a_{\pi}\land a_{\nu}\land 1}\big{)}+\frac{3(d
+b_{\nu}+b_{\pi})}{a_{\pi}\land a_{\nu}}\big{)}$
depends on the constants from Assumption 2,
the second moment of the initial distribution $p_{0}$, and linearly on the dimensional $d$.

The proof of Theorem 3 can be found in Appendix B.
The first three terms are the discrete-time equivalent of those obtained in the continuous-time setup of Theorem 1.
The novelty is the fourth term which is the bias from the discretization: it becomes null as the step sizes $h_{k}$ tend to zero. Otherwise, it involves the geometry of the intermediate target distributions via their smoothness constants $L_{k}$, additionally to their inverse log-Sobolev constants $\alpha_{k}$.
Again, when there is no tempering, i.e. setting $\lambda_{k}\equiv 1$, since the second and third term cancel, we recover the known upper bound on the convergence of ULA [, Th. 2] up to a multiplicative constant.
Similarly to the continuous case, we derive in Appendix B.2
sufficient conditions for converging to the target with a given precision $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)<{\epsilon}$.

Understanding the upper bounds in this section
mainly involves two key points: the geometry of the moving targets via their inverse log-Sobolev constants $\alpha_{t}$, and the tempering schedule $\lambda(\cdot)$.
These will be the focus of the next sections.

###### Assumption 1 (Regularity of proposal, target,
and tempering)

###### Assumption 2 (Lipschitz gradients
and dissipativity)

###### Theorem 1 (Continuous time)

###### Remark 2 (Recovering standard
upper bound for Langevin dynamics without tempering)

###### Theorem 3 (Discrete time)

## 4 Analysis and optimization of the upper-bounds

In this section we explore the continuous-time upper bound
from Theorem 1.
We first present in section 4.1 a simple example where the log-Sobolev constants of the intermediate
distributions along the geometric mean path can be exponentially worse than those of the target and proposal.
Motivated by this result,
we then conduct a detailed study of the
optimal tempering schedule in section 4.2
in the setting
where both $\nu$ and $\pi$ are strongly log-concave.

### 4.1 Geometric tempering can exponentially
worsen functional inequalities

Because of the fundamental role that log-Sobolev constants
play in governing the convergence of Langevin dynamics without
tempering, it is natural that our upper bounds for
tempered Langevin dynamics
depend on the log-Sobolev constants of the intermediate distributions.
Nonetheless, the size of these log-Sobolev constants
is crucial for ensuring rapid convergence of tempered Langevin dynamics.
We are thus led to ask a fascinating yet, to the best
of our knowledge,
new question: how do the log-Sobolev constants
along the geometric tempering path depend on the
proposal and target distributions?

Figure: Figure 1: Bi-modal intermediate distribution at $\lambda=0.45$ with $\nu,\pi$ as in Eq. 13 for $m=10$.
Refer to caption: x1.png

Developing a complete answer to this question is an interesting direction
for future work, but here we provide a simple example which shows that,
in general, the geometric path can actually make functional
inequalities exponentially worse.
As is commonly done in practice, we take the
proposal distribution $\nu$ to be Gaussian [, , ].
For the target, we take a parameter $m>0$ and put

$$ $\pi:=(1-e^{-m^{2}/4})\mathcal{N}(m,1)+e^{-m^{2}/4}u_{m},$ (13) $$

where $u_{m}$ is the smoothed
uniform distribution on $I_{m}:=[-m,2m]$
with density proportional to $e^{-\frac{1}{2}d(x,I_{m})^{2}}$.
Note that without the small mixing with the smoothed uniform
distribution in Eq. 13,
the target $\pi$ would be strongly log-concave,
and the geometric path would remain well-conditioned.
The next result shows that while this small mixing does not
greatly worsen the log-Sobolev constant of $\nu$,
it does cause the geometric tempering
to have exponentially worse log-Sobolev constant,
in fact even Poincaré constant.

###### Theorem 4

Let $\nu:=\mathcal{N}(0,1)$ and $\pi$ be as defined in Eq. 13
for $m\geq 10$.
Then $C_{LS}(\nu)=1$ and $C_{LS}(\pi)\leq 81m^{5}$,
yet for all $\lambda\in[\frac{1}{2},1]$,

$$ $\displaystyle C_{P}(\mu_{\lambda})\geq\frac{1}{4\cdot 10^{4}m}e^{m^{2}(1- \lambda)/100}-m^{2}.$ $$

Since $C_{LS}(\cdot)\geq C_{P}(\cdot)$,
the above holds, in particular, with $C_{LS}(\mu_{\lambda})$
on the left-hand side.

The proof of Theorem 4 can be found in Section D.3.
This example is plotted in Figure 1;
the intuition is that while
both distributions are unimodal and thus
well-conditioned,
the small mixing with the uniform measure creates multi-modality
in the geometric tempering.
The proof relies on careful analysis to characterize
this multi-modality, and then uses a test function which simply linearly interpolates
between the modes to witness
the exponentially large Poincaré constant.

Theorem 4
rules out the possibility that the geometric tempering
generically improves, or even preserves, functional inequalities. Since our upper bounds
depend on the log-Sobolev constants of the geometric
tempering, they also can suffer from such exponentially
poor conditioning. But since log-Sobolev inequalities
only govern worst-case convergence, it is
still at least a priori possible
that geometric tempering nonetheless achieves
fast convergence.
We investigate
this question further in section 5,
and here instead continue exploring
our upper bounds.

###### Theorem 4

### 4.2 Optimal tempering in the strongly log-concave case

Other than the log-Sobolev constants $\alpha_{t}$, the main input to our upper bounds is the tempering schedule
$\lambda$, and in this section we use our upper
bounds to investigate the optimal schedule, an important
question in practice [, ].
Both to make our analysis tractable and because
of the degeneracy in the non log-concave case
identified in the previous section, we here restrict
to the strongly log-concave setting.
Specifically, we assume that both the proposal $\nu$ and the target $\pi$
are log-concave with strong-concavity parameters $\alpha_{\pi},\alpha_{\nu}>0$.
In this case, $\alpha_{t}\geq(1-\lambda_{t})\alpha_{\nu}+\lambda_{t}\alpha_{\pi}$.

We start by reformulating the continuous time result
that we obtained in Theorem 1, in the case where both the proposal $\nu$ and target $\pi$ are log-concave.

###### Corollary 5

Suppose $\nu$ and $\pi$
satisfy Assumptions 1 and 2,
are $\alpha_{\nu}$ and $\alpha_{\pi}$-strongly log-concave respectively
so that
$\alpha_{t}\geq\lambda_{t}\alpha_{\pi}+(1-\lambda_{t})\alpha_{\nu}$,
and that the process is initialized at the proposal distribution $p_{0}=\nu$.
Then for all $t\geq 0$, we have

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)\leq AG_{t}(\lambda), \quad\quad G_{t}(\lambda):=1-2\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\big(-2\int _{s}^{t}\alpha_{v}\mathrm{d}v\big{missing})\mathrm{d}s,$ (14) $$

where $A$ is as in Theorem 1.
Suppose additionally that $\alpha_{\pi}\geq\alpha_{\nu}$. Then
$G_{t}(\lambda)$ is minimized by the vanilla
Langevin scheme $\lambda(t)\equiv 1$.

The proof of Corollary 5 is in Appendix C.1 and relies on integration by parts. This new expression allows us to optimize on the schedule $\lambda$ independently of the *unknown* quantity $A$. As one could expect, the corollary above states that when the target $\pi$ is already better conditioned than the proposal $\nu$, so $\alpha_{\pi}\geq\alpha_{\nu}$, there is no need to temper and the optimal tempering scheme is given by vanilla Langevin $\lambda\equiv 1$. In the next proposition, we show on the contrary that if $\pi$ is too poorly conditioned with respect to $\nu$, then one should indeed use a custom tempering scheme other than Langevin.

###### Proposition 6

Suppose $\alpha_{\pi}<\alpha_{\nu}$.
Then the functional $G_{t}(\lambda)$ is minimized for the scheme

$$ $\displaystyle\lambda(s)=\min\bigg{(}\frac{\alpha_{\nu}}{\alpha_{\nu}-\alpha_{ \pi}}\frac{1+\alpha_{\nu}s}{2+\alpha_{\nu}s},1\bigg{)}.$ (15) $$

In particular, the optimal schedule does not
depend on the horizon $t$, and when
$\alpha_{\pi}\geq\alpha_{\nu}/2$,
vanilla Langevin $\lambda(t)\equiv 1$ is optimal.

Proposition 6 is proven in Appendix C.2.
Hence when the target is sufficiently peakier than the proposal $\alpha_{\pi}\geq\alpha_{\nu}/2$, tempering does not improve
convergence beyond that of vanilla Langevin. Conversely, when the target is flat enough $\alpha_{\pi}<\alpha_{\nu}/2$, then tempered Langevin with the schedule in Eq. 15 does improve convergence over vanilla Langevin. While the optimal schedule is provided analytically in Eq. 15, it cannot be computed exactly in practice given that the constant $\alpha_{\pi}$ that describes the geometry of the target distribution is unknown. On the other hand,
in the limit of a flat and log-concave target $\alpha_{\pi}\rightarrow 0$, the optimal schedule tends to $\lambda(s)=1-\frac{1}{2+\alpha_{\nu}s}$, which can be implemented in practice.

A natural question follows: can other schedules, which may not be optimal but are feasible to implement in general, actually improve convergence beyond that of vanilla Langevin? A simple example is
the linear schedule. Here, we obtain an explicit convergence rate that does not improve on standard Langevin at large times, but that is faster than standard Langevin at small times for small $\alpha_{\pi}$.

###### Proposition 7

Assume $\alpha_{\nu}>\alpha_{\pi}$.
Let $t>0$ until which the continuous process  9 is run. Then, with the linear tempering scheme $\lambda(s)\equiv\frac{s}{t}$ defined on [0,t], $G_{t}$ in the upper-bound of Corollary 5 writes

$$ $G_{t}(\lambda)=\sqrt{\frac{\pi}{4t(\alpha_{\nu}-\alpha_{\pi})}}\biggl{\{} \operatorname{erfcx}\biggl{(}\alpha_{\pi}\sqrt{\frac{t}{\alpha_{\nu}-\alpha_{ \pi}}}\biggr{)}-e^{-(\alpha_{\nu}+\alpha_{\pi})t}\operatorname{erfcx}\biggl{(} \alpha_{\nu}\sqrt{\frac{t}{\alpha_{\nu}-\alpha_{\pi}}}\biggr{)}\biggr{\}},$ $$

where $\operatorname{erfcx}$ is the complementary scaled error function
$\operatorname{erfcx}(x)=e^{x^{2}}(1-\erf(x))$.
In particular, as $t\to\infty$,
we have $G_{t}(\lambda)\sim\frac{1}{2\alpha_{\pi}t}$.

Figure: Figure 2: Value of the upper-bound $G$ uling the optimal tempering, linear tempering, and standard Langevin.
Refer to caption: x2.png

The proof of Proposition 7 appears in Appendix C.3.

Finally, we compare in Figure 2 the value of the upper-bound $G$ at different time horizons $t$ using
optimal tempering scheme given in Eq. 15, the linear tempering scheme $\lambda(s)\equiv\frac{s}{t}$ and vanilla Langevin $\lambda(s)\equiv 1$, for $\alpha_{\pi}=0.01$ and $\alpha_{\nu}=1.0$. We observe that the optimal schedule always yields a lower value of $G$ (as it should) and that it provides a clear advantage over vanilla Langevin at short horizons $t$. However, as the horizon grows, this edge is eventually lost. Similarly, we observe that the linear tempering schedule improves over vanilla Langevin at short time horizons yet is eventually beaten as the horizon grows.

###### Corollary 5

###### Proposition 6

###### Proposition 7

## 5 Exponentially
slow convergence for tempered
Langevin dynamics

The upper bounds in
Theorem 3
show that,
so long as the log-Sobolev constants
remain well-behaved along the geometric tempering,
Langevin with moving target can successfully sample
from the target distribution.
While this assumption holds in favorable
cases where the proposal and target are both
strongly log-concave, it may fail even when
both distributions are well-conditioned yet not
log-concave,
as demonstrated in Theorem 4.
Nevertheless, such
poor functional inequalities
do not necessarily rule out fast convergence of the geometric
tempering because
functional inequalities only govern mixing in the worst case,
and so it is still possible a priori
that our upper bounds are loose in such cases.
The purpose of this section is to develop
rigorous lower bounds for the geometric tempering in two
simple examples where the log-Sobolev constants
of the intermediate distributions are poor.

#### Setup.

Throughout this section, we let the proposal
distribution
be the standard Gaussian $\nu:=\mathcal{N}(0,1)$,
as is common for the geometric tempering [, , , ].
We work in the setting
of a discrete temperature schedule but with continuous
time inner Langevin iterations.
In particular, we take as fixed
a discrete temperature
schedule $\lambda_{0}=0<\lambda_{1}<\cdots<\lambda_{K-1}<\lambda_{K}=1$
and a sequence of times $T_{1},\ldots,T_{K}$ that the
inner Langevin iteration is run for.
We then
put $p^{0}_{T_{0}}:=\nu$ and define
inductively $p^{k}_{t}$ to be the law at time $t$
of Langevin initialized
at $p^{k-1}_{T_{k-1}}$
and run towards
$\mu_{k}$.
Our goal is then to study the convergence
of the final output $p^{K}_{T_{K}}$ towards $\pi$,
as a function of the temperature and time sequences,
as well as the target $\pi$.

#### Bi-modal target.

Since annealing is designed to
overcome multi-modality and associated poor mixing
in the target, we begin by studying a
toy model of multi-modality.
Specifically, we take a parameter
$m>0$, and consider

$$ $\nu:=\mathcal{N}(0,1),\quad\quad\pi:=\frac{1}{2}\mathcal{N}(0,1)+\frac{1}{2} \mathcal{N}(m,1).$ (16) $$

It can be checked that $\pi$,
as well as some of the intermediate
distributions in the geometric tempering,
have log-Sobolev constant exponential in
the mode separation $m$. However, as we mentioned above, it remains
possible a priori that the geometric tempering
avoids this exponentially poor conditioning by following non-worst
case distributions.
The following result shows that this is not the
case, and indeed that the
total time spent on Langevin dynamics
must be exponential in $m$ to ensure convergence.

###### Theorem 8

Suppose $\nu,\pi$ are as
in Eq. 16 for $m\geq 11$.
Then

$$ $\mathrm{TV}(p^{K}_{T_{K}},\pi)\geq\frac{1}{20}-16\cdot e^{-m^{2}/64}\cdot\sum_ {k=1}^{K}T_{k}.$ $$

The proof of Theorem 8
can be found in Appendix D.2.
Several remarks are in order.
First, we emphasize that this result has no dependence whatsoever
on the tempering schedule.
Second, the same result of course also holds
with $\sqrt{\frac{1}{2}\mathop{\mathrm{KL}}\nolimits(\rho_{T},\mu_{k})},\sqrt{\frac{
1}{2}\chi^{2}(\rho_{T},\mu_{k})}$
on the left-hand side.
And finally, we remark that other
works have studied related tempering algorithms
with a uniform, rather than Gaussian, proposal, and shown
that in this case tempered dynamics
can successfully sample from
mixtures of Gaussians, so long as
each mixture component has the same variance [, ].
Theorem 8
shows that, in contrast, tempered Langevin dynamics with
Gaussian proposal can fail for mixtures of Gaussians with
identical variance, and
therefore additionally suggests an unfavorable property of Gaussian proposals as compared with uniform.

###### Theorem 8

#### Well-conditioned target.

The previous result
establishes a simple case where tempering is a natural
approach, yet the geometric tempering suffers from
exponentially poor performance.
Since the target distribution in that
case has poor functional inequalities,
a simpler sanity check for the geometric
tempering is to establish its convergence when the target
is actually well-conditioned.
We now analyze an example similar to that of Theorem 4,
where the target has decent log-Sobolev inequalities,
and show that, nonetheless, the geometric tempering suffers from exponentially poor
convergence, at least until the end of the tempering
scheme. For some $m>0$, put

$$ $\nu:=\mathcal{N}(0,1),\quad\quad\pi:=\frac{1}{2}\mathcal{N}(m,1)+\frac{1}{2}u_ {m},$ (17) $$

where, as in section 4.1,
$u_{m}$ is the probability distribution with density proportional
to $e^{-\frac{1}{2}d^{2}(x,I_{m})}$ for $I_{m}=[-m,2m]$.
Similar to Theorem 4,
although $\pi$ has a reasonable log-Sobolev
constant, the geometric tempering
is partially bimodal.
The next result shows that
the geometric tempering suffers from exponentially
slow convergence, at least until the tempering is
almost at $1$.

###### Theorem 9

Suppose $\nu,\pi$ are as in Eq. 17
for $m\geq 4$. Then $C_{LS}(\pi)\leq 324m^{3}$,
yet for all $k\in[K]$

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\frac{1}{5}-\delta_{k}-10m\cdot\sqrt{\delta_ {k}}\cdot\sum_{i=1}^{k}T_{i},$ $$

for
$\delta_{k}:=6m^{3}e^{-(1-\lambda_{k})m^{2}/10}.$

The proof of Theorem 9
can be found in Appendix D.3.
This result demonstrates
a simple case where geometric tempering suffers
from exponentially slower convergence
than Langevin dynamics,
and to the best of our knowledge is the first result
of this kind for the geometric tempering in the literature.
As for Theorem 8,
the statement holds
with $\sqrt{\frac{1}{2}\mathop{\mathrm{KL}}\nolimits(\rho_{T},\mu_{k})},\sqrt{\frac{
1}{2}\chi^{2}(\rho_{T},\mu_{k})}$
on the left-hand side.
We finally remark that Theorems 8
and 9 are both
consequences of a more general TV lower
bound, Theorem 20
in Appendix D.1, which may
be of further interest.

###### Theorem 9

## 6 Conclusion

We provided the first convergence analysis of tempered
Langevin dynamics, Eq. 9,
in the literature, both for
continuous (Theorem 1), and discrete (Theorem 3), time. Our bounds are naturally
driven by the log-Sobolev constants of the geometric tempering path,
and we identified in Theorem 4 a surprising degeneracy of the geometric
tempering where it can make these constants exponentially
worse than that of the target.
Restricting to the strongly log-concave setting,
we rigorously established the optimal tempering
schedule for our upper bounds in Proposition 6, and identified a regime
where it is strictly distinct from vanilla Langevin.
Finally, we developed rigorous lower bounds
proving exponentially slow convergence
for a bimodal target
in Theorem 8, and
even demonstrated a novel failure
of the geometric tempering
for
a uni-modal target in Theorem 9, where it has exponentially worse
performance than vanilla Langevin.
Interesting questions for future work include developing
a more complete understanding of the log-Sobolev constants
along the geometric tempering,
particularly for the uniform proposal,
as well as identifying alternative paths for Langevin
which have more favorable properties.
In this connection, we mention some recent works
which modify the geometric path so that mode weights are kept constant along the path [, ]; it would be interesting to extend our
analysis to these algorithms.

## Appendix

The paper and appendix are organized as follows.

## Appendix A Convergence of continuous-time tempered Langevin dynamics

In this section, we give
the proof of our continuous-time
upper bound, Theorem 1.
In Appendix A.1
we discuss the well-posedness of the continuous time
dynamics. The proof
of Theorem 1
is then given in Appendix A.2.
In the next section, Appendix A.3,
we derive from Theorem 1
guarantees for convergence to a given precision.
In Appendix A.4
we give the proofs of the lemmas we used in the proof of Theorem 1.

### A.1 Well-posedness of continuous tempered Langevin dynamics

Notice that in Equation 9, the drift $b(t,x)=\nabla\log\mu_{t}(x)$ is time-dependent and the diffusion coefficient is constant.
Still, existence and uniqueness of solutions can be guaranteed under mild assumptions. For instance, if $\nabla\log\nu$ and $\nabla\log\pi$ are $L_{\nu}$ and $L_{\pi}$-Lipschitz respectively, the drift is also Lipschitz with bounded constant $L\leq\max(L_{\nu},L_{\pi})$
(since the dynamic $\lambda_{t}$ is bounded between 0 and 1), hence satisfy the usual linear
growth condition in the second argument. In this case, there exists a unique, continuous strong solution $(X_{t})_{t\geq 0}$ adapted to the filtration generated by the Brownian motion which satisfies Equation 9 [, ].
Strong uniqueness also means that if two processes satisfy this equation with the same initial conditions, their trajectories are almost surely indistinguishable.
The law $(p_{t})_{t\geq 0}$ of Equation 9 satisfies a Fokker-Planck equation [] that can be written

$$ $\displaystyle\frac{\partial p_{t}}{\partial t}=\divergence(p_{t}\nabla\log\Big (\frac{p_{t}}{\mu_{t}}\Big{missing}))\enspace.$ (18) $$

Generally, proving the existence and uniqueness of solutions for FPEs is more difficult than for SDEs, but
one can also get under mild assumptions existence and uniqueness for solutions of Equation 18, under the same Lipschitzness assumptions on the score of proposal and target distributions, and using that the tempering dynamics are bounded in $[0,1]$
[, Proposition 2].

### A.2 Proof of Theorem 1

In this section, we will prove Theorem 1
on the convergence rate of tempered Langevin dynamics.
The proof is in two steps: first, we compute how the process $p_{t}$ tracks the moving target $\mu_{t}$, then we compute how well the moving target $\mu_{t}$ tracks the final target $\pi$.

#### Step 1: contraction of KL ( p t , μ t ) KL subscript 𝑝 𝑡 subscript 𝜇 𝑡 \mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t}) roman_KL ( italic_p start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ) over time.

Using the chain rule, we have

$$ $\displaystyle\frac{d}{dt}\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})$ $\displaystyle=\int\log\Big(\frac{p_{t}}{\mu_{t}}\Big{missing})\frac{\partial p _{t}}{\partial t}+\int\frac{-p_{t}}{\mu_{t}}\frac{\partial\mu_{t}}{\partial t} :=a+b.$ $$

The first term $a$ involves the Langevin dynamics given by the Fokker-Planck equation Eq. 18. Hence, using
integration by parts and the inverse log-Sobolev
constants defined in Eq. 8, we
obtain:

$$ $\displaystyle a=\int\log\Big(\frac{p_{t}}{\mu_{t}}\Big{missing})\divergence \Big(p_{t}\nabla\log\Big(\frac{p_{t}}{\mu_{t}}\Big{missing})\Big{missing})$ $\displaystyle=-\int p_{t}\Big{\|}\nabla\log\Big(\frac{p_{t}}{\mu_{t}}\Big{ missing})\Big{\|}^{2}$ $\displaystyle=-\mathop{\mathrm{FD}}\nolimits(p_{t},\mu_{t})\leq-2\alpha_{t} \mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t}).$ (19) $$

The second term $b$ is specific to the tempering scheme: it involves the tempering dynamics $\dot{\mu}_{t}$, which is zero when there is no tempering and are here determined by the tempering rule $\mu_{t}=c_{\lambda_{t}}\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}$, where $c_{\lambda_{t}}=1/\int\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}$ is a normalizing factor, that we will denote $c_{t}$ in this proof to alleviate notation. We can compute the (log) tempering dynamics

$$ $\displaystyle\frac{\partial\log\mu_{t}}{\partial t}$ $\displaystyle=\frac{\partial}{\partial t}\Big{(}\lambda_{t}\log\frac{\pi}{\nu} +\log\nu-\log\int\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}\Big{)}=\dot{\lambda}_{t} \log\frac{\pi}{\nu}-\frac{\frac{\partial}{\partial t}\int\nu^{1-\lambda_{t}} \pi^{\lambda_{t}}}{\int\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}}$ $\displaystyle=\dot{\lambda}_{t}\log\frac{\pi}{\nu}-\dot{\lambda}_{t}\int\log \frac{\pi}{\nu}\frac{\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}}{\int\nu^{1-\lambda_ {t}}\pi^{\lambda_{t}}}=\dot{\lambda}_{t}\Big{(}\log\frac{\pi}{\nu}-\mathbb{E}_ {\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\Big{)}$ $$

so that the second term becomes

$$ $\displaystyle b$ $\displaystyle=\int p_{t}\frac{-\partial\log\mu_{t}}{\partial t}=\dot{\lambda}_ {t}\Big{(}\mathbb{E}_{\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_ {t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\Big{)}\enspace.$ $$

To control this term we prove the following Lemma in Appendix A.4.

###### Lemma 10 (Discrepancy between the laws of the sampling process and tempering path)

We have

$$ $\displaystyle\mathbb{E}_{\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_ {p_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\leq 2(L_{\pi}+L_{\nu})\Big{(}\frac{2( d+b_{\nu}+b_{\pi})}{a_{\nu}\land a_{\pi}}+\mathbb{E}_{p_{0}}[\|x\|^{2}]\Big{)}.$ $$

Let $A$ be the right-hand side in Lemma 10, namely

$$ $\displaystyle A:=2(L_{\pi}+L_{\nu})\Big{(}\frac{2(d+b_{\nu}+b_{\pi})}{a_{\nu} \land a_{\pi}}+\mathbb{E}_{p_{0}}[\|x\|^{2}]\Big{)}.$ (20) $$

Then we obtain

$$ $\displaystyle b\leq A\dot{\lambda}_{t}.$ (21) $$

Combining Eq. 19
and Eq. 21 we obtain

$$ $\displaystyle\frac{d}{dt}\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})$ $\displaystyle\leq-2\alpha_{t}\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})+A \dot{\lambda}_{t}.$ $$

To conclude this step, we apply
Grönwall’s lemma [, Lemma 1.1]
to yield

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},$ $\displaystyle\mu_{t})\leq\exp(\int_{0}^{t}-2\alpha_{s}ds)\mathop{\mathrm{KL}} \nolimits(p_{0},\mu_{0})+A\int_{0}^{t}\dot{\lambda}_{s}\exp(\int_{s}^{t}-2 \alpha_{v}dv)ds.$ $$

###### Lemma 10 (Discrepancy between the laws of the sampling process and tempering path)

#### Step 2: compare KL ( p t , μ t ) KL subscript 𝑝 𝑡 subscript 𝜇 𝑡 \mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t}) roman_KL ( italic_p start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ) and KL ( p t , π ) KL subscript 𝑝 𝑡 𝜋 \mathop{\mathrm{KL}}\nolimits(p_{t},\pi) roman_KL ( italic_p start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_π ) .

This measures how well the moving target $\mu_{t}$ tracks the final target $\pi$. We write

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})+\mathop{\mathrm{KL} }\nolimits(p_{t},\pi)-\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})+\mathbb{E}_{p_{t}} \Big{[}\log\frac{\mu_{t}}{\pi}\Big{]}$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{t},\mu_{t})+(1-\lambda_{t}) \mathbb{E}_{p_{t}}\Big{[}\log(\frac{\nu}{\pi})\Big{]}+\log c_{t}.$ $$

We make the following observation on the log normalizing constants,
proved in Appendix A.4.

###### Lemma 11 (Bounding the normalizing constant of the law of the tempering path)

We have

$$ $\displaystyle 0\leq\log c_{t}\leq\min\Big{(}\lambda_{t}\mathop{\mathrm{KL}} \nolimits(\nu,\pi),(1-\lambda_{t})\mathop{\mathrm{KL}}\nolimits(\pi,\nu)\Big{) }\enspace.$ $$

Using Lemma 11
to control the normalizing constant $c_{t}$, we obtain

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)\leq\mathop{\mathrm{KL}} \nolimits(p_{t},\mu_{t})\ +(1-\lambda_{t})\Big{(}\mathbb{E}_{p_{t}}\Big{[}\log (\frac{\nu}{\pi})\Big{]}+\mathbb{E}_{\pi}\Big{[}\log(\frac{\pi}{\nu})\Big{]} \Big{)}.$ $$

Finally, we control this last term using
similar estimates as in Lemma 10;
the proof is again deferred to Appendix A.4.

###### Lemma 12 (Discrepancy between the laws of the sampling process and target)

We have

$$ $\displaystyle\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{ t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\leq 2(L_{\pi}+L_{\nu})\Big{(}\frac{2(d+b_ {\nu}+b_{\pi})}{a_{\nu}\land a_{\pi}}+\mathbb{E}_{p_{0}}[\|x\|^{2}]\Big{)}.$ $$

Applying this result we obtain

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)\leq\mathop{\mathrm{KL}} \nolimits(p_{t},\mu_{t})+(1-\lambda_{t})A.$ $$

###### Lemma 11 (Bounding the normalizing constant of the
law of the tempering path)

###### Lemma 12 (Discrepancy between the laws of the sampling process and target)

#### Step 3: putting it together.

We
find

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)$ $\displaystyle\leq(u_{1})+(u_{2})+(u_{3})$ (22) $\displaystyle(u_{1})$ $\displaystyle=\exp(-2\int_{0}^{t}\alpha_{s}ds)\mathop{\mathrm{KL}}\nolimits(p_ {0},\mu_{0})$ $\displaystyle(u_{2})$ $\displaystyle=(1-\lambda_{t})A$ $\displaystyle(u_{3})$ $\displaystyle=A\int_{0}^{t}\dot{\lambda}_{s}\exp(-2\int_{s}^{t}\alpha_{v}dv)ds\enspace.$ $$

### A.3 Continuous-time convergence in precision form

As in Vempala and Wibisono, [], we can derive from
Theorem 1
sufficient conditions for convergence to precision ${\epsilon}$ by setting each of the three terms in the upper-bound to be less than
$\epsilon/3$.

###### Corollary 13

Suppose the assumptions of Theorem 1
hold.
To achieve convergence with precision $\epsilon>0$ such that $\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)<\epsilon$, sufficient conditions on the time $t$ and schedule $\lambda(\cdot)$ are

$$ $\displaystyle t$ $\displaystyle>\max\Big{(}\frac{1}{2\alpha_{\min}}\log\Big(\frac{3\mathop{ \mathrm{KL}}\nolimits(p_{0},\mu_{0})}{\epsilon}\Big{missing}),\frac{1}{\alpha_ {\min}}\log\Big(\frac{6A}{\epsilon}\Big{missing})\Big{)}$ (23) $\displaystyle\lambda_{t}$ $\displaystyle>1-\frac{\epsilon}{3A}$ (24) $\displaystyle\lambda_{t}$ $\displaystyle<\frac{\epsilon}{6}+\lambda_{t/2},$ (25) $$

where $\alpha_{\min}=\min_{s>0}\alpha_{s}$ is the smallest log-Sobolev constant among the path of tempered distributions.

###### Proof of Corollary 17 .

We upper-bound the first term by $(u_{1})\leq e^{-2t\alpha_{\min}}\mathop{\mathrm{KL}}\nolimits(p_{0},\mu_{0})$ so that a sufficient condition for $(u_{1})<\epsilon/3$ is $t>\frac{1}{2\alpha_{\min}}\log\Big(\frac{3\mathop{\mathrm{KL}}\nolimits(p_{0},
\mu_{0})}{\epsilon}\Big{missing})$.

A sufficient condition $(u_{2})<\epsilon/3$ is $\lambda_{t}\in]1-\frac{\epsilon}{3A},1]$. If $\lambda$ is bijective, this yields $t>\lambda^{-1}\Big{(}1-\frac{\epsilon}{3A}\Big{)}$.

Finally, we upper-bound the third term:

$$ $\displaystyle(u_{3})$ $\displaystyle=A\int_{0}^{t}\dot{\lambda}_{s}\exp(-2\int_{s}^{t}\alpha_{v}dv)ds$ (26) $\displaystyle=A\Big{(}\int_{0}^{t/2}\dot{\lambda}_{s}\exp(-2\int_{s}^{t}\alpha _{v}dv)ds+\int_{t/2}^{t}\dot{\lambda}_{s}\exp(-2\int_{s}^{t}\alpha_{v}dv)ds \Big{)}$ (27) $\displaystyle\leq A\Big{(}\exp(-2\int_{t/2}^{t}\alpha_{v}dv)\int_{0}^{t/2}\dot {\lambda}_{s}+\int_{t/2}^{t}\dot{\lambda}_{s}ds\Big{)}$ (28) $\displaystyle\leq A\big{(}\exp(-t\alpha_{\min})(\lambda_{t/2}-\lambda_{0})+( \lambda_{t}-\lambda_{t/2})\big{)}$ (29) $\displaystyle\leq A\big{(}\exp(-t\alpha_{\min})+(\lambda_{t}-\lambda_{t/2}) \big{)}$ (30) $$

so that sufficient conditions for $(u_{3})<\frac{\epsilon}{3}$ can be obtained by setting each of the two terms smaller than $\frac{\epsilon}{6}$, yielding $t>\frac{1}{\alpha_{\min}}\log\frac{6A}{\epsilon}$ and $\lambda_{t}-\lambda_{t/2}<\epsilon/6$.
∎

###### Corollary 13

###### Proof of Corollary 17 .

### A.4 Proofs of technical lemmas from Appendix A.2

In this section, we give the deferred
proofs from Appendix A.2.
We first state and prove two observations that will be useful,
before turning to the deferred proofs.
The following proposition translates the dissipativity assumptions into a condition on the tails of the proposal and target.

###### Proposition 14 (Tails of the proposal and target)

For all $x\in\mathbb{R}^{d}$, we have

$$ $\displaystyle V_{\nu}(x)-\inf_{y\in\mathbb{R}^{d}}V_{\nu}(y)\leq 2L_{\nu}\Big{ (}\|x\|^{2}+\frac{b_{\nu}}{a_{\nu}}\Big{)},\quad\quad V_{\pi}(x)-\inf_{y\in \mathbb{R}^{d}}V_{\pi}(y)\leq 2L_{\pi}\Big{(}\|x\|^{2}+\frac{b_{\pi}}{a_{\pi}} \Big{)}.$ $$

###### Proof of Proposition 14 .

Observe that because

$$ $\langle\nabla V_{\nu}(x),x\rangle\geq a_{\nu}\|x\|^{2}-b_{\nu},$ $$

the function $V_{\nu}$ must be minimized by some point $x_{0}\in B(0,\sqrt{\frac{b_{\nu}}{a_{\nu}}})$.
Therefore, for all $x\in\mathbb{R}^{d}$,

$$ $V_{\nu}(x)-\inf_{y\in\mathbb{R}^{d}}V_{\nu}(y)=V_{\nu}(x)-V_{\nu}(x_{0})\leq L _{\nu}\|x-x_{0}\|^{2}\leq 2L_{\nu}\Big{(}\|x\|^{2}+\frac{b_{\nu}}{a_{\nu}}\Big {)}.$ $$

The proof for $V_{\pi}$ is identical, so we omit it.
∎

The next observation is our main quantitative use of the
dissipativity assumption, and crucial for our control
on the terms arising from the tempering dynamics in the continuous time
convergence proof.

###### Lemma 15 (Bounded second moment along the dynamics)

For all $t\geq 0$,

$$ $\displaystyle\mathbb{E}_{p_{t}}[\|x\|^{2}]\leq\max\Big{(}\mathbb{E}_{p_{0}}[\| x\|^{2}],\frac{d+b_{\nu}+b_{\pi}}{a_{\nu}\land a_{\pi}}\Big{)}.$ $$

###### Proof of Lemma 15 .

Using the Fokker-Planck equation Eq. 18
and integration by parts several times, we find

$$ $\displaystyle\partial_{t}\mathbb{E}_{p_{t}}[\|x\|^{2}]$ $\displaystyle=\int\|x\|^{2}\nabla\cdot\big{(}p_{t}\nabla\log\frac{p_{t}}{\mu_{ t}}\big{)}$ $\displaystyle=-2\int\langle x,\nabla\log p_{t}-\nabla\log\mu_{t}\rangle p_{t}$ $\displaystyle=2d-2\int\langle x,(1-\lambda_{t})\nabla V_{\nu}+\lambda_{t} \nabla V_{\pi}\rangle p_{t}\enspace.$ $$

Applying the dissipativity assumption, we obtain

$$ $\displaystyle\partial_{t}\mathbb{E}_{p_{t}}[\|x\|^{2}]$ $\displaystyle\leq 2(d+(1-\lambda_{t})b_{\nu}+\lambda_{t}b_{\pi})-2((1-\lambda_ {t})a_{\nu}+\lambda_{t}a_{\pi})\mathbb{E}_{p_{t}}[\|x\|^{2}]$ $\displaystyle\leq 2(d+b_{\nu}+b_{\pi})-2(a_{\nu}\land a_{\pi})\mathbb{E}_{p_{t }}[\|x\|^{2}].$ $$

Therefore, as soon as
$\mathbb{E}_{p_{t}}[\|x\|^{2}]$ exceeds the
level $(d+b_{\nu}+b_{\pi})/(a_{\nu}\land a_{\pi})$,
it must start decreasing. The result follows.
∎

We now give the proofs of the Lemmas from Appendix A.2.

###### Proof of Lemma 10 .

Use Proposition 14
to obtain

$$ $\displaystyle\mathbb{E}_{\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_ {p_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}$ $\displaystyle=\mathbb{E}_{\mu_{t}}\big{[}V_{\nu}-V_{\pi}\big{]}+\mathbb{E}_{p_ {t}}\big{[}V_{\pi}-V_{\nu}\big{]}$ $\displaystyle\leq\mathbb{E}_{\mu_{t}}[V_{\nu}-\inf_{y\in\mathbb{R}^{d}}V_{\nu} (y)]+\mathbb{E}_{p_{t}}[V_{\pi}-\inf_{y\in\mathbb{R}^{d}}V_{\pi}(y)]$ $\displaystyle\leq 2L_{\nu}\mathbb{E}_{\mu_{t}}[\|x\|^{2}]+2L_{\pi}\mathbb{E}_{ p_{t}}[\|x\|^{2}]+2L_{\nu}\frac{b_{\nu}}{a_{\nu}}+2L_{\pi}\frac{b_{\pi}}{a_{ \pi}}.$ $$

Let $M$ be the quantity appearing on the right-hand side of Lemma 15.
Then we obtain

$$ $\displaystyle\mathbb{E}_{\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_ {p_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\leq 2L_{\nu}\mathbb{E}_{\mu_{t}}[\|x \|^{2}]+2L_{\pi}\Big{(}M+\frac{b_{\pi}}{a_{\pi}}\Big{)}+2L_{\nu}\frac{b_{\nu}} {a_{\nu}}.$ $$

To handle $\mathbb{E}_{\mu_{t}}[\|x\|^{2}]$, we apply the dissipativity assumption to yield

$$ $\displaystyle\mathbb{E}_{\mu_{t}}[\|x\|^{2}]\leq\frac{1}{(1-\lambda_{t})a_{\nu }+\lambda_{t}a_{\pi}}\mathbb{E}_{\mu_{t}}\Big{[}\langle(1-\lambda_{t})\nabla V _{\nu}+\lambda_{t}V_{\pi},x\rangle+(1-\lambda_{t})b_{\nu}+\lambda_{t}b_{\pi} \Big{]}.$ $$

Integration by parts gives

$$ $\displaystyle\mathbb{E}_{\mu_{t}}[\|x\|^{2}]\leq\frac{d+(1-\lambda_{t})b_{\nu} +\lambda_{t}b_{\pi}}{(1-\lambda_{t})a_{\nu}+\lambda_{t}a_{\pi}}\leq\frac{d+b_{ \nu}+b_{\pi}}{a_{\nu}\land a_{\pi}}.$ $$

Hence,

$$ $\displaystyle\mathbb{E}_{\mu_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_ {p_{t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\leq$ $\displaystyle 2L_{\pi}\Big{(}\frac{b_{\pi}}{a_{\pi}}+\max\Big{(}\mathbb{E}_{p_ {0}}[\|x\|^{2}],\frac{d+b_{\nu}+b_{\pi}}{a_{\nu}\land a_{\pi}}\Big{)}\Big{)}$ $\displaystyle+2L_{\nu}\Big{(}\frac{b_{\nu}}{a_{\nu}}+\frac{d+b_{\nu}+b_{\pi}}{ a_{\nu}\land a_{\pi}}\Big{)}.$ $$

Using $\max(x,y)\leq x+y$ when $x,y\geq 0$
and

$$ $\frac{b_{\nu}}{a_{\nu}},\,\,\frac{b_{\pi}}{a_{\pi}}\leq\frac{d+b_{\nu}+b_{\pi} }{a_{\nu}\land a_{\pi}},$ $$

we conclude.
∎

###### Proof of Lemma 11 .

We have

$$ $\displaystyle\log c_{t}$ $\displaystyle=\log\Big(\frac{1}{\int\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}}\Big{ missing})=-\log\int\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}$ $$

The lower bound is immediate from Hölder’s inequality. For the upper bound, write

$$ $\displaystyle\log c_{t}$ $\displaystyle=-\log\mathbb{E}_{\nu}\Big{[}\Big{(}\frac{\pi}{\nu}\Big{)}^{ \lambda_{t}}\Big{]}\leq\lambda_{t}\mathbb{E}_{\nu}\Big{[}\log\frac{\nu}{\pi} \Big{]}=\lambda_{t}\mathop{\mathrm{KL}}\nolimits(\nu,\pi)$ $$

using Jensen’s inequality. Similarly, we can write

$$ $\displaystyle\log c_{t}$ $\displaystyle=-\log\mathbb{E}_{\pi}\Big{[}\Big{(}\frac{\nu}{\pi}\Big{)}^{1- \lambda_{t}}\Big{]}\leq(1-\lambda_{t})\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{ \nu}\Big{]}=(1-\lambda_{t})\mathop{\mathrm{KL}}\nolimits(\pi,\nu)\enspace,$ $$

and therefore conclude that

$$ $\displaystyle\log c_{t}$ $\displaystyle\leq\min\Big{(}\lambda_{t}\mathop{\mathrm{KL}}\nolimits(\nu,\pi), (1-\lambda_{t})\mathop{\mathrm{KL}}\nolimits(\pi,\nu)\Big{)}\enspace.\qed$ $$

###### Proof of Lemma 12 .

Denoting by $V_{\pi}^{*}$ (resp. $V_{\nu}^{*}$) the infimum of $V_{\pi}$ (resp. $V_{\nu}$), we have

$$ $\displaystyle\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{ t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}=\int p_{t}(V_{\pi}-V_{\pi}^{*}-(V_{\nu}-V _{\nu}^{*}))+\int d\pi(V_{\nu}-V_{\nu}^{*})-(V_{\pi}-V_{\pi}^{*}).$ $$

Using Proposition 14, we obtain the upper-bound

$$ $\displaystyle\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{ t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\leq 2L_{\pi}\Big{(}\mathbb{E}_{p_{t}}[\|x \|^{2}]+\frac{b_{\pi}}{a_{\pi}}\Big{)}+2L_{\nu}\Big{(}\mathbb{E}_{\pi}[\|x\|^{ 2}]+\frac{b_{\nu}}{a_{\nu}}\Big{)}.$ $$

Let $M$ be the quantity appearing on the right-hand side of Lemma 15.
Then

$$ $\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{t}}\Big{[} \log\frac{\pi}{\nu}\Big{]}\leq 2L_{\pi}\Big{(}M+\frac{b_{\pi}}{a_{\pi}}\Big{)} +2L_{\nu}\Big{(}\mathbb{E}_{\pi}[\|x\|^{2}]+\frac{b_{\nu}}{a_{\nu}}\Big{)}.$ $$

On the other hand, a direct application of the dissipativity
condition Assumption 2
implies

$$ $\mathbb{E}_{\pi}[\|x\|^{2}]\leq\frac{1}{a_{\pi}}\mathbb{E}_{\pi}[\langle x, \nabla V_{\pi}(x)\rangle+b_{\pi}]=\frac{d+b_{\pi}}{a_{\pi}}\leq\frac{d+b_{\pi} +b_{\nu}}{a_{\nu}\land a_{\pi}}.$ $$

Therefore

$$ $\displaystyle\mathbb{E}_{\pi}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{ t}}\Big{[}\log\frac{\pi}{\nu}\Big{]}$ $\displaystyle\leq 2L_{\pi}\Big{(}\max\Big{(}\mathbb{E}_{p_{0}}[\|x\|^{2}], \frac{d+b_{\nu}+b_{\pi}}{a_{\nu}\land a_{\pi}}\Big{)}+\frac{b_{\pi}}{a_{\pi}}$ $\displaystyle+2L_{\nu}\frac{d+b_{\pi}+b_{\nu}}{a_{\nu}\land a_{\pi}}+2L_{\nu} \frac{b_{\nu}}{a_{\nu}}\Big{)}.$ $$

Again, bounding $\max(x,y)\leq x+y$ for $x,y\geq 0$
and using

$$ $\frac{b_{\nu}}{a_{\nu}},\,\,\frac{b_{\pi}}{a_{\pi}}\leq\frac{d+b_{\nu}+b_{\pi} }{a_{\nu}\land a_{\pi}},$ $$

we conclude.
∎

###### Proposition 14 (Tails of the proposal and target)

###### Proof of Proposition 14 .

###### Lemma 15 (Bounded second moment along the dynamics)

###### Proof of Lemma 15 .

###### Proof of Lemma 10 .

###### Proof of Lemma 11 .

###### Proof of Lemma 12 .

## Appendix B Convergence of discrete-time tempered Langevin dynamics

In this section we give proof of our discrete-time upper
bound, Theorem 3.
In Appendix B.1
we outline the proof of Theorem 3.
In Appendix B.2,
we derive from Theorem 3
sufficient conditions to precision $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)<{\epsilon}$.
And in Appendix B.3
we give the deferred proof from Appendix B.1.

### B.1 Proof of Theorem 3

We next prove Theorem 3. Broadly speaking, the proof is in two steps: first, we compute how the process $p_{k}$ tracks the moving target $\mu_{k}$, then we compute how well the moving target $\mu_{k}$ tracks the final target $\pi$.

#### Step 1: contraction of KL ( p k , μ k ) KL subscript 𝑝 𝑘 subscript 𝜇 𝑘 \mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k}) roman_KL ( italic_p start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT , italic_μ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) .

Using Vempala and Wibisono, [, Lemma 3], under Assumptions 1
and 2 and $h_{k}\leq\frac{\alpha_{k}}{4L_{k}^{2}}$, we obtain

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})\leq\mathop{\mathrm{ KL}}\nolimits(p_{k-1},\mu_{k})e^{-\alpha_{k}h_{k}}+6h_{k}^{2}dL_{k}^{2}\enspace.$ (31) $$

Next, we can compute the (log) tempering dynamics of $\mu_{k}$

$$ $\displaystyle\log\mu_{k-1}-\log\mu_{k}$ $\displaystyle=(\lambda_{k}-\lambda_{k-1})\log\frac{\nu}{\pi}-\log\frac{\int\nu ^{1-\lambda_{k-1}}\pi^{\lambda_{k-1}}}{\int\nu^{1-\lambda_{k}}\pi^{\lambda_{k}}}$ $\displaystyle=(\lambda_{k}-\lambda_{k-1})\log\frac{\nu}{\pi}-\log\int\frac{\nu ^{1-\lambda_{k-1}}\pi^{\lambda_{k-1}}}{\nu^{1-\lambda_{k}}\pi^{\lambda_{k}}} \frac{\nu^{1-\lambda_{k}}\pi^{\lambda_{k}}}{\int\nu^{1-\lambda_{k}}\pi^{ \lambda_{k}}}$ $\displaystyle=(\lambda_{k}-\lambda_{k-1})\log\frac{\nu}{\pi}-\log\mathbb{E}_{ \mu_{k}}\Big{[}\Big{(}\frac{\nu}{\pi}\Big{)}^{\lambda_{k}-\lambda_{k-1}}\Big{]}$ $\displaystyle\leq(\lambda_{k}-\lambda_{k-1})\Big{(}\log\frac{\nu}{\pi}-\mathbb {E}_{\mu_{k}}\Big{[}\log\frac{\nu}{\pi}\Big{]}\Big{)},$ $$

where we used Jensen’s inequality at the last step.
Thus

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{k-1},\mu_{k})$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{k-1},\mu_{k-1})+\mathop{\mathrm {KL}}\nolimits(p_{k-1},\mu_{k})-\mathop{\mathrm{KL}}\nolimits(p_{k-1},\mu_{k-1})$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{k-1},\mu_{k-1})+\int p_{k-1} \log\frac{\mu_{k-1}}{\mu_{k}}$ $\displaystyle\leq\mathop{\mathrm{KL}}\nolimits(p_{k-1},\mu_{k-1})+(\lambda_{k} -\lambda_{k-1})\Big{(}\mathbb{E}_{\mu_{k}}\Big{[}\log\frac{\pi}{\nu}\Big{]}- \mathbb{E}_{p_{k-1}}\Big{[}\log\frac{\pi}{\nu}\Big{]}\Big{)}.$ $$

Using Proposition 14
we can upper bound the difference of expectations via

$$ $\mathbb{E}_{\mu_{k}}\Big{[}\log\frac{\pi}{\nu}\Big{]}-\mathbb{E}_{p_{k-1}}\Big {[}\log\frac{\pi}{\nu}\Big{]}\leq 2L_{\nu}\Big{(}\mathbb{E}_{\mu_{k}}[\|x\|^{2 }]+\frac{b_{\nu}}{a_{\nu}}\Big{)}+2L_{\pi}\Big{(}\mathbb{E}_{p_{k-1}}[\|x\|^{2 }]+\frac{b_{\pi}}{a_{\pi}}\Big{)}$ $$

The next Lemma, proved in Appendix B.3 controls
the second moment of $p_{k}$.

###### Lemma 16 (Bounded second moment along the dynamics)

Suppose $h_{k}\leq\min\big{(}1,\frac{a_{\pi}\land a_{\nu}}{2(L_{\pi}+L_{\nu})^{2}}\big{)}$.
Then

$$ $\displaystyle\mathbb{E}_{p_{k}}[\|x\|^{2}]\leq\max\Big{(}\mathbb{E}_{p_{0}}[\| x\|^{2}],\frac{2(3(b_{\pi}+b_{\nu})/2+d)}{a_{\pi}\land a_{\mu}\land 1}\Big{)}\enspace.$ $$

For the second moment of $\mu_{k}$ we use the following
bound from the proof of Lemma 10

$$ $\mathbb{E}_{\mu_{k}}[\|x\|^{2}]\leq\frac{d+b_{\nu}+b_{\pi}}{a_{\nu}\land a_{ \pi}}.$ $$

To combine these bounds, let us define

$$ $\displaystyle A^{\prime}\coloneqq 2(L_{\pi}+L_{\nu})\Big{\{}\max\Big{(}\mathbb {E}_{p_{0}}[\|x\|^{2}],\frac{2(3(b_{\pi}+b_{\nu})/2+d)}{a_{\pi}\land a_{\nu} \land 1}\Big{)}+\frac{3(d+b_{\nu}+b_{\pi})}{a_{\pi}\land a_{\nu}}\Big{\}}.$ (32) $$

Plugging into Eq. 31, we obtain

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})\leq\mathop{\mathrm{ KL}}\nolimits(p_{k-1},\mu_{k-1})e^{-\alpha_{k}h_{k}}+(\lambda_{k}-\lambda_{k-1 })A^{\prime}e^{-\alpha_{k}h_{k}}+6h_{k}^{2}dL_{k}^{2}.$ $$

Now put $\psi_{i}^{k}:=\sum_{j=i}^{k}\alpha_{j}h_{j}$.
Unrolling the recursion, we obtain

$$ $\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})\leq e^{-\psi_{1}^{k}}\mathop{ \mathrm{KL}}\nolimits(p_{0},\mu_{0})+\sum_{i=1}^{k}\Big{(}A^{\prime}(\lambda_{ i}-\lambda_{i-1})e^{-\alpha_{i}h_{i}}+6h_{i}^{2}dL_{i}^{2}\Big{)}e^{-\psi_{i+1 }^{k}}.$ (33) $$

Step 2: compare $\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})$ and $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)$.
Here we use Lemma 11
to control the log-normalizing constants and
obtain

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})+\mathop{\mathrm{KL} }\nolimits(p_{k},\pi)-\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})+\mathbb{E}_{p_{k}} \Big{[}\log\frac{\mu_{k}}{\pi}\Big{]}$ $\displaystyle=\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})+(1-\lambda_{k}) \mathbb{E}_{p_{k}}\Big{[}\log\frac{\nu}{\pi}\Big{]}+\log c_{k}$ $\displaystyle\leq\mathop{\mathrm{KL}}\nolimits(p_{k},\mu_{k})+(1-\lambda_{k}) \big{(}\mathbb{E}_{p_{k}}\Big{[}\log\frac{\nu}{\pi}\Big{]}+\mathop{\mathrm{KL} }\nolimits(\pi,\nu)\big{)}.$ $$

To control the term in parentheses, we apply Proposition 14
to yield

$$ $\mathbb{E}_{p_{k}}\Big{[}\log\frac{\nu}{\pi}\Big{]}+\mathop{\mathrm{KL}} \nolimits(\pi,\nu)\leq 2L_{\pi}\Big{(}\mathbb{E}_{p_{k}}[\|x\|^{2}]+\frac{b_{ \pi}}{a_{\pi}}\Big{)}+2L_{\nu}\Big{(}\mathbb{E}_{\pi}[\|x\|^{2}]+\frac{b_{\nu} }{a_{\nu}}\Big{)}.$ $$

Using Lemma 15 and the following
bound from the proof of Lemma 12

$$ $\mathbb{E}_{\pi}[\|x\|^{2}]\leq\frac{d+b_{\pi}+b_{\nu}}{a_{\nu}\land a_{\pi}},$ $$

we find

$$ $\mathbb{E}_{p_{k}}\Big{[}\log\frac{\nu}{\pi}\Big{]}+\mathop{\mathrm{KL}} \nolimits(\pi,\nu)\leq A^{\prime},$ $$

for $A^{\prime}$ as in Eq. 32.

###### Lemma 16 (Bounded second moment along the dynamics)

#### Step 3: putting it together.

Combining the results of steps 1 and 2,
we can finally write

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)$ $\displaystyle\leq(v_{1})+(v_{2})+(v_{3})+(v_{4})$ (34) $\displaystyle(v_{1})$ $\displaystyle=\exp\Big(-\sum_{j=1}^{k}\alpha_{j}h_{j}\Big{missing})\mathop{ \mathrm{KL}}\nolimits(p_{0},\mu_{1}),$ $\displaystyle(v_{2})$ $\displaystyle=(1-\lambda_{k})A^{\prime},$ $\displaystyle(v_{3})$ $\displaystyle=A^{\prime}\sum_{i=1}^{k}(\lambda_{i}-\lambda_{i-1})\exp\Big(- \sum_{j=i}^{k}\alpha_{j}h_{j}\Big{missing}),$ $\displaystyle(v_{4})$ $\displaystyle=6\sum_{i=1}^{k}h_{k}^{2}dL_{k}^{2}\exp\Big(-\sum_{j=i+1}^{k} \alpha_{j}h_{j}\Big{missing})\enspace.$ $$

### B.2 Discrete-time convergence in precision form

###### Corollary 17

To achieve convergence with precision $\epsilon>0$ such that $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)<\epsilon$, sufficient conditions
are

$$ $\displaystyle h$ $\displaystyle<\min\Big{(}\frac{1}{4\alpha_{\min}},\frac{\alpha_{\min}}{96L_{ \max}^{2}d}\epsilon,\frac{\alpha_{\min}}{4(L_{\pi}+L_{\nu})^{2}},\frac{a_{\pi} \land a_{\nu}}{2(L_{\pi}+L_{\nu})^{2}},1\Big{)}$ (35) $\displaystyle k$ $\displaystyle>\max\Big{(}\frac{1}{h\alpha_{\min}}\log\Big(\frac{4\mathop{ \mathrm{KL}}\nolimits(p_{0},\mu_{1})}{\epsilon}\Big{missing}),\frac{2}{h\alpha _{\min}}\log\Big(\frac{8A^{\prime}}{\epsilon}\Big{missing})\Big{)}$ (36) $\displaystyle\lambda_{k}$ $\displaystyle>1-\frac{\epsilon}{4A^{\prime}}$ (37) $\displaystyle\lambda_{k}-\lambda_{\lfloor k/2\rfloor}$ $\displaystyle<\frac{\epsilon}{24A^{\prime}}$ (38) $$

where $\alpha_{\min}=\min_{s>0}\alpha_{s}$ and $L_{\max}=\max_{s>0}L_{s}$ denote the smallest (resp. largest) log-Sobolev (resp. smoothness) constant among the path of tempered distributions.

###### Proof.

Again, as in Vempala and Wibisono, [], we can derive sufficient conditions for convergence with a given precision $\mathop{\mathrm{KL}}\nolimits(p_{k},\pi)<\epsilon$ by setting each of the four terms in the upper-bound inferior to $\epsilon/4$.

First, we upper-bound the fourth term:

$$ $\displaystyle(v_{4})$ $\displaystyle\leq 6h^{2}dL_{\max}^{2}\sum_{i=1}^{k}e^{-(k-i)h\alpha_{\min}}=6h ^{2}dL_{\max}^{2}\frac{1-e^{-kh\alpha_{\min}}}{1-e^{-h\alpha_{\min}}}$ (39) $\displaystyle\leq 6h^{2}dL_{\max}^{2}\frac{1}{1-e^{-h\alpha_{\min}}}\leq 6h^{2 }dL_{\max}^{2}\frac{4}{3h\alpha_{\min}}=\frac{8hdL_{\max}^{2}}{\alpha_{\min}}$ (40) $$

where in the last inequality, similarly to Vempala and Wibisono, [], we use that $1-e^{-c}\geq\frac{3}{4}c$ for $0<c=h\alpha_{\min}\leq\frac{1}{4}$ which holds assuming that $h\leq\frac{1}{4\alpha_{\min}}$.
Thus, a sufficient condition for $(v_{4})\leq\epsilon/4$ is $h\leq\frac{\alpha_{\min}}{32L_{\max}^{2}d}\epsilon$.

Next, we upper-bound the first term by $(v_{1})\leq e^{-kh\alpha_{\min}}\mathop{\mathrm{KL}}\nolimits(p_{0},\mu_{0})$ so that a sufficient condition for $(v_{1})<\epsilon/4$ is $k>\frac{1}{h\alpha_{\min}}\log\Big(\frac{4\mathop{\mathrm{KL}}\nolimits(p_{0},
\mu_{0})}{\epsilon}\Big{missing})$.

A sufficient condition $(v_{2})<\epsilon/4$ is $\lambda_{k}\in]1-\frac{\epsilon}{4A^{\prime}},1]$.

Finally, we upper-bound the third term:

$$ $\displaystyle(v_{3})$ $\displaystyle:=A^{\prime}\sum_{i=1}^{k}(\lambda_{i}-\lambda_{i-1})\exp\Big(-h \sum_{j=i}^{k}\alpha_{j}\Big{missing})$ (41) $\displaystyle=A^{\prime}\Big{(}\sum_{i=1}^{\lfloor k/2\rfloor}(\lambda_{i}- \lambda_{i-1})\exp\Big(-h\sum_{j=i}^{k}\alpha_{j}\Big{missing})+\sum_{i= \lfloor k/2\rfloor}^{k}(\lambda_{i}-\lambda_{i-1})\exp\Big(-h\sum_{j=i}^{k} \alpha_{j}\Big{missing})\Big{)}$ (42) $\displaystyle\leq A^{\prime}\Big{(}\exp\Big(-h\sum_{j=\lfloor k/2\rfloor}^{k} \alpha_{j}\Big{missing})\sum_{i=1}^{\lfloor k/2\rfloor}(\lambda_{i}-\lambda_{i -1})+\sum_{i=\lfloor k/2\rfloor}^{k}(\lambda_{i}-\lambda_{i-1})\Big{)}$ (43) $\displaystyle\leq A^{\prime}\biggr{(}\exp(-hk\alpha_{\min}/2)(\lambda_{\lfloor k /2\rfloor}-\lambda_{1})+(\lambda_{k}-\lambda_{\lfloor k/2\rfloor})\big{)}$ (44) $\displaystyle\leq A^{\prime}\exp(-hk\alpha_{\min}/2)+A^{\prime}(\lambda_{k}- \lambda_{\lfloor k/2\rfloor})$ (45) $$

so that sufficient conditions for $(v_{3})<\frac{\epsilon}{4}$ can be obtained by setting each of the two terms smaller than $\frac{\epsilon}{8}$, yielding $k>\frac{2}{\alpha_{\min}h}\log\frac{8A^{\prime}}{\epsilon}$ and $\lambda_{k}-\lambda_{\lfloor k/2\rfloor}<\frac{\epsilon}{8A^{\prime}}$.
∎

###### Corollary 17

###### Proof.

### B.3 Technical lemma from Appendix B.1

In this section, we prove Lemma 16.

###### Proof of Lemma 16 .

We recall that the particles follow the recursion

$$ $X_{k+1}=X_{k}-h_{k}\nabla V_{\lambda_{k}}(X_{k})+\sqrt{2h_{k}}z_{k},$ $$

where $z_{k}$ follows a standard normal distribution on $\mathbb{R}^{d}$ and $X_{k}\sim p_{k}$. Hence, we have

$$ $\displaystyle\mathbb{E}[\|X_{k+1}\|^{2}]$ $\displaystyle=\mathbb{E}[\|X_{k}-h_{k}\nabla V_{\lambda_{k}}(X_{k})+\sqrt{2h_{ k}}z_{k}\|^{2}]$ (46) $\displaystyle=\mathbb{E}[\|X_{k}-h_{k}\nabla V_{\lambda_{k}}(X_{k})\|^{2}]+2dh _{k}$ (47) $\displaystyle=\mathbb{E}[\|X_{k}\|^{2}]-2h_{k}\mathbb{E}[X_{k}^{\top}\nabla V_ {\lambda_{k}}(X_{k})]+h_{k}^{2}\mathbb{E}[\|\nabla V_{\lambda_{k}}(X_{k})\|^{2 }]+2dh_{k}.$ (48) $$

The dissipativity assumption yields $\mathbb{E}[X_{k}^{\top}\nabla V_{\lambda_{k}}(X_{k})]\geq(a_{\pi}\land a_{\nu}
)\mathbb{E}[\|X_{k}\|^{2}]-(b_{\nu}+b_{\pi})$ and as in the proof of Proposition 14
we have $\|\nabla V_{\lambda_{k}}(X_{k})\|^{2}\leq 2(L_{\pi}+L_{\nu})^{2}(\|X_{k}\|^{2}
+\frac{b_{\nu}+b_{\pi}}{a_{\mu}\land a_{\pi}})$ so that

$$ $\displaystyle\mathbb{E}[\|X_{k+1}\|^{2}]$ $\displaystyle\leq\mathbb{E}[\|X_{k}\|^{2}]-2h_{k}((a_{\pi}\land a_{\nu}) \mathbb{E}[\|X_{k}\|^{2}]-(b_{\nu}+b_{\pi}))+2dh_{k}$ $\displaystyle~{}~{}~{}+2h_{k}^{2}(L_{\pi}+L_{\nu})^{2}\Big{(}\mathbb{E}[\|X_{k }\|^{2}]+\frac{b_{\nu}+b_{\pi}}{a_{\mu}\land a_{\pi}}\Big{)}.$ $$

Letting $L:=L_{\pi}+L_{\nu}$, $a:=a_{\nu}\land a_{\pi}$ and $b:=b_{\nu}+b_{\pi}$ we obtain

$$ $\displaystyle\mathbb{E}[\|X_{k+1}\|^{2}]$ $\displaystyle\leq\mathbb{E}[\|X_{k}\|^{2}]-2h_{k}\Big{(}(a-h_{k}L^{2})\mathbb{ E}[\|X_{k}\|^{2}]-(b+d)-h_{k}\frac{Lb}{a}\Big{)}$ $\displaystyle=\mathbb{E}[\|X_{k}\|^{2}](1-2h_{k}(a-h_{k}L^{2}))+2h_{k}\Big{(}b +d+h_{k}\frac{L^{2}b}{a}\Big{)}.$ $$

Now by induction, assume that $\mathbb{E}[\|X_{k}\|^{2}]\leq\max(\mathbb{E}_{p_{0}}[\|x\|^{2}]),\frac{2(3b/2+
d)}{a\land 1})$. By construction on $h_{k}$, $a-h_{k}L^{2}>0$ hence if $\mathbb{E}[\|X_{k}\|^{2}]>\frac{b+d+h_{k}L^{2}b/a}{2h_{k}(a-h_{k}L^{2})}$, then $\mathbb{E}[\|X_{k+1}\|^{2}]<\mathbb{E}[\|X_{k}\|^{2}]$ and in particular $\mathbb{E}[\|X_{k+1}\|^{2}]\leq\max(\mathbb{E}_{p_{0}}[\|x\|^{2}],\frac{2(3b/2
+d)}{a\land 1})$. Now, if $\mathbb{E}[\|X_{k}\|^{2}]\leq\frac{b+d+h_{k}L^{2}b/a}{2h_{k}(a-h_{k}L^{2})}$, then if $1>2h_{k}(a-h_{k}L^{2})$ we have

$$ $\displaystyle\mathbb{E}[\|X_{k+1}\|^{2}]$ $\displaystyle\leq\frac{b+d+h_{k}L^{2}b/a}{a-h_{k}L^{2}}(1-2h_{k}(a-h_{k}L^{2}) )+2h_{k}(b+d+h_{k}L^{2}b/a)$ (49) $\displaystyle=\frac{b+d+h_{k}L^{2}b/a}{a-h_{k}L^{2}}$ (50) $\displaystyle\leq\frac{2(3b/2+d)}{a},$ (51) $$

by construction on $h_{k}$. Conversely, if $1\leq 2h_{k}(a-h_{k}L^{2})$, then

$$ $\displaystyle\mathbb{E}[\|X_{k+1}\|^{2}]$ $\displaystyle\leq 2h_{k}\Big{(}b+d+h_{k}\frac{L^{2}b}{a}\Big{)}$ $\displaystyle\leq 2(3b/2+d).$ $$

∎

###### Proof of Lemma 16 .

## Appendix C Optimization of continuous-time tempered Langevin Dynamics

### C.1 Proof of Corollary 5

We will rewrite and bound the terms $(u_{1})$, $(u_{2})$ and $(u_{3})$ in the upper bound of Theorem 1 provided in Eq. 34, so that the role of the tempering schedule $\lambda(\cdot)$ is more explicit, at the expense of a looser upper-bound.

#### Rewriting ( u 3 ) subscript 𝑢 3 (u_{3}) ( italic_u start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT ) .

We begin with the third term, using integration
by parts to write

$$ $\displaystyle(u_{3})$ $\displaystyle:=A\int_{0}^{t}\dot{\lambda}_{s}\exp(-2\int_{s}^{t}\alpha_{v}dv)ds$ $\displaystyle=A\Big{(}\lambda_{t}-\lambda_{0}\exp(-2\int_{0}^{t}\alpha_{v}dv)- 2\int_{0}^{t}\lambda_{s}\alpha_{s}\exp(-2\int_{s}^{t}\alpha_{v}dv)ds\Big{)}\enspace.$ $$

#### Recalling ( u 2 ) subscript 𝑢 2 (u_{2}) ( italic_u start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) .

Recall that

$$ $\displaystyle(u_{2})$ $\displaystyle=A(1-\lambda_{t})\enspace.$ $$

#### Rewriting ( u 1 ) subscript 𝑢 1 (u_{1}) ( italic_u start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) .

We recall that $(u_{1})=\exp(-2\int_{0}^{t}\alpha_{v}dv)\mathop{\mathrm{KL}}\nolimits(p_{0},
\mu_{0})$. Assuming that the process is initialized at the proposal distribution $p_{0}=\nu$, we can use the tempering rule $\mu_{t}=c_{t}\nu^{1-\lambda_{t}}\pi^{\lambda_{t}}$ to rewrite the $\mathop{\mathrm{KL}}\nolimits$ term

$$ $\mathop{\mathrm{KL}}\nolimits(\nu,\mu_{0})=\lambda_{0}\mathop{\mathrm{KL}} \nolimits(\nu,\pi)-\log c_{0}.$ $$

By positivity of $\log c_{0}$, we can write $-\log c_{0}\leq\lambda_{0}\mathop{\mathrm{KL}}\nolimits(\pi,\nu)$. In particular

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(\nu,\mu_{0})$ $\displaystyle\leq\lambda_{0}(\mathop{\mathrm{KL}}\nolimits(\nu,\pi)+\mathop{ \mathrm{KL}}\nolimits(\pi,\nu))$ $\displaystyle=\lambda_{0}\Big{(}\int[V_{\pi}(x)-V_{\pi}^{*}-(V_{\nu}(x)-V_{\nu }^{*})]d\nu(x)+\int[V_{\nu}(x)-V_{\nu}^{*}-(V_{\pi}(x)-V_{\pi}^{*})]d\pi(x) \Big{)}$ $\displaystyle\leq\lambda_{0}A.$ $$

#### Upper bounding the sum.

We can now combine upper bounds on $(u_{1}),(u_{2})$ and $(u_{3})$ and simplify the result, using that the terms $\lambda_{0}A\exp(-2\int_{0}^{t}\alpha_{v}dv)$ and $A\lambda_{t}$ cancel out, to finally yield

$$ $\displaystyle\mathop{\mathrm{KL}}\nolimits(p_{t},\pi)\leq A\cdot G_{t}(\lambda ),\quad\quad G_{t}(\lambda):=1-2\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\Big(-2 \int_{s}^{t}\alpha_{v}\mathrm{d}v\Big{missing})\mathrm{d}s.$ (52) $$

#### Optimal schedule when α π ≥ α ν subscript 𝛼 𝜋 subscript 𝛼 𝜈 \alpha_{\pi}\geq\alpha_{\nu} italic_α start_POSTSUBSCRIPT italic_π end_POSTSUBSCRIPT ≥ italic_α start_POSTSUBSCRIPT italic_ν end_POSTSUBSCRIPT

Now, let $\Phi_{s}:=\exp\big(-2\int_{s}^{t}\alpha_{u}\mathrm{d}u).$
We have

$$ $G_{t}(\lambda)=1-2\int_{0}^{t}\lambda_{s}\alpha_{s}\Phi_{s}\mathrm{d}s.$ $$

Applying integration by parts, we find

$$ $\displaystyle G_{t}(\lambda)$ $\displaystyle=1-[\lambda_{s}\Phi_{s}]_{0}^{t}+\int_{0}^{t}\dot{\lambda}_{s} \Phi_{s}\mathrm{d}s=1-\lambda_{t}+\lambda_{0}\Phi_{0}+\int_{0}^{t}\dot{\lambda }_{s}\Phi_{s}\mathrm{d}s.$ $$

Since $\dot{\lambda}_{s}\geq 0$ and $\Phi_{s}\geq e^{-2(t-s)\alpha_{\pi}}$ (using the assumption $\alpha_{\pi}\geq\alpha_{\nu}$), it follows that

$$ $G_{t}(\lambda)\geq 1-\lambda_{t}+\lambda_{0}e^{-2t\alpha_{\pi}}+\int_{0}^{t} \dot{\lambda}_{s}e^{-2(t-s)\alpha_{\pi}}\mathrm{d}s.$ $$

Reversing the integration by parts,
we obtain

$$ $G_{t}(\lambda)\geq 1-2\int_{0}^{t}\lambda_{s}\alpha_{\pi}e^{-2(t-s)\alpha_{\pi }}\mathrm{d}s\geq 1-2\int_{0}^{t}\alpha_{\pi}e^{-2(t-s)\alpha_{\pi}}\mathrm{d}s,$ $$

where the last inequality uses $\lambda_{s}\leq 1$.
Recognizing the right-hand side as $G_{t}$ evaluated
at schedule $\lambda\equiv 1$, we conclude.

### C.2 Proof of Proposition 6

###### Sketch of proof.

We first make the change of variable $\Phi(s)=\exp\biggl(-\int_{s}^{t}\alpha_{u}du\biggr{missing})$ so that the problem can be re-written as

$$ $\sup_{\Phi\in I_{t}}\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{ \nu}}{2}-\int_{0}^{t}\dot{\Phi}^{2}_{s}ds-\frac{\alpha_{\nu}}{2}\Phi_{0}^{2} \Big{)},$ $$

where $I_{t}$ is the set of strictly positive functions $\Phi:[0,t]\mapsto\mathbb{R}$ with weak second derivative and such that $\alpha_{\pi}\Phi\leq\dot{\Phi}\leq\alpha_{\nu}\Phi$ and $\Phi\ddot{\Phi}\leq\dot{\Phi}^{2}$ and $\Phi(t)=1$. Unlike the previous objective $G(\cdot)$, note that our new problem has now a concave objective yet has non-convex (and non closed) constraints. Hence we make a convex relaxation and solve instead

$$ $\sup_{\Phi\in J_{t}}\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{ \nu}}{2}-\int_{0}^{t}\dot{\Phi}^{2}_{s}ds-\frac{\alpha_{\nu}}{2}\Phi_{0}^{2} \Big{)},$ $$

where $J_{t}$ is the set of non-negative functions in $W^{1,2}([0,t])$ such that $\alpha_{\pi}\Phi\leq\dot{\Phi}$ and $\Phi(t)=1$. After showing that an optimal solution $\Phi$ indeed exists, we explicitly describe it and show that it belongs to $I_{t}$ a.k.a. it verifies the original constraints. In order to come up with an explicit solution $\Phi$, we make a disjunction of cases on whether the constraint $\alpha_{\pi}\Phi\leq\dot{\Phi}$ is saturated: if it is always saturated, then $\Phi$ is exponential if not, then it must be linear on a maximal neighborhood around the non saturated point. We then prove that this maximal neighborhood is unique, pathwise connected and can only be of the form $[0,x_{0}]$ with $x_{0}\leq t$ so that $\Phi$ is linear on $[0,x_{0}]$ and is then exponential on $[x_{0},t]$.
∎

###### Proof of Prop. 6 .

We first notice that minimizing $G_{t}$ defined in Corollary 5 over the set of admissible tempering schedules $\lambda$
is equivalent to solving

$$ $\sup_{\lambda\in\Lambda_{t}}\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\Big(-2\int_{ s}^{t}\alpha_{u}\mathrm{d}u\Big{missing})\mathrm{d}s,$ $$

where $\Lambda_{t}$ is the set of functions from $[0,t]$ to $[0,1]$ with non-negative weak derivative.

###### Proposition 18

Suppose $\alpha_{\pi}<\alpha_{\nu}$ and
let $I_{t}$ be the set of positive functions $\Phi$ with weak second derivative
, such that $\Phi_{t}=1$,  $\alpha_{\pi}\Phi\leq\dot{\Phi}\leq\alpha_{\nu}\Phi$ and $\ddot{\Phi}\Phi-\dot{\Phi}^{2}$ is a non-positive measure. Then

$$ $\sup_{\lambda\in\Lambda_{t}}\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\Big(-2\int \alpha_{u}\mathrm{d}u\Big{missing})\mathrm{d}s=\sup_{\Phi\in I_{t}}\frac{1}{ \alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{\nu}}{2}-\int_{0}^{t}\dot{\Phi} ^{2}_{s}ds-\frac{\alpha_{\nu}}{2}\Phi_{0}^{2}\Big{)}.$ (53) $$

###### Proof.

Let $\lambda\in\Lambda_{t}$ and denote $\Phi_{s}:=\Phi(s)=\exp(-\int_{s}^{t}\alpha_{u}\mathrm{d}u)$. The function $\Phi$ is strictly positive and such that $\Phi_{t}=1$. Its first and second derivatives read

$$ $\begin{cases}&\dot{\Phi}_{s}=\alpha_{s}\Phi_{s},\\ &\ddot{\Phi}_{s}=\dot{\alpha}_{s}\Phi_{s}+\frac{\dot{\Phi}^{2}_{s}}{\Phi_{s}}. \end{cases}$ $$

In particular, since $\lambda\in[0,1]$ and $\alpha_{s}=(1-\lambda_{s})\alpha_{\nu}+\lambda_{s}\alpha_{\pi}$, we have $\alpha_{s}\in[\alpha_{\pi},\alpha_{\nu}]$ and by positiveness of $\Phi$, it holds

$$ $\alpha_{\pi}\Phi\leq\dot{\Phi}\leq\alpha_{\nu}\Phi.$ $$

Similarly, since $\dot{\lambda}$ is a non-negative measure, $\dot{\alpha}=(\alpha_{\pi}-\alpha_{\nu})\dot{\lambda}$ is a non-positive measure and so is $\dot{\alpha}\Phi^{2}$. This implies in particular

$$ $\ddot{\Phi}\Phi-\dot{\Phi}^{2}=\dot{\alpha}\Phi^{2}\leq 0.$ $$

Hence we verified that $\Phi\in I_{t}$. Furthermore, it reads

$$ $\displaystyle\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\Big(-2\int_{s}^{t}\alpha_{u }\mathrm{d}u\Big{missing})\mathrm{d}s$ $\displaystyle=\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\int_{0}^{t}(\alpha_{\nu}- \alpha_{s})\alpha_{s}\exp\Big(-2\int_{s}^{t}\alpha_{u}\mathrm{d}u\Big{missing} )\mathrm{d}s$ $\displaystyle=\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\int_{0}^{t}\alpha_{\nu}\dot{ \Phi}_{s}\Phi_{s}-\dot{\Phi}^{2}_{s}\mathrm{d}s$ $\displaystyle=\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{\nu}}{2} [\Phi^{2}_{s}]_{0}^{t}-\int_{0}^{t}\dot{\Phi}^{2}_{s}\mathrm{d}s\Big{)}$ $\displaystyle=\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{\nu}}{2} (1-\Phi_{0}^{2})-\int_{0}^{t}\dot{\Phi}^{2}(s)\mathrm{d}s\Big{)}.$ $$

In particular, we have

$$ $\sup_{\lambda\in\Lambda_{t}}\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\Big(-2\int \alpha_{u}du\Big{missing})ds\leq\sup_{\Phi\in I_{t}}\frac{1}{\alpha_{\nu}- \alpha_{\pi}}\Big{(}\frac{\alpha_{\nu}}{2}-\int_{0}^{t}\dot{\Phi}^{2}_{s}ds- \frac{\alpha_{\nu}}{2}\Phi_{0}^{2}\Big{)}.$ $$

Conversely, let $\Phi\in I_{t}$, defining $\alpha_{s}=\partial_{s}\log\Phi=\dot{\Phi}/\Phi$ and $\lambda_{s}=\frac{\alpha_{\nu}-\alpha_{s}}{\alpha_{\pi}-\alpha_{\nu}}$ we have by construction that $\lambda\in\Lambda_{t}$. Furthermore, the previous computations show that

$$ $\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{\nu}}{2}(1-\Phi_{0}^{2 })-\int_{0}^{t}\dot{\Phi}^{2}_{s}\mathrm{d}s\Big{)}=\int_{0}^{t}\lambda_{s} \alpha_{s}\exp\Big(-2\int\alpha_{u}\mathrm{d}u\Big{missing})ds.$ $$

In particular, we recover the reverse inequality

$$ $\sup_{\Phi\in I_{t}}\frac{1}{\alpha_{\nu}-\alpha_{\pi}}\Big{(}\frac{\alpha_{ \nu}}{2}-\int_{0}^{t}\dot{\Phi}^{2}_{s}ds-\frac{\alpha_{\nu}}{2}\Phi_{0}^{2} \Big{)}\leq\sup_{\lambda\in\Lambda_{t}}\int_{0}^{t}\lambda_{s}\alpha_{s}\exp \Big(-2\int\alpha_{u}\mathrm{d}u\Big{missing})\mathrm{d}s.\qed$ $$

Hence the problem can be re-written as the minimization of the convex functional $\Phi\mapsto\int_{0}^{t}\dot{\Phi}^{2}_{s}ds+\frac{\alpha_{\nu}}{2}\Phi_{0}^{2}$ under the constraint $\Phi\in I_{t}$. As can be noted, the constraint $\ddot{\Phi}\Phi-\dot{\Phi}^{2}\leq 0$ is non-convex and the constraints $\Phi>0$, $\Phi$ has a weak second derivative are non-closed. Hence we are going to relax all of these constraints and solve instead

$$ $\inf_{\Phi\in J_{t}}~{}\int_{0}^{t}\dot{\Phi}^{2}_{s}\mathrm{d}s+\frac{\alpha_ {\nu}}{2}\Phi_{0}^{2},$ (54) $$

where $J_{t}\subset W^{1,2}([0,t])$ is the set of positive functions such that $\Phi_{t}=1,~{}\alpha_{\pi}\Phi\leq\dot{\Phi}$ almost everywhere.
Note that we also dropped the constraint $\dot{\Phi}\leq\alpha_{\nu}\Phi$ for convenience of the proof. Nevertheless, we show that at the optimum, the solution of the problem above verifies all the initial constraints.

###### Proposition 19

Assume $\alpha_{\pi}<\alpha_{\nu}$.
Then Eq. 54 admits a minimizer $\Phi$ which has the following expression:

- 1.
If $\alpha_{\pi}>\frac{\alpha_{\nu}}{2}$, then $\Phi_{s}=e^{\alpha_{\pi}(s-t)}$.
- 2.
If $\frac{\alpha_{\nu}}{t\alpha_{\nu}+2}<\alpha_{\pi}\leq\frac{\alpha_{\nu}}{2}$, then
$\Phi_{s}=\begin{cases}\alpha_{\pi}e^{\alpha_{\pi}(\frac{1}{\alpha_{\pi}}-\frac
{2}{\alpha_{\nu}}-t)}s+\frac{2\alpha_{\pi}}{\alpha_{\nu}}e^{\alpha_{\pi}(\frac
{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}-t)}&s\leq\frac{1}{\alpha_{\pi}}-\frac
{2}{\alpha_{\nu}},\\
e^{\alpha_{\pi}(s-t)}&s>\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}.\end{cases}$
- 3.
If $\alpha_{\pi}\leq\frac{\alpha_{\nu}}{t\alpha_{\nu}+2}$, then $\Phi_{s}=\frac{\alpha_{\nu}}{2+t\alpha_{\nu}}s+(1-\frac{t\alpha_{\nu}}{2+t
\alpha_{\nu}})$.

###### Proof.

We aim to solve the minimization problem defined in Eq. 54.

###### Sketch of proof.

###### Proof of Prop. 6 .

###### Proposition 18

###### Proof.

###### Proposition 19

###### Proof.

#### Existence of a minimum.

Since the objective has compact sub-level sets and is continuous for the $W^{1,2}([0,t])$ norm, we can extract a minimizing sequence $(\Phi_{n})_{n}$ in $J_{t}$ that converges in
$W^{1,2}$ towards some $\Phi$ in $W^{1,2}([0,t])$.
Because $W^{1,2}$ metrizes pointwise convergence,
we obtain that the infimum verifies two of the constraints: $\Phi_{t}=1$ and $\Phi\geq 0$ almost everywhere.

Then, since $\Phi_{n}\in J_{t}$, for $s_{0},h>0$ such that $s_{0},s_{0}+h\in[0,t]$ we have $0\leq\alpha_{\pi}\Phi_{n}\leq\dot{\Phi}_{n}$ and then:

$$ $\displaystyle\alpha_{\pi}(\Phi_{n})_{s_{0}}\leq\frac{\alpha_{\pi}}{h}\int_{s_{ 0}}^{s_{0}+h}(\Phi_{n})_{s}\mathrm{d}s\leq\frac{1}{h}\int_{s_{0}}^{s_{0}+h}( \dot{\Phi}_{n})_{s}\mathrm{d}s=\frac{(\Phi_{n})_{s_{0}+h}-(\Phi_{n})_{s_{0}}}{ h}.$ $$

Letting $n$ go to infinity and $h$ to zero, we obtain,
for almost all $s_{0}\in[0,t]$

$$ $\displaystyle\alpha_{\pi}\Phi_{s_{0}}\leq\dot{\Phi}_{s_{0}},$ $$

hence $\Phi\in J_{t}$, showing $\Phi$ is a minimizer of Eq. 54.

#### Explicit expression of the minimum.

We now derive an explicit expression for $\Phi$ based on whether or not there exists a point $x_{0}$ where the constraint

$$ $\displaystyle\alpha_{\pi}\Phi\leq\dot{\Phi}\,,$ $$

is not saturated.

#### Case 1: the inequality is saturated everywhere.

In the case where the inequality constraint above is saturated for $x$ almost everywhere, we obtain that the minimizer $\Phi$ is of the form $\Phi_{s}=K\exp(\alpha_{\pi}s)$ and using the fact that $\Phi_{t}=1$, we recover that $\Phi_{s}=\exp((s-t)\alpha_{\pi})$.

#### Case 2: the inequality is not saturated saturated everywhere.

Now let us assume that there exists $x_{0}$ where the inequality is not saturated by the minimizer

$$ $\displaystyle\alpha_{\pi}\Phi(x_{0})<\dot{\Phi}(x_{0}).$ $$

We can make a disjunction of cases with respect to $x_{0}$.

#### If x 0 = t subscript 𝑥 0 𝑡 x_{0}=t italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = italic_t .

We will show that $\Phi$ is linear on $[0,t]$. We first define a neighborhood of $x_{0}$ of size $\epsilon$ that satisfies a certain inequality.
By continuity of $\Phi$ and the definition of the derivative, there exists an $\epsilon>0$ such that for all $\delta<\epsilon$

$$ $\alpha_{\pi}\Phi(t)<\frac{\Phi(t)-\Phi(t-\delta)}{\delta}.$ (55) $$

Let us now define the neighborhood size $\epsilon$ to be the largest $\epsilon>0$ such that $t-\epsilon\geq 0$ and such that the inequality above holds for all $\delta<\epsilon$.

Next, we define a candidate $\tilde{\Phi}$ that is linear in this neighborhood, and equal to the minimizer $\Phi$ outside the neighborhood. Let

$$ $\displaystyle\begin{cases}&\tilde{\Phi}(x)=\Phi(x)~{}\text{if}~{}x\notin[t- \epsilon,t],\\ &\tilde{\Phi}(x)=\frac{\Phi(t)-\Phi(t-\epsilon)}{\epsilon}(x-t+\epsilon)+\Phi( t-\epsilon)~{}\text{if}~{}x\in[t-\epsilon,t].\end{cases}$ $$

By construction, $\tilde{\Phi}$ verifies the constraints, i.e. $\tilde{\Phi}\in J_{t}$. Indeed, taking $\delta\to\epsilon$ in Eq. 55, and using the monotonicity of $\tilde{\Phi}$, we get successively for almost every $x\in[0,t]$:

$$ $\alpha_{\pi}\tilde{\Phi}(x)\leq\alpha_{\pi}\tilde{\Phi}(t)\leq\frac{\Phi(t)- \Phi(t-\epsilon)}{\epsilon}=\dot{\Phi}(x).$ $$

Hence, $\tilde{\Phi}$ is a suitable candidate for solving Problem Eq. 54.

Finally, we show that the candidate we built $\tilde{\Phi}$ achieves a smaller objective than a minimizer and must therefore be equal to a minimizer $\Phi\in J_{t}$. By optimality,

$$ $\displaystyle\int_{0}^{t}\dot{\Phi}^{2}(s)ds+\frac{\alpha_{\nu}}{2}\Phi(0)^{2} \leq\int_{0}^{t}\dot{\tilde{\Phi}}^{2}(s)ds+\frac{\alpha_{\nu}}{2}\tilde{\Phi} (0)^{2}$ $$

and since $\Phi$ and $\tilde{\Phi}$ coincide on $[0,t-\epsilon]$, it holds

$$ $\displaystyle\int_{t-\epsilon}^{t}\dot{\Phi}^{2}(s)ds\leq\frac{(\Phi(t)-\Phi(t -\epsilon))^{2}}{\epsilon}.$ $$

The same inequality in the other direction is obtained by applying Jensen’s inequality

$$ $\displaystyle\int_{t-\epsilon}^{t}\dot{\Phi}^{2}(s)ds$ $\displaystyle\geq\epsilon\Big{(}\frac{1}{\epsilon}\int_{t-\epsilon}^{t}\dot{ \Phi}(s)ds\Big{)}^{2}=\frac{(\Phi(t)-\Phi(t-\epsilon))^{2}}{\epsilon}.$ $$

We are therefore in the equality case of Jensen with a strongly convex and smooth function, so it must hold for $s$ almost everywhere in the neighborhood $[t-\epsilon,t]$ that

$$ $\dot{\Phi}(s)=\frac{\Phi(t)-\Phi(t-\epsilon)}{\epsilon},$ $$

and in particular $\Phi$ is linear in the neighborhood $[t-\epsilon,t]$ and is of the form $\Phi(x)=ax+b$.

Finally, we will show that the neighborhood covers the entire interval $[0,t]$, or in other words, that $\epsilon=t$. Suppose it is not the case and
$\epsilon<t$. Then, by continuity of $\Phi$ at the neighborhood border $t-\epsilon$,

$$ $\displaystyle\alpha_{\pi}\Phi(t)=\frac{\Phi(t)-\Phi(t-\epsilon)}{\epsilon}\enspace.$ $$

Combined with the fact that $\Phi(t)=1$, this implies $a=\alpha_{\pi}$ which is a contradiction with the inequality Eq. 55 that characterizes the neighborhood, and in particular yields $a>\alpha_{\pi}$. Hence, we must have
$\epsilon=t$
and in particular, $\Phi$ is linear on the whole interval $[0,t]$.

#### If x 0 ∈ ] 0 , t [ x_{0}\in]0,t[ italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ∈ ] 0 , italic_t [

As before we can define $\epsilon_{+}$ and $\epsilon_{-}$ as the largest $\epsilon>0$ such that $x_{0}+\epsilon<t$ (resp. $x_{0}-\epsilon>0$) and $\frac{\Phi(x_{0}+\delta)-\Phi(x_{0})}{\delta}>\alpha_{\pi}\Phi(x_{0}+\delta)$ for all $\delta<\epsilon_{+}$ (resp. $\frac{\Phi(x_{0})-\Phi(x_{0}-\delta)}{\delta}>\alpha_{\pi}\Phi(x_{0})$ for all $\delta<\epsilon_{-}$). Again, we obtain that $\Phi$ must be linear on $[x_{0},x_{0}+\epsilon_{+}]$ of the form $\Phi(x)=a_{+}x+b_{+}$ and linear on $[x_{0}-\epsilon_{-},x_{0}]$ of the form $\Phi(x)=a_{-}x+b_{-}$. Furthermore, since $\Phi$ is differentiable at $x_{0}$, its derivative must read

$$ $\dot{\Phi}(x_{0})=\lim_{h\to 0}\frac{\Phi(x_{0}+h)-\Phi(x_{0})}{h}=\lim_{h\to 0 }\frac{\Phi(x_{0})-\Phi(x_{0}-h)}{h},$ $$

which implies $a_{+}=a_{-}\coloneqq a$ and by continuity of $\Phi$ at $x_{0}$, we also recover $b_{+}=b_{-}$. In particular, $\Phi$ is linear across the whole interval $[x_{0}-\epsilon_{-},x_{0}+\epsilon_{+}]$. We have now four possibilities: either a) $x_{0}-\epsilon_{-}=0$ and $x_{0}+\epsilon_{+}=t$, b) $x_{0}-\epsilon_{-}>0$ and $x_{0}+\epsilon_{+}<t$, c) $x_{0}-\epsilon_{-}>0$ and $x_{0}+\epsilon_{+}=t$, d) $x_{0}-\epsilon_{-}=0$ and $x_{0}+\epsilon_{+}<t$. The case a) simply corresponds to the case where $\Phi$ is linear across the whole interval. The case b) implies by continuity that $a=\alpha_{\pi}\Phi(x_{0})=\alpha_{\pi}\Phi(x_{0}+\epsilon_{+})$ which implies that $a=0$. This cannot hold as we initially assumed that $\alpha_{\pi}\Phi(x_{0})<\dot{\Phi}(x_{0})=0$ which would result in a violation of the positivity constraint. The case c) yields the contradiction $a=\alpha_{\pi}\Phi(x_{0})$ and $a>\alpha_{\pi}\Phi(x_{0})$. Finally, let us deal with case d). We prove that in this case, there exists no other point outside $[0,x_{0}+\epsilon_{+}]$ such that the constraint $\alpha_{\pi}\Phi\leq\dot{\Phi}$ is not saturated ; in particular this implies that $\Phi$ is linear on $[0,x_{0}+\epsilon_{+}]$ and of the form $K\exp(\alpha_{\pi}x)$ on $[x_{0}+\epsilon_{+},t]$. Let us assume that there exists $x_{1}$ outside of $[0,x_{0}+\epsilon_{+}]$ such that

$$ $\alpha_{\pi}\Phi(x_{1})<\dot{\Phi}(x_{1}).$ $$

Just as before, this implies the existence of $\tilde{\epsilon}_{+}$ such that $\Phi$ is linear across $[0,x_{1}+\tilde{\epsilon}_{+}]$ and such that

$$ $\alpha_{\pi}\Phi(x_{1}+\tilde{\epsilon}_{+})\leq\frac{\Phi(x_{1}+\tilde{ \epsilon}_{+})-\Phi(x_{1})}{\tilde{\epsilon}_{+}}.$ $$

By linearity, if we take $\epsilon$ such that $x_{0}+\epsilon<x_{1}+\tilde{\epsilon}_{+}$, the right hand side is also given by $\frac{\Phi(x_{0}+\epsilon)-\Phi(x_{0})}{\epsilon}$ and since $\Phi$ is strictly increasing, the left-hand side can be lower-bounded by $\alpha_{\pi}\Phi(x_{0}+\epsilon)$ which implies

$$ $\alpha_{\pi}\Phi(x_{0}+\epsilon)<\frac{\Phi(x_{0}+\epsilon)-\Phi(x_{0})}{ \epsilon},$ $$

for all $\epsilon$ such that $x_{0}+\epsilon<x_{1}+\tilde{\epsilon}_{+}$. Since $x_{1}+\tilde{\epsilon}_{+}>x_{0}+\epsilon_{+}$, this contradicts the definiton of $\epsilon_{+}$ which was chosen as the largest $\epsilon$ such that for all $\epsilon\leq\epsilon_{+}$,

$$ $\alpha_{\pi}\Phi(x_{0}+\epsilon)<\frac{\Phi(x_{0}+\epsilon)-\Phi(x_{0})}{ \epsilon}.$ $$

In particular, the constraint $\alpha_{\pi}\Phi\leq\dot{\Phi}$ is always saturated outside of $[0,x_{0}+\epsilon_{+}]$.

#### If x 0 = 0 subscript 𝑥 0 0 x_{0}=0 italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT = 0

As before, we obtain that $\Phi$ is either linear across the whole space $[0,t]$, either there exists $x_{0}$ such that $\Phi$ is linear across $[0,x_{0}]$ and of the form $K\exp(\alpha_{\pi}x)$ on $[x_{0},t]$ and such that $\alpha_{\pi}\Phi(x_{0})=\dot{\Phi}(x_{0})$.

#### Summary of the minimizer candidates

We can now summarize the candidates we obtained for the minimizer function $\Phi$. It has the three following possible forms:

- •
Form 1: $\Phi$ is an exponential function of the form $K\exp(\alpha_{\pi}x)$ on the entire interval $[0,t]$.
- •
Form 2: $\Phi$ is a linear function on the entire interval $[0,t]$.
- •
Form 3: $\Phi$ is linear function then an exponential function on the entire interval.
Specifically, there exists $x_{0}\in]0,t[$ such that $\Phi$ is linear on $[0,x_{0}]$ and of the form $K\exp(\alpha_{\pi}x)$ on $[x_{0},t]$ and such that $\alpha_{\pi}\Phi(x_{0})=\dot{\Phi}(x_{0})$.

We shall determine which candidate $\Phi$ among the three is the true minimizer, by evaluating the objective function Eq. 54 for each and picking the candidate which achieves the lowest value.

#### Form 1.

Since $\Phi(t)=1$, it implies that the function $\Phi$ is entirely determined and given by $\Phi(x)=\exp(\alpha_{\pi}(x-t))$. In this case, the value of the objective is given by

$$ $\displaystyle\int_{0}^{t}\dot{\Phi}^{2}(s)ds+\frac{\alpha_{\nu}}{2}\Phi(0)^{2}$ $\displaystyle=\alpha_{\pi}^{2}\Big{[}\frac{e^{2\alpha_{\pi}(x-t)}}{2\alpha_{ \pi}}\Big{]}_{0}^{t}+\frac{\alpha_{\nu}}{2}e^{-2\alpha_{\pi}t},=\frac{\alpha_{ \pi}}{2}+\frac{e^{-2\alpha_{\pi}t}}{2}(\alpha_{\nu}-\alpha_{\pi}).$ $$

#### Form 2.

The function $\Phi$ is of the form $\Phi(x)=ax+b$. Since $\Phi(t)=1$, the coefficient $b$ is given by $1-at$. Furthermore, the constraint $\alpha_{\pi}\Phi\leq\dot{\Phi}$ is equivalent to solving
$a\geq\alpha_{\pi}$ and the constraint $\Phi\geq 0$ becomes $a\leq 1/t$. Hence, in the case where $1/t<\alpha_{\pi}$, there is no linear admissible potential. In the case where, $\alpha_{\pi}\leq 1/t$, we need to solve the following one dimensional quadratic problem

$$ $\inf_{1/t\geq a\geq\alpha_{\pi}}ta^{2}+\frac{\alpha_{\nu}}{2}(1-at)^{2}.$ $$

The objective can be rewritten as $\theta(a)=a^{2}(t+\frac{t^{2}\alpha_{\nu}}{2})-at\alpha_{\nu}+\frac{\alpha_{
\nu}}{2}$. The minimum of $\theta$ is given by

$$ $a_{*}\coloneqq\frac{\alpha_{\nu}}{2+t\alpha_{\nu}}$ (56) $$

Note that we always have $a_{*}\leq 1/t$, hence if $\alpha_{\pi}\leq a_{*}$ the minimum is attained for $a=a_{*}$ and is given by

$$ $\displaystyle\theta(a^{*})$ $\displaystyle=\frac{\alpha_{\nu}}{2}-\frac{t\alpha_{\nu}^{2}}{4+2t\alpha_{\nu} }=\frac{\alpha_{\nu}}{2}(1-\frac{t\alpha_{\nu}}{2+t\alpha_{\nu}})=\frac{\alpha _{\nu}}{2+t\alpha_{\nu}}.$ $$

If $\alpha_{\pi}>a_{*}$, the minimum is attained for $a=\alpha_{\pi}$ and is given by

$$ $\displaystyle\theta(\alpha_{\pi})$ $\displaystyle=t\alpha_{\pi}^{2}+\frac{\alpha_{\nu}}{2}(1-\alpha_{\pi}t)^{2}=t \alpha_{\pi}^{2}+\frac{\alpha_{\nu}}{2}-\alpha_{\nu}\alpha_{\pi}t+(t\alpha_{ \pi})^{2}\frac{\alpha_{\nu}}{2}=t\alpha_{\pi}(\alpha_{\pi}-\alpha_{\nu}+t\frac {\alpha_{\pi}\alpha_{\nu}}{2})+\frac{\alpha_{\nu}}{2}.$ $$

#### Form 3.

There exists $0<x_{0}<t$ such that the function $\Phi$ is of the form $ax+b$ over $[0,x_{0}]$ and then is given by $e^{\alpha_{\pi}(x-t)}$ over $[x_{0},t]$ and which is such that $\dot{\Phi}(x_{0})=\alpha_{\pi}\Phi(x_{0})$. The continuity of $\Phi$ implies that
$ax_{0}+b=e^{\alpha_{\pi}(x_{0}-t)}$ and the previous equation gives $a=(ax_{0}+b)\alpha_{\pi}$. Both these equations uniquely determine $a$ and $b$ when $x_{0}$ is fixed as

$$ $\begin{cases}&a=\alpha_{\pi}e^{\alpha_{\pi}(x_{0}-t)},\\ &b=e^{\alpha_{\pi}(x_{0}-t)}(1-\alpha_{\pi}x_{0}),\end{cases}$ $$

and in particular the positivity constraint is equivalent to $x_{0}\leq\frac{1}{\alpha_{\pi}}$ ; note that the constraint $\alpha_{\pi}\Phi\leq\dot{\Phi}$ is indeed respected over $[0,t]$. Hence, we must solve the following one dimensional problem

$$ $\inf_{0\leq x_{0}\leq\min(t,\frac{1}{\alpha_{\pi}})}x_{0}\alpha_{\pi}^{2}e^{2 \alpha_{\pi}(x_{0}-t)}+\frac{\alpha_{\pi}}{2}(1-e^{2\alpha_{\pi}(x_{0}-t)})+ \frac{\alpha_{\nu}}{2}e^{2\alpha_{\pi}(x_{0}-t)}(1-\alpha_{\pi}x_{0})^{2}.$ $$

Let us remark that $x_{0}=0$ being an admissible candidate, the potential $\Phi(x)=e^{\alpha_{\pi}(x-t)}$ is indeed an admissible candidate and in particular, the value of the problem above is always lower than the one obtained with Form 1. Denoting $f$ the objective function, let us compute the derivative of $f$. For all $x_{0}$, we have

$$ $\displaystyle f^{\prime}(x_{0})$ $\displaystyle=\alpha_{\pi}^{2}e^{2(x_{0}-t)}+2x_{0}\alpha_{\pi}^{3}e^{2(x_{0}- t)}-\alpha_{\pi}^{2}e^{2(x_{0}-t)}+\alpha_{\pi}\alpha_{\nu}(1-x_{0}\alpha_{\pi })^{2}e^{2(x_{0}-t)}$ $\displaystyle~{}~{}~{}-\alpha_{\nu}\alpha_{\pi}(1-x_{0}\alpha_{\pi})e^{2(x_{0} -t)},$ $\displaystyle=e^{2(x_{0}-t)}\alpha_{\pi}\Big{(}2x_{0}\alpha_{\pi}^{2}-\alpha_{ \nu}(1-x_{0}\alpha_{\pi})(1-1+x_{0}\alpha_{\pi})\Big{)},$ $\displaystyle=x_{0}e^{2(x_{0}-t)}\alpha_{\pi}^{2}(2\alpha_{\pi}-\alpha_{\nu}(1 -x_{0}\alpha_{\pi})).$ $$

The term $(2\alpha_{\pi}-\alpha_{\nu}(1-x_{0}\alpha_{\pi}))$ cancels for $x_{0}=\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}$, hence if $\alpha_{\pi}\geq\frac{\alpha_{\nu}}{2}$, the derivative $f^{\prime}$ is always non-negative for all $x_{0}\geq 0$ hence the optimal choice of $x_{0}$ is given by $x_{0}=0$. Let us remark that this case implies $\alpha_{\pi}>a_{*}$ where $a_{*}$ is defined in Eq. 56 and for which the optimal Form 2. is given by $\Phi(x)=\alpha_{\pi}x+(1-t\alpha_{\pi})$ which an admissibile candidate for Form 3. This proves that whenever $\alpha_{\pi}>\frac{\alpha_{\nu}}{2}$, the optimal potential is given by $\Phi(x)=e^{\alpha_{\pi}(s-t)}$.with $x_{0}=t$.
If $\alpha_{\pi}<\frac{\alpha_{\nu}}{2}$, then $f$ decreases between 0 0 and $\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}$ and then increases. In particular, since $\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}<\frac{1}{\alpha_{\pi}}$, the minimum is attained for $x_{0}=\min(t,\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}})$. In the case where $t\leq\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}$ which is equivalent to $\alpha_{\pi}\leq a_{*}$ with $a_{*}$ defined in Eq. 56, the obtained potential is linear hence it is necessarily sub-optimal with respect to Form 2. which yields as an optimal potential

$$ $\Phi(x)=a_{*}x+(1-a_{*}t).$ $$

Let us now place ourselves in the case $t>\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}$. In the case where $t>\frac{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}$, which is equivalent to $\alpha_{\pi}>a_{*}$, the optimal potential yielded by Form 2. (if any) is given by $\Phi(x)=\alpha_{\pi}x+(1-\alpha_{\pi}t)$ which is admissible for Form 3. by taking $x_{0}=t$ hence, Form 3. is necessarily sub-optimal.
As a conclusion, we have obtained the following expressions for $\Phi$:

- 1.
If $\alpha_{\pi}>\frac{\alpha_{\nu}}{2}$, we have $\Phi(x)=e^{\alpha_{\pi}(x-t)}$.
- 2.
If $\frac{\alpha_{\nu}}{t\alpha_{\nu}+2}<\alpha_{\pi}\leq\frac{\alpha_{\nu}}{2}$, then $\Phi$ is given by
$\begin{cases}&\Phi(x)=\alpha_{\pi}e^{\alpha_{\pi}(\frac{1}{\alpha_{\pi}}-\frac
{2}{\alpha_{\nu}}-t)}x+\frac{2\alpha_{\pi}}{\alpha_{\nu}}e^{\alpha_{\pi}(\frac
{1}{\alpha_{\pi}}-\frac{2}{\alpha_{\nu}}-t)}~{}\text{if}~{}x\leq\frac{1}{
\alpha_{\pi}}-\frac{2}{\alpha_{\nu}},\\
&\Phi(x)=e^{\alpha_{\pi}(x-t)}~{}\text{if}~{}x>\frac{1}{\alpha_{\pi}}-\frac{2}
{\alpha_{\nu}}.\end{cases}$
- 3.
If $\alpha_{\pi}\leq\frac{\alpha_{\nu}}{t\alpha_{\nu}+2}$, then $\Phi(x)=\frac{\alpha_{\nu}}{2+t\alpha_{\nu}}x+(1-\frac{t\alpha_{\nu}}{2+t
\alpha_{\nu}})$.

Note that in any case, $\Phi$ is in fact continuously differentiable and verifies almost everywhere $\ddot{\Phi}\Phi\leq\dot{\Phi}^{2}$ as well as $\dot{\Phi}\leq\alpha_{\nu}\Phi$, hence it is a solution of the problem

$$ $\inf_{\begin{subarray}{c}\Phi\geq 0,\ddot{\Phi}\Phi\leq\dot{\Phi}^{2},\\ \Phi(t)=1,~{}\alpha_{\pi}\Phi\leq\dot{\Phi}\leq\alpha_{\nu}\Phi.\end{subarray} }~{}\int_{0}^{t}\dot{\Phi}^{2}(s)ds+\frac{\alpha_{\nu}}{2}\Phi(0)^{2}.$ $$

∎
The optimal $\Phi$ is linked to the optimal tempering scheme $\lambda$ as $\lambda_{s}=\frac{\alpha_{\nu}-\alpha_{s}}{\alpha_{\nu}-\alpha_{\pi}}$ with $\alpha_{s}=\partial_{s}\log(\Phi)$. Hence we obtain

$$ $\lambda_{s}=\min\Big{(}1,\frac{\alpha_{\nu}(\alpha_{\nu}s+1)}{(\alpha_{\nu}- \alpha_{\pi})(\alpha_{\nu}s+2)}\Big{)}.$ $$

∎

### C.3 Proof of Proposition 7

Reversing the integration by parts we have

$$ $\displaystyle G_{t}(\lambda)$ $\displaystyle=1-2\int_{0}^{t}\lambda_{s}\alpha_{s}\exp\big(-2\int_{s}^{t} \alpha_{v}\mathrm{d}v\big{missing})\mathrm{d}s=\int_{0}^{t}\dot{\lambda}_{s} \exp\big(-2\int_{s}^{t}\alpha_{v}\mathrm{d}v\big{missing})\mathrm{d}s.$ $$

Hence

$$ $\displaystyle G_{t}(\lambda)$ $\displaystyle=\int_{0}^{t}\dot{\lambda}_{s}\exp\Big(-2\int_{s}^{t}\alpha_{v}dv \Big{missing})ds$ $\displaystyle=\frac{1}{t}\int_{0}^{t}\exp\Big(-2\int_{s}^{t}(\frac{v}{t}( \alpha_{\pi}-\alpha_{\nu})+\alpha_{\nu})dv\Big{missing})ds$ $\displaystyle=\frac{1}{t}\int_{0}^{t}\exp\Big(-2\frac{\alpha_{\pi}-\alpha_{\nu }}{t}\frac{1}{2}(t^{2}-s^{2})-2(t-s)\alpha_{\nu}\Big{missing})ds$ $\displaystyle=\frac{1}{t}\int_{0}^{t}\exp\Big(-\frac{\alpha_{\nu}-\alpha_{\pi} }{t}s^{2}+2\alpha_{\nu}s-t(\alpha_{\nu}+\alpha_{\pi})\Big{missing})ds\enspace.$ $$

Recall that for generic $a,b,c>0$, we have

$$ $\int\exp(-ax^{2}+bx-c)dx=\frac{\sqrt{\pi}}{2\sqrt{a}}\exp(b^{2}/4a-c)\erf((2ax -b)/(2\sqrt{a}))+\mathrm{constant}.$ $$

We may apply this formula since $\alpha_{\pi}<\alpha_{\nu}$.
it yields the equality claim:

$$ $\displaystyle G_{t}(\lambda)$ $\displaystyle=\frac{1}{\sqrt{t}}\frac{\sqrt{\pi}}{2\sqrt{\alpha_{\nu}-\alpha_{ \pi}}}\exp\Big(\frac{t\alpha_{\pi}^{2}}{\alpha_{\nu}-\alpha_{\pi}}\Big{missing })\Big{(}\erf\Big(\frac{\sqrt{t}\alpha_{\nu}}{\sqrt{\alpha_{\nu}-\alpha_{\pi}} }\Big{missing})-\erf\Big(\frac{\sqrt{t}\alpha_{\pi}}{\sqrt{\alpha_{\nu}-\alpha _{\pi}}}\Big{missing})\Big{)}\enspace.$ $$

Now, let us consider the
behavior of $G_{t}(\lambda)$ as $t\to\infty$.
Here, we Taylor expand to obtain

$$ $\displaystyle\erf\Big(\frac{\sqrt{t}\alpha_{\nu}}{\sqrt{\alpha_{\nu}-\alpha_{ \pi}}}\Big{missing})-\erf\Big(\frac{\sqrt{t}\alpha_{\pi}}{\sqrt{\alpha_{\nu}- \alpha_{\pi}}}\Big{missing})$ $\displaystyle=\sqrt{\frac{\alpha_{\nu}-\alpha_{\pi}}{t\pi}}\Big{(}\frac{1}{ \alpha_{\pi}}\exp\Big(-\frac{t\alpha_{\pi}^{2}}{\alpha_{\nu}-\alpha_{\pi}}\Big {missing})-\frac{1}{\alpha_{\nu}}\exp\Big(-\frac{t\alpha_{\nu}^{2}}{\alpha_{ \nu}-\alpha_{\pi}}\Big{missing})\Big{)}$ $\displaystyle+O\Big{(}\frac{1}{t^{3/2}}\Big{)}\Big{(}\exp\Big(-\frac{t\alpha_{ \nu}^{2}}{\alpha_{\nu}-\alpha_{\pi}}\Big{missing})-\exp\Big(-\frac{t\alpha_{ \pi}^{2}}{\alpha_{\nu}-\alpha_{\pi}}\Big{missing})\Big{)}\enspace.$ $$

Therefore

$$ $\displaystyle G_{t}(\lambda)$ $\displaystyle=\frac{1}{2t\alpha_{\pi}}-\frac{1}{2t\alpha_{\nu}}\exp\Big(\frac{ -t\alpha_{\nu}^{2}-\alpha_{\pi}^{2}}{\alpha_{\nu}-\alpha_{\pi}}\Big{missing})+ O(\frac{1}{t}\exp\Big(\frac{-t\alpha_{\nu}^{2}-\alpha_{\pi}^{2}}{\alpha_{\nu}- \alpha_{\pi}}\Big{missing}))\enspace.$ $$

This yields the claimed asymptotic result.

These results are numerically validated in Figure 3.

Figure: Figure 3: Numerical validation of the rate of convergence predicted by Proposition 7. Dashed lines are our prediction from Proposition 7 and full lines are from simulations of the process using 10 000 particles. The proposal and target are two-dimensional Gaussians, with zero mean and covariance matrices that have a constant diagonal, equal to one for the proposal and 10 for the target. As expected, the predicted rate from Proposition 7 (in dashed red) matches the approximated upper bound from Theorem 3 (in dashed yellow) as well as particle-based simulations (full lines), for large values of time.
Refer to caption: extracted/5922458/image/linear_rate_validation.png

## Appendix D Lower bounds

In this section, we give the proofs of
Theorems 4, 8
and 9.
In section D.1
we prove a general lower bound in total variation for
the setup we consider in Theorems 8
and 9.
We apply this result to the bimodal example in section D.2.
We then study the unimodal
examples from Theorems 4 and 9
in section D.3.
The bound on the log-Sobolev constant for the uni-modal example
is deferred to section D.4.
Throughout, we use the notation introduced in section 5.

### D.1 A general lower bound

In this section we
state and prove the following general lower
bound for the geometric path; in the following
sections it is applied to obtain Theorems 8
and 9.

###### Theorem 20 (Total variation lower bounds for the geometric path)

Suppose $\nu,\pi\in\mathcal{P}_{\rm ac}(\mathbb{R})$
have log-Lipschitz densities
and there is an interval $I=[a,b]\subset\mathbb{R}$
and $\lambda_{\star}\in[0,1]$, $\delta,B>0$ such that:

- 1.
Bounded scores on $I$: both $|V_{\nu}^{\prime}(x)|,|V_{\pi}^{\prime}(x)|\leq B$ for $x\in I$.
- 2.
Small mass on $I$: for all
$\lambda\in[0,\lambda_{\star}],$ we have $\mu_{\lambda}(I)\leq\delta$.

Then for each $k\in[K]$ such that $\lambda_{k}\leq\lambda_{\star}$,

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([b,\infty))-\pi(I)-\nu([b,\infty))- \delta-\frac{B}{b-a}\cdot\sqrt{\delta}\cdot\Big{(}\sum_{i=1}^{k}T_{i}(\chi^{2} (p_{0}^{i},\mu_{i})+1)^{1/2}\Big{)}.$ $$

This result will be typically be
applied in conjuction with the following
lemma, which allows us to control the $\chi^{2}$ terms arising
above when we have pointwise comparisons
of one distribution to another.

###### Lemma 21

Suppose that there exists
a $C>0$ such that in the support
of $\pi$, $\nu(x)\leq C\pi(x)$. Then

$$ $\chi^{2}(p_{0}^{k},\mu_{k})\leq C^{\lambda_{k}}-1.$ $$

###### Proof of Lemma 21 .

Take $k\in[K]$. Write

$$ $\chi^{2}(p_{0}^{k},\mu_{k})=\int\frac{(p_{0}^{k})^{2}}{\mu_{k}}-1=\int\frac{(p _{0}^{k})^{2}}{\mu_{k-1}}\cdot\frac{\mu_{k-1}}{\mu_{k}}-1.$ $$

Now, letting $c_{i}:=c_{\lambda_{i}}$ for each $i\in\{0,\ldots,k\}$, we have

$$ $\frac{\mu_{k-1}}{\mu_{k}}=\frac{c_{k-1}}{c_{k}}\cdot\nu^{\lambda_{k}-\lambda_{ k-1}}\pi^{\lambda_{k-1}-\lambda_{k}}\leq C^{\lambda_{k}-\lambda_{k-1}}\cdot \frac{c_{k-1}}{c_{k}}.$ $$

Hence

$$ $\displaystyle\chi^{2}(p_{0}^{k},\mu_{k})$ $\displaystyle\leq C^{\lambda_{k}-\lambda_{k-1}}\cdot\frac{c_{k-1}}{c_{k}}\int \frac{(p_{0}^{k})^{2}}{\mu_{k-1}}-1$ $\displaystyle=C^{\lambda_{k}-\lambda_{k-1}}\cdot\frac{c_{k-1}}{c_{k}}\int\frac {(p_{T_{k-1}}^{k-1})^{2}}{\mu_{k-1}}-1.$ $$

But since $\chi^{2}(\cdot,\mu_{k-1})$
is non-increasing under Langevin dynamics towards $\mu_{k-1}$,
we find that

$$ $\chi^{2}(p_{0}^{k},\mu_{k})\leq C^{\lambda_{k}-\lambda_{k-1}}\cdot\frac{c_{k-1 }}{c_{k}}\int\frac{(p_{0}^{k-1})^{2}}{\mu_{k-1}}-1$ $$

Proceeding recursively, we obtain

$$ $\displaystyle\chi^{2}(p_{0}^{k},\mu_{k})$ $\displaystyle\leq C^{\lambda_{k}}\cdot\frac{c_{0}}{c_{k}}\int\frac{(p_{0}^{0}) ^{2}}{\mu_{0}}-1$ $\displaystyle=C^{\lambda_{k}}\cdot\frac{c_{0}}{c_{k}}-1=C^{\lambda_{k}}\cdot \frac{1}{c_{k}}-1\leq C^{\lambda_{k}}-1,$ $$

where at the last step we use the fact
that for all $\lambda\in[0,1]$, Cauchy-Schwarz implies that

$$ $\frac{1}{c_{\lambda}}=\int\nu^{1-\lambda}(x)\pi^{\lambda}(x)\mathrm{d}x\leq 1.$ $$

∎

###### Proof.

For convenience, let us put

$$ $V_{\lambda}(x):=-\log\mu_{\lambda}(x),\quad\quad\lambda\in[0,1].$ $$

Define

$$ $\psi(x):=\begin{cases}0&x<a\\ \frac{1}{b-a}(x-a)&x\in I\\ 1&x>b.\end{cases}$ $$

We write

$$ $\pi(\psi)-p_{T_{k}}^{k}(\psi)=\pi(\psi)-\nu(\psi)+\sum_{i=1}^{i}p_{T_{i-1}}^{i -1}(\psi)-p_{T_{i}}^{i}(\psi).$ $$

Observe

$$ $\pi(\psi)\geq\pi([b,\infty)).$ $$

On the other hand,

$$ $\nu(\psi)\leq\nu([a,\infty))=\nu(I)+\nu([b,\infty))\leq\delta+\nu([b,\infty)).$ $$

We thus find

$$ $\pi(\psi)-p_{T_{k}}^{k}(\psi)\geq\pi([b,\infty))-\nu([b,\infty))-\delta+\sum_{ i=1}^{k}p_{T_{i-1}}^{i-1}(\psi)-p_{T_{i}}^{i}(\psi).$ $$

To reduce to a lower bound in total variation,
we note that

$$ $\pi(\psi)-p^{k}_{T_{k}}(\psi)\leq\pi([a,\infty))-p^{k}_{T_{k}}([b,\infty))\leq \mathrm{TV}(p^{k}_{T_{k}},\pi)+\pi(I)$ $$

We finally obtain the lower bound

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([b,\infty))-\pi(I)-\nu([b,\infty))- \delta+\sum_{i=1}^{k}p_{T_{i-1}}^{i-1}(\psi)-p_{T_{i}}^{i}(\psi).$ (57) $$

To conclude from Eq. 57, we
study the above summands. Notice
that by definition, $p^{i-1}_{T_{i-1}}(\psi)=p^{i}_{0}(\psi)$, so that
these terms are the difference of the expectation
of $\psi$ at the start and end of Langevin dynamics
run towards $\mu_{i}.$
Hence,

$$ $p_{T_{k-1}}^{k-1}(\psi)-p_{T_{k}}^{k}(\psi)=-\int_{0}^{T_{k}}\partial_{t} \langle\psi,p_{t}^{k}\rangle_{L^{2}(\mu_{k})}\mathrm{d}t.$ $$

Now, $p_{t}^{k}$ evolves by the
weighted Fokker-Planck operator

$$ $\partial_{t}p_{t}^{k}=\mathcal{L}_{\mu_{k}}p_{t}^{k}:=\Delta p_{t}^{k}-\langle \nabla V_{\lambda_{k}},\nabla p_{t}^{k}\rangle,$ $$

so by self-adjointness of $\mathcal{L}_{\mu_{k}}$,
we obtain

$$ $\displaystyle\int_{0}^{T_{k}}\partial_{t}\langle\psi,p_{t}^{k}\rangle_{L^{2}( \mu_{k})}\mathrm{d}t$ $\displaystyle=\int_{0}^{T_{k}}\langle\psi,\mathcal{L}_{\mu_{k}}p_{t}^{k} \rangle_{L^{2}(\mu_{k})}\mathrm{d}t$ $\displaystyle=\int_{0}^{T_{k}}\langle\mathcal{L}_{\mu_{k}}\psi,p_{t}^{k} \rangle_{L^{2}(\mu_{k})}\mathrm{d}t.$ $$

Notice that since $\psi$ is linear where it is
non-constant,
we have

$$ $\mathcal{L}_{\mu_{k}}\psi(x)=-\langle\nabla V_{\lambda_{k}}(x),\nabla\psi(x) \rangle=\begin{cases}-\frac{1}{b-a}\partial_{x}V_{\lambda_{k}}(x)&x\in I\\ 0&x\not\in I.\end{cases}$ $$

Hence

$$ $\displaystyle\langle\mathcal{L}_{\mu_{k}}\psi,p_{t}^{k}\rangle_{L^{2}(\mu_{k})}$ $\displaystyle=\frac{-1}{b-a}\int_{a}^{b}\partial_{x}V_{\lambda_{k}}(x)p_{t}^{k }(x)\mathrm{d}\mu_{k}(x)$ $\displaystyle\leq\frac{B}{b-a}\int_{a}^{b}p_{t}^{k}(x)\mathrm{d}\mu_{k}(x).$ $$

Now, we use Cauchy-Schwarz to observe that

$$ $\displaystyle\int_{a}^{b}p_{t}^{k}(x)\mathrm{d}\mu_{k}(x)$ $\displaystyle\leq\mu_{k}(I)^{1/2}\Big{(}\int_{a}^{b}p_{t}^{k}(x)^{2}\mathrm{d} \mu_{k}(x)\Big{)}^{1/2}$ $\displaystyle\leq\mu_{k}(I)^{1/2}(\chi^{2}(p_{t}^{k},\mu_{k})+1)^{1/2}$ $\displaystyle\leq\sqrt{\delta}(\chi^{2}(p_{t}^{k},\mu_{k})+1)^{1/2}$ $\displaystyle\leq\sqrt{\delta}(\chi^{2}(p_{0}^{k},\mu_{k})+1)^{1/2},$ $$

where the last step follows because
$\chi^{2}(\cdot,\mu_{k})$ is non-increasing
along Langevin dynamics towards $\mu_{k}$.
Hence

$$ $p_{T_{k-1}}^{k-1}(\psi)-p_{T_{k}}^{k}(\psi)=-\int_{0}^{T_{k}}\langle\mathcal{L }_{\mu_{k}}\psi,p_{t}^{k}\rangle_{L^{2}(\mu_{k})}\geq-\frac{BT_{k}}{b-a}\sqrt{ \delta}(\chi^{2}(p_{0}^{k},\mu_{k})+1)^{1/2}.$ $$

Plugging this inequality into Eq. 57
yields the result.
∎

###### Theorem 20 (Total variation
lower bounds for the geometric path)

###### Lemma 21

###### Proof of Lemma 21 .

###### Proof.

### D.2 Lower bounds for bimodal target

In this section, we apply
the general lower bound
from Theorem 20
to prove Theorem 8,
and accordingly throughout take
$\nu$ and $\pi$
to be as defined there.
We begin by collecting some useful facts about the
geometric path between $\nu$ and $\pi$;
the proof is included
after that of Theorem 8.

###### Proposition 22 (Useful facts about the bi-modal example.)

Let $\nu,\pi$ be as in Theorem 8 for
$m\geq 11$.
Then

- 1.
for all $\lambda\in[0,1]$,
the normalizing constant $c_{\lambda}\in[1,2]$.
- 2.
for each $\lambda\in[0,1]$,
$\mu_{\lambda}([m/4,3m/4])\leq 6e^{-m^{2}/32}.$
- 3.
for all $k\in[K]$
and $t\in[0,T_{k}]$,
$\chi^{2}(p_{t}^{k},\mu_{k})\leq 1.$

###### Proof of Theorem 8 .

We will apply Theorem 20
with $I=[m/4,3m/4]$. An easy
calculation shows that we may take $B=2m$ for the first
assumption,
and Proposition 22
shows that $\lambda_{0}=1$ and $\delta=6e^{-m^{2}/32}$ suffice
for the second assumption.
We thus obtain

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([3m/4,\infty))-\nu([3m/4,\infty))-12e^{- m^{2}/32}-4\sqrt{6}\Big{(}\sum_{i=1}^{k}T_{i}(\chi^{2}(p_{0}^{i},\mu_{i})+1)^{ 1/2}\Big{)}e^{-m^{2}/64}.$ $$

Applying Proposition 22 to control
the $\chi^{2}$ terms yields

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([3m/4,\infty))-\nu([3m/4,\infty))-12e^{- m^{2}/32}-16\Big{(}\sum_{i=1}^{k}T_{i}\Big{)}e^{-m^{2}/32}$ $$

Note that by Mill’s ratio, we can bound using
$m\geq 4$ that

$$ $\nu([3m/4,\infty))\leq e^{-9m^{2}/32}\leq e^{-m^{2}/32}.$ $$

On the other hand,

$$ $\displaystyle\pi([3m/4,\infty))$ $\displaystyle=\pi([m/2,\infty))-\pi([m/2,3m/4])$ $\displaystyle\geq\pi([m/2,\infty))-\pi([m/4,3m/4])$ $\displaystyle=\frac{1}{2}-\pi([m/4,3m/4])$ $\displaystyle\geq\frac{1}{2}-6e^{-m^{2}/32},$ $$

where at the last step we applied Proposition 22
one more time.
Plugging in terms yields

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\frac{1}{2}-19e^{-m^{2}/32}-16\Big{(}\sum_{i =1}^{k}T_{i}\Big{)}e^{-m^{2}/32}.$ $$

Now, we use our assumption that $m\geq 11$
to observe that

$$ $\frac{1}{2}-19e^{-m^{2}/32}\geq\frac{1}{20},$ $$

and finally conclude.
∎

###### Proof of Proposition 22 .

Proof of Fact 1.
Note that Cauchy-Schwarz immediately implies
that for any $\lambda\in[0,1]$,

$$ $\frac{1}{c_{\lambda}}=\int\nu^{1-\lambda}\pi^{\lambda}\leq 1.$ $$

On the other hand, using the fact that $2\pi\geq\nu$,
we have that

$$ $\frac{1}{c_{\lambda}}=\int\nu^{1-\lambda}\pi^{\lambda}=\int\big{(}\frac{\pi}{ \nu}\big{)}^{\lambda}\nu\geq 2^{-\lambda}\geq\frac{1}{2}.$ $$

The claim about the normalizing
constant follows.

Proof of Fact 2.
We use the previous part
to observe

$$ $\displaystyle\mu_{\lambda}([m/4,3m/4])$ $\displaystyle\leq 2\int_{m/4}^{3m/4}\nu^{1-\lambda}(x)\pi^{\lambda}(x)\mathrm{ d}x$ $\displaystyle\leq 2\nu([m/4,3m/4])^{1-\lambda}\pi([m/4,3m/4])^{\lambda}$ $\displaystyle=2\nu([m/4,3m/4]),$ $$

where the last equality follows by symmetry.
We then observe that by Mills’ ratio,

$$ $\nu([m/4,3m/4])\leq\nu([m/4,\infty))\leq 3e^{-m^{2}/32}.$ $$

The result follows.

Proof of Fact 3. The result follows immediately
from Lemma 21 once
we observe that $\nu\leq 2\pi$.
∎

###### Proposition 22 (Useful facts about the
bi-modal example.)

###### Proof of Theorem 8 .

###### Proof of Proposition 22 .

### D.3 Lower bounds for unimodal target

In this section, we prove Theorem 4
as well as Theorem 9.
Since these results concern the same
distributions with different mixture weights,
in this section we generalize slightly to consider,
for some $a\in[\sqrt{2\log 2}/m,1]$, the target

$$ $\pi=(1-e^{-a^{2}m^{2}/2})\mathcal{N}(m,1)+e^{-a^{2}m^{2}/2}u_{m},$ (58) $$

By taking $a=1/\sqrt{2}$, we
recover the setting of Theorem 4,
and by taking $a=\sqrt{2\log 2}/m$
we recover the setting of Theorem 9.
Note that when dealing with various
numerical constants, we will
frequently use the assumption $m\geq 10$
without comment.
For both results, the following facts
will be useful.

###### Proposition 23 (Useful facts about the unimodal target)

Let $\nu:=\mathcal{N}(0,1)$
and $\pi$ be as in Eq. 58
for $m\geq 10$.
Then

- 1.
For all $\lambda\in[0,1]$,
$\mu_{\lambda}([m(1-a)/2,m(1-a)])\leq 5am^{2}c_{\lambda}e^{-\lambda a^{2}m^{2}/
2-(1-\lambda)(1-a)^{2}m^{2}/8}.$
- 2.
If $1\geq a+2/m$,
then for all $\lambda\in[0,1]$,
$\mu_{\lambda}((-\infty,m(1-a)/2])\geq\frac{c_{\lambda}e^{-\lambda a^{2}m^{2}/2
}}{10m}.$
- 3.
For all $\lambda$ such that
$1\leq a+2\lambda-2/m$, we have
$\mu_{\lambda}([m(1-a)/2,\infty))\geq\frac{c_{\lambda}}{2}e^{-\frac{1}{2}
\lambda(1-\lambda)m^{2}}.$
- 4.
For all $\lambda\in[0,1]$
$\frac{1}{4(e^{-\lambda a^{2}m^{2}/2}+e^{-\frac{1}{2}\lambda(1-\lambda)m^{2}})}
\leq c_{\lambda}\leq 10me^{\lambda a^{2}m^{2}/2}.$

We also use the following.

###### Lemma 24 (Log-Sobolev constants of the unimodal target.)

Let $\pi$ be as in Eq. 58
for $m\geq 10$.
Then

$$ $C_{\mathrm{LS}}(\pi)\leq\frac{81a^{2}m^{5}}{1-2e^{-a^{2}m^{2}/2}},$ $$

with the convention that the right-hand side is $324m^{3}$
when $a=\sqrt{2\log 2}/m$.

The proof of Lemma 24
requires a digression into log-Sobolev inequalities
for mixtures and restrictions, so is deferred to the next section,
Appendix D.4.

We first prove Theorems 4
and 9,
then return to proving Proposition 23.

###### Proof of Theorem 4 .

The fact that
$C_{LS}(\nu)=1$ is the Gaussian log-Sobolev inequality,
and the bound $C_{LS}(\pi)\leq 6m^{5}$ follows immediately
from Lemma 24 upon plugging in $a=1/\sqrt{2}$.

For the lower bound on $C_{P}(\mu_{\lambda})$,
take $\lambda\in[\frac{1}{2},1]$ and
let $I:=[m(1-a)/2,m(1-a)]$;
recall that $a\in[0,1)$ is a free
parameter controlling the mixture weights in Eq. 58.
Put

$$ $\psi(x):=\begin{cases}1&x<m(1-a)/2,\\ 1-\frac{2}{(1-a)m}(x-m(1-a)/2)&x\in I,\\ 0&x>m(1-a).\end{cases}$ $$

Then

$$ $\|\nabla\psi\|^{2}_{L^{2}(\mu_{\lambda})}=\frac{4}{m^{2}(1-a)^{2}}\mu_{\lambda }(I).$ $$

On the other hand,

$$ $\displaystyle\mathrm{Var}_{\mu_{\lambda}}(\psi)$ $\displaystyle=\mu_{\lambda}(\psi^{2})-\mu_{\lambda}(\psi)^{2}$ $\displaystyle\geq\mu_{\lambda}((-\infty,m(1-a)/2])-(\mu_{\lambda}((-\infty,m(1 -a)/2])+\mu_{\lambda}(I))^{2}$ $\displaystyle=\mu_{\lambda}((-\infty,m(1-a)/2])(1-\mu_{\lambda}((-\infty,m(1-a )/2])))$ $\displaystyle-2\mu_{\lambda}(I)\mu_{\lambda}((-\infty,m(1-a)/2])-\mu_{\lambda} (I)^{2}$ $\displaystyle\geq\mu_{\lambda}((-\infty,m(1-a)/2])(1-\mu_{\lambda}((-\infty,m( 1-a)/2])))-3\mu_{\lambda}(I)$ $\displaystyle=\mu_{\lambda}((-\infty,m(1-a)/2])\mu_{\lambda}([m(1-a)/2,\infty) )-3\mu_{\lambda}(I)$ $$

We obtain

$$ $\displaystyle C_{P}(\mu_{\lambda})\geq\frac{\mathrm{Var}_{\mu_{\lambda}}(\psi) }{\|\nabla\psi\|^{2}_{L^{2}(\mu_{\lambda})}}$ $\displaystyle=\frac{m^{2}(1-a)^{2}}{4}\mu_{\lambda}(I)^{-1}\mu_{\lambda}((- \infty,m(1-a)/2])\mu_{\lambda}([m(1-a)/2,\infty))-\frac{3m^{2}(1-a)^{2}}{4}.$ (59) $$

We’ll
now apply Proposition 23
with $a=1/\sqrt{2}$. With this choice
of $a$ and for $\lambda\in[\frac{1}{2},1]$,
the sufficient conditions are all verified,
so that

$$ $\displaystyle\mu_{\lambda}(I)^{-1}\mu_{\lambda}((-\infty,m(1-a)/2])\mu_{ \lambda}([m(1-a)/2,\infty))\geq\frac{1}{100am^{3}}c_{\lambda}e^{(1-\lambda)m^{ 2}(1-a)^{2}/8-\frac{1}{2}\lambda(1-\lambda)m^{2}}.$ $$

Applying Proposition 23
once more, this time
to control $c_{\lambda}$,
we obtain

$$ $\mu_{\lambda}(I)^{-1}\mu_{\lambda}((-\infty,m(1-a)/2])\mu_{\lambda}([m(1-a)/2, \infty))\geq\frac{e^{(1-\lambda)m^{2}(1-a)^{2}/8-\frac{1}{2}\lambda(1-\lambda) m^{2}}}{400am^{3}(e^{-\lambda a^{2}m^{2}/2}+e^{-\frac{1}{2}\lambda(1-\lambda)m ^{2}})}.$ $$

To complete the proof of
Theorem 4,
we finally plug in $a=1/\sqrt{2}$,
and observe that
for $\lambda\in[\frac{1}{2},1]$ it holds that
$e^{-\lambda a^{2}m^{2}/2}\leq e^{-\frac{1}{2}\lambda(1-\lambda)m^{2}}$,
so that

$$ $\mu_{\lambda}(I)^{-1}\mu_{\lambda}((-\infty,m(1-a)/2])\mu_{\lambda}([m(1-a)/2, \infty))\geq\frac{1}{800m^{3}}e^{(1-\lambda)m^{2}/100}.$ $$

Plugging into Eq. 59
we find

$$ $C_{P}(\mu_{\lambda})\geq\frac{m^{2}(1-1/\sqrt{2})^{2}}{4}\Big{(}\frac{1}{800m^ {3}}e^{(1-\lambda)m^{2}/100}-3\Big{)}.$ $$

Observe that $\frac{1}{12}\leq(1-1/\sqrt{2})^{2}\leq 1$, so that

$$ $C_{P}(\mu_{\lambda})\geq\frac{1}{48\cdot 800m}e^{(1-\lambda)m^{2}/100}-\frac{3 m^{2}}{4}\geq\frac{1}{4\cdot 10^{4}m}e^{(1-\lambda)m^{2}/100}-m^{2}.$ $$

∎

###### Proof of Theorem 9 .

The equality $C_{LS}(\nu)=1$ is the Gaussian
log-Sobolev inequality. For the log-Sobolev constant
of $\pi$, the result is immediate from Lemma 24
upon plugging in $a=\sqrt{2\log 2}/m$.

For the lower bound in total variation,
we will apply Theorem 20
using the interval $I=[m(1-a)/2,m(1-a)]$;
recall that $a\in[0,1)$ is a free
parameter controlling the mixture weights in Eq. 58
that we will eventually set
to $a=\sqrt{2\log 2}/m$.

In this case, it clear that we may bound
the scores with $B=m$.
The main issue
is then to get control on $\mu_{\lambda}(I)$,
and for this we apply Proposition 23
to obtain

$$ $\mu_{\lambda}(I)\leq 50am^{3}e^{-(1-\lambda)(1-a)^{2}m^{2}/8}.$ $$

So for $\lambda_{\star}:=\lambda_{k}$, we may take

$$ $\delta:=50am^{3}e^{-(1-\lambda_{\star})(1-a)^{2}m^{2}/8}.$ $$

Theorem 20
then implies

$$ $\displaystyle\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([m(1-a),\infty))-$ $\displaystyle\pi([m(1-a)/2,m(1-a)])-\nu([m(1-a),\infty))-\delta$ $\displaystyle-\frac{2}{1-a}\cdot\sqrt{\delta}\cdot\Big{(}\sum_{i=1}^{k}T_{i}( \chi^{2}(p_{0}^{i},\mu_{i})+1)^{1/2}\Big{)}.$ $$

Next, we observe that $4mu_{m}(x)\geq\nu(x)$ for all $x\in\mathbb{R}$, so that

$$ $\pi(x)\geq\frac{1}{2}u_{m}(x)\geq\frac{1}{8m}\nu(x).$ $$

Hence we may Lemma 21 with $C=8m$
to obtain

$$ $\displaystyle\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\pi([m(1-a),\infty))-$ $\displaystyle\pi([m(1-a)/2,m(1-a)])-\nu([m(1-a),\infty))$ $\displaystyle-\delta-\frac{8\sqrt{m}}{1-a}\cdot\sqrt{\delta}\cdot\Big{(}\sum_{ i=1}^{k}T_{i}\Big{)}.$ $$

Let us specialize to $a=\sqrt{2\log 2}/m$.
In this case, Mills’ ratio implies

$$ $\nu([m(1-a),\infty))\leq e^{-(1-a)^{2}m^{2}/2}\leq e^{-2m^{2}/5}.$ $$

For the other two terms, let us adopt
the notation $g_{m}:=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}(x-m)^{2}}$,
and then write

$$ $\displaystyle\pi([m(1-a),\infty))-$ $\displaystyle\pi([m(1-a)/2,m(1-a)])$ $\displaystyle\geq\int_{m(1-a)}^{2m}\big{(}\frac{1}{2}g_{m}(x)+\frac{1}{2}u_{m} (x))\mathrm{d}x-\int_{m(1-a)/2}^{m(1-a)}\big{(}\frac{1}{2}g_{m}(x)+\frac{1}{2} u_{m}(x)\big{)}\mathrm{d}x$ $\displaystyle=\frac{1}{2}\int_{m(1-a)}^{2m}g_{m}(x)\mathrm{d}x-\frac{1}{2}\int _{m(1-a)/2}^{m(1-a)}g_{m}(x)\mathrm{d}x+\frac{1}{2}\int_{m(1-a/2)}^{2m}u_{m}(x )\mathrm{d}x$ $\displaystyle\geq\frac{1}{2}\int_{m(1-a)}^{2m}g_{m}(x)\mathrm{d}x-\frac{1}{2} \int_{m(1-a)/2}^{m(1-a)}g_{m}(x)\mathrm{d}x$ $\displaystyle=\int_{m(1-a)}^{m(1+a)}g_{m}(x)\mathrm{d}x\geq\int_{m-1}^{m+1}g_{ m}(x)\geq\frac{1}{4}.$ $$

We finally obtain

$$ $\mathrm{TV}(p^{k}_{T_{k}},\pi)\geq\frac{1}{4}-e^{-2m^{2}/5}-\delta-10m\cdot \sqrt{\delta}\cdot\Big{(}\sum_{i=1}^{k}T_{i}\Big{)}.$ $$

For this choice of $a$,
note that

$$ $\delta\leq 6m^{3}e^{-(1-\lambda_{k})m^{2}/10}.$ $$

By the restriction on $m$ we know
$1/4-e^{-2m^{2}/5}\geq 1/5$, yielding the result.
∎

###### Proof of Prop. 23 .

For ease of notation, let us write $g_{m}(x):=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}(x-m)^{2}}$.
Also, put $u_{m}(x)=c_{u_{m}}e^{-\frac{1}{2}d(x,I_{m})^{2}}$
for $c_{u_{m}}$ a normalizing constant and observe that

$$ $c_{u_{m}}^{-1}=\int_{-\infty}^{\infty}e^{-\frac{1}{2}d(x,I_{m})^{2}}\mathrm{d} x=3m+\sqrt{2\pi}\implies\frac{1}{4m}\leq c_{u_{m}}\leq\frac{1}{3m}.$ $$

Therefore,

$$ $e^{-a^{2}m^{2}/2}u_{m}(x)\leq\frac{e^{-a^{2}m^{2}/2}}{3m}\leq\frac{1}{m}g_{m}( x),\quad\quad\forall x\in[m(1-a),m(1+a)],$ (60) $$

and

$$ $g_{m}(x)\leq e^{-a^{2}m^{2}/2}\leq 4me^{-a^{2}m^{2}/2}u_{m}(x)\quad\quad \forall x\in[-m,m(1-a)]\cup[m(1+a),2m].$ (61) $$

Proof of Fact 1.
We use Eq. 61
to observe that

$$ $\displaystyle\mu_{\lambda}([m(1-a)/2,m(1-a)])$ $\displaystyle=c_{\lambda}\int_{m(1-a)/2}^{m(1-a)}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle\leq c_{\lambda}(5m)^{\lambda}e^{-\lambda a^{2}m^{2}/2}\int_{m(1- a)/2}^{m(1-a)}\nu^{1-\lambda}$ $\displaystyle\leq 5am^{2}c_{\lambda}e^{-\lambda a^{2}m^{2}/2}\cdot e^{-(1- \lambda)m^{2}(1-a)^{2}/8}.$ $$

Proof of Fact 2.
We compute

$$ $\displaystyle\mu_{\lambda}((-\infty,m(1-a)/2])$ $\displaystyle=\int_{-\infty}^{m(1-a)/2}c_{\lambda}\nu^{1-\lambda}\pi^{\lambda} \mathrm{d}x$ $\displaystyle\geq c_{\lambda}\int_{-m(1-a)/2}^{m(1-a)/2}\nu^{1-\lambda}\pi^{ \lambda}\mathrm{d}x$ $\displaystyle\geq c_{\lambda}\Big{(}\frac{e^{-a^{2}m^{2}/2}}{4m}\Big{)}^{ \lambda}\Big{(}\frac{1}{\sqrt{2\pi}}\Big{)}^{1-\lambda}\int_{-m(1-a)/2}^{m(1-a )/2}e^{-\frac{1}{2}x^{2}(1-\lambda)}\mathrm{d}x$ $\displaystyle\geq c_{\lambda}\frac{e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m} \int_{-m(1-a)/2}^{m(1-a)/2}e^{-\frac{1}{2}x^{2}(1-\lambda)}\mathrm{d}x$ $\displaystyle\geq c_{\lambda}\frac{e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m} \int_{-m(1-a)/2}^{m(1-a)/2}e^{-\frac{1}{2}x^{2}}\mathrm{d}x$ $\displaystyle\geq c_{\lambda}\frac{e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m} \int_{-1}^{1}e^{-\frac{1}{2}x^{2}}\mathrm{d}x$ $\displaystyle\geq c_{\lambda}\frac{2e^{-1/2}e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{ 2\pi}m}$ $\displaystyle\geq\frac{c_{\lambda}e^{-\lambda a^{2}m^{2}/2}}{10m}.$ $$

Proof of Fact 3.
We calculate,

$$ $\displaystyle\mu_{\lambda}([m(1-a)/2,\infty))$ $\displaystyle=\int_{m(1-a)/2}^{\infty}c_{\lambda}\nu^{1-\lambda}\pi^{\lambda} \mathrm{d}x$ $\displaystyle\geq\frac{c_{\lambda}}{2}\int_{m(1-a)/2}^{2m}\frac{1}{\sqrt{2\pi} }e^{-\frac{1}{2}(1-\lambda)x^{2}-\frac{1}{2}\lambda(x-m)^{2}}\mathrm{d}x$ $\displaystyle=\frac{c_{\lambda}}{2}e^{-\frac{1}{2}\lambda(1-\lambda)m^{2}}\int _{m(1-a)/2}^{2m}\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}(x-\lambda m)^{2}}\mathrm{ d}x$ $\displaystyle\geq\frac{c_{\lambda}}{2}e^{-\frac{1}{2}\lambda(1-\lambda)m^{2}},$ $$

where we used the
fact that under the hypothesis, we have $m(1-a)/2\leq\lambda m-1$.

Proof of Fact 4.
We compute

$$ $\displaystyle\frac{1}{c_{\lambda}}=\int_{-\infty}^{\infty}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle\geq\frac{1}{(2\pi)^{(1-\lambda)/2}}\cdot\Big{(}\frac{e^{-a^{2}m^ {2}/2}}{4m}\Big{)}^{\lambda}\cdot\int_{-m/2}^{m/2}e^{-\frac{1}{2}x^{2}(1- \lambda)}\mathrm{d}x$ $\displaystyle\geq\frac{e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m}\int_{-m/2}^{m /2}e^{-\frac{1}{2}x^{2}(1-\lambda)}\mathrm{d}x$ $\displaystyle\geq\frac{e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m}\int_{-m/2}^{m /2}e^{-\frac{1}{2}x^{2}}\mathrm{d}x$ $\displaystyle\geq\frac{2e^{-1/2}e^{-\lambda a^{2}m^{2}/2}}{4\sqrt{2\pi}m}$ $\displaystyle\geq\frac{e^{-\lambda a^{2}m^{2}/2}}{10m}.$ $$

On the other hand,
we use Eq. 60
and Eq. 61
to bound

$$ $\displaystyle\frac{1}{c_{\lambda}}$ $\displaystyle=\int_{-\infty}^{\infty}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle=\int_{-m}^{m(1-a)}\nu^{1-\lambda}\pi^{\lambda}+\int_{m(1-a)}^{m( 1+a)}\nu^{1-\lambda}\pi^{\lambda}+\int_{m(1+a)}^{2m}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle+\int_{-\infty}^{-m}\nu^{1-\lambda}\pi^{\lambda}+\int_{2m}^{ \infty}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle\leq 2\int_{-m}^{m(1-a)}\nu^{1-\lambda}\pi^{\lambda}+\int_{m(1-a) }^{m(1+a)}\nu^{1-\lambda}\pi^{\lambda}+\int_{-\infty}^{-m}\nu^{1-\lambda}\pi^{ \lambda}+\int_{2m}^{\infty}\nu^{1-\lambda}\pi^{\lambda}$ $\displaystyle\leq 2\Big{(}\frac{5e^{-am^{2}/2}}{3}\Big{)}^{\lambda}\cdot\frac{ 1}{(2\pi)^{(1-\lambda)/2}}\int_{-m}^{m(1-a)}e^{-\frac{1}{2}(1-\lambda)x^{2}} \mathrm{d}x$ $\displaystyle+\frac{2^{\lambda}}{\sqrt{2\pi}}\int_{m(1-a)}^{m(1+a)}e^{-\frac{1 }{2}(1-\lambda)x^{2}-\frac{1}{2}\lambda(x-m)^{2}}\mathrm{d}x+\int_{-\infty}^{- m}\nu^{1-\lambda}+\int_{2m}^{\infty}\nu^{1-\lambda}$ $\displaystyle\leq 4e^{-\lambda a^{2}m^{2}/2}+\frac{2}{\sqrt{2\pi}}e^{-\frac{1} {2}\lambda(1-\lambda)m^{2}}\int_{-\infty}^{\infty}e^{-\frac{1}{2}(x-\lambda m) ^{2}}\mathrm{d}x+\frac{2}{\sqrt{2\pi}}\int_{-\infty}^{-m}e^{-\frac{1}{2}x^{2}} \mathrm{d}x$ $\displaystyle\leq 4e^{-\lambda a^{2}m^{2}/2}+2e^{-\frac{1}{2}\lambda(1-\lambda )m^{2}}+e^{-\frac{1}{2}m^{2}}$ $\displaystyle\leq 4(e^{-\lambda a^{2}m^{2}/2}+e^{-\frac{1}{2}\lambda(1-\lambda )m^{2}}).\qed$ $$

###### Proposition 23 (Useful facts about the
unimodal target)

###### Lemma 24 (Log-Sobolev constants
of the unimodal target.)

###### Proof of Theorem 4 .

###### Proof of Theorem 9 .

###### Proof of Prop. 23 .

### D.4 Upper bounds on the log-Sobolev
constant of the unimodal target

In this section we prove Lemma 24
on the log-Sobolev constant of the unimodal target
defined in Eq. 17.
We use the following result which controls
the log-Sobolev constants of mixtures,
and appears as [, Corollary 2].

###### Theorem 25 (Upper bounds on log-Sobolev constant of mixtures [ 63 ] )

Suppose $Q_{0},Q_{1}\in\mathcal{P}(\mathbb{R}^{d})$
are such that $Q_{0}\ll Q_{1}$. For $p\in[0,1]$,
consider the mixture $Q_{p}:=pQ_{0}+(1-p)Q_{1}$.
Then

$$ $C_{LS}(Q_{p})\leq\max\big{\{}(1+(1-p)\lambda_{p})C_{LS}(Q_{0}),(1+p\lambda_{p} (1+\chi^{2}(Q_{0},Q_{1})))C_{LS}(Q_{1})\big{\}},$ $$

for

$$ $\lambda_{p}:=\begin{cases}\frac{\log p-\log(1-p)}{2p-1}&p\in[0,\frac{1}{2}) \cup(\frac{1}{2},1]\\ 2&p=\frac{1}{2}.\end{cases}$ $$

With this result in hand, we just need to get control on the
the log-Sobolev constant of $u_{m}$.
This is accomplished in the following lemma.

###### Lemma 26 (Log-Sobolev constant of $u_{m}$ )

We have

$$ $C_{LS}(u_{m})\leq 16m^{2}.$ $$

###### Proof of Lemma 26 .

We will apply the Holley-Stroock perturbation principle to a custom
comparison distribution.
Indeed, for a parameter $r>0$ to be chosen later, let

$$ $\phi_{r}(x):=\begin{cases}\frac{1}{2}(x-2m)^{2}&x>2m+r\\ \alpha_{r}\big{(}x-\frac{m}{2}\big{)}^{2}+\delta_{r}&x\in[-m-r,2m+r]\\ \frac{1}{2}(x+m)^{2}&x<-m-r,\end{cases}$ $$

where we take $\alpha_{r},\delta_{r}$ to make $\phi$ continuously
differentiable; in particular

$$ $\alpha_{r}:=\frac{r}{2r+3m},\quad\quad\delta_{r}:=-\frac{3mr^{2}}{8}.$ $$

Note that $\phi_{r}$ is $\alpha_{r}$ strongly convex, so that
$C_{LS}(e^{-\phi_{r}})\leq\frac{1}{\alpha_{r}}$. On the other hand

$$ $\delta_{r}-\frac{1}{2}r^{2}\leq\phi_{r}-\frac{1}{2}d(x,I_{m})^{2}\leq\alpha_{r }\big{(}\frac{3m}{2}+r\big{)}^{2}+\delta_{r}.$ $$

Hence

$$ $\mathrm{osc}(\phi-\frac{1}{2}d(\cdot,I_{m})^{2})\leq\alpha_{r}\big{(}\frac{3m} {2}+r\big{)}^{2}+\frac{r^{2}}{2}.$ $$

Hence by the Holley-Stroock perturbation principle []
we know that

$$ $C_{LS}(u_{m})\leq\exp\big(\alpha_{r}\big{(}\frac{3m}{2}+r\big{)}^{2}+\frac{r^{ 2}}{2}\big{missing})C_{LS}(e^{-\phi_{r}})\leq\frac{1}{\alpha_{r}}\cdot\exp\big (\alpha_{r}\big{(}\frac{3m}{2}+r\big{)}^{2}+\frac{r^{2}}{2}\big{missing}).$ $$

Taking $r=1/m$, we find

$$ $C_{LS}(u_{m})\leq(2+3m^{2})\exp\big(\frac{1}{3m^{2}}(2m)^{2}+\frac{1}{2m^{2}} \big{missing})=(2+3m^{2})\exp\big(\frac{4}{3}+\frac{1}{2m^{2}}\big{missing}) \leq 16m^{2}.$ $$

∎

With the result in hand, we can prove Lemma 24.

###### Proof of Lemma 24 .

We first compute $\chi^{2}(\mathcal{N}(m,1),u_{m})$. For this,
let us write $u_{m}=c_{u_{m}}e^{-\frac{1}{2}d^{2}(x,I_{m})}$,
and note that

$$ $c_{u_{m}}^{-1}=\int_{\infty}^{\infty}e^{-\frac{1}{2}d^{2}(x,I_{m})}\mathrm{d}x =\sqrt{2\pi}+3m\leq 4m.$ $$

Hence

$$ $\displaystyle\chi^{2}(\mathcal{N}(m,1),u_{m})+1$ $\displaystyle\leq\frac{2m}{\pi}\int_{-\infty}^{\infty}e^{-(x-m)^{2}+\frac{1}{2 }d(x,I_{m})^{2}}\mathrm{d}x$ $\displaystyle=\frac{2m}{\pi}\int_{-\infty}^{-m}e^{-(x-m)^{2}+\frac{1}{2}d(x,I_ {m})^{2}}\mathrm{d}x+\frac{2m}{\pi}\int_{-m}^{2m}e^{-(x-m)^{2}+\frac{1}{2}d(x, I_{m})^{2}}\mathrm{d}x$ $\displaystyle+\frac{2m}{\pi}\int_{2m}^{\infty}e^{-(x-m)^{2}+\frac{1}{2}d(x,I_{ m})^{2}}\mathrm{d}x$ $\displaystyle=\frac{2m}{\pi}\int_{-\infty}^{-m}e^{-(x-m)^{2}+\frac{1}{2}(x+m)^ {2}}\mathrm{d}x+\frac{2m}{\pi}\int_{-m}^{2m}e^{-(x-m)^{2}}\mathrm{d}x$ $\displaystyle+\frac{2m}{\pi}\int_{2m}^{\infty}e^{-(x-m)^{2}+\frac{1}{2}(x-2m)^ {2}}\mathrm{d}x$ $\displaystyle\leq\frac{2m}{\pi}\int_{-\infty}^{-m}e^{-\frac{1}{2}(x-m)^{2}} \mathrm{d}x+\frac{2m}{\pi}\int_{-\infty}^{\infty}e^{-(x-m)^{2}}\mathrm{d}x$ $\displaystyle+\frac{2m}{\pi}\int_{2m}^{\infty}e^{-\frac{1}{2}(x-m)^{2}}\mathrm {d}x$ $\displaystyle\leq\frac{2m}{\pi}\big{(}\sqrt{2\pi}+\sqrt{\pi}+\sqrt{2\pi}\big{) }\leq 5m.$ $$

Using Lemma 26
and
plugging into Theorem 25,
with $p=1-e^{-a^{2}m^{2}/2}$,
we find

$$ $\displaystyle C_{LS}(\pi)$ $\displaystyle\leq\max\big{\{}1+(1-p)\lambda_{p},80m^{3}(1+p\lambda_{p})\big{\} }\leq 162m^{3}\lambda_{p}.$ $$

The result follows.
∎

###### Theorem 25 (Upper bounds on log-Sobolev constant of mixtures [ 63 ] )

###### Lemma 26 (Log-Sobolev constant of u m subscript 𝑢 𝑚 u_{m} italic_u start_POSTSUBSCRIPT italic_m end_POSTSUBSCRIPT )

###### Proof of Lemma 26 .

###### Proof of Lemma 24 .

## Appendix E Additional numerical illustrations

The geometric path is often illustrated in a setup where the initialization is chosen in the middle of a two symmetric modes: see for example Cabezas et al., [, Sampling Book, Tempered SMC] or Maurais and Marzouk, [, Fig. 1] or Chehab et al., [, Fig. 1]. In this very specific setting, the geometric path conveys a sense that it evolves particle positions. In a more general setting, we can observe in Figure 4 that once the closer mode is reached, the path seems to evolve the particle weights, which is problematic for Langevin dynamics.

Figure: Figure 4: Geometric path from a Gaussian to a Gaussian mixture. We observe that that this path displaces mass “horizontally” to the nearest modes (left columns), and then “vertically” to the remaining modes (right columns). Intuitively, this second part is problematic for a Langevin sampler.
Refer to caption: extracted/5922458/image/geometric_path_bimodal_vis.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: * I believe for $KL(p_0, \mu_0)$ to disappear in Corollary 5, one needs to set $\lambda_0 = 0$. In that case, it would not be possible to choose $\lambda_t = 1$ for all $t > 0$ in a continuous manner.

* If all $\lambda_i$s are very close to 1 in Theorem 9, we are effectively running vanilla Langevin. In that case, why should we have exponential convergence time?

* The vanilla Langevin analysis only requires the log-Sobolev inequality and smoothness for discretization. Why do we additionally need dissipativity of proposal and target measures here?

    * In fact, the Langevin algorithm is known to convergence under extremely mild conditions, namely a weak Poincaré inequality (which holds for all locally bounded potentials, although without explicit control on the constant) and smoothness of the gradients, see e.g. [1] and references therein. Are there major challenges for obtaining convergence guarantees under (weak) Poincaré inequalities for the tempered Langevin algorithm? 

* Is there a sense in which one can choose optimal proposal distributions $\nu$ when we only know some information about $\pi$?

* I believe a summation over $i$ is missing in Equation (12).

* Some typos:
    * Line 152 missing absolute continuity before “... and $+\infty$ otherwise”.
    * Line 175: potential -> potentials
    * Line 119, 233, 253, 467: missing parentheses in citation
    * Line 238: satisfy -> satisfies
    * Line 336, 339, 383: section … -> Section …
    * Line 420: are unknown -> is unknown
    * Line 425: where we obtain
    * A typo in Line 439 makes the sentence unreadable.




---
[1] A. Mousavi-Hosseini, T. Farghly, Y. He, K. Balasubramanian, M. A. Erdogdu. "Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality". COLT 2023.
soundness: 3
strengths: While I am not an expert in annealing or tempering algorithms for sampling, it seems that this is the first paper that proves the convergence of geometric tempering for the Langevin diffusion using functional inequalities, which is interesting. The negative results also provide a good example of why tempering may not work in practice, despite both proposal and target measures having suitable isoperimetry.
summary: This work studies the convergence guarantee of geometric tempering for the Langevin diffusion and its time-discretization the Langevin algorithm. The authors prove a convergence rate under a general tempering schedule, demonstrating dependency on the isoperimetry of the intermediate probability measures, in particular their log-Sobolev constant. While this constant can be suitably controlled when both measures are strongly log-concave, the authors show that even when both proposal and target densities are unimodal, intermediate measures can suffer from a poor log-Sobolev constant that scales exponentially with the distance between the modes of proposal and target measures.
weaknesses: * The related work section could be better structured. For example, breaking into multiple paragraphs and adding paragraph titles could help with readability and following the discussion.
* The lower bound examples hold in dimension 1, and show exponentially bad dependence on the distance between modes. While these bounds are interesting, it is not very intuitive to me why it would be natural for the distance between modes to grow in fixed dimensions. On the other hand, in a high-dimensional setting, it is more intuitive that $m$ grows with square root of dimension. Could it be straightforward to (perhaps only intuitively) extend the lower bounds to high-dimensional settings?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see question abobe
soundness: 3
strengths: Perhaps surprisingly, the paper's findings are largely negative regarding the effectiveness of geometric tempering. The authors demonstrate that geometric tempering can actually worsen functional inequalities exponentially, even when both the proposal and target distributions have favorable properties. Through theoretical analysis, they show a simple bimodal case where geometric tempering takes exponential time to converge. More strikingly, they prove that similar poor convergence results can occur even with unimodal target distributions that have good functional inequalities. These results suggest that geometric tempering may not only fail to help with convergence but could actually be harmful in some cases, challenging the conventional wisdom about its utility.
summary: This paper presents a theoretical analysis of geometric tempering when applied to Langevin dynamics, a popular sampling method in machine learning and statistics. Geometric tempering is a technique that attempts to improve sampling from complex multi-modal distributions by sampling from a sequence of intermediate distributions that interpolate between an easy-to-sample proposal distribution and the target distribution. The authors provide the first convergence analysis under functional inequalities, proving both upper and lower bounds for tempered Langevin dynamics in continuous and discrete time. They also derive optimal tempering schedules for certain pairs of proposal and target distributions.
weaknesses: In this paper they consider targets of the form $\nu^{1 - \lambda} \pi^{\lambda}$, where $\nu$ is called the proposal. In many other prior works, the targets are of the form $\pi^{\lambda}$, which corresponds to $\nu$ being an improper uniform distribution. This seems to be the main source of the largely negative results provided in this paper. Could the authors clarify the reason for considering target the above form?

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: The following suggestions relate to minor areas of the paper:

In Figure 2, should we not be scaling the $y$-axis logarithmically for a more reasonable demonstration?

The comment after (3) is strange. Probably, you mean to take $kh = t$ for a fixed choice of $t \in \mathbb R$, and then some schedule $h = t/K$ for a set of integers $K$, rather than what is written.

There is a spacing issue in Line 190~191.

Line 240: Lebesgue -> Lebesgue measure.

Line 425: where obtain-> where we obtain

It is a bit strange to cite Durmus 2019 for the Langevin rate in the str. convex + smooth setting, compared to earlier work such as [1].

Durmus, Alain, and Eric Moulines. "High-dimensional Bayesian inference via the unadjusted Langevin algorithm." (2019): 2854-2882.
soundness: 4
strengths: The main positive result on geometric tempering (Theorem 3) seems quite thorough (in that it comprises every reasonable regime of interest) and about as good as one could hope for in this context.

The negative example is very intuitive and is a worthwhile inclusion into the paper. It offers a good characterization about why one might be skeptical about the occasional poor performance of these schemes in practice, and gives good intuition about the heart of the problem (the appearance of multimodality).

The inclusion of more concrete lower bounds is also insightful.
summary: This paper offers a thorough study of geometric tempering combined with a Langevin MCMC scheme. In particular, a general theory is given which characterizes the error induced by said dynamics for arbitrary tempering schemes. Negative results are then given for the efficacy of tempering schemes (over the naive Langevin dynamics) both in terms of the intermediate distributions' log-Sobolev constants, as well as the worst-case convergence rate, although some regimes where the tempering is beneficial are highlighted.
weaknesses: It would be more helpful if the paper offered more positive examples of instances where the tempering can improve over vanilla Langevin by at least polynomial factors; in particular, a comparative bound would be helpful in Propositions 6, 7.

It would also be good if the paper could explore further the areas where tempering has a provable benefit over Langevin, especially in cases of multimodality where the algorithm would likely be used.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: The theoretical results in this work suggest that geometric tempering may not help the convergence of Langevin dynamics. Yet tempering is a strategy that is used in practice (per the authors' presentation of the literature). In practice, is tempering observed to lead to improved performance compared to vanilla Langevin dynamics? If yes, is there any intuitive reason why?

Minor questions:
- Would the conclusions, and the analysis techniques, of this paper still apply if one takes $\nu$ to be the Lebesgue measure instead of a probability measure?
- In practice, is the proposal $\nu$ always taken to be a Gaussian? Is it sometimes taken to be the Lebesgue measure? Or multi-modal?
- Is the $\frac{1}{2\alpha_\pi t}$ rate in Proposition 7 (line 433) classical? If so please give a reference.
soundness: 4
strengths: This paper addresses a natural question on the convergence of a sampling algorithm. The positive results (first item in "Summary") are of theoretical interest, as they address the technically difficult question of optimizing the upper bounds w.r.t the temperature schedule. The negative findings are surprising: namely, adding geometric tempering may actually slow down Langevin dynamics. This new insight is significant for both theory and practice.

The presentation is very clear and "flows" very nicely. All the technical claims are correct are far as I checked.
summary: This work analyzes the convergence rate of Langevin dynamics with geometric tempering (LD-GT), a modification of the Langevin dynamics which attempts to follow the geometric path between a proposal distribution $\nu$ (e.g. a standard Gaussian) and the target distribution $\pi$. 
More precisely, LD-GT with tempering schedule $(\lambda_k)_k \subset [0,1]$ is

$$X_0 \sim \nu, ~~~~ X_{k+1} = X_k + h \nabla \log \mu_k(X_k) + \sqrt{2 h} \epsilon_k,$$

where $\mu_k \propto \nu^{1-\lambda_k} \pi^{\lambda_k}$ is the geometric path (and $\epsilon_k$ are independent Gaussians).

(Per the authors' account of the literature,) LD-GT was proposed since the 1990s, and one of the motivations is the intuition that sampling progressively from the path $\mu_k$ is easier than sampling directly from the target $\pi$, especially if $\pi$ is multi-modal. 

This work's contributions are two-fold:
- Precise convergence guarantees for LD-GT under certain common assumptions on the proposal $\nu$ and the target $\pi$: Poincare inequality (PI), log-Sobolev inequality (LSI), strong log-concavity.\
To this aim, a key sub-question is to estimate the PI or LSI constant of the path $(\mu_k)_k$. Besides showing how to best utilize well-known upper bounds, the authors also identify cases where these constants are surprisingly poor, leading to the next item.
- This work provides evidence that the original intuition motivating LD-GT is wrong, by exhibiting cases where LD-GT must converge very slowly (regardless of the choice of schedule). Remarkably this can even happen for well-conditioned and uni-modal targets $\pi$, for which vanilla LD can be expected to converge fast.
weaknesses: No substantial weaknesses, but the negative results of this paper naturally lead to a question which is not addressed nor mentioned in this paper, see "Questions" below.

Minor comments on the presentation:
- use citep instead of citet on lines 119, 233, 254, 468
- correct typos and/or grammar on lines 271, 326, 420, 496, 1389, 1494, 1838
- justify the fact that chi^2, KL > TV rather than say it "of course" holds (line 493)
- line 988 contains the proof of Corollary 13, not 17
- add details on the argument on line 1824 (I could not reconstruct it using Cauchy-Schwarz, only Jensen)
- use different markers for each curve in Figure 2
- consider using a log scale or showing less iterations in Figure 3
- consider including the example of section 4.1 in Figure 4, in addition to Figure 1 (which shows only $\lambda \in \{0, 0.45, 1\}$)

Meta-review: The authors analyze the convergence of tempered Langevin dynamics. Most interestingly, the authors derive lower bounds where tempering leads to exponentially poor convergence. This result is quite novel as agreed upon by all reviewers. On top of this, the authors also provide the first upper bound results on convergence under functional inequality, which is already a nice result in itself. 

No significant criticisms were raised during the review process, and both reviewers with a score of 6 have agreed with acceptance, albeit not good enough to raise the scores to 8. Therefore, I believe this paper is welcomed contribution to the sampling literature and a clear accept.

Decision: Accept (Poster)