Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants

Fares Fourati; Mohamed-Slim Alouini; Salma Kharrat; Vaneet Aggarwal

REVIEW 4 major objections 6 minor 23 references

Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants

T0 review · 4 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A black-box optimizer claims minimax-optimal regret without ever estimating the Lipschitz constant.

desk verdict ECP is a useful parameter-free Lipschitz optimizer with a legitimate new twist, but the paper's central finite-budget regret proof has a fixable gap and an off-by-one that need attention. read the letter →

arxiv 2502.04290 v1 pith:MAJA5TQW submitted 2025-02-06 cs.LG cs.AIcs.SYeess.SYmath.OCstat.ML

Fares Fourati , Salma Kharrat , Vaneet Aggarwal , Mohamed-Slim Alouini This is my paper · ORCID

classification cs.LGcs.AIcs.SYeess.SYmath.OCstat.ML MSC 90C2690C56

keywords globaloptimizationLipschitzcontinuousfunctionsunknownconstantblack-boxno-regretminimaxregretacceptanceregionexpensivefunctionevaluations

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes ECP, a global optimization algorithm for black-box functions that are Lipschitz continuous with an unknown Lipschitz constant. The central claim is that by screening every sampled point through a growing acceptance region, ECP spends function evaluations only on potential maximizers, never on uniform sampling to estimate $k$, and yet achieves no-regret behavior and minimax-optimal finite-budget regret. This matters for expensive evaluations: users need no estimate of $k$, no separate exploration calls, and no hand-tuned local smoothness, and the same method works across many non-convex benchmarks. If the theory holds, ECP closes the gap between methods that need $k$ and adaptive methods that waste calls estimating it.

What carries the argument

The central object is the acceptance region $A_{\varepsilon_t,t}=\{x\in\mathcal{X}: \min_{i\le t}(f(x_i)+\varepsilon_t\|x-x_i\|_2)\ge \max_{j\le t} f(x_j)\}$. It is the set of points consistent with at least one $k$-Lipschitz function matching the observed evaluations once $\varepsilon_t=k$, so it tracks the paper's notion of potential maximizers. The mechanism is the monotone interplay: the region expands as $\varepsilon_t$ grows and shrinks as $t$ grows; ECP deliberately grows $\varepsilon_t$ faster than rejection rates explode, guaranteeing eventual acceptance with polynomial complexity. The hitting time $i^\star$ is when $\varepsilon_t\ge k$, after which the region provably contains every level set above the current best.

What would settle it

Fix a simple $1$-$\mathrm{D}$ Lipschitz function with a known $k$, e.g. $f(x)=k x$ on $[0,1]$, and run ECP with known $\varepsilon_1$ and $\tau$ so that $i^\star=\lceil \log_\tau(k/\varepsilon_1)\rceil$. Record whether, for every threshold $y\ge \max_{i<i^\star} f(x_i)$, the maximum value of accepted points from rounds $i^\star$ through $n$ stochastically dominates $n-i^\star+1$ independent uniform samples. A single $y$-level or seed where $P(\max_{i=i^\star,\dots,n} f(x_i)\ge y) < P(\max \text{uniform}\ge y)$ would disprove Proposition 6 and with it the current proof of Theorem 3.

Watch

Extended reading notes

Core claim

The paper's discovery is that a purely threshold-driven acceptance rule can carry the full weight of Lipschitz optimization. At round $t$, ECP accepts a uniformly sampled point $x$ only if $\min_i (f(x_i)+\varepsilon_t\|x-x_i\|_2) \ge \max_j f(x_j)$; the tolerance $\varepsilon_t$ grows geometrically with $\tau_{n,d}>1$ and also whenever rejections pile up. Because $\varepsilon_t$ eventually reaches the unknown constant $k$, the acceptance region catches every potential maximizer, and Proposition 6 asserts that after that hitting time $i^\star$ ECP's evaluations stochastically dominate independent uniform samples. Consequently Theorem 3 gives $R_{\mathrm{ECP},f}(n) \le \mathrm{diam}(\mathcal{X})\, (i^\star)^{1/d}\, k\, (\ln(1/\delta)/n)^{1/d}$ with probability at least $1-\delta$, matching the minimax lower bound $\Omega(k n^{-1/d})$ recalled in Proposition 1.

Load-bearing premise

