Local Entropy Search over Descent Sequences for Bayesian Optimization
Authors: David Stenger
Armin Lindicke
Alexander von Rohr
Sebastian Trimpe
Venue: ICLR 2026 Poster (2026)
Keywords: Bayesian Optimization
Entropy Search
Local Bayesian Optimization
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: Local Entropy Search is a Bayesian optimization algorithm that reduces uncertainty over an optimizer’s descent path, enabling sample-efficient local search for high complexity problems.

Abstract: Searching large and complex design spaces for a global optimum can be infeasible and unnecessary. A practical alternative is to iteratively refine the neighborhood of an initial design using local optimization methods such as gradient descent. We propose local entropy search (LES), a Bayesian optimization paradigm that explicitly targets the solutions reachable by the descent sequences of iterative optimizers. The algorithm propagates the posterior belief over the objective through the optimizer, resulting in a probability distribution over descent sequences. It then selects the next evaluation by maximizing mutual information with that distribution, using a combination of analytic entropy calculations and Monte-Carlo sampling of descent sequences. Empirical results on high-complexity synthetic objectives and benchmark problems show that LES achieves strong sample efficiency compared to existing local and global Bayesian optimization methods.

Published as a conference paper at ICLR 2026
LOCAL ENTROPY SEARCH OVER DESCENT SEQUENCES FOR BAYESIAN OPTIMIZATION
David Stenger', Armin Lindicke' Alexander Rohr², Sebastian Trimpe'
'Inttitute for Data Science in Mechanical Engineering, RWTH Aachen University, Germany 2I Learning Systems and Robotics Lab, Technical University of Munich, Germany (david. stteggr,,, trimpe @ddme rwth-aachen. de, ?[alex. von. rohr @ttum
ABSTRACT
Searching large and complex design spaces for a global optimum can be infeasible and unnecessary. A practical alternative is to iteratively refine the neighborhood of an initial design using local optimization methods such as gradient descent. We propose local entropy search (LES), Bayesian optimization paradigm that explicitly targets the solutions reachable by the descent sequences of iterative optimizers. The algorithm propagates the posterior belief over the objective through the optimizer, resulting in a probability distribution over descent sequences. It then selects the next evaluation by maximizing mutual information with that distribution, using combination of analytic entropy calculations and Monte-Carde sampling of descent sequences. Empirical results on high-complexity synthetic objectives and benchmark problems show that LES achieves strong sample efficiency compared to existing local and global Bayesian optimization methods.
INTRODUCTION
Many practical optimization problems can be solved to the desired accuracy by relying solely on iterative search strategies such as gradient descent, quasi-Newton methods, or evolutionary algorithms. These methods do not necessarily discover global minimizer, but refine the current solution. Local optimization has repeatedly demonstrated its effectiveness in finding good solutions particularly in high-dimensional and complex search spaces. Indeed, gradient-based methods remain state-of-the-art for solving extreme-scald problems such as training deep neural networks with billions of parameters (Chowdhery et al., 2023). However, those local optimization methods cannot directly be applied to expensive-to-evant to-ellluae black-box functions due their poor sample-efficiency.
Bayesian optimization (BO) (Garnett, 2023) methods are popular for expensive-tue toressive-to-evllatee black- box functions, yet they typically aim to minimize regret relative the global optimum. Global search requires reducing uncertainty across the entire domain, which can be intractable in large and high- dimensional spaces (Hvarfner et al., 2024; Xu et al., 2025). Thus, the emphasis global search in BO stands in contrast to the demonstrated effectiveness of local optimization for complex problems.
We introduce local entropy search (LES)), an informatiion-hhorree framework for local BO that transfers the idea of iterative local optimizers to the expensive-to-evaluut black-box setting. LES explicitly targets the solution obtainable by an iterative optimizer starting from an initial design. LES propagates the uncertainty of Gaussian process (GP) surrogate through the local optimizer, yielding a distribution over the descent sequence and the local optimum (see Fig. 1). At each iteration, LES chooses the next evaluation to maximize the mutual information with the distribution over the descent sequence, thereby reducing its uncertainty.
While several recent efforts (see Sec. 1) have brought local strategies to BO framework, acquisition functions have so far provided only partial use of the iterative descent structure or have focused on special cases. Our approach builds directly entropy search principles (Hennig & Schuler, 2012) but shifts the focus from the global optimum to the reachable local optimum as defined by the optimizer's descent trajectory.
"oode available hhtp://wwh.nn.aaaacecccecc.ceeea

---

Published as a conference paper at ICLR 2026
Deterministic:
Prior
Posterior
GP Samples
Local Optima
Descent Sequences
20
Figure 1: Distribution over Descent Sequences: Left:: Local optimization on the unknown objective function. Middle: The prior over the objective function induces a belief over descent sequences. Right: After sampling data points the distributions over descent sequences and local optimum approach the deterministic ones. In LES the next query minimizes the entropy of the descent sequences.
To ensure tractability, LES combines analytic predictive entropy calculations with Monte-Carie conditioning over sampled descent sequences. We evaluate LES against state-of-the-arr local and global BO methods on dimee--aimesiioall synthetic objectives with varying complexity and policy search tasks. LES achieves lower simple and cumulativv regret with fewer evaluations especially in high-complxxity tasks. In summary, our contributions are:
We formulate local entropy search (LES) as an information-theorede Bayesian optimization paradigm that targets the terminal iterate of an arbitrary optimizer, making LES the first entropy-basee based approach explicitly focusing on local optima rather than the global optimum. We present computationally lightweight instantiation of LES as an active learning problem over descent sequences by propagating the posterior belief through the optimizer via Monte-
Carlo approximation based on efficient GP sampling (Wilson et al., 2020).
We provide empirical evidence that this LES instantiation surpasses both global entropy- search baselines and existing local BO methods on high-complexity benchmarks.
In addition, adapt recent stopping criterion for BO (Wilson, 2024) the LES setting, guarantee- ing a probabilistic local regret bound (see Appx. E).
2
PRELIMINARIES
In this section, we discuss the related work on local BO and entropy search and briefly introduce GPs and analytical approximation of their sampling paths.
2.1 RELATED WORK
Bayesian optimization is a popular method for many challenging real-world applications such as AutoMI. (Barbudo al., 2023), drug discovery (Colliandre & Muller, 2023), and policy search (Paulson et al., 2023). For a recent introduction and overview see (Garnett, 2023). Below we present related work in entropy search and local BO the two BO subfields most relevant LES.
Entropy Search Global entropy search acquisition functions use an information-thherrtiic perspec- tive to select the next BO query point (See Appx. A for a detailed introduction).. They find a point that maximizes the expected information gain about properties of the global optimum. The original entropy search (ES) (Hennig & Schuler, 2012) and predictive entropy search (PES) (Hernández- Lobato et al., 2014) maximize the information gain about the location of the optimum. max-value entropy search (MES) (Wang & Jegelka, 2017) maximize the information gain about the function value of the optimum. MES is computationally more efficient than both ES and PES. Joint entropy search (Hvarfner et al., 2022; Tu et al., 2022) maximizes the information gain about the joint distribution of location and function value of the optimum. Entropy search has been extended to constrained (Perrone et al., 2019), multi- muuli-oojecctive (Belakaria et al., 2020), and multi multi-fideliyy (Marco et al., 2017) optimization. With LES we propose the first local version of entropy search by targeting local optimum instead of global one.
contrast,
2

---

Published as a conference paper at ICLR 2026
Local BO There are two main approaches commonly used for local BO, trust regions (Akrour et al., 2017; Fröhlich Lukas P. et al., 2019; Eriksson et al., 2019) and line search (Kirschner et al., 2019; Müller et al., 2021; Nguyen et al., 2022: Wu et al., 2023; Fan al., 2024). Trust-region BO such as TuRBO (Friksson et al., 2019) explicitly maintain a subset of the search space X' and restricts queries be within this subset. In contrast, BÓ methods based on line search maintain incumbent solution and iteratively choose search direction and step size to improve the candidate. For example, gradient information BO (GIBO) (Müller al., 2021) leverages the GP model of the objective's gradient f to find its search direction and step size. Similar to these methods, LES starts its search from an incumbent solution but contrast GIBO and its variants does not use the learned gradient to update it but instead learns about the entire descent sequence. The local BO methods above have been shown to outperform global BO methods in high-complexity tasks.
Recent works showed that vanilla Bayesian optimization can solve high-dimensional problems if model complexity. specifically length scales of the GP kernel, is chosen appropriately (Hvarfner et al., 2024; Xu al., 2025). While assumed model complexity is an important consideration for BO, the design of suitable prior assumption can benefit local and global BO methods and the acquisition strategy is mostly orthogonal. In Section 6, we show empirically that local BO and especially LES outperforms global BO for complex and nigher-dimensional tasks.
2.2 GPS AND EFFICIENT POSTERIOR GP SAMPLING
In this paper, BO uses a Gaussian Process (GP) (Rasmussen Williams, 2006) as a fast-to-evaluate probabilistic surrogate for the unknown scalar function f(x). We denote GP as
p(f) = GP(ff k).
(I)
where μ : X + R the prior mean and k X' X' + R the prior covariance function, with ((x) = (xr) w=). k(#, x') = [(([(x) ((==)) plxx)),
where E is the expectation. Without loss of generality. we assume ,(xx) = O. Given a dataset of noisy observations y(œ) = f()) + Et, where the noise realization E, is modeled as a draw from normal distribution (0, o²)), denoted as D, = { v1), (1)) the posterior belief over a function value (x) a normal distribution denoted as
p(f(x) Da) N (f( D.), D.))
Here, we denote p(æ D:) as the posterior mean and A( x' De) as the posterior covariance between two points and x'. The predictive variance for a noisy observation is oz(2x (ac D.)
k( x D.) + of See (Rasmussen & Williams, 2006) for details on GP regression.
To draw samples from the posterior distribution of objective functions p(J DD)) we follow the analytical approximation proposed by (Wilson et al., 2020) that relies on Matheron's rule (Journel Huijbregts, 1978) (see Appx. C.I). We denote Jt as sample from p( Dr):
AO Σ wlde())
Σ (yk((,
weight- prior
function-space update
where wa are randomly drawn weights, (.(-) are basis functions and ey is calculated from the training- data covariance matrix. The sample approximations of (4) are analytic which means we can easily differentiate with respect to æ and apply iterative optimizers such as gradient descent. LES can be applied to other probabilistic models from which we can efficiently draw posterior samples, e.g., variational Bayesian last layer models (Brunzema et al., 2024).
3 PROBLEM STATEMENT
The local black-box optimization problem is to find the best reachable solution from given initial
design æo
given Tu X, find x
arg min f(x), =
(5)
3

---

Published as a conference paper at ICLR 2026
where f + R is the black-box objective function and X (æo) is some neighborhood around Zo-
We consider local optimization where an iterative (and possibly stochastic) optimization routine O generates sequence of iterates the descent sequence converging to local optimum x' as
Ozo F(X) - X Ono (J) = (zo = 2o, 21, 21....) C X
(6)
where
x lim Zn. 7=000
(7)
or xx = NN for finite descent sequences. We assume that the chosen optimizer converges for all sample paths of the GP prior (I). For instance, under suitable assumptions, gradient descent with an appropriate step size produces the convergent sequence
GD zz (f)
(2 Zu, 20 V (zo), 22 21 1 (Z)()))
(8)
When f is known we can directly apply O. However, we are in the standard BO black-box setting, where we cannot directly create this sequence. We instead consider the bandit setting with sequential queries to an expensive-lo-evaluate black-box function with noisy zero-order evaluations y/+ = fxxx +r at locations æ;. Therefore, the objective of this work is to find a practical strategy that best approximates the solution to (5) in a data-efficient manner by learning about the descent sequence.
ENTROPY MINIMIZATION OF UNCERTAIN DESCENT SEQUENCES
Overview. We aim apply the entropy search principle not to the global optimum but to the descent sequence started from Zy. Goal: Choose the next query x that most reduces uncertainty about the entire descent sequence starting from Tu, i.e., the sequence generated by an iterative optimizer O. Once we know the descent sequence, we also know the local optimum x". Idea: Treat the descent sequence itself the object of interest and apply the entropy-seare maximize information gain about that sequence. We target the mutual information between (æc, y(x)) and the random descent sequence induced by the GP posterior and O. The remainder of this section formalizes this idea. After the formalization we give practical algorithm in Sect. 5.
principle it: select to
Given p(f) distribution over functions, applying an optimizer O from Do induces random descent sequence with observations R, as
Qun ((zo, Ro), (21, R1)....)
where nn are iterates and Rn are some observation of the objective function / at x depending on O. Examples are function values R. == f(2n) (e.g.. hill climbing) gradient information RS == fzn) (c.g. gradient descent). Reducing the uncertainty about Qm, also reduces uncertainty about the local optimum xt (see Fig. 1).
To apply the entropy search framework (Hennig Schuler, 2012) to this problem, we minimize the entropy H(Qzp) of the descent sequence. Minimizing the entropy with new observation is equivalent to maximizing the mutual information between the new observation (x, (z)) and the descent sequence Qte, conditioned on the current data D,, Therefore, in LES reduce entropy over Qay by selecting queries that maximize mutual information with this distribution, as
(1) = / ((æ, y())); Qao D:).
(10)
which we reformulate into tractable form in Sect. 5. Note, that the observations R needs to contain the information the iterative optimizer requires to determine the next iterate. Therefore, (10) requires knowledge about the inner workings of the iterative optimizer to determine Q. We will discuss the case of gradient descent sequences as an example at the end of this section.
Remark 1. An alternative formulation for LES is to define the random variable O" directly over the local optimum xx of Oz., (f). The distribution of O is the push-forware of p(f) under Oz, and taking the limit as in (7). Unfortunately, the mutual information
2g
I ((æ, v())); 0%, Di))
(11) no x
not tractable in the general case since we would need to condition GP on the event O which involves the entire descent sequences (see Appx. B.1). We propose and evaluate an alternative approximation in Appx. F.2.
A tractable special case is gradient descent that terminates after the first step. The resulting acquisition function is GIBO (Müller et al., 2021) with entropy instead of the trace of the covariance matrix (see Appx. B.2).
4

---

