Peter L Bartlett Peter

Victor Gabillon
email: victor.gabillon@huawei.com

Michal Valko

Aurélien Garivier

Satyen Kale

P L Bartlett

A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption

Keywords: optimization, tree search, deterministic feedback, stochastic feedback 1. Alternatively, we can turn

We study the problem of optimizing a function under a budgeted number of evaluations. We only assume that the function is locally smooth around one of its global optima. The difficulty of optimization is measured in terms of 1) the amount of noise b of the function evaluation and 2) the local smoothness, d, of the function. A smaller d results in smaller optimization error. We come with a new, simple, and parameter-free approach. First, for all values of b and d, this approach recovers at least the state-of-the-art regret guarantees. Second, our approach additionally obtains these results while being agnostic to the values of both b and d. This leads to the first algorithm that naturally adapts to an unknown range of noise b and leads to significant improvements in a moderate and low-noise regime. Third, our approach also obtains a remarkable improvement over the state-of-the-art SOO algorithm when the noise is very low which includes the case of optimization under deterministic feedback (b = 0). There, under our minimal local smoothness assumption, this improvement is of exponential magnitude and holds for a class of functions that covers the vast majority of functions that practitioners optimize (d = 0). We show that our algorithmic improvement is borne out in experiments as we empirically show faster convergence on common benchmarks.

Introduction

In budgeted function optimization, a learner optimizes a function f : X → R having access to a number of evaluations limited by n. For each of the n evaluations (or rounds), at round t, the learner picks an element x t ∈ X and observes a real number y t , where y t = f (x t ) + ε t , where ε t is the noise. Based on ε t , we distinguish two feedback cases:

Deterministic feedback The evaluations are noiseless, that is ∀t, ε t = 0 and y t = f (x t ). Please refer to the work by [START_REF] Nando De Freitas | Exponential regret bounds for Gaussian process bandits with deterministic observations[END_REF] for a motivation, many applications, and references on the importance of the case b = 0.

Stochastic feedback

The evaluations are perturbed by a noise of range b ∈ R + 1 : At any round, ε t is a random variable, assumed independent of the noise at previous rounds, E[y t |x t ] = f (x t ) and |y tf (x t )| ≤ b.

(1)

The objective of the learner is to return an element x(n) ∈ X with largest possible value f (x(n)) after the n evaluations. x(n) can be different from the last evaluated element x n . More precisely, the performance of the algorithm is the loss (or simple regret),

r n sup x∈X f (x) -f (x(n)) .
We consider the case that the evaluation is costly. Therefore, we minimize r n as a function of n.

We assume that there exists at least one point x ∈ X such that f (x ) = sup x∈X f (x).

Prior work Among the large work on optimization, we focus on algorithms that perform well under minimal assumptions as well as minimal knowledge about the function. Relying on minimal assumptions means that we target functions that are particularly hard to optimize. For instance, we may not have access to the gradients of the function, gradients might not be well defined, or the function may not be continuous. While some prior works assume a global smoothness of the function [START_REF] János | Global optimization in action. continous and lipschitz optimization: Algorithms, implementations and applications[END_REF][START_REF] Strongin | Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms[END_REF][START_REF] Hansen | Global optimization using interval analysis: revised and expanded[END_REF][START_REF] Baker | Rigorous global search: continuous problems[END_REF], another line of research assumes only a weak/local smoothness around one global maximum [START_REF] Auer | Improved rates for the stochastic continuumarmed bandit problem[END_REF][START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF]Bubeck et al., 2011a). However, within this latter group, some algorithms require the knowledge of the local smoothness such as HOO (Bubeck et al., 2011a), Zooming [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], or DOO [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF]. Among the works relying on an unknown local smoothness, SOO [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF][START_REF] Kawaguchi | Global continuous optimization with error bound and fast convergence[END_REF] represents the state-of-the-art for the deterministic feedback. For the stochastic feedback, StoSOO [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF] extends SOO for a limited class of functions. POO [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] provides more general results. We classify the most related algorithms in the following table. Note that for more specific assumptions on the smoothness, some works study optimization without the knowledge of smoothness: DiRect [START_REF] Jones | Lipschitzian optimization without the Lipschitz constant[END_REF] and others [START_REF] Slivkins | Multi-armed bandits on implicit metric spaces[END_REF]Bubeck et al., 2011b;[START_REF] Malherbe | Global optimization of lipschitz functions[END_REF] tackle Lipschitz optimization. Finally, there are algorithms that instead of simple regret, optimize cumulative regret, like HOO (Bubeck et al., 2011a) or HCT (Azar et al., 2014). Yet, none of them adapts to the unknown smoothness and compared to them, the algorithms for simple regret that are able to do that, such as POO or our StroquOOL, need to explore significantly more, which negatively impacts their cumulative regret [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF][START_REF] Locatelli | Adaptivity to Smoothness in X-armed bandits[END_REF].

Existing tools Partitionining and near-optimality dimension As in most of the previously mentioned work, the search domain X is partitioned into cells at different scales (depths), i.e., at a deeper depth, the cells are smaller but still cover all of X . The objective of many algorithms is to explore the value of f in the cells of the partition and determine at the deepest depth possible in which cell is a global maximum of the function. The notion of near-optimality dimension d aims at capturing the smoothness of the function and characterizes the complexity of the optimization task. We adopt the definition of near-optimality dimension given recently by [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] that unlike Bubeck et al. (2011a), [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF], [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF][START_REF] Gheshlaghi Azar | Online stochastic optimization under correlated bandit feedback[END_REF], avoids topological notions and does not artificially attempt to separate the difficulty of the optimization from the partitioning. For each depth h, it simply counts the number of near-optimal cells N h , cells whose value is close to f (x ), and determines how this number evolves with the depth h. The smaller d, the more accurate the optimization should be.

New challenges Adaptations to different data complexities As did [START_REF] Bubeck | The best of both worlds: stochastic and adversarial bandits[END_REF], [START_REF] Seldin | One practical algorithm for both stochastic and adversarial bandits[END_REF][START_REF] Seldin | One practical algorithm for both stochastic and adversarial bandits[END_REF][START_REF] De Rooij | Follow the leader if you can, hedge if you must[END_REF] in other contexts, we design algorithms that demonstrate near-optimal behavior under data-generating processes of different nature, obtaining the best of all these possible worlds. In this paper, we consider the two following data complexities for which we bring new improved adaptation.

• near-optimality dimension d = 0: In this case, the number of near-optimal cells is simply bounded by a constant that does not depend on h. As shown by [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF], if the function is lower-and upper-bounded by two polynomial envelopes of the same order around a global optimum, then d = 0. As discussed in the book of Munos (2014, section 4.2.2), d = 0 covers the vast majority of functions that practitioners optimize and the functions with d > 0

