Hypocoercivity in metastable settings and kinetic simulated annealing

Combining classical arguments for the analysis of the simulated annealing algorithm with the more recent hypocoercive method of distorted entropy, we prove the convergence for large time of the kinetic Langevin annealing with logarithmic cooling schedule.


Main result
Consider the kinetic Langevin diffusion on R 2d , solution of the stochastic differential equa- where U is a smooth confining potential on R d (in the sense it goes to +∞ at infinity), m a mass, ν a friction coefficient, T a temperature and (B t ) t≥0 a standard brownian motion on R d . It is ergodic, so that the law L(X t , Y t ) is an approximation for t large enough of its invariant measure, which is the Gibbs law with density exp − 1 T U (x) + |y| 2 2 if m = ν = 1. At low temperature (namely when T goes to 0) the mass of the Gibbs law concentrates near the global maxima of U . The principle of the annealing procedure is that if T decay with time slowly enough so that L(X t , Y t ) is still a good approximation of the Gibbs law, then the process will reach the global minima of U . This mechanism has been abundantly studied for another process, the stochastic gradient descent which may be obtained from (1) when the mass vanishes or, up to a proper time rescaling, when the friction coefficient ν goes to infinity (and thus is sometimes called the overdamped Langevin process). In particular it is known (see [7] for instance) there exist a constant E * depending on U and called the critical depth of the potential such that, considering a positive cooling schedule (T t ) t≥0 , • if T t ≥ E ln t for t large enough with E > E * then for all δ > 0 P (U (Z t ) ≤ min U + δ) −→ t→∞ 1.
• if T t ≤ E ln t for t large enough with E < E * then for δ small enough lim sup t→∞ P (U (Z t ) ≤ min U + δ) < 1.
The reason Z has been more studied than (X, Y ) is that it is a reversible process whose carré du champ operator is Γf = |∇f | 2 , which relates its convergence to equilibrium to some functional inequalities satisfied by the Gibbs law (see [1] for definitions and more precise statements). On the contrary, (X, Y ) is not reversible and Γf = |∇ y f | 2 is not elliptic (it lacks some coercivity in the x variable), which is due to the fact the randomness only appears in dY and thus only indirectly intervenes in the evolution of X. In other word, Z has been more studied than (X, Y ) because it is simpler to deal with from a theorical point of view. However from a practical point of view a process with inertia can be expected to explore the space more efficiently than a reversible one. Indeed the velocity variable Y acts as an instantaneous memory which prevent the process to instantaneously come back to a place it has just been. Moreover the deterministic hamiltonian dynamics x ′′ (t) = −∇U (x(t)) − x ′ (t) is able to leave the catchment area of a local minimum of U , provided it starts with an energy U (x) + |x ′ | 2 2 large enough, which is not the case of the gradient descent x ′ (t) = −∇U (x(t)). This heuristic, according to which kinetic processes should converge more rapidly than reversible ones, has been proved for some toy model (for instance the Langevin process with a quadratic potential in [5]). On the other hand it has been numerically observed (in [14]) that (X, Y ) is indeed more efficient than Z (or than the Metropolis-Hastings mutation/selection procedure) to sample the Gibbs law at a given temperature for practical potentials. But to our knowledge a theorical proof of the convergence of a simulated annealing algorithm based on the Langevin dynamics was still missing.
According to the classical analysis of the simulated annealing (developped in the early nineties), the convergence of the algorithm is linked to the speed of convergence at fixed temperature of the process toward equilibrium. On the other hand this question of ergodicity has been intensively investigated over the past fifteen years for degenerate processes such as the Langevin one, which are called hypocoercive.
Pooling together classical (mainly the work of Holley and Stroock [8] and Miclo [11]) and hypocoercive (mostly the work of Talay [15] and Villani [17]) ideas, we are able to prove the following: Theorem 1. Consider a positive non-increasing cooling schedule (ε t ) t≥0 , a smooth positive function σ and the inhomogeneous Markov process which solves Assume U has at least one non-global local minimum and is quadratic at infinity, the ratio σ(ε) ε is bounded below by a positive constant, The theorem is proved in Section 2 (Corollary 4) in some general settings, and in Section 3 the requisite assumptions in order to apply the general result are checked for the kinetic Langevin case. Before proceeding to the proof, we make the following remarks: • The precise meaning of "quadratic at infinity" is stated in Assumption 3 below. It may be seen as an unecessarily strong requirement, but then the hypocoercive computations are simpler and, anyway, we are mostly concerned with the behaviour of the process in a compact set which contains all the local minima of U , since it is the place of the metastable behaviour of the process and thus, of its slow convergence to equilibrium (we refer to [19] for considerations about the growth of the potential at infinity in an annealing framework).
• Since at fixed ε the invariant law of the process is the Gibbs measure associated to the Hamiltonian − 1 ε U (x)+ |y| 2 2σ(ε) , we call ε the temperature and (ε t ) t≥0 the cooling schedule, despite the fact ε does not correspond to the physical temperature when the process is interpreted as the position and speed of a particle subjected to potential, friction and thermal forces.
• The fact there are two control parameter, ε and σ, make the framework slightly more general than the so-called semiclassical studies (cf. [13] and references within). These spectral studies furnish precise asymptotics at low (and fixed) temperature of the rate of convergence to equilibrium. However we will only need very rough estimates since, due to the metastable behaviour of the process, only an exponential large deviation scaling is relevant, and it is given by a log-Sobolev inequality satisfied by the Gibbs law: in other word it comes from an information on U alone, independant from the Markov dynamics.
• There are other natural kinetic candidates for the algorithm. We have in mind the run-and-tumble process (see [12], in which the convergence of the annealing procedure is studied in dimension one), the linear Boltzmann equation (see [13] and references within) or the gradient descent with memory (see [6]). The reasons we considered in a first instance the Langevin dynamics are twofold: first, each of the hereabove processes has additional difficulties. Both the run-and-tumble and the Boltzmann one are not diffusions but piecewise deterministic processes with a random jump mechanism, so that their carré du champ is a non-local quadratic operator, satisfying no chain rule, which make less convenient some forthcoming manipulations on entropies and Fisher informations. As far as the gradient descent with memory is concerned, no explicit formula is available for the invariant measure. The second reason to start with the Langevin dynamics is that it has been abundantly studied so that all the results we need are already proved and we will just have to pool them together.
• The result holds in particular if σ(ε t ) = ε t = E 1+ln(1+t) with E > E * . Of course the critical depth E * is unknown in pratice, and moreover in a real implementation the algorithm is only run up to a finite time. In this context, logarithmic cooling schedules are unefficient (see [3] on this topic).
• Theorem 1 only deals with the sufficient condition for the algorithm to converge, and not the necessary one, but we can't expect any reasonable Markov process with continuous trajectory (or at least small increments 1 , such as gaussian steps for a Metropolis-Hastings algorithm) to allow cooling schedule at a faster order of magnitude that E * ln t (of course it can be done by an artificial dilatation of the time scale, but this makes no sense in practice). Indeed, heuristically, such a process would take a time of order O(1) (at least at an exponential scale) to follow a reaction path, namely to go from a ball around a local minimum to a ball around another minimum without falling back to the first ball. Since by ergodicity the ratio between the mean time spent in the reaction path and the mean time spent in the small balls should be of the same order as the ratio between their probability density with respect to the Gibbs law, the mean time between two crossings from one ball to another should be of order O(e E ε ) where E is the energy barrier to overcome (this is the so-called Arrhenius law). While the process stays in the catchment area of a local minimum, it will make successive attempts to escape, which will be more or less independant from mixing properties due to the lack of (long-term) memory of the dynamics. The time between two deccorelated attempts would be somehow of order O(1), which mean the probability for each escape attempt to succed would be of order O(e − E ε ), or at least its logarithm will be equivalent to −ε −1 E (this is a large deviation scaling). If ε k , the temperature at the k th attempt, is of order c ln k , then the logarithm of the probability p k for the k th attempt to succeed will be of order − E c ln k, so that According to the Borel-Cantelli theorem, it means the process will almost surely leave the local minimum if c > E (slow cooling) or will stay trapped forever with a non-zero probability if c < E (fast cooling). Having a non-zero probability to get trapped forever in the cusp of any local minimum of depth at least E (where the depth of a local minimum x 0 is the smallest energy barrier to overcome starting from x 0 to reach another minimum x 1 with U (x 1 ) < U (x 0 ), and the cusp of x 0 is the set of points the process can reach from x 0 while staying at an energy level lower than U (x 0 ) + E), it will almost surely end up trapped in one of this cusp. Since E * is by definition the largest depth among all non-global minima of U , if E > E * then necessarily when the process is trapped, it is in the cusp of a global minimum, but if E < E * , it may be the cusp of a non-global minimum with positive probability, which means the algorithm may fail.
• Theorem 1 does not allow an efficiency comparison between the kinetic annealing and the reversible one. That said, from the previous remark, such a comparison cannot be expected at this level (low temperature and infinite time asymptotics; convergence in probability to any neighborhood of global minima) for different Markov processes. In fact in practice non-Markov strategies are developped, such as the Wand-Landau or adaptative biasing force (ABF) algorithms (see [9,4] and references within). Since the study [9] of the ABF algorithm relies on an entropy method, we can hope the present method to extend to this non-Markovian case.
• The result does not give any indication of what a good choice of σ would be. It is even unclear if it should go to zero or to infinity. A large σ allows high velocities, which means a stronger inertia and shorter exit times from local cusps, but may lead in high dimension to the same problem as uniform random large jumps, namely a blind tend to visit absurd configurations, and oscillations between high levels of potential, hardly affected by too short straight-line crossings of the compact where all the minima are located. This is reminescent to the fact too much memory yields instability for the gradient descent [6].
• Despite the above temperate remarks on its practical interest, we repeat and emphasize that even a theorical result such as Theorem 1 was yet to be rigorously established.