The entire finite-budget guarantee rests on the assertion that once $\varepsilon_t$ reaches the unknown Lipschitz constant $k$, every point at least as good as the current best passes ECP's acceptance test, so the later evaluations are at least as good as uniform random samples; if that containment fails at the claimed round, the regret bound is not proven.

Editorial extensions

If this is right

For a fixed budget $n$, ECP's regret is $O(k n^{-1/d})$ with no separate term for estimating $k$, so every evaluation counts toward the objective rather than toward exploration.
ECP is no-regret over all $k$-Lipschitz functions for any choices of $\varepsilon_1>0$, $\tau_{n,d}>1$, and $C>1$, because $\varepsilon_t$ deterministically crosses $k$.
When $\varepsilon_1\ge k$ and $\tau_{n,d}=1$, ECP reduces to the known-constant method LIPO, giving the same regret bound; thus ECP is a strict generalization.
Computational complexity is polynomial in $n$ with high probability, and the growth condition prevents the infinite rejection loops that can stall AdaLIPO and AdaLIPO+.
In the empirical comparison on 30 problems at budget 50, ECP ranks first most often among the 11 methods, and it keeps a strong edge at smaller and larger budgets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof of Proposition 6 depends on the level-set containment $\{x: f(x)\ge y\}\subseteq A_{\varepsilon_t,t}$ holding exactly at $i^\star$; if the off-by-one in Lemma 2 is a genuine gap, the bound likely survives with $i^\star+1$, so the minimax rate is probably intact even if the stated constant is not.
The same acceptance-rule idea extends to local smoothness via a semi-metric $\ell(x^\star,x)$, as the paper's Remark 1 sketches, and could be tested on structured or discrete search spaces where the uniform-volume rejection bound changes.
Because ECP's advantage concentrates at small budgets, a natural hybrid is to run ECP early and hand off to a surrogate-based or evolutionary method once enough evaluations accumulate; the paper's own large-budget tables hint this could be beneficial.
The ablations suggest performance improves with smaller $\varepsilon_1$, smaller $\tau$, and larger $C$ at higher computational cost; an adaptive schedule that sets these from the observed rejection rate, without knowing $k$, is a direct testable extension.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, quick take on arXiv:2502.04290. ECP is a genuinely useful twist on LIPO: instead of estimating the Lipschitz constant, it grows an acceptance-region parameter and uses rejections to trigger growth. That removes the space-filling exploration AdaLIPO needs, and the finite-budget regret bound is the right target. The empirical work is solid and extensive – 30 problems, multiple budgets, ablations, public code. I believe the algorithm works.

But the proof of Theorem 3 is not complete as written. The stochastic-dominance step in Proposition 6 (Appendix C.12) has an unhandled case at the base: the threshold y only dominates the first i*-1 evaluations, while the point x_{i*} is not controlled. If f(x_{i*}) ≥ y, the event is already achieved, but the containment X_y ⊆ X_{k,i*} can fail, so the displayed equality/lower bound isn't justified. A case split on whether the running max already exceeded y repairs this; the induction step is fine because it conditions on the running max being below y. Also, Lemma 2's bound is off by one: ε_t ≥ ε_1 τ^{t-1} gives hitting time at most ceil(log_τ(k/ε_1))+1, not ceil(···). Moreover, the paper's indexing conflates ε_t used at iteration t with the evaluation index; x_{t+1} is evaluated under ε_t, so the hitting time for evaluations is shifted. These are all fixable, but a referee needs to see a corrected proof.

The abstract's claim of outperforming 10 methods across 30 problems is stronger than Table 1 supports: ECP has the most top-1 placements, but Bayesian methods (Botorch, SMAC3, A-GP-UCB) win on several problems and dominate some. The median ranking story is fair; 'outperforms' is too absolute.

Bottom line: this is a meaningful incremental advance for Lipschitz optimization and deserves peer review, but as a conditional accept requiring the proof gap to be closed and the empirical claims softened. If you work on expensive black-box optimization, it's worth reading.

Referee Report

4 major / 6 minor

Summary. The paper introduces ECP, an adaptive sampling algorithm for global maximization of Lipschitz black-box functions when the Lipschitz constant is unknown. In each round ECP samples uniformly from the search space but evaluates a point only if it lies in an acceptance region A_{ε_t,t}, where ε_t grows both deterministically after evaluations and stochastically when rejections accumulate. The paper claims that ECP is no-regret in the infinite-budget setting, achieves the minimax-optimal finite-budget regret rate O(k n^{-1/d}) without knowing k, has polynomial computational complexity, and outperforms 10 benchmarks on 30 synthetic and real-world problems.

