Anne Auger

Olivier Teytaud

Continuous lunches are free plus the design of optimal optimization algorithms

Keywords: No-Free-Lunch, Kolmogorov's extension Theorem, Expensive Optimization, Dynamic Programming, Complexity, Bandit-Based Monte-Carlo Planning. 1

This paper analyses extensions of No-Free-Lunch (NFL) theorems to countably infinite and uncountable infinite domains and investigates the design of optimal optimization algorithms.

The original NFL theorem due to Wolpert and Macready states that, for finite search domains, all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measurability issues and stochastic process theory. For countably infinite domains, we prove that the natural extension of NFL theorems, for the current formalization of probability, does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distributions of fitness leading to equal performances for all search heuristics. Our main result is that for continuous domains, NFL does not hold. This free-lunch theorem is based on the formalization of the concept of random fitness functions by means of random fields.

We also consider the design of optimal optimization algorithms for a given random field, in a black-box setting, namely, a complexity measure based solely on the number of requests to the fitness function. We derive an optimal algorithm based on Bellman's decomposition principle, for a given number of iterates and a given distribution of fitness functions. We also approximate this algorithm thanks to a Monte-Carlo planning algorithm close to the UCT (Upper Confidence Trees) algorithm, and provide experimental results.

Introduction

Search heuristics like evolutionary algorithms, tabu search, grid search are general heuristics that can be applied to any objective function. Much research is devoted to develop heuristics that are superior to others when the target functions belong to a certain class of problems.

The No-Free-Lunch (NFL) theorem for optimization [START_REF] Wolpert | No Free Lunch Theorems for optimization[END_REF], introduced for fitness functions defined on a finite domain, rules out statements that some search heuristics have some advantages when performances are averaged uniformly among all possible functions. Controversial discussions on the usefulness of search heuristics ensued from this theorem [START_REF] Culberson | On the futility of blind search: an algorithmic view of "No Free Lunch[END_REF][START_REF] Radcliffe | Fundamental limitations on search algorithms: Evolutionary computing in perspective[END_REF]. Droste et al. argue that the NFL scenario is not a realistic one and they show that for realistic black box scenarios, NFL will not hold [START_REF] Droste | Optimization with randomized search heuristics -The (A)NFL theorem, realistic scenarios, and difficult functions[END_REF]. Igel and Toussaint [START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF] show that classes of functions relevant in practice are not likely to satisfy the (sharpened) NFL scenario [START_REF] Schumacher | The No Free Lunch and Problem Description Length[END_REF]. Corne and Knowles [START_REF] Corne | Some multiobjective optimizers are better than others[END_REF] show that NFL does not hold in the multi-objective case.

However, a basic assumption of NFL theorems is that the search space is finite. In that case "averaging uniformly among all possible functions" has a clear meaning: the average is made with respect to the cardinal and uniform random fitness can be easily defined as a mapping from a probability space to the finite set of all possible functions. It is more tricky to give a meaning to uniform average among functions when the domain is countably infinite or continuous (uncountable infinite). More generally, it is difficult to define a random mapping from a probability space to the (infinite) space of all possible functions. Doing so in a proper way, for the current formalization of probability, involves measurability and stochastic process theory [START_REF] Daniell | Integrals in an infinite number of dimensions[END_REF][START_REF] Kolmogorov | Foundations of the theory of Probability (original: Grundbegriffe der Wahrscheinlichkeitsrechnung)[END_REF][START_REF] Billingsley | Probability and Measure[END_REF].

A related question is the existence of optimal optimization algorithms assuming a priori information on the distribution of objective functions and given a finite number of iterations. Such optimal optimization algorithms require representation of all the past information. This has already been investigated in the field of global optimization; for example, [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF] proposes the EGO algorithm (Efficient Global Optimization) based on a modelization by Gaussian processes, and the criterion is improved in [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF]. In these two cases, the expensive optimization framework is the opportunity for deriving complex algorithms with large computation times; as the fitness function is assumed very expensive, the goal is solely the optimization for a given number of iterations, and not the computational cost of choosing the iterates. However, in these papers, the suboptimality is due to the principle itself; even though all priors would be true and the algorithms could be run without any numerical trouble, the algorithm would not be mathematically optimal.

In this paper, we investigate NFL results for countably infinite and continuous domains and study the optimal framework, for a given distribution of problems, a given criterion, and a given number of iterates, at least in the limit of a large computational power for choosing each iterate. In Section 2 we start by reviewing NFL theorems for finite domains. We recall important definitions from measure theory required when dealing with uncountable infinite domains.

We also introduce definitions required for the extensions of (N)FL theorems to countably infinite and uncountable domains. In Section 3, we show that the natural (for the current formalization of probability) extension of NFL results, for countably infinite domains does not hold but show that a weaker form of NFL does hold. In Section 4, we show that this weaker form of NFL does not hold anymore for continuous domains. In Section 5, we derive an optimal optimization algorithm assuming a prior distribution on the distribution of functions and a finite number of iterates. We also approximate this algorithm using a Monte-Carlo planning algorithm and show its tractability.

Preliminaries on the NFL theorems

In this section, we present (i) the finite case (ii) the definitions required for the rest of the paper.

Finite lunches

We present in this section NFL theorems for objective functions mapping a finite domain X , with cardinal |X |, into a finite codomain Y ⊂ R [START_REF] Wolpert | No Free Lunch Theorems for optimization[END_REF][START_REF] Schumacher | The No Free Lunch and Problem Description Length[END_REF][START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF][START_REF] Droste | Optimization with randomized search heuristics -The (A)NFL theorem, realistic scenarios, and difficult functions[END_REF][START_REF] Corne | Some multiobjective optimizers are better than others[END_REF]. The search heuristics considered are randomized or deterministic and it is assumed that they are non-repeating. In practice, this can be ensured by archiving the different inputs. For any integer m in {1, . . . , |X |}, the vector (x 1 , . . . , x m ) represents the m first iterates of a search algorithm and the vector (f (x 1 ), . . . , f (x m )) their associated objective values for a given function f mapping X into Y. The performance of an algorithm a after m iterations is measured using the vector of cost values

Y (f, m, a) = f (x 1 ), . . . , f (x m ) (1)
where we stick to the notations used in [START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF]. Let c denote a performance measure mapping the vector of cost values to the real numbers. The function c can be for instance the minimum value of the vector Y (f, m, a) or the number of iterations before reaching a given value. We denote by Π(X ) the set of permutations on X . A set of functions F is closed under permutation (c.u.p.) if for any f ∈ F and any permutation π ∈ Π(X ), f • π ∈ F.

The original NFL for optimization was stated for the set of all possible functions on X , i.e., F = Y X [START_REF] Wolpert | No Free Lunch Theorems for optimization[END_REF] and has been generalized for c.u.p. subsets [START_REF] Schumacher | The No Free Lunch and Problem Description Length[END_REF][START_REF] Droste | Optimization with randomized search heuristics -The (A)NFL theorem, realistic scenarios, and difficult functions[END_REF]: Theorem 2.1 (NFL for c.u.p. subsets). Let F be a subset of Y X . Then, for any two algorithms a and b, any m in {1, . . . , |X |}, any performance measure c,

any k ∈ R f ∈F δ(k, c(Y (f, m, a))) = f ∈F δ(k, c(Y (f, m, b))) ( 2
)
iff F is c.u.p.1

In the previous theorem, averaging is done by uniform summation over F which implicitly means that all functions in F are equally likely. An equivalent point of view is to define f as a random variable taking values in the set of functions F, with the same probability for each function in F. The vector Y (f, m, a) defined in Eq. 1 is then a random vector and an equivalent formulation to "for all k in R, Eq. 2 holds" is

∀k ∈ R, P (c(Y (f, m, a)) = k) = P (c(Y (f, m, b)) = k) , (3)
where the random variable f is uniformly distributed on F, i.e., for any f 0 ∈ F, A generalization of this NFL theorem to non uniform distributions of fitness has been presented in [START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF]. They consider the histogram h f0 of a function f 0 ∈ Y X defined for each y ∈ Y as the cardinal of the pre-image f -1 0 (y), i.e.,

P(f = f 0 ) is constant
h f0 : y ∈ Y → |f -1 0 (y)| .
Then, Theorem 2.2 holds for random variables f having distributions constant for functions having the same histogram [START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF], i.e.,

if

h f0 = h f1 , P(f = f 0 ) = P(f = f 1 ). ( 4
)
One simple random variable satisfying the condition in Eq. 4 is defined as follows: consider the c.u.p. subset F Π f0 defined for a function f 0 ∈ Y X as

F Π f0 = {f 0 • π for π ∈ Π(X )} (5)
and define the corresponding random variable f

F Π f 0 as f F Π f 0 = f 0 • π , (6)
where π is a random variable uniformly distributed on Π(X ). Then f F Π f 0 satisfies the histogram condition (Eq. 4) and also Theorem 2.2. Averaging with any unequal weights multiple random variables of this form (with different functions f 0 ) provides a random variable satisfying Eq. 4 without, in general, satisfying the uniformity on a c.u.p. subset condition required in Theorem 2.2.

Generalization

The generalization of NFL theorems for countably infinite and uncountable infinite domains calls upon measurability theory. We summarize here some basics that we will need in the rest of the paper. Consider a probability space (Ω, A, P), where A is a σ-algebra on Ω and P a probability measure defined on A. When X is finite, a mapping X : Ω → X is a random variable2 if for any x 0 , {ω ∈ Ω, X(ω) = x 0 }, denoted in short {X = x 0 }, is in A. P X : x 0 → P X (x 0 ) = P({X = x 0 }) is then well defined and called the distribution function of X. This definition is extended to X = R n using measurability. A mapping