Published as a conference paper at ICLR 2026
d)
0.0
1.0
-1.2
0.5
224
0.0
0
0
14
Evaluations
Samples
Estimated optimum
Local optituua distr.
Objective
Best observed
Convergeuce likelihood
Illustration of LES 2D example: a) After three initial evaluations, the distribution over reachable local optima wide. b, c) As LES selects new points, evaluations concentrate near the descent sequence, and the distribution of the local optimum narrows. d) Convergence behavior of LES. After 14 evaluations, the convergence criterion (see Appx. E. stops the optimization.
Figure 2:
Local Entropy Search with Gradient Descent Sequences. Before we move on to the next section, we discuss the LES acquisition function for the gradient descent algorithm. The descent sequence is defined through the initial design Zu and the gradient of the function f at the locations 2n as
2;-1 7/ V/
with žg = zo. (za 2a) converges, then x: 2n + lim, E V
Since we can easily condition GP on gradient information (Rasmussen & Williams, 2006) a LES acquisition function for local optimization via gradient descent is
CLES-GD(2)) with Qmo ((zo Zg. Vz(z))), (z1, Vf(z)).....) In words: We are looking for the query whose outcome will reveal the most information about gradients of the function at the (distribution of) locations the descent sequence. Generally, the design the sequence Qzg is dependent on the optimizer choice O and the properties of the GP samples (see Appx. C.2). The performance and computational burden of LES depends on the design choices. We investigate alternative choices for gradient descent in Section 6.
y(=)) Qao (D)).
(12)
Remark 2. For GPs with squared exponential kernel the purh-forward of gradient-descen dense in X. This means, in principle, there can be sequences arbitrarily close to any point in the domain and no region is priori "forbidden." In addition, all descent sequences possible under this prior. For details, see Appx. G.2.
sequeeneeeeeeeeess sequences
LOCAL ENTROPY SEARCH
This section casts the general local entropy search paradigm (Sec. 4) into practical algorithm; see Fig. 2 for illustrative example and Algorithm 1. We first derive the acquisition function (Sec. 5.1), afterwards we describe how to approximate the distribution gradient descent sequences and how to condition on them (Sec. 5.2).
5.1 THE LES ACQUISITION FUNCTION
The LES acquisition function follows the entropy-search principle: ask where an observation (x, v(x)) would tell us most about the optimizer's descent sequence Qa. their mutual infor- mation. In practice this means comparing two entropies: (i) the predictive entropy at æ, which measures the overall uncertainty about yar) under the GP, and (ii) the expected entropy that remains if we condition on how æ would influence the descent sequences drawn from the GP posterior.
CLES = 7 ((xr, ()x)) (a:)); Qano De))
H))()) D. Es H (v( Des Quall
(13)
predictive entropy
conditional entropy
The predictive entropy (see Fig. 3, b)) can be calculated in closed form,
1
H (x)
D 2
log (2 e 2z D.)).
(14)
5

---