Significance. If the theoretical claims were fully established, this would be a strong contribution to Lipschitz global optimization. The algorithm is simple, publicly implemented, and avoids the space-filling exploration used by AdaLIPO to estimate the Lipschitz constant. The claimed finite-budget regret bound matches the minimax lower bound, and the empirical study is broad, with ablations over the three hyperparameters. However, the proof of the key stochastic-dominance lemma is incomplete, the hitting-time lemma contains an off-by-one error, and the empirical claim of universal superiority is overstated. The significance of the paper is therefore conditional on the repair of these load-bearing points.

major comments (4)

[Appendix C.12 (Proposition 6)] The proof of stochastic dominance does not justify the containment X_y ⊆ X_{k,i⋆} used in the base case. At time i⋆, the set X_{k,i⋆} is defined with max_{j≤i⋆} f(x_j), which includes the newly evaluated point x_{i⋆}. For z ∈ X_y, Lipschitzness only gives f(x_i) + k∥z−x_i∥ ≥ f(z) ≥ y; if f(x_{i⋆}) ≥ y, this does not imply z ∈ X_{k,i⋆}, and the displayed lower bound E[µ(X_{k,i⋆}∩X_y)/µ(X)] is not justified. The same gap appears at the induction step, where X_y ⊆ X_{k,n} is used conditionally on max_{i=i⋆,...,n} f(x_i) < y without controlling the value at the next evaluated point. A case split on whether the running maximum has already exceeded y can likely repair the argument, but as written Proposition 6 is unproven, and Theorem 3, which relies on Proposition 6, is therefore not established.
[Appendix C.10 (Lemma 2)] The stated upper bound i⋆ ≤ ceil(log_τ(k/ε1)) is off by one when log_τ(k/ε1) is an integer. Since ε_t ≥ ε1 τ^{t−1}, if k/ε1 = τ^m with integer m, then ε_{m+1} ≥ k while ε_m < k, so i⋆ ≥ m+1 = ceil(log_τ(k/ε1))+1. For example, ε1=1, τ=2, k=4 gives i⋆=3, while the lemma as stated gives i⋆≤2. The correct minimal bound is ceil(log_τ(k/ε1)) when the logarithm is non-integral and ceil(log_τ(k/ε1))+1 when it is integral. This timing is exactly what Proposition 6's base case needs, so the lemma must be corrected and its consequences for Proposition 6 and Theorem 3 re-derived.
[Appendix C.11 (Theorem 2)] The proof of the no-regret claim is not a proof. It argues that once ε_t > k, Proposition 2 gives P_{k,t} ⊆ A_{ε_t,t}, and then concludes that 'the search space uniformly recovers all the potential maximizers and beyond.' This does not establish that max_{i≤n} f(x_i) converges in probability to max_X f, because no quantitative statement is made about the probability that accepted points fall near a maximizer as n grows. The no-regret conclusion is a central advertised contribution and needs a rigorous argument, for instance by invoking the stochastic dominance in Proposition 6 or by giving a direct covering argument for the acceptance region.
[Section 6, Table 1, and Abstract] The claim that ECP 'outperforms 10 benchmark algorithms' across 30 problems is stronger than the reported data. In Table 1 with n=50, ECP is Top-1 on 13 of 30 problems, and it is not the best on several named problems (e.g., autoMPG, concrete, housing, yacht, Bukin, Easom, Langermann). The violin plot supports a good median ranking, but it does not support universal dominance. The abstract, introduction, and Section 7 should be reworded to say that ECP is competitive and often best, with a precise definition of the aggregate comparison, and ideally with statistical significance tests.

minor comments (6)

