Jérémie Decock
email: jeremie.decock@inria.fr

Olivier Teytaud
email: olivier.teytaud@inria.fr

Noisy Optimization Complexity Under Locality Assumption

Keywords: G.1.6 [Mathematics of Computing]: Numerical Analysis-Optimization Noisy optimization, black box complexity model, local sampling

In spite of various recent publications on the subject, there are still gaps between upper and lower bounds in evolutionary optimization for noisy objective function. In this paper we reduce the gap, and get tight bounds within logarithmic factors in the case of small noise and no long-distance influence on the objective function.

INTRODUCTION

Noisy optimization is the optimization of stochastic objective functions, i.e. the objective value f (x, ω) depends on x and on a random variable ω. Equivalently, f (x) is a random variable distributed as f (x, ω). Often (yet not always, as risk considerations can be involved), the goal is to optimize the expected value, i.e. Eωf (x, ω) where Eω is the expectation with respect to ω. We here work on derivativefree noisy optimization, on a continuous domain D = [0, 1] d ; we assume that the optimum is unique, and the detailed setting below will assume that getting rid of tricky local optima is less important than handling noise properly.

In all the paper, we use Õ(f (n)) as a short notation for O(f (n) log(n)). Section 1.1 presents our framework, and in particular the family of functions on which we show lower bounds (all families including this family are also concerned by the lower bounds). Section 1.2 discusses the context of

Framework

There are many convergence rates known in numerical optimization, depending on assumptions (derivative-free [START_REF] Conn | Recent progress in unconstrained nonlinear optimization without derivatives[END_REF] or not, comparison-based [START_REF] Doerr | Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity[END_REF] or not, global [START_REF] Grünewälder | Regret Bounds for Gaussian Process Bandit Problems[END_REF] or not). Robustness to noise, even early in the origins of evolutionary computation [START_REF] Schwefel | Numerical Optimization of Computer Models[END_REF], is cited as a strength of these algorithms. In spite of this strong interest for noise in evolutionary computation, complexity in the noisy case is less clear, because details on the assumption have a big impact on the performance [START_REF] Beyer | Mutate large, but inherit small ! On the analysis of mutations in (1, λ)-ES with noisy fitness data[END_REF][START_REF] Fitzpatrick | Genetic algorithms in noisy environments, in machine learning: Special issue on genetic algorithms[END_REF][START_REF] Arnold | Local performance of the (1+1)-ES in a noisy environment[END_REF][START_REF] Arnold | Evolution strategies with cumulative step length adaptation on the noisy parabolic ridge[END_REF][START_REF] Hammel | Evolution strategies on noisy functions: How to improve convergence properties[END_REF][START_REF] Fitzpatrick | Genetic algorithms in noisy environments[END_REF]; a main distinction being adaptive noise [START_REF] Jebalia | On multiplicative noise models for stochastic search[END_REF] (with small noise variance around the optimum) and additive noise [START_REF] Teytaud | On the adaptation of the noise level for stochastic optimization[END_REF] (with lower-bounded variance around the optimum). Also, defining convergence rates is more difficult when either the algorithm or the objective function has a random part, because the distance of xn to the optimum x * is not a constant (n being the n th objective function evaluation). Various convergence rates can be defined depending on the precise considered definition of convergence (we will not give too many details on this in this introduction, but our results will state precisely the definitions involved).

For example, the algorithm CLOP [START_REF] Coulom | Clop: Confident local optimization for noisy black-box parameter tuning[END_REF][START_REF] Coulom | Handling expensive optimization with large noise[END_REF] reaches a convergence xnx * = Õ(1/

√ n)on a wide range of symmetric objective functions, using regression; in a very structured case (when the family of functions is very well approximated by a known model), statistical tools (supervised machine learning) provide such fast rates, even on very flat functions.

An other example of algorithm for noisy optimization is R-EDA (Racing-based Estimation of Distribution Algorithm, [START_REF] Rolet | Bandit-based estimation of distribution algorithms for noisy optimization: Rigorous runtime analysis[END_REF][START_REF]Adaptive Noisy Optimization[END_REF]). It considers a different definition of convergence (more on this later).R-EDA was proposed as a typical noisy optimization algorithm, easy to analyze and making a good approximation of real-world approaches [START_REF] Heidrich-Meisner | Uncertainty handling cma-es for reinforcement learning[END_REF]. The noisy optimization framework is described in Algorithm 1 and R-EDA is defined in Algorithm 2. For β > 0, the convergence rate is typically xnx * = Õ(1/n 1/β ) on the family of objective functions