given as examples in prior work (Bubeck et al., 2011b;[START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF][START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF][START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF][START_REF] Shang | General parallel optimization without metric[END_REF] are carefully engineered. Therefore, the case of d = 0 is of practical importance. However, even with deterministic feedback, the case d = 0 with unknown smoothness has not been known to have a learner with a near-optimal guarantee. In this paper, we also provide that. Our approach not only adapts very well to the case d = 0 and b ≈ 0, it also provides an exponential improvement over the state of the art for the simple regret rate.

• low or moderate noise regime: When facing a noisy feedback, most algorithms assume that the noise is of a known predefined range, often using b = 1 hard-coded in their use of upper confidence bounds. Therefore, they cannot take advantage of low noise scenarios. Our algorithms have a regret that scales with the range of the noise b, without a prior knowledge of b. Furthermore, our algorithms ultimately recover the new improved rate of the deterministic feedback suggested in the precedent case (d = 0).

Main results

Theoretical results and empirical performance We consider the optimization under an unknown local smoothness. We design two algorithms, SequOOL for the deterministic case in Section 3 and StroquOOL for the stochastic one in Section 4.

• SequOOL is the first algorithm to obtain a loss e -Ω(n) under such minimal assumption, with deterministic feedback. The previously known SOO [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF] is only proved to achieve a loss of O(e - √ n ). Therefore, SequOOL achieves, up to log factors, the result of DOO that knows the smoothness. Note that [START_REF] Kawaguchi | Global continuous optimization with error bound and fast convergence[END_REF] designed a new version of SOO, called LOGO, that gives more flexibility in exploring more local scales but it was still only shown to achieve a loss of O(e - √ n ) despite the introduction of a new parameter. Achieving exponentially decreasing regret had previously only been achieved in setting with more assumptions [START_REF] Nando De Freitas | Exponential regret bounds for Gaussian process bandits with deterministic observations[END_REF][START_REF] Malherbe | Global optimization of lipschitz functions[END_REF][START_REF] Kawaguchi | Bayesian optimization with exponential convergence[END_REF]. For example, de Freitas et al. ( 2012) achieves e -Ω(n) regret assuming several assumptions, for example that the function f is sampled from the Gaussian process with four times differentiable kernel along the diagonal. The consequence of our results is that to achieve e -Ω(n) rate, none of these strong assumptions is necessary.

• StroquOOL recovers, in the stochastic feedback, up to log factors, the results of POO, for the same assumption. However, as discussed later, StroquOOL is a simpler approach than POO which additionally features much simpler and elegant analysis.

• StroquOOL adapts naturally to different noise range, i.e., the various values of b.

• StroquOOL obtains the best of both worlds in the sense that StroquOOL also obtains, up to log factors, the new optimal rates reached by SequOOL in the deterministic case. StroquOOL obtains this result without being aware a priori of the nature of the data, only for an additional log factor. Therefore, if we neglect the additional log factor, we can just have a single algorithm, StroquOOL, that performs well in both deterministic and stochastic case, without the knowledge of the smoothness in either one of them.

• In the numerical experiments, StroquOOL naturally adapts to lower noise. SequOOL obtains an exponential regret decay when d = 0 on common benchmark functions.

Algorithmic contributions and originality of the proofs Why does it work? Both SequOOL and StroquOOL are simple and parameter-free algorithms. Moreover, both SequOOL and StroquOOL are based on a new core idea that the search for the optimum should progress strictly sequentially from an exploration of shallow depths (with large cells) to deeper depths (small and localized cells). This is different from the standard approach in SOO, StoSOO, and the numerous extensions that SOO has inspired [START_REF] Bus ¸oniu | Optimistic planning for continuous-action deterministic systems[END_REF][START_REF] Wang | Bayesian Multi-Scale Optimistic Optimization[END_REF][START_REF] Al-Dujaili | Multi-objective simultaneous optimistic optimization[END_REF][START_REF] Qian | Scaling simultaneous optimistic optimization for high-dimensional nonconvex functions with low effective dimensions[END_REF][START_REF] Muhammad | Infinite dimensional optimistic optimisation with applications on physical systems[END_REF][START_REF] Derbel | Simultaneous optimistic optimization on the noiseless BBOB testbed[END_REF][START_REF] Preux | Bandits attack function optimization[END_REF][START_REF] Bus | Consensus for black-box nonlinear agents using optimistic optimization[END_REF][START_REF] Kawaguchi | Global continuous optimization with error bound and fast convergence[END_REF]. We come up with our idea by identifying a bottleneck in SOO [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF] and its extensions that open all depths simultaneously (their Lemma 2). However, in general, we show that the improved exploration of the shallow depths is beneficial for the deeper depths and therefore, we always complete the exploration of depth h before going to depth h + 1. As a result, we design a more sequential approach that simplifies our Lemma 2. This desired simplicity is also achieved by being the first to adequately leverage the reduced and natural set of assumptions introduced in the POO paper [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF]. This adequate and simple leverage should not conceal the fact that our local smoothness assumption is minimal and already way weaker than global Lipschitzness. Second, this leveraging was absent in the analysis for POO which additionally relies on the 40 pages proof of HOO; see [START_REF] Shang | General parallel optimization without metric[END_REF] for a detailed discussion. Our proofs are succinct2 while obtaining performance improvement (d = 0) and a new adaptation (b = 0). To obtain these, in an original way, our theorems are now based on solving a transcendental equation with the Lambert W function. For StroquOOL, a careful discrimination of the parameters of the equation leads to optimal rates both in the deterministic and stochastic case.

Intriguingly, the amount of evaluations allocated to each depth h follows a Zipf law [START_REF] Powers | New methods in language processing and computational natural language learning[END_REF], that is, each depth level h is simply pulled inversely proportional to its depth index h. It provides a parameter-free method to explore the depths without knowing the bound C on the number of optimal cells per depth (N h = C ∝ n/h when d = 0) and obtain a maximal optimal depth h of order n/C. A Zipf law has been used by [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] and [START_REF] Abbasi-Yadkori | Best of both worlds: Stochastic & adversarial best-arm identification[END_REF] in pure-exploration bandit problems but without any notion of depth in the search. In this paper, we introduce the Zipf law to tree search.

Finally, another novelty is that were are not using upper bounds in StroquOOL (unlike StoSOO, HCT, HOO, POO), which results in the contribution of removing the need to know the noise amplitude.

Partition, tree, assumption, and near-optimality dimension

Partitioning The hierarchical partitioning P = {P h,i } h,i we consider is similar to the ones introduced in prior work [START_REF] Munos | Optimistic optimization of a deterministic function without the knowledge of its smoothness[END_REF][START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF][START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF]: For any depth h ≥ 0 in the tree representation, the set {P h,i } 1≤i≤I h of cells (or nodes) forms a partition of X , where I h is the number of cells at depth h. At depth 0, the root of the tree, there is a single cell P 0,1 = X . A cell P h,i of depth h is split into children subcells {P h+1,j } j of depth h + 1. As [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], our work defines a notion of near-optimality dimension d that does not directly relate the smoothness property of f to a specific metric but directly to the hierarchical partitioning P. Indeed, an interesting fundamental quest is to determine a good characterization of the difficulty of the optimization for an algorithm that uses a given hierarchical partitioning of the space X as its input (see [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], for a detailed discussion). Given a global maximum x of f , i h denotes the index of the unique cell of depth h containing x , i.e., such that x ∈ P h,i h . We follow the work of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] and state a single assumption on both the partitioning P and the function f . Assumption 1 For any global optimum x , there exists ν > 0 and ρ ∈ (0, 1) such that ∀h ∈ N,

∀x ∈ P h,i h , f (x) ≥ f (x ) -νρ h .
Definition 1 For any ν > 0, C > 1, and ρ ∈ (0, 1), the near-optimality dimension3 d(ν, C, ρ) of f with respect to the partitioning P and with associated constant C, is

d(ν, C, ρ) inf d ∈ R + : ∀h ≥ 0, N h (3νρ h ) ≤ Cρ -d h , where N h (ε) is the number of cells P h,i of depth h such that sup x∈P h,i f (x) ≥ f (x ) -ε.
Tree-based learner Tree-based exploration or tree search algorithm is an approach that has been widely applied to optimization as well as bandits or planning [START_REF] Kocsis | Bandit-based Monte-Carlo planning[END_REF][START_REF] Coquelin | Bandit algorithms for tree search[END_REF][START_REF] Hren | Optimistic Planning of Deterministic Systems[END_REF]; see [START_REF] Munos | From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning[END_REF] for a survey. At each round, the learner selects a cell P h,i containing a predefined representative element x h,i and asks for its evaluation. We denote its value as f h,i f (x h,i ). We use T h,i to denote the total number of evaluations allocated by the learner to the cell P h,i . Our learners collect the evaluations of f and organize them in a tree structure T that is simply a subset of P: T {P h,i ∈ P : T h,i > 0}, T ⊂ P.

For the noisy case, we also define the estimated value of the cell f h,i . Given the T h,j evaluations y 1 , . . . , y T h,j , we have f h,i

1 T h,j
T h,j s=1 y s , the empirical average of rewards obtained at this cell. We say that the learner opens a cell P h,i with m evaluations if it asks for m evaluations from each of the children cells of cell P h,i . In the deterministic feedback, m = 1. For the sake of simplicity, the bounds reported in this paper are in terms of the total number of openings n, instead of evaluations. The number of function evaluations is upper bounded by Kn, where K is the maximum number of children cells of any cell in P.

Our results use the Lambert W function. Solving for the variable z, the equation A = ze z gives z = W (A). Notice that W is multivalued for z ≤ 0. Nonetheless, in this paper, we consider z ≥ 0 and W (z) ≥ 0, referred to as the standard W. Lambert W cannot be expressed with elementary functions. Yet, due to [START_REF] Hoorfar | Inequalities on the lambert w function and hyperpower function[END_REF], we have W (z) = log(z/ log z) + o(1).

Finally, let SequOOL explores the depth sequentially, one by one, going deeper and deeper with a decreasing number of cells opened per depth h, h max /h openings at depth h. The maximal depth that is opened is h max . The analysis of SequOOL shows that it is useful that h max n/log n , where log n is the n-th harmonic number, log n n t=1 1 t with log n ≤ log n + 1 for any positive integer n. SequOOL returns the element of the evaluated cell with the highest value, x(n) = arg max x h,i :P h,i ∈T f h,i . We use the budget of n + 1 for the simplicity of stating our guarantees. Notice that SequOOL does not use more openings than that as

, P = {P h,i } Initialization: Open P 0,1 . h max ← n/log(n) • For h = 1 to h max Open h max /h cells P h,i of depth h with largest values f h,j . Output x(n) ← arg max x h,i :P h,i ∈T f h,i .
1 + hmax h=1 h max h ≤ 1 + h max hmax h=1 1 h = 1 + h max log h max ≤ n + 1.
Remark 2 The algorithm can be made anytime and unaware of n using the classic 'doubling trick'.