X : Ω → R n is a random variable if it is a measurable function, i.e., a function such that X -1 (E) = {ω ∈ Ω, X(ω) ∈ E} is in A for any measurable subset E of R n . This implies that P X (E) = P({ω ∈ Ω; X(ω) ∈ E}) is defined for any measurable E ⊂ R n .
When X has no natural measure, defining something similar to a random variable is more difficult. For defining a random variable with values in Y X with Y ⊂ R and X finite, one can simply use the natural isomorphism from Y X to R n where n is the cardinal of X . Doing so induces a measure on Y X that is the usual measure in this case. When X is infinite but countable, then Kolmogorov's extension theorem provides a natural extension. But when X is uncountable, typically X = R n , we need stochastic processes or random fields [START_REF] Vanmarcke | Random Fields: Analysis and Synthesis[END_REF] 3 . This will be detailed in Section 4.

Performance measurement

In Theorem 2. Lemma 2.3. Let M be the set of measurable functions from R n to R and M ′ the set of characteristic functions4 of measurable sets of the form ] -∞,

t 1 ]×] - ∞, t 2 ] × • • • ×] -∞, t n ] ⊂ R n .
Then, for any family A of random variables in R n , the following statements are equivalent:

∀(a 1 , . . . , a n ) ∈ A, ∀c ∈ M, c(a 1 , . . . , a n ) have the same distribution (7) ∀(a 1 , . . . , a n ) ∈ A, ∀c ∈ M ′ , c(a 1 , . . . , a n ) have the same distribution (8) ∀(a 1 , . . . , a n ) ∈ A, ∀c ∈ M ′ , E (c(a 1 , . . . , a n )) are equal (9) ∀(a 1 , . . . , a n ) ∈ A, (a 1 , . . . , a n ) have the same distribution (10)
Proof. Eq. 10 implies Eq. 7 which in turn implies Eq. 8 which in turn implies Eq. 9. We just have to show that Eq. 9 implies Eq. 10. Eq. 9 states that all the (a 1 , . . . , a n ) have the same cumulative distribution function, and therefore the same distribution. This implies Eq. 10.

For the sake of simplicity we will prefer the last statement in our NFL definitions: two algorithms will be equivalent if Y (f, m, a) and Y (f, m, b) follow the same distribution.

No-Free-Lunch definitions

We introduce here different notions of NFL. We generalize first the definition of No-Free-Lunch in order to extend results stated in Theorem 2.2. To do so, we consider the simple c.u.p. subset F Π f0 introduced in Eq. 5 and satisfying Theorem 2.2. A permutation π on X is a bijective (or one-to-one) mapping from X to X . This definition also holds when X is uncountable. In some cases, we will have to consider measure-preserving permutations: Definition 2.4 (Measure-preserving). Let (X , B, µ) be a measure space, and T : X → X be a measurable mapping. We call T measure-preserving if for all A ∈ B, we have that

µ(T -1 (A)) = µ(A).
When X is a discrete space and µ the cardinal measure (µ(A) = |A|), any permutation is measure-preserving. In all the paper, we will restrict our attention to the cardinal measure when X is a discrete (finite or countable) domain. In [0, 1], we will consider the Lebesgue measure.

For our first definition of NFL we consider distributions of functions f 0 • π where π is a random permutation (see below for a formal definition). We will see other, more general (weaker) forms of NFL in the rest of the paper, and show that even weaker forms do not hold in the continuous case.

The intuitive idea of a random permutation π is a random variable with values in X X . However, the definition of a random variable involves σ-algebras: a mapping with values in X X is a random variable if it is measurable. Therefore, we need a σ-algebra on X X for using this terminology. Such σ-algebras exist, but they have several weaknesses [START_REF] Billingsley | Probability and Measure[END_REF]. Instead, we will simply require that π is a measurable map as a function (ω, x) ∈ Ω × X → π(x) (where, as usual, π implicitly depends on ω ∈ Ω). We extend Definition 2.4 to a random permutation T : Ω × X → X as follows: T is measure-preserving if T (ω) is measure-preserving in the sense of Definition 2.4 almost surely in ω. Our first No-Free-Lunch definition reads: Definition 2.5. Let f 0 : X → R be a measurable function and π a measurepreserving random permutation on X . N FL(X , π, f 0 ) holds iff for any integer m (smaller than |X | when X is finite) and any two optimization algorithms a and b, Y (f 0 • π, m, a) and Y (f 0 • π, m, b) follow the same distribution.

A proper median of a deterministic mapping f 0 is a value M f0 such that the measure of {x ∈ X ; f (x) > M f0 } is equal to the measure of {x ∈ X ; f (x) < M f0 } and {x ∈ X ; f (x) = M f0 } has measure zero. Definition 2.6. Let f 0 : X → R be a measurable function with a proper median. Then N FL(X , f 0 ) holds iff there exists a measure-preserving random permutation π on X such that N FL(X , π, f 0 ) holds. Definition 2.7. N FL(X ) holds iff N FL(X , f 0 ) holds for all measurable functions f 0 : X → R with proper median.

When X is finite, Theorem 2.2 implies that N FL(X ) holds: Proposition 2.8. When X is finite, N FL(X ) holds.

Proof. Apply Theorem 2.1 to f F Π f 0 defined in Eq. 6.

We want now to generalize Definitions 2.5, 2.6 and 2.7. In particular we do not want to restrict the distribution of fitness functions to f 0 • π where π is a measure-preserving random permutation. We therefore have to define a general framework for "random variables", that works also in the case of X continuous. This is the issue in stochastic processes also termed random fields when X is multi-dimensional, for instance R n . A stochastic process f is a mapping Ω × X : (ω, x) → f (x) (where, as usual, f (x) implicitly depends on ω). It is termed measurable when it is measurable as a function of both (ω, x). This condition is not restrictive: it is necessary for making Y (f, m, a) meaningful as a random variable. We implicitly assume in the rest of the paper that all stochastic processes are measurable, otherwise all statements are pointless.

We have no more permutation, but we need the weaker assumption that a median of the fitness values is constant. Our definition of a random fitness distribution is as follows: Definition 2.9. A random fitness is a measurable map f from Ω to R X such that there exists a constant M f ∈ R which is a proper median of f for any ω. Definition 2.9 requires that a proper median exists for any ω, and that it does not depend on ω. Our generalized definition for No-Free-Lunch reads as follows:

Definition 2.10. Let f be a random fitness. GN FL(X , f ) holds iff for any m ∈ N (smaller than |X | when X if finite) and any two optimization algorithms a and b, Y (f, m, a) and Y (f, m, b) follow the same distribution.

This No-Free-Lunch statement depends on the random fitness distribution f . We would like to characterize domains X for which GN FL(X , f ) holds for at least one f : Definition 2.11. GN FL(X ) holds if there is one random fitness f such that GN FL(X , f ) holds.

Note that we only require the existence of one non-trivial random fitness f such that GN FL(X , f ) holds which is less restrictive than N FL(X ) requiring that N FL(X , f 0 ) holds for any measurable f 0 with a proper median.

If there exists f 0 such that N FL(X , f 0 ) holds, the distribution

f = {f 0 • π, π random permutation s.t. N FL(X , f 0 , π) holds}
is such that GN FL(X , f ) holds (a median of f is a median of f 0 as π is measurepreserving). Therefore:

Proposition 2.12 (Link between NFLs). For any measure space (X , B, µ), for any f 0 with a proper median,

N FL(X , f 0 ) holds ⇒ ∃ π s.t. GN FL(X , f 0 • π) holds ⇒ GN FL(X ) holds 3 Countable (No)-Free-Lunch
In this section, X is countably infinite, without loss of generality X = N. We recall that the measure considered is then the cardinal measure implying that all permutations are measure-preserving. We start by building a non-trivial measurable function f 0 such that N FL(X , f 0 ) does not hold.

Proposition 3.1. If X = N and f 0 (i) = (-1) i+1 i, for all i ∈ N, then there is no random permutation π such that N FL(X , π, f 0 ) holds. Therefore, N FL(X , f 0 ) does not hold.

Proof. First note that f 0 admits proper medians: every M ∈ R is a proper median. Assume now that there exists a random permutation π such that N FL(X , π, f 0 ) holds. Then, consider, for any i ∈ N, the algorithm that always chooses x 1 = i as first iterate. The property N FL(X , π, f 0 ), i.e., Definition 2.5, applied to this algorithm for any two different values of i, leads to

P(f 0 (π(i)) = 1
) is the same for all i, which, thanks to the definition of f 0 , leads to P(π(i) = 1) is the same for all i.

But as the events {π(i) = 1} for i ∈ N are a partition, we have

1 = i≥0 P(π(i) = 1) . (11)
This yields the expected contradiction as P(π(i) = 1) = 0 and P(π(i) = 1) > 0 both lead to a contradiction (resp. i≥0 P(π(i) = 1) = 0 and i≥0 P(π(i) = 1) = ∞).

Note that any injective f 0 , i.e., such that i = j ⇒ f 0 (i) = f 0 (j) would work, provided that a proper median exists. This proposition shows that contrary to finite domain, N FL(X ) does not hold: there are some "histograms of values" (i.e., some f 0 ) for which some algorithms are better than others, for any measurepreserving random permutation π. However, one can study the existence of distributions of functions for which all algorithms are equivalent. In particular if the objective function is a random function with "enough independence" (see proof below), one does not expect any optimization algorithm to be better than another one. This is what we formalize in the following proposition. Proposition 3.2 (No-Free-Countable-Lunch). When X = N, there exists a non-trivial random fitness f , i.e., a random fitness with minimum different of the maximum with probability one such that GN FL(N, f ) holds. Moreover, one can choose f such that there exists f 0 satisfying f = f 0 • π with probability 1, where π is a (necessarily measure-preserving) random permutation of N. Therefore N FL(N, f 0 ) holds.