F β,γ = {f x * ,β,γ (x); x * ∈ D} , (1)
where D = [0, 1] d and Here B(p) states for a Bernoulli random variable with parameter p (i.e. equal to 1 with probability p and 0 otherwise). Fig. 1 show the expected values of f x * ,β,γ with respect to x for some set of parameters. We will show in this paper that R-EDA is optimal within logarithmic factors for F β,γ under locality assumptions discussed below and for some values of γ (case with variance linearly decreasing as a function of expected fitness values).

f x * ,β,γ (x) = B γ x -x * √ d β + (1 -γ) . (2)
Algorithm 2 R-EDA: algorithm for optimizing noisy fitness functions. Bernstein denotes a Bernstein race, as defined in Algorithm 3. The initial domain is [x - 0 , x + 0 ] ∈ R D , δ is the confidence parameter. This algorithm goes back to [START_REF] Rolet | Bandit-based estimation of distribution algorithms for noisy optimization: Rigorous runtime analysis[END_REF][START_REF]Adaptive Noisy Optimization[END_REF]. Please note that x - i and x + i are indexed by i, the iteration number, and not by the number of evaluations as in our convergence criteria.

n ← 0 while True do // Pick the coordinate with highest uncertainty cn = arg maxi(x

+ n )i -(x - n )i δ max n = (x + n )c n -(x - n )c n for i ∈ [[1, 3]] do
// Consider the middle point

x ′i n ← 1 2 (x - n + x + n ) // The c th n coordinate may take 3 = values (x ′i n )c n ← (x - n )c n + i-1 2 (x + n -x - n )c n end for (goodn, badn) = Bernstein(x ′1 n , x ′2 n , x ′3 n , 6δ π 2 (n+1) 2 ). // A
ǫ (T ) = 3 log 3π 2 T 2 6δ ′ /T +max i σi 2 log 3π 2 T 2 6δ ′ /T .
(3) until Two points (good ,bad) satisfy f (bad)-f (good) ≥ 2ǫ -return (good, bad)

Symmetry assumptions and information theory

We pointed out above that the Õ(1/ √ n) is possible for algorithms (e.g. CLOP) using models which are very close to the real objective function (for example if we know that the fitness function is a Bernoulli as in Eq. 2). In these algorithms, the sampled point is not necessarily close to the optimum or to the current approximation of the optimum that the algorithm has. This is related to information theory: there are areas in which one gets more information than others, and points minimizing x → Eωf (x, w) are not necessarily the most informative. Typically, when you have a relevant model of the objective function, you will learn more about the optimum by sampling maximum uncertainty points (i.e. points x such that f (x, ω) has high variance), rather than by sampling points close to the optimum. There are therefore two distinct strategies1 :

• sampling close to the current estimation of the optimum;

• sampling maximum uncertainty areas.

As we have already said, getting knowledge on the objective function far from the current approximation of the optimum does not help for finding x * if you have no model of the objective function (at least in a setting without tricky local optima). But, if you have a strong prior on the objective function, you can indeed sample only very far from the current estimation of the optimum, at locations where the objective function is less flat and from this sampling, you get knowledge on x * . Again, this leads to algorithms which sample much more far from the current approximation of the optimum than close to it.

Algorithm 1 Noisy optimization framework. This is not an optimization algorithm; this just explains the framework of noisy optimization with Bernoulli random variables (the fitness function outputs

1 if random (= ωn) is less than Ef x * ,β,γ (x x * ,n,ω,ω ′ )).
Optimize is an optimization algorithm taking as input a sequence of visited points, their binary noisy fitness values and an internal noise. It outputs a new point to be visited, looking for points x of the domain such that f x * ,β,γ (x) is as small as possible.

Input:

ω the uniform noise of f , ω ′ a random seed of the algorithm, x * the optimal point, β and γ two fixed parameters of f . Output:

x x * ,n,ω,ω ′ the estimation of the optimum.

for all n = 1, 2, 3, . . . do

x x * ,n,ω,ω ′ = Optimize(x x * ,1,ω,ω ′ , . . . , x x * ,n-1,ω,ω ′ , y1, . . . , yn-1, ω ′ ) if ωn ≤ Ef x * ,β,γ (x x * ,n,ω,ω ′ ) then yn = 1 else yn = 0 end if end for return x x * ,n,ω,ω ′
These algorithms have two distinct steps:

• Exploration: choosing a point xn for which they want to sample f (xn).

• Recommendation: providing an estimate x * n of arg min Ef . Nevertheless, various compromises are possible (for not relying too much on the model) between strategies relying only on maximum uncertainty (strongly trusting a model) and strategies relying only on sampling close to the estimation of the optimum; [START_REF] Coulom | Handling expensive optimization with large noise[END_REF] is based on methods for choosing to which extent the model should be trusted.

So far, we have discussed the distinction between algorithms which samples close to the estimation of the optimum and those which samples at maximum uncertainty areas. But in this paper we will only consider the fastest theoretical convergence rates for algorithms which samples close to the estimation of the optimum. Formally speaking, we assume the following locality assumption for some 0 < δ < 1/2 and some constant C(d) > 0 depending on d only,

∀f ∈ F, ∀i ≤ n, xi -x * ≤ C(d) i α , (4)
with probability at least 1 -δ/2; α > 0 large implies that there is a fast convergence. This equation depends on n; in fact, the whole work would make sense with n replaced by ∞, but we can show our results for any n sufficiently large, so we keep this assumption under this form (the main theorem will assume this for all n, but results in it are derived for n sufficiently large). Actually, convergence rates could be formalized differently. For example, we might consider that the rate is α if

∀f ∈ F, ∀n, x kn -x * ≤ C(d) kn α . (5)
for some increasing sequence kn. This is a weaker assumption, because only xi such that ∃n; i = kn have a fast rate; other points can be sampled anywhere in the domain without modifying the measure α of the convergence rate. For instance, the following algorithm satisfies Eq. 5 but not Eq. 4, for 0 < α < 1/2:

• define kn = n 2 ;

• if i different from kn for all n, then do exploration (xi is uniformly drawn on the domain);

• otherwise, do exploitation (xi is the maximum likelihood estimate of x * given the xi and their fitness evaluations).

Indeed, this algorithm is quite good for the objective function model that we have chosen (see Eq. 2); but it does not satisfy Eq.4 as some points are sampled far from the optimum. In fact the algorithm above can even be optimized by choosing xi, for exploration, at locations where it is most likely to help finding the optimum (this is active learning); see e.g. [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF][START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF]. Also, sometimes, the xi for exploitation are computed, but not evaluated. When designing a testbed for noisy optimization, this issue makes sense. Many optimization algorithms for noisy settings distinguish xi's which are supposed to be good approximations of the optimum and xi's which are sampled for gathering information about the optimum. If the testbed makes no difference between the two kinds of points, it implicitly assumes that sampling far from the optimum for gathering information is unlikely to be a good method. Rates reachable with no constraints are a well established part of the state of the art [START_REF] Fabian | Stochastic approximation of minima with improved asymptotic speed[END_REF]; we here focus on rates which can be attained when focusing on Eq. 4 as a criterion for convergence. Importantly, this criterion is also relevant when all fitness values sampled are important; e.g. when improving, online, a production unit.

To sum up, the locality assumption (Eq.4) used to obtain our main result means that the algorithm has a given rate if and only if all its search points follow this rate; it is not allowed, for instance, to have one point out of two which is close to the optimum, and another far away in order to get some information which, for some reason, would help for the convergence. In other words, this assumption means that we consider rates that can be reached without relying on long distance correlations between fitness values. This is by no mean a negligible technical detail; as we have already said, there are fast algorithm which rely on sampling far from the optimum; these fast algorithms, however, can only be fast when there is a strong structure on the objective functions so that sampling far away can provide significant improvements on the convergence rate. This paper is devoted to showing bounds on rates for algorithms which do not use such sampling "far" from the current estimate of the optimum.

The results can therefore be viewed with two different complementary conclusions:

• either as the proof that fast rates (faster than the limits obtained in this paper) can only be obtained by sampling also far from the optimum;

• or as the proof that fast rates (faster than the limits obtained in this paper) are only possible for algorithm which assume some strong "flatness" of the objective function around the optimum, and these algorithms will not be so fast if we test them on other objective functions.