Published as a conference paper at ICLR 2026
Predicted mean
Predictive entropy
Info, gain & =
Info. gain 2:
Info, gain & 250
High
Observations
Samples
Descent sequences
Figure 3: Illustration of the LES acquisition function after three evaluations: Left: The GP posterior mean after conditioning on the observations. Second: The predictive entropy is high in regions with large posterior variance. Third to fifth: The information gain between sampled descent sequences and query locations in X' (the LES acquisition function) high at points that are far from existing observations and aligned with likely descent sequences.
The expectation over the conditional entropy more challenging. We do not have a closed form expression of the distribution of Qæo this would mean apply the optimization routine O to the distribution pl ())). Thus, we cannot analytically calculate the expectation from it. Therefore, we approximate it L Monte-Carlo samples:
By [ (v(x) Dr, 2
Σ H (p(((()) De (mn))
(15)
L
To approximate Qay first draw L sample paths from the posterior GP according to (4) retrieve samples fi..... fi,..., f! Then we apply the optimization routine O to each sample to retrieve the descent sequences Q ((=b: Ro), (2) Ri);-.) and the local optima a!.*.
For example, in the case of gradient descent, (wo)), (zl = Fo (xo)), R = V)'( ((=) = =o, Ry of
get
Q
To condition on the parameter observation pairs Q'zg. we add them to the already existing observations and analytically compute the predictive posterior variance and entropy. Note that approximate
20 with a finite sequence to compute (15) (see Sec. 5.2). By inserting (14) and the approximation
(15) into (13) get the final LES acquisition function (see Fig. 3):
L log (2 (æ D. D.UQL.))
1 (LES(x) log (2 D.))
Σ
(16)
Extension of the LES acquisition function the batch case is straight forward (see Appx. C.3).
Algorithm Local Entropy Search with stopping rule
I: Input: initial design and corresponding observation D; (#o, Jo), local optimizer for 2.... do
3: gP, +- fit GP model of f(x) using D, with MAP hyperparameter optimization
fc +- identify current optimum from D: fl f!....,j'' + draw I. samples from GP;
5:
b cf. (4)
6:
for E L...,, Q' apply O to I' starting from #7
L
7:
#141 argmax
for 1,..., do .4 wwt.ae.......................... am.
Maximize LES acquisition function ef. Sec. 5.1 Estimate local regret
8:
(at) (mx
9:
if I (r]
kimax do stop
b Stopping rule for probabilistic regret. See Appx. E.
10:
Me+1 evaluate objective with æ++1
D < U
12:
end for
13: return "'

---

Published as a conference paper at ICLR 2026
Within Model Comparison
d= 10
d 20
30
50
0
2
Out of Model Comparison
169
0
100
200
0
200
400
0
200
400
200
400
Evaluations #
LES (ours)
loghl
TuRBO
Sobal random
MES
logEI-DSP
HCI CCB-GIBO
Figure 4: Optimizing Gaussian Process Samples: Median, 25-, and 75-percent quantiles for the best function values found for 20 sampled objective functions with medium complexity (see Tab. 1). LES outperforms baselines as dimensionality increases.
5.2 ADDITIONAL APPROXIMATIONS AND IMPLEMENTATION DETAILS
To make LES practical algorithm we introduce additional approximations and design choices. For hyperparameter values, we refer to Appx. D.1. To solve the original problem (see Sec. 3) need to apply the local optimizer from a fixed initial design æn- However, in practice, we always start the descent sequence from the current best guess क;. Additionally, instead of ensuring convergence of the local optimizer, we simply stop all the iterative optimizers after finitely many steps. Still, conditioning on all elements in Q! can be prohibitively expensive. Thus, we choose to only condition P equally spaced elements along the interpolated descent sequence. Additionally, we condition on function values instead of gradient observations which reduces runtime while achieving similar performance (see Appx. D.5). Optimizing any acquisition function is challenging in high-dimensions it non-convex (see Fig. 3). Fortunately, the approximation of Qm, gives access promising candidates. Thus we optimize the acquisition function under the finite candidate set Q2, Q with L times P candidate points.
Practical LES in paragraph (i) Draw L posterior GP samples. (ii) For each sample, run O for a finite number of steps starting at the current incumbent é to obtain a descent sequence; discretize each sequence P support points. (iii) Compute the predictive entropy candidate and the average conditional entropy after conditioning on those discretized sequences; their difference the acquisition function in (16) (Fig. 2). (iv) To keep optimization tractable, maximize the acquisition over the finite candidate set given by the union of all discretized sequences. (v) Evaluate, update the GP, and repeat (Alg. 1).
EMPIRICAL RESULTS
In this section, we empirically evaluate LES and compare it against other local and global BO variants (additional results in Appx. D). As objectives, GP-samples with varying lengthscales to increase complexity as well as synthetic and application-oriented benchmarks.
6.1 ABLATIONS AND BENCHMARK ALGORITHMS
LES Variants We evaluate LES with three local optimization algorithms: gradient descent, ADAM (Kingma & Ba, 2015), and covariance matrix adaptive evolutionary search (CMA-ES) (Hansen
7

---

Published as a conference paper at ICLR 2026
Table 1: Within-Model Comparisons: Median final objective for LES, logEI, TuRBO, and Sobol
random sampling. Bold indicates performance not statistically significantly below the best. "Hyper- prior as in (Hvarfner et al., 2024).
Complexity
Method
d=
5
d =
10
20
30
50
high: p(l; d) logn( 2.5v + logv v3/5)
LES (ours)
-2.8
-4.8
-7.4
-9.0
- -10.8
logEl
-3.9
-4.4
-2.9
-3.2
-2.9
TuRBO
-3.5
-4.8
-7.2
-8.0
-7.1
Elp(t; 50)] 0.25
Sobol random
-2.4
-2.7
-2.8
33.2
-3.0
LES (ours)
-2.9
-4.4
-7.3
8.6
-00.4
medium: p(4; d)
logEi
-3.6
-5.3
-7.1
-8.4
-9.6
( 22.0 + logv d, v3/4)
TuRBO
-3.1
-4.8
-7.0
8.5
-7.9
E[p(t; 50) 0.52
Sobol random
-25
227
-28
-2.9
-2.7
LES (ours)
-2.1
-3.7
-5.5
6.8
-8.8
low: p(I; d)
logE1
-2.9
-4.1
-5.8
6.66
8.5
logn( 11.02 logvd, v3/2)
TuRBO
-2.4
-3.6
-5.5
6.5
-8.1
E[p(I; 50) = 2.65
Sobol random
-2.0
-23
-29
2.8
-3.0
extremely low*; d(l;d)= d)=
LES (ours)
-0.6
-0.8
-1.
-1.5
-3.0
logEl
-0.6
009
-.3
-15
33.0
logn(1.0v/2 log/d.
TuRBO
-0.6
-0.8
-12
-1.5
-2.8
E[p(I; 50)] = 96.2
Sobol random
-0.5
-0.7
-.0
-.0
-1.5
& Ostermeier, 2001). Results show that LES-ADAM and LES-GD perform best depending problem complexity, while LES-CMA-ES shows more global search behavior which is beneficial for low dimensional problems (see Appx. D.7). Additionally, acquisition function approximation (higher L and P), the better the performance at the cost of higher runtime. Below, investigate LES-ADAM with medium approximation accuracy resulting in average runtime of 17.8 sec per iteration in 50 dimensions excluding hyperparameter optimization (see Appx. D.5 for runtime comparisons).
show that the
accurate the
Baselines We compare LES-ADAM to other local BO paradigms: TuRBO (Eriksson al., 2019) is based on trust-regions and high-confidence improvement Bayesian optimization (HCI-GIBO) gradient-based approach. HCI-GIBO (He et al., 2025) extension. As global ES alternative we choose max max-value entropy search (MES) (Wang & Jegelka, 2017). Additionally, we compare to logEl (Ament et al., 2023) and Sobol random sampling.
recent GIBO (Müller et al., 2021)
Theoretic Strategies We propose and evaluate two other search strate- gies as special cases of the LES paradigm: local Thompson sampling and conditioning only on the final point of the descent sequence. They empirically perform worse confirming that conditioning on the whole sequences and Monte-Carlo sampling (see Appx. F.2).
Other Local Information- Information-Thhorrtiic
6.2 GAUSSIAN PROCESS SAMPLES
Model Complexity Recent work by (Hvarfner al., 2024) highlights model complexity key factor in high-dimonn ligh-dimensional BO performance. The assumed difficulty of the problem encoded through the model complexity the form of length scale priors deetermines global BO performance. Smaller length scales yield more complex functions with more local optima (Adler, 2010, Chapt. 6). Building on this insight, we construct benchmark functions with varying problem difficulty by sampling functions from a GP with different model complexities. Specifically, we generate functions by scaling the log-normal length scale prior p(l) proposed (Hvarfner et al., 2024). We consider four complexity levels across 5 to 50 dimensions (see Tab. where the lowest model complexity corresponds to the one used in (Hvarfner et al., 2024).
Within Model Comparison To assess the performance of the proposed acquisition function independently of the effects of hyperparameter optimization, first use known hyperparameters in all evaluated BO algorithms. Results on medium model complexity (Fig. 4) show that, after 400 evaluations, LES outperforms all baselines dimensionality increases. The asymptotical
8

---

Published as a conference paper at ICLR 2026
Table Out-Or-Model Comparisons: Median final objective for LES, logEI-DSP, TuRBO, and
Sobol random sampling. Bold indicates performance not statistically significantly below the best.
Complexity
Method
5=5
d
10
d =
20
d=
30
d
50
high: p(1; d)
LES
-29
5..0
7.2
-8.5
-7.8
TuRBO
-3.7
-5.0
-7.1
-8.2
-7.1
logn( - 2.5v2 + logvd, v3/5)
logEI-DSP
-3.7
-4.1
-4.0
-4.0
-4.1
Elp(1; 50)] = 0.25
Sobol
-2.4
-27
-2.8
-3.2
-3.0
LES
-3.0
-4.6
-7.1
88.6
- 8.8
medium: p(l;d)=
TuRBO
-3.1
-4.9
-7.0
-7.9
-8.0
logn(
2..0/2 logv v3/4) E|p(I; 50]] = 0.52
loSE
-3.6
-5.0
-7.0
-7.9
-7.0
Sobol
2.5
2.7
-28
2.9
-2.7
low: d(l;d)=
LES
-2.1
33.7
-52
6.6
8.5
TuRBO
-2.4
-3.7
-5.4
6.4
-7.7
logn( 11.002 + logv d. v3/2)
logEI-DSP
229
-41
-5.7
-6,6
-8.1
Elp(I; 50)] 2.65
Sobol
-2.0
2.3
2.9
2.8
-3.0
extremely low: p(4; d)
LES
0.6
0.8
-12
1.5
-2.9
TuRBO
-0.6
-0.8
-.2
-1.5
-2.9
1ogn(1.0v2 - -l.00022-lg-/d logvd, 3
logEI-DSP
-0.6
0.9
-1.3
-1.5
-3.0
E[p(I,; 50)] 96.2
Sobol
-0.5
-0.7
-1.0
-1.0
-1.
performance benefits of searching globally with logEI is only seen for d = 10. MES, the global entropy search benchmark is not competitive. For other problem complexities the same trends can be observed (see 1 and Appx. D.3). Performance differences increase with increasing problem complexity with LES clearly outperforming other methods for high complexity tasks in higher dimensions (see Appx. D.3).
Out-Of-Model Comparison The out-of-model setup is identical the within-model one except that GP hyperparameters are now estimated via MAP. All methods use the hyperprior that is used to sample from the GP, except for logEI-DSP, which was recently proposed by Hvarfner et al. (2024) and assumes a hyperprior with longer length scales. Appx. D.3 reports additional detailed results.
The results mirror the within-model case. Interestingly, logEl performs better when using the wrong (less complex) hyperprior, as in logEI-DSP which supports the claims made in (Hvarfner et al., 2024).
Cumulative Regret The local search behavior inherent to LES leads to substantially lower empirical cumulative regret for all problems except for 5 and the lowest complexity (Appx. D.3).
Stopping Criterion for Local Entropy Search We incorporate a probabilistic stopping rule for LES that assesses whether the current solution is locally optimal. Following the Monte-Carlo test of Wilson (2024), we estimate the probability that the local simple regret falls below a user-specified tolerance and terminate once this criterion is met. The full formulation, assumptions, and theoretical guarantees, along with empirical stopping soopinggtimme results, are provided in Appx. When compared to the results in (Wilson, 2024) these results show that the local optimization needs fewer samples before stopping, reinforcing the intuition that reaching a local optimum is easier
6.3 SYNTHETIC AND APPLICATION DELLICATTON-ORINNEDD OBJECTIVE FUNCTIONS
We evaluate LES additional analytic benchmarks (Fig. 5) and application-orientel tasks, with further results in Appx. D.4. On single-optimum functions (square), all methods reliably identify the solution, though LES and TuRBO achieve lower cumulative regret, highlighting the conservative exploration behavior inherent to local search. On the 30-d Ackley function, LES and TuRBO outperform global methods but LES shows high run-to-run variance due to the many local optima. For the rover (Wang et al., 2018) and Mopta08 (Jones, 2008) tasks, LES, logEl, and TuRBO perform similarly, with LES best rover and logEl best Mopta08.
Additional experiments, including benchmarks designed to expose weaknesses of local search are presented in Appx. D.4. In these cases, LES frequently gets trapped in local optima, leading high

---

Published as a conference paper at ICLR 2026
Square: d = 30
Ackley: d d= 30
Rover: d = 60
Mopta08: d 124
1.0
f(x))
0.5
0.0
200
400
200
400 0
120
240
200
400
Evaluations # logEI
LES (ours)
HCI-GIBO
MES
TuRBO
Sobol random
Figure 5: Synthetic and Application-Orienteedd Objective Functions: Median, 25-, and 75 75-pereent quantiles for the best (normalized) function values found. Additional results Appx. D.4.
run-to-run variance and overall poor performance relative to global methods. These results highlight the limitations of LES on highly multimodal landscapes with hard-to-escape local optima.
7 LIMITATIONS
We show that LES is beneficial especially in the high -igh-iimensoonlityy and high-complexity case. However, the focus on locality also its most obvious constraint. Once the algorithm commits to basin, it possesses no intrinsic mechanism for escape; achieving coverage of the full design space therefore requires globalization strategies. Furthermore, in real-world use cases it may be difficult to determine the problem complexity a-priori. Therefore, multi-starts, more advanced incumbent search, e.g., based on (Adebiyi al., 2025), or switching heuristics between local and global optimization based estimated objective complexity interesting directions for future research. The stopping rule introduced in Appx. E. can be used to trigger a restart instead of stopping.
LES inherits the strengths and weaknesses of its surrogate. All acquisition decisions driven by posterior samples; if the model is misspecified, the algorithm will exploit the wrong belief. Moreover, approximating the mutual information in (16) each iteration requires drawing and optimizing posterior samples, with the number of samples increasing with dimensionality and model complexity.
The present formulation tackles unconstrained, single-objective optimization. LES entropy-search based and therefore future work can naturally extend LES to more complex settings, such as multi- fidelity, constrained, batch (see Appx. C.3), or asynchronous optimization.
Finally, LES currently lacks finite-time regret guarantees of the GP-UCB type (Srinivas et al., 2012), and the current theoretical claims are limited the high-probability certificate of local optimality offered by the stopping test. In addition, bound on the difference between local and global regret for GP sample paths would bridge the current theoretical gap between local and global BO.
DISCUSSION AND CONCLUSION
This paper introduces LES, the first entropy-searde paradigm tailored local optimization. By propagating the GP posterior through the optimizer's 's descent sequence, LES selects each evaluation to maximize mutual information with that sequence, thereby reducing uncertainty over possible descent sequences.
Empirically, LES delivers strong sample efficiency. Across high-complexing GP samples and policy- search benchmarks, the ADAM-based variant consistently attains lower simple regret than global entropy-search baselines and other local BO strategies, especially as dimensionality and complexity grows. Additionally, behavior than global BO. This can be a great asset when optimizing outside of simulated environments, e.g., in real-world robot learning. A probabilistic stopping rule guarantees bounded local regret by detecting convergence to a local optimum without additional overhead by reusing the samples from the acquisition step (Appx. E).
show in Appx. D.4 that local search has more conservative exploration
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank Johanna Menn, Paul Brunzema, and Friedrich Solowjow for the many helpful discus- sions. This work has been supported by the Robotics Institute Germany, funded by BMFTR grant 16ME0997K, and by the Deutsche Forschungsgemeinnchatt (DFG, German Research Foundation) under Germany's Excellence Strategy EXC-2023 Internet of Production 390621612. Computa- tions were performed with computing resources granted by RWTH Aachen University under project rwth1723.
REPRODUCIBILITY STATEMENT
All code necessary reproduce the results is available². Additionally, we elaborate on approximations and implementation details in Sec. 5.2. We report hyperparameter values in Appx. D.
REFERENCES
Taiwo Adebiyi, Bach Do. and Ruda Zhang. Optimizing posterior samples for Bayesian optimization via rootfinding. In The Thirteenth International Conference on Learning Representations, 2025.
Robert Adler. The geometry of random fields. SIAM. 2010.
Riad Akrour, Dmitry Sorokin, Jan Peters, and Gerhard Neumann. Local Bayesian optimization of
motor skills. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 41-50, 2017.
Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Unex- pected improvements to expected improvement for bayesian optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 20577-20612, 2023.
Maximilian Balandat, Brian Karrer, Daniel Jiang. Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy. BoTorrch A framework for efficient Monte-Carke Bayesian optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 21524-21538, 2020.
Rafael Barbudo, Sebastián Ventura, and José Raúl Romero. Eight years of AutoML: categorisation, review and trends. Knowledge and Information Systems, 65(12):5097-5149, 2023, doi: 10.1007/ s10115-023-01935-1
Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-valu entropy search for multi- objective Bayesian optimization with constraints. Workshop on Machine Learning and the Physical Sciences (NeurIPS), 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Paul Brunzema, Mikkel Jordahn, John Willes, Sebastian Trimpe, Jasper Snoek, and James Harrison. Variational last layers for Bayesian optimization. In NeurlPS 2024 Workshop Bayesian Decision- making and Uncertainty, 2024.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellster Douglas Eck, Jeff Dean,
"Code available http://:wtccccoooooeeeeeeeeeeece

---

Published as a conference paper at ICLR 2026
Slav Petrov, and Noah Fiedel. PaLM: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Lionel Colliandre and Christophe Muller. Bayesian optimization in drug discovery. In High Performance Computing for Drug Discovery and Biomedicine, pp. 101-136. Springer, 2023.
doi: 1100779778-1-011--4449907
Bach Do, Nafeezat A Ajenifuja, Taiwo A Adebiyi, and Ruda Zhang. Sampling from Gaussian processes: A tutorial and applications in global sensitivity analysis and optimization. arXiv preprint urXiv:2507.147444 2025,
David Eriksson, Michael Pearce, Jacob Gardner, Ryan Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. In Advances in Neural Information Processing Systems, pp- 5496-5507, 2019.
Zheyi Fan, Wenyu Wang. Szu Hui Ng, and Qingpei Hu. Minimizing ucb: better local search strategy in local Bayesian optimization. In Advances in Neural Information Processing Systems, volume 37, pp. 130602-130634, 2024.
Fröhlich Lukas P., Klenske Edgar D., Daniel Christian G., and Zeilinger Melanie N. Bayesian optimization for policy search in high-dimensional systems via automatic domain selection. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 757-764, 2019. doi: 10. 10.1 (000/RR0S00097.21988996677
Roman Garnett, Bayesian Optimization. Cambridge University Press, 2023.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Compulation, 9(2):199-155, 2001. doi: 10. 22211///6666566015009999333
Shiming He, Alexander von Rohr, Dominik Baumann, Ji Xiang, and Sebastian Trimpe. Simulation- aided policy tuning for black-box robot learning. IEEE Transactions on Robotics, 41:2533-2544 2025. doi: 10. 1011000R..222..5539
Philipp Hennig and Christian J. Schuler. Entropy search for information-efficien global optimization. Journal of Machine Learning Research, 13(6), 2012.
José Miguel Bernándezz-Lbato Matthew W. Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Advances in Neural Information Processing Systems, volume 27, 2014.
Carl Hvarfner, Frank Hutter, and Luigi Nardi. Joint entropy search for maximally-ifformed Bayesian optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 11494-11506, 2022.
Carl Hvarfner, Erik Orm Hellsten, and Luigi Nardi. Vanilla Bayesian optimization performs great in high dimensions. In Proceedings of the 4/ International Conference on Machine Learning. volume 235, pp. 20793-20817, 2024.
D. Jones. Large-scale multi-disciplinary mass optimization in the auto industry, 2008, Presented at the Modeling and Optimization: Theory and Applications (MOPTA) 2008 Conference.
A. G. Journel and C. J. Huijbregts. Mining Geostatistics. Academic Press, London, 1978.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference Learning Representations, 2015.
Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adaptive and safe Bayesian optimization in high dimensions via miedimmnsional subspaces. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3429-3422 3438, 2019.
Alonso Marco, Felix Berkenkamp, Philipp Hennig, Angela P. Schoellig, Andreas Krause, Stefan Schaal, and Sebastian Trimpe. Virtual vs. real: Trading off simulations and physical experiments in reinforcement learning with Bayesian optimization. In JEEE International Conference on Robotics and Automation, pp. 1557-1563, 2017. doi: 2..110//CRA.201.....00 186.
12

---

Published as a conference paper at ICLR 2026
Sarah Müller, Alexander von Rohr, and Sebastian Trimpe. Local policy search with Bayesian optimization. In Advances in Neural Information Processing Systems, volume 34, pp. 20708- 20720, 2021.
Quan Nguyen, Kaiwen Wu, Jacob Gardner, and Roman Garnett. Local Bayesian optimization via maximizing probability of descent. In Advances in Neural Information Processing Systems, volume 35, pp. 11190-13202, 2022.
Joel A. Paulson, Farshud Sorourifar, and Ali Mesbah. tutorial on derivative-free policy learning methods for interpretable controller representations. In American Control Conference, pp. 1295- 1306, 2023. doi: 10.239 200 10156412.
Valerio Perrone, laroslav Shcherbatyi, Rodolphe Jenatton, Cedrie Archambeau, and Matthias Seeger. Constrained Bayesian optimization with max-value entropy search, 2019.
Carl Edward Rasmussen and Christopher K. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006. doi: 10.755 h/mitprrsss/3200600000 .00.0001....
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information-theorret regret bounds for Gaussian process optimization in the bandit setting. IEEE Transuctions on Information Theory, 58(5):3250-322 3265, 2012. doi: 10.1109/T1..2011.22 1..122233..
Wei-Ting Tang and Joel A. Paulson. CAGES: Cost-aware gradient entropy search for efficient local multi-fidelity Bayesian optimization. In IEEE 63rd Conference on Decision and Control, pp. 1547-1552, 2024. doi: 10.1 N0.1109/CDDC55724.0000 2022..0884..555
Ben Tu, Axel Gandy, Nikolas Kantas, and Behrang Shafei. Joint entropy search for oujti-obeecttve Bayesian optimization. In Advances in Neural Information Processing Systems, volume 35, pp. 9922-9938, 2022.
A. Vaart, van der and J.H. Zanten, van. Reproducing kernel Hilbert spaces of Gaussian priors, pp. 200-222 222. 2008. doi: 10. 10121447742270000000155
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 3627-3635, 2017.
Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale Bayesian optimization in high-dimensional spaces. In Proceedings of the Firetty-First International Con- ference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 745-754, 2018.
James Wilson, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Mare Deisenroth. Efficiently sampling functions from Gaussian process posteriors. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 10292-10302, 2020.
James Wilson. Stopping Bayesian optimization with probabilistic regret bounds. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024.
Kaiwen Wu, Kyurae Kim, Roman Garnett, and Jacob Gardner. The behavior and convergence of local Bayesian optimization. In Advances Neural Information Processing Systems, volume 36, pp. 73497-73523, 2023.
Zhitong Xu, Haitao Wang, Jeff M. Phillips, and Shandian Zhe. Standard Gaussian process is all you need for high-dimensional Bayesian optimization. In The Thirteenth International Conference on Learning Representations, 2025.
13

---

Published as a conference paper at ICLR 2026
Supplementary Material for "Local Entropy Search over Descent Sequences for Bayesian Optimization"
A Introduction to Bayesian Optimization with Entropy Search
15
Exact Information Gain Maximization the Local Optimizer
16
B.I Impracticability in the General Case
16
B.2 Exact Information Gain Maximization in Entropy-Base Based GIBO
16
C Additional Details LES
18
C.1 GP-Sample Approximation Strategies
18
C.2 Relationship Between Properties of Target Function, Model Samples and Local Optimizer
18
C.3 qLES: Batched Local Entropy Search
18
Empirical Evaluation
19
D.I LES Algorithm hyperparameter
19
D.2 Benchmark Algorithm Hyperparameter
19
D.3 Additional Details and Results on GP Samples
19
D.4 Additional Details and Results Synthetic and Application Application-Orienteed Objective Funetions
32
D.5 Ablations on Approximation Accuracies and Runtime
35
D.6 Descent Sequence Length and Step Size
36
D.7 Comparing Different Iterative Optimizers
37
A Stopping Criterion for Local Entropy Search
40
E.1 Method
40
E.2
Results
40
F
Alternative Information-Theone Local Acquisition Functions
42
F11
Local Thompson Sampling
42
F2
Conditioning only on the Local Optimum
42
F3
Results
42
G Theoretical Results
43
LES queries are dense
43
G.2 Gradient descent paths under GP prior with squared exponential kernel
44
Following is the technical appendix. Note that all citations here are in the bibliography of the main document and similarly for many of the cross-references.
14

---

Published as a conference paper at ICLR 2026
A INTRODUCTION TO BAYESIAN OPTIMIZATION WITH ENTROPY SEARCH
Because evaluating f() is costly, BO leverages all data obtained until iteration t to choose the next parametrization #14-1 in Domain X. After tinit random samples are evaluated, BO takes two steps to maximize the utility of the next experiment. First, a GP is trained on all past observations to approximate f(z). Second, this model is used in an acquisition function balance exploration and exploitation. The acquisition function a uses the probabilistic GP predictions to calculate the utility of an experiment. It is maximized to find the next query:
1++1 argmax x (GPk))
(17)
Approximately solving (17) is much easier than the original problem because only the fast-to-evaluate GP model needs to be evaluated. This new query evaluated. new data is received, and the next iteration is started by again updating the GP model. This way, the GP model is iteratively refined in promising regions. We refer to (Garnett, 2023) for a detailed introduction to BO.
Global entropy search methods use an information-thhorelt perspective to select where evaluate. They find a query point that maximizes the expected information gain about the global optimum x arg m E (x) whose value fr f(x") achieves the global maximum of the function ʃ.
The original entropy search (ES) (Hennig & Schuler, 2012) and predictive entropy search (PES) (Hernández-Lane Lobato et al., 2014) maximize the information gain about the location the optimum:
ar (2) (1z, (x))); Dz)
(18)
The random variable y(z) denotes the predictive distribution of the noisy observation at the query location and x denotes the estimated distribution of the global optimizer. The information gain can be expressed as the difference between predictive entropy of noisy observation at the query location, H (p ar D.)) and the expectation of the predictive conditioned on the distribution of minimizers E [ (æ. Dj {ar, y})]] Calculating those terms requires expensive approximations that do not scale well especially in high dimensions.
Max-value entropy search (MES) (Wang & Jegelka, 2017) maximize the information gain about the function value of the optimum:
ax(x) = (1x,y): D.)
(19)
This approach is computationally significantly more efficient than ES and PES, because the expec- tation and entropy need to be only calculated over the one dimensional distribution of optimum values.
Joint entropy search (JES) (Hvarfner et al., 2022; Tu et al., 2022) maximizes the information gain about the joint distribution of location location and function value of the optimizer
(x)s(x)) ((x, y): (zg. f() D,))
(20)
This paper applies the entropy search paradigm to local BO. Up to here, only discussed entropy search for single objective optimization. It can be extended to other BO paradigms such as constrained (Perrone al., 2019), multi-objective (Belakaria al., 2020), and multi-fidelity (Marco al., 2017) optimization.
15