Proof. Let f be the random fitness distribution such that the f (i), for i ∈ N, are independent and uniformly distributed in {0, 1}. Technically, such a fitness can be built thanks to Kolmogorov's extension theorem.

Then, for any algorithm a, and any m,

Y (f, m, a) is uniformly distributed on {0, 1} {1,...,m}
and therefore GN FL(N, f ) holds.

Let us now show the second statement of the proposition, i.e., that for some f 0 , N FL(N, f 0 ) holds.

With probability one, the subsets of N, {f -1 (1)} and {f -1 (0)} are infinite. Consider the deterministic fitness function f 0 defined as f 0 (i) = 1 if i is even and f 0 (i) = 0 otherwise. Let π be the random permutation defined for all m ∈ N as follows:

• if f (m) = 1, then π(m) = 2 × k(m) with k(m) minimal such that 2k(m) is different from π(i) for any i < m • if f (m) = 0, then π(m) = 2 × k(m) + 1 with k(m) minimal such that 2k(m) + 1 is different from π(i) for any i < m.
Then N FL(N, f 0 , π) holds.

From this proposition we deduce the following corollary:

Corollary 3.3. N FL(N, f 0 ) holds with f 0 (x) = 1 for x even and f 0 (x) = 0 for x odd.

We summarize the results of Proposition 2.8, Proposition 3.1 and Proposition 3.3 in the following theorem: Theorem 3.4 (NFL in discrete spaces). The following holds:

• If X is finite, then N FL(X ) holds, and therefore GN FL(X ) holds.

• If X is countably infinite:

-GN FL(X , f ) holds with f (x) = 1 with probability 1 2 , independently for each x.

-Therefore, GN FL(X ) holds.

-N FL(X , f 0 ) holds with f 0 (x) = 1 for x even and f 0 (x) = 0 for x odd.

-But N FL(X ) does not hold, and for any f 0 with proper median such that i = j ⇒ f 0 (i) = f 0 (j), N FL(X , f 0 ) does not hold.

Continuous free-lunch

In this section, we show the main result of this paper, namely that there is no random fitness for which all algorithms are equivalent in the sense of Definition 2.10 when X is a continuous domain. Without loss of generality we assume that X = [0, 1] and Y = R.

It is known that the measurability issue in stochastic processes and random fields is non-trivial [START_REF] Doob | Stochastic process measurability conditions[END_REF]. Consider X a continuous domain. One cannot just set a covariance kernel (X × X → R) on X , marginal laws, and consider "a" random field f with such marginals and covariances. Even with null covariance, one cannot just define marginal laws, and consider "a" random variable with such independent marginals. It is not better with just one distribution of probability on R: one cannot simply define a random field with independent marginals and all marginal distributions equal to the required distribution of probability. It is working with countable domains, as shown by Kolmogorov's extension theorem [START_REF] Daniell | Integrals in an infinite number of dimensions[END_REF][START_REF] Kolmogorov | Foundations of the theory of Probability (original: Grundbegriffe der Wahrscheinlichkeitsrechnung)[END_REF], but it does not work in continuous domains at least for the current formalism of probability theory, based on measurability conditions. The interested reader is referred to [START_REF] Billingsley | Probability and Measure[END_REF][START_REF] Doob | Stochastic process measurability conditions[END_REF] for a more detailed discussion, in particular for stochastic processes and random fields. The proof of this theorem relies on Lemma 4.2 and Lemma 4.5 that are stated and proved below. Proof of Theorem 4.1: Assume that such an f exists. Then, consider two optimization algorithms for just 1 iterate:

• the algorithm deterministically choosing a given x ∈ [0, 1];

• the algorithm deterministically choosing a given x ′ ∈ [0, 1];

Assuming that GN FL([0, 1], f ) holds leads to the fact that f (x) is distributed as f (x ′ ). Therefore, all the f (x) for x ∈ [0, 1] are identically distributed. Hence, we have shown that in the continuous domain, No-Free-Lunch theorems imply the identical distribution of the fitness-values of each point in the domain.

Define g(x) = 1 if f (x) > M f , for some M f a proper median of f , and g(x) = 0 otherwise. g is another random field.

First, GN FL([0, 1], f ) implies that the g(x) are identically distributed for x ∈ [0, 1]. Now, let us show that the g(x) are independent for x ∈ [0, 1]. Consider some fixed x 1 , . . . , x n-1 , x n in [0, 1] (all different). Then, (g(x 1 ), . . . , g(x n )) must be, if GN FL([0, 1], f ) holds, the same as for random search. Therefore, the g(x 1 ), . . . , g(x n ) are independent. Besides, for random search, (g(x 1 ), . . . , g(x n )) is uniformly distributed on {0, 1} n . Therefore, g is a random field, such that g(x) = 1 with probability 1 2 and g(x) = 0 otherwise, for any x, and all the g(x) are independent.

We then conclude by Lemma 4.2 that such a g cannot exist.

Kolmogorov's extension theorem ensures that for any distribution of probability, sequences of independent random variables with the same distribution can be built. Some extensions exist for continuous cases, but without independence. The interested reader is referred to random field theory for this point. We here show that a fully independent and identically distributed family of non-constant random variables indexed by the continuum cannot be defined. Lemma 4.2 (No continuous family of i.i.d. RV). Assume that g is a random function with values in {0, 1} [0,1] , such that all the g(x) for x ∈ [0, 1] are identically distributed. Assume that there is p ∈]0, 1[ such that p = P(g(x) = 1) for all x. Then, the g(x) are not independent.

We will use in the proof the fact that almost surely g is Lebesgue measurable. This is not a hidden assumption: this is implied by our definition of stochastic processes. Also, this holds as soon as 1 0 g(x)dx is well defined almost surely in the realization g.

Proof. Assume that the g(x) are independent. We will now try to get a contradiction. We will split the proof in the following steps:

1. We show (by Lemma 4.5) that almost surely g -1 (1) has Lebesgue measure p.

We apply

Step 1 to show that almost surely, there is an open interval in which g -1 (1) has average density ≥ p ′ > p. We now present the detailed steps of the proof.

We apply

Step 1. We can apply Lemma 4.5 since all the g(x) are independent, identically distributed with non zero variance (since each g(x) is a Bernoulli random variable with probability p ∈]0, 1[ to take the value 1). Lemma 4.5 ensures that with probability 1, g -1 (1) has a Lebesgue measure of p. This concludes the first step.

Step 2. By Lebesgue's density theorem, E = g -1 (1) has density 1 at almost every point in E. We recall below the definition of density and Lebesgue's density theorem:

Definition 4.3. The density of a set A ⊂ R d in an ǫ-neighborhood of a point x ∈ R d , with ǫ > 0, is d ǫ (x, A) = µ (A ∩ B(x, ǫ)) µ (B(x, ǫ))
The density of a set A at a point x is Therefore, almost surely there is a rational segment5 s such that

d(x, A) = lim E ′ →0 d ǫ ′ (x, A)
µ(s ∩ E) ≥ 1 + p 2 µ(s) (12)
One can extend Eq. 12 for any constant < 1 instead of (1 + p)/2; (1 + p)/2 is enough for the rest of this paper, so we here only show Eq. 12.

This concludes step 2.

Step 3. By step 2, and as the set of rational segments is countable, and as almost surely one of them verifies equation 12, there is at least one rational segment which has non-zero probability of verifying equation 12. Consider then a, b ∈ Q 2 such that s = [a, b] realizes equation 12 with positive probability. This concludes step 3.

Step (

) 13
Step 5. Eq. 13 is a contradiction with Eq. 12.

We now have to deal with the following lemma. This lemma is necessary for our proof, as it is used in order to get a contradiction; as a by-product of this paper, we will see that, in fact, the assumptions in Lemma 4.5 cannot hold. Lemma 4.5. Assume that g is a stochastic process with values in {0, 1} [0,1] . Assume that almost surely g is Lebesgue measurable. Assume that all the g(x) are identically distributed, have non-zero variance and are independent. Define E = g -1 (1). Let p = P(g(x) = 1) that does not depend on x by hypothesis above. Then, with probability 1, µ(E) = p, with µ the Lebesgue-measure.

Proof. Since g is a stochastic process taking values in {0, 1} [0,1] , the Lebesgue measure of the pre-image of 1 under g is a random variable that we denote m = µ(g -1 (1)) = µ(E). We are going to prove that the random variable m is constant almost surely and equal to p (in other words equal to p with probability one).

Let E be the expected value of µ(E), i.e., E = E(µ(E)) and V its variance, i.e., V = V ar(µ(E)).

Step 1. By definition, the three following mappings have the same distribution:

• x → g(x); • x → g(x/2); • x → g((1 + x)/2).
Step 2: By decomposition of the integral,

1 0 g(x)dx = 1 2 0 g(x)dx+ 1 1 2 g(x)dx; this shows that 1 0 g(x)dx is distributed as 1 2 1 0 g(x/2)dx + 1 2 1 0 g((1 + x)/2)dx.
This concludes step 2.

Step 3: V = 0.

Step 1 and step 2 together state that µ(E) is distributed as (m + m ′ )/2, with m ′ an independent copy of m. An important consequence of that is V = V ar(µ(E)) = V/4 + V/4 = V/2, and therefore V = 0.

Therefore, µ(E) has variance 0.

Step 4: concluding the proof of Lemma 4.5. Consider x a uniform variable in [0, 1], independent of g. Using the Fubini Theorem, we have that P(g(x) = 1) = p = E(µ(E)). Therefore, µ(E) is equal to p with probability 1.

