Global Optimization Algorithm through High-Resolution Sampling
Authors: Daniel Cortild
Claire Delplancke
Nadia Oudjane
Juan Peypouquet
Venue: Accepted by TMLR ()

Abstract: We present an optimization algorithm that can identify a global minimum of a potentially nonconvex smooth function with high probability, assuming the Gibbs measure of the potential satisfies a logarithmic Sobolev inequality. Our contribution is twofold: on the one hand we propose said global optimization method, which is built on an oracle sampling algorithm producing arbitrarily accurate samples from a given Gibbs measure. On the other hand, we propose a new sampling algorithm, drawing inspiration from both overdamped and underdamped Langevin dynamics, as well as from the high-resolution differential equation known for its acceleration in deterministic settings. While the focus of the paper is primarily theoretical, we demonstrate the effectiveness of our algorithms on the Rastrigin function, where it outperforms recent approaches.

Published in Transactions on Machine Learning Research (09/2025)
Global Optimization Algorithm through High-Resolution Sampling
Daniel Cortild
d.cortild@rug. ml
University of Groningen, Netherlands
Laboratoire de Finance des Marchés de l'Energie, Dauphinee CREST, EDF RED, France
Claire Delplancke
claire.delplancceeeee
EDF R&D Palaiseou, France
Nadia Oudjane
nadia oudjane Bedf
Laboratoire de Finance des Marchés de l'Energie, Dauphine, CREST, EDF RED, France
Juan Peypouquet
j.g. E.gpeggoouucttrrggg. ml
University of Groningen, Netherlands
Reviewed on OpenReview: https: // openreview. net/ forum? id=+3VEA1AWYS
Abstract
We present an optimization algorithm that can identify a global minimum of a potentially nonconvex smooth function with high probability, assuming the Gibbs measure of the potential satisfies logarithmic Sobolev inequality. Our contribution is twofold: on the one hand we propose said global optimization method, which is built on an oracle sampling algorithm producing arbitrarily accurate samples from given Gibbs measure. On the other hand, we propose underdamped Langevin dynamics, well as from the high-resolution differential equation known for its acceleration in deterministic settings. While the focus of the paper is primarily theoretical, we demonstrate the effectiveness of our algorithms on the Rastrigin function, where outperforms recent approaches.
sampling algorithm, drawing inspiration from both overdamped and
1 Introduction
Smooth nonconvex optimization remains a challenge with broad applications in machine learning and statistical inference. Despite significant advances, convex optimization techniques often lead suboptimal computationally infeasible solutions in many inherently nonconvex real-world problems.
In this paper, we focus on the unconstrained global minimization problem: given a smooth nonconvex potential U: R + R. we search for a point x² such that
x' E argmin Uxx,,
assuming such a point exists.
A recent trend in optimization consists of studying contimuous-time versions of algorithms to obtain better estimates for their discrete-tine time counterparts. Notable progress has been made in accelerating convergence of first-order optimization methods by analyzing socond-order dynamical systems in their contimuous-time formulation. In specific, shall interest ourselves in the high-resolution differential equation, given by
#(t) + (z))(( + vVU(2(()) =
(1)
where a, , > could in principle depend on time, but are supposed constants as indicated by the notation. The equation was originally introduced in Alvarez et (2002) and has since been further explored in Attouch et al. (2016), to mitigate the oscillations. The algorithmic consequences of this, including the

---