Under the locality assumption (Eq. 4), we show that for the family F β,γ of objective functions (γ > 0), α is necessarily less than or equal to 1/β -if the function is very flat around the optimum (β large), the convergence of algorithms sampling close to the optimum (Eq. 4) is necessarily slow (α ≤ 1/β in Eq. 4). On the other hand, for β = 2, local algorithms (like R-EDA) have the same order as the rate reached by machine learning methods, and can even be better for β = 1, reaching Õ(1/n) when β = 1 instead of Õ(1/

√ n) by max-uncertainty sampling.

MODELS AND LEMMAS

Algorithm 1 describes our framework. As introduced in section 1.2 (Eq. 4), we assume, for some 0 < δ < 1/2, the locality assumption

∀f ∈ F, ∀i ≤ n, xi -x * ≤ C(d) i α
with probability at least 1 -δ/2. This contains two important elements:

• there is an Õ(1/n α ) convergence to the optimum;

• there is no sampling far from the current estimate of the optimum.

This implies that the algorithm converges and does not sample far from its limit. As already stated in Eq. 1 and 2, we also consider the family of functions

F = F β,γ = {f x * ,β,γ (x) ; x * ∈ D}, where f x * ,β,γ (x) = B γ xn -x * √ d β + (1 -γ) ,
that is to say the random variable ω is uniform in [0, 1] and

f (x, ω) = 1 if and only if ω ≤ γ xn-x * √ d β + (1 -γ) (f (x, ω) = 0 otherwise).
Equation 2 and the locality assumption (Eq. 4) imply

Ef (x * ) 1-γ ≤ Ef (xn) ≤ Ef (x * ) 1-γ + γ d β/2 C(d) β n αβ ,
with probability at least 1 -δ/2 and where Ef (x) is a short notation for Eωf (x, ω).

The n th function evaluation yn is, by definition, at x x * ,n,ω,ω ′ which depends on x * (which specifies the objective function), ω (which is the sequence of random variables ω of the stochasticity of the objective function), ω ′ (which is the sequence of random choices within the optimization algorithm, which might be stochastic). It also depends on β and γ, but these will be considered as fixed.

For short, we will note Xn,Ω, with Ω = (ω, ω ′ ) the set of all the x x * ,n,ω,ω ′ for all x * , that is to say Xn,Ω is the set of all points which can be chose by the optimization algorithm Optimize for the nth point to sample if we consider a given noise and internal randomness.

To obtain our main result, we first need a combinatorial lemma as follows:

Lemma 1. The cardinality of Xn,Ω is at most 2 N , where N is the cardinality of      1 ≤ i ≤ n ; Ef (x * ) 1-γ ≤ ωi ≤ Ef (x * ) 1-γ + γ d β/2 C(d) β i αβ      .
Proof. xn is deterministic as a function of Ω and of the fitness values; so the possible values of x x * ,n,ω,ω ′ only depend on the 2 N possible values of the yi for i in the set above.

We also need the following Lemma 2. Let N be the cardinality of

1 ≤ i ≤ n ; Ef (x * ) ≤ ωi ≤ Ef (x * ) + γ d β/2 C(d) β i αβ .
Then, N has expectation at most

z = γ d β/2 C(d) β n i=1 i -αβ (6)
and variance also at most z.

which is an immediate consequence of the definition of N . Lemma 2 and Chebyshev's inequality [START_REF] Bienaymé | Considérations à l'appui de la découverte de laplace[END_REF][START_REF] Chebyshev | Sur les valeurs limites des integrales[END_REF][START_REF] Markov | On certain applications of algebraic continued fractions[END_REF] ensure the following lemma:

Lemma 3. Consider δ ∈ [0, 1]. N ≤ z + √ z (δ/2) -1/2
with probability at least 1 -δ/2.

Lemmas 1 and 3 together imply that the cardinality of Xn,Ω is at most [START_REF] Arnold | Local performance of the (1+1)-ES in a noisy environment[END_REF] with probability at least 1 -δ/2.

2 z+ √ z √ δ/2

MAIN RESULTS

Theorem 1. Assume that F is as proposed in Eq. 2 for some 1 > γ > 0 and β > 0. Assume that Eq. 4 (locality assumption) holds for all n ≥ 1, d ≥ 1, and for some

C(d), δ < 1, α > 0, i.e. ∀f ∈ F, ∀i ≤ n, xi -x * ≤ C(d) i α ,
with probability at least 1 -δ/2. Then α ≤ 1/β.

Proof. Let us show that αβ ≤ 1. In order to do so, let us assume, in order to get a contradiction, that αβ > 1; then, knowing convergence of Riemann series for αβ > 1

