Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling

Ioannis Kontoyiannis; Sean Meyn

math.OCSep 5, 2026

Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling

Authors: Ioannis Kontoyiannis, Sean Meyn

Organizations: Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK · Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL, USA

Abstract

This paper addresses a fundamental question in non-convex optimization: How should a stochastic optimizer allocate computation between global exploration and local exploitation? We study this question in continuous time, using Langevin dynamics for global exploration and deterministic gradient flow for local exploitation. The simplest algorithm in this class is the best-state Langevin--gradient method: several Langevin trajectories explore the objective landscape, the best state encountered is retained, and a single gradient trajectory then refines this state to high terminal accuracy. Our main objective is to characterize the computational work required to achieve a prescribed accuracy with prescribed confidence. We develop low-temperature approximations for this probably approximately correct (PAC) work--accuracy tradeoff, both for the best-state method and for related Langevin schemes. Global exploration is governed by energy barriers, through spectral-gap and Eyring--Kramers asymptotics. The resulting approximations expose the competing effects of temperature, computational budget, and the number of exploratory trajectories, and quantify their dependence on the confidence parameter. In contrast, terminal accuracy is largely separated from global exploration: once a suitable region of attraction has been reached, gradient flow requires only $O(\log(1/\varepsilon))$ additional work to reach accuracy at least $\varepsilon$ . Numerical experiments on challenging objectives serve to compare algorithms and to test the quantitative predictions of the asymptotic theory. They identify regimes in which the low-temperature approximations provide useful guidance, as well as regimes exhibiting substantial temperature sensitivity and potentially significant high-dimensional limitations.

Figures & tables

Figure 1: Representative sample-path comparison for the modified six-hump camel objective. The value $\uprho=1$ was used in $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ to obtain good visibility of the trajectory–a larger value is much more effective in this example, especially combined with $N>1$ .

Method	Prior information used in sufficient PAC conditions	Information needed online
SimA	A sufficiently large upper bound on the dominant energy barrier $E^{\bullet}$ to select the cooling constant.	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ , together with the prescribed cooling schedule.
$\textsf{L}_{\uprho}$	An upper bound on $E^{\bullet}$ for conservative selection of temperature and simulation time.	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ .
$\textsf{L}_{\uprho,N}$	As for $\textsf{L}_{\uprho}$ , together with the chosen number $N$ of independent trajectories.	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ .
$\textsf{LG}_{\uprho,N}$	An upper bound on $E^{\bullet}$ , a lower bound on the attraction margin $\eta$ , and conservative local convergence constants $c_{\mathcal{S}},\upmu_{\mathcal{S}}$ .	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ ; the deterministic switching time is fixed in advance, so no online test for membership in $\mathcal{S}$ is required.
$\textsf{LG}_{\uprho,N}^{\textsf{\tiny FE}}$	For a finite-time PAC guarantee, quantitative information controlling the hitting time of the target region, together with local convergence constants.	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ , together with an online test for entry into the switching region.
$\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$	An upper bound on $E^{\bullet}$ , a lower bound on the attraction margin $\eta$ , and conservative local convergence constants.	Evaluation of $\Upgamma$ and $\nabla\Upgamma$ , together with storage of the state having lowest observed objective value. No online test for membership in $\mathcal{S}$ is required.

Table 1: Prior information required by the Langevin-based schemes. The second column lists quantities used in sufficient conditions for a finite-time PAC guarantee; the third lists information required to run the algorithm.

Figure 2: Failure probability as a function of work for the six-hump camel objective using

\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}

with

\uprho=24.5

and

N=24

Figure 3: Empirical performance of two best-state Langevin–gradient methods for the modified six-hump camel objective. The left hand side shows results for $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ and the right hand side $\textsf{LGS}_{\uprho,N}^{\textsf{\tiny RM}}$ , each using $N=24$ .

Figure 4: Contour plots of the six hump camel function ( 46 ) and the curve

\{x:h_{2}(x)=0\}

with

h_{2}

the second eigenfunction of the differential generator when

\uprho=0.2

Figure 5:

\textsf{LG}_{\uprho,1}^{\textsf{\tiny FE}}

for the six hump camel function ( 46 ). Shown on the left is a plot of the excess cost with

\uprho=0.2

. The time

\tau_{\eta}

indicated in the figure is ( 20 ) using

\eta=0.5

. Shown on the right is the associated trajectory of

X_{t}

, along with level sets of the objective: The outlines of two convex regions shown in the figure indicate the boundaries of the two connected components of

\mathcal{S}

Figure 6: A repetition of the experiment illustrated in Fig. 5 using

\uprho=10

, resulting in entry to

\mathcal{S}

at approximately

\tau_{\eta}=0.1

Figure 7: Empirical distribution of

\tau_{\eta}

with

\uprho=10

Figure 8: The logarithm of the spectral gap for the six hump camel along with two approximations.

Figure 9: A single run of $\textsf{LG}_{\uprho,1}^{\textsf{\tiny FE}}$ for the Rastrigin objective in dimension 2.

Figure 10: Empirical performance of two best-state Langevin–gradient methods for the Rastrigin objective in dimension 2. The left hand side shows results for $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ and the right hand side $\textsf{LGS}_{\uprho,N}^{\textsf{\tiny RM}}$ , each using $N=24$ .