[Throughout] There are numerous typos and grammatical slips, including 'intersting', 'unkown', 'Morever', 'potentailly', 'arbitraly', and running headers such as 'F unctions'; these should be corrected in a revision.
[Appendix E.4] The ablation text says 'keeping τ = 10^{-3}', but τ must be > 1 in the algorithm; the text and captions should consistently state a valid value such as τ = 1.001.
[Appendix C.6 (Proposition 7)] The notation for the exploration event is inconsistent: the text first says E=1 denotes an exploitation phase, then says 'during exploration (E=1) a point is never rejected'; the conditional probability statement P(R | E=0) is also unclear. Please define the event and its complement coherently.
[Appendix A, Tables 2 and 4] Tables 2 and 4 omit several baselines that appear in Table 1 (Botorch, SMAC3, A-GP-UCB), so the comparisons at n=25, n=100, and n=300 are not against the same set of methods; the captions should state this explicitly or the tables should be completed.
[Algorithm 1] The use of h_{t+1} both as a counter of rejections at round t and as an index in the pseudocode is confusing; renaming the counter to something like r_t would make the growth condition and the reset rule easier to follow.
[Appendix C.13 (Theorem 3)] The proof applies Lemma 4 with the stated constant diam(X), but the standard uniform-sampling regret bound for Lipschitz functions contains an additional constant depending on the covering number of X; if Lemma 4 is quoted from Malherbe and Vayatis (2017), the exact constant should be checked and stated explicitly.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: ECP's no-regret and finite-budget regret claims derive from external PRS/LIPO bounds plus the acceptance-region inclusion; the few self-citations are not load-bearing.

full rationale

The central derivation chain is not circular. The acceptance region in Definition 2 is defined independently of any estimate of k; Proposition 2 uses the external identity P_{k,t} = A_{k,t} (Lemma 3, Malherbe and Vayatis 2017) to obtain the inclusions A_{εt,t} ⊆ P_{k,t} for εt ≤ k and P_{k,t} ⊆ A_{εt,t} for εt > k. Lemma 2 bounds the hitting time i* from the deterministic geometric growth εt ≥ ε1·τ^{t-1}, which is an analysis step, not a fitted input. Theorem 2 (no-regret) follows from eventual coverage of P_{k,t}; Proposition 6 compares the ECP tail with i.i.d. uniform sampling using the level-set containment X_y ⊆ X_{k,i*}; Theorem 3 then converts that stochastic dominance into a regret bound by applying the external PRS finite-budget bound of Lemma 4 and matches the external lower bound of Bull (2011). No parameter is fitted to the data or to the target regret, and the bound's dependence on the unknown k appears only in the analysis, not in the algorithm's operation. The self-citations (Fourati et al. 2023/2024; Kharrat et al. 2024) occur in related-work and motivation passages and do not support the acceptance-region or regret theorems. There is a genuine proof gap in Proposition 6: the induction does not handle the case where f(x_{i*}) already exceeds y, so X_y need not be contained in X_{k,i*}, and Lemma 2's ceiling may be off by one for non-integral logarithms. These are correctness risks, not circular reductions, because the missing argument would still be independent of the conclusion being proved.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claims rest on the Lipschitz domain assumption and on two standard results from prior work (LIPO's potential-maximizer characterization and the PRS regret bound). The three hyperparameters epsilon_1, tau, C are free choices, but the theory holds for any allowed values, so they do not create a fitted-parameter circularity.

free parameters (3)

epsilon_1 = 1e-2
Initial acceptance-region slope. Theory holds for any epsilon_1>0; the paper fixes 1e-2 across all benchmarks based on ablations.
tau = 1.001 (with tau_{n,d} = max(1+1/(nd), tau))
Geometric growth multiplier for epsilon_t. Fixed by hand; ablations show robustness.
C = 1000
Rejection-growth threshold. Larger C leads to fewer stochastic grows; fixed at 1000 as a middle value.

assumptions (4)

domain assumption f is Lipschitz continuous with a finite but unknown constant k
The acceptance region and all regret bounds are defined for f in Lip(k); invoked in Section 3 and everywhere.
domain assumption X is compact and convex with non-empty interior
Needed for uniform sampling, volume measures, and the lower bound; stated in Section 3.
standard math Lemma 3 and Lemma 4 from Malherbe and Vayatis (2017) are taken as given
Lemma 3 equates potential maximizers to the LIPO acceptance region; Lemma 4 gives the PRS regret bound. Cited in Appendix C.1 and used in Proposition 2 and Theorem 3.
standard math Bull's lower bound (Proposition 1) on minimax regret
Used to claim minimax optimality; cited without proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants." pith.science (2026). https://pith.science/paper/MAJA5TQW

@misc{pith2026250204290,
  author       = {Pith},
  title        = {Pith review of: Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MAJA5TQW}},
  note         = {Machine review of arXiv:2502.04290}
}