The design of optimal optimization algorithms

In the previous sections, we have seen strong limitations to NFL theorems. Only in some very specific cases of fitness distributions, a NFL result holds. We investigate now the following questions: assuming a given distribution of fitness functions, which algorithm is better than the random search and does an optimal optimization algorithm exist? We here provide a positive answer to the question of optimality among all possible optimization algorithms when a priori information on the distribution of the problems is known and when a finite number of function evaluations (FE) is known in advance. Such a question is of drastic importance for real-world problems where the objective function is so expensive that one can afford to spend minutes or hours to choose the next iterate.

This question can be seen as a problem of sequential decision with uncertainty [START_REF] Poupart | An analytic solution to discrete bayesian reinforcement learning[END_REF], with a delayed reward:

• at each time step, a "decision", which is in the context of optimization a point of the search domain, is proposed,

• a reward is provided at the N th time step (that can be for instance the mean squared distance to the optimum), where N is the number of FE allowed.

For such a problem, Bellman's optimality principle [START_REF] Bellman | Dynamic Programming[END_REF] precisely states that an optimal strategy on average exists and provides an explicit derivation of one optimal algorithm.

Optimal optimization algorithms

We consider a family of fitness functions defined on a domain D and depending on a random parameter θ: f (., θ) :

D → R . (14)
The domain D can be either discrete, continuous or mixed. For each realization of θ, we assume that the fitness function f (., θ) has only one global minimum that we denote x * (θ) (this is not necessary for our results, but simplifies notations).

Example 1. Let f s (., θ) be the family of sphere functions with optimum located in θ, uniformly distributed in [0, 1] d , and mapping the continuous d-dimensional hyper-square [0, 1] d into R + , i.e.,

f s (x, θ) = x -θ 2 = d i=1 (x i -θ i ) 2
where x = (x 1 , . . . , x d ) and θ = (θ 1 , . . . , θ d ).

We investigate the question of optimal algorithms for a predefined number of iterations N ∈ N \ {0}. Let Opt be a general optimization algorithm that defines for a given instance of θ, a sequence (x n ) 1≤n≤N of points in D and their associated fitness values (y n ) 1≤n≤N , i.e.,

x 1 = Opt() and y 1 = f (x 1 , θ) and for n ∈ {1, . . . , N }

x n = Opt(x 1 , x 2 , x 3 , . . . , x n-1 , y 1 , . . . , y n-1 ) and y n = f (x n , θ).

We consider optimality in the sense of minimizing a criterion at iteration N . To define this criterion we measure the so-called loss at iteration N by mean of a loss function denoted L(x N , θ). This loss function can be either

L(x N , θ) = x N -x ⋆ (θ) 2 , or L(x N , θ) = x N -x ⋆ (θ) , or L(x N , θ) = f (x N , θ) -f (x ⋆ (θ), θ), . . .
For the example of the sphere functions (Example 1) with d = 2 and N = 4, there exists an (optimal) algorithm for the loss functions defined above -this algorithm will be optimal for the three loss functions above simultaneously. Indeed, let us choose any point x 1 ∈ [0, 1] 2 and evaluate the objective function f (x 1 , θ) = x 1θ 2 . The optimum θ is located on the circle C 1 of center x 1 and radius f (x 1 , θ). Let us choose a second point x 2 (different from x 1 ), θ is located on the circle C 2 of center x 2 and radius f (x 2 , θ). The intersection between C 1 and C 2 is at most two points. Let x 3 be one of the two points (or the only one), if f (x 3 , θ) = 0, then θ = x 3 and choose x 4 = x 3 , otherwise choose the other intersection point for x 4 . This leads to f (x 4 , θ) = 0. In this case we see that for any random parameter θ, the algorithm sketched finds the optimum in four iterations. In general though, the result after N iterations depends on the instance of the parameter θ. Moreover, some optimization algorithms are stochastic and their outcome for a same θ can be different. In order to take into account stochastic optimization algorithms and the random parameter in the fitness function, one defines optimality on average as follows: Definition 5.1 (Optimality on average). An algorithm Opt is optimal on average if it minimizes

E rs,θ (L(x N , θ)) , ( 15
)
where rs is the random variable (independent of θ) which is the random-seed of the optimizer (x N depends on Opt, and Opt implicitly depends on rs, therefore the loss depends on rs).

For any integer n ∈ {0, . . . , N -1}, we define Opt n as the restriction of Opt to entries of at least n points. This means that Opt n (x 1 , . . . , x j , y 1 , . . . , y j ) is defined if and only if n ≤ j < N . The only difference between Opt and Opt n is that for Opt n the n first points (at least) are already given. This difference is only mathematical, not algorithmic.

Choosing the best possible function Opt is exactly a problem of stochastic optimal sequential decisions with discrete time steps and finite horizons. A classical tool for such a problem is called Bellman principle of optimality [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. For n ∈ {1, . . . , N }, the so-called value function V n is defined almost surely on D n × R n as follows:

V n = D n × R n → R ∪ {∞} (x 1 , . . . , x n , y 1 , . . . , y n ) → inf Optn E rs,θ;∀k≤n,y k =f (x k ,θ) L(x N , θ) (16)
where the expectation with respect to θ is conditionally on the event that {for all k ≤ n, y k = f (x k , θ)}. This is almost surely well-defined in (y 1 , . . . , y i ) for the random variable (y 1 , . . . , y n ) = (f (x 1 , θ), f (x 2 , θ), . . . , f (x n , θ)) -then, the conditional distribution is well-defined, assuming that the loss is non-negative. Bellman's principle of optimality states that:

1. The value function V n can be computed by backward induction as follows:

V N (x 1 , . . . , x N , y 1 , . . . , y N ) =E θ;∀i,f (xi,θ)=yi L(x N , θ) (17) V n-1 (x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) = inf x E y V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , y)
where y is distributed as f (x, θ), with θ following its probability distribution conditionally on ∀i ≤ n -1, f (x i , θ) = y i .

Any optimizer

Opt such that ∀n ∈ {2, . . . , N },

Opt(x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) ∈ arg min x E θ;∀i≤n-1, yi=f (xi,θ) V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , f (x, θ))
minimizes [START_REF] Gelly | The parallelization of monte-carlo planning[END_REF].

The optimality is formalized in the following theorem: Theorem 5.2 (Bayesian optimization). Consider N ∈ N. Consider θ a random variable. Assume that almost surely, f (., θ) has one and only one minimum x * (θ). If we define Opt as:

Opt(x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) ∈ arg min x E y=f (x,θ)|∀i≤n-1,f (xi,θ)=yi V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , y) (18)
with V n defined by backwards induction as follows:

V N (x 1 , . . . , x N , y 1 , . . . , y N ) = E θ;∀k=1,...,N,f (x k ,θ)=y k L(x N , θ) (19)
For all n = 2, . . . , N, V n-1 (x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) = inf

x E y=f (x,θ)|∀i≤n-1,f (xi,θ)=yi V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , y) (20)
then Opt minimizes E rs,θ (L(x N , θ)) among all possible optimizers.

Proof. This result is an immediate application of Bellman's optimality principle [START_REF] Bellman | Dynamic Programming[END_REF]. By backward induction, Eq. 17 constructs the functions V n of Eq. 16. Eq. 18 and Eq. 16 precisely state the optimality of Opt.

Consider Example 1 with d = 2, and N = 4 and investigate the behavior of the algorithm defined in Theorem 5.2 in that framework. Denote by S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) a value of θ such that ∀i ∈ {1, 2, 3}, f (x i , θ) = y i , when such a value exists. By definition of V 4 and of L(x N , θ) = x Nx * (θ) 2 , V 4 (x 1 , x 2 , x 3 , x 4 , y 1 , y 2 , y 3 , y 4 ) = y 4 . This implies that x 4 , chosen by Eq. 18, is x minimizing

E y V 4 (x 1 , x 2 , x 3 , x, y 1 , y 2 , y 3 , y) = y = x -S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) 2 (21)
i.e., x = S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) (at least almost surely in (x 1 , x 2 , x 3 , y 1 , y 2 , y 3 )we drop in the sequel detailed references to such almost-sure well-definiteness notions). We can also compute V 3 (x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) by Eq. 17:

V 3 (x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) = inf x E y V 4 (x 1 , x 2 , x 3 , x, y 1 , y 2 , y 3 , y) ≤ V 4   x 1 , x 2 , x 3 , S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ), y 1 , y 2 , y 3 , f (S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ), θ) =0   = 0 .
The previous equation implies that, at least when x 1 = x 2 , x 3 can be chosen anywhere in the domain, except in a set of null measure such that the x i do not uniquely determine θ.

Then, we can compute V 2 (x 1 , x 2 , y 1 , y 2 ) by Eq. 17 again, at least if x 1 = x 2 :

V 2 (x 1 , x 2 , y 1 , y 2 ) = inf x E y V 3 (x 1 , x 2 , x, y 1 , y 2 , y) ≤ V 3 (x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) ≤ 0 (22)
with x 3 such that there is only one solution θ to ∀i ∈ {1, 2, 3}, f (x i , θ) = y i . Eq. 22 and Eq. 18 show that x 2 can be chosen anywhere in the domain except at x 1 without losing optimality. Also, V 1 (x 1 , y 1 ) = 0 and x 1 can be chosen anywhere in the domain.

Therefore, the algorithm suggested by Theorem 5.2 in the specific case of the sphere function works as follows with N = 4 points in dimension 2:

• choose x 1 in the domain;

• choose x 2 = x 1 ;
• choose x 3 such that S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ) is uniquely determined;