Main ideas
In the following we present a sketch of the method applied in an abstract framework, in order to highlight the main arguments.
As a first step, consider the temperature ε > 0 is fixed. We consider an homogeneous Markov process (X t , Y t ) t≥0 on E × F where both E and F are polish spaces. We call X the position, and Y the auxiliary variable (or velocity in the case where dX t = Y t dt). Let m t be the law of (X t , Y t ), (P t ) t≥0 and L be respectively the associated semi-group and infinitesimal generator, defined on a suitable set A of test functions f on E × F by Suppose the process admits a unique invariant measure µ = q ⊗ η where q ∈ P(E), η ∈ P(F ) (we note P(W ) the set of probability measures on a polish space W ) and ⊗ denotes the tensor product for probability measure. Suppose furthermore m 0 and P t are such that m t ≪ µ for all t ≥ 0. Then h t = dmt dµ is a weak solution of the usual entropy of f with respect to ν. Recall that entropy tensorizes (cf [1]), in the sense that We consider some non-negative (possibly equal to +∞) functions I q (f ) and J η (f ), that we call Fisher informations, defined on some subspace of non-negative function on respectively E or F , and we extend them to non-negative functions on E × F by We also consider a so-called distorted entropy H µ (f ) defined on non-negative functions on E × F and the corresponding disrupted entropy dissipation when this make sense. Then an (informal, since our framework is rather vague) abstract hypocoercive result (hypocoercive in the sense H µ is not necessarily equal to Ent µ , which would be the more classical settings) would be:

Proposition 2.
Suppose that there exist C, ρ such that for all non-negative f on E × F , and that q and η satisfies some log-Sobolev inequalities, in the sense there exist c 1 , c 2 such that for all f and g non-negative functions on, respectively, E or F , Then there exists κ > 0 such that H e tL * f ≤ e −κt H µ (f ) for all non-negative suitable f .
Proof. There is not much to say, since all the difficulties are hidden in the ad hoc assumptions.
Since the entropy tensorizes, µ inherits a log-Sobolev inequality from q and η, namely for all non-negative f on E × F , so that ∂ t H e tL * h ≤ −κH e tL * h for some κ > 0.
As a second step we let the temperature vary. More precisely we consider a nonincreasing positive cooling schedule (ε t ) t≥0 . Let L ε and µ ε = q ε ⊗ η ε be the generator and invariant measure of the process at fixed temperature ε. We call L εt and µ εt the instantaneous generator and invariant measure of the inhomogeneous process. Indeed, under suitable regularity assumptions, there exist an inhomogeneous process (X t , Y t ) t≥0 such that the semi-group (P s,t ) 0≤s≤t defined by satisfies ∂ t P 0,t f = P 0,t L εt f for suitable test functions f . We write L * ε the dual of L ε in L 2 (µ ε ). Let m t = L(X t , Y t ) and suppose m 0 is such that m t ≪ µ εt for all t ≥ 0, so that Assumption 1.