read the original abstract

Optimizing expensive, non-convex, black-box Lipschitz continuous functions presents significant challenges, particularly when the Lipschitz constant of the underlying function is unknown. Such problems often demand numerous function evaluations to approximate the global optimum, which can be prohibitive in terms of time, energy, or resources. In this work, we introduce Every Call is Precious (ECP), a novel global optimization algorithm that minimizes unpromising evaluations by strategically focusing on potentially optimal regions. Unlike previous approaches, ECP eliminates the need to estimate the Lipschitz constant, thereby avoiding additional function evaluations. ECP guarantees no-regret performance for infinite evaluation budgets and achieves minimax-optimal regret bounds within finite budgets. Extensive ablation studies validate the algorithm's robustness, while empirical evaluations show that ECP outperforms 10 benchmark algorithms including Lipschitz, Bayesian, bandits, and evolutionary methods across 30 multi-dimensional non-convex synthetic and real-world optimization problems, which positions ECP as a competitive approach for global optimization.

Figures

Figures reproduced from arXiv: 2502.04290 by the authors.

**Figure 2.** An illustration of the acceptance region (orange), which is determined based on the 8 evaluated points on a non-convex, single-dimensional objective function (black). The ε8 controls the slopes of the blue functions, directly impacting the acceptance region. While the former type of growth is stochastic and depends on the threshold C > 1, the latter is deterministic and occurs regardless of the input parameters… view at source ↗

**Figure 3.** Violin plots showing the ranking distributions of diverse optimization algorithms, ordered by increasing median ranking, across 30 non-convex, multi-dimensional synthetic and real-world problems. The results are based on a budget of n = 50 for the different algorithms, with maxima averaged over 100 repetitions. shows that for sufficiently large t, the event of reaching k is inevitable, with proof provided in Appendi… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Figures of the various considered non-convex 2-dimensional objective functions. D Details of the Experiments The implementations of ECP and the considered objectives are publicly available at https://github.com/fouratifares/ECP. D.1 Optimization Algorithms For DIRECT a…

**Figure 5.** Figure 5: Ablation Study on the Constant ε1 > 0 of ECP with fixed C = 103 and τ = 10−3 on various real-world and synthetic non-convex multi-dimensional optimization problems [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]

**Figure 6.** Figure 6: Ablation Study on the Constant τ > 1 of ECP with fixed C = 103 and ε1 = 10−2 on various real-world and synthetic non-convex multi-dimensional optimization problems [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]