---

Published as a conference paper at ICLR 2026
B EXACT INFORMATION GAIN MAXIMIZATION OF THE LOCAL OPTIMIZER
In LES, we do not directly minimize the entropy of the solution of the local optimization algorithm but instead minimize the entropy of the descent sequence. This section shows why directly minimizing the entropy of the solution is not possible in general. Furthermore, we show that the entropy search version of GIBO is special case for one step gradient descent, where it actually is possible.
B.1 IMPRACTICABILITY IN THE GENERAL CASE
Suppose we want to directly minimize the entropy of the local optimizer:
max / ((ær, y (())); Oz, (P)).
(21)
xEX
One way of going forward is reformulate in the standard entropy search way:
((2, y(z)); O Dr)) ((2,
Hly(() Djl By H ((()) Dr, Oz
(22)
predictive entropy
conditional entropy
After Monte-Carl approximation we get:
E H p (v(2) Dr, 0%
T. T
E H p (v(x)) De, 01))
(23)
Unfortunately, we can condition a GP efficiently only on point-wise observations of, for example, function values or gradients by adding them to the original data set as virtual points. It is not possible to condition a GP directly on O being a location that can be reached by gradient descent from Zg-
In Appendix F.2 we show how we can condition on O being local optimum with zero gradient and positive Hessian. However, this loses information about the sequence to the local optimum. An alternative approach would be the following reformulation:
a(x) I ((22 yz=));; O Dz)
H Dj Ey(())
H [ (Dr,
(24)
predictive entropy
conditional entropy
In principle, we can approximate the conditional entropy in (24) with Monte-Carlo approximation because we only have to condition GP on realizations of y(x). However, this is prohibitively expensive because would require new Monte-Carlo approximation of O to evaluate a at a new query location æ. Therefore, we do not consider this possibility any further.
B.2 EXACT INFORMATION GAIN MAXIMIZATION IN EXTROPY-BASEE GIBO
This paragraph shows that the information theoretic version CAGES (Tang & Paulson, 2024) of the GIBO (Müller et al., 2021) acquisition function can be seen special case of LES (11). This special case arises when considering a one step gradient descent algorithm that produces the following descent sequence
GSa, (f) = { 2o = Fu, 21 = zg
V {2
(25)
Now suppose that the local optimum is the last element of that sequence O 30 - fxxo). Inserting in equation (24) yields:
oGES (z) H(O Dz] Ey(a)) [ OO (Di, v=)]]
(26)
H| v/V f (zoo) D.)]
Ey(z)) [H [wo 1/ f(o)) Pr,((x))
Since By and n are non-random variables, we get:
aCES(#)) (x) [(v)) D.J Eyy()) [H (x)) D. (xx y(x)]]
(27)
Inserting the entropy of a multivariate normal distribution, we get the original GES acquisition function (Tang & Paulson, 2024, Eq. (8)):
1
ages (x) log E' (au DJ) log E' (xx | Dr U (x, y(x))
(28)
2
2
16

---

Published as a conference paper at ICLR 2026
The covariance of the gradient at location Ee given data D, is denoted as E' (zu Dt). Note that the expectation over y(x) can be ignored because the predictive variance the gradient is independent of y(x) and only depends function that the GIBO acquisition function uses the trace operator instead of the determinant operator in (28).
The small difference between the CAGES and the GIBO acquisition
This observation highlights that GIBO-style acquisition functions learn about one step of the gradient descent sequence, whereas LES maximizes the information gain about the whole descent sequence.
17

---

Published as a conference paper at ICLR 2026
C ADDITIONAL DETAILS ON LES
C.I GP-SAMPLE APPROXIMATION STRATEGIES
In this work, approximate GP sample paths using the decoupled method of (Wilson al., 2020) (Eq. (4)), which we regard as state-of-the-an and computationally attractive. It has been shown to outperform alternatives, readily available in TensorFlow and PyTorch, and is still recommended in recent tutorials on GP sampling (Do et al., 2025). We therefore do not empirically investigate alternative sampling strategies for LES.
By contrast, the Ga-sample benchmarks in GIBO (Müller et al., 2021) and follow-up work (Nguyen al., 2022) adopt different approach: they sample the posterior fixed locations and then re- interpolate these points with GP.. In our preliminary experiments, this led to overly smooth sample functions low dimensions.
Exploring how different sampling strategies affect LES remains interesting direction for future work, both to assess robustness and to better understand potential biases introduced by approximation schemes.
C.2 RELATIONSIIIP BETWEEN PROPERTIES OF TARGET FUNCTION, MODEL SAMPLES AND LOCAL OPTIMIZER
The choice of local optimizer O is constrained by the properties of the GP sample paths and practically by their approximations. For instance, is gradient-based, the sample paths I' must be at least once differentiable. More generally, the samples need to be differentiable to the same order required by O. LES, however, is not limited to gradient-bart based methods: zeroth-order optimizers such as hill climbing or pattern search can be used when samples are non-differentiable. We illustrate this in Appx. D.7 with LES-CMAES, which employs zeroth-order evolutionary optimizer.
Different kernels also practically affect optimizer choice. For example, Matérn-1/2 or Matérn-3, -322 kernels often generate sample paths with many shallow local minima. In such cases, optimizer that incorporates momentum (e.g., Adam) may help to avoid undesired convergence to these minima.
Crucially, these requirements apply to the GP sample paths, not to the true objective. Indeed, GPs can approximate sub-gradients of non-differentiable functions, as shown in (Wu al., 2023).
C.3 QLES: BATCHED LOCAL ENTROPY SEARCH
The LES paradigm can be straightforwardly extended to the batch case. This serves an example of the versatility of entropy search methods and their potential for local optimization. We simply maximize the mutual information between the joint predictive distribution of multiple samples v(z)),.., and the distribution descent sequences. Equation (13) becomes:
QLLES(E1,.... ....... tGg) I (I1, .... Tg. v(x1), ..., y xz amo (Di) = =H(y(a)),... y(x,)) D.) - EE, [H (y(x)), .... y(o,)) Dr, Qmo
(29)
predictive entropy
conditional entropy
With this, the only change to the acquisition function calculation the entropy calculation. The entropy of the predictive and conditional entropies still be calculated in closed form and omitting the intermediate steps, the acquisition function (16) becomes:
1
CELES(E1,.... x.g) x log det (Ey( xg (i))
2
(30)
ΣΣ
log det (2i, (I), ..... T. Dr U Q.o))
The term (x) Dg D.) denotes the predictive covariance matrix of the posterior GP at the query locations 2 ..... F. given data D,.
Optimizing (30) becomes more computationally expensive as increases. However, we expect this increase to be relatively minor. The most expensive parts of the LES formalisms, i.e., generating
18

---

Published as a conference paper at ICLR 2026
GP samples, locally optimizing them and then conditioning L GPs on the descent sequences have to be done only once, independently of q.
D EMPIRICAL EVALUATION
This section gives additional results and details the empirical evaluation. Most notably, show that the local exploration behavior results in reduced cumulative cost (D.3.D.4) and show extended results on Ga-samples with varying problem complexity for the within and out of model comparison setting (D.3). Additional results are the impact of the discretizations on runtime and quality (D.5) and the impact of the local optimizer choice (D.7).
D.1 LES ALGORITHM HYPERPARAMETER
Table summarizes the main LES hyperparameter. In summary, LES has four types of hyper parameters: (a) CP-hyyerparameter any other BO algorithm (see Tab. 4, 10). (b) L. and P that govern the accuracy of the acquisition function approximation. They should be chosen as large as computational resources permit (see Appx. D.5) (c) parameter of the stopping rule of the stopping rule (see Appx. E) (d) the local optimizer and its parameters (see Appx. D.7).
Table Default hyperparameter LES
Name
Description
Value
Number of initial uniform random samples
Monte-Carlo samples of gradient descent sequences
250
P
discretizations of the gradient descent sequences
M
prior features of the GP posterior sampling
1024
stopping criterion optimality total risk
0.1, 0.01
6
0.05
Jest
estimation risk
0.0025
Taoe
samples between each decision
25
Local Optimizer
ADAM
Number Local Optimization Steps
500
Learning Rate
0.002
Momentum Parameters
Keras Default
D.2 BENCHMARK ALGORITHM HYPERPARAMETER
For HCI-GIBO we choose a 0.9 and perform hyperparameter optimization after each gradient step. We use the BoTorch (Balandat et al., 2020) implementations of MES, logEl, and TuRBO. MES uses candidate set of 5000 points and both MES and TuRBO use default parameters of the BoTorch implementation. Again, all algorithm use identical GP parameters with the exception of ISSHI-DSP, where the hyperprior of (Hvarfner et al., 2024) is chosen.
D.3 ADDITIONAL DETAILS AND RESULTS ON GP SAMPLES
General Setup. Table 4 summarizes the GP hyperparameters used the Ga-sample experiments. Following (Hvarfner et al., 2024), we employ a log-normal hyperprior p(l) for the length scales and assume a constant, known measurement noise distribution. Test functions are generated by first sampling length scales from the hyperprior and then drawing functions according to (4). To vary problem difficulty, we scale the log-normal hyperpriors expected length scales are reported in Table 5. Note that the original hyperprior assumes very large average length scales, whereas in the high-complexity scenario the expected length scale at d = 50 is E[p(1)] 0.25, which is still reasonable.
(Hvarfner et al., 2024) (see Sec. 6.2);
Across all experiments, data is not standardized, each algorithm evaluated on 20 random seeds, and the two initial points chosen randomly.
19

---