Framework: the log-derivative
exists and is finite. There exist an inhomogeneous Markov process (X t , Y t ) t≥0 whose law m t satisfies the Kolmogorov forward equation (4) and m t ≪ µ εt for all t ≥ 0, so that the density h t satisfies equation (5). There exists a subset D of non-negative function on E × F such that h t ∈ D for all t ≥ 0, and such that for all f ∈ D and ε > 0, H µε (f ), I µε (f ) and J µε (f ) are well-defined and finite, as well as We write H t = H µε t (h t ) and use a similar notation for I, J, K, K and Ent.

Moment estimates:
There exist p ∈ N and l(ε) > 0 such that where, if d 1 stands for the metric on E and x 0 is some fixed point in E, by d p 1 we mean the function x → (d 1 (x, x 0 )) p , and the same goes for d 2 , the metric on F , and a fixed y 0 ∈ F (note that this assumption does not depend on the choice of (x 0 , y 0 ), up to the choice of l(ε)). Moreover for all α > 0,

5.
Large deviation scaling: the function κ, λ and l defined in the previous assumptions are all sub-exponential, where we say a function w(ε) is sub-exponential if ε ln w(ε) goes to 0 as ε goes to 0. On the other hand there exist D 1 > D 2 ≥ 0 such that ρ i (ε)e D i ε is sub-exponential for i = 1, 2.

Slow cooling: the cooling schedule (ε t ) t≥0 is positive non-increasing, and for t large enough
Let's make some remarks on this set of assumptions.
• Everything could be stated with a unique variable rather than a couple (X, Y ), but we wanted to emphasize the different role of the position, which is the variable of interest from which arises the metastable behaviour, and of the auxiliary variable, which can anyway be taken equal to zero to cover the one variable case.
• Concerning the log-Sobolev inequalities, contrary to the classical case (see [1] for instance), the Fisher informations I and J are not necessarily defined thanks to the generator (or the carré du champ operator) of the semi-group, or in other word they are not linked to the underlying dynamics. For instance, even if it is often associated to the reversible Marko process (2) (or, in an equivalent manner, to the Witten Laplacian), the usual I q (f ) = |∇ ln f | 2 f dq is only built on two ingredients: the mesure q, and the gradient of R d , or in other words the underlying metric.
• For the Langevin dynamics, Part 3 of these assumptions is proved by Villani in [17]. The link of K and some moments of the process, in Part 4, appears in the classical annealing analysis of Holley and Stroock [8] and Miclo [11]. For the Langevin process, an estimate on M p (t) has been proved at fixed temperature by Talay [15] via Lyapunov techniques.
• Part 5 of these assumptions is in fact the crucial point. At fixed temperature, the distorted entropy method does not usually yield sharp estimates of the real convergence rate (apart, for now, from the gaussian case [2]). But when the measure q is multi-modal, with high-probability areas separated by low-probability barriers, the log-Sobolev constant ρ 1 is exponentially small at low temperature (see [10], and this is indeed sharp), namely D 1 > 0. Hence, only the large deviation scale is relevant, and while they stay at a sub-exponential level, all the other computations can be very rough.
• The fact the only relevant parameter -the log-Sobolev constant ρ 1 -is just defined thanks to the measure q and the metric of R d , and does not depend on the generator, makes sense in view of our previous remark according to which all reasonable continuous Markov process devised to sample a Gibbs law should follow the same Arrhenius law, regardless of the local Markov dynamics.