Remark 3 (More efficient use of the budget) Because of the use of the floor functions • , the budget used in practice, 1 + hmax h=1 hmax h

, can be significantly smaller than n. While this only affects numerical constants in the bounds, in practice, it can influence the performance noticeably. Therefore one should consider, for instance, having h max replaced by c × h max with c ∈ R and c = max{c ∈ R : 1 + hmax h=1 c hmax h ≤ n}. Additionally, the use the budget n could be slightly optimized by taking into account that the necessary number of pulls at depth h is actually min h max /h , K h .

Analysis of SequOOL

For any global optimum x in f , let ⊥ h be the depth of the deepest opened node containing x at the end of the opening of depth h by SequOOL-an iteration of the for cycle. Note that ⊥ (•) is increasing. The proofs of the following statements are given in Appendix A.

Lemma 4 For any global optimum x with associated (ν, ρ) as defined in Assumption 1, for C > 1,

for any depth that h ∈ [h max ], if h max /h ≥ Cρ -d(ν,C,ρ)h , we have ⊥ h = h with ⊥ 0 = 0.
Lemma 4 states that as long as at depth h, SequOOL opens more cells than the number of nearoptimal cells at depth h, the cell containing x is opened at depth h.

Theorem 5 Let W be the standard Lambert W function (Section 2). For any function f , one of its global optima x with associated (ν, ρ), C > 1, and near-optimality dimension d = d(ν, C, ρ), we have, after n rounds, the simple regret of SequOOL is bounded as follows:

• If d = 0, r n ≤ νρ 1 C n log n . • If d > 0, r n ≤ νe -1 d W d log(1/ρ) C n log n .
For more readability, Corollary 6 uses a lower bound on W by [START_REF] Hoorfar | Inequalities on the lambert w function and hyperpower function[END_REF]. while the regret of SequOOL is ρ Ω(n) which is a significant improvement. As discussed in the introduction and by Valko et al. (2013, Section 5), the case d = 0 is very common. As pointed out by Munos (2011, Corollary 2), SOO has to actually know whether d = 0 or not to set the maximum depth of the tree as a parameter for SOO. SequOOL is fully adaptive, does not need to know any of this and actually gets a better rate. 4The conceptual difference from SOO is that SequOOL is more sequential: For a given depth h, SequOOL first opens cells at depth h and then at depth h + 1 and so on, without coming back to lower depths. Indeed, an opening at depth h + 1 is based on the values observed while opening at depth h. Therefore, it is natural and less wasteful to do the openings in a sequential order. Moreover, SequOOL is more conservative as it opens the lower depths more while SOO opens every depth equally. However from the perspective of depth, SequOOL is more aggressive as it opens depth as high as n, while SOO stops at √ n.

Comparison with DOO Contrarily to SequOOL, DOO knows the smoothness of the function that is used as input parameter ν = ν and ρ = ρ. However this knowledge only improves the logarithmic factor in the current upper bound. When d > 0, DOO achieves a simple regret of O n -1/d , when d = 0, the simple regret is of O(ρ n ).

DOO with multiple parallel ( ν, ρ) instances? An alternative approach to SequOOL, based on DOO, which would also not require the knowledge of the true smoothness (ν, ρ), is to run m multiple parallel instances of DOO with different values for ν and ρ. For instance, we could mimic the behavior of POO [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], and runm log n instances of DOO, each with budget n/ log n , where, in instance i ∈ [ log n ], ρ i is set to 1/2 i . Under the condition that ρ ≥ ρ min = 1/2 log n ≈ 1/n, among these log n instances, one of them, let us say that the j-th one, is such that we have

ρ j = 1/2 j ≤ ρ ≤ 1/2 j-1 = 2 ρ j . This instance j of DOO therefore a x(n) with a regret ρ Ω(n) .
However, in the case of ρ ≤ ρ min = 1/2 log n = 1/n, we can only guarantee a regret ( ρ min ) Ω(n) . Therefore, for a fixed n, this approach will fail to capture the case where ρ ≈ 0 such as, for instance, the case ρ = e -n . Note that this argument still holds if the number of parallel instances m = o(n). Finally, the other disadvantage would be that as in POO, this alternative would use upper-bounds ν max and ρ max that would appear in the final guarantees.

Lower bounds As discussed by [START_REF] Munos | From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning[END_REF] for d = 0, DOO matches the lower bound and it is even comparable to the lower-bound for concave functions. While SOO was not matching the bound of DOO, with our result, we now know that, up to a log factor, it is possible to achieve the same performance as DOO, without the knowledge of the smoothness.

h max ← n 2(logn+1) 2 , p max ← log h max . For h = 1 to h max Exploration For m = 1 to h max /h
Open hmax hm times the non-opened cell P h,i with the highest values f h,i and given that T h,i ≥ hmax hm •

For p = 0 to p max Cross-validation Evaluate h max /2 times the candidates:

x(n, p) ← arg max

(h,i)∈T , T h,i ≥2 p f h,i . Output x(n) ← arg max {x(n,p), p∈[0:pmax]} f (x(n, p))
Figure 2: The StroquOOL algorithm

In the presence of noise, it is natural to evaluate the cells multiple times, not just one time as in the deterministic case. The amount of times a cell should be evaluated to differentiate its value from the optimal value of the function depends on the gap between these two values as well as the range of noise. As we do not want to make any assumptions on knowing these quantities, our algorithm tries to be robust to any potential values by not making a fixed choice on the number of evaluations. Intuitively, StroquOOL implicitly uses modified versions of SequOOL, denoted SequOOL(p),5 where each cell is evaluated p times, p ≥ 1, while in SequOOL p = 1. On one side, given one instance of SequOOL(p), evaluating more each cells (p large) leads to a better quality of the mean estimates in each cell. On the other side, as a tradeoff, it implies that SequOOL(p) is using more evaluations per depth and therefore is not able to explore deep depths of the partition. The largest depth explored is now O(n/p). StroquOOL then implicitly performs the same amount of evaluations as it would be performed by log n instances of SequOOL(p) each with a number of evaluations of p = 2 p , where we have p ∈ [0 : log n].

The St(r)ochastic sequential Online Optimization aLgorithm, StroquOOL, is described in Figure 2. Remember that 'opening' a cell means 'evaluating' its children. The algorithm opens cells by sequentially diving them deeper and deeper from the root node h = 0 to a maximal depth of h max . At depth h, we allocate, in a decreasing fashion, different number of evaluations h max /(hm) to the cells with highest value of that depth, with m from 1 to h max /h . The best cell that has been evaluated at least O(h max /h) times is opened with O(h max /h) evaluations, the next best cells that have been evaluated at least O(h max /(2h)) times are opened with O(h max /(2h)) evaluations, the next best cells that have been evaluated at least O(h max /(3h)) times are opened with O(h max /(3h)) evaluations and so on, until some O(h max /h) next best cells that have been evaluated at least once are opened with one evaluation. More precisely, given, m and h, we open, with h max /(hm) evaluations, the m non-previously-opened cells P h,i with highest values f h,i and given that T h,i ≥ h max /(hm) . For each p ∈ [0 : p max log 2 (h max ) ], the candidate output x(n, p) is the cell with highest estimated value that has been evaluated at least 2 p times, x(n, p) arg max

(h,i)∈T ,T h,i ≥2 p f h,i .
We set h max n/(2(logn + 1) 2 ) . Then, StroquOOL uses less than n openings, which we detail in Appendix B.

Analysis of StroquOOL

The proofs of the following statements are given in Appendix D and E. For any x , ⊥ h,p is the depth of the deepest opened node with at least 2 p evaluations containing x at the end of the opening of depth h of StroquOOL.

Lemma 7 For any global optimum x with associated (ν, ρ) from Assumption 1, any C > 1, for any δ ∈ (0, 1), on event ξ δ defined in Lemma 12, for any pair (h, p) of depths h, and integer p such that h ∈ [h max ], and p ∈ [0 : log h max /h ], we have that if b log(2n 2 /δ)/2 p+1 ≤ νρ h and if h max /(4h2 p ) ≥ Cρ -d(ν,C,ρ)h , that ⊥ h,p = h with ⊥ 0,p 0.

Lemma 7 gives two conditions so that the cell containing x is opened at depth h. This holds if (a) StroquOOL opens, with 2 p evaluations, more cells at depth h than the number of near-optimal cells at depth h (h max /(4h2 p ) ≥ Cρ -d(ν,C,ρ)h ) and (b) the 2 p evaluations are sufficient to discriminate the empirical average of near-optimal cells from the empirical average of sub-optimal cells (b log(2n 2 /δ)/2 p ≤ νρ h ). To state the next theorems, we introduce h a positive real number satisfying (h max ν 2 ρ 2 h )/(4 hb 2 log(2n 2 /δ)) = Cρ -d h . We have