**Figure 7.** Figure 7: Ablation Study on the constant C > 1 of ECP with fixed τ = 10−3 and ε1 = 10−2 on various real-world and synthetic non-convex multi-dimensional optimization problems [PITH_FULL_IMAGE:figures/full_fig_p027_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 19 canonical work pages

[1]

The first column indicates whether the optimization method was proposed for Lipschitz functions

and c = k · diam(X ), where k is the unknown Lipschitz constant. The first column indicates whether the optimization method was proposed for Lipschitz functions. The second column specifies whether the method requires prior knowledge. The third column indicates whether or not the method is stochastic adaptive, stochastically leveraging the collected data ...

work page 2002
[2]

The result is extended to the case where n ≤ i⋆ by noticing that the bound is superior to k · diam(X ) in that case, and thus trivial. □ Every Call is Precious: Global Optimization of Black-Box F unctions with Unknown Lipschitz Constants (a) Ackley (b) Bukin (c) Camel (d) Crossintray (e) Damavandi (f) Dropwave (g) Easom (h) Eggholder (i) Griewank (j) Himm...

work page 2020
[3]

nan indicates an error related insufficient budget to return a value

For AdaLIPO, we set p = 0 .1, as specified in their paper. nan indicates an error related insufficient budget to return a value. B Extended Related Works Several methods have been proposed for global optimization (T¨ orn andˇZilinskas, 1989; Pardalos, 2013; Floudas and Pardalos, 2014; Zabinsky, 2013; Stork et al., 2022). The most straightforward ones are ...

work page 2008
[4]

Let X ⊂Rd be a compact and convex set with non-empty interior and let f ∈ Lip(k) be a k-Lipschitz functions defined on X for some k ≥

(Malherbe and Vayatis (2017)). Let X ⊂Rd be a compact and convex set with non-empty interior and let f ∈ Lip(k) be a k-Lipschitz functions defined on X for some k ≥

work page 2017
[5]

To ensure fairness, we run AdaLIPO+ without stopping, thereby maintaining the same budget across all methods

For AdaLIPO and AdaLIPO+, we use the implementation provided by (Serr´ e et al., 2024). To ensure fairness, we run AdaLIPO+ without stopping, thereby maintaining the same budget across all methods. Furthermore, since AdaLIPO requires an exploration probability p, we fix it at 0 .1, as done by the authors (Malherbe and Vayatis, 2017). F ares F ourati, Salm...

work page 2024
[7]

LIPO+: Frugal Global Optimization for Lipschitz Functions

Ga¨ etan Serr´ e, Perceval Beja-Battais, Sophia Chirrane, Argyris Kalogeratos, and Nicolas Vayatis. Lipo+: Frugal global optimization for lipschitz functions. arXiv preprint arXiv:2406.19723 ,

work page Pith review arXiv
[8]

Bruno O Shubert

doi: 10.1109/JPROC.2015.2494218. Bruno O Shubert. A sequential method seeking the global maximum of a function. SIAM Journal on Numerical Analysis, 9(3):379–388,

work page arXiv 2015
[10]

Finite-time anal- ysis of kernelised contextual bandits

Michal Valko, Nathaniel Korda, R´ emi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time anal- ysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869,

arXiv

Show all 23 references

[12]

However, in this work we focus on Lipschitz continious functions, with unkonw Lipschitz constants

and SequOOL (Bartlett et al., 2019). However, in this work we focus on Lipschitz continious functions, with unkonw Lipschitz constants. The introduction of the Lipschitz constant, first proposed in the pioneering works of Shubert (1972) and Piyavskii (1972), sparked significan...

1972
[13]

Infinite Loop indicates that the method failed to return a valid value within the budget

For AdaLIPO, we set p = 0 .1, as specified in their paper. Infinite Loop indicates that the method failed to return a valid value within the budget. recently, AdaLIPO/AdaLIPO+ (Malherbe and Vayatis, 2017; Serr´ e et al., 2024). The DIRECT algorithm (Jones et al.,

2017
[15]

More recently, Lindauer et al

have been proposed. More recently, Lindauer et al. (2022) introduced SMAC3 as a robust and efficient baseline for global optimization. In our empirical evaluation, we demonstrate that ECP outperforms these recent BO baselines. Evolutionary algorithms, such as CMA-ES (Hansen an...

2022
[18]

(Malherbe and Vayatis (2017)) If Pk,t denotes the set of potential maximizers of the function f , as defined in Definition 3, then we have Ak,t = Pk,t. Lemma

2017
[20]

(2022), with the default hyperparameters

For SMAC3, we utilize the implementation provided by Lindauer et al. (2022), with the default hyperparameters. For the A-GP-UCB (Berkenkamp et al., 2019), the kernel used is “Matern”. The tolerance is set to 1 × 10−2, and the exploration-exploitation tradeoff is controlled by ...

2022
[23]

In the following, we test the performance of ECP, with various values of τ , with fixed C = 103 and ε1 = 10−2

E.3 Ablation Study on the Coefficient τ Recall that τn,d = max 1 + 1 nd , τ , therefore the choice of τ only impacts the algorithm, when the value of τ is larger than 1 + 1 nd . In the following, we test the performance of ECP, with various values of τ , with fixed C = 103 and...

2000
[24]

F ares F ourati, Salma Kharrat, V aneet Aggarwal, Mohamed-Slim Alouini 0 10 20 30 40 50 Evaluations 12 10 8 6 4 2 Maximum Value ECP(epsilon=1.0001) ECP(epsilon=1.001) ECP(epsilon=1.01) ECP(epsilon=1.1) ECP(epsilon=1.5) (a) Ackley 0 10 20 30 40 50 Evaluations 180 160 140 120 10...

2000
[1972]

Ban- dits attack function optimization

Philippe Preux, R´ emi Munos, and Michal Valko. Ban- dits attack function optimization. In 2014 IEEE congress on evolutionary computation (CEC), pages 2245–2252. IEEE,

2014
[1993]

is a Lipschitz optimization algorithm where the Lipschitz constant is unknown. It uses a deterministic splitting technique of the search space in order to sequentially divide and evaluate the function over a subdivision of the space that have recorded the highest upper bound a...

2014
[2010]

A tutorial on bayesian optimization

Peter I Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811 ,

arXiv
[2014]

Bayesian Optimization: Open source constrained global optimization tool for Python, 2014–

Every Call is Precious: Global Optimization of Black-Box F unctions with Unknown Lipschitz Constants Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014–. URL https://github.com/ bayesian-optimization/BayesianOptimization...

2014
[2016]

Acing: Actor-critic for instruction learning in black-box large language models

Salma Kharrat, Fares Fourati, and Marco Canini. Acing: Actor-critic for instruction learning in black-box large language models. arXiv preprint arXiv:2411.12736,

arXiv
[2019]

Waltraud Huyer and Arnold Neumaier

URL https://doi.org/10.5281/zenodo.2559634. Waltraud Huyer and Arnold Neumaier. Global opti- mization by multilevel coordinate search. Journal of Global Optimization, 14:331–355,

doi
[2020]

✕ ✓ ✓ ✓ ✕ ✕ − BayesOpt (Nogueira, 2014–) ✕ ✓ ✓ ✓ ✕ ✕ − DIRECT (Jones et al.,

2014
[2022]

Surjanovic and D

S. Surjanovic and D. Bingham. Virtual library of sim- ulation experiments: Test functions and datasets. Retrieved October 10, 2024, from http://www.sfu. ca/~ssurjano,

2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

The first column indicates whether the optimization method was proposed for Lipschitz functions

and c = k · diam(X ), where k is the unknown Lipschitz constant. The first column indicates whether the optimization method was proposed for Lipschitz functions. The second column specifies whether the method requires prior knowledge. The third column indicates whether or not the method is stochastic adaptive, stochastically leveraging the collected data ...

work page 2002

[2] [2]

The result is extended to the case where n ≤ i⋆ by noticing that the bound is superior to k · diam(X ) in that case, and thus trivial. □ Every Call is Precious: Global Optimization of Black-Box F unctions with Unknown Lipschitz Constants (a) Ackley (b) Bukin (c) Camel (d) Crossintray (e) Damavandi (f) Dropwave (g) Easom (h) Eggholder (i) Griewank (j) Himm...

work page 2020

[3] [3]

nan indicates an error related insufficient budget to return a value

For AdaLIPO, we set p = 0 .1, as specified in their paper. nan indicates an error related insufficient budget to return a value. B Extended Related Works Several methods have been proposed for global optimization (T¨ orn andˇZilinskas, 1989; Pardalos, 2013; Floudas and Pardalos, 2014; Zabinsky, 2013; Stork et al., 2022). The most straightforward ones are ...

work page 2008

[4] [4]

Let X ⊂Rd be a compact and convex set with non-empty interior and let f ∈ Lip(k) be a k-Lipschitz functions defined on X for some k ≥

(Malherbe and Vayatis (2017)). Let X ⊂Rd be a compact and convex set with non-empty interior and let f ∈ Lip(k) be a k-Lipschitz functions defined on X for some k ≥

work page 2017

[5] [5]

To ensure fairness, we run AdaLIPO+ without stopping, thereby maintaining the same budget across all methods

For AdaLIPO and AdaLIPO+, we use the implementation provided by (Serr´ e et al., 2024). To ensure fairness, we run AdaLIPO+ without stopping, thereby maintaining the same budget across all methods. Furthermore, since AdaLIPO requires an exploration probability p, we fix it at 0 .1, as done by the authors (Malherbe and Vayatis, 2017). F ares F ourati, Salm...

work page 2024

[6] [7]

LIPO+: Frugal Global Optimization for Lipschitz Functions

Ga¨ etan Serr´ e, Perceval Beja-Battais, Sophia Chirrane, Argyris Kalogeratos, and Nicolas Vayatis. Lipo+: Frugal global optimization for lipschitz functions. arXiv preprint arXiv:2406.19723 ,

work page Pith review arXiv

[7] [8]

Bruno O Shubert

doi: 10.1109/JPROC.2015.2494218. Bruno O Shubert. A sequential method seeking the global maximum of a function. SIAM Journal on Numerical Analysis, 9(3):379–388,

work page arXiv 2015

[8] [10]

Finite-time anal- ysis of kernelised contextual bandits

Michal Valko, Nathaniel Korda, R´ emi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time anal- ysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869,

arXiv