• choose x 4 = S(x 1 , x 2 , x 3 , y 1 , y 2 , y 3 ).
This is exactly the analytic algorithm solving the problem.

Applications

In this section, we discuss a theoretical application to surrogate models; a theoretical application to the possible optimality of estimation-of-distribution principles and experiments about the algorithm suggested by Theorem 5.2, to see if this optimality is purely theoretical or if it can be applied in practice within reasonable computation time.

Application to surrogate models

Meta-models [START_REF] Dennis | Managing approximation models in optimization[END_REF][START_REF] Booker | A rigorous framework for optimization of expensive functions by surrogates[END_REF][START_REF] Emmerich | Metamodel-assisted evolution strategies[END_REF] are used in evolutionary algorithms to make them faster, in particular when the objective function is expensive. Under some very mild assumptions on the objective functions, surrogate algorithms converge globally with a 3/2 convergence rate [START_REF] Auger | Local and global order 3/2 convergence of a surrogate evolutionary algorithm[END_REF]. Moreover surrogate models built without derivatives are superior to local surrogate models built with derivatives for some surprisingly simple and smooth frameworks [START_REF] Powell | Unconstrained minimization algorithms without computation of derivatives[END_REF][START_REF] Conn | Recent progress in unconstrained nonlinear optimization without derivatives[END_REF]. Some experiments with very different forms of meta-models can be found in [START_REF] Gelly | Resource-aware parameterizations of EDA[END_REF][START_REF] Kern | Local meta-models for optimization using evolution strategies[END_REF][START_REF] Runarsson | Ordinal regression in evolutionary computation[END_REF], and many applications can be found in [START_REF]Aerodynamic design using neural networks, the amount of computation needed to optimize a design is reduced[END_REF][START_REF] Leary | A derivative based surrogate model for approximating and optimizing the output of an expensive computer simulation[END_REF][START_REF] Hopkins | Neural network and regression methods demonstrated in the design optimization of a subsonic aircraft[END_REF][START_REF] Husken | Structure optimization of neural networks for evolutionary design optimization[END_REF][START_REF] Keane | Computational Approaches for Aerospace Design : The Pursuit of Excellence[END_REF][START_REF] Grieken | Optimisation pour l'apprentissage et apprentissage pour l'optimisation[END_REF][START_REF] Kleijnen | Sensitivity analysis of simulation experiments: regression analysis and statistical design[END_REF][START_REF] Ibric | Artificial neural networks in the modeling and optimization of aspirin extended release tablets with Eudragit L100 as matrix substance[END_REF].

Theorem 5.2 can also be applied to optimization with surrogate models. Assume that a prior distribution on θ is available, as previously assumed. Then, we have proposed above optimal algorithms Opt(.) that provide x n+1 as a function of (x 1 , . . . , x n , y 1 , . . . , y n ). These algorithms only depend on V n , where V n is a function mapping sequences of the form (x 1 , . . . , x k , y 1 , . . . , y k ) with k ≤ N to real values.

Let us consider P = P (θ|x 1 , . . . , x n , y 1 , . . . , y n ), the distribution of θ conditionally on x 1 , . . . , x n , y 1 , . . . , y n . Interestingly, one can see by induction on V n (see Eq. 19 and Eq. 20) that V n (x 1 , . . . , x n , y 1 , . . . , y n ) only depends on P if n < N , and on (P, x N ) if n = N . This implies that Opt can be reformulated as a function of P only:

x n+1 = Opt(P) = Opt(θ|x 1 , . . . , x n , y 1 , . . . , y n ) (23)
Interestingly, P is a distribution of fitness functions. This shows that a distribution of meta-models is sufficient, and not only one meta-model. Interestingly, some implementations, e.g. in [START_REF] Kern | Local meta-models for optimization using evolution strategies[END_REF], use populations of meta-models and not only one meta-model; also, methods like stepwise-uncertainty-reduction models use distributions of models instead of one model [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF][START_REF] Geman | An active testing model for tracking roads in satellite images[END_REF]. A distribution of models is richer than pointwise uncertainty as used in many surrogate models.

Application to Estimation of Distribution Algorithms (EDAs)

EDAs are intuitively satisfactory for expensive optimization as they iteratively improve a given distribution of probability for the optima [START_REF] Gelly | Resource-aware parameterizations of EDA[END_REF], in a way very similar to sequential design of experiments. We have studied conditions under which optimal algorithms do exist. We have seen optimal algorithms, that take decisions depending on the distribution of fitness functions conditionally on previously visited points. We here derive a particular case. We define an EDA as an algorithm depending only on the conditional distribution of probability of the optimum:

x n+1 = Opt(P (x * (θ)|x 1 , . . . , x n , y 1 , . . . , y n )) (24)
and we define the HEDA hypothesis as HEDA: ∀x, there exists only one θ such that x * (θ) = x.

We show that this implies the optimality of EDAs for any prior distribution of probability on fitness functions.

Theorem 5.3 (A sufficient condition for the optimality of EDAs). Consider a space of fitness-functions of the form F = {f (., θ); θ ∈ Ω}, and algorithms as

x n+1 = Opt(x 1 , . . . , x n , y 1 , . . . , y n ), y i = f (x i , θ) 6 (25)
Assume that for any θ, f (., θ) has one and only one minimum at x * (θ). Assume that θ follows some distribution of probability. Consider the criterion

L(x N , θ) = E θ x N -x * (θ) 2 . ( 26
)
If HEDA holds, then there is an optimal algorithm for criterion 26 of the form given in Eq. 24.

Interpretation: If for each x in the domain there is one and only one possible fitness function such that the optimum is at x, then there is an optimal algorithm which is an EDA.

Proof. We consider a space of fitnesses of the following form: F = {f (., θ); θ ∈ Ω} Assume that for each θ ∈ Ω, f (., θ) has one and only one minimum x * (θ). Thanks to Eq. 23, an optimal strategy for criterion 26 can be designed of the following form:

x n+1 = Opt (P (θ|x 1 , . . . , x n , y 1 , . . . , y n )) Therefore, if there exists a function k(.) such that θ = k(x * (θ)) for any θ (i.e., for any x * if there is only one function in F with minimum at x * ) then the optimal Opt() can be rewritten as follows

x n+1 = Opt (x 1 , . . . , x n , P (k(x * (θ))|x 1 , . . . , x n , y 1 , . . . , y n ))
which can be rewritten (within a change of variable in Opt):

x n+1 = Opt (x 1 , . . . , x n , P (x * (θ)|x 1 , . . . , x n , y 1 , . . . , y n ))
which is an EDA in the sense of Eq. 24.

UNLEO, a heuristic approximation of an optimal optimization algorithm using Upper Confidence Trees (UCT)

The principle of our approach (Theorem 5.2) is similar to Bayesian inference in machine learning. We here applied bayesian priors in optimization; this approach is inspired by the known optimality (without taking into account any computational cost but only the number of examples) of Bayesian inference for supervised learning, when a prior distribution is available. A main drawback is that Bayesian inference is often very expensive, and involves billiard algorithms, or Monte Carlo Markov Chains, for high dimensional integration. This drawback also holds for our approach: we can only use it when the computational cost of the fitness function is such that we can spend a lot of time in the choice of each iterate. The approach that we propose here is computationally very expensive, but can be implemented thanks to UCT as explained below, and the approach is realistic for expensive optimization problems (problems in which evaluating the objective function requires a long time). Its efficient approximation for non-expensive optimization problems is under work.

Implementation and experimental setup. We perform experiments with the algorithm presented in Theorem 5.2. The comparison-based nature of some optimization algorithms, in particular most evolutionary algorithms, provides optimal robustness for some criterion [START_REF] Gelly | Comparison-based algorithms are robust and randomized algorithms are anytime[END_REF]; we here adapt the algorithm in Theorem 5.2 to the comparison-based case. This reduces the assumptions underlying the algorithm: we only need a prior on the fitness functions up to a monotonic mapping. The algorithm is as follows:

Opt(x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) ∈ arg min

x E y=f (x,θ)|∀i≤n-1,f (xi,θ)=yi V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , y)
with V defined by backwards induction as follows: where σ(a 1 , . . . , a k ) is the ranking of a 1 , . . . , a k , i.e., σ(a 1 , . . . , a k ) = (sign(a ia j )) (i,j)∈{1,...,k} 2 and sign(x) = 1 if x > 0, sign(x) = -1 if x < 0 and sign(0) = 0.