h = 1 (d + 2) log(1/ρ) log n log n + o(1) with n ν 2 h max (d + 2) log(1/ρ) 4Cb 2 log(2n 2 /δ) •
The quantity h gives the depth of the deepest cell opened by StroquOOL that contains x with high probability. Consequently, h also lets us characterize for which regime of the noise range b we recover results similar to the loss for the deterministic case. Discriminating on the noise regime, we now state our results, Theorem 8 for a high noise and Theorem 10 for a low one.

Theorem 8 High-noise regime After n rounds, for any function f , a global optimum x with associated (ν, ρ), C > 1, and near-optimality dimension simply denoted d = d(ν, C, ρ), with probability at least 1δ, if b ≥ νρ h / log(2n 2 /δ), the simple regret of StroquOOL obeys

r n ≤ νρ 1 (d+2) log(1/ρ) W n 2(log 2 n+1) 2 (d+2) log(1/ρ)ν 2 4Cb 2 log(2n 2 /δ) + 2b log(2n 2 /δ) n 2(log 2 n + 1) 2 •
Corollary 9 With the assumptions of Theorem 8 and n > e, r n ≤ ν log n n

1 d+2 + 2b 18 log(2n 2 /δ) 2 n 2(log 2 n+1) 2 , where n n/2 (log 2 n + 1) 2 (d + 2) log(1/ρ)ν 2 4Cb 2 log(2n 2 /δ) •
Theorem 10 Low-noise regime After n rounds, for any function f and one of its global optimum x with associated (ν, ρ), any C > 1, and near-optimality dimension simply denoted d = d(ν, C, ρ), with probability at least 1δ, if b ≤ νρ h / log(2n 2 /δ), the simple regret of StroquOOL obeys

• If d = 0, r n ≤ 3νρ 1 4C n/2 (log 2 (n)+1) 2 . • If d > 0, r n ≤ 3νe -1 d W n/2 (log 2 n+1) 2 d log 1 ρ 4C .
This results also hold for the deterministic feedback case, b = 0, with probability 1.

Corollary 11 With the assumptions of Theorem 10, if d > 0, then

r n ≤ 3ν log( n) n 1 d with n n/2 (log 2 n + 1) 2 d log(1/ρ) 4C
and n > e.

Discussion for the stochastic feedback

Worst-case comparison to POO and StoSOO When b is large and known StroquOOL is an algorithm designed for the noisy feedback while adapting to the smoothness of the function. Therefore, it can be directly compared to POO and StoSOO that both tackle the same problem. The results for StroquOOL, like the ones for POO, hold for d ≥ 0, while the theoretical guarantees of StoSOO are only for the case d = 0. The general rate of StroquOOL in Corollary 96 is similar to the ones of POO (for d ≥ 0) and StoSOO (for d = 0) as their loss is O(n -1/(d+2) ). More precisely, looking at the log factors, we can first notice an improvement over StoSOO when d = 0. We have r

StroquOOL n = O(log 3/2 (n)/ √ n) ≤ r StoSOO n = O(log 2 n/ √ n).
Comparing with POO, we obtain a worse logarithmic factor, as

r POO n = O((log 2 (n)/n)) 1/(d+2) ) ≤ r StroquOOL n = O(((log 3 n)/n) 1/(d+2)
). Despite having this (theoretically) slightly worse logarithmic factor compared to POO, StroquOOL has two nice new features. First, our algorithm is conceptually simple, parameter-free, and does not need to call a sub-algorithm: POO repetitively calls different instances of HOO which makes it a heavy meta-algorithm. Second, our algorithm, as we detail next, naturally adapts to low noise and, even more, recovers the rates of SequOOL in the deterministic case, leading to exponentially decreasing loss when d = 0. We do not know if the extra logarithmic factor for StroquOOL as compared to POO to is the unavoidable price to pay to obtain an adaptation to the deterministic feedback case. Comparison to HOO HOO is also designed for the noisy optimization setting. HOO needs to know the smoothness of f , i.e., (ν, ρ) are input parameters of HOO. Using this extra knowledge HOO is only able to improve the logarithmic factor to achieve a regret of r HOO n = O((log(n)/n) 1/(d+2) ). Adaptation to the range of the noise b without a prior knowledge A favorable feature of our bound in Corollary 9 is that it characterizes how the range of the noise b affects the rate of the regret for all d ≥ 0. Effectively, the regret of StroquOOL scales with n/b 2 -1/(d+2) . Note that b is any real non-negative number and it is unknown to StroquOOL. To achieve this result, and contrarily to HOO, StoSOO, or POO, we designed StroquOOL without using upper-confidence bounds (UCBs). Indeed, UCB approaches are overly conservative as they use, in the design of their confidence bound, hard-coded (and often overestimated) upper-bound on b that we denote b. HOO, POO, and StoSOO, would only obtain a similar regret to StroquOOL, scaling with b, when b is known to them, in with case b would be set as b = b. In general, UCB approaches have their regret scaling with (n/ b 2 ) -1/(d+2) . Therefore, the most significant improvement of StroquOOL over HOO, POO, and StoSOO is expected when b b. (it is often set to 1 by default) this is a behavior that one cannot expect from HOO, POO, or StoSOO as they explicitly use confidence intervals based on b. Finally, using UCB approaches with empirical estimation of the variance σ 2 would not circumvent this behavior. Indeed, the UCB in such case is typically of the form σ 2 /T + b/T [START_REF] Maurer | Empirical bernstein bounds and sample variance penalization[END_REF]. Then if b b, the term b/T in the upper confidence bound will force an overly conservative exploration. This prevents having e -Ω(n) when d = 0 and b ≈ 0.

Experiments

We empirically demonstrate how SequOOL and StroquOOL adapt to the complexity of the data and compare them to SOO, POO, and HOO. We use two functions used by prior work as testbeds for optimization of difficult function without the knowledge of smoothness. The first one is the wrappedsine function (S(x), Grill et al., 2015, Figure 3, bottom right) with S(x) .8 . This function has d > 0 for the standard partitioning [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF]. The second is the garland function (G(x), Valko et al., 2013, Figure 4, bottom right) has d = 0 for the standard partitioning [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF]. Both functions are in one dimension, X = R. Our algorithms work in any dimension, but, with the current computational power available, they would not scale beyond a thousand dimensions.

1 2 (sin(π log 2 (2|x - 1 2 |)) + 1)((2|x -1 2 |) -log .8 -(2|x -1 2 |) -log .3 ) -(2|x -1 2 |) -log
with G(x) 4x(1 -x)( 3 4 + 1 4 (1 -| sin(60x)|)). Function G
StroquOOL outperforms POO and HOO and adapts to lower noise. In Figure 3 Regrets of SequOOL and StroquOOL have exponential decay when d = 0. In Figure 4, we test in the deterministic feedback case with SequOOL, StroquOOL, SOO and the uniform strategy on the garland function (left) and the wrap-sine function (middle). Interestingly, for the garland function, where d = 0, SequOOL outperforms SOO and displays a truly exponential regret decay (y-axis is in log scale). SOO appears to have the regret of e - √ n . StroquOOL which is expected to have a regret e -n/ log 2 n lags behind SOO. Indeed, n/ log 2 n exceeds √ n for n > 10000, for which the result is beyond the numerical precision. In Figure 4 (middle), we used the wrapped-sine. While all algorithms have similar theoretical guaranties since here d > 0, SOO outperforms the other algorithms.

