Perceval Beja-Battais

Gaëtan Serré
email: gaetan.serre@ens-paris-saclay.frsophia.chirrane@student-cs.fr

Sophia Chirrane

Experimental Improvements of Global Optimization Algorithms for Lipschitz Functions

Keywords: global optimization, Lipschitz applications, statistical analysis, convergence rate bounds, numerical analysis

In this paper, we define an experimental context in which we tested the performances of LIPO and AdaLIPO, two global optimization algorithms for Lipschitz functions, introduced in [10]. We provide experimental proofs of the efficiency of those algorithms, led numerical statistical analysis of our results, and suggested two intuitive improvements from the vanilla version of the algorithms, referred as LIPO-E and AdaLIPO-E. Within our test bench, these improvements allow the algorithms to converge significantly faster and whenever they struggle to find a better maximizer. Finally, we defined the scope of application of LIPO and AdaLIPO. We show that they are very prone to the curse of dimensionality and tend quickly to Pure Random Search when the dimension increases. We provide source code for LIPO, AdaLIPO, and our enhanced versions here 1 .

General context

Global optimization refers to any method whose aim is to find the global maxima of a function over a set. This branch of applied mathematics is largely studied since numerous real life problems require it. One of the major fields where global optimization is widely used is shape optimization (Figure 1). Taking the example of optimizing the shape of an aircraft wing or a car, we can define an objective function by weighting several properties we desire (robustness, weight, wind penetration, etc.). The so defined objective function is highly complex and often requires to launch a whole simulation to be evaluated. Figure 1: Global optimization for shape optimization: some finite element methods use global optimization algorithms to compute the updates [START_REF] Girardi | A finite element model updating method based on global optimization[END_REF].

Another major real life application of global optimization is hyperparameter tuning (Figure 2). Often done using cross validation in machine learning, this task requires the evaluation of very complex functions living in big dimensional space (according to the chosen models), making the hyperparameter selection very difficult. Global optimization methods can provide more clever ways to explore the space of hyperparameter than Grid Search or Pure Random Search. Global optimization has countless other applications such as protein structure prediction, TSP, and object packing. These are challenging real-life applications that would benefit from a quick resolution. Most of the time, we aim to optimize an unknown function, living in a continuous space. We cannot assume strong properties like differentiability or convexity, which considerably reduces the number of usable algorithms. Furthermore, the evaluation of the studied function is often expensive: the less the optimizing method evaluates the function, the better.

The LIPO method and its adaptative variant AdaLIPO [START_REF] Malherbe | Global optimization of lipschitz functions[END_REF] aims at addressing all these raised issues. This global optimization method address the problem of optimizing a function f : X → R, with X ⊂ R d a compact and convex set with non-empty interior such that f is k-Lipschitz, i.e.

∃k ≥ 0, |f (x) -f (x ′ )| ≤ k∥x -x ′ ∥ 2 ∀(x, x ′ ) ∈ X 2 .
The Lipschitz assumption controls how fast variations of a function can change. This regularity constraint is enforced by the Lipschitz constant k. The bigger k is, the less regular the function. As k can be potentially huge this assumption offers a not too restrictive scope of application and thus can be posed in many real world problems.

In this paper we aim at providing a complete experimental analysis of LIPO and AdaLIPO. First, in Section 3 we proposed a reference implementation of these algorithms, fully reproducible and explained. Then, in Section 4 we designed experiments to evaluate the theoretical properties of the method introduced in the paper and compared LIPO with AdaLIPO and other methods. We, then, propose some improvements of both LIPO and AdaLIPO based on empirical observations in Section 5. Finally, in Section 6, we defined the application scope of LIPO.

Notations. We define some notations that we will use through this entire article. Most are taken directly from [START_REF] Malherbe | Global optimization of lipschitz functions[END_REF]. Let X ⊂ R d a compact and convex set with nonempty interior. Let

x * ∈ arg max x∈X f (x) for f : X → R. Let B(x, r) = {x ′ ∈ R d : ∥x ′ -x∥ 2 ≤
r} the ball centered in x of radius r ≥ 0. For any bounded set X ⊂ R d , let rad(x) = sup{r > 0 : ∃x s.t. B(x, r) ⊂ X} its radius and diam(x) = sup x,x ′ ∈X ∥x-x ′ ∥ 2 its diameter. We also define µ(X ) its volume where µ(•) stands for the standard Lebesgue measure or the counting measure if X is countable. Finally, let