n i=1 1 i αβ < αβ αβ -1 equation 6 leads to: z ≤ γC(d) β d β/2 αβ αβ -1 if αβ > 1 (8)
Consider any optimization algorithm (stochastic or not). Eq. 8 implies the finiteness of z, and therefore by Eq. 7 the finiteness of Xn,Ω, bounded above by a constant C independent of n, with probability at least 1 -δ/2.

We will here use sets of points with lower bounded distance to each other; such sets are classical in statistics [START_REF] Vaart | Weak Convergence and Empirical Processes[END_REF], and are now also used for building lower bounds based on information theory [START_REF] Teytaud | General lower bounds for evolutionary algorithms[END_REF][START_REF] Fournier | Lower bounds for comparison based evolution strategies using vc-dimension and sign patterns[END_REF].

Consider R a set of cardinality C ′ such that

C ′ C > 1 -δ 2 1 -δ (9)
and such that two distinct elements of R are at distance greater than 2ǫ, with ǫ = C(d)/n α , from each other; such a set certainly exists if n is large enough. A nice property of this set is that if the optimum x * is uniformly drawn in R, then it can only be found with probability 1 -δ/2 and with precision C(d)/n α if Xn,Ω contains one point close to r for a proportion at least 1 -δ/2 of points r ∈ R.

Consider fx * = f x * ,β,γ with x * uniformly distributed in R. Then:

P ( xn -x * ≤ ǫ) ≤ EΩPx * (x * ∈ Enl(Xn,Ω, ǫ)) ≤ P (#Xn,Ω ≤ C)Px * (x * ∈ Enl(Xn,Ω, ǫ)|#Xn,Ω ≤ C) +P (#Xn,Ω > C) ≤ (1 - δ 2 ) C C ′ + δ 2 < 1 - δ 2
where Enl(U, ǫ) is the ǫ-enlargement of U defined as:

Enl(U, ǫ) = x; ∃x ′ ∈ U, x -x ′ ≤ ǫ .
This contradicts Eq. 4. This concludes the proof of αβ ≤ 1.

CONCLUSION

Our results are based on the locality assumption (Eq. 4). They show tight results in some cases. The locality assumption is somewhat natural, as most evolution strategies (not all, but almost all) verify this assumption; for example, [START_REF] Auger | Convergence results for (1,λ)-SA-ES using the theory of ϕ-irreducible Markov chains[END_REF], one of the main evolutionary optimization convergence results, shows a linear convergence, with no sampling far away; [START_REF] Auger | Local and global order 3/2 convergence of a surrogate evolutionnary algorithm[END_REF], showing faster rates with surrogate models, also verifies this assumption; and polynomial rates in noisy optimization as in [START_REF] Coulom | Handling expensive optimization with large noise[END_REF][START_REF] Arnold | Efficiency and mutation strength adaptation of the (mu/mui,lambda)-es in a noisy environment[END_REF] have the same property as well as many experimentally known rates [START_REF] Beyer | The Theory of Evolution Strategies, ser. Natural Computing Series[END_REF]. Nonetheless, other assumptions leading to similar results (e.g. assumptions ensuring that points far from the optimum cannot help too much) are worth being investigated for clarifying the overall picture.

Basically, our results are about optimization tricks as follows: an optimization algorithm uses the far sampling trick if there is a clear distinction between the approximation of the optimum that they propose and the search points that they use for exploring the fitness function.

Our results can be seen either:

• As proofs that fast rates (faster than those in the tables below) are possible only if you assume that points far away from the optimum do bring information, by statistical model estimation, which are relevant for improving the rate (so that the "far sampling trick" can work).

• As proofs that algorithms which, like most evolutionary algorithms (but not all), do not sample far away from the optimum, can not be optimal when the function is "flat" enough around the optimum (there are algorithms and families of functions for which better rates are possible -which does not mean that algorithms which do not want to use the far sampling trick are necessarily bad algorithms).

The hot discussions on the BBOB mailing list, around the fact that the test beds should distinguish the search points used for approximating the optimum and the search points used for gathering information by sampling far away, suggest that this paper comes at the right moment for noisy optimization formal analysis. Table 1 summarizes the state of the art; new result from this paper are in bold, and we emphasize cases in which a gap is known. We see that our results show the tightness in the case γ = 1 (small noise; the variance goes to zero around the optimum), and reduce the gap in the case γ < 1 (large noise). Our results also show that for fast rates, sampling far from the optimum is necessary; e.g. if β = 4, α = 1/2 is possible only with sampling far from the optimum. Though, this is only possible if there are long range dependencies on the fitness function, so that such points far from the optimum can be used.

Further work

The locality assumption might be or might not be, depending on the application, a good idea. From many discussions around that, we believe that there is room for works like this one, in which a locality assumption prevents the use of information far from the optimum, reliable only when strong assumptions on the model are available. It is also a model which shows that some rates imply sampling far from the x * with β coefficient; see [START_REF] Coulom | Handling expensive optimization with large noise[END_REF] for more details. Experimental rates for R-EDA are for functions with strong invariances/symmetries; see [START_REF] Coulom | Handling expensive optimization with large noise[END_REF] for details. The last column presents results with α = 1/2, corresponding to cases in which using statistical model estimation is possible: the limit case of infinite differentiability in [START_REF] Chen | Lower rate of convergence for locating a maximum of a function[END_REF][START_REF] Kiefer | Stochastic estimation of the maximum of a regression function[END_REF][START_REF] Fabian | Stochastic approximation of minima with improved asymptotic speed[END_REF], is also reached by quadratic logistic regression under parametric assumptions on the objective function [START_REF] Coulom | Handling expensive optimization with large noise[END_REF]; assumptions are not directly comparable to those of the other columns. Lower bounds on the complexity (upper bounds on α) from this paper are under the additional assumption of local sampling.

optimum. Fast optimization algorithms might, as CLOP, be a compromise between sampling close to the optimum and sampling on areas of maximum uncertainty. Further investigations on intermediate models might be a good idea.

There is still a gap between the upper and the lower bound, for algorithms having the locality assumption, in the case γ < 1 (large noise), which is an immediate further work.

We consider noisy optimization in the case of local convergence; clearly, the global convergence case can also be interesting [START_REF] Vazquez | Global optimization based on noisy evaluations: an empirical study of two statistical approaches[END_REF].

We did not compute exactly constants C and C ′ . Maybe it is possible to obtain more information on the constant in the convergence using detailed computations of C and C ′ .

Figure 1 :

 1 Figure 1: Expected values of f x * ,β,γ with respect to x, for d = 1 and with the optimal point x * = 0.5, the noise level γ = 0.8 and β (the "flatness" of Ef around x * ) equals to 1, 2 and 3.

Table 1 :

 1 This table summarizes the state of the art in terms of α for which ||xn-x * || = Õ(1/n α ) is possible. Rates for E-EDA include functions which are not differentiable, and are just upper bounded by flat functions around

		Proved rate for R-EDA	Lower bound in R-EDA experimental	This paper	Rate for
	"flatness"	in [16]	[16]	rate in [14]	(lower bound learnable
		("flatness" on an envelope		(on functions with	under	cases
	β	of the fitness function;		invariances)	locality
		the fitness function does not have to be flat around x * )		assumption)
			Framework γ = 1 (small noise)
	1 2 4	α ≥ 1 α ≥ 1/2 α ≥ 1/4	α ≤ 1 α ≤ 1 α ≤ 1 Framework γ < 1 (large noise) α = 1 α = 1/2 α = 1/4	α ≤ 1 α ≤ 1/2 α ≤ 1/4	α = 1/2 α = 1/2 α = 1/2
	1 2 4	α ≥ 1/2 α ≥ 1/4 α ≥ 1/8	α ≤ 1 α ≤ 1 α ≤ 1	α = 1/2 α = 1/4 α = 1/8	α ≤ 1 α ≤ 1/2 α ≤ 1/4	α = 1/2 α = 1/2 α = 1/2

Interestingly there were debates on the mailing list dedicated to the BBOB noisy optimization testbeds because the designers of the testbeds assess the quality of optimization algorithms not from their estimation on the location of the optimum, but from the points they sample, which is clearly not fair for algorithms which are precisely based on estimating the optimum from points far from the optimum.

Acknowledgments

We are grateful to the Dagstuhl seminar on Evolutionary Algorithms, to the Montefiore institute in University of Belgium in which author #2 had interesting discussions around noisy optimization. We are grateful to various members of the Tao team for interesting discussions, as well as discussions in the BBOB mailing list. We are grateful to European project MASH, FP7 program.