A more thorough empirical study is desired. Especially we would like to see how our methods compare with state-of-the-art black-box GO approaches (Pintér, 2018;Pintér et al., 2018;[START_REF] Strongin | Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms[END_REF][START_REF] Yaroslav | Introduction to global optimization exploiting space-filling curves[END_REF]Sergeyev andKvasov, 2017, 2006;[START_REF] Yaroslav | Global one-dimensional optimization using smooth auxiliary functions[END_REF][START_REF] Lera | An information global minimization algorithm using the local improvement technique[END_REF][START_REF] Kvasov | Lipschitz gradients for global optimization in a onepoint-based partitioning scheme[END_REF][START_REF] Lera | Deterministic global optimization using space-filling curves and multiple estimates of lipschitz and hölder constants[END_REF][START_REF] Kvasov | Deterministic approaches for solving practical blackbox global optimization problems[END_REF]. Appendix A. Regret analysis of SequOOL for deterministic feedback Lemma 4 For any global optimum x with associated (ν, ρ) as defined in Assumption 1, for C > 1, for any depth that h ∈ [h max ], if h max /h ≥ Cρ -d(ν,C,ρ)h , we have ⊥ h = h with ⊥ 0 = 0.

Proof We prove Lemma 4 by induction in the following sense. For a given h, we assume the hypotheses of the lemma for that h are true and we prove by induction that ⊥ h = h for h ∈ [h]. 1 • For h = 0, we trivially have ⊥ h ≥ 0. 2 • Now consider h > 0 and assume ⊥ h -1 = h -1 with the objective to prove ⊥ h = h . Therefore, at the end of the processing of depth h -1, during which we were opening the cells of depth h -1 we managed to open the cell (h -1, i h -1 ) the optimal node of depth h -1 (i.e., such that

x ∈ P h -1,i h -1
). During phase h , the hmax h cells from P h ,i i with highest values f h ,i i are opened. For the purpose of contradiction, let us assume ⊥ h = h -1 that is P h ,i h is not one of them. This would mean that there exist at least hmax h cells from P h ,i i , distinct from P h ,i h , satisfying -d(ν,C,ρ)h . This contradicts f being of near-optimality dimension d(ν, C, ρ) with associated constant C as defined in Definition 1. Indeed the condition N h (3νρ h ) ≤ Cρ -dh in Definition 1 is equivalent to the condition N h (3νρ h ) ≤ Cρ -dh as N h (3νρ h ) is an integer.

f h ,i ≥ f h ,i h . As f h ,i ≥ f (x ) -νρ h by
≥ Cρ -d(ν,C,ρ)h ≥ Cρ -d(ν,C,ρ)h . It follows that N h (3νρ h ) > Cρ
Theorem 5 Let W be the standard Lambert W function (Section 2). For any function f , one of its global optima x with associated (ν, ρ), C > 1, and near-optimality dimension d = d(ν, C, ρ), we have, after n rounds, the simple regret of SequOOL is bounded as follows:

• If d = 0, r n ≤ νρ 1 C n log n . • If d > 0, r n ≤ νe -1 d W d log(1/ρ) C n log n .
Corollary 6 If d > 0, assumptions in Theorem 5 hold and n n/log n d log(1/ρ)/C > e,

r n ≤ ν n log( n) -1 d .
Proof Let x be a global optimum with associated (ν, ρ). For simplicity, let d = d(ν, C, ρ). We have

f (x(n)) (a) ≥ f ⊥ hmax +1,i (b) ≥ f (x ) -νρ ⊥ hmax +1 .
where (a) is because x(⊥ hmax + 1, i ) ∈ T and x(n) = arg max P h,i ∈T f h,i , and (b) is by Assumption 1. Note that the tree has depth h max + 1 in the end. From the previous inequality we have

r n = sup x∈X f (x) -f (x(n)) ≤ νρ ⊥ hmax +1
. For the rest of the proof, we want to lower bound ⊥ hmax . Lemma 4 provides a sufficient condition on h to get lower bounds. This condition is an inequality in which as h gets larger (more depth) the condition is more and more likely not to hold. For our bound on the regret of SequOOL to be small, we want a quantity h so that the inequality holds but having h as large as possible. So it makes sense to see when the inequality flip signs which is when it turns to equality. This is what we solve next. We solve Equation 2 and then verify that it gives a valid indication of the behavior of our algorithm in term of its optimal h. We denote h the positive real number satisfying h max h = Cρ -dh .

(2)

First we will verify that h is a reachable depth by SequOOL in the sense that h ≤ h max . As ρ < 1, d ≥ 0 and h ≥ 0 we have ρ -dh ≥ 1. This gives Cρ -dh ≥ 1. Finally as hmax h = Cρ -dh , we have h ≤ h max .

If

d = 0 we have h = h max /C. If d > 0 we have h = 1 d log(1/ρ) W (h max d log(1/ρ)/C
) where W is the standard Lambert W function. Using standard properties of the • function, we have

h max h ≥ h max h = Cρ -dh ≥ Cρ -d h . (3)
We always have

⊥ hmax ≥ 0. If h ≥ 1, as discussed above h ∈ [h max ], therefore ⊥ hmax ≥ ⊥ h , as ⊥ • is increasing. Moreover ⊥ h = h
r n ≤ νρ ⊥ hmax +1 ≤ νρ h +1 = νρ hmax C +1 ≤ νρ hmax C = νρ 1 C n log n . If d > 0 r n ≤ νρ ⊥ hmax +1 ≤ νρ 1 d log(1/ρ) W hmaxd log(1/ρ) C
. To obtain the result in Corollary 6, we use that W (x) verifies for x ≥ e, W (x) ≥ log x log x [START_REF] Hoorfar | Inequalities on the lambert w function and hyperpower function[END_REF]. Therefore, if

h max d log(1/ρ)/C > e we have, denoting d ρ = d log(1/ρ), r n ν ≤ ρ 1 dρ log hmaxdρ/C log(hmaxdρ/C) = e 1 d log(1/ρ)   log   hmaxdρ/C log hmaxdρ C     log(ρ) =   h max d ρ /C log hmaxdρ C   -1 d .
Appendix B. StroquOOL is not using a budget larger than n

Summing over the depths except the depth 0, StroquOOL never uses more evaluations than the budget h max log 2 (h max ) during this depth exploration as

hmax h=1 hmax/h p=0 h max hp ≤ hmax h=1 hmax/h p=0 h max hp = hmax h=1 h max h hmax/h p=0 1 p = hmax h=1 h max h log( h max /h ) ≤ log(h max ) hmax h=1 h max h = h max log 2 (h max ).
We need to add the additional evaluations for the cross-validation at the end, -d(ν,C,ρ)h , that ⊥ h,p = h with ⊥ 0,p 0.

Proof We place ourselves on event ξ δ defined in Lemma 12 and for which we proved that P (ξ δ ) ≥ 1δ. We fix p. We prove the statement of the lemma, given that event ξ δ holds, by induction in the following sense. For a given h and p, we assume the hypotheses of the lemma for that h and p are true and we prove by induction that ⊥ h ,p = h for h ∈ [h]. 1 • For h = 0, we trivially have that ⊥ h ,p ≥ 0. 2 • Now consider h > 0, and assume ⊥ h -1,p = h -1 with the objective to prove that ⊥ h ,p = h . Therefore, at the end of the processing of depth h -1, during which we were opening the cells of depth h -1 we managed to open the cell P h -1,i h -1 with at least 2 p evaluations. P h -1,i h -1 is the optimal node of depth h -1 (i.e., such that x ∈ P h -1,i ,ρ)h . This leads to having a contradiction with the function f being of near-optimality dimension d(ν, C, ρ) as defined in Definition 1. Indeed, the condition N h (3νρ h ) ≤ Cρ -dh in Definition 1 is equivalent to the condition N h (3νρ h ) ≤ Cρ -dh as N h (3νρ h ) is an integer. Reaching the contradiction proves the claim of the lemma.

h ,i + νρ h ≥ f h ,i + νρ h (a) ≥ f h ,i + b log(2n 2 /δ) 2 p+1 (b) ≥ f h ,i ≥ f h ,i h (b) ≥ f h ,i h -b log(2n 2 /δ) 2 p+1 (a) ≥ f h ,i h -νρ h ≥ f h ,i h -νρ h ,
p ≥ Cρ -d(ν,C,ρ)h ≥ Cρ -d(ν,C,ρ)h . It follows that N h (3νρ h ) > Cρ -d(ν,C
with probability at least 1δ, if b ≤ νρ h / log(2n 2 /δ), the simple regret of StroquOOL obeys

• If d = 0, r n ≤ 3νρ 1 4C n/2 (log 2 (n)+1) 2 . • If d > 0, r n ≤ 3νe -1 d W n/2 (log 2 n+1) 2 d log 1 ρ 4C
.

Proof [Proof of Theorem 8 and Theorem 10] We first place ourselves on the event ξ defined in Lemma 12 and where it is proven that P (ξ) ≥ 1δ. We bound the simple regret of StroquOOL on ξ. We consider a global optimum x with associated (ν, ρ). For simplicity we write d = d(ν, C, ρ).

We have for all p ∈ [0 :

p max ] f (x(n)) + b log(2n 2 /δ) h max (a) ≥ f (x(n)) (c) ≥ f (x(n, p)) (b)
≥ f (x(⊥ hmax,p + 1, i )) From the previous inequality we have r n = f (x )f (x(n)) ≤ νρ ⊥ hmax,p +1 + 2b log(2n 2 /δ) hmax , for p ∈ [0 : p max ].

For the rest of proof we want to lower bound max p∈[0:pmax] ⊥ hmax,p . Lemma 7 provides some sufficient conditions on p and h to get lower bounds. These conditions are inequalities in which as p gets smaller (fewer samples) or h gets larger (more depth) these conditions are more and more likely not to hold. For our bound on the regret of StroquOOL to be small, we want quantities p and h where the inequalities hold but using as few samples as possible (small p) and having h as large as possible. Therefore we are interested in determining when the inequalities flip signs which is when they turn to equalities. This is what we solve next. We denote h and p the real numbers satisfying h max ν 2 ρ 2 h 4 hb 2 log(2n 2 /δ) = Cρ -d h and b log(2n 2 /δ) 2 p = νρ h .

(5)

Our approach is to solve Equation 5 and then verify that it gives a valid indication of the behavior of our algorithm in term of its optimal p and h. We have

h = 1 (d + 2) log(1/ρ) W ν 2 h max (d + 2) log(1/ρ) 4Cb 2 log(2n 2 /δ)
where standard W is the Lambert W function. However after a close look at the Equation 5, we notice that it is possible to get values p < 0 which would lead to a number of evaluations 2 p < 1. This actually corresponds to an interesting case when the noise has a small range and where we can expect to obtain an improved result, that is: obtain a regret rate close to the deterministic case. This low range of noise case then has to be considered separately. and 7 in the high-noise regime and because of Equations 8 and 9 in the low-noise regime, and, in general, ḧ ∈ h max /2 p and p ∈ [0 : p max ]. So in general we have ⊥ hmax/2 p , p ≥ ḧ .

We can now bound the regret in the two regimes.

High-noise regime In general, we have, on event ξ, r n ≤ νρ While in the deterministic feedback case, the regret was scaling with d when d ≥ 0, in the stochastic feedback case, the regret scale with d + 2. This is because the uncertainty due to the presence of noise diminishes as n -1 2 when we collect n observations. Moreover, as proved by [START_REF] Hoorfar | Inequalities on the lambert w function and hyperpower function[END_REF], the Lambert W (x) function verifies for x ≥ e, W (x) ≥ log x log x . Therefore, if ν 2 hmax(d+2) log(1/ρ)

Results in Expectation

We want to obtain additionally, our final result as an upper bound on the expected simple regret Er n . Compared to the results in high probability, the following extra assumption that the function f is bounded is made: For all x ∈ X , |f (x)| ≤ f max . Then δ is set as δ = 4b fmax √ n . We bound the expected regret now discriminating on whether or not the event ξ holds. We have

Er n ≤ (1 -δ)   νρ ⊥ hmax, p+1 + 2b log(f max n 5/2 /b) h max   + δ × f max ≤ νρ ⊥ hmax,

  [a : c] = {a, a + 1, . . . , c} with a, c ∈ N, a ≤ c, and [a] = [1 : a]. Next, log d denotes the logarithm in base d, d ∈ R. Without a subscript, log is the natural logarithm in base e.

Figure 1 :

 1 Figure 1: The SequOOL algorithm

Corollary 6

 6 If d > 0, assumptions in Theorem 5 hold and n n/log n d log(1/ρ)/C > e, r n ≤ ν n log( n) Discussion for the deterministic feedback Comparison with SOO SOO and SequOOL are both for deterministic optimization without knowledge of the smoothness. The regret guarantees of SequOOL are an improvement over SOO. While when d > 0 both algorithms achieve a regret O n -1/d , when d = 0, the regret of SOO is O(ρ √ n )

4.

  Noisy optimization with adaptation to low noise 4.1. The StroquOOL algorithm Parameters: n, P = {P h,i } Init: Open h max times cell P 0,1 .

Figure 3 :

 3 Figure 3: Bottom right: Wrapped-sine function (d > 0). The true range of the noise b and the range used by HOO and POO is b. Top: b = 0, b = 1 left -b = 0.1, b = 1 middleb = b = 1 right. Bottom: b = b = 0.1 left -b = 1, b = 0.1 middle.

Figure 4 :

 4 Figure 4: Left & center: Deterministic feedback. Right: Garland function for which d = 0.

  , we report the results of StroquOOL, POO, and HOO for different values of ρ. As detailed in the caption, we vary the range of noise b and the range of noise b used by HOO and POO. In all our experiments, StroquOOL outperforms POO and HOO. StroquOOL adapts to low noise, its performance improves when b diminishes. To see that, compare top-left (b = 0), top-middle (b = .1), and top-right (b = 1) subfigures. On the other hand, POO and HOO do not naturally adapt to the range of the noise: For a given parameter b = 1, the performance is unchanged when the range of the real noise varies as seen by comparing again top-left (b = 0), top-middle (b = .1), and top-right (b = 1). However, note that POO and HOO can adapt to noise and perform empirically well if they have a good estimate of the range b = b as in bottom-left, or if they underestimate the range of the noise, bb, as in bottom-middle. In Figure5, we report similar results on the garland function. Finally, StroquOOL demonstrates its adaptation to both worlds in Figure4(left), where it achieves exponential decreasing loss in the case d = 0 and deterministic feedback.

Figure 5 :

 5 Figure 5: Garland function: The true range of the noise is b and the range of noise used by HOO and POO is b and they are set as top: b = 0, b = 1 left -b = 0.1, b = 1 middleb = 1, b = 1 right, bottom: b = 0.1, b = 0.1 left -b = 1, b = 0.1 middle.

  f (x(⊥ hmax,p + 1, i ))b log(2n 2 /δ) h max (d) ≥ f (x )νρ ⊥ hmax,p +1b log(2n 2 /δ) h maxwhere (a) is because the x(n, p) are evaluated h max times at the end of StroquOOL and because ξ holds,(b) is because x ⊥ hmax,p +1,i ∈ {(h, i) ∈ T , T h,i ≥ 2 p } and x(n, p) = arg max P h,i ∈T ,T h,i ≥2 p f h,i , (c) is because x(n) = arg max {x(n,p),p∈[0:pmax]}f (x(n, p)), and (d) is by Assumption 1.

≤

  4C log(2n 2 /δ) > e we have, denoting d = (d + 2) log(1/ρ), r n -2b log(2n 2 /δ2νρ h ≤ 2νρ h . Therefore r n ≤ νρ ⊥ hmax,p +1 + 2b log(2n 2 /δ) hmax ≤ 3νρ h . Discriminating between d = 0 and d > 0 leads to the claimed results.

  Assumption 1, this means we have N h (3νρ h ) ≥ (the +1 is for P h ,i h ). As h ≤ h this gives hmax

	hmax h hmax h	+ 1 h +1. However by assumption of the lemma we have hmax ≥ hmax h and therefore N h (3νρ h ) ≥ h

  because of Lemma 4 which assumptions are verified because of Equation 3 and h ∈ [0 : h max ]. So in general we have ⊥ hmax ≥ h . If d = 0 we have,

  Therefore, in total the budget is not more than n 2 + n 4 + h max = n. that h ∈ [h max ], and p ∈ [0 : log h max /h ], we have that if b log(2n 2 /δ)/2 p+1 ≤ νρ h and if h max /(4h2 p ) ≥ Cρ

	pmax p=0	1 2	n 2(logn + 1) 2 ≤	n 4	•

  ). Let m be the largest integer such that 2 p ≤ hmax 2h m . We have hmax 2h m ≤ hmax h m and also 2 p ≥ hmax 2h (m+1) ≥ hmax 4h m . During phase h , the m cells from P h ,i with highest values f (x h ,i ) ≥ 2 p are opened at least hmax h m ≥ 2 p times. For the purpose of contradiction, let us assume that P h ,i h is not one of them. This would mean that there exist at least m cells from P h ,i , distinct from P h ,i h , satisfying f h ,i ≥ f h ,i h and each having been evaluated at least 2 p times. This means that, for these cells we have f

	h ,i	and having been evaluated at least
	hmax
	h m

Proceedings of Machine LearningResearch vol 98:1-23, 2019

The proof is even redundantly written twice for StroquOOL and SequOOL for completeness

[START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] define d(ν, C, ρ) with the constant 2 instead of 3. 3 eases the exposition of our results.

A similar behavior is also achieved by combining two SOO algorithms, by running half of the samples for d = 0 and half for d > 0. However, SequOOL does this naturally and gets a better rate when d = 0.

Again, this is only for the intuition, the algorithm is not a meta-algorithm over SequOOL(p)s.

Note that the second term in our bound has at most the same rate as the first one.

Acknowledgements

We would like to thank Jean-Bastien Grill for his code and Côme Fiegel for helpful discussions and proof reading. We gratefully acknowledge the support of the NSF through grant IIS-1619362 and of the Australian Research Council through an Australian Laureate Fellowship (FL110100281) and through the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS). The research presented was also supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, Inria and Otto-von-Guericke-Universität Magdeburg associated-team north-european project Allocate, and French National Research Agency projects ExTra-Learn (n.ANR-14-CE24-0010-01) and BoB (n.ANR-16-CE23-0003). This research has also benefited from the support of the FMJH Program PGMO and from the support to this program from Criteo.

Appendix C. Lower bound on the probability of event ξ δ

In this section, we define and consider event ξ δ and prove it holds with high probability.

Lemma 12 Let C be the set of cells evaluated by StroquOOL during one of its runs. C is a random quantity. Let ξ δ be the event under which all average estimates in the cells receiving at least one evaluation from StroquOOL are within their classical confidence interval, then P (ξ δ ) ≥ 1δ, where

Proof The proof of this lemma follows the proof of the equivalent statement given for StoSOO [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF]. The crucial point is that while we have potentially exponentially many combinations of cells that can be evaluated, given any particular execution we need to consider only a polynomial number of estimators for which we can use Chernoff-Hoeffding concentration inequality.

Let m denote the (random) number of different nodes sampled by the algorithm up to time n. Let τ 1 j be the first time when the j-th new node P H j ,I j is sampled, i.e., at time τ 1 j -1 there are only j -1 different nodes that have been sampled whereas at time τ 1 j , the j-th new node P H j ,I j is sampled for the first time. Let τ s j , for 1 ≤ s ≤ T H j ,I j (n), be the time when the node P H j ,I j is sampled for the s-th time. Moreover, we denote Y s j = y τ s jf (x H j ,I j ). Using this notation, we rewrite ξ as:

Now, for any j and p, the (Y s j ) 1≤s≤u are i.i.d. from some distribution P H j ,I j . The node P H j ,I j is random and depends on the past samples (before time τ 1 j ) but the (Y s j ) s are conditionally independent given this node and consequently:

using Chernoff-Hoeffding's inequality. We finish the proof by taking a union bound over all values of 1 ≤ j ≤ n and 1 ≤ p ≤ p max .

Appendix D. Proof of Lemma 7

Lemma 7 For any global optimum x with associated (ν, ρ) from Assumption 1, any C > 1, for any δ ∈ (0, 1), on event ξ δ defined in Lemma 12, for any pair (h, p) of depths h, and integer p such

Theorem 10 Low-noise regime After n rounds, for any function f and one of its global optimum x with associated (ν, ρ), any C > 1, and near-optimality dimension simply denoted d = d(ν, C, ρ), Therefore, we distinguish two cases which corresponds to different noise regimes depending on the value of b. Looking at the equation on the right of (5), we have that p < 0 if

Based on this condition we now consider the two cases. However for both of them we define some generic ḧ and p.

High-noise regime

and,

Low-noise regime

In this case, we can reuse arguments close to the argument used in the deterministic feedback case in the proof of SequOOL (Theorem 5), we denote ḧ = h and p = p where h and p verify,

If

where standard W is the standard Lambert W function. Using standard properties of the • function, we have

where (a) is because of the following reasoning. First note that one can assume b > 0 as for the case b = 0, the Equation 9 is trivial. As we have hmaxν 2 ρ 2 h 4 hb 2 log(2n 2 /δ) = Cρ -d h and

From the inequality hmax 4 h < Cρ -d h and the fact that h corresponds to the case of equality hmax 4h = Cρ -dh , we deduce that h ≤ h, since the left term of the inequality decreases with h while the right term increases. Having h ≤ h gives ρ h ≥ ρ h .

Given these particular definitions of ḧ and p in two distinct cases we now bound the regret. First we will verify that ḧ is a reachable depth by StroquOOL in the sense that ḧ ≤ h max and p ≤ log 2 (h max /h) for all h ≤ ḧ. As ρ < 1, d ≥ 0 and ḧ ≥ 0 we have ρ -d ḧ ≥ 1. This gives Cρ -d ḧ ≥ 1. Finally as hmax ḧ2 p = Cρ -d ḧ, we have ḧ ≤ h max /2 p. Note also that from the previous equation we have that if ḧ ≥ 1, p ≤ log 2 (h max /h) for all h ≤ ḧ . Finally in both regimes we already proved that p ≥ 0.

We always have ⊥ hmax, p ≥ 0. If ḧ ≥ 1, as discussed above ḧ ∈ [h max ], therefore ⊥ hmax, p ≥ ⊥ ḧ , p , as ⊥ •, p is increasing for all p ∈ [0, p max ]. Moreover on event ξ, ⊥ ḧ , p = ḧ because of Lemma 7 which assumptions on ḧ and p are verified because of Equations 6


Yasamin Eslami

Michele Dassisti

Hervé Panetto

Mario Lezoche

Sustainability assessment of manufacturing organizations

Keywords: Sustainability Assessment, Sustainable Organization, Indicator-Based Sustainability Assessment, Formal Concept Analysis

published or not. The documents may come

Introduction

Companies across the world are facing with elevated expectations of customers on one hand and increasing prices for materials, energy and compliance on the other. Therefore, the sustainability target seems to become a vital opportunity and has changed face from a show-off achievement to a competitive imperative and a must-have in today's market. However, the pressure made the manufacturing organizations think about ways, tools and methodologies to assess the level of sustainability in the whole manufacturing system. Therefore, it is safe to say that Sustainable Assessment of manufacturing operations is one of the essentials of sustainable development in an organization. The concept of sustainability assessment is introduced to offer new perspectives to impact assessment geared toward planning and decision making on sustainable development [START_REF] Hacking | A framework for clarifying the meaning of Triple Bottom-Line, Integrated, and Sustainability Assessment[END_REF]. sustainability assessment is defined as a methodology that can help decisionmakers and policy-makers decide what actions they should take and should not take in an attempt to make society more sustainable [START_REF] Hardi | The Bellagio principles for assessment. Assessing sustainable development: Principles in practice[END_REF]. Sustainability Assessment (SA) is known to be a complex task and conducted for supporting decision making and policy in a broad environmental, economic and social context [START_REF] Sala | A systemic framework for sustainability assessment[END_REF]. Various methods of assessment have been accomplished through the literature so far, trying to find a way for companies to assess their sustainability state, help the companies choose between sustainable solutions, define and solve problems on the way to sustainability and identify potential solutions. Among all methods, assessment through adopting indicators are increasingly recognized and it is known to be a tool for policymakers to convey performance information in environmental, economic, social and development field [START_REF] Nardo | State-of-the-art report on simulation and indicators[END_REF]. Sustainable development indicators, in general, can serve to assess and evaluate the performance, provide trends on improvements plus warnings in case the corporate is facing a drop off in features of sustainability and provide information to decision makers [START_REF] Lundin | Indicators for Measuring the Sustainability of Urban Water Systems -A Life Cycle Approach[END_REF][START_REF] Mayer-Spohn | Sustainable development indicators within the German water industry: a case study[END_REF]. Therefore, the choice of indicators inside organizations can represent the priorities of the organization and to define strategic and political goals as well as its objectives [START_REF] Corbire-Nicollier | Towards a global criteria-based framework for the sustainability assessment of bioethanol supply chains: Application to the Swiss dilemma: Is local produced bioethanol more sustainable than bioethanol imported from Brazil?[END_REF]. Accordingly, the aim of this study is to get deep into the definition of the indicators applied for sustainability assessment to pave the path to the comparison of organizations on their strategies toward assessing their sustainability status. To serve this purpose, an analysis has been conducted on the sustainability reports of 100 manufacturing organizations and a Formal Concept analysis (FCA) was run on the results to get deep into the definition and choice of indicators by the organizations. The rest of the paper will discuss the analysis procedure and its sample. Furthermore, the FCA results will be discussed. Finally, the conclusion and the future work is presented.

Analysis

The abundance of the sustainability indicators created a huge confusion for manufacturers when it comes to indicators selection and sustainability assessment [START_REF] Joung | Categorization of indicators for sustainable manufacturing[END_REF]. In order to increase the reliability and effectiveness of the indicators, several standard sets, guidelines and frameworks have been introduced by international initiatives. To serve the purpose of the study, an analysis on sustainability reports of organizations which use a defined and standard set of indicators needs to be run. A study of the existing sets of indicators is here performed to clarify the differences between the sets and raising the awareness on the applicability and adjustability of the indicators. The study, as represented in the following, will be led to choosing a standardized set of indicators.

Review of the Standard Sets of Indicators

In the literature, standard sets of indicators are presented. For the present work, the sets were studied and analysed according to the fulfilment of the following criteria: 1) Level of Application: As the aim of the study clearly stated, the assessment needs to be done throughout the whole organization. Therefore, the tools which are not applicable or adaptable for the factory levels were excluded from the study. 2) Cross-Industry Comparison: The chosen set of indicators needs to have generic applicability to enable the decision makers to make a comparison between various organization without limitation. Thus, the product/process-specific sets limit the general use of the proposed study.