Published as a conference paper at ICLR 2026
Table 4: GP hyperparameters for out of model comparison on GP samples
Name
Description
Value
kernel
SE-ARD
p(1:d)
length-scale hyper prior
Log Normal (see Tab. 5)
On
observation noise
fixed at 0.002
GP output scale
variable init at 1
linit
length scale initialization
E[p(4; d)]
hyperparameter optimization frequency standardize data
after every sample'
yes
Table 5: Expected length scales Eip([;; d)] for the different hyperpriors.
Complexity
d d=
d
10
d = 20
d = 30
d 50
high: p(1: d)
0.08
0.11
0.15
0.19
0.25
logn( -2.5 logvd. v3/5)
medium: p((; 1ogn-2.0v/2+ logvd, v3/4)
0.16
0.23
0.33
0.4
0.52
low: p; d(() =
0.83
1.19
1.67
2.05
2.65
logn(-1.0/2+ +ogv v3/2)
extremely low (Hvarfner et al., 2024): d(l:d) = 21.86 30.92
34.73
53.56
69.15
logn(1.0v2 + log.00//++oo v3)
Within-Model Comparison. In this setting, all BO algorithms are given access to the sampled ground-truth hyperparameters (length scales, output scale, and noise variance). Tables 6 and summarize the results, with statistical significance determined by the signed rank test. Entries not in bold are statistically significantly worse than the best- best-performing algorithm. Figures 6-13 show the convergence curves.
LES achieves statistically significant improvements in gigher-dimensionll. high-complexity settings, particularly in terms of cumulative regret. Global BO methods only outperform LES in high- complexity, tow-dimensional cases.
FExcept for the GTBO variants, where optimize the hyperparameter only after each step.
20

---

Published as a conference paper at ICLR 2026
Table Best achieved function value after full budget for within model comparison on GP samples. Entries not in bold are statistically significantly worse than the best preforming algorithm. Smaller is better.
Complexity
Method
d=5
10
20
30
50
LES (ours)
-2.8
-488
-7.4
-9.0
-10.8
MES
-2.4
-2.6
-3.0
-2.9
-2.8
logEl
-3.9
-4.4
-2.9
-3.2
-2.9
high
TuRBO
-3.5
-4.8
-7.2
-8.0
-7.1
HCI-GIBO
-277
-2.0
-2.3
-18
-0.7
Sobol random
-2.4
-2.7
-2.8
332
-3.0
LES (ours)
-2.9
-4.4
7.3
8.6
10.4
MES
-3.4
-2.0
-28
-29
-2.9
logEl
33.6
-5.3
-7.1
-8.4
-9.6
medium
TuRBO
-3.1
-4.8
-7.0
-8.5
-7.9
HCI-GIBO
229
-3.6
-29
-2.
-1.7
Sobol random
-25
-2.7
-28
-29
-2.7
LES (ours)
-2.1
-3.7
-5.5
6.8
-8.8
MES
-2.9
-4.0
-4.9
-4.6
-3.9
logEI
22.9
-4.1
-5.8
-6.6
8.5
low
TuRBO
-2.4
-3.6
-5.5
-8.1
HCI-GIBO
-2.1
-3.4
-5.0
55.
-7.3
Sobol random
-20
-23
229
-28
33.0
LES (ours)
-0.6
-0.8
1.2
-.55
3.0
MES
-0.6
-09
-13
-1.5
-2.7
logEl
-0.6
0.9
1.3
-15
3.0
extremely low
TuRBO
-0.6
-0.8
-.2
-1.
-2.
HCI-GIBO
0066
0.8
-11
-1.3
-2.7
Sobol random
0.5
-0.7
-10
-1.0
-1.5
Table Cumulative observed function values after full budget for within model comparison on GP samples. Entries not in bold are statistically significantly worse than the best preforming al algorithm. Smaller better.
Complexity
Method
d 30
d 50
LES (ours)
-260.1
-842.1
2515.1
2938.4
-3214.3
MES
35.8
22.3
0.1
1.1
4.0
logEl
-176.6
-230.6
-17.1
-0.8
6.5
high
TuRBO
-247.9
-672.5
-1783.3
1503.00
-977.9
HCI-GIBO
-59.5
-28.3
-16.6
19.8
-24.7
Sobol random
1.5
-1.7
-7.2
7.2
3.7
LES (ours)
272.8
811.4
2464.3
2861.7
3159.
MES
-97.1
167.3
288.4
6.5
-0.6
logEl
-163.7
-64.5
221113
2077.3
1378.3
medium
TuRBO
246.7
697.6
1876.0
19924.9
1375.1
HCI-GIBO
-14.55
-12.33
-51.4
-27.4
4.2
Sobol random
6.4
3.0
0.6
5.3
1.3
LES (ours)
192.9
685.7
2059.5
2415.1
2969.3
MES
-97.6
358.9
682.8
-276.7
337.6
logEl
-88.1
434.0
16799.0
-214.88
-2795.6
low
TuRBO
201.8
637.6
19166.6
-0048.7
-2390.1
HCI-GIBO
- 169.8
581.9
1638.9
-1874.3
2224.6
Sobol random
7.1
1.7
-42.8
-0.2
-1.5
LES (ours)
56.8
160.5
477.9
591.0
11142.4
MES
-13.0
-7.5
-132.2
69.1
-25233
logEl
-51.0
-122.5
337.4
320.6
-581.0
extremely low
TuRBO
-57.1
-152.3
-456.3
-16.88
-896.0
HCI-GIBO
-543
-145.2
-420.7
-496.1
-913.7
Sobol random
-1.9
21.1
-74.3
61.9
-88.9
21

---

Published as a conference paper at ICLR 2026
d
a-
current best
-2
-2
-4
100
150
200
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
LES-ADAM: L 250, P (default)
Currett best
MES
logEl
-6
TURBO
ICI-GIBO
Sobal random
10
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 6: Within Model Comparison, Complexity high: Median, 25-, and 75-percent quantiles detailed results
d
0
200
-500
Cumulatedy
-1000
-100
100
-1500
600
-200
-000
800
-2500
-300
1000
20
40
60
100
50
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d=300
d= 50
-500
LES-ADAM:
(default)
Cumulated y
-1000
-1000
MES
logEl
-1500
TURBO
2000
-2000
GIBD
-2500
3000
3000
200
300
Objective function evaluation
Objective function evaluation
Figure 7: Within Model Comparison, Complexity high: Median, 25-, and 75-percent quantiles detailed results
22

---

Published as a conference paper at ICLR 2026
G
- 10
- 20
Current best
-2
60
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaiuation
LES:ADMM: L= 250, P (default)
Lurrent best.
MES
logEi
-4
TURBO
HCI-GIBO
-8
Sobol random
-8
400
300
400
Objective function evaluation
Objective function evaluation
Figure 8:
Within Model Comparison, Complexity medium: Median, 25-, and 75-percent
quantiles detailed results
d 5
d0
200
500
Curulaated
200
11000
100
15500
-200
600
2000
800
-300
-200
20
40
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
0
LES ADAM: L= 250, P 8 (default)
Cumurased
-1000
-1000
MES
logEl
-1500
2000
2000
HCI-GIBO
Sobel random
-2500
-3000
-3000
100
200
300
400
100
200
300
400
Objective evaluation
Objective
Within Model Comparison, Complexity medium: Median, 25-, and 75 75-pertent quantiles detailed results
Figure
23

---

Published as a conference paper at ICLR 2026
10
- 20
Current best
-2
-2
20
40
80
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d' 30
d'
current best
-2
-2
MES
LES-ADAM:
250, (default)
logEl
TURBO
-6
Sobol
-6
100
200
400
200
300
Objective function evaluation
Objective function evaluation
Figure 10: detailed results
Within Model Comparison, Complexity low: Median, 25-, and 75-percent quantiles
d
d=
0
-500
-50
200
Curmulateed
-100
-1000
400
-150
-1500
2000
-50
20
40
100
100
150
200
100
200
300
400
Objective function evaiuation
Objective function evaluation
Objective function evaluation
d
0
Cumuriatdd y
-500
LES ADAM: L= 250, P 8 (default)
MES
-1000
logEl
TURBO
-1500
-2000
GIBO
Sobol random
-2000
-2500
3000
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 11: Within Model Comparison, Complexity low: Median, 25-, and 75-percent quantiles detailed results
24

---

Published as a conference paper at ICLR 2026
5
10
20
1.0
0.5
0.5
0.0
Current best
0.0
00.
0.5
-1.0
40
80
100
150
200
100
200
300
100
Objective function evaluation
Objective function evaluation
Objective function evaluation
LES-ADAM:
250, P (default)
Current best
-1
MES
logEl
-2-
HCI-GIBO
Sobal random
-3
-2
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 12: Within Model Comparison, Complexity extremely low: Median, 23-, and 75 --preeeettt quantiles detailed results
d' 10
50
100
0
cumulated
-00
-50
1100
400
-200
1000
600
20
40
100
100
150
200
200
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
LES-ADAM: L 250, P (default)
Cumulated
MES
-500
logËl
-250
TURBO
HCI-GIBO
-500
1000
Sobol random
-750
1500
100
200
300
400
100
200
300
400
Objective evaluation
Objective evaluation
Figure 13: Within Model Comparison, Complexity extremely low: Median, 25-, and 75 15-percent quantiles detailed results
25

---

Published as a conference paper at ICLR 2026
Out of Model Comparison. The out-of-model setup is identical to the within-modee except that GP hyperparameters are now estimated via MAP according to Table 4. Tables and report best and cumulative evaluations, and Figures 14-21 show the corresponding progress in optimization over the number of queries.
Table 8: Best achieved function value after full budget for out-of-model comparison on GP samples. Entries not in bold are statistically significantly worse than the best preforming algorithm. Smaller is better.
Complexity
Method
d=
d=
d=
20
d=
30
d
50
LES (ours)
-299
-5.0
-7.2
-8.5
-7.8
MES
-1.9
-2.5
-2.8
-2.8
-3.0
logEl
-4.0
-4.3
-288
-2.9
-3.0
high
logEI-DSP
-3.7
-4.1
-4.0
-4.0
-4.1
TuRBO
-3.7
-5.0
-7.1
-8.2
-7.1
HCI-GIBO
-23
-2.
-19
-2.0
-18
Sobol random
2.4
-277
-28
3.2
3.0
LES (ours)
3.0
-4.6
77.1
8.6
8.8
MES
-3.6
-211
-29
-28
229
logEl
-366
-5.1
-7.2
-8.1
-4.5
medium
logEI-DSP
-3.6
-5.0
-7.0
-7.9
-7.0
TuRBO
-3.1
-4.9
-7.0
-7.9
-8.0
HCI-GIBO
2.9
-3.7
-29
-2.
-1.6
Sobol random
2.5
-2.7
-28
-29
227
LES (ours)
-211
-3.7
-52
6,6
8.5
MES
-2.9
-4.0
-5.1
-5.4
-3.7
logEl
22.9
-4.1
5.7
6.4
8.4
low
logEI-DSP
22.9
-4.1
-5.7
-6.6
-8.1 8,1
TuRBO
-2.4
-3.7
-5.4
-6.4
-7.7
HCI-GIBO
2.2
-3.5
-4.9
-5.
-7.5
Sobol random
2.0
-2.3
-2.
-28
330
LES (ours)
-0.6
-0.8
-12
-15
22.9
MES
-0.6
-0.9
-12
-1.
-2,5
logEl
-0.6
-0.9
-1.3
-1.5
-3.0
extremely low
logEI-DSP
0.6
- -0.9
-.3
-1.5
-3.0
TuRBO
-0.6
00.8
-1.2
-1.5
-2.9
HCI-GIBO
-0.6
-0.7
-13
-1.5
-2,
Sobol random
0.5
-0.7
-1.0
-1.0
-1.5
26

---

Published as a conference paper at ICLR 2026
Table Cumulative observed function values after full budget for out of model comparison on GP samples. Entries not in bold are statistically significantly worse than the best preforming algorithm. Smaller better.
Complexity
Method
d
d 10
d 20
d= 30
d = 50
LES (ours)
-259.0
-67.2
2298.3
-2482.5
-2081.9
MES
56.9
13.6
11.6
-0.2
10.7
logEI
-172.9
197.77
0.4
3.4
2.8
high
logEI-DSP
-130.4
-169.4
128.11
-127.2
-19.33
TuRBO
-257.0
-649.4
17899.6
-1565.5
-977.9
HCI-GIBO
-50.6
-24.5
-27.7
-18.1
-8.9
Sobol random
1.5
-1.7
-7.2
7.2
3.7
LES (ours)
269.6
819.0
2267.5
2494.5
2427.1
MES
-111.1
176.1
34.3
-3.5
-5.4
logEI
-172.8
-667.3
1949.77
-1597.4
-110.1
medium
logEI-DSP
-150.1
-524.4
1912.4
-1644.4
-652.1
TuRBO
-250.9
-6735
19000.0
-1737.7
11352.6
HCI-GIBO
160.11
109.00
-40.8
-15.1
-19.9
Sobol random
6.4
3.0
0.6
5.3
1.3
LES (ours)
182.3
662.1
1883.7
2183.6
2572.6
MES
-102.5
337300
666.8
-433.0
317.9
logEI
-101.7
448.3
1639.7
2049.2
-2691.8
low
logEI-DSP
-88.9
380.8
1563.44
-1966.1
-2604.0
TuRBO
204.1
620.1
-1764.8
-1848.2
-2151.1
HCI-GIBO
148.5
456.3
1454.9
-1783.2
21128.8
Sobol random
7.1
1.7
-42.7
-0.1
-1.5
LES (ours)
54.2
146.5
475.7
580.9
-1063.6
MES
-22.8
-10.7
117.11
-8.6
243.6
logEl
-43.6
-002.3
-338.4
331.66
-629.5
extremely low
logEI-DSP
-40.7
-103.1
335.6
3310.1
623.9
TuRBO
-54.7
-155.0
-66.00
-554.3
-1053.0
HCI-GIBO
-40.9
-88.7
338.11
2966.4
337.1
Sobol random
-1.9
21.1
-74.2
61.9
-88.8
27

---

Published as a conference paper at ICLR 2026
10
- 20
Current best
-2
20
40
80
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d' 30
d'
LES ADAM: 250, (default)
current Dest
-2
logEl
logEl-DSP
TURBO
-6
HCI-GIBO
Sobol random
200
400
200
400
Objestive function evaiuation
Objective function evaluation
Figure 14: detailed results
Out of model comparison, complexity high: Median, 25-, and 75-percent quantiles
-20
Curmulated
-100
400
-1000
1500
-200
-200
800
20
40
100
100
150
200
100
200
300
400
Objective function evaiuation
Objective function evaluation
Objective function evaluation
d
0
-500
LES-ADAM: L- 250, P 8 (default)
Cumulated y
logEl
logEl DSP
TURBO
15000
HCI- HCI-GIBO
2000
-2500
2000
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 15: Out of model comparison, complexity high: Median, 25-, and 75 75-percent quantiles detailed results
28

---

Published as a conference paper at ICLR 2026
10
-
20
0
Current best
-2
8
20
40
80
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d' 30
d'
LES ADAM: 250, P (default)
current Dest
-2
MES
logEl
logEl-DSP
TURBO
-6-
-6
HCI-GIBO
Sobol random
200
400
200
300
400
Objective function evaiuation
Objective function evaluation
Figure 16: Out of model comparison, complexity medium: Median, 25-, and 75-percent quantiles detailed results
0
200
-50
-500
Curmulatee
100
11000
-150
400
200
1500
600
-250
-200
800
-30
-200
20
40
100
100
150
200
100
200
300
400
Objective function evaiuation
Objective function evaluation
Objective function evaluation
d
0
-500
LES-ADAM: L- 250, P 8 (default)
Cumuriatdd y
-1000
1000
logEl
logEl DSP
-1500
TURBO
HCI HCI-GIBO
-2000
-2500
-200
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 17: Out of model comparison, complexity medium: Median, 25-, and 75-percent quantiles detailed results
29

---

Published as a conference paper at ICLR 2026
10
- 20
Current best
-2
20
40
80
100
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d' 30
d=
LES ADAM: 250, P (default)
current best.
MES
logEl
-4
logEl-DSP
TURBO
-6
HCI-GIBO
Sobol random
-6
200
400
200
400
Objective function evaluation
Objective function evaluation
Figure 18: detailed results
Out of model comparison, complexity low: Median, 25-, and 75-percent quantiles
d ==5
d=
0
-50
200
Curmulated
-100
1000
400
-150
-1500
600
-250
-2000
20
40
100
100
150
200
100
200
300
400
Objective function evaiuation
Objective function evaluation
Objective function evaluation
d
LES-ADAM: L- 250, P 8 (default)
Cumulated y
logEl
-1000
-1000-
logEl DSP
TURBO
-1500
HCI HCI-GIBB
-2000
-2000
100
200
300
400
1000
200
300
400
Objective function evaluation
Objective function evaluation
Figure 19: Out of model comparison, complexity low: Median, 25-, and 75-percent quantiles detailed results
30

---

Published as a conference paper at ICLR 2026
5
10
20
0.5
0.5
0.0
Current best
0.0
005
00.5
-15
40
80
100
150
200
100
200
300
100
Objective function evaluation
Objective function evaluation
Objective function evaluation
LES-ADAM: L 250, P- (default)
Current best
-1-
logEl
logEl-DSP
-2-
TURBO
HCI HCI-GIBO
-3
Sobol random
-2
100
200
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 20: Out of model comparison, complexity extremely low: Median, 25-, and 75 75-percent quantiles detailed results
d' 10
50
100
0
cumulated
-50
400
-200
-100
20
40
100
100
150
200
200
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
LEAM: 250, (default)
MES
Cumulated
0
logËt
-500
-250
logEl-DSP
TURBO
-500
1000
Sobol random
-750
1500
0
100
200
300
400
100
200
300
400
Objective function evaluation
Objective
Figure 21: Out of model comparison, complexity extremely low: Median, 25-, and 75-percent quantiles detailed results
31

---

Published as a conference paper at ICLR 2026
D.4 ADDITIONAL DETAILS AND RESULTS ON SYNTHETIC AND ORRENTEDD OBJECTIVE FUNCTIONS
In total, evaluate LES nine benchmark functions (Fig.23 and 24). On functions with single local optimum (square function f(xx) æx: ), all methods reliably identify the optimum, though LES and TuRBO achieve lower cumulative regret, underscoring the advantage local search in this setting. In contrast, the 5-d Ackley function designed as failure case for LES leads all methods, including LES and the global baselines, to perform poorly (Appx. D.4). Surprisingly, for 30-d Ackley, LES and TuRBO outperform global methods. However, LES has high run-to-run variance which indicates that some runs get stuck in local optima.
In the rover (Wang et al., 2018) and Mopta08 (Jones, 2008) tasks, LES, logEl and TuRBO perform similarly with LES being best in the rover task and logEl being best in the Mopta08 task. In the lunar lander task (Brockman al., 2016). LES is not competitive. The lunar lander task has multiple local optima where LES getting stuck in some runs (see Fig. 22).
The lunar lander problem (Fig. 22) and the Ackley function both contain many local minima, which makes them particularly challenging for our local method. Interestingly, LES performs still best on the 30-dimensional Ackley function. Overall, LES achieves the lowest cumulative regret sometimes tied with other algorithms except on low-dimensional problems with many local optima (Ackley- d Lunar). For logEi,, high exploration costs occur only in low dimensions, which may be explained by its tendency to repeatedly sample the same location once it has found a (local) optimum. In terms of simple regret, LES matches the baselines except on the low-dimensional. multi-modal benchmarks (5-d Ackley and Lunar).
All BO algorithms use the hyperparameter as presented in Table 10. Hyperparameters follow (Xu al., 2025), using a box hyperprior and length scale initialization scaled by vd favor low model complexity. Observations are generated without noise. We use 20 seeds for the policy search tasks and 10 seeds for the synthetic functions.
Table 10: Model Hyperparameters for the synthetic and application-oriented objective functions
Name
Description
Value
k(-,-)
kernel
SE-ARD
p(I)
length-scale hyper prior
None
observation noise
fixed at 0.001
GP output scale
variable
Imax
length scale upper bound
Vd
Imin
length scale lower bound
0.05
linit
length scale initialization
0.2vd
hyperparameter optimization frequency
after every sample*
standardize data
yes
*Except for the GIBO variants, where optimize the hyperparameter only after each step.
32

---

Published as a conference paper at ICLR 2026
Objective Function Along Random Direction
200
URjaative Value
1.00
-100
-200
1.00
0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.00
Parameter Space Direction
Figure 22: A random slice through the deterministic lunar lander objective function. Although the objective is deterministic, we see multiple noise-like local optima and a prominent step in the objective function landscape. Both properties are hard to model with a GP using an SE kernel with small observation noise.
Square d 5
x10 Dixon-P. =
Ackley d= 5
1.5
0.45
18
0.30
1.0
12
0.15
0.5
0.00
0.0
50
100
0
50
100
50
100
Square d 30
1 Dixon-P. P. d= 30
Ackley d = 30
2.4
20
3.0
f(x)
1.6
15
0.8
1.5
10
0.0
0.0
200
400
0
200
400
200
400
10
Lunar = 12
x 101
Rover d 60
x002
Mopta d 124
1.5
9
4.2
f(x))
0.0
6
3.6
3
3.0
3.0
0
2.4
120
240
0
200
400
200
400
Evaluations #
LES (ours)
logEI
HCI-GIBO
MES
TuRBO
Sobol random
Figure 23: Median, 25-, and 75-percent quantiles synthetic and application-orien orientte objective
functions
33

---

Published as a conference paper at ICLR 2026
Square 5
x10 Dixon-P. 5
Ackley
1800
30
f(x))
1200
15
4
600
0
0
50
100
100
Square d 30
x 1
Dixon-PP d=
Ackley
1.5
900
7500
f(x*)
600
1.0
5000
300
0.5
2500
0.0
200
400
0
200
400
200
400
1004
Lunar = 12
x104
Rover d
60
x10 Mopta d 124
2.5
3
1.5
0.0
2
1.0
2.5
1
0.5
0.0
120
240
0
200
400
200
400
Evaluations
LES (ours)
logEI
HCI-GIBO
MES
TuRBO
Sobol random
Figure 24: Median, 25-, and 75-percent quantiles of cumulative cost synthetic and application- oriented objective functions
34

---

Published as a conference paper at ICLR 2026
D.5 ABLATIONS ON APPROXIMATION ACCURACIES AND RUNTIME
Figure 25 illustrates the effect the number of Monte Carlo samples and the number of equally spaced points P taken from each descent sequence. We evaluate this in the out-of-model GP sample scenario with medium complexity (see Sec. 6.2). As expected, more accurate approximations yield better performance, with the differences most pronounced in the d = 50 case. While L = 250 and P 16 performs best, we adopt 250 and P in our experiments as a compromise between runtime and accuracy.
We further verify that conditioning on function values instead of gradients in the descent sequence does substantially harm performance. For runtime and memory reasons, gradient conditioning LLFS-ADAM-GGrad--- was only run with coarse discretizations, up to 300 samples and excluding
50.
5=5
d=10
d= 20
-2
Current best
-2
-3
40
60
80
100
50
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
d 30
d' 50
-2
current best
LES ADAM: 250, P 8 (default)
LES-ADAM: - 250, P
-4
LES-ADAM: 250, P
-6
LES-ADAM-Grad, Cond.. 20, 8
-8
-10
400
100
200
Objective function evaluation
Objective function evalustion
Figure 25: Comparing different acquisition function approximation accuracies the better the approximation (larger value and L) the better the results (Out-Of-Model Comparison on GP-Samples medium complexity).
The computational cost of LES is closely related to the chosen discretization, i.e., the values of L and P. To compare influence the acquisition function choice on overall runtime we evaluate it in the within-model comparison case. Table 11 shows the results for medium complexity. For comparison, we also include the runtime of our baselines. Additionally, Figure 26 shows the average runtime per iteration.
Our proposed approximation of LES requires roughly 10 times the wall-clock time compared to TuRBO, with average of 17 seconds per iteration to select the next query. Notably, BoTorch's logEl has a similar runtime.
As caveat, runtime depends strongly several factors, including settings for acquisition function optimization. We used the default configurations from BoTor tutorials for all baselines and did not optimize any baseline implementation for speed.
35

---

Published as a conference paper at ICLR 2026
Table 11: Average computation time per iteration LES-ADAM for the medium complexity within model comparison, i.e., without GP hyperparameter optimization. Results are given in seconds and are averaged over 20 seeds.
d =
5
d
10
d = 20
d = 30
d = 50
LES: L 250, P 8 (default)
11.4
12.6
16.5
17.1
17.6
LES: L 230, P 4
10.6
11.7
14.0
14.3
15.4
LES: L 250, P 16
13.8
16.6
24.5
24.1
25.3
LES: L 20, P=
3.5
3.8
4.0
4.2
4.3
MES
8.2
2.1
5.1
1.8
1.3
TuRBO
0.4
0.4
1.2
1.4
1.4
logEl
0.3
0.5
15.5
23.0
24.0
d=
d 10
d=
25
50
40
Time In S8C
15
15
30
10
10
5
10
0
0
Iteration
Iteration
Iteration
d=
=
8.0
LES ADAM: 250, (default)
LES ADAM: 20,
Time sec
LES-ADAM-Graa ADD.--Gadd-Con..
20,
40
LES-ADAM:
40
LES ADAM: 250.
MES
20
20
TURBO
logEl
100
200
300
400
100
200
300
400
Figure 26: Evaluating LES with different local optimizers (Out-Of-Me) Of-Meeell Comparison on GP- Samples low complexity)
D.6 DESCENT SEQUENCE LENGTH AND STEP SIZE
To further evaluate the behavior of LES, examine the average length of the descent sequences, i.e., 1a o with 2/ = 2t and the step size (average distance between the new query and the current incumbent), i.e. | 2.+1l. Table 12 shows the medium-complexin within model-comparison for LES-ADAM with default configuration. We aggregate results of the first and second half of the iterations.
36