Lip(k) = f : X → R s.t. ∀x, x ′ ∈ X 2 , |f (x) -f (x ′ )| ≤ k∥x -x ′ ∥ 2
the set of k-Lipschitz functions defined on X .

Related work

As stated in the introduction, global optimization is a very interesting field for solving industrial problems, so one can find a lot of papers describing variants and merges of algorithms or applications on new problems. One of the most known global optimization algorithm is Simulated Annealing [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. It is based on the Metropolis-Hastings algorithm ( [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF] and [START_REF] Hastings | Monte carlo sampling methods using markov chains and their applications[END_REF]) as it samples random configurations and accepts it in a explorationexploitation perspective. More generally, one can distinguish deterministic methods from stochastic ones. Deterministic methods provide theoretical guarantee that the returned solution is the real global maximum. Cutting-plane methods [START_REF] Gilmore | A linear programming approach to the cutting-stock problem[END_REF] and branch and bounds methods [START_REF] Land | An automatic method of solving discrete programming problems[END_REF] are two extremely popular deterministic algorithms for solving discrete NP-hard problems. One can also cite [START_REF] Arnon | Cylindrical algebraic decomposition i: The basic algorithm[END_REF], the state of the art algorithm based on real algebraic geometry, also discrete. On the other hand, stochastic methods are based on Monte-Carlo and can return inexact results. LIPO and AdaLIPO are stochastic methods, as Bayesian optimization methods [START_REF] Martinez-Cantin | Bayesopt: A bayesian optimization library for nonlinear optimization, experimental design and bandits[END_REF], that construct a gaussian process that best describes the function to be optimized and samples the next evaluation point given this posterior distribution. As LIPO and AdaLIPO, Bayesian optimization methods are advantageous when the function is difficult to evaluate. Another interesting stochastic algorithm is CMA-ES [START_REF] Hansen | The CMA evolution strategy: A comparing review[END_REF], it samples next evaluation points using a multivariate gaussian distribution with mean and covariance maximizing the likelihood of previous candidate solutions and search steps. Finally, in 2018 [START_REF] Luo | Minima distribution for global optimization[END_REF] established a relationship between any continuous function f on a compact set Ω ⊂ R d and its global minima f * :

Ω f (x)m (k) (x)µ(dx) ---→ k→∞ f * , where m (k) (x) = e -kf (x)
Ω e -kf (y) µ(dy)

.

Note that:

Ω m (k) (x)µ(dx) = 1 and lim k→∞ m (k) (x) = 1 µ(X * ) if x ∈ X * 0 if x ∈ Ω/X *
where X * ⊆ Ω is the set of minimizers. Thus, m (k) is a probability density function, that one can think of as a kind of generalized softmax for infinite dimension, that pointwise converges to a uniform distribution on X * .

Methods

In this section we provide a reference implementation of LIPO and AdaLIPO. First, we decided to use oriented object programming to define the objective function. We thus defined a class Function which has two attributes and one method:

• bounds: The bounds of the definition space of the function for each dimension (attribute)

• k: The Lipschitz constant of the function (attribute)

• call: The closed form of the objective function (method)

The two presented algorithms' pseudo code are available in Section A.

LIPO

The LIPO algorithm improvement, compared to Pure Random Search, is that it evaluates the objective function only when a certain condition is verified:

min i=1..t (f (X i ) + k • ∥X t+1 -X i ∥ 2 ) ≥ max i=1...t f (X i ) . (1)
The meaning of this condition can be understood in depth in [START_REF] Malherbe | Global optimization of lipschitz functions[END_REF], but it basically means that we won't explore a point for which, according to our observations, we can be sure that the evaluation will be below one of our other observations, thus it can't be the maximum. This condition is implemented as followed in Algorithm 1. Then, we define the LIPO algorithm in Section A Algorithm 3. With this algorithm, we have new confidence intervals on the value of the maximum, described below.

Naive LIPO Upper Bound

For any f ∈ Lip(k), any n ∈ N ⋆ and δ ∈ (0, 1), we have with probability at least 1 -δ,

max x∈X f (x) -max i=1...n f (X i ) ≤ k • diam(X) • ln(1/δ) n 1 d . (2)

Fast LIPO Bounds

When the following conditions are satisfied:

LIPO bounds conditions 1. the global optimizer x ⋆ ∈ X is unique;

2. for some κ ≥ 1, c κ ≥ 0, for all x ∈ X :

f (x ⋆ ) -f (x) ≥ c κ • ∥x -x ⋆ ∥ κ 2 . (3)
we have faster rates for the same confidence intervals:

Fast LIPO Bounds: for any n ∈ N ⋆ and δ ∈ (0, 1), we have with probability at least 1 -δ the following upper bound,

max x∈X f (x) -max i=1...n f (X i ) ≤k • diam(X ) ×      exp -C k,κ • n ln(2) ln(n/δ)+2(2 √ d) d if κ = 1 2 κ 2 1 + C k,κ • n(2 d(κ-1) -1) 2 ln(n/δ)+2(2 √ d) d -κ d(κ-1) if κ > 1 (4)
where C k,κ = (c κ max x∈X ∥x -x ⋆ ∥ κ-1 /8k) d , and the following lower bound:

c κ • rad(X ) κ • e -κ d n+ √ 2n ln(1/δ)+ln(1/δ) ≤ max x∈X f (x) -max i=1...n f (X i ). (5)

AdaLIPO

The AdaLIPO algorithm is a variant for LIPO when the Lipschitz constant of the objective function is unknown. AdaLIPO provides a way to estimate this constant while optimizing the function. The estimated constant is given according to the Eq. 6:

kt ≜ inf k i∈Z : max i̸ =j |f (X i ) -f (X j )| ∥X i -X j ∥ 2 ≤ k i . (6)
We can choose any series (k i ) i∈Z ∈ R. In this paper, we choose to use one series defined in [START_REF] Malherbe | Global optimization of lipschitz functions[END_REF]:

k i = (1 + α) i . Thus, kt = (1 + α) it , where i t = ln max i̸ =j |f (X i ) -f (X j )| ∥X i -X j ∥ 2 1 ln(1 + α) . ( 7
)
The estimation of the Lipschitz constant of AdaLIPO ensures that the constant k cannot be overestimated of more than one term in the series. For example, if

k i < k < k i+1 , AdaLIPO ensures that kt ≤ k i+1 .
The AdaLIPO algorithm is defined in Section A Algorithm 4.

For this algorithm, we also have "naives" rates if conditions defined in 3.1.2 are not satisfied.

Naive AdaLIPO Upper Bound:

max x∈X f (x) -max i=1...n f (X i ) ≤ k i ⋆ × diamX × 5 p + 2 ln(δ/3) p ln(1 -Γ(f, k i ⋆ -1 )) 1 d × ln(3/δ) n 1 d (8)
where Γ(f,

k i * -1 ) ≜ P |f (X 1 )-f (X 2 )| ∥X 1 -X 2 ∥ 2 > k i * -1 > 0 and i ⋆ = min{i ∈ Z : f ∈ Lip(k i )}.
When 3.1.2 are satisfied, we have a faster upper bound.

Fast AdaLIPO Upper Bound:

max x∈X f (x) -max i=1...n f (X i ) ≤ k i ⋆ × diam(X ) × exp 2 ln(δ/4) p ln(1 -Γ(f, k i ⋆ -1 )) + 7 ln(4/δ) p(1 -p) 2 ×      exp -C k i * ,κ • n(1-p) ln(2) if κ = 1, 2 κ 1 + C k i * ,κ • n(1-p)(2 d(κ-1) -1) 2 ln(n/δ)+4(2 √ d) d -κ d(κ-1) if κ > 1 (9)
where

C k i ⋆ ,κ = (c κ max x∈X ∥x -x ⋆ ∥ κ-1 2 /8k i ⋆ ) d .

Experimental analysis

The main purpose of this paper is to provide improvements through experimental analysis for LIPO and AdaLIPO. We led several experiments on popular global optimization benchmark functions.

Selected benchmark functions

As global optimization algorithms such as LIPO can be used for low dimensional problems, we picked 2D functions for visualization purposes. Note that any of the code can be executed on higher dimensional problems also. As our optimization aims to find a global maximum here, some of the functions we selected are the opposite of "classical" benchmark functions.

Himmelblau function

This functions writes

f (x, y) = -(x 2 + y -11) 2 -(x + y 2 -7) 2 , ∀x, y ∈ R. (10)
This function has 4 global maxima, at

• (3, 2)
• (-2.805118..., 3.131312...)

• (-3.779310, -3.283186...)

•

Hölder table function

This functions writes

f (x, y) = sin(x) cos(y) exp 1 - x 2 + y 2 π , ∀x, y ∈ R. (11)
This function has 4 global maxima, at

Rastrigin function

This functions writes, in dimension n,

f (x 1 , ..., x n ) = -10n - n i=1 x 2 i -10 cos(2πx i ) . (12)
This function has 1 global maximum, at (0, ..., 0), such that f = 0. In dimension 2, it has a Lipschitz constant of approximately 96 over [-5.12, 5.12] 2 , and satisfies the fast rate property 3.1.2, with k = 2, c k = 1 + 20π 2 .

Rosenbrock function

This functions writes,

f (x, y) = -(1 -x) 2 -100(y -x 2 ) 2 . ( 13
)
This function has 1 global maximum, at (1, 1), such that f = 0. It has a Lipschitz constant of approximately 14607 over [-3, 3] 2 , and does not satisfy the fast rate property 3.1.2.

Sphere function

This functions writes, in dimension n

f (x 1 , ..., x n ) = - x - π 16 2 + y - π 16 2 . ( 14
)
This function has 1 global maximum, at (0, 0), such that f = 0. In dimension 2, it has a Lipschitz constant of approximately 1.5 over [0, 1] 2 , and satisfies the fast rate property 3.1.2, with k = 1, c k = 1.

Square function

This functions writes, in dimension n

f (x 1 , ..., x n ) = - n i=1 x 2 i = -∥x∥ 2 2 . ( 15
)
This function has 1 global maximum, at (0, ..., 0), such that f = 0. In dimension 2, it has a Lipschitz constant of 20 √ 2 over [-5.12, 5.12] 2 , and satisfies the fast rate property 3.1.2, with k = 2, c k = 1.

Experiment setup

For both LIPO and AdaLIPO, we fixed a number of steps n = 2000 which represents the maximum number of times we will evaluate the function. Remember that what is supposed to be costly in this kind of problem is not the number of samples we draw, but the evaluation of the function (typically a simulation, costing a lot of time to be executed). We compared both algorithms with Pure Random Search (PRS) on the 6 functions defined in 4.1. For AdaLIPO, we set p = 0.5 and α = 0.01 (needed in Eq. 7). Each algorithm is stopped when it reaches n iterations or when it gets close enough to the known maximum. To evaluate the latter, we used a metric defined in [START_REF] Malherbe | Global optimization of lipschitz functions[END_REF]:

Stop at iteration i if f (X i ) ≥ f target (t) (16)
where

f target (t) = max x∈X f (x) -max x∈X f (x) - x∈X f (x) dx µ(X ) (1 -t), ∀t ∈ [0, 1]. (17)
This condition allows us to stop the algorithm whenever we consider it is close enough to the true maximum, given the parameter t. The bigger t, the closer the algorithm must be to the true maximum. In our experiment, we fixed t = 0.99. To compute Eq. 17, we need the value of the true maximum (which we know because we chose the the benchmark functions accordingly), and the value of the integral, which we estimated using a Monte-Carlo method with 10 6 samples.

Results

We ran 100 times the experiment for each algorithm on each benchmark function.

The results are shown in Table 1. As stated in the original paper, both algorithms are way better than PRS and the AdaLIPO quickly converges to the same results as LIPO. For each function, we observed the same behavior of LIPO and AdaLIPO. While PRS simply tests uniformly the whole set, LIPO and AdaLIPO first sample uniformly before sampling mostly in the region of interest. This behavior is even more pronounced for AdaLIPO when we reduce the parameter p for exploration. However, reducing p too much might be problematic for the algorithm to properly estimate the Lipschitz constant of the function, as it won't have a representation of the function's graph precise enough. A too large underestimation of the Lipschitz constant could lead the LIPO's condition (Eq. 1) to erase regions where the maximizers live. On the contrary, setting p close to 1 will make AdaLIPO behave like PRS. Figure 5 illustrates this behavior on the Himmelblau function. Moreover, as we can see on Figure 6, AdaLIPO tends to underestimate the real Lipschitz constants when p decreases. This is due to the fact that the constants are estimated within local regions where the sparseness is proportional to p. Within these regions, the functions can be more regular than when considering the entire compact sets X . However, this behavior can lead to faster convergence, as we only are interested in the neighborhood of x * . Thus, we need to find a good compromise between enough exploration to have a good estimation of the Lipschitz constant and fast convergence through exploitation. 1 and p = 0.9 on the benchmark functions. The graphs represent the evolution of the estimated Lipschitz constant during the optimization process. We observe that AdaLIPO often tends to underestimate the Lipschitz constant, which can be explained because the "true" Lipschitz constant around the maximum is smaller than the one on X . The bigger is p, the closer the estimate is to the real value.

Convergence analysis

We led statistical analysis on the convergence of both LIPO and AdaLIPO. Using Eqs. 2, 4, and 9, we obtain for each function graphics showing the 95% confidence interval in which f (x * ) should be. In most cases, when the conditions for Eq.4 are satisfied, we see in Figure 4 that the convergence of the confidence interval is way faster than using the boundaries given by Eq.2.

5 Empirical improvements

Stopping criterion

While experimenting with both LIPO and AdaLIPO, we noticed, as expected, that the number of samples drawn from a uniform law grows exponentially (in fact probably hyperbolically) with respect to the number of function evaluations as shown in Figure 7. This makes us want to define a stopping criterion that is different from while t < n with fixed n, because it might take a really long time to converge, or not converge at all (as the condition Eq.1 will never be satisfied). The improvement we propose in this paper consists in stopping the algorithm as soon as the slope of the plot in Figure 7 exceeds a threshold γ. The bigger γ, the longer but the more precise the result will be. In practice, we approximate γ with finite differences on several iterations (because from the one to the other, there might be too much randomization and a moment of bad luck can stop the algorithm too soon). The pseudocode for this stopping criterion is described in 2.

Decreasing Bernoulli parameter for AdaLIPO

For AdaLIPO, as explained in Section 3, it has two possibilities at each iteration: exploration or exploitation. The choice of the path it will take is given by the result of a Bernoulli random variable B(p). By intuition and by experience, we can think that exploring a lot at the beginning of the algorithm is a good way to approximate correctly the Lipschitz constant k, whereas the exploitation phase is the one where we will really use the observations we already have to find the maximum. That's why we propose to decrease progressively the parameter p during the optimization, for it to be high enough in the beginning, and to be small enough at the end so we can focus on exploiting our observations. In a way, one can think of this as a first phase where the algorithm focuses on estimating the Lipschitz constant, and a second phase where it basically applies LIPO to this estimated Lipschitz constant. Of course, the two phases are not really separated (we propose a continuous decrease of p = p(t)), but that's the idea behind it.

For instance, we empirically suggest to take p(t) = min 1, 1 ln(t) , with the convention

1 0 = +∞.
These two improvements resulted in new versions of LIPO and AdaLIPO, referred to as LIPO-E and AdaLIPO-E in the following.

Empirical comparison

We decided to compare both versions of LIPO and AdaLIPO, with and without the proposed improvements. Regarding the stopping criterion, we set γ = 800 and the slope is computed over the 5 last number of samples. We ran the 4 algorithms on some benchmark functions defined in Section 4.1. We fixed a maximum number of evaluations for each function, depending on their difficulties. We removed the target stopping condition defined in Eq. 16, therefore, the original version of LIPO and AdaLIPO exhausted the maximum number of evaluations allowed. However, the enhanced versions could stop earlier if the slope condition defined in Section 5.1 is reached. The other hyperparameters of the experiment are the same as in Section 4.2, except that we ran 10 times the experiment instead of 100 times. The results are shown in Table 2. We chose to display only the 3 benchmark functions where the slope stopping criterion is met. We can see that, with significantly fewer iterations, the distances from the real global maximum of our enhanced algorithms are in the same order of magnitude and sometimes less than the original versions. As expected, our stopping criterion allows to totally emancipate from the maximum number of evaluations, which is an arbitrary parameter. Indeed, the original versions of LIPO and AdaLIPO stop when they evaluate the function n times. However, sampling a potential maximizer (a point verifying Eq. 1) can be very difficult; for instance if the Lipschitz constant is small or if the algorithm already has a good approximation of the maximum. Our stopping criterion ensures that, if the algorithm struggles too much to sample a potential maximizer, it stops. One can run LIPO or AdaLIPO until it met the slope stopping criterion, the resulting value will be the best value one can obtain using the algorithm in a reasonable amount of time. 2: Comparison between the original algorithms and our empirically improved versions. # evals represents the number of function evaluations and d max the distance from the real maximum. For AdaLIPO-E, γ = 800. We can see that, with significantly less evaluation, LIPO-E and AdaLIPO-E compete with the original version in terms of distance to the real maximum.

We also compared AdaLIPO using only the decreasing Bernoulli parameter (referred as AdaLIPO-B) with LIPO and AdaLIPO in the exact same experimental setup as in Section 4.2. The results are summarized in Table 3. As we can see, AdaLIPO-B significantly outperforms the original AdaLIPO on this benchmark. It even succeeded to beat LIPO on almost every problem. In the next section, we highlight how our empirical improvements allows such a performance gain.

Understanding the improvements' contributions

This section aims at understanding the contribution of the two improvements introduced in Section 2. Indeed, the enhanced version of AdaLIPO includes the two improvements (decreasing Bernoulli parameter and Stopping criterion) and leads to better performance for some benchmark functions, both in terms of the number of evaluations and distance to the maximum (i.e. the difference between the real maximum value and our best observation). To understand better these results we need to identify the separate contribution of the improvements. To this end, we conducted an experiment where we compared the original AdaLIPO, AdaLIPO-E and two other AdaLIPO versions one called AdaLIPO-B which includes only the Bernoulli parameter and AdaLIPO-slope which only includes the stopping criterion. We studied the behavior of these 4 algorithms for 4 benchmark functions. We fixed the number of evaluations to 2000 (except from Rastrigin function where we fixed this parameter to 1000) and ran 100 times each experiment. The results are summarized in Table 4. We fixed the following hyperparameters: slope's size to 5, maximum slope to γ = 1000 and p = 0.5.

On the one hand we observed that the Bernoulli parameter allows a better estimation of the function's maximum while slightly degrading the Lipschitz constant estimation compared to the classic AdaLIPO. This improvement also increases the number of samples however, this step is not expensive. On the other hand, the stopping criterion, as expected, reduced the number of function evaluations which is the expensive step of the method. Combined these two improvements lead to AdaLIPO-E. Thus, we can see that our version of this algorithm inherits the properties of the two improvements. Indeed, the maximum estimation is better while having in general a slightly worse Lipschitz constant estimation but proceeding to less evaluation. It corroborates what we assumed in Section 4.3, i.e. underestimating the Lipschitz constant can lead to faster convergence. We also provide with a visual illustration of the improvements' behaviors in Figure 8.

Application scope of LIPO

As many optimization algorithms, LIPO is subject to the curse of dimensionality. In fact, we can show that in some sense, LIPO converges towards PRS in high dimension. Indeed, if we want to optimize f on a "non-small" subset X of R d , by looking at our algorithm 3, we will at iteration t + 1 erase from our search space, at best, the ball B x t+1 , α k with k being the Lipschitz constant of the objective function, and α ≥ max x∈X f (x) -min x∈X f (x). For LIPO to be efficient we need:

• to reduce the search space, so we need to have a control on k (for it not to be too big);

• to have a control on µ(X ) (for it not to be too big as well).

The main problem is that classical functions in high dimensions are usually defined on quite big subspaces X , with high Lipschitz constants k. To summarize, in the best case, we will have a search space of volume

V t = µ(X ) -t π d/2 α d k d Γ( d 2 + 1)
at iteration t + 1. Thus, the probability to reject the point at iteration t + 1 will be in the best scenario:

P(Reject(x t+1 )) = t π d/2 α d k d Γ d 2 + 1 µ(X ) (18)
i.e., the probability for x t+1 to be in the erased space. Most of the time,

t π d/2 α d k d Γ( d 2 +1)µ(X )
will be tiny.

To properly see it, let's take a simple example. Define f as the square function 15. Let's take X ≜ [-1, 1] d which verifies µ(X ) = 2 d . For this subset, the Lipschitz constant will be k = 2 d as well, and α = d. Then, using 18, we will have

P(Reject(x t+1 )) ≤ t π d/2 d d (2 d ) d Γ d 2 + 1 2 d ≜ tC d . (19)
For instance, the value of C d is 0.78 for d = 2, 0.22 for d = 3, 4.9 × 10 -4 for d = 5, 2.0 × 10 -20 for d = 10 etc.

Therefore, LIPO and, by extension, AdaLIPO, are not good choices of algorithms for maximizing a high dimensional function.

Conclusion

In this paper, we provide a reproducible implementation of both LIPO and AdaLIPO and we tested them on classical benchmark functions for global optimization. Through numerical experiments, we also propose two intuitive improvements: a decreasing exploration-exploitation parameter for AdaLIPO, and a stopping criterion based on the number of rejected samples for both algorithms. We compared original and enhanced versions of both algorithms on our benchmark with respect to the number of evaluations of the objective function and the distance to the real maximum. Those experiments show significant improvements of the two methods (LIPO and AdaLIPO), with respect to both criteria. The stopping criterion allows the algorithm to reduce the number of evaluations of the function in exchange of a small decrease of the precision, whereas the progressive decrease of the Bernoulli parameter often increases precision due to an evolving exploration-exploitation trade-off. We also discussed on the application scope of LIPO and AdaLIPO, stating that these algorithms quickly tend to PRS with respect to dimension. LIPO, AdaLIPO, and our enhanced versions are not suitable for maximizing high dimensional functions in a reasonable amount of time.

Note that the benchmark functions we used in this paper are fast to evaluate, which is not generally the case in the industry. This choice allowed us to perform a complete statistical analysis of the algorithms, which required a lot of function evaluations to be significant. However, these functions are as hard to optimize as most industrial objective functions (e.g. [START_REF] Papamichail | Global optimization of dynamic systems[END_REF], [START_REF] Hovd | A brief introduction to model predictive control[END_REF], [START_REF] Ríos-Mercado | Optimization problems in natural gas transportation systems: A state-of-the-art review[END_REF], [START_REF] Parsopoulos | Unified particle swarm optimization for solving constrained engineering optimization problems[END_REF]). Thus, our results are fully extendable to the latter case, without loss of generality.

In the future, it would be interesting to make a study of our versions of LIPO and AdaLIPO within a complex industrial framework in order to assess the performance of these algorithms in a more realistic problem. We also would like to develop a library containing efficient implementations of these algorithms for making them usable by as many people as possible, from all fields.

Image Credits

MrMambo (Wikipedia) 2 Alexander Elvers (Wikipedia), CC-BY-SA 3

Figure 2 :

 2 Figure 2: Global optimization for hyperparameters tuning. Traditional methods for hyperparameters tuning consist in a grid search on which the function is evaluated at every cross from the above graph. The resulting values of the objective function are represented with colored level lines.

Figure 3 :

 3 Figure 3: Graphs of benchmark functions in 2D.

Figure 4 :

 4 Figure 4: Lower and upper bounds estimation for the maximum value for Rastrigin function through the evaluations given by Eqs. 2 and 4. Fast rates are here much closer to the true value of the maximum (which is 0) than naive rates. The maximum value is very close thus hidden by the LIPO lower bound curve.

9 Figure 5 :

 95 Figure 5: Visual comparison between each algorithm on the Himmelblau function. As PRS (a) explores uniformly X , LIPO (b) andAdaLIPO (c & d) methods tend to explore only the interesting areas to find the maximum. Also, we see the impact of the exploration rate p from AdaLIPO: the higher p, the more we explore and the more AdaLIPO will behave like PRS.

Figure 6 :

 6 Figure6: Examples of Lipschitz constant estimations of AdaLIPO with p = 0.1 and p = 0.9 on the benchmark functions. The graphs represent the evolution of the estimated Lipschitz constant during the optimization process. We observe that AdaLIPO often tends to underestimate the Lipschitz constant, which can be explained because the "true" Lipschitz constant around the maximum is smaller than the one on X . The bigger is p, the closer the estimate is to the real value.

Figure 7 :

 7 Figure 7: Number of samples with respect to the number of function evaluations for LIPO on the Rastrigin function. The growth appears to be exponential, and in fact is hyperbolic as the more we evaluate, the less we are likely to accept a new point (to the point where we won't accept any new point).

Figure 8 :

 8 Figure 8: Visual understanding of the contributions of the proposed improvements.Compared to AdaLIPO (a), AdaLIPO-B (b) tends to explore more the region of interest (which can be seen with a higher number of evaluations at the center of X , in yellow). AdaLIPO-slope (c) reduces its overall number of function evaluations, without modifying its exploration-exploitation parameter, and AdaLIPO-E (d) combines those two behaviors.

Table 1 :

 1 Results of the numerical experiments. The table shows the total number of function evaluations (mean ± standard deviation) required to meet the condition stated in Eq. 16. We clearly see that LIPO and AdaLIPO outperform PRS. On some functions, AdaLIPO converges faster than LIPO which can be due to an underestimation of the Lipschitz constant around the maximum.

		Himmelblau	Hölder	Rastrigin	Rosenbrock	Sphere	Square
	PRS	184 ± 185	1245 ± 686 1950 ± 236	13 ± 13	1811 ± 436 188 ± 152
	LIPO	100 ± 86	508 ± 217	670 ± 183	11 ± 10	46 ± 10	43 ± 22
	AdaLIPO	97 ± 77	319 ± 201	913 ± 297	12 ± 11	28 ± 8	62 ± 47

Table 3 :

 3 Empirical performance of our enhanced AdaLIPO. The table shows the total number of function evaluations (mean ± standard deviation) required to meet the condition stated in Eq. 16. AdaLIPO-B outperforms LIPO and AdaLIPO in almost every problem.

		Himmelblau	Hölder	Rastrigin	Rosenbrock Sphere	Square
	LIPO	100 ± 86	508 ± 217	670 ± 183	11 ± 10	46 ± 10 43 ± 22
	AdaLIPO	97 ± 77	319 ± 201	913 ± 297	12 ± 11	28 ± 8	62 ± 47
	AdaLIPO-B	65 ± 46	228 ± 136 616 ± 187	11 ± 10	22 ± 6	51 ± 36

Table 4 :

 4 Empirical performance of the two proposed improvements of our enhanced AdaLIPO. The table shows the contributions of each improvement by evaluating several criteria. The total number of function evaluations (mean ± standard deviation), the distance from the real maximum d max , the estimation of the Lipschitz constant κ and the number of samples. We see that AdaLIPO-B has the best maximum estimation in general while AdaLIPO-slope stops earlier but with a worse estimation. AdaLIPO-E is a combination of the two improvements and has the best performance in terms of maximum estimation and the number of function evaluations.

			Himmelblau	Hölder	Rosenbrock	Square	Rastrigin
		d max	0.0188 ± 0.0188 0.0024 ± 0.0029	0.0529 ± 0.0487	0.0028 ± 0.0025	0.4066 ± 0.3439
	AdaLIPO	# samples κ	9846 ± 1286 224.9 ± 19.7	133217 ± 61770 27.84 ± 2.36	2793.01 ± 56.25 13358.31 ± 671.16 28.1024 ± 0.00 42806 ± 2753	21028 ± 9583 94.46 ± 4.00
		# evals	2000	2000	2000	2000	1000
		d max	0.0061 ± 0.0058 0.0010 ± 0.0017	0.034 ± 0.034	0.001 ± 0.0008	0.0632 ± 0.0960
	AdaLIPO-B	# samples κ	22745 ± 3975 201.74 ± 20.09	519322 ± 410188 26.36 ± 4.09	3458 ± 119 12151.9 ± 977.6	113937 ± 9827 27.03 ± 1.26	178520 ± 98026 90.8434 ± 4.0417
		# evals	2000	2000	2000	2000	1000
		d max	0.0136 ± 0.0111	0.003 ± 0.003	0.0391 ± 0.0361	0.0029 ± 0.0027	0.4040 ± 0.3923
	AdaLIPO-slope	# samples κ	9870 ± 1187 221.24 ± 18.98	109004 ± 34252 28.08 ± 2.43	2779 ± 58 13358 ± 677.8	42582 ± 2342 28.10 ± 0.00	19086 ± 9630 95.6237 ± 3.7340
		# evals	2000	1976.22 ± 126.23	2000	2000	999.5400 ± 4.5769
		d max	0.0062 ± 0.0056 0.0027 ± 0.0041	0.0352 ± 0.0295	0.001 ± 0.0009	0.0825 ± 0.0819
	AdaLIPO-E	# samples κ	23596 ± 4171 199.52 ± 22.47	168210 ± 66780 24.02 ± 5.84	3463 ± 127 12302 ± 1070	114184 ± 9295 27.05 ± 1.26	72081 ± 16582 90.2581 ± 4.3964
		# evals	2000	1399 ± 567	2000	2000	894.8700 ± 124.5155

https://github.com/gaetanserre/LIPO-E

ln(n/δ)+4(2 √ d) d

https://commons.wikimedia.org/wiki/File:Hyperparameter_Optimization_using_Grid_

A Algorithms

Algorithm 1 LIPO's condition Require:

x: the candidate point X t+1 values: set of previous evaluated values f (X i ) k: Lipschitz constant points: set of previous point of evaluation ▷ sample counter to compute the difference between sampling and iterating X 1 ∼ U(f.bounds)

▷ sample from a uniform distribution k ← 0 ▷ initialized the estimation of the Lipschitz constant to 0 nb samples ← nb samples + 1 points ← [X 1 ] ▷ stored the points where f is evaluated, needed for condition algorithm 1

▷ stored the evaluations of f , needed for condition algorithm 1