3) Holistic View over Sustainability: as mentioned before, the assessment of progress toward sustainable development should consider the well-being of social, ecological, and economic sub-systems, the tools which are specified on just one feature, i.e. environmentally focused ones, might limit the assessment in the proposed study and will not be considered.

As shown in table 1, tools like GRI, NIST and LCSP appear to meet all our needs. However, NIST is not an open source set of Indicator anymore and LCSP considers a limited and generalized assessment. Therefore, GRI seemed to be an effective selection of standard indicators based on the needs of the study. Indicators of GRI which are related to the three dimensions of sustainability are available through the website ( https://www.globalreporting.org/standards/gri-standards-download-center/)

2.2

The Sample of 100 Organizations Among the verified sustainability assessment reports available on the website (https://www.globalreporting.org/reportregistration/verifiedreports# ), the first 100 manufacturing ones related to the years 2016 and 2017 were chosen regardless of the size, country and the field of activity. The reports were all inspected for GRI indicators they encompass in three traditional sustainability dimensions: economic, environmental and social.

FCA on GRI indicators

As previously indicated, the organization's reports were studied and the GRI indicators related to the three traditional sustainability dimensions were scrutinized. Then, each dimension was analysed separately with the help of Formal Concept Analysis (FCA). Formal Concept Analysis (FCA) as a clustering technique was chosen to assist the interpretation of the indicators used for sustainability assessment within the organizations. FCA is a branch of lattice theory [START_REF] Wille | Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[END_REF] and it is best used for knowledge representation, data analysis and information management. It detects conceptual structures in data and consequently extraction of dependencies within the data by forming a collection of objects and their properties [START_REF] Mezni | Multi-cloud service composition using Formal Concept Analysis[END_REF][START_REF] Wajnberg | Complex system tacit knowledge extraction trough a formal method[END_REF]. FCA is able to visualize and represent knowledge by exploring the relationship between objects and is known to be effective for data analysis and association rule extraction [START_REF] Li | Method for generating decision implication canonical basis based on true premises[END_REF][START_REF] Yan | Formal concept analysis and concept lattice: Perspectives and challenges[END_REF].

Based on the set of data given by FCA, GRI indicators were categorized in a formal context in which the regularity of the indicators' choice by the organizations was shown. Having Access to these kinds of result, made it possible to analyses the tendency of the organizations toward the definition of sustainability knowing what indicators have been adopted the most and with what frequency in each dimension. Consequently, the most practiced combinations of the indicators were shown. However, for only one dimension like environmental, more than 15000 combinations were exposed. The wide range in the formal context and the limitation of the space, restricted the present study only upon results of the application of the indicators alone and in two-indicator combinations that are shown in figures 1,2 and 3.

In each figure, solo indicators are shown as circles whose size varies based on the number of the organizations that have applied them in the analysis. Therefore, the bigger the circles are, the more frequent the indicators appeared in the analysis. The scale of the size of the circles is fixed, therefore all indicators in all three dimensions are comparable. On the other hand, if the indicator was applied in the sustainability report of the organization in company with another indicator, the two were connected with a line. The thickness of the line shows the frequency of the application of the two indicators in comparison with the rest of the two-combination indicators in the same dimension. In better words, the thicker the connection line is, the more the two connected indicators were used in the assessment process of the organizations. The position of the circles and the length of the connection lines speak for no meaning and are fully accidental.

Results and Discussion

Looking through the economic dimension (figure1), the indicator "direct economic value generated and distributed" (201-1), was ranked as the first with a significant difference from the second one. However, the vast meaning of the indicator can be a justification of its highly ranked application since it contains all three aspects of direct economic value generated (revenues), economic value distributed (operating costs, employee wages and etc) and economic value retained. On the other hand, the rest of the economic indicators are practiced with smaller differences in frequency of the application which can be the representative of the tendency toward interpreting economic sustainability as costs and profit. In addition, the second-most-used indicator was surprisingly "Communication and training about anti-corruption policies and procedures" (205-2) which is known as both a social and economic value in sustainability definition and it was employed more than "Significant indirect economic impacts" (203-2). The other two anti-corruption indicators, (205-3, 205-1) come next and before "other indirect economic impacts" or "procurement practices" that can be a sign of propensity of organizations toward the concept of anti-corruption. Nonetheless, indicators related to "market presence" which seemed to be an interesting topic were positioned at the end of the ranking list. As concerns the combinations, it is clear that the combinations with the indicators related to "direct economic value" and "anti-corruption" (all its three indicators) be the ones with the highest position among all. However, the two-indicator combination of (201-1 and 205-2) stood first with an evident difference from the second one which is the combination thought to be the first: direct and indirect economic value (201-1, 203-2). The observation reconfirms the importance of anti-corruption when it comes to economic sustainability in an organization. Considering the environmental dimension of sustainability (figure2), "Energy Consumption within the organization" which is represented by the indicator (302-1) stood out while the "GHG emission" with two indicators of (305-2) and (305-1) came closely after. However, the difference between the third place (305-1) and the fourth (307-1) and forward is clearly notable. On the other hand, it is observed that most of the indicators at the top of the ranking are the ones related to topics of "energy" (energy consumption, energy intensity, reduction of energy consumption, etc) and "GHG emissions" (Direct and Indirect GHG emission, GHG intensity, Reduction of GHG emission, etc) which displays the most representative concepts of environmental sustainability in the organizations. Indicators covering "waste management" like (306-2), (306-1) and the ones for the "water" like (303-1) were among the highest ranked ones which put an emphasis on the importance of this categories on the concept of environmental sustainability in an organization. However, indicators like (301-2), (304-1), (304-3) relating to the categories of "material" and "biodiversity" were placed at the bottom of the list but it does not imply a lack of importance or their ineffectiveness toward sustainability since the shortage can be related to the field of the organizations participated in the analysis. The combination of direct and indirect GHG emissions and their combination with energy consumption within the organization were the most used ones as it was expected. However, although waste management was not the at the top of the list of solo indicators, its combination with GHG emission came rather high in the ranking.

Inspecting the social dimension(figure3), the most noticeable fact is the closeness of the frequency of the indicators and also how repetitive the thickness of the lines is which itself can express that how selective the social dimension is, and the choice can thoroughly differ based on the objective of an organization. However, it is seen that three indicators which deal with "employees", "diversity and equal opportunities" and "injuries" were the ones with the most concentration on with negligible differences. Nevertheless, the indicator (401-1) which stood at the top of the list, covers the new employees and their turnover, gender, age and region, so it is relatively vast in terms of what it covers regarding the characteristics of employees. The same goes for the next indicator, (403-2), which examines the "occupational health and safety" inside the organization and it encompasses types of injury, injury rate (IR), occupational disease rate (ODR), lost day rate (LDR), absentee rate (AR), and work-related fatalities, for all employees, with a breakdown by gender and region. On the other hand, the next topic with a bit of difference in frequency is "training and education". Yet, these prominent topics reveal the importance of the employees, their safety and health and non-discrimination in terms of employment in reaching sustainability from a social point of view. In addition to these topics, indicators representing social screening of suppliers (414-1), incidents of non-compliance with laws and regulation (419-1), and operations with local community engagement (413-1) also attracted a good deal of attention to themselves. Subsequently, looking through the combination of the indicators, it can be detected that employees and their related issues are the ones that are the most depictive of social sustainability in an organization.

As seen above, the economic and environmental indicators, seem to be more straightforward than the social ones. In other words, unlike economic and environmental, no indicator can be strictly called as the representative of the social dimension. all indicators have been chosen to reach sustainability in the manufacturing organization while the difference in the frequency of the choice is almost negligible. The approach the organizations took toward social sustainability, can speak for the irregularity in defining sustainability from the social point of view while the other two dimensions are mostly approached the same.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Economic GRI Indicators

Fig. 3 .

 3 Fig. 3. Social GRI Indicator

Table 1 .

 1 Indicators' set review

					Holistic
	Indicator set	Description	Reference	Level of Application	Social	View Environmental	Economic	Cross-Industry Comparison
	GRI	Global Reporting Initiatives	[14] Organization Level	Y Y	Y	•
	DJSI	Dow Jones Sustainability Index	[15] Organization Level	N N	Y	▲
	ISO 14031		[16] Organization Level	Y Y	Y	○
	IChemE	The institution of Chemical En-gineering	[17] factory Level	Y Y	Y	○
	LCSP	The Lowell Centre for Sustain-able Production	[18] Organization level	Y Y	Y	•
	UNCSD	UN Commission on Sustainable Development	[19] Country Level Y Y	Y	•
	FPSI	Ford of Europe's Product Sus-tainability Index	[20] Product Level	Y Y	Y	○
	GM MSM	General Motors Metrics for Sustainable Manufacturing	[21] Product Level	Y Y	Y	▲
		National Institute of Standard	[22] Organiza-
	NIST	and Technology Sustainable Manufacturing Indicator Repos-		tion/Pro-cess/Product	Y Y	Y	•
		itory		Level
		Organization for Economic Co-	[23]
	OECD	Operation and Development (OECD) Sustainable Manufac-		organization level	N Y	N	•
		turing Toolkit

Note: Y=YES; N=NO; • = Covered; ▲= Covered with the limitation ; ○ = Not Covered

Conclusion and Future Work

The paper focuses on indicator-based sustainability assessment in manufacturing organizations and tries to scrutinize the meaning of the choice of indicators by the organizations. The study starts with a survey on available indicators set provided for sustainability assessment to choose the most responsive one according to the defined criteria. Among all sets, GRI was elected as the indicator source of the assessment throughout the organizations. Furthermore, 100 organizations were inspected on their choice of GRI indicators for assessing their sustainability status. The result of the analysis was then interpreted by Formal Concept Analysis (FCA) to investigate the strategies of the organizations toward sustainability and help decision makers define a more sustainable strategy for the organization considering the trends. Nevertheless, the future work of the present study can focus on comparing the painted picture of sustainability by the manufacturers to the assumed concept of sustainability delineated in the literature.