Figure 11: Empirical performance of the best-state Langevin–gradient scheme $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ for the Rastrigin objective in dimension 2, with $N=300$ .

Figure 12: log spectral gap and approximations.

Figure 13: Zero sets of two linearly independent eigenfunctions associated with

\lambda_{2}=\lambda_{3}=-\textsf{{r}}_{\!\uprho}

Figure 14: Representative sample path from simulated annealing for the Rastrigin objection with dimension

d=2

Figure 15: Empirical performance of $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ for the Rastrigin objective. The left hand side shows results for $d=5$ and $N=24$ . The right hand side displays results for $d=10$ with $N=300$ , and in addition a plot of the realized work for a smaller range of temperature, minimized over a range of $(N,T)$ for each $\uprho$ in the selected range ( 52 ).

Figure 16: Representative sample-path of simulated annealing for the Griewank objective function in dimension $d=2$ .

Figure 17: Representative sample-path of simulated annealing for the Griewank objective function in dimension

d=2

Figure 18: Empirical performance of $\textsf{LG}_{\uprho,N}^{\textsf{\tiny RM}}$ for the Griewank objective in dimension 2.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 19: One-dimensional Rastrigin potential

g(z)=10+z^{2}-10\cos(2\pi z)

, with dominant one-dimensional barrier is

E^{\bullet}_{1}=g(s)-g(m)

. The global minimum is at

z=0

, the first neighboring local minima are at

z=\pm m

, and the intervening local maxima are at

z=\pm s

Explore similar work

Mar 6, 2026

Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging

Significant recent work has studied the ability of gradient descent to recover a hidden planted direction

θ^\star \in S^{d-1}

in different high-dimensional settings, including tensor PCA and single-index models. The key quantity that governs the ability of gradient descent to traverse these landscapes is the information exponent

k^\star

(Ben Arous et al., (2021)), which corresponds to the order of the saddle at initialization in the population landscape. Ben Arous et al., (2021) showed that

n \gtrsim d^{\max(1, k^\star-1)}

samples were necessary and sufficient for online SGD to recover

θ^\star

, and Ben Arous et al., (2020) proved a similar lower bound for Langevin dynamics. More recently, Damian et al., (2023) showed it was possible to circumvent these lower bounds by running gradient descent on a smoothed landscape, and that this algorithm succeeds with

n \gtrsim d^{\max(1, k^\star/2)}

samples, which is optimal in the worst case. This raises the question of whether it is possible to achieve the same rate without explicit smoothing. In this paper, we show that Langevin dynamics can succeed with

n \gtrsim d^{ k^\star/2 }

samples if one considers the average iterate, rather than the last iterate. The key idea is that the combination of noise-injection and iterate averaging is able to emulate the effect of landscape smoothing. We apply this result to both the tensor PCA and single-index model settings. Finally, we conjecture that minibatch SGD can also achieve the same rate without adding any additional noise.

Stanley Wei, Alex Damian, Jason D. Lee

Princeton University · Harvard University · University of California, Berkeley

Langevin Dynamics Single-Index Models

Ask PDF

Oct 5, 2026

Sharp dimensional analysis of midpoint methods for Langevin sampling

We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target

π\propto e^{-V}

, where

0 \prec αI\preceq\nabla^2V\preceqβI

and

κ=β/α

. To achieve

\sqrtα\,W_2\leqslant\varepsilon

, we show that deterministic Heun uses at most

\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3})

gradient queries, and underdamped exponential midpoint uses

\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2})

. The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings. At bounded condition number, a lower bound matches the

d

and

\varepsilon

powers of both deterministic methods. To contrast, for the randomized midpoint methods and Poisson midpoint with at least two grid points (both overdamped and underdamped variants), a simple Gaussian calculation yields a lower bound

d^{1/3}\varepsilon^{-1/3}

to get an

\varepsilon

-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.

Fan Chen, Sinho Chewi, Jianfeng Lu +1

Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1

Markov Chain Monte Carlo Stochastic Differential Equations Langevin Dynamics Sample Complexity

Ask PDF

Mar 3, 2026

LAGO: A Local-Global Optimization Framework Combining Trust Region Methods and Bayesian Optimization

We introduce LAGO, a LocAl-Global Optimization framework coupling Bayesian Optimization (BO) and gradient-based trust region local refinement through an adaptive competition mechanism for smooth expensive-to-evaluate objective functions with available gradients. At each iteration, global and local optimization strategies independently propose candidate points, and the next evaluation is selected based on predicted improvement. LAGO separates global exploration from local refinement at the proposal level: the BO acquisition function is optimized outside the active trust region, while local candidates are proposed within the trust region. Points in the vicinity of the accepted local step are incorporated in the global GP dataset only when satisfying a lengthscale-based minimum-distance criterion, hence reducing the risk of numerical instability during local exploitation. LAGO enhances BO with efficient local refinement when reaching promising regions, and reverts to exploratory behavior when local steps are not competitive.

Eliott Van Dieren, Tommaso Vanzan, Fabio Nobile

Institute of Mathematics, EPFL, Lausanne, Switzerland · Dipartimento di Scienze Matematiche, Politecnico di Torino, Turin, Italy

Black-Box Optimization Bayesian Optimization Trust-Region Optimization

Ask PDF