V N (
The inputs (including parameters) of the optimizer are therefore:

• a random field on the domain;

• a number of iterations,

• a sequence of points x 1 , . . . , x n in the input domain;

• the ranking of the f (x 1 , θ), . . . , f (x n , θ) (as defined above).

The algorithm outputs x n+1 . The two first inputs are parameters of the algorithm (they do not change during an optimization run). We used the now famous UCT algorithm, which is a bandit-based Monte-Carlo planning algorithm [START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF], for approximately solving the dynamic programming problem. The family of functions is

x → f (x, θ) = 1 d i |x i -θ i | (hence x * (θ) = θ), for θ uniformly distributed in [0, 1] d .
The number of fitness evaluations is fixed to d + 4. We term the resulting algorithm UNLEO (UCT for non-linear expensive optimization). The domain is [0, 1] d .

Results. The UNLEO algorithm that we define, using UCT, is optimal only at the limit of a huge computational cost. The comparisons with random search, quasi-random search and the (1 + 1) Evolution Strategy ((1 + 1)-ES) are here only so that one can see that, with reasonnable computation times, one can have reasonnable results with UNLEO. A detailed comparisons with other techniques is a further work, beyond the scope of this paper.

We present the results in Table 1; all the computation times are per optimization run and averaged over 400 runs. The quasi-random search is performed by the Halton-sequence. Of course, this is not a fair comparison: UNLEO is computationally far more expensive than other algorithms. We only want here to point out the feasability of the approach. A further work is the comparison with other approaches, like e.g. EGO [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF]; this paper and this section only show the feasibility of the UCT approximation of our proved optimal optimization approach.

We see that the time is far from being prohibitive. Preliminar experiments with standard approximate dynamic programming were prohibitive; this confirms the known efficiency of UCT for implementing large scale dynamicprogramming problems (on this topic, see [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF][START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF][START_REF] Gelly | The parallelization of monte-carlo planning[END_REF], which have provided the first win of a computer against a professional human in the difficult game of Go).

Conclusion

In this paper we have investigated extensions of NFL results for countably infinite and continuous domains and derived applications to the design of optimal optimization algorithms. We have shown that a consequence of NFL theorems for a finite domain X is that for any algorithms a and b, for any m, the ran-

dom vectors Y (f 0 • π, m, a) = f 0 • π(x 1 ), . . . , f 0 • π(x m ) and Y (f 0 • π, m, b) = f 0 • π(x 1 ), . . . , f 0 • π(x m )
follow the same distribution for any objective function f 0 and π random permutation uniformly distributed among all permutations over X . We investigate how this property generalizes to countably infinite and continuous domains. For a non-trivial measurable objective function f 0 and π a measure-preserving random permutation, we define N FL(X , π, f 0 ) as the fact that for any integer m and any two optimization algorithms a and b, Y (f 0 • π, m, a) and Y (f 0 • π, m, b) follow the same distribution. For X = N we give non-trivial objective functions f 0 such that it is not possible to find a random permutation π such that N FL(N, π, f 0 ) holds. Those objective functions can be chosen such that they admit finite proper median. We also prove that there exists non-trivial f 0 (also with finite proper median) and a random permutation over N such that N FL(N, π, f 0 ) holds. We define a weaker form of NFL, GN FL that does not restrict the distribution of fitness to the form f 0 • π. For a non-trivial random fitness distribution f , with constant proper median, we define GN FL(X , f ) as the fact that for any integer m and any two optimization algorithms a and b, Y (f, m, a) and Y (f, m, b) follow the same distribution. Since there exists f 0 with finite proper median and π such that N FL(N, π, f 0 ) holds, the distribution

f = f 0 • π is such that GN FL(N, f ) holds. When X = [0, 1],
we show that it is not possible to find non-trivial random fitness f such that GN FL([0, 1], f ) holds. Our conclusions for NFL can be summarized in Table 2.

Assuming a prior distribution for the fitness distribution and a fixed number of iterates, Bellman's optimality principle allow us to derive optimal optimization algorithms. We define an EDA as an algorithm based on the conditional distribution of the optima. We show that EDAs are optimal if there exists a one-to-one mapping between the fitness-functions and the optima.

In some sense, NFL theorems are true for extremely hard finite cases (e.g. [START_REF] Droste | Perhaps not a free lunch but at least a free appetizer[END_REF][START_REF] Droste | Optimization with randomized search heuristics -The (A)NFL theorem, realistic scenarios, and difficult functions[END_REF][START_REF] Igel | A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions[END_REF]), but they are false for multi-objective optimization [START_REF] Corne | Some multiobjective optimizers are better than others[END_REF] and we show in this paper that they are also moderately true in infinite discrete cases and false in continuous spaces. The deep reason for this fact is that in "bigger" spaces (and continuous spaces are "very" big), random fields (and distributions of fitness functions are non-trivial random fields in the continuous case) necessarily have correlations [START_REF] Doob | Stochastic process measurability conditions[END_REF].

For our analysis, we have kept a finite horizon perspective and investigated non-asymptotic properties by looking at the distribution of Y (f, m, a) for finite values of m. We could reasonably wonder what would be true when considering asymptotic behaviors. We know that many randomized search heuristicsincluding the random search-asymptotically find the essential minimum of any fitness function, almost surely whereas some non-repeating algorithms (e.g. any non-repeating deterministic algorithms) fail for this asymptotic property. Therefore, some algorithms are better than others from the point of view of the asymptotic behavior.

Technically speaking, an interesting fact is that in our proofs, measurability plays a positive role and is not only a technical detail that should be used for the mathematical soundness: the continuous case directly relies on measurability. A possible future direction is to take into account the study of random spaces of fitnesses with some separability conditions [START_REF] Doob | Stochastic process measurability conditions[END_REF], where separability could be used to characterize "possible" random-fitness-functions. Hierarchies of optimization algorithms might be defined thanks to a proper formalization of continuous optimization problems as separable random fields.

An interesting point is that the idea of large memory costs, i.e., keeping all the information, is underlying all this paper. Optimal algorithms derived in this paper use all the archive of visited points to decide each new iterate. Optimal meta-model-based algorithms use a distribution of meta-models, and not only one meta-model. It is in accordance with the efficiency of population-based methods, BFGS with large memory, or EDAs with complex-representations of the past information like bayesian-networks, or also the covariance matrixadaptation memorizing past information [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF].

As a consequence, the application to the design of optimal optimization algorithms involves Monte-Carlo planning algorithms, and in particular the famous UCT algorithm, which is based on developing incrementally a large tree representing the possible futures, has a large memory cost. This paper originates in (i) a theory (the NFL family of results), (ii) an innovative research area (the Monte-Carlo planning algorithms), in the direction of the design of new innovative algorithms, with application to the expensive optimization framework. UNLEO is quite different from all existing algorithms and its main advantages are

• The optimality for a given prior (distribution of problems), a given number of iterates and a criterion quantifying the quality of an optimization run, at least asymptotically in the computation time.

• Very good practical results on artificial benchmarks. These benchmarks are rather preliminary, and further experimental works are required in order to quantify the efficiency of UNLEO, but the experiments in this paper show the feasability of UNLEO, without untractable computational costs.

• Possibility of taking into account particular cases in the design of the algorithm, e.g. we could use specific criteria. For example, we can consider the expected log-fitness, or the expected fitness for increasing the robustness or we can consider a fitness function with noise decreasing with the computational cost (i.e., the fitness value is noisy and the noise depends on the computational effort for reducing the noise as in Monte-Carlo integration) and develop an optimal algorithm for the point of view of the best fitness within some constraint on the overall computational cost instead of the number of iterates.

However, this algorithm is quite complex, is relatively expensive with a cost increasing quickly as the number of iterates increases and has only been tested yet on artificial problems.

  and equals to 1/|F|. Eq. 3 is an equivalent way to state that the distributions of c(Y (f, m, a)) and c(Y (f, m, b)) are the same and an equivalent formulation for Theorem 2.1 is Theorem 2.2 (NFL for c.u.p. subsets). Let F be a subset of Y X and f a random variable uniformly distributed on F. Then, for any two algorithms a and b, any m in {1, . . . , |X |} and any performance measure c, c(Y (f, m, a)) and c(Y (f, m, b)) follow the same distribution iff F is c.u.p.

  2, performance is measured using the distribution of c(Y (f, m, a)): two algorithms a and b are equivalent if the distributions of c(Y (f, m, a)) and c(Y (f, m, b)) are the same. Lemma 2.3 below shows that it is equivalent to requiring that the distributions of Y (f, m, a) and Y (f, m, b) are the same.

Theorem 4 . 1 (

 41 Continuous free-lunch). Let f be a random fitness function with values in R[0,1] .Then GN FL([0, 1], f ) does not hold.

4 . 5 .

 45 Step 2 to show (by countability) that there is at least one(a, b) ∈ Q 2 ∩ [0, 1]2 with a < b such that g -1 (1) has average density > p ′ in [a, b] with positive probability. We show (by Lemma 4.5) that for any a, b rationals in [0, 1], almost surely g -1 (1) ∩ [a, b] has Lebesgue measure p × (ba). The contradiction arises as Step 3 shows that g -1 (1) ∩ [a, b] has measure p ′ × (ba) and Step 4 shows that g -1 (1) ∩ [a, b] has measure p × (ba).

Theorem 4 . 4 (

 44 Lebesgue's density theorem). Consider A a measurable set of R d . Then, almost any x ∈ A verifies d(x, A) = 1.

4 .

 4 Consider g ′ (x) = g(a+x×(b-a)) defined on [0, 1]. Apply Lemma 4.5 to g ′ . Almost surely, by Lemma 4.5 g ′-1 (1) = {x ∈ [0, 1]; a + x(ba) ∈ E} has measure p. This implies almost surely g -1 (1) ∩ [a, b] has measure p(ba).

  x 1 , . . . , x N , y 1 , . . . , y N ) = E θ;σ(f (x1,θ),...,f (xN ,θ)=σ(y1,...,yN ) L(x N , θ) V n (x 1 , . . . , x n-1 , x, y 1 , . . . , y n-1 , y)

	For all n = 2, . . . , N
	V n-1 (x 1 , . . . , x n-1 , y 1 , . . . , y n-1 ) =
	inf x	E y=f (x,θ)|σ(f (x1,θ),...,f (xn-1,yn-1))=σ(y1,...,yn-1)

Table 1 :

 1 Results of UNLEO versus random-search, quasi-random search and the (1 + 1)-ES with one-fifth rule (isotropic, σ 0 = 1/3, σ n+1 = 2σ n for succesful mutations and σ n+1 = 2 -1/4 σ n otherwise). The random part in the experiments is due to (i) the random choice of the target function and (ii) the random part in the optimization algorithm. We see that the improvement over random-search is much better than the improvement from quasi-random-search versus randomsearch, in spite of the very small number of iterates. The (1 + 1)-ES does not perform well in this frugal case (only a few iterations). All results are averaged on 400 runs unless otherwise stated. As UCT is an approximate algorithm for stochastic dynamic programming, the results are presented for various values of the computation time; this computation time is controlled by the number of simulations in the Monte-Carlo exploration of the tree in UCT.

	Dimension 2 -6 points	Dimension 3 -7 points
	Algorithm	mean best	Algorithm	mean best
		fitness value		fitness value
	UNLEO		UNLEO
	(computation time)		(computation time)
	1.55 ms	13.50 ± 0.003	7.3 ms	15.86 ± 0.003
	8.025 ms	10.75 ± 0.003	14.05 ms	14.60 ± 0.003
	25.975 ms	9.91 ± 0.003	27.05 ms	14.00 ± 0.003
	91.85 ms	8.60 ± 0.002	53 ms	13.84 ± 0.003
	212.85 ms	7.89 ± 0.002	115.325 ms	12.88 ± 0.003
	432.975 ms	7.74 ± 0.002	202.725 ms	11.91 ± 0.003
	1 s	7.54 ± 0.002	5s	10.13 ± 0.002
	Random search	14.2 ± 0.06	Random search	16.4 ± 0.06
	Quasi-random search	11.8 ± 0.05	Quasi-random search	14.9 ± 0.05
	(1 + 1)-ES	14.8 ± 0.04	(1 + 1)-ES	17.2 ±
		Dimension 4 -8 points
		Algorithm	mean best
			fitness value
		UNLEO
		(computation time)
		24.725 ms	17.22 ± 0.002
		47.1 ms	16.32 ± 0.002
		239.35 ms	15.73 ± 0.002
		7.5s	12.44 ± 0.002
		Random search	18.0 ± 0.05
	Quasi-random search	16.7 ± 0.04
		(1 + 1)-ES	18.8 ± 0.04

Table 2 :

 2 Conclusions for the NFL.

The Kronecker delta function, δ, is defined as δ(a, b) = 1 if a = b and δ(a, b) = 0 otherwise.

We implicitly use here the standard σ-algebra on finite sets. With other σ-algebra, more restrictive definitions of a random variable could be stated.

Stochastic processes and random fields are formally very similar; however, the term "random field" is usually prefered when the dimension of X is greater than 1.

[START_REF] Billingsley | Probability and Measure[END_REF] A characteristic function of a set A is defined to be identically one on A and is zero elsewhere.

A rational segment is a closed segment included in [0, 1] with rational bounds and non-zero measure.

Note that all algorithms can be described as in this equation.

Acknowledgments

We thank the anonymous reviewers for their valuable comments and for pointing out the defect in the Proposition 3.1. We also thank Christian Igel and Marc Toussaint for their comments and encouragements.


Ida Marie
email: idamarie@cas.au.dk

S Lassen

Yuri Bizzoni
email: yuri.bizzoni@cc.au.dk

Telma Peura
email: tpeura@cc.au.dk

Mads Rosendahl Thomsen
email: madsrt@cc.au.dk

Kristoffer Nielbo

REVIEWER PREFERENCES AND GENDER DISPARITIES IN AESTHETIC JUDGMENTS *

Keywords: Aesthetic Judgement, Gender, Bias, Literary Review

Aesthetic preferences are considered highly subjective resulting in inherently noisy judgements of aesthetic objects, yet certain aspects of aesthetic judgement display convergent trends over time. This paper present a study that uses literary reviews as a proxy for aesthetic judgement in order to identify systematic components that can be attributed to bias. Specifically we find that judgement of literary quality in newspapers displays a gender bias in preference of male writers. Male reviewers have a same gender preference while female reviewer show an opposite gender preference. While alternative accounts exist of this apparent gender disparity, we argue that it reflects a cultural gender antagonism.

Introduction

Aesthetic judgements are notoriously complex and subject to considerable variation, because aesthetic objects are complex (ex. literature is a complex linguistic phenomenon that conveys information indirectly), aesthetic preferences are subjective (ex. readers have different aesthetic preferences), and there is a general lack of robust scientific measuring instruments (ex. there is no definitive metric to measure aesthetics or aesthetic judgments). Literary quality, for instance, can be considered one of the most subjective fields of evaluation, and variation mostly attributable to noise introduced by individual preferences. Yet the perception of literary quality from large amounts of readers over time does show convergent trends: communities tend to establish and update canons [START_REF] Guillory | Cultural capital: The problem of literary canon formation[END_REF]; specific texts and narratives manage to remain popular [START_REF] Stephens | Retelling stories, framing culture: traditional story and metanarratives in children's literature[END_REF] despite the changing of fashions and political phases and certain author names become eponymous of literary quality in different countries and throughout the social spectrum [START_REF] Bloom | The western canon: The books and school of the ages[END_REF]. Some facets of literary quality can be explained in terms of the literary content (ex. predictability of content, coherence of the narrative), while others depend on socio-cultural priors that introduce systematic variation in aesthetic judgements. It is the latter that are the object of this study, specifically the possible effects of gender on assessment of literary quality as an example of how aesthetic judgements can be biased by contextual factors.

There are two important caveats to consider. First, we are not claiming that variability in aesthetic judgement is undesirable, on the contrary, it facilitates expressive variation and counters aesthetic standardization as has been the norm under some authoritarian regimes [START_REF] Buch | Composing for the State: Music in Twentieth-Century Dictatorships[END_REF][START_REF] Frajese | Nascita dell'Indice: la censura ecclesiastica dal Rinascimento alla Controriforma[END_REF][START_REF] Herrero-Olaizola | The censorship files: Latin American writers and Franco's Spain[END_REF][START_REF] Kwon | Literature and art in north korea: Theory and policy[END_REF]. We are only interested in the systematic components of aesthetic judgement that can be attributed to bias, specifically gender bias, and approach this problem from the perspective of fairness challenges in classification of real-world data [START_REF] Miconi | The impossibility of" fairness": a generalized impossibility result for decisions[END_REF]. Second, it is not our intention to 'point fingers' or addressing specific individual (ex. specific reviewers) or institutional levels of biases (ex. specific outlets). Fairness challenges first and foremost concern a systemic level of biases, that is, macro-relations that are systematic and disadvantages groups of people based on their identity (gender, race, class, sexual orientation), while at the same time advantaging members of a dominant group. While at the individual level a bias effect may seem small or trivial, it is important to emphasize that systems of bias can result in rampant injustice [START_REF] Daniel Kahneman | Noise: A Flaw in Human Judgment[END_REF].

The problem of literary quality's subjective status becomes even more intriguing when we turn to the challenge of its computational assessment. Most studies assume the possibility of one one-dimensional ground truth by modelling literary quality as a single rating or class associated with a text [START_REF] Ferrer | Canonical values vs. the law of large numbers: The canadian literary canon in the age of big data[END_REF][START_REF] Wang | Success in books: predicting book sales before publication[END_REF][START_REF] Walsh | The goodreads 'classics': A computational study of readers, amazon, and crowdsourced amateur criticism[END_REF]. These ground truths are retrieved from various sources: literary critics, book sale numbers, bestseller lists, or crowd-sourced reader opinions. Such approaches have several limitations: Relying only on experts' judgment (ex. awards, prestigious reviews) biases the model to reflect their preferences, but striving for representativity by crowd-sourcing opinions ends up ignoring important differences in the readers' population. To properly understand the scientific value of these ground truths and develop standardized measures of quality, it is necessary to model possible sources of bias.

Recent studies have analyzed the impact of the gender of authors as well as of reviewers in literary reviews. [START_REF] Touileb | Gender and sentiment, critics and authors: a dataset of Norwegian book reviews[END_REF] investigates differences in sentiments in Norwegian book reviews and how literary reviewers are describing authors of same and opposite gender. Their findings show differences in how female and male book authors are positively or negatively described and that the gender of the critics influences this difference. In line with the findings in [START_REF] Thelwall | Reader and author gender and genre in goodreads[END_REF] for Goodreads reviews, the authors point out, that male critics deem crime novels written by female authors and sentimental romance novel by male authors as negative and suggest that this indicate that book reviews contain the social hierarchies tending to ascribe emotional traits to women. In the Goodreads reviews, differences are both found in preferences of types of books as well as within genres, meaning that when reviewers of both genders read and review books of the same genre, differences in grading are found between male and female reviewers. In addition, the results show that within the majority of genres, readers prefer books written by an author of their own gender.

In the greater context of circulation and reception of books, [START_REF] Squires | The Review and the Reviewer[END_REF] and [START_REF] Dane | Gender and Prestige in Literature[END_REF] address the role of both review and reviewer in the broader Anglophone literary field. The former point to an imbalance found in the British and Australian review scenes: Most book reviewers are men, and books reviewed are often written by men, resulting in books written by female authors are being treated like a niche. The latter offers a historical account of the gendered structure of the literary field and maps out how authors build their reputations and accumulate prestige in contemporary book publishing. By taking the historical perspectives of the literary field into account, it might not be surprising that gender disparities still exist. As the reception and judgment of books exist within a greater societal context where structural oppression occurs, signs of systemic inequality call for further investigation.

In other areas, studies have examined the role of gender in assessment situations. [START_REF] Macnell | What's in a name: Exposing gender bias in student ratings of teaching[END_REF] shows how students' ratings of instructors are biased towards a more positive assessment of male instructors compared to female instructors. By conducting their study in an online learning situation, the authors were able to disguise the gender identity of the instructors. The found bias was not dependent on the actual gender of the instructor, but on the perceived gender of the instructor. That allows for a conclusion that points out that the gender bias is not a result of gendered behavior of the instructors, but actual bias in the students, suggesting that a female instructor would have to work harder than a male to receive comparable ratings. In an academic context, a study from 2020 [START_REF] Stefanie | Dual-anonymization yields promising results for reducing gender bias: A naturalistic field experiment of applications for hubble space telescope time[END_REF] shows how female applicants were less likely than male applicants to receive access to resources (in terms of telescope time) when the review process was single-, rather than dual-anonymized. In particular, the findings indicate that male reviewers rated female applicants significantly worse than they rated male applicants before dual-anonymization was adopted, and after applying dual-anonymization, the gender bias was reduced. Similar results are shown in the hiring process of orchestra musicians [START_REF] Goldin | Orchestrating impartiality: The impact of" blind" auditions on female musicians[END_REF] and several studies have shed light upon the effect of gender in hiring processes [START_REF] Booth | Do employers discriminate by gender? a field experiment in female-dominated occupations[END_REF][START_REF] Michael S Cole | Interaction of recruiter and applicant gender in resume evaluation: a field study[END_REF].

Evidence of gender bias across domains, may indicate that similar structural dynamics are at play, and hence, not a unique gender bias evolving in the field of literature. 2 Methods

Data

The data set covers book reviews published in Danish media in the years 2010-2021. The data are retrieved from the online platform bog.nu's API which collects book reviews published in Danish media. This includes reviews written in national newspapers, literature magazines, online media as well as in personal blogs. See table 1 for a brief overview of the data set.

Grade Transformation and Estimation

As different media use different grading scale, the grades on bog.nu are transformed to a 100-point grading scale. This approach, however, results in a sparse distribution of grades as the use of the original grading scales maps onto different intervals on the 100 point scale. Instead of this naive approach, we have used the original grade and applied a linear transformation to map all grades to a shared 6-point scale 2 . Mapping from an a-b-point scale to a 1-6-point scale:

Y = (B -A) (x -a) (b -a) + A = (6 -1) (x -a) (b -a) + 1 = 5(x -a) b -a + 1 (1)
Figure 1 shows the distributions of grades in Danish Newspapers transformed to a shared 6-point scale.

Some media do not provide a grade in a given review, but only a qualitative review. Bog.nu does however provide a quantification of the review, which is estimated by a human editor. For reviews written in Danish newspapers this estimation procedure is used in less than 25% of the cases. Two important clarifications are needed: First, these estimates are made for both genders of both reviewers and authors. Secondly, to test the robustness of these estimates, the analysis below was performed both on the full data set and on the subset with original quantitative grades given in the reviews. We see that the same trends occur when excluding the reviews with estimated grades.

Gender Retrieval

The original data set from bog.nu does not contain gender for all authors and reviewers. We used a gendered name list to retrieve the missing gender variables. We are working with a binary understanding of gender, and we have used the API genderize.io that gives the probability of a name being either male or female, based on a data set of 250.000 names.

We are aware of the problems with this method and how it rules out other gender identities [START_REF] Dev | Harms of gender exclusivity and challenges in non-binary representation in language technologies[END_REF]. However, a binary understanding of gender is still dominant in Denmark, and to investigate existing structures a binary gender variable is relevant.

Looking at feature distributions in our data set, we see that both gender variables and grades differ across media types. As shown in Figure 2, we see a highly skewed gender distribution across media types: Male reviewers reviewing male authors are the dominant group in newspapers, whereas female reviewers reviewing female authors are the dominant group in the blogosphere. Furthermore, we have identified different 'grading behaviours' in newspapers and in blogs.

Hence, due to different distributions of gender as well as grades given across media types, we have in the rest of this study directed our attention towards newspapers.

Figure 2: The histogram shows the distribution of reviewer-and author gender across the media types blog, online media, and newspapers.

Model

In order to estimate the effect the relative effect of author and reviewer gender of author on reviewer assigned grade (six-point scale), we solve the following linear model:

y grade i = x i β author * x i β reviewer + ϵ i (2)
Where y i is the grade of review i, x i is the predictor value (gender) of review i, beta represents unknown parameters and ϵ is the error terms.

Results

Solving for y i (grade of review) in the model above with ordinary least square (OLS), we get the following results, see Table 2. The model and all contrasts are statistically significant (p < .0001) Conceptually, same gender (male * male, female * female) reviews spans the extreme values, while opposite gender (female * male, male * female) represent the middle of the distribution, see Fig. 3. Female reviewers reviewing female authors account for the on average lowest grade. Male reviewers reviewing male authors results in the highest grade, with a 0. Finally, as mentioned in section 2 and shown in figure 2, men account for the majority of reviewers in the newspapers. Men actually dominate in number of reviewers (63% are men) and out of these, reviews are 69% reviews by male authors. Fig. 3 shows the development over the years 2010-2021. Here we see that the fraction of female authors being reviewed are slightly increasing, but the fraction of male reviewers is relatively stable through the years.

Discussion

In line with the results in [START_REF] Thelwall | Reader and author gender and genre in goodreads[END_REF][START_REF] Touileb | Gender and sentiment, critics and authors: a dataset of Norwegian book reviews[END_REF], our results show that the gender of authors as well as of reviewers play a role in newspapers' literary reviews. In particular, the results above show that men review same gender more positive than opposite gender, and that women show the reverse pattern, that is, same gender is reviewed more negatively than opposite gender. A partial explanation of the behavior is that if males display a same gender preference and male reviewers make up the majority of newspaper reviewers, then the gender minority adapt to this preference and develop an same gender antagonism. At a more general level, the same gender preference of male in aesthetic judgement may reflect a cultural gender antagonism that follows a long historical trajectory. The female opposite gender preference is very likely to follow a the same cultural gender antagonism.

There are caveats to this interpretation. First, it is possible that the gender bias is confounded with expertise bias, that is that specific literary language leads to higher literary appreciation. If women in general write more genre literature, then the observed difference may stem from a difference in complexity of linguistic features. In order to resolve this, we would need genre classification for all reviewed books. Second, although the average differences in grades are highly significant, the effect size is not considerable (ex. 0.2 points on a six-point scale for same gender). This however begs the question, how large is a systematic differences supposed to be before it counts as a bias? We would argue that whenever we find systematic variation that co-insides with demographic variables, we are likely to see an indication of a relevant bias irrespective of the effect size. Conversely, if only a difference of a large magnitude (ex. two to three points on a six-point scale) were to count, then biases would only reflect common-sense propositions that most of us would share irrespective of their truth (ex. if women were on average reviewed two to three points lower, most of us would agree that they were worse writers).

The last caveat points to an important issue, we are not arguing that this or that newspaper, or for that matter all newspapers, follow an explicit exclusionary strategy formulated by male reviewers and editors. Whenever we make a judgement there are essentially two sources of errors, bias and noise. While noise is randomly distributed and lack a systematic explanatory mechanism, biases are systematic and can be explained in terms of a mechanism. Demographic biases often originate in a systemic oppression of minority groups. For the specific review cases, the results are likely to mirror existing oppressive structures in the society such as those found in [START_REF] Dane | Gender and Prestige in Literature[END_REF][START_REF] Macnell | What's in a name: Exposing gender bias in student ratings of teaching[END_REF][START_REF] Stefanie | Dual-anonymization yields promising results for reducing gender bias: A naturalistic field experiment of applications for hubble space telescope time[END_REF][START_REF] Goldin | Orchestrating impartiality: The impact of" blind" auditions on female musicians[END_REF][START_REF] Booth | Do employers discriminate by gender? a field experiment in female-dominated occupations[END_REF][START_REF] Michael S Cole | Interaction of recruiter and applicant gender in resume evaluation: a field study[END_REF]. We expect that majority groups in general will define norms and values that result in biased judgements irrespective of societal domain. Denmark is an excellent example of how more or less explicit biases persist in the face of societal countermeasures (ex. equal rights, , parity policies) and in general high gender equality.

Figure 1 :

 1 Figure 1: Histogram over grades given in Danish newspapers, after grades are transformed into shared 6-point likert scale

Figure 3 :

 3 Figure 3: The left-hand figure is a point plot showing the average grades in each of the four gender combinations. The lines indicate the standard deviations with a confidence interval of 95%. The stacked areas plot on the right shows the percentage distribution over the years 2010-2021 of the four different gender combinations.

Table 1 :

 1

	Nr of reviews	57 369
	Male reviewer	18 958
	Female reviewer	28 984
	Unknown	9 427
	Nr of different titles	14 647
	Male author	8 056
	Female author	6 591
	Nr of reviews by media type
	Newspapers	22 131
	Blogs	16 791
	Online media	10 635
	Blog-like websites	3 456
	Regional newspapers	2 622
	Weekly magazines	1 566
	Professional magazines	168

An overview of the dataset presented in this paper. The category Online media includes (literary) sites that fall between online newspapers and personal blogs.

Table 2 :

 2 2 average grade increase. Opposite gender reviews is statistically speaking indistinguishable, but they differ on average 0.1 grade point from from same gender scoring. Results for an OLS predicting grade based on the gender combination: reviewer and author. The intercept is the gender combination female reviewer and female author. The t-test shows that all results are statistically significant.

	Gender combination (reviewer * author) Average grade	SD	t	p < |t|	CI95%
	Intercept [female * female]	3.9820	0.015 267.502 0.0001 [3.953, 4.011]
	female * male	0.0881	0.022	3.924	0.0001 [0.044, 0.132]
	male * female	0.1140	0.021	5.382	0.0001 [0.072, 0.156]
	male * male	0.2084	0.018 11.523 0.0001 [0.173, 0.244]

It should be noted that most six-point scales have become the standard in many review outlets.

Acknowledgments

This was was supported in part by the Velux Foundation for the Fabula-Net project and DeiC Interactive HPC with id DeiC-AU1-L-000011. The authors would like to thank Bog.nu for access to data.