---

Published as a conference paper at ICLR 2026
Table 12: Average descent sequence length and step size (with % of seq. length in brackets) for LES-ADAM; L 250, P = (default): Comparison between first and second half of iterations.
seq. length (Ist half)
seq. length (2nd half)
step size (Ist half)
step size (2nd half)
0.0900
0.0051
0.0173 (19.2%)
0.0026 (51.5%)
10
0.1906
0.0200
0.0254 (13.3%)
0.0068 (34.1%)
20 0.3966
0.1206
0.0468 (11.8%)
0.0737 (61.1%)
0.6470
0.3597
0.0838 (12.9%)
0.0627 (17.4%)
50
0.9697
0.7946
0.1559 (16.1%)
0.1274 (16.0%)
We can observe that, the step size is always significantly smaller than the sequence length, so entropy reduction is not highest at the descent sequences endpoints. The step size and descent sequence length decrease in the second half of the optimization.
In addition. Fig. 27 shows the average step size and sequence length the medium- cemplexxit within model-comparison case for LES-ADAM with default configuration. We can see that both the sequence length and the step size decrease over time, which further indicates local search behavior.
d
0.5
0.4
0.8
Distance (L2)
0.6
0.6
0.2
0.1
0.2
0.2
20
60
80
50
100
150
100
200 Iteration
300
Iteration
Iteration
d 30
d= 50
1.0
Distance (U2)
0.6
0.8
Step Size
0.4
0.6
Average Sequence Length
0.2
0.0
100
200
300
100
200
300
Iteration
Iteration
Figure 27: Average descent sequence length and step size for LES-ADAM: L 250, P= (default)
In summary, the LES framework automatically chooses the optimal (with respect to entropy reduction) exploration behavior/step size from the current model discover the descent sequence.
D.7 COMPARING DIFFERENT ITERATIVE OPTIMIZERS
If not stated otherwise, the ADAM optimizer was employed as the local optimization algorithm throughout this work. However, the general framework is applicable to any kind of iterative optimiza- tion. Therefore, evaluated the impact of different iterative optimization schemes on the overall performance. We use the out of model comparison GP sample scenarios (see Sec. 6.2).
We expect that the performance of different inner optimizers also depends on the kernel. Sample paths from a GP with a Matérn 1/2 kernel are not continuously differentiable, making LES-ADAM and LES-GD less suitable choices. In such cases, LES with CMA-ES other zeroth-order order optimizers (e.g., hill climbing or pattern search) may perform better. We leave a more thorough evaluation the benefits of different local optimizers in LES for future work.
37

---

Published as a conference paper at ICLR 2026
For Adam 500 local optimization steps step size of 0.002, and default Keras momentum hyperparameter (31 = 0.9, 32- = 0.999). As an alternative, we also evaluate a LES- ADAM variant with less aggressive gradient smoothing (81 0.5). Instead of conditioning the gradient observations, we condition on function values. We show in Appx. D.5 that this simplification justified empirically.
ADAM
Gradient Descent For Gradient Descent (GD) we also use 500 local optimization steps and smaller learning rate of 0.0001. Preliminary results with larger step size (the same as ADAM) has produced oscillating behavior. Similarly to ADAM we condition on function values instead of gradient observations.
CMAES As third optimizer choose CMAES and run it for 50 steps. We approximate the descent sequence by the mean of the parameter distribution. The a hyperparameter is set to 0.5 and similar ADAM and GD warm-start CMAES from the best solution found far. Due the high computational cost of running CMAES on multiple GP samples in each iteration, we evaluate only in the 5-d and 10-d case and use coarse discretization. Note that CMAES is zeroth-order optimization algorithm and therefore does not require the GP-samples to be differentiable.
Figures 28 30 show the results for low, medium, and high complexity. LES-CMAES performs better than the other algorithms for d = 5 and low problem complexity. This may hint to a more global search behavior and may indicate that the optimizer's properties on the individual samples may carry over the respective LES version. However, already at d = 10 higher complexity LES- CMAES falls behind. This can be attributed to the worse performing global optimization or to descent sequence approximation using the mean of the population not being accurate enough. Both LES-ADAM version perform similar in all complexities. LES-GD performs worse than LES-ADAM in the low-complexity case. However, in the medium and high complexity cases LES-GD performs best.
Overall, results highlight that investigating various local optimizers for different model properties is an interesting direction for future research.
d=10
d= 20
0
0
1
Current best?
-1
60
100
50
200
100 Objective function evaluation
400
Objective function evaluation
Objective function evaluation
d 30
d = 50
Current beat?
-2
LES-ADAM: L 250, P (default)
LES-ADAM (beta, 1 0.5): 250,
250,
LES ADA:: L 20, P
-6
LES CMAES: 20, P =
300
400
300
400
Objective function evaluation
Objective function evaluation
Figure 28: Evaluating LES with different local optimizers (Out- (Out-Of-Model Comparison on GP- Samples low complexity)
38

---

Published as a conference paper at ICLR 2026
5
d-10
d
20
Current best.
-2
-2
44
-3
-6
40
100
50
100
150
200
100
200
100
Objective function eval uation
Objective function evaluation
Objective function evaluation
-2
Current beat!
LES-ADAM: 250, 8 (default)
-4
LES-ADAM (beta 1 - 0.5): L 250,
LES-GD: L 250,
20,
LES CMAES: L 20, P
-10
Objective function evaluation
Objactive function evaluation
Figure 29: Evaluating LES with different local optimizers (Out-Or-Model Comparison on GP- Samples medium complexity)
d= 10
= 20
-2
Current bext
-4
-3
-6
-8
40
60
80
100
50
100
150
200
100
200
300
Objective function evaluation
Objective function evaluation
Objective function evaluation
d= 30
d 50
-2
Current best.
LES-ADAM: 250, (default)
-4
(bela_ 0.5):
-6
LES 20, P
-8
LES-CMAES L - 20, P -
-10
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 30: Evaluating LES with different local optimizers Dout-Of-Modes Comparison on GP. Samples high complexity)
39