Theorem 3. Under Assumption 1, H t goes to 0 as t goes to +∞.
Proof. Once again the main difficulties are hidden in the assumptions. We compute Since l is sub-exponential and ε t ln t is bounded below for t large enough by a positive constant (from the slow cooling assumption), ∀α > 0 On the other hand |ε ′ t | ≤ ε 2 0 Dt for t large enough and M p (t) = o(t α ) for all α > 0, so that for any α > 0, β(t) := |ε ′ t |l(ε t )(1 + M p (t)) = o(t −1+α ). In particular, since K t ≤ 0, for t large enough. From the tensorization of the entropy, we have for some c 2 > 0. Thus we have obtained, for t large enough, ε with a sub-exponential γ, so that γ (ε t ) = o(t α ) for all α > 0 (same argument as l(ε t )). From the slow cooling assumption, there exists c 3 > 0 such that for any α > 0 and t large enough, which implies e − D 1  o (b(t)). As a result, we have obtained for t large enough , which implies H t goes to 0 ([11, Lemma 6]). Now suppose the sequence of law (q ε ) ε>0 satisfies a large deviation principle with rate function U , in the following sense: Proof. In the previous proof, we have showed that for all α > 0, there exists t 0 , r 1 , r 2 > 0 such that for all t ≥ t 0 , for t large enough and, in fact, for all t. But then, by part 3 of Assumption 1 and thanks to the Pinsker's Inequality, Finally, since for any

The kinetic Langevin diffusion
In this section we consider the diffusion process (X t , Y t ) t≥0 on R 2d solution of the stochastic differential equation where (B t ) t≥0 is a standard brownian motion on R d , and σ, ε > 0 are control parameters. The associated generator at temperature ε > 0 is and the corresponding invariant law is µ ε (dxdy We write ∇ x · and ∇ y · the divergence operators with respect to the variable x and y, so that in L 2 (µ ε ), .∇ y + ∆ y .
Assumption 3. The potential U is smooth, with a finite number of critical points, all non-degenerate (i.e. U is a so-called Morse function) and at least one non-global minimum. Furthermore and U is quadratic at infinity in the sense there exist a 1 , a 2 , M , r > 0 such that for all x ∈ R d Under this assumption, writing q ε (x)dx and η ε (y)dy the marginal laws of µ ε , the log-Sobolev inequalities are known. More precisely, let D be the set of smooth non-negative functions on R d whose derivative of all order grow at most polynomialy at infinity, D 1 (resp. D 2 ) the set of function in D which does not depend on y (resp. x). Then for all ε > 0, for all f ∈ D, Ent µε (f ) is finite and for all f 1 ∈ D 1 and f ∈ D 2 , are well-defined and finite.

Proposition 5.
Under Assumption 3 there exist E * , called the critical depth of U , and a subexponential c(ε) such that for all f 1 ∈ D 1 and f ∈ D 2 , Proof. For the first point, among several proofs, we refer to the recent work [10]. For the second one, note that η ε is the image by the multiplication by σ(ε) of the standard gaussian law, which satisfies a log-Sobolev with constant 1 2 . The description of E * is the following: it is the larger energy barrier the process has to overcome, starting from a non-global minimum of U , to reach a global one (see [10]).
• The cooling schedule ε t is positive, non-increasing and satisfies for t large enough 1 Et with E > E * . In particular ε t ≥ E A+ln t for some A > 0, and |ε ′ t | ≤ Proof. For an hypoellipticity result for inhomogeneous diffusions, we refer to [16], and for the non-explosion of the process, the arguments of [18,Lemma 1.1] can be adapted to the inhomogeneous case, noting that the homogeneous Markov process (X t , Y t , t) t≥0 can be obtained from the non-explosive, strong Feller process ( t 0 B s ds, B t , t) t≥0 via a Girsanov formula.

Distorted entropy
In this subsection, the temperature ε is fixed, and we consider h t = e tL * ε h 0 ∈ D. For the kinetic Langevin process, we already know from the work [17] of Villani that the hypocoercivity part of Assumption 1 holds. We will explicit the computations to check all the involved parameters are sub-exponential. Then and, according to [17, Lemma 32], writing |∇ 2 With δ = 1 4 , this yields and conclusion follows.
In other words, writing K µε (f ) = d dt |t=0 H µε e tL * ε f for f ∈ D, we have proved

Moment estimates
The aim of this subsection is to prove under Assumptions 3 and 4 the following: Proposition 8. For all p ∈ N and α > 0, and for any initial condition with all moments finite, there exists a constant k such that We follow the methods of Talay [15] (see also [18]) and Miclo [11], making sure the temperature is only involved in sub-exponential functions.
Finally, from σ(ε) ≥ lε and the non-increasivity of ε, Lemma 10. For all p ∈ N, there is a sub-exponential C p (ε) such that Proof. It is straightforward from the fact σ, δ, ∂ ε σ and ∂ ε δ are sub-exponential, since the product and sum of sub-exponential functions are still sub-exponential.