Published in Transactions on Machine Learning Research (09/2025)
connection with Nesterov's method, were investigated independently in Attouch et al. (2022) and Shi et al (2022). The theoretical convergence rates obtained for the resulting algorithmic framework were comparable to those established for Nesterov's method in the convex case. However, in the strongly convex case, the theoretical guarantecs were more conservative. Nevertheless, this motivated intense research within the convex optimization community, and the high-resolution differential equation seems to be displacing the classical differential equation studied Su ct al. (2016) and Attouch et al. (2018), which corresponds to the overdamped Langevin system, as the preferred continuous-lime model for Nesterov's acceleration. Amongst other reasons, the resolutionn model extends better to the nonsmooth setting, and it captures the linear convergence rates of FISTA and the Optimized Gradient Method in the strongly convex case, while the overdamped one does not. These characteristics, coupled with the more stable trajectories it enables and the potential for integrating other techniques, such as restart schemes (Su et al., 2016), underscore the high-resolution differential equation's siguificance as a promising area of interest in convex optimization. To the best of our knowledge, only the convergence critical points has been shown for Equation (1) in nonconvex landscapes (Alvarez et al., 2002).
By setting v(t) = =(1) + (v((((( and renaming the parameter 7, we can rewrite Equation (1) as a first-order system
a(t) =-VV((x(t) + v(t)
(2)
((t) =->vU(=()) - ay(t).
This reformulation has the benefit of not requiring the Hessian of U, making it more user-friendly, whilst still preserving the favourable convergence results.
However, deterministic models like System (2) may struggle when the potential U is nonconvex, as they can become trapped in local minima and fail to identify the global minimizer. To overcome this limitation, it has been proposed to add stochasticity to the dynamics to enable them lo escape local minima. This stochasticity can come in the form of random perturbations, encouraging the dynamics to navigate through more complex, potentially nonconvex, landscapes. This perspective naturally leads us to consider stochastic differential equations, specifically the Langevin dynamics (Langevin, 1908), which combine the advantages of gradient flows with stochastic elements. Rather than the iterates of these dynamics, we study their law, and hope for it to concentrate around the global minimizers of the potential. This pushes us towards sampling problems, where we aim to produce samples from a given distribution xx exp(-U).
Many problems in statistics require sampling from probability distributions. Sampling through the Langevin dynamics is well-studied approach when the target distribution is strongly log-concave (or equivalently, when the potential is strongly convex) (see Durmus and Moulines (2016); Dalalyan and Karagulyan (2019); Cheng and Bartlett (2018); Dalalyan and Riou-Durand (2020) and the references therein), and has recently also been studied in the non log-concave setting, when it, for instance, verifies a log-Sobolev inequality (Vempala and Wibisono, 2019; Ma et al., 2021), a Poincaré inequality (Chewi et al., 2022), a weak Poincaré inequality Aloussvi-Hosseein al., 2023), or even in the fully nonconvex setting (Balasubramanian al., 2022).
The simplest variant of the Langevin dynamics is the overdamped Langevin dynamics, governed by
dX,- VX)(( + Vr
where (Bt) is standard Brownian motion, 7 > O is free parameter and U is the negative logarithm of the distribution we wish to sample from. Under weak assumptions, the invariant distribution of the dynamics is exactly la x exp(-U). Convergence of the Euler discretization of the overdamped Langevin dynamics in Wasserstein-2 distance under strong convexity of U was shown in Durmus and Moulines (2016), and convergence in Kullback-Leibler divergence under a log-Sobolev assumption on f in Vempala and Wibisono (2019). Accelerated rates may be obtained under different discretizations. For instance, see Dalalyan and Karagulyan (2019) for strongly log-concave targets.
2

---

Published in Transactions on Machine Learning Research (09/2025)
A different approach to faster convergence involves the underdamped Langevin dynamics, governed by the stochastic differential equation
dXx; = Vidt
dV, = (->VUUXX)) - Vi)dt + /2,dBr.
where V/2 represents the velocity. Under weak assumptions, the invariant measure is u(z,0) x exp(-U(a))
(2?)) Accelerated convergence with respect to the overdamped dynamics was shown in Wasscrstein-2 distance in the strongly log-concave case by Chong and Bartlett (2018) and in Kullback-Leibler divergence under log-Sobolev inequality by Ma et al. (2021). We again note that different discretizaaions are possible, we cite for instance Dalalyan and Riou- Durand (2020) and Schuh and Whalley (2024).
Sampling algorithms for optimization were first introduced for strongly convex potentials in Dalalyan (2017), and further studied in Raginsky et al. (2017); Xu et al. (2018); Zhang al. (2017); Tzen et al. (2018), the nonconvex setting. All of these focused on discretizations of the overdamped Langevin dynamics. The underdamped Langevin dynamics have also been studied, refer to Gao et al. (2020) and Borysenko and Byshkin (2021) for more details. Discretizations of other underlying processes were investigated in Chen et al (2018) Zhang (2024). Langevin dynamics have also been studied for global optimization outside the context. of sampling. We refer interested readers to Chen et al. (2024) and the references therein.
1.1 Contribution
The contributions of the paper are the following:
1. We design a global optimization algorithm capable of minimizing nonconvex functions and obtaining arbitrarily accurate solutions with high probability. This optimization algorithm relies on an oracle sampling algorithm.
2. We propose new variant of the classical Langevin dynamies, both for continuous-time and discrete- time. The dynamics is inspired by the first-order high-resolution System (2), which is known to exhibit accelerated convergence rates in the deterministic convex setting. We anticipate that this study will encourage further exploration of this system, with the potential to deliver comparable breakthrough in the field of nonconvex sampling as it has achieved in convex optimization. This sampling algorithm will then serve as oracle algorithm in our global optimization algorithm.
1.2 Structure
Section 2 introduces notation and preliminaries. Section 3 is dedicated to the design of our global optimization algorithm. In Scction 4 we study a novel continnous- and discrcte-time dynamics, and formulate the sampling results. Finally, Section 5, we illustrate our results numerically on the Rastrigin function, where we improve on current methods. Technical results and proofs are provided in the appendix.
2 Notation and Assumptions
The following standing assumptions on the potential U: Rd + R will be valid throughout the paper:
U is twice differentiable, L-smooth and has Lipschitz continuous and bounded Hessian.
There exists ao > 0 such that exp(-aoU) is integrable.
U has a nonzero finite number of global minimizers, and admits no global minimizers at infinity, We define its minimal value to be U"
Let || || denote the Euclidean norm on T&d and P(TR)) denate the space of probability measures on Rd. With abuse of notation, we shall denote interchangeably by μ P(Rd) the probability distribution and its density function with respect to the Lebesgue mcasure, in the case where it exists. For given potential U: Rd - R and reals a 2 ag and b > 0, we define S E P(Rd) and pad E P(R2d) to be the probability distributions whose densities satisfy
11 (x) x exp(-aU(x)) and (x, exp (-aU(s)
||u1l 2
3

---

Published in Transactions on Machine Learning Research (09/2025)
which are well-defined by assumption.
Given distribution e P(RR), denote by
Ex~nI[(X) J [())
the expected value of f(X) where X μ.. Whenever the random variable or distribution is clear from context, we shall abbreviate this to [x)) or [X](X)).
Let μ.v E P(RR) both have density with respect to the Lebesgue measure and have full support. We define the total variation distance between μ and v
| v lTv = sup [ Exlfll ff S 1}
We define the Kullback-Leibler divergence of μ with respect to
KT(uIIV) Exx= [og (X) v(X)
Morcover, we define their relative Fisher information as
V (X) 27
Voo v(X)
Fi(p Ex~
Finally, we define the Wasscrstein-2 distance between μ and v as
1/2
W2(H, = inf E(x,y~ |Xx (EIT())))
| - 212
where l' v) is the of couplings of i and v, namely the of distributions Ç P( such that C(A (Rd) ((A) and C(R A) v(A) for all B(R"). The infimum is always attained, and we call the minimizers optimal couplings (Villani, 2009).
A standard assumption in the literature when dealing with nonconvex sampling is logarithmic Sobolev inequality (Vempala and Wibisono, 2019; Ma et al., 2019; 2021), which may be viewed as Polyak-Lojasiewicr inequality on the space of probability measures (Liu et al., 2023; Chewi and Stromme, 2024). To the best of our knowledge, this assumption is not standard in the field of global optimization. A log-Sobolev inequality on ae with coefficient states that, for all v E P(R.),
KT(vllm) S Fi(vllm).
(3)
2p
Remark 2.1. The notion of a logarithmic Sobolev inequality as presented in Inequality (3) was originally introduced in Feissner (1972) for Gaussian measures, and extended in Gross (1975) for general measures. All strongly log-concave probability distributions satisfy the inequality (Bakry and Emery, 1985), which is stable under bounded perturbations (Holley and Suroock, 1987), tensorization, convolution and mixture (Ledoux, 2006; Bakry al., 2014), and Lipschitz perturbations (Brigati and Pedrotti, 2024), although this might come at the expense of the constant. In the case of mixtures of Gaussians of equal variance, the log-Sobolev constant has an exponential dependency in the problem dimension (Menz and Schlichting, 2014; Schlichting, 2019). Moreover, measures with potentials which are strongly convex outside a ball satisfy a log-Sobolev inequality (Ma et al., 2019), although the constant may again have an exponential dependency in the dimension.
Assumption 2.2. The Gibbs measures μrt of U: Rd > R satisfy a logarithmic Sobolev incquality with coofficients Pa > 0, for all 2 ag.
4

---

Published in Transactions on Machine Learning Research (09/2025)
Remark 2.3. Under Assumption 2.2, the measures μrth also satisfy a log-Sobolev incquality with constant Pa,b = min(pa, Pb) by tensorization, where we know that pb = 1/b since the marginal in y of µad is strongly log-concave with parameter b. Verifying the logarithmic Sobolev inequality for each a 2 ao may be challenging in general, however is readily verified under some structural assumptions on the potential. For instance, it is satisfied U V F, where V strougly convex and F is bounded, as strongly convex polentials induce a Gibbs mcasure satisfying the log-Sobolev property, which is stable under bounded perturbations. To the best of our kuowledge, the tightest known lower bound for Pe given by Osc(P)) (ap)) where p is the strong convexity constant of V. As Osc(F) typically scales with the dimension d, this highlights the possible exponential dependency in the dimension and in the parameter a of Pa: and hence also of Pa.b-
We now recall Pinsker's Inequality (Pinsker, 1964), which relates the KL divergence and the total variation distance.
Thcorem 2.4 (Pinsker's Incquality). For any two p, v E P(RR), holds that
KL(UI
| -llv S
We finish this section by recalling McDiarmid's Inequality (MeDiarmid, 1989) in the single case. Lemma 2.5. Let f: I& + R satisfy Osc(f) = sup(f) inf < +00. For any random variable X, it holds
thal
P(E[f(X) f(X) 2 E) - exp ( (Osc(f)z
2s²
3 Optimization
The idea behind the global optimization algorithm is to sample from distribution that produces samples close to global minimizers. Specifically, we define f4 E P((RR) to be a mixture of Dirac measures concentrated around the global minimizers U with weights as defined in (Hasenpflug et al., 2024, Equation 18). As such,
by Hasenpllug et al. (2024), under the technical Assumption B.1, there exists a constant 0, depending only, satisfying
W2(n", 1²) S C a114
(4)
As such, an approximate sample from nº will yield samples close global minimizers. Concretely, we suppose have access to distribution i satisfying
KL(ĀIlm" < ="//18
5
for some 0, and that we can draw samples from ja.
We are now ready to introduce our global optimization algorithm, dependent on a yet unspecified oracle sub-algorithm, correspouding to a sample from j..
Algorithm Global Optimization Algorithm Require: Oracle algorithu.
Generate N random i.i.d. samples (0) according to oracle algorithm where i i= 1,..., N. Set X (1) for I argmin (X)))..
With these results at hand, we may prove convergence in probability of Algorithm 1.
Theorem 3.1. Let U: Rd R satisfy Assumptions 2.2 and B.1. Fix E (0, 8 10, and suppose
9C*12 T? and NY 18 18
a 2 max
ao:
(6)
22
2²
Suppose we have access to an oracle algorithum that can produce a sample from p. where i satisfies (5). Then, if X is simulated according to Algorithm 1 with the same oracle algoritim, it holds that
P(U(X) U > 6.
5

---

Published in Transactions on Machine Learning Research (09/2025)
Remark 3.2. A natural choice for the oracle algorithm producing samples X satisfying (5) is iterative sampling algorithm, producing the sample in K iterations. The total complexity to produce the sample X is then of K .N, with the possibility of parallelization when N > 1. For a fixed computational budget, there is a trade-off between the number of iterations and the number N of samples, as indicated by Equation (8) below, where the number of iterations K will control how small the probability P(U((()) 2 e) is. Therefore, the number of iterations should be big enough if one wants to ensure that increasing the number of samples N leads improved accuracy.
Proof. Without loss of generality, set U = O.
Let X for i i= I,..,, NN be N ii.d. copies generated according to the oracle algorithm, such that X 80) where I = argmin;=11....! ()).
Note that, for any i 1,..., N,
- e- -U((() - [[((x]]
(7a)
c [[U(X()] Eee ((x1)
(7b)
+ Ele u(X1) 1881 - U(810))
(7c)
Ele ((x60)) - -(((1))
(7d)
Term (7a) is bounded by L-smoothness as
[[U(X")] = E(U(X)) - U(x)]
E (X- - -x+) + 2 | x xx113
L W3 (p) 2/ v 2
LC
6'
where X 1e such that VU(X*) 0 almost surely, and (X*,'') 5" for 5 optimal coupling between fx and jz". As such, using that - e- < x, we obtain that (7a) is bounded by e/6. Moreover, I + exp(=x) is convex, (7b) is nonpositive, by Jensen's inequality. Since I + exp(-U(x)) is bounded by 1, (7c) is bounded as
e U(X*) - [e[e- [((0)))))] S 1 1 1ll I
KL mM)
2
where the second step uses Pinsker's Inequality 2.4. Finally, by considering all the bounds on (7), we have
IP (1- (1----0(80) ((((() 2 e/2) < Eie - - -U((0) > s/6) I exp(==²/18) - 8'NN
where the third inequality follows by Lemma 2.5, as x holds that 1 1- -- 2 x/2, and hence
x + e- ((x) takes values in [0, 1]. For x E [0, 102], it
P(U(X() 2 26) SP (1 -U(()) 2 20/2) S
As X x1) where I = argmin = U()()), and (X (8)()) are iid, it holds that )
P(U(X) 2 = P(U())) 26) <o.
(8)
Remark 3.3. In Theorem 3.1, the bound of s < 1/2 is artificial to the proof. By scaling U one can obtain similar results, up to a constant factor, for any value of > 0.
Algorithm depends on a yet unspecified oracle algorithm. A new such oracle algorithm discussod Section 4. However, the modular form of Algorithm provides simple framework to employ other sampling algorithms, which potentially may lead to faster provable convergence, or be applicable in different. contexts.

---

Published in Transactions on Machine Learning Research (09/2025)
4 High- nigh-Ressluutin Langevin
4.1 Continuous-Timg Study
As previously highlighted, the high-resolution differential equation introduced in System (2) has played pivotal role in advancing the study of accelerated convex optimization algorithms. Aiming to build an algorithm with accelerated convergence rale for nonconvex sampling, we introduce the Raah-Reesootion Longevin Dynamics, inspired by these dynamics. Let FI,),1)) be a filtered probability space and consider the following stochastic differential equation:
dX, = (-BVU(X)) + Ki)dt + V20
dY, (-VVUXX) - + / 20
where (B", B is standard 2d-dimensional Brownian motion, (Xo. Yo) Mo for some initial distribution Mo: and a, B, 7, of of 0. As the drift coefficient is Lipschitz continuous, System (9) has unique solution (Friedman, 1975). We denote the joint law of (Xe, Yr) by Me: which has a twice continuously differentiable density with respect to the Lebesgue measure, as the drift coefficient has Lipschitz continuous and bounded gradient (Menozzi et al., 2021).
A slight variation of System (9) has been studied previously in Li et al. (2022), with similar motivations. The authors obtain convergence rates in the W2 metric, in the strongly log-concave sctting. As our study addresses the nonconvex setting, comparative analysis falls outside the scope of this work.
Remark 4.1. System (9) is equivalent to
dz, - 7/a a/b)
(3/a -1/b)
(z) + 203
0 og
dB
where Z Yt) and H((, v)) aU (x) + b 2 As such, System (9) may be viewed preconditioned Langevin dynamics in larger space the function H.
Moreover, the difference between System (9) and the underdamped Langevin dynamics, through the presence of additional noise.
Finally, as 22 o + O, we recover the deterministic System (2), which exhibits accelerated convergence.
We now study the convergence in KL, divergence System (9), similarly to what was done Ma al. (2021). A byproduct of the proof (see Appendix C.1) is the uniqueness of the invariant measure.
Theorem 4.2. Let U: Rd R, and let 2 ag and b, a, 7, 7.0 oz, O satisfy
B b and b =
(10)
1. System (9) admits a weak solution (X,, Yi) which has as invariant law a.
2. If pab satisfies a log-Sor noo-Sooolev inequality with > 0, (L, (L(Hollee*)) 22pmin(03.02
In specific, provided 02, og > 0, we obtain (T(pp,11uu - O ad exponential rate t co, and the invariant law aad is unique.
4.2 Discrete-Time Time Study
Consider the following discrctization of System (9):
dx; = (- (xxt) V.)dt + (0oid+++22200 2202dBE
(11)
dP; (->V aa + 200ddBy
7

---

Published in Transactions on Machine Learning Research (09/2025)
for t E [kh, (k + 1)hl, where is the step-size and Mo is the initial distribution, such that (Xo, Yo) ~ Poo We define i4, - L((X,, V.).
Conditionally on (X&,, Ykh), System (11) describes an Ornstein- Uhlenbbekk process for E [kh, + 1)h). We may thus simulate 114 by sampling an appropriate Gaussian random variable. The explicit computations leading to Algorithm 2 are presented in Appendix C.2.
Algorithm High-Resolutin Sampling Algorithm
Require: An imitial distribution io E (((2))). Simulate (Xo, Yo) Mo. for == O.....I. K do
3: Generate (K(++1) ((x+1))) ~ N(m, Σ) conditionally on (Ken, Faa), where
mx Xun (XEU)( + 1-c
Yun 2 h
1 1 c-ah
(U(()))
a my E aah kh (1 (1-e- -aaaa Σxx = 02
a
a
a
22ah 2nh + de -ah -3] Ia + h la
a
Σyy = 01 2aa))
a
o22 - adbl
Σxy Σyx
ld-
a²
end for return (KKh, YKι).
Our result, well our analysis, is comparable to Vempala and Wibisono (2019), who studied the highly overdamped Langevin Dynamics. The more precise result and its derivation are given in Appendix C.3.
Thcorem 4.3. Let E > 0, a 2 an, b > O and assume (10) holds. If a log-Sobolev inequality on p with parameler p holds, and h X O(p), then there exist
Ā = O(),, B B Oco(d// and B= Oaadd),
such that
KL S - (KT.(poolle + Bhi,
and, for all K 2 1,
KT -AKh (T.(polll1ad)) + Bh.
(12)
As an immediate corollary we obtain sufficient conditions to obtain an s-accurate sample.
Corollary 4.4. Let 0, 2 au, b O and assume (10) holds. If log-Sobolev inequality a. with parameler p > 0 holds, then KL Kh 10 Se for
h S δ
De
and
da² K 2
add
i3
Proof. Bound each term in Equation (12) by e/2.
We ready to complement Theorem 3.1, by replacing the oracle algorithm by Algorithm 2.
8

---

Published in Transactions on Machine Learning Research (09/2025)
Corollary 4.5. Let U: -R satisfy Assumptions 2.2 and B.1, and fiz E E (0, 1/2) and 8 E (0. 1). Suppose (6) holds, and that X is simulaatdd according to Algoritim 1 with K ilerations of Algoritlu 2 being used for the oracle sub-prot aod-procedure It holds that
P(U(X) - 0² 2 28 So for h h
Pa,tee a²d (a'd)
and K KZO
du²
E² Pa,b
Remark 4.6. As Remark 3.3, the results in Corollary 4.5 immediately extend to any & > 0.
Remark 4.7. It may be observed that the rales presented in Corollary 4.5 do not improve upon the best-known rates for the overdamped Langevin dynamics (Vempala and Wibisono, 2019) or the underdamped Langevin dynamics (Ma et al., 2021). However, this does not imply the absence of acceleration; rather, it reflects that our current analytical framework is not sufficiently tight to capture it. This is comparable to the initial studies on high-resolution differential equations which similarly did not demonstrate provable acceleration, yet. laid the groundwork for the remarkable advancements in acceleration techniques that we benefit from today.
5 Numerical Results
All experiments have been performed in Python 3.8. The code is available on the author's GitHub page." Our theoretical study does not answer the question of the optimality of the parameter choice, which we leave for future work. Given a > 0, we fix a = 1, 3 = 1, b = 10, 7 = a/10, o = 1/a and of = 0.1. The remaining parameters, namely the number of samples N, the number of iterations K and the step-size h, will vary with the experiments. The number of runs over which we compute empirical probabilities is denoted by M.
We illustrate the convergence of our algorithm on the Rastrigin function, a classical example of highly multimodal function with regularly distributed local minima. Let U: IR + R be given by
U(x) = d ||x0|| Σ cos (2Tx;),
which is minimized in x² = (O....,,)) 0) E Rd, with objective value U -~x) The Rastrigin function for d= 1 and d = 2 is plotted in Figure of Appendix A for illustrative purposes. The Gibbs measure of the Rastrigin function satisfies log-Sobolev inequality by Remark 2.3, and it is easy to see it also satisfies Assumption B.1. We select d = 10 for all the experiments, unless otherwise specified.
In Figure 1, we show the empirical probabilities computed over M = 100 runs that -(X+)-U* 2 for various thresholds E. In each run, a step-size h = 0.01, sample number N = 10 and a maximal number of iterations K = 14000 have been chosen. The initial distribution is set to jo = (3 1a, 10- Idxa). We observe that for smaller values of a, μa is not representative enough of μ= to guarantee the wanted threshold, even after numerous iterations. For larger a, the probability converges, with a rate that decreases as increases. This is expected, as yuth approaches fu" as incrcases, but the number of iterations to reach good estimate of 4º also increases a increases. These observations qualitatively confirm Corollary 4.5, as well as the dependency in a of Pa.b as outlined in Remark 2.3.
Table shows similar results in a tabular form, for various values of the step-size h. We report the average, median and standard deviation of M = 100 runs after K 14000 iterations. The small standard deviation showcases the robustness of our method. These results motivate our selection of step-size for the subsequent. experiments.
As previously noted, Algorithm achieves convergence for any sampling algorithm that satisfies the conditions outlined in Theorem 3.1. In particular, discretizations of both overdamped and underdamped Langevin dynamics are anticipated to be viable candidates. In Figure 2, we compare the high-resolution Langevin algorithm (HRLA) proposed in Algorithm 2 with the overdamped Langevin algorithm (OLA) from Vempala and Wibisono (2019) and the underdamped Langevin algorithm (ULA) from Ma et al. (2021), using comparable parameter settings. The values of a are selected empirically to optimize the convergence rate for a given value
9

---

Published in Transactions on Machine Learning Research (09/2025)
E=
0.75
PluiX)) 1 -U*
0.25
1.00
E-4
6
0.75
P --
0.50
0.25
0.00
0
2500
5000
7500 10000 12500
0
2500 5000
7500 12000
2500 5000 7500 10000 12500
Iteration count (k)
Iteration count (k)
Iteration count (k)
Figure 1: Empirical Probabilities Hitting Tolerance e for 14000 Iterations.
Table 1: Average, Median and Standard Deviation of Objective Function Value for Various Step-Sizes.
1
= 2
= 3
=
4
0.001
Avg
2.974
0.920
1.363
4.216
0.001
Med
3.034
0.895
1.427
4.291
0.001
SD
0.595
0.334
0.617
0.906
0.01
Avg
3.422
0.949
0.425
0.318
0.01
Med
3.488
0.960
0.422
0.329
0.01
SD
0.599
0.257
0.101
0.076
0.1
Avg
7.840
6.970
6.780
6.570
Med
7.977
7.168
6.894
6.712
0.1
SD
1.031
0.959
0.842
0.766
E, with convergence assessed by the speed al which the empirical probability reaches 1, which reflects the accuracy of the invariant measure and does not depend on the sampling algorithm. Hence the chosen pairs (a, are common to all three algorithms.
1.0
2=4,8=2
3,8
P(U(X)) -U
0.5
0.0
0
5000
10000
0
5000
10000
Iteration count (k)
Iteration count (k)
ULA
OLA
HRLA
Figure 2: Comparison of Different Sampling Methods.
Extending the results of Figure/ to a larger number of iterations (K 100000) with larger values of allows to reach better accuracies. This is shown in Figure 3, in which observe the same trends as in Figure/ 1.
10

---

Iteration count (k) Published in Transactions on Machine Learning Research (09/202))
E=2
0.75
PluiX)) - -U*
0.50
0.25
1.00
E E
6
0.75
P -
0.50
0.25
0.00
0
20000 40000 60000 80000
0 20000 40000 60000 80000
0 20000 40000 60000 80000
Iteration count (k)
Iteration count (k)
Iteration count
4
a=5
a
Figure 3: Empirical Probabilities Hitting Tolerance for 100000 Iterations.
The impact of the problem's dimensionality can also be analyzed. In Figure 4, we compare the cases of d 10 with and d = 20 with 4. The observed trends are remarkably similar, which aligus with theoretical expectations: doubling the dimension proportionally the expected initial objective value, and consequently, doubling the tolerance maintains the relative error at a consistent level.
1.0
d = 10,
20,
P(U(X)) -U"
0.5
0.0
0
5000
10000
0
5000
10000
Iteration count (k)
a=1
a =
a
=
3
a 4
Figure 4: Empirical Probabilities of Hitting Tolerance for d = 10 and d 20.
In all preceding figures, we observe faster convergence to the target n² for smaller a, however the target 4ºt is further from the true target μ², such that the probability converges to a value far from 1. In order to leverage this, one can updale the value of a over the iterations, in the same spirit as simulated annealing (Gidas, 1985). For a given a and a, we let ag be the value a at iteration k, where we assume (ax) evolves linearly between a and in Specifically, we set
0g (K k) k
(13)
K
where is the lotal number of iterations. We select a = 0.1, and vary the final value a. Figure 5 plots the empirical probabilities for various values of a, now for smaller tolerances. We observe a faster convergence abrupt, causing the
higher accuracy, as expected. For large values of a, the increase from a suboptimality of the algorithm to become trapped in local minima. This behavior may originate from the cooling scheme described in Equation (13). Further acceleration may be obtained either by optimizing the
11

---

Published in Transactions on Machine Learning Research (09/2025)
Table Average Objective Function Value for Fixed Effort N K
140000,
with dg given by Equation (13).
N
12
20
10
1
0.140
0.062
0.078
0.141
10
0.143
0.048
0.054
0.176
100
0.197
0.229
1.311
4.432
1000
3.653
8.781
11.167
12.558
10000
16.206
16.014
16.023
16.160
Table 3: Comparison to Results in Guilmeau et al. (2021), with given by Equation (13).
K
SA
FSA
SMC-SA
CSA
1
2
4
a 5
α 6
50
Avg
3.29
3.36
3.26
3.23
15.76
15.30
14.04
13.61
13.40
13.40
50
SD
0.425
0.453
0.521
0.484
2.539
2.262
2.563
2.068
2.306
2.065
500
Avg
2.52
2.64
2.62
2.47
2.56
0.74
0.38
0.32
0.31
0.61
500
SD
0.320
0.304
0.413
0.502
0.549
0.244
0.101
0.095
0.223
0.433
cooling scheme, or by employing alternatives to simulated annealing. Although we do not delve further into this, we refer the interested reader to Marinari and Parisi (1992).
1.00
0.5
E=
0.75
PlU(X)) U
0.50
0.25
0.00
0
2500
5000
7500 10000 12500
0
2500 5000 7500 10000 12500
2500 5000 7500 10000 12500
Iteration count (k)
Iteration count (k)
Iteration count (k)
ä= 12
==20
40
Figure 5: Empirical Probabilities of Hitting Tolerance e with ag given by Equation (13), for 14000 Iterations.
For a fixed computational effort N. K, one can choose to put a heavier emphasis on the number of samples N or the number of ilerations K. Table shows a comparison between multiple pairs of (N, K) having constant product and the average rumning best value over all iterates obtained. We observe that is beneficial to select N small, although N is not always optimal. Morcover, N = does not allow for parallelization, contrary to N 1. This does align with the observations in Remark 3.2.
In Table 3 we compare our results to well-studied variants of simulated annealing. Our algorithm is compared to Simulated Annealing (SA) as presented in Haario and Saksman (1991), Fast Simulated Annealing (FSA) as presented in Rubenthaler et al. (2009), Sequential Monte Carlo Simulated Annealing (SMC-SA) as presented in Zhou and Chen (2013), and Curious Simulated Annealing as presented in Guilmeau et al. (2021). The numerical values for the four aforementioned methods are extracted from Guilmeau et al. (2021). For a fair comparison we use the same parameters, namely we perform M 50 runs with N 250 samples and K = 500 number of iterations, and an initial distribution ñ4 6(zo)> where xo (1,..., 1)T "0 Table 3 transcribes the average running best function value and its corresponding standard deviation over the runs. Although at 50 iterations the accuracy of our algorithm is worse than for the other presented algorithms, the comparison reverses at 500 ilerations, where our method oulperforms the state-of-the-art methods by an order of magnitude of 10. In the state-of-the-ar simulated annealing methods, we observe very little improvement between 50 and 500 itcrations compared to our algorithm. This reflocts the well-known fact that simulated annealing methods tend to get stuck in local minimizers if the cooling scheme not tailored to the problem, issue which our method does not encounter.
12

---

Published in Transactions on Machine Learning Research (09/2025)
6 Conclusions
The main focus of the paper is on a global optimization algorithm, which produces arbitrarily accurate solution with high probability. The main assumptions the potential to be minimized were some regularity assumptions, and a log-Sobolev inequality on the Gibbs measure. This global optimization algorithm relies on an oracle sub-algorithm, which produces samples from a given Gibbs distribution.
For this oracle algorithm, we introduced new variant of Langevin dynamics, given in System (9). These dynamics are inspired by the deterministic high-resolution differential equation presented in System (2) to tackle global optimization in nonconvex settings. Our continuous- time and discrete-time dynamics complement the classical overdamped and underdamped Langevin methods by adding another noise lerm. We established convergence properties of the continuous- time dynamics, showing that their invariant measure concentrates around the global minimizers of the potential U, and developed practical sampling algorithm through discrelization, which provably converges.
Our theoretical analysis and numerical experiments on the Rastrigin function demonstrate that the proposed method effectively navigales nonconvex landscapes and can obtain accurate solutions with high probability.
6.1 Open Questions
Several open questions remain for future work:
1. The parameters of the algorithm were presented in a general form, and the optimal selection of these parameters is unclear. This is also the case for the ideal combination (N, K), as suggested by Table 2.
2. The constant C' in Incquality (4) is not explicitly defined in Hasenpflug et al. (2024). An explicit value would enable an explicit bound in Theorem 3.1.
3. The technical Assumption B.1 might be restrictive in certain contexts. Under more general smoothness assumptions, Algorithm can make use of sampling algorithms from non-smooth potentials, such as the proximal algorithm (Lee et al., 2021; Chen et al., 2022; Liang and Chen, 2023). Whence the interest in establishing bound similar to Inequality (5), under less restrictive assumptions.
4.
The cooling scheme outlined in Equation (13) is suboptimal, as evidenced by Figure Further research is needed to provide theoretical analysis of the simulated annealing variant of our algorithm. Additionally, the exploration of an adaptive scheme could be considered.
6.2 Acknowledgements
The authors thank the anonymous reviewers for their careful reading and insightful feodback on our manuscript.
They moreover thank Guillaume Garrigos, Huiyuan Guo, Lucas Ketels, Filip Voronine and Zepeng Wang, for our numerous mectings and their interesting and helpful insights and questions, and Marcike Hascnpflug for her help regarding her paper (Hasenpflug et al., 2024).
This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science. We thank the Center for Information Technology of the University of Groningen for their support and for providing access the Hábrók high performance computing cluster.
References
Alvarez, F., Attouch, H., Bolte, J., and Redont, P. (2002). A second-order gradient-like dissipative dy- namical system with Hessian-driven damping.: Application to optimization and mechanics. Journal de Mathématiques Pures Appliquées, (8):7777777
Ambrosio, I.., Gigli, N., and Savaré, G. (2005). Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Modia.
Attouch, H., Chbani, Z., Fadili, J., and Riahi, H. (2022). First-order optimization algorithms via inertial systems with Hessian driven damping. Mathematicnl Programming, pages 1-43. Publisher: Springer.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Attouch, H., Chbani, Z., Peypouquet, J., and Redont, P. (2018). Fast convergence of inertial dynamics and algorithms with asympiotic vanishing viscosity. Mathematical Programming, 168:123-18 Publisher: Springer.
Attouch, H., Peypouquet, J., and Redont, (2016). Fast convex optimization via inertial dynamics with Hessian driven damping. Journal of Differential Equations, 261 (61()))57344--788
Bakry, D., Gentil, I., and Ledoux, M. (2014). Analysis and Geometry of Markov Diffusion Operators, volume 348 of Grundlehren der malhematischen Wissenschaften. Springer International Publishing, Cham.
Bakry, D. and Emery, M. (1985). Diffusions hypercontractives. Séminaire de probabilités de Strasbourg, 19:177-206. Publisher: Springer- Lecture Notes in Mathematics.
Balasubramanian, K., Chewi, S., Erdogdu, M. A., Salim, A., and Zhang, (2022). Towards a theory of non-log-concave sampling: first-order stationarity guarantees for Langevin Monte Carlo. In Conference on Learning Theory, pages 2896-2922 PMLR.
Borysenko, O. and Byshkin, M. (2021). CoolMomentum: A method for stochastic optimization by Langevin dynamics with simulated annealing. Scientifie Reports, 11(1):10705.
Brigati, G. and Pedrotti, F. (2024). Heat flow, log-concavity, and Lipschitz transport maps. arviv preprint arXiv:2404.15205.
Chen, A. Y., Sekhari, A., and Sridharan, K. (2024). Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials, In OPT 2024: 16th Annual Workshop on Optimization for Machine Learning.
Chen, Y., Chen, J., Dong, J., Peng, J., and Wang, Z. (2018). Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion. In International Conference on Learning Representations.
Chen, Y., Chewi, S., Salim, A., and Wibisono, A. (2022). Improved analysis for proximal algorithm for sampling. In Proceedings of Thirly Fifth Conference Learning Theory, pages 2984 3014. PMLR.
Cheng, X. and Bartlett, P. (2018). Convergence of Langevin MCMC KL-divergence. In Algorithmmic Learning Theory, pages 186 211. PMLR.
Chewi, S., Erdogdu, M. A., Li, M. B., Shen, R., and Zhang, M. (2022). Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pages 2. PMLR.
Chewi, S. and Stromme, A. J. (2024). The ballistic limit of the log-Sobolev constant equals the Polyak- Eojasiewicz constant. arXiv preprint arXiv:2411.11415.
Dalalyan, A. (2017). Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages
PML.R
Dalalyan, A. S. and Karagulyan, A. (2019). User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12):5278 5311.
Dalalyan, A. S. and Riou-Durand, L. (2020). On sampling from log-concave density using kinetic Langevin diffusions. arXiv preprint arXim:1807.0000 09382.
Durmus, A. and Moulines, E. (2016). Sampling from a strongly log-concave distribution with the Unadjustod Langevin Algorithm. arXiv preprint orXiv:1605.0155
Feissner, G. F. (1972). A Gaussian measure analogue to Sobolev's inequality. Cornell University.
Friedman, A. (1975). Stochastic Differential Equations and Applications. In Friedman, A., editor, Stochastic Differential Equations, pages 75-148 Springer.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Gao, X., Gurbuzbalaban, M., and Zhu, L. (2020). Breaking Reversibility Accelerates Langevin Dynamics for Non-Convex Optimization. In Advances in Neural Information Processing Systems, volume 33, pages 17850 17862. Curran Associates, Inc.
Gidas, B. (1985). Global optimization via the Langevin equation. In 24th IEEE Conference Decision and Control, pages 774-778.
Gross, L. (1975). Logarithmic Sobolev Inequalities. American Journal of Mathematics, 97(4))1061 1083.
Guilmeau, T., Chouzenoux, E.., and Elvira, V. (2021). Simulated Annealing: Review and a New Scheme. In JEEE Statistical Signal Processing Workshop, pages 101-105.
Haario, Н. and Saksman, E. (1991). Simulated Annealing Process in General State Space. Advances in Applied Probability, 23(4) 23(4):866-89)) 893.
Hasenpflug, M., Rudolf, D., and Sprungk, B. (2024). Wasscrstein convorgence rates of increasingly concen- trating probability measures. The Annuls of Applied Probobilily, 34(3):3320 3347.
Holley, R. and Stroock, D. W. (1987). Logarithmic Sobolev inequalities and stochastic Ising models. Journal of Slatistical Physics, 46(5):1159) 159-):1159-11144
Langevin, P. (1908). On the theory of brownian motion. Comples Rendus de l'Académie des Sciences (Paris), 146:530.
Ledoux, M. (2006). Concentration of measure and logarithmic Sobolev inequalities. In Seminaire de probabilites XXXIII, pages 120-216. Springer.
Lee, Y. T., Shen, R., and Tian, K. (2021). Structured Logconcave Sampling with a Restricted Gaussian Oracle. In Proceedings of Thirty Fourth Conference on Learning Theory, pages 2993-3050. PMLR.
Li, R., Zha, H., and Tao, M. (2022). Hessian-Free High-Rosolution Nesterov Acceleration For Sampling. In Proceedings of the 39th International Conference Machine Learning, pages 13125 13162. PMLR.
Liang. J. and Chen, Y. (2023). A Proximal Algorithm for Sampling. Transactions on Machine Learning Research.
Liu, L., Majka, M. B., and Szpruch, L. (2023). Polyak Lojasiewicz inequality on the space of measures and convergence of mean-fiet field birth-death processes. Applied Mathematics & Optimization, 87(3):48.
Ma, Y.-.,, Chatterji, N. S., Cheng, X., Flammarion, N., Bartlett, P. L., and Jordan, M. I. (2021). Is there analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3):1942 1992.
Ma, Y.-A., Chen, Y., Jin, C., Flammarion, N., and Jordan, M. I. (2019). Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116 (16(42):20881-2088)
Marinari, E. and Parisi, G. (1992). Simulated Tempering: A New Monte Carlo Scheme. Europhysics Letters, 1956):451.
McDiarmid, C. (1989). On the method of bounded differences. Surveys in Combinatorics, 141(1))148-188.
Menozzi, S., Pesce, A., and Zhang, X. (2021). Density and gradient estimates for non degenerate Brownian SDEs with unbounded measurable drift. Journal of Differential Equations, 272:330 369.
Menz, G. and Schlichting, A. (2014). Poincaré and logarithmic Sobolev incqualities by decomposition of the energy landscape. The Annals of Probability, 42(5))1809 1884.
Mousavi-Hosssenn, A., Farghly, T. K., He, Y., Balasubramanian, K., and Erdogdu, M. A. (2023). Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincare Inequality. In The Thirty Sizth Annual Conference on Learning Theory, pages 1-35. PMLR.
Pinsker, M. S. (1964). Information and information stability of random variables and processes. Holden- Day.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Raginsky, M., Rakhlin, A., and Telgarsky, M. (2017). Non-convex learning via Stochastic Gradient Langevin Dynamics: nonasymptotic analysis. In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 1674 1703. PMLR.
Rubenthaler, S., Rydén, T., and Wiktorsson, M. (2009). Fast simulated annealing in $ (aathbb(R) with application to maximum likelihood estimation in state-space models. Stochastic Processes and their Applications, 119(6):1912 1931.
Schlichting, A. (2019). Poincaré and log-Sobolev inequalities for mixtures. Entropy. 21(1):89.
Schuh, K. and Whalley, P. A. (2024). Convergence of kinetic Langevin samplers for non-convex potentials. Xrviv preprinl 4r5 09992.
Shi, B., Du, S. S., Jordan, M. I., and Su, W. J. (2022). Understanding the acceleration phenomenon via high-resolution differential equations. Mathemalical Programmingg 195(1):79-11 148.
Su, W., Boyd, S., and Candes, E. (2016). A differential equation for modeling Nesterov's 's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1 43.
Talagrand, M. (1996). Transportation cost for Gaussian and other product measures. Geometric & Functional Analysis, 6(3):587 600.
Tzen, B., Liang, T., and Raginsky, M. (2018). Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability. In Proceedings of the 31st Conference On Learning Theory, volume 75, pages 857 875. PMLR.
Vempala, S. and Wibisono, A. (2019). Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimctry Suffices. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Villani, C. (2009). Oplämal Transport: Old and New, volume 338. Springer.
Xu, P., Chen, J., Zou, D., and Gu, Q (2018). Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization. In Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc.
Zhang, X. (2024). New algorithms for sampling and diffusion models. arXiv preprint Sit.::220000066655
Zhang, Y., Liang, P., and Charikar, M. (2017). Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1980 2022. PMLR.
Zhou, E. and Chen, X. (2013). Sequential Monte Carlo simulated anncaling. Journal of Global Optimization, 55:101 124.
16

---

Published in Transactions on Machine Learning Research (09/2025)
A
Deferred Figures
Figure 6 depicts the Rastrigin function in dimensions d and d 2, illustrating its nonconvex nature.
Figure 6: Rastrigin Function for d == and d = 2.
B Technical Assumptions
Equation (4) holds under the following technical assumptions:
Assumption B.1. We assume
1. There exists a global minimizer & of satisfying
f || - E|| (x)((((( < to0.
2. U is 6-times continuously differentiable set F Rd such that all global minimizers contained in the interior of F.
The Hessian of U is positive definite at each global minimizer.
C Deferred Proofs
For a probability measure μa E P((Rd)) we use the notation p(f) E[S(Z)] where Z la and ʃ is an integrable test function defined on Rd Given a process Ze pe: the notation (oje(f) denotes the function defined on Rd such that (z)) = (Zo) = z] for any E IRd.
We start by introducing lemma that will be used throughout the proofs.
Lemma C.1. Let fe: Rzo + P(R)) be a curve. Suppose that ve: B20 x Rdd Rd is sequence of vector felds salisfying n + V (m, vx) 0. Then it holds that, for all p P(R4),
d KL(H)1m(") Ey,, [ log w-
Hr (vlog
dt
Proof. See (Ambrosio et al., 2005, Equation 10.1.16).
C.1 Proof of Theorem 4.2
1. Observe that
V Valad a.b = (z) Vy a.
V -VV + +2 (2)
V Vanpaco (-b+ 1² b
17

---

Published in Transactions on Machine Learning Research (09/2025)
As such, under the given parameters, one easily checks that
0 = (-a3 + oo
+ (0 (B + -2,b)
-KN01//00-////000001-00-000----0 onjy
1 - ((- 9)) V. ((~>VU(x)) ay) pa.)) b) + of tr(02n11 + of tr(0)
v
It thus holds that nMd satisfies the Lokker-Planck Equation, and must hence be an invariant distribution.
2. The Fokker-Planck Equation associated with System (9) reads
0.14 = 2, ((-BVU(x) 4) (x, v))
Vy ((->VU(x) -oy) (x, v)) Aottt + Sntt
02
-1/b)
(VU(()) Me + + {
-1/b
=
1/bb
0g
by
1/6 oy
(1/0
-1/b)
V.
| V log aad + Voog uel Me
oy
(0)
-1/b
b4 p.a.
1/6
Vlog
14
As such, by Lemma C.1, we know that
d KL(Mellaeei)) -IEss
Hi
o
-1/6
V log
V
log
di
m0,5
1/b
dg
u4a.
=E,,
(
V Vllg log
H4
02
V
log
H4
0
2
0z) E
V
log
H4
(14)
In specific, if we assume a log-Sobolev incquality with coofficient P, we get
dt (L(H,1A < 22pmin(o2, KL (1
which, by Grönwall's Inequality, implies
(L ( S exp(-22min(o22 ot)t) KL (L (o
which means get convergence long as oz o > O.
C.2 Explicit Computations for Algorithm
We first note that we can rewrite System (11) in integral form as, for / [kh,, (k- 1)h),
8, = XRA -((t - (X + '' Y,ds + 2202 I' dB=
kh
(15)
--=e-ate -alt - 7 ----111-1 (1-6 (U(())) + 2202
c-a(t-s)dBB
kh
Conditionally on the initial condition (KAn. PEE), the process (X, Dan is an Ormstein-Uhlenber
process on [kh,, (k + 1)4).
From now on, in this subsection, we always work implicitly conditionally to (XRa, Yun).
In particular, L(XX, Y.) is Gaussian and remains compute the associated expectation and covariance matrix to fully characterize it.
18

---

Published in Transactions on Machine Learning Research (09/2025)
We thus compute
E|y.] e pntt-khjyp
7 (1- ((t vU(X)n);
a
from which we get that
B[X,] = Nuh- - 3(L (VL--h)VU(XAA. 1 aa(t-khi
? (1 e- (U((s))
Ven
a
a
a
Now note that the Brownian motion term for Y is 20 Skn e-alt-o)dBy, whereas the Brownian motion term for X, is
20 S" dB. + 2208 '" (" -alo- 5) dr = 22 I' dB, + 20
bh f e: ca(r- aal-s dBa
kh Jhh
kh
kh
= =202
dB² + 20
kh
kh
As such,
Cov (Ve, P.) = E [Y,
E(Pi))
= 20 E [ e e-a(t=s) dag f e-o(t- |]
(2 Is
= 20
kh
1 c 20(l-khh) la-
a
Moreover,
Cov (x,, =R
(X, P1)=
- (v: - (V-))) "]
(v00
dBT + v 20% / k/
--(((_))
dB3 (222g
I' -altto)d kh
=E
kh
(110 dB%) (/r e-a(L=s)
= 2 10203B
kn
+ y E (1r)
1 - c-(l- dB! ( e-a(tto)
hhh
20
-a(tt (1 -a(--s) - ds)) ds
la
a (sh
of(1 - aalt-hhh))
la-
19

---

Published in Transactions on Machine Learning Research (09/2025)
And, finally,
Cov Xx) = {Xx (X,- -((,)) (X, - -[(x,) |
E [V207 dB" + 2207 {"
a(t-a)
dB
kh
kb
a
a(t-ss)
22 khh
dBa + 20 kh
dB
a
1 -- -a(t-s)
(%/0
a((
20
mh
d
dB²t
+ 20
dB
dBy
kh
(
20y a²
(
20
ds
la
+
(1 (1- alt- e ol)
La
kh
20
dg
2a(t
kh) + 2allt
2a(t-kh) - -4(1 --a(t-hii)] la.
a
Selecting t = (k: + 1)h yields the wanted result.
C.3 Proof of Theorem 4.3
For completion, we introduce the following technical lemma:
Lemma C.2. Consider the -aluud random process (Z,) defined through
dZ, b(Zo)dtt + odW.,
with initial condition Zo vo for some vo )(TRd).. Then us L(Z+) is weak solution of
d.v. Live
where
- =
Σ (v((o)(()))) + 2 i,==
Σ Eas((oo")
Proof. Let us consider smooth realevalued function f. Then Ito's lemma together with the tower property of conditional expectation yields
d
+
E
Σ
+ Σ
((os)ii ds,
0
1,j
which reads
(ve - v)) L vs
Σ
d
(bjo
1 Σ +
(oo" )isoof ds.
:-=1
Let L be the differential operator such that
1 L,f - (o)(b)00 + Σ )ooT)isfsst
i-=1
Then
(p- = vs(Le))ds= = S' Liv.(fids,
and differentiating yields the wanted result.
20

---

Published in Transactions on Machine Learning Research (09/2025)
Given the parameters a, 1, dz og. b, p. L, we define
0 = p
c2 + +b-2)
mmin(o o.))
A = 12 2 + L2
(16)
12
4
+ 30 + 2 L
B = 20 +
b
We now introduce the more precise statement of Theorem 4.3.
Theorem C.3. Assume pad salisfies log-Sobolev inequality with conslant p. Assume (X,, V.) follows System (11), with initial distribution (Xo, Yo) Mo. Moreover, assume that
h < min ( 8
8p
(17)
Then it holds that
KI( 00h///2 = ( + Bhh,
(18)
and for all K 2 1,
KL(pxallee (xxp::llll)xx((((00000 [xxpp(-KK///))K[(i/lllel 3ßh
(19)
Proof. Choose h according to Equation (17), and fix some S h, such that System (11) reduces to
8, N - (b-BUU + S/" Y,ds + 20 f dB.
(20)
Y. = e -r0 - ? (1 a1- (1-(0) + / 20
(" e ((t-s) dB"
Denote by in the joint law of (Xe, P)). Note that in the above process, (Xo. Vo) is itself random variable, with joint law Pg- Denote by Poo the joint law of (Xo, Yo) and (X,, Yr), and by Poja the conditional law C((X,, {o), Y))).
Applying Lemma C.2 the process 7 = (8 implies that nr satisfies
a u V.
-1/b)
aatooe (VU)
iu + v
11/
d
by
(11)
-1/6)
[
(uVU(a)) by
(apoos (VU)) (VU)))(VUV,.)) -U(c)) in
log +
oy
(11)
-1 -1/b)
(apop (VU) - vU(co)] ar
V.
v
log
+
dy
uab
0
As such, the vector field given by
(1/
0
-1/b)
-
(vlog
me
aapooe (VU) -V(()))
2/ =
1/b
0y
+
21

---

Published in Transactions on Machine Learning Research (09/2023)
is tangent to (i,), and hence, by Lemma C.1, it holds that
(V)) - -V
-1/b)
Mr.
-Bp,
v log
v Vogg
+
dt
ua.
1/b
oy
4ea6
0
i
1/6
i4,
=-Epa -xa
V log
V uad
log
wab
1/b
y
02
-1/b)
(VU)
-
Ep.
V log
(21)
na.b
1/b
oy
0
H4
ua. )
Me
VVloo log
V
log
ua..
0
1/b)
Epo.
Vlog
1/b
o
min( Ø1 o
Fi(
[1(18
-1/00
(dIVU(8)) vu(x,))
+ 2min(o
E Po.t
(22)
o
where the final incquality follows by Young's Inoquality with coefficient min(o?, (inno??,0))) of). Now note that
Epo.i [1100
(0) - (dlVU(x)) - vU(X.)) -
-1/b)
|
do E, (Xx() VU(X))
< I + E Xo X.11.1.
As such, Equation (22) reads
d Kl(aillua.b) < min (in(o2200)
Fi(ūi, |1 ( + BT.., - X.112..
(23)
di
Now notice that, by the integral Equations (20) and Jensen's Inequality,
[IAUUUXO)) / ('Vdss + 220 L: d..
Ep, 1118
Xx1121 = Epo.
< 22 Epp [| +2 Ep., [1|\,1]] [|] ds + 20 L.
(24)
Now observe that, for Ç an optimal coupling between eo and n and for (Xa,, ya.b) ~ a.b
(VU VE VU(Xaa)] 21 2 /// (X(+)))))
< 2 ||| X, - , [2] + 2 2F VU (1
= 2 2 (U
(25)
22

---

Published in Transactions on Machine Learning Research (09/2025)
where Wo W2 (Mo: ).)))). Moreover, by denoting Za,b the normalization constant of y
// VU(x). (U
B [U(x)11
e
VU(x)- (x(x) al (4) drdy
Zu,b Jud
R2
VU(x). Ve at) drdy
Za,ba JRd
R2
1
blle1l
AU( at((a) dxdy
Zapba
E
JR.
Byso.h (AU(((a))
dL
(26)
a
where the third-to-last equality follows from integration by parts, and the final incquality follows from L-smoothness. Plugging this into (25) then yields
E (VX(() s 2 + 2dl
(27)
which, replacing in Equation (24), gives
E E
|1 - xx|1 s 25222
22 +
2dL + 2t / Epo.t [||8|] ds + 20 d. t.
(28)
By Equations (20)
11%/ vu((x)jrr 19/ + 600
111. -a(s dBP
E Pao
|| |
s pBp
||]6||]
+ Ip
< 6W + ,.,....
[||
+ 3- [|
+ +6o,d-s
6W + 6E na.b
[||a0]]]] + +3
2I.2Wo + 2dl.
+ 60
(29)
Now we realize that analogous computations to (26) give that
B y y d b
which, plugged into (29), yields, after rearranging the terms,
(72Ll 6d
Ep, || s 6W, (1 (1+ + 6 +
a + +
Returning to Equation (28), we obtain
Ep. [|x0 - x.11"] < 2
2T.2W, + a
2dL
+ 2d
2 1" (6W6 (1+ -²(²²²) + +67 + 6ds
d
(272Ls oz) 2 ds
2T. 2T + 2dL
2
+ 20
(Wo t+ 1,2333
6d
2d +3 2T
2t
+
3d 0002)
b
12t²
432 L
2
Wo
[126 1 + 4 12+ d
20
2 +
30
33
a
23

---

Published in Transactions on Machine Learning Research (09/2025)
Using that E h < 1 and recalling the notation defined in Equation (16), we obtain
Wo A. 2. + d B E E || x011
Combining the above with (23), obtain
KL (K(lalll min(o o²)
Fi( + W. A. +. B.t
dt
2
Applying a log-Son Sobolev inequality, we obtain
d (I(Ha1l - +TA W, -t +TB. d.
dt
Rearranging the terms yields
d KL(Aall = TA Wo E d.
_ e
di
As t $ h,
d at (L(pllle S TA Wo h22 + t BB h.
dl
which we integrate from 0 to h in i, yielding
0h -
0h
eh (KL( (L(HollAe)))
TA Wo h +
T B d. h
0
0
$ 2TA Wo h + 2TB d h2
where used e < 1 2c for 0 < < 1 for c= 0h. Using Talagrand's Inequality (Talagrand, 1996) and
denoting KLo KL(Ap u gives us that
oh ( - KLU I TA KL + 2
h22
This implies that
-0 KLo KLo 1+ -T 1/3
+ + 0h TB d h?
which implies (18), using (17) and the fact that In(x) S x for 0. Iteratively applying the result of (18), we obtain, where KL KL (ft (. for all k
KL S 01/2 KLK-1 +B11
20h/2 KL +(e 0h/2 + 1)h
K-1
S KKoh/ KLo +
Σ
kAh/2
BIe
k=0
which, by bounding the finite sum by an infinite sum and using e < 3e for << <<<< 1, yields (19).
for
24


Reviews:
[{"review_id": "op2lBu9rLM", "reviewer": "Reviewer_VURz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths***\n\n- The method makes sense and the writing is quite clear.\n- The method seems to perform decently well on the example.\n\n***Weaknesses***\n\n- While interesting, I believe that the strategy of sampling from a Gibbs measure to optimize non-convex functions has been well-known, and relates to annealing and other similar algorithms, as discussed in comparisons and related work. It is unclear to me why this particular architecture might do better.\n- It is not clear why just running the standard Langevin Monte Carlo to the Gibbs measure (with some well-chosen temperature) would not work here. Why do we want the high-resolution algorithm? It does not seem to clearly be better than the overdamped Langevin in practice. Furthermore, there are many possible tuning parameters, which makes the comparison unclear. Finally, what about Hamiltonian Monte Carlo methods?\n- While the high-resolution algorithm is interesting, the theoretical analysis strongly resembles that for the overdamped/underdamped Langevin and does not show any improvement in theory.\n- In the theoretical analysis, it seems important that the Gibbs measure has a good log-Sobolev constant. However, this is unlikely to occur when the function is non-convex. As a result, I do not find this theoretical result very compelling.\n- There should be more experimental results.\n\nOverall, I do not find the theoretical results to be too surprising or impactful. Nonetheless, the paper is well-written and rigorous.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method for global optimization of non-convex functions. It samples from the Gibbs measure associated with the function using a “high resolution Langevin dynamics”, which is new to this work. Theoretical guarantees are given when the Gibbs measure satisfies a log-Sobolev inequality, and it is assessed on an empirical benchmark.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Hopefully, my concerns have been clearly stated in the “Strengths and Weaknesses” section. \n- I think a clearer understanding of why the high-resolution algorithm is chosen would be important. Additionally, the authors should attempt harder to show theoretical improvements over other sampling algorithms.\n- The experimental results are narrow and hence unconvincing. I hope the authors can add more.\n\n** Minor typos **\nPage 3: exhibt -> exhibit\nPage 11: in specific -> specifically", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gboIZV8BUG", "reviewer": "Reviewer_4QFu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is a bit theoretically heavy for me but I follow the general argument and believe there are interesting results here. It would be helpful if some intuition as to what type of functions follow a log-Sobolev inequality, since the formal definition is obtuse (that the KL is bounded by a constant times the relative Fisher information). It would also help to give parameters informative names: e.g. a is an inverse temperature, epilson is an error tolerance (optimality gap?).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider global optimization of a nonconvex function U, under several assumptions on U, including a logarithmic Sobolev inequality on the Gibbs measure mu^ab \\propto exp(-aU-b||y||^2/2) for all a>a0. Assuming access to an approximation tilde{mu} which has KL divergence with mu^a less than epsilon^2/18, the simple \"optimization algorithm\" of taking the best of N samples from tilde{mu} gets close to the global optimum with high probability 1-delta. For actually sampling from tilde{mu} they propose \"high resolution Langevin dynamics\" which can be viewed as a SDE version of ODE-type continuous representations of optimization algorithms. They prove exponential rate convergence of both the continuous and discretized versions. Finally promising numerical results are presented on the Rastrigin function.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The numerical results are reasonable. Figures 1 and 3 should presumably be one figure. Although it doesn't connect as cleanly to the theory, it would be helpful to see something like the median error over runs as well as the probability of hitting a specific accuracy epsilon (e.g. as a supplemental fig). \n\nTables 1 and 2 have too many significant figures, and it is not immediately obvious that these are values of the objective function.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "E3JzBG905J", "reviewer": "Reviewer_WeR4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Generally well-written, logical structure, extensive related-work coverage.\n- Connects high-resolution ODE analysis (classically convex deterministic) with non-convex sampling, opening a new avenue for accelerated MCMC.\n- The finite-time probabilistic global-optimality guarantee is a novel approach as far as I am aware.\n\nWeekness:\n- Acceleration remains unproved: rates in Cor. 4.5 match, but do not beat, those of ULA/OLA; the main motivation of the paper leads to a plausibility argument.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes two key theoretical advances in nonconvex global optimization under a log-Sobolev inequality assumption: first, it introduces a modular “global optimization” meta‐algorithm that, by drawing $N$ i.i.d. samples from a Gibbs distribution $\\mu_a$, provably finds an $\\varepsilon$-accurate global minimizer of a smooth nonconvex $U$ with high probability.\n\nSecond, it proposes a novel “high-resolution” Langevin sampler both in continuous form (a noisy first-order system inspired by the accelerated deterministic ODE $ \\ddot x+\\alpha\\dot x+\\beta\\nabla^2U\\,\\dot x+\\gamma\\nabla U=0 $) and an exact Gaussian discretizatio that converges exponentially fast in KL divergence to the Gibbs target whenever $μ_{a,b}$ satisfies an LSI (Thm 4.2).\n\nTheir experiments on the Rastrigin benchmark, tested at dimensions 10 and 20, exhibit empirical convergence rates that align closely with the theoretical guarantees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Clarification needed: You assume a single constant $\\rho>0$ works for every Gibbs measure  \n Does it make sense that $\\rho$ (log-Sobolev constant) is independent of both $a$ and  $b$ (Gibbs measure parameters)?\n\nIf possible (not blocking): An ablation study isolating the effect of (i) inertia, (ii) Hessian-driven noise, and (iii) discretization bias so we really know which component is doing the “heavy lifting.”", "broader_impact_concerns": "The work is largely theoretical and methodological. No immediate ethical red-flags arise.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)