---

Published as a conference paper at ICLR 2026
E A STOPPING CRITERION FOR LOCAL ENTROPY SEARCH
E.1 METHOD
In practical applications, it is essential to determine when to terminate the optimization. In the previous section, we performed local optimization on multiple posterior samples. This enables us to adopt the Honte-Carlo-basee stopping criterion proposed by (Wilson, 2024) in local setting without incurring significant additional cost, as we can directly reuse the samples generated during the acquisition step. To achieve this we define new notion of local regret:
Definition (Local simple regret), Given the posterior GP fi at BO step t. the local simple regret with respect to the model-based local optimum fi sup, fe(ar) of candidate point E X is
(x) - St ft(x).
(31)
Local regret formalizes how close we are to the best value reachable from the user's initial guess by the optimizer O. This attractive when the global optimum is irrelevant or unattainable in practice. We stop the optimization if the current solution is within e of the optimum with probability ò, i.e., when it is (e, 6) locally optimal:
Definition 2 ((E, 80-local optimality). Fix tolerances > 0 and á (0,1). 1). A point observed up to step t (e, -0l---ollll-ppiiiie (with respect to z and optimizer O)
Pt(r
1.
(32)
We estimate the probability of the regret being smaller than epsilon using Monte-Carlo sampling:
Σ 1=1
= - 1 Se).
Pr 5s) ~ I
(33)
1=1
We follow (Wilson, 2024) and design probabilistic stopping rule that leads to bounded local regret (31) with high (within-model) probability. Next, we restate the formal results from (Wilson, 2024) for LES.
Assumption 1.
The search space is the unit hyper-cube X' 17= 1]
There exists constant L3 so that V Vx, X, |x 2) -(z,z)
x(x,x') La || x' 2olloc.
The sequence of query locations (at) is almost surely dense in X.
We show in Appx. G.1 that LES fulfills the third assumption for specific kernels.
Theorem 1 (Proposition 2, (Wilson, 2024)), Assume 1. Given risk tolerance 5 > O, define non-zero probubilities 5mod and dest such that dmod + Sest 8 and let (8tes) 120 be a positive sequence that Eee 8t S Sest. For any regret bound
if the Monte-Carlo test of (Wilson, 2024, Alg. 2) is run al each step l. E No with tolerance o,ost to decide whether a point satisfies Pr(r(()) (x) < 8 2 1 8mod, then LES almost surely terminates and returns a solution with probabilistic regret that satisfies Definition 2.
E.2 RESULTS
The stopping times (Sec. E. for LES on the out-of-model comparison with low model complexity are Tab. 13. For d 2 30 fewer than half the runs stop within the budget of 400 evaluations. When compared to the results in (Wilson, 2024) these results show that the local optimization needs fewer samples before stopping. These results reinforce the intuition that reaching a local optimum is easier than reaching global one in black-box optimization problems.
40

---

Published as a conference paper at ICLR 2026
Table 13: Median stopping times with decision every 25 queries (d 0.05) model comparison.
d =
5
d = 10
d = 20
0.1
50
150
325
0.01
50
175
350
Table 14 summarizes the results for the stopping rule within model comparison case with low problem complexity. For comparison, (Wilson, 2024) reported average stopping time after 100 queries for the 4-d within-model case. Note that we choose the results (Wilson, 2024) for the low noise case, since it is most fitting to our experiments. The parameters reported in Table 3 lead to BO run being stopped after kmax = 248 out of 250 samples show local regret smaller than &.
Table 14: Number of queries until half of the runs stopped (6 0.05). Decision every 25 queries within model comparison.
d
5
d
10
d
20
0.1
50
150
275
0.01
50
175
300
41

---

Published as a conference paper at ICLR 2026
F ALTERNATIVE INFORMATION-THEORREE LOCAL ACQUISITION FUNCTIONS
We propose additional cntommation-theorettte local acquisition functions that closely related to the local entropy search paradigm: Local Thompson sampling and local-optimum LES. Both are conceptually more straight forward and easier compute than LES but perform worse.
F.1 LOCAL THOMPSON SAMPLING
In local Thompson sampling (L--TS) we sample only one path from the GP, which we then minimize locally using the ADAM optimizer and query at its minimum. This method proves to be significantly more computationally efficient than the entropy search approach, it avoids the need for the relatively costly Monte Carlo approximation outlined in equation (16).
We assess local Thompson sampling to better understand the benefits of considering the distribution over descent sequences at each iteration, as implemented in LES. We expect that L-TS may not perform well LES, since L-TS optimizes single descent sequence in greedy manner. In contrast, LES recognizes that multiple descent sequences exist and seeks to maximize information gain across all of them.
F.2 CONDITIONING ONLY THE LOCAL OPTIMUM
In Appx. B.I, we have shown that directly conditioning on the local optimum is not possible in general. That is, we cannot condition GP on O in
E H (v((z) D., 2%
E Hp(((()) De, O.d)
(34)
cannot encode that the local optimum location =dd was reached through a local optimizer from point zg. What encode is that xnd is local optimum defined gradient of zero and positive (known) Hessian:
1
le (v(x) D2,0%%
L
(35)
H (y(m) D. D ( (at () (wt (A(
I.
Note that the exact values of the observations again are irrelevant for the conditional entropy. This gives rise to the LES-ADAM Opt. Cond. acquisition function.
We evaluate LES-ADAM Opt. Cond. because aim demonstrate that the sequence leading the local optima contains valuable information; merely conditioning on the local optimum-thh the final point of this descent sequence-is insufficient.
F.3 RESULTS
Figure 31 shows that LES-ADAM outperforms the other information-theoredd approaches, with the performance gap widening in higher dimensions. The experiments are conducted in the out-of- model GP sample scenario with medium complexity (see Sec. 6.2). Overall, the results indicate that considering multiple descent sequences per itcration, as well as the entire descent sequence rather than only the distribution of local optima, improves performance.
42

---

Published as a conference paper at ICLR 2026
d-3
d'110
d-20
-1
Lurrent best.
-1
-
2
20
60
80
100
50
100
150
200
100
200
300
400
Objective function evaluation
Objective function evaluation
Objective function evaluation
30
d 50
-2
-2
current DEStr
LES ADAM: 250, P 8 (default)
-4
LES-ADAM-Opt.Com Cond.: 250,
Thempson Sampling
-6-
100
200
300
400
100
200
300
400
Objective function evaluation
Objective function evaluation
Figure 31: Median, 25-, and 75 75-percent quantiles, out-Of-model comparison GP-Samples medium complexity).
G THEORETICAL RESULTS
This section contains some theoretical results in support of the main claims of the paper. We use the notational shorthand (;,) k(., D,).
G.1 LES QUERIES ARE DENSE
Lemma 1 (Density of LES maximizers). Assume X [0. 1jd and let ka X continuous, positive-defuit kernel that admits the no-empty-ball property (Wilson, 2024, Definition 3). Vx, x & D, M(x, x²) O, and the descent sequence (z,)) contains least one & DD almost surely. Fix a noise variance 72 2 and denote by ki, of the posterior covariance and predictive variance after I evaluations. Then, for every i. N and all x. x' EX
X x X R be
kx x) > ke(x', xx) =0 = aLES,(()) > (LES,((x')
(36)
Consequently the sequence (æx) of maximizers E arg max (1.)..(x)) form a dense sequence X almost surely.
Proof. If (x', x') = 0, positive-semidéeniiennss implies ke(x', x)) = 0 for every z E X. Hence, of(x') = of Xps (x') = 22 for every Monte-Carke draw Xps. so aLES,e(x') = 0.
Take with k x)) > O. Because the the descent sequence (zn) contains at least one Dr almost surely the posterior covariance GP variance update gives
zero the covariance vector ky (æ, Xps) non-zero. The
of X (x) (0)) (ar Xns) [K((X XnS) + + ky (X)s,
(37)
and the quadratic form on the right is strictly positive, hence x (x) < (2)). Therefore each logarithm inside o1.Fs,((:) is positive and their expectation is strictly positive (r.Fs.((e)) > 0. Density of the query points now follow from (Wilson, 2024, Proposition 4).
43

---

Published as a conference paper at ICLR 2026
G.2 GRADIENT DESCENT PATHS UNDER GP PRIOR WITH A SQUARED EXPONENTIAL KERNEL
In this section we zoom in on a specific instantiation of LES that samples candidate points by running gradient-descent (8) on functions drawn from a squared-exponential (SE) GP prior. This section explains why that particular pairing sensible starting point. We show, with a suitably step size, gradient descent sequence starting from an initial design can reach any subset of the domain with positive prior probability. addition, for any finite horizon the distribution of such sequences has full support on the corresponding product space and can therefore realize any finite sequence. Importantly, these reachability and support guarantees ensure that no part of the search space is ruled out by construction in this setting.
Assumption 2 (Design domain), The search space X C Rd is non-empty, compact, convex, and has non-empty interior.
We formalize the assumptions as follows.
Assumption 3 (Step size). Let X C R. be compact. For every realized objective f E C² (x) denote by L(f) the global Lipschitz constant of its gradient. Choose step size n(f) > 0 satisfying
n(f) L(f) < 1.
With this choice the gradient-descent map f = x - --m f is a strict contraction on X.
Assumption snntared-exponentiin prior). The objective is random draw from p(f)
GP ksE), that f E C ( (X) almost surely and the associated RKHS is dense in C (2)) with the -orm.
Lemma 2 (Open-set reachability of GD paths). Let Assumption 2, 3, 4 hold. Define the gradi- det-descent iterates as in (8) so that
Zu X,
Zn+1 In - (((n), n2 0.
(38)
Then for every non-emply open set U CX
P=((z)) 4 > 0.
(39)
Proof. Fix U + Ø open and choose U and a horizon m E N.
Since the map T x)(2) z (=) is contraction (Assumption 3) one can constructs a smooth function f ( such that
Zm (8*) u,
||V & T...
(40)
Since the RKHS Higg of the squared-exponential kernel is dense in (X)) every Ca-ball flf lf < < contains at least one element of Hesn By the Gaussian measure support theorem (Vaart, van der & Zanten, van, 2008, Lem. 5.1), every open set that intersects HasR has positive prior probability, hence
= (f
Pr[lf-- < 0.
(41)
The mapping (x) g + 4./m (m) (xx) is continuous in the C"-noom when nL. < 1. Hence there exists & > such that Ilf f*lloi <E =
= Fm (f) U.
Combining this with (41) gives Pr[#m (f) U] > O, which implies (39).
Corollary (Full support of finite GD paths). Fix an integer horizon N 2 0 and define
O x XN11,
-
O(f) = (Zo. Ei.... 22)).
(42)
where (ar)) are obtained by gradient descent. Under Assumptions 2-4, the forward measure O₂ PPO, ksR)) has full support on X iee. for every open cylinder set Up ... x UN C N with all U, open and non-empty.
Pa. ÆN) E Uo x ... x UN > 0.
(43)
44

---

Published as a conference paper at ICLR 2026
Proof. Proceed inductively on N.
Base case N = O: trivial because zo is fixed.
Inductive step: Assume the claim holds up horizon N 1. Given open Vo..... Un. the induction hypothesis provides a function f and > such that f - - < E implies (To..... xN-1) E Uo x... x -1 Apply Lemma 2 with starting point xx-1(f") and target open set UN to obtain a further refinement e'. Choose min and use the support property (41) to conclude the probability is positive.
As long k (a, a) > 0 Va E X' the same applies to the posterior. The proofs are identical because conditioning on finitely many points does not change the RKHS nor the support of the measure; only shifts the mean.
In summary, Lemmas and 1 together show that, in the SE-prior/GD instantiation of LES, the candidate-generafie mechanism is fully expressive: no open region is inaccessible and no finite GD sequence is excluded.
45


Reviews:
[{"review_id": "tiSi67xtS1", "reviewer": "Reviewer_o3dG", "summary": "Local Entropy Search (LES) is presented as a local, information-theoretic Bayesian optimization framework aimed at finding better solutions in complex, large design spaces. LES combines iterative local optimizers with the entropy-search principle to identify the best reachable solution from a given initial design $x_0$ for an expensive-to-evaluate black-box function. The key idea is to target the solution produced by a chosen local optimizer by focusing on its descent sequence, and to propagate the uncertainty of a Gaussian process (GP) surrogate through that optimizer to induce a distribution over possible descent paths starting from the initial design. This leads to an LES acquisition that selects the next candidate by minimizing the entropy of the descent sequence, equivalently maximizing the mutual information between the new observation and the descent sequence conditioned on current data. The derivation uses a closed-form expression for predictive entropy and a Monte Carlo estimate of the conditional entropy over sampled sequences. With these components in place, the paper presents the LES algorithm. For practicality, conditional entropy is evaluated at discretized support points along the descent sequences, and an early-stopping criterion is employed. Empirically, LES shows strong performance on high-complexity settings and remains competitive with TuRBO.", "questions": "1. On local minima traps: the paper mentions multistart or switching between local and global algorithms. A recent ICLR paper by Adebiyi et al. (2025) proposes optimizing posterior samples via root-finding to identify starting points that lie near the global optimum of a posterior sample. Can the authors comment on the possibility of integrating such sorting algorithm in that paper to guarantee the selection of the ideal starting point to further extend the applicability of LES in multimodal scenarios?\n\n2. From the results, it appears LES and TuRBO remains competitive in several complex settings, can the authors comment on the incentives of LES over TuRBO?\n\n3. Although minor, could the authors comment on the selection of learning rate for LES-Adam? This can materially affect performance, especially in GP based settings.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper shows real depth, both theoretically and empirically. The authors clearly know the literature, handle the fine details, and take a principled path to build LES. \n\n2. The empirical study is broad, with enough variants to support strong claims about LES performance across complex settings, different distribution regimes (in-model and out-of-model), and a thoughtful set of baselines.\n\n3. The paper gives a robust treatment of edge cases. It shows the one-step equivalence to GIBO, explains why certain alternative formulations are intractable, introduces an early stopping rule based on probabilistic regret, and provides demonstrations across multiple levels of complexity.\n\n4. LES works across optimizers. The paper backs this with results for Adam, CMA ES, and others, which makes the robustness claim of LES credible.\n\n5. The authors paid careful attention to scalability, including a batched variant (QLES) for practical deployment and efficient sampling via decoupled GP.\n\n6. The experimental setup is clean and complete, which makes the work reproducible.\n\n7. The authors also provide a clear and sufficient exposition of all components of the LES algorithm, with careful pointers to the appendix for detailed explanations, which helps both interested and unfamiliar readers.", "weaknesses": "1. The most prominent weakness, which the authors already acknowledge, is the tendency to get trapped in a local minimum basin, especially in complex settings with a highly multimodal posterior. The paper offers a careful discussion of this issue and introduces a stopping rule to trigger restarts, but the risk remains in challenging landscapes.\n\n2. LES performance depends on several core components, including the chosen optimizer, the surrogate model specification, and the underlying problem complexity. All of these are however not uncommon in BO settings, and the authors provided a clear account of this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "A5d88t4Xy3", "reviewer": "Reviewer_yURN", "summary": "This paper considers the problem of black-box optimization, in which one is trying to optimize a function while having access only to noisy function calls: no gradient, convexity, or other information is available.\nIn this setting, Bayesian Optimization (BO) is the state-of-the-art approach. BO learns a statistical surrogate for the objective and plugs it into an _acquisition function_ (AF), whose maximization yields the next design to evaluate, in an exploration-exploitation balancing way.\nThe authors contribute to this field with the introduction of a novel acquisition function, Local Entropy Search (LES), which belongs to the realm of information-theoretic AFs. Such AFs aim to find designs that maximize the _information gain_ about a random quantity, usually of interest for BO purposes, like the optimum $f^\\star$, its location $x^\\star$, or even $(x^\\star,f^\\star)$. The proposed LES selects a design that maximizes the information gain about a _local optimum_, here characterized as the last iterate of an arbitrary optimizer like gradient descent. After introducing their theoretical framework, the authors derive an efficient algorithm for computing LES and perform an extensive set of experiments, comparing LES against other state-of-the-art baselines on multiple synthetic and real-world examples, jointly with numerous ablation studies. LES emerges as a strong competitor by delivering the best overall performance, thus providing empirical evidence about the relevance of focusing on local optima rather than global optima when searching large, complex design spaces.", "questions": "Since I don't think the paper suffers from any major weaknesses, my questions stem from genuine curiosity rather than a desire to challenge the method. \n\n- Throughout the paper, an RBF kernel is employed for the GP surrogate. Draws from that surrogate are used to compute the acquisition function, where a finite number of optimization steps are performed for each draw, leading to a discretized descent sequence, again for each draw.\nGiven that the RBF kernel produces infinitely differentiable function draws, these should be quite amenable to gradient descent /ADAM, putting aside convexity. If one knows that the black-box function is not as regular as draws from an RBF kernel, one could opt for, say, a Matern 1/2 GP surrogate, whose draws should be more difficult to optimize. Have you tried to see how the performance of the AF changes as the kernel changes? In particular, I would assume that the results reported in Appendix E.6 (comparing different iterative optimizers) might vary conditionally on the kernel?\n\n- It might be interesting to discuss the case of latent space BO, where one learns a continuous latent representation $\\mathcal{Z}$ of a structured space $\\mathcal{X}$ (e.g., JT-VAE [1,2]) and performs BO within that latent space, decoding any selected design $x=h(z)$ and then evaluating it. Without any incentive, there is little reason to think that the function $z \\mapsto f(h(z))$ is smooth, and hence an AF based on maximizing the information about sequences produced by a gradient descent optimizer might not perform as well. As in the previous question, perhaps then a zero-order optimizer like CMAES might outperform ADAM/GD. \n\n[1] Junction Tree Variational Autoencoder for Molecular Graph Generation, ICML 2018\n[2] Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining, NeurIPS 2020\n\nSome comments:\n- Appendix E.6: performing a fair comparison with CMA-ES is always tricky, in my mind, given the number of hyperparameters it involves. You mentioned $\\sigma$, but there is also the popsize, the evolution strategy conducted every generation (e.g., bipop), to only mention two.\n- noise is kept pretty low throughout the paper, between $0.001$ and $0.02$ for standardized data. I know this is not the point of the paper, but varying the noise to see the impact would have been interesting as well. \n- page 21, a superscript \"2\" points to a footnote \"3\".\n- appendix F, I would also write the definition $f_t^\\star = \\text{sup}_x f_t(x)$\n- Defintiion 2: use $\\varepsilon$ or $\\epsilon$ not both ?\n- Algorithm 1 L9 involves $k_{test}$, shouldn't it be $\\delta_{test}$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed AF belongs to the class of information-theoretic AFs, a class of theoretically grounded strategies. Framing the problem as trying to gain information over local optima rather than global optima is novel and well-motivated, specifically for high-dimensional settings, and the practical execution into a computationally reasonable algorithm is also a contribution in itself. \n\n- The experiments section is quite extensive, to say the least. I have to say that I rarely encounter BO papers involving this level of thoroughness at the experiment section level. This was quite pleasant.\n\n- ``Despite'' such a large breadth of experiments, LES does not seem to suffer any major flaw, compared to other baselines, and achieved the overall best performance. While one can always pretend that problems were cherry-picked to favor LES, I consider that the range of experiments here is wide enough to provide a fair representation of the test cases usually considered in the BO literature.\n\n- Besides comparing to other baselines, the authors carried out several ablation studies to assess the impact of modifying individual blocks, which did not reveal any major flaw either.", "weaknesses": "I cannot pinpoint concrete weaknesses. The limitations of the approach are clearly stated, albeit briefly in the conclusion, but are presented in more detail in the appendix. I agree with such limitations; they do not represent grounds for rejection in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "WOjV0JlFOk", "reviewer": "Reviewer_gXxy", "summary": "This paper proposes Local Entropy Search (LES) , a Bayesian optimization method for local optimization that aims to find the best solution reachable by an iterative optimizer starting from an initial design, rather than searching for the global optimum. The core idea is to reduce uncertainty about descent sequences by sampling GP posterior, running gradient optimizer on each sample to obtain finite step trajectories, then querying points that maximally reduce the average entropy of these trajectories. Empirically, LES outperforms global entropy search methods and existing local BO baselines on various benchmark problems up to 124 dimensions, though the method provides no theoretical guarantees and involves significant computational overhead compared to simpler local BO approaches.", "questions": "- Is there any intuition that the algorithm will work better in high dimension? Because this is slightly counterintuitive to me as I would imagine the local trajectory get randomly distributed in high dimenison, making an entropy reduction also very random.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The acquistion function is very straightforward.\n- The combination of entropy search with local search is freshing", "weaknesses": "- The empirical benchmark, although demonstrate up to 124 d, is on somwhat easy and not very representative BO benchmark, its unclear that the method will really be competitive in high input dimensionality or not. I think to demonstrate the real benifit of the acquisition function, which to me is the most promising point of this work, is to conduct more thorough empirical results to provide more compelling results.\n- The algorithm is rather heuristic without too much theoretical insight. The existing theoretical analysis does not provide any insight.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "laLVJzr7ME", "reviewer": "Reviewer_8PaV", "summary": "The paper proposes a new Acquisition Function (ACF) for Bayesian Optimization (BO), which especially improves the local search using the idea from two other main papers (Hennig & Schuler, 2012) and (Muller et al., 2021). In general, replacing the conventional sampler of the ACF at one point with a trained Gaussian Process model (GP), then maximizing utilities, this method proposes a gradient descent-based ACF with finite sequences to determine the potential candidates. The gradients of the GP model are used to create the sequences from different samples, and the potential candidates should minimize the entropy of these sequences, based on the assumption that reaching local extrema will have a stable gradient path. Their main contribution is the improvement of the stability and robustness of the local search within the GP model. Experimentally, the algorithm delivers remarkable performance in synthetic benchmarks, while showing marginal improvement in real-world problems. In addition, the ACF-only benchmarks are impressive, and the computational cost is handled well. The discussion is well done, which explains clearly the working conditions and the limitations of the approach. Overall, this work proves a slight contribution, which can potentially improve the outputs of low-dimensional problems (under 100 dimensions).", "questions": "There are some concerns that need to be clarified to strengthen the robustness of the work.\n\nIs there any mathematical proof or empirical validation regarding the behaviour of the LES ACF, particularly concerning the issue of incumbent search? This could be clarified if the data-point maps indicate whether the samples are regionally concentrated. The incumbent search problem was raised by (Hvarfner et al., 2024). Although the authors demonstrate that the LES ACF can balance exploration and exploitation through entropy minimization and achieve full-space coverage, stabilizing sequential gradient chains may still induce incumbent search and reduce the ability to perform large exploratory jumps. Even though the use of optimizers such as ADAM supports escaping local optima, and the authors state that the global value is not the target, being easily trapped in local minima remains a major bottleneck. Furthermore, regionally clustered data points may cause the hyperparameters to reflect only the characteristics of nearby areas, making it difficult to escape those regions. Addressing this could lead to discovering higher-quality local optima or even the global optimum.\nIn the experimental setting, the number of initialization samples is only two. Why is this number so low compared with other works? Has any empirical study been conducted to justify this hyperparameter choice? At the beginning, with only two samples, BO behaviour is purely exploratory or even random, relying heavily on the prior hyperparameters. BO typically requires a sufficient number of observations to adequately represent the search space, whereas the LES ACF amplifies this early-stage phenomenon by over-exploiting incumbent values. Consequently, the exploration phase, crucial for finding global solutions, is further reduced during the stage that contributes most to global discovery. A minor question: since BoTorch supports standardization, what does the statement “data is not standardized” specifically mean?\n(Hvarfner et al., 2024) claim their method improves performance in high-dimensional problems, most exceeding 100 dimensions. A benchmark with a higher dimensionality is therefore necessary to clearly reveal the limitations. Common synthetic benchmarks such as Levy or Hartmann should be included for more comprehensive comparison. Other local search methods have also shown strong results without neglecting global optimization, such as BAxUS (Papenmeier et al., 2022). The concern about BO-based benchmarks arises from the alignment between the target model and the surrogate model used by the optimizer. When both share similar characteristics and nearly identical uncertainty-quantification mechanisms, especially in within-model comparisons, the results may be biased. This study employs Matheron’s rule for sampling, which provides superior posterior draws, while other methods do not leverage it. Thus, much of the observed improvement might be attributed to the Matheron’s rule sampler rather than the LES ACF itself. Adding additional synthetic benchmarks would help clarify this effect. There is no need to test multiple levels of GP-based benchmarks.\nThere are further suggestions for improving the presentation:\n\nClaiming that the global optimum is not the objective is acceptable; however, the ability to escape local optima deserves stronger emphasis. Completely disregarding global-optimum search is a significant drawback that limits the method’s applicability. If this design choice is justified more clearly and explained earlier in the paper, the overall persuasiveness would increase considerably.\nFor your consideration, it may be beneficial to adopt a multi-start ACF. Although this may slow down computation, it could prevent the method from getting trapped in a single region. Using only one current best value is risky; incorporating two or three additional starting points in different regions, while reducing the number of gradient chains, could achieve a better balance between efficiency and reliability. Increasing the number of initial points, as noted above, would also enhance robustness and exploration consistency. Combining an exploration-oriented ACF with the LES ACF could further expand the applicability beyond strictly local optimization tasks.\nA brief note on structure: Section 4 contains only one subsection (4.1) and no 4.2, which seems redundant. Figure 4 appears in isolation and is discussed almost two pages later, perhaps due to layout constraints, but this should be improved. Early in the paper, when introducing the concept of gradient-based BO and entropy-based ACF, Figure 1 does not effectively illustrate the overall concept. A clearer overview diagram would help, ideally explaining the gradient-chain mechanism directly instead of using dense phrasing such as “The algorithm propagates the posterior belief over the objective through the optimizer, yielding a probability distribution over descent sequences.”", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This work demonstrates several notable strengths across originality, quality, clarity, and significance. First, it introduces a comprehensive and well-structured benchmarking framework, making the experimental evaluation both reproducible and conceptually clear. The presentation is straightforward, allowing readers to easily grasp the main ideas without being overwhelmed by technical complexity. Second, the paper’s core contribution, an efficient entropy-based search strategy for finding optimal values within GP models, is conceptually sound and addresses a gap in current Bayesian optimization approaches, where inner GP models' search efficiency has been underexplored. Third, the authors’ methodological choices, including their assumptions and theoretical lemmas, are particularly aligned with the challenges of local optimization under uncertainty, especially the computational cost problem. Finally, the synthetic benchmark results are consistently strong, showing that the proposed Local Entropy Search (LES) method outperforms existing baselines across multiple complexity levels, which is both empirically impressive and practically significant.", "weaknesses": "While the paper is well written and experimentally solid, several aspects could be strengthened to better support its claims. First, the motivation for emphasizing local search over global exploration is not clearly justified. The paper references use cases in neural network optimization and other machine learning settings, which differ substantially from the BO context. Although improving local search efficiency is meaningful, the trade-off between local exploitation and global convergence remains underexplored. As a result, the proposed method effectively bridges an inner-GP optimization gap but simultaneously introduces ambiguity regarding its global behavior.\n\nSecond, the experimental evaluation is limited primarily to synthetic benchmarks. While these results are strong, the real-world tasks show marginal improvement, and the performance quickly degrades when computational budgets are constrained. They did compare with the current state-of-the-art high-dimensional BO methods, but the benchmarks are set for low-dimensional problems. Besides, their synthetic benchmark is GP-based, which raises a question of the harmony between the target model and the optimizer GP model. Third, although the authors provide lemmas ensuring that the acquisition function (ACF) can cover the entire input space, they omit theoretical analysis on regret bounds and convergence guarantees. Aligned with the first problem, the convergence condition is properly needed in this case, despite the logical assumption that reaching local extrema will have a stable gradient path. Finally, while computational efficiency is discussed, the ACF evaluation may become a bottleneck in high-dimensional settings, as it dominates runtime when the dimension increases. Since improving acquisition-function efficiency is an active research direction, this approach may be less competitive in high-dimensional or highly multi-modal problems. Consequently, LES performs strongly in low-dimensional spaces with relatively few local optima but may struggle to maintain its advantages as dimensionality grows. This shows a narrow possible implementation range for LES, where it matches the ideal condition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)