The Sampling-and-Learning Framework:
A Statistical View of Evolutionary Algorithms
Yang Yu∗, Hong Qian

arXiv:1401.6333v2 [cs.NE] 11 Apr 2014

National Key Laboratory for Novel Software Technology
Nanjing University, Nanjing 210023, China

Abstract
Evolutionary algorithms (EAs), a large class of general purpose optimization algorithms inspired from the natural phenomena, are widely used in various industrial optimizations and often show excellent performance. This
paper presents an attempt towards revealing their general power from a statistical view of EAs. By summarizing a large range of EAs into the sampling-and-learning framework, we show that the framework directly
admits a general analysis on the probable-absolute-approximate (PAA) query complexity. We particularly focus
on the framework with the learning subroutine being restricted as a binary classification, which results in the
sampling-and-classification (SAC) algorithms. With the help of the learning theory, we obtain a general upper
bound on the PAA query complexity of SAC algorithms. We further compare SAC algorithms with the uniform
search in different situations. Under the error-target independence condition, we show that SAC algorithms can
achieve polynomial speedup to the uniform search, but not super-polynomial speedup. Under the one-side-error
condition, we show that super-polynomial speedup can be achieved. This work only touches the surface of the
framework. Its power under other conditions is still open.
Key words: Evolutionary Algorithms, Computational Complexity of Algorithms, Stochastic Optimization,
Heuristic Search

1. Introduction

In many practical optimization problems, the objective functions are hidden or too complicated to be analyzed.
Under this kind of circumstances, direct optimization algorithms are appealing, which follows the trial-anderror style with some heuristics. Evolutionary algorithms (EAs) [3] are a large family of such algorithms. The
family includes genetic algorithms [17], evolutionary programming [26], evolutionary strategies [5], and also
covers other nature-inspired heuristics including particle swarm optimization [25], ant colony optimization [11],
estimation of distribution algorithms [29], etc.

∗ Corresponding

author
Email addresses: yuy@lamda.nju.edu.cn (Yang Yu), qianh@nju.edu.cn (Hong Qian)

Preprint submitted for review

January 22, 2018

Theoretical studies of EAs have been developed rapidly in the recent decades, particularly noticeable of the
blooming of running time analysis [32, 2, 20]. With the development of several analysis techniques (e.g. [18,
43, 9, 37]), EAs have been theoretically investigated on problems from simple synthetic ones (e.g. [13]) to
combinatorial problems (e.g. [35]) as well as NP-hard problems (e.g. [44]). During these analyses, effects
of EAs components have been disclosed [42], including the crossover operators (e.g. [21, 31, 10, 33]), the
population size (e.g. [23, 36, 40, 6]), etc. Measures of the performance also have developed to cover the
approximation complexity (e.g. [19, 16, 44, 28]), the fixed-parameter complexity (e.g. [27, 38]), the complexity
under fixed-budget computation [22], etc. While most of these analyses studied instances of EAs on problem
cases, general performance analysis may even be more desired, as the application of EAs is nearly unlimited.
The famous No-Free-Lunch Theorem [41] used a quite general framework of EAs and gave a general conclusion
that any two EAs are with the same performance (at least on discrete domains) given no prior knowledge of the
problem distribution, of which the general running time is exponential [43]. When the complexity of a problem
class is bounded, a general convergence lower bound can be derived for a class of EAs [15]. For more general
EAs, the Black-Box model can derive the best possible performance [12, 1, 30, 8]. We have learned that a
general performance analysis relies on a general framework of EAs.
It has been noticed that various implementations of EAs share a common structure that consists of a cycle
of sampling and model building [47]. In this work, we propose to study the sampling-and-learning (SAL)
framework. EAs commonly employ some heuristic to reproduce solutions, which is captured by the sampling
step of SAL; and they also distinguish the quality of the reproduced solutions to guide the next sampling (e.g.,
genetic algorithms remove a portion of the worst solutions), which is captured by the learning step of SAL. The
SAL framework can simulate a wide range of EAs as well as other heuristic search methods, by specifying the
sampling and the learning strategies.
We evaluate this framework by the probable-absolute-approximate (PAA) query complexity. PAA complexity
counts the number of fitness evaluations before reaching to an approximate solution with a probability, which
is close to the intuitive evaluation of EAs in practice. We show that the SAL framework immediately admits
a general PAA upper bound. For a specific version of SAL that uses classification algorithms, named the SAC
algorithms, we obtain a tighter PAA upper bound by incorporating the learning theory results. Further comparing with the uniformly random search, we disclose that, under the error-target independence condition, SAC
algorithms can polynomially reduce the complexity of the uniform search, but not super-polynomially; while
the one-side-error condition further allows a super-polynomial improvement. This study shows that the classification error is an important effecting factor, which was not noticed before. We also notice that a good learning
algorithm may not be necessary for a good SAL algorithm.
The rest of this paper is organized as follows: Section II introduces the SAL framework. In Section III, we
compare the SAC algorithms, a specific version of the SAL framework, with the uniform search. Finally,
Section IV concludes the paper.
2

2. The Sampling-and-Learning Framework

In this paper, we consider general minimization problems f . We always denote X as the whole solution space
which an algorithm will search among. In the analysis of this paper, we consider X ⊆ Rn is a compact set (in
the Euclidean space, the compact set is equivalent to the bounded and closed set) and f : X → R is a continuous

function. Thus there must exist at least one solution x∗ ∈ X such that f (x∗ ) = minx∈X f (x). We use D to
R
denote sub-regions of X and define |D| = D 1dx. For the sake of convenience for the analysis, we assume
without loss of generality that |X| = 1 since X is a bounded and closed set. Denote Dα = {x ∈ X|f (x) ≤ α}

for any scaler α, UX as the uniform distribution over X, T and D as the probability distributions. Besides, by
poly(· · · ), we mean the set of all polynomials with the related variables, and by superpoly(· · · ), we mean
the set of all functions that grow faster than any function in poly(· · · ) with the related variables.
Definition 1 (Minimization Problem)

A minimization problem consists of a continuous solution space X and a continuous function f : X → R,

where X ⊆ Rn and X is a compact set. The goal is to find a solution x∗ ∈ X such that f (x∗ ) ≤ f (x) for all
x ∈ X.
Since X is a compact set and f is a continuous function, there must exist one solution x′ ∈ X such that
f (x′ ) = maxx∈X f (x). Namely, f is bounded in [f (x∗ ), f (x′ )]. Therefore, in the rest of the paper, we assume
without loss of generality that the value of f is bounded in [0, 1], i.e., ∀x ∈ X : f (x) ∈ [0, 1]. Given an
arbitrary function g with bounded value range over the input domain, the bound can be implemented by a simple
normalization f (x) =

g(x)−g(x∗ )
maxx′ g(x′ )−g(x∗ ) .

Thus we assume in the rest of this paper that every minimization

problem has its minimum value 0.
In real-world applications, we expect EAs to achieve some good enough solutions with a not quite small probability, which corresponds to approximation (e.g. [44]) and probabilistic performance (e.g. [45]). Combining
the two, we study the probable-absolute-approximate (PAA) query complexity, which is the number of fitness
evaluations that an algorithm takes before reaching an approximate quality, as defined in Definition 2. The PAA
query complexity closely reflects our intuitive evaluation of EAs in practice.
Definition 2 (Probable-Absolute-Approximate Query Complexity)

Given a minimization problem f , an algorithm A, and any 0 < δ < 1 as well as any approximation level α∗ > 0,
then the probable-absolute-approximate (PAA) query complexity is the number of calls to f (·) such that, with
probability at least 1 − δ , A finds a solution x with f (x) ≤ α∗ .

2.1. The General Framework
Most EAs share a common trial-and-error structure with several important properties:

3

a) directly access the solution space, generate solutions, and evaluate the solutions;
b) the generation of new solutions depends only on a short history of past solutions;
c) both “global” and “local” heuristic operators are employed to generate new solutions.

We present a sampling-and-learning (SAL) framework in Algorithm 1 to capture these properties. The SAL
framework starts from a random sampling in Step 1 like all EAs. Steps 2 and 13 record the best-so-far solutions
throughout the search. SAL follows a cycle of learning and sampling stages. In Step 7, it learns a hypothesis ht
(i.e., a mapping from X to R) via the learning algorithm L. Note that the learning algorithm allows to take the
current data set Tt , the last data set Tt−1 , and the last hypothesis ht−1 into account. Different EAs may make
different use of them. Step 8 initializes the sample set for the next iteration. The sample set can be initialized
as an empty set, or to preserve some good solutions from the previous iteration. In Steps 9 to 12, it samples
from the distribution transformed from the hypothesis as well as from the whole solution space balanced by a
probability. The distribution Tht implies the potential good regions learned by ht .
It should be noted that the SAL framework is not a concrete optimization algorithm but an abstract summary
of a range of EAs, nor does the learning stage of the framework imply an accurate learning. We explain in
the following how we could mimic several different EAs by the SAL framework. It is noticeable that the
explanation is not a rigorous proof, but an intuitive illustration that the SAL framework can correspond to
various implementations.
The genetic algorithms (GAs) [17] deal with discrete solution spaces consisting of solutions represented as a
vector of vocabulary. The element-wise mutation operator changes every element of a solution to a randomly
selected word from the vocabulary with a probability. Converting this operation probability to the probability
of generating a certain solution, let Pm (x′ |x) be the probability of generating the solution x′ from x via the
′

′

element-wise mutation, thus Pm (x′ |x) = ( |V p|−1 )kx −xkH (1 − p)n−kx −xkH , where n is the length of the

solution, |V | is the vocabulary size, k · kH is the Hamming distance, and p is the probability of changing
the element that is commonly

1
n.

It is easy to calculate that Pm (x′ |x) is

constant (and otherwise Pm (x′ |x) =

1
superpoly(n) ).

1
poly(n)

only when kx′ − xkH is a

Given any set of solutions S = {x1 , x2 , . . . , xm }, we

divide the search space into two sets that Xpoly (S) = {x ∈ X | ∃x′ ∈ S : kx − x′ kH = O(1)} and
Xsuper (S) = X − Spoly (S). SAL can simulate the GA as that, for every population S of the GA, SAL

learns the hypothesis h that circles the area Xpoly (S), and uses Th as Th (x) =

P

P

x∈S

Pm (x′ |x)
P
′′
x∈S Pm (x |x)

x′′ ∈Xpoly (S)

for solutions in Xpoly (S). And for the area Xsuper (S), SAL uses the uniform distribution to approximate the
sampling with super-polynomially small probability. In this way, SAL can mimic the behavior of the GA. We
have discussed a simplified GA. Most GAs also employ the crossover operators, which is a kind of local search
operator and thus the resulting distribution can be compiled into the local distribution. Many GAs also employ
a probabilistic selection, which can be simulated by selecting the initial solution set St in the same way.

4

Algorithm 1 The sampling-and-learning (SAL) framework
Input:
α∗ > 0: Approximation level
T ∈ N+ : Number of iterations

m0 , . . . , mT ∈ N+ : Number of samples

λ ∈ [0, 1]: Balancing parameters
L: Learning algorithm
T : Distribution transformation of hypothesis
Procedure:
1:

Collect S0 = {x1 , . . . , xm0 } by i.i.d. sampling from the uniform distribution over X

2:

x̃ = argminx∈S0 f (x)

3:

Initialize the hypothesis h0

4:

T0 = ∅

5:

for t = 1 to T do

6:

Construct Tt = {(x1 , y1 ), . . . , (xmt−1 , ymt−1 )},
where xi ∈ St−1 and yi = f (xi )

7:

ht = L(Tt , Tt−1 , ht−1 , t), the learning step

8:

Initialize St from Tt

9:

for i = 1 to mt do 

Tht , with probability λ
Sample xi from

UX , with probability 1 − λ
St = St ∪ {xi }

10:

11:
12:

end for

13:

x̃ = argminx∈St ∪{x̃} f (x)

14:

end for

15:

return x̃

It has been argued that model-based search algorithms including the estimation of distribution algorithms
(EDAs) [29], the ant colony optimization algorithms (ACOs) [11], the cross-entropy method [34] can be unified
in the sampling and model building framework [47], which respectively correspond to the sampling and learning
steps in the SAL framework. The particle swarm optimization algorithms (PSOs) [25] is particularly interesting
since the simulation is perhaps the most sophisticated. A PSO algorithm maintains a set of “flying” particles
each with a location (representing a solution) and a velocity vector. The location of a particle in the next iteration
is determined by its current location and current velocity, and the velocity is updated by the current velocity and
the locations of the “globally” and “personally” best particles. To simulate a PSO, a SAL algorithm needs to
use the initial hypothesis resulting the same sampling distribution as that from the initial velocity. Let St be an

5

ordered set to contain the globally best particle and the personally best particles in Step 8. The learning algorithm in the SAL algorithm can be set to utilize the current data set and the last data set to recover the velocity,
and utilize the last hypothesis and the globally and personally best particles recorded through St to generate the
new hypothesis that simulates the movement of particles in the PSO.
Overall, the SAL framework captures the trial-and-error structure as well as the global–local search balance,
while leaving the details of the local sampling distribution being implemented by different heuristics.
The SAL framework directly admits a general upper bound of the PAA query complexity, as stated in Theorem
1.
Theorem 1

For any minimization problem f and any approximation level α∗ > 0, with probability at least 1 − δ , a SAL

algorithm will output a solution x with f (x) ≤ α∗ using mΣ number of queried samples bounded from above
by

o
n
1 XT
1
,
mPrht
O m0 +max
ln ,
t=1
(1 − λ)Pru + λPrh δ
R
where Pru = Dα∗ UX (x) dx is the success probability of uniform sampling,
Prh =

PT

t=1 mt · Prht
=
PT
t=1 mt

PT

t=1

R
mt · Dα∗ Tht (x) dx
PT
t=1 mt

is the average success probability of sampling from the learnt hypothesis, mPrht is the required sample size
realizing Prht , and Dα∗ = {x ∈ X|f (x) ≤ α∗ }.
Proof. m0 is the initial sample size. In every iteration, we need mPrht samples to realize the probability Prht
(generally the higher the probability the larger the sample size, but it depends on the concrete implement of the
PT
algorithm), thus t=1 mPrht number of samples is naturally required. We prove the rest of the bound.
Let’s consider the probability that after T iterations, the SAL algorithm outputs a bad solution x such that
f (x) > α∗ . Since the x is the best solution among all sampled examples, the probability is the intersection of
events that every step of the sampling does not generate such a good solution.
1. For the sampling from uniform distribution over the whole solution space X, the probability of failure is
1 − Pru .
2. For the sampling from the learnt hypothesis ht according to the distribution Tht , the probability of failure is
denoted as 1 − Prht .
Since every sampling is independent, we can expand the probability of overall failures, i.e., for any solution x
belongs to the all sampled examples,
Pr(f (x) > α∗ )

6

= (1 − Pru )m0 ·

mt 
T X
Y
mt
(1 − λ)i λmt −i (1−Pru )i (1−Prht )mt −i
i
t=1 i=0
YT
m
(1 − (1 − λ)Pru − λPrht ) t
= (1 − Pru )m0
t=1
YT
e−((1−λ)Pru mt +λPrht mt )
≤ e−Pru ·m0
t=1

=e

−(Pru ·m0 +(1−λ)

≤ e−((1−λ)

PT

t=1

PT

t=1

Pru mt +λ

Pru mt +λ

= e−((1−λ)Pru +λPrh )

PT

PT

t=1

t=1

mt

PT

t=1

Prht mt )

Prht mt )

,

where the first inequality is by (1 − x) ≤ e−x for x ∈ [0, 1].
In order that Pr(f (x) > α∗ ) < δ, we let e−((1−λ)Pru +λPrh )


O (1−λ)Pr1 +λPr ln δ1 .
u

PT

t=1

mt

< δ, which solves that

h

PT

t=1

mt =

2.2. The Sampling-and-Classification Algorithms
To further unfold the unknown term Prh in Theorem 1, we focus on a simplified version of the SAL framework
that employs a classification algorithm in the learning stage. We call this type of algorithms as the samplingand-classification (SAC) algorithms. In the learning stage of a SAC algorithm, as described in Algorithm 2,
the learning algorithm first uses a threshold to transform the data set into a binary labeled data set, and then
invokes the classification algorithm to learn from the binary data set. sign[·] is defined as sign[v] = +1 if v ≥
0 and − 1 if v < 0. Note that SAC algorithms use the current data set T in the learning algorithm, but not the
last data set T ′ and the last hypothesis h′ . Putting Algorithm 2 into the framework of Algorithm 1, we always

set St = ∅ for SAC, and Th will be some distribution over the positive area of h.
Algorithm 2 Learning sub-procedure for the sampling-and-classification (SAC) algorithms
Input:
T, T ′, h′ , t: The input variables
α1 > . . . > αt : Preset threshold parameters
C: Classification algorithm
Procedure:
1:

Construct B = {(x1 , z1 ), . . . , (x|T | , z|T | )} from that,
for all i and all (xi , yi ) ∈ T , zi = sign[αt − yi ]

2:

h = C(B)

3:

return h

By these specifications, we can have a general PAA performance for SAC algorithms. According to Theorem
1, we need to estimate a lower bound of Prh , i.e., how likely the distribution Tht will lead to a good solution.
7

Recall Dα = {x ∈ X|f (x) ≤ α} for any scaler 0 < α < 1. Denote Dh = {x ∈ X|h(x) = +1} for any
hypothesis h, UDh as the uniform distribution over Dh , and DKL as the Kullback-Leibler (KL) divergence.
KL-divergence measures how difference one distribution departs from another one. For probability distributions

R +∞ 
P and Q of two continuous random variables, DKL (P ||Q) = −∞ ln p(x)
q(x) p(x)dx, where p(x) and q(x) are

the probability densities of P and Q. Let ∆ denote the symmetric difference operator of two sets. We have a
lower bound of the success probability as in Lemma 1.
Lemma 1

For any minimization problem f , any approximation level α∗ > 0, any hypothesis h, the probability that a
solution sampled from an arbitrary distribution Th defined on Dh will lead to a solution in Dα∗ is lower bounded
as
|Dα∗ ∩ Dh |
Prh ≥
− |Dα∗ ∩ Dh |
|Dh |

r

1
DKL (Th kUDh )
2

Proof. Let I[·] denote the indicator function, namely, I[true] = 1 and I[false] = 0. The proof starts from
the definition of the probability,
Z
Th (x) · I[x ∈ Dα∗ ]dx
Prh =
Dh
Z
(Th (x) − UDh (x) + UDh (x)) · I[x ∈ Dα∗ ]dx
=
Dh
Z
|Dα∗ ∩ Dh |
(Th (x) − UDh (x)) · I[x ∈ Dα∗ ]dx
+
=
|Dh |
Dh
Z
|Dα∗ ∩ Dh |
≥
− sup |Th (x′ )−UDh (x′ )|·I[x ∈ Dα∗ ]dx
|Dh |
D x′
rh
Z
1
|Dα∗ ∩ Dh |
≥
I[x ∈ Dα∗ ]dx
−
DKL (Th kUDh )
|Dh |
2
Dh
r
|Dα∗ ∩ Dh |
1
=
− |Dα∗ ∩ Dh |
DKL (Th kUDh ),
|Dh |
2
where the last inequality is by Pinsker’s inequality.
We cannot pre-determine Dh , but we know that h is derived by a binary classification algorithm from a data set
which is labeled according to the threshold parameter α. For the binary classification, we know that the generalization error, which is the expected misclassification rate, can be bounded above by the training error, which
is the misclassification rate in the seen examples, as well as the generalization gap involving the complexity of
the hypothesis space [24], as in Lemma 2. The V C(H) is the VC-dimension measuring the complexity of H.
Lemma 2 ([24])

Let H = {h : X → {−1, +1}} be the hypothesis space containing a family of binary classification functions
and V C(H) = d, if there exist m samples i.i.d. from X according to some fixed unknown distribution D, then,
∀ h ∈ H and ∀ 0 < η < 1, the following upper bound holds true with probability at least 1 − η :
q

ǫD ≤ ǫ̂D + 8m−1 d log (2emd−1 ) + log (4η −1 )
8

where ǫD is the expected error rate of h over D and ǫ̂D is the error rate in the sampled examples from D, and
when ǫ̂D = 0,

ǫD ≤ 2m−1 d log (2emd−1 ) + log (2η −1 ) .
Again by Pinsker’s inequality, we know that the error ǫD under the distribution D can be converted to the error
ǫU under the uniform distribution, as
ǫU ≤

≤

1−

q

ǫ̂D +

ǫD
1
2 DKL (DkU)

q

8m−1 d log (2emd−1 ) + log (4η −1 )
q
,
1 − 12 DKL (DkU)

where we only take the event that the generalization inequality holds with probability 1 − η into account. For
simplicity, we denote the right-hand part as Ψm,η
ǫ̂D ,d,DKL (DkU ) , which decreases with m and η, and increases with
ǫ̂D , d, and DKL (DkU).
We can use this inequality to eliminate the Dh in Lemma 1. In every iteration of SAC algorithms, there are mt
samples collected, which make the error of ht bounded.
Theorem 2

For any minimization problem f , any constant 0 < η < 1, and any approximation level α∗ > 0, the average
success probability of sampling from the learnt hypothesis of any SAC algorithm is lower bounded as
!
r
T
|Dα∗ | − 2Ψǫ̂mDt ,η,d,DKL (Dt kUX )
1
1−η X
t
mt
Prh ≥ PT
− |Dα∗ |
DKL (Tht kUDht ) ,
|Dαt | + Ψǫ̂mDt ,η,d,DKL (Dt kUX )
2
t=1 mt t=1
t

where Dt = λTht + (1 − λ)UX is the sampling distribution at iteration t, ǫ̂Dt is the training error rate of ht , d
is the VC-dimension of the learning algorithm.
Proof. By set operators,
|Dα∗ ∩ Dht | = |Dα∗ ∪ Dht | − |Dα∗ ∆Dht |
≥ |Dα∗ ∪ Dht | − |Dα∗ ∆Dαt | − |Dαt ∆Dht |
= |Dα∗ ∪ Dht | − |Dα∗ ∆Dαt | − ǫUX ,t
= |Dα∗ ∪ Dht | + |Dα∗ | − |Dαt | − ǫUX ,t ,
where ∆ is the symmetric difference operator of two sets and ǫUX ,t is the expected error rate of ht under UX .
The first inequality is by the triangle inequality, and the last equation is by that Dα∗ is contained in Dαt .
Since |Dht | − |Dαt | ≤ |Dht ∆Dαt | = ǫUX ,t , we can bound |Dht | as |Dαt | + ǫUX ,t ≥ |Dht | ≥ |Dαt | − ǫUX ,t .
9

Now, we can apply Lemma 1, and the success probability of sampling from Dht is lower bounded as
r
|Dα∗ ∩ Dht |
1
Prht ≥
− |Dα∗ ∩ Dht |
DKL (Tht kUDht )
|Dht |
2
r
1
1
≥
· (|Dα∗ ∪ Dht | + |Dα∗ | − |Dαt | − ǫUX ,t ) − |Dα∗ | ·
DKL (Tht kUDht )
|Dht |
2
r
1
1
· (|Dht | + |Dα∗ | − |Dαt | − ǫUX ,t ) − |Dα∗ | ·
DKL (Tht kUDht )
≥
|Dht |
2
r
1
|Dα∗ | − 2ǫUX ,t
∗
− |Dα |
DKL (Tht kUDht ).
≥
|Dαt | + ǫUX ,t
2
Substituting this lower bound and the probability 1−η of the generalization bound into Prh obtains the theorem.

Combining Theorem 1 and Theorem 2 results an upper bound on the sampling complexity of SAC algorithms.
Although the expression looks sophisticated, it can still reveal relative variables that generally effect the complexity. One could design various distributions for Th to sample potential solutions, however, without any a
priori knowledge, the uniform sampling is the best in terms of the worst case performance. Meanwhile, without
any a priori knowledge, a small training error at each stage from a learning algorithm with a small VC-dimension
can also improve the performance.

3. SAC Algorithms v.s. Uniform Search

When EAs are applied, we usually expect that they can achieve a better performance than some baselines.
The uniform search can serve as a baseline, which searches the solution space always by sampling solutions
uniformly at random. In other words, the uniform search is the SAL algorithm with λ = 0. In this section, we
study the performance of SAC algorithms relative to the uniform search.
SAC algorithms will degenerate to uniform search if λ = 0. Thus, it is easy to know that the PAA query
complexity of uniform search is


1
1
.
· ln
Θ
Pru
δ
Contrasting this with Theorem 1, we can find that how much a SAC algorithm improves from the uniform search
depends on the average success probability Prh that relies on the learnt hypothesis. A SAC algorithm is not
always better than the uniform search. Without any restriction, Prh can be zero and thus the SAC algorithm is
worse. We are then interested in investigating the conditions under which SAC algorithms can accelerate from
the uniform search.

10

3.1. A Polynomial Acceleration Condition
Condition 1 (Error-Target Independence)

In SAC algorithms, for any t and any approximation level α∗ > 0, when sampling a solution x from UX , the
event x ∈ Dht ∆Dαt and the event x ∈ Dα∗ are independent.
We call SAC algorithms that are under the error-target independence condition as SACI algorithms. The condition is defined using the independence of random variables. From the set perspective, it is equivalent with
|Dα∗ ∩ (Dαt ∆Dht )| = |Dα∗ | · |(Dαt ∆Dht )|.
Under the condition, we can bound from below the probability of sampling a good solution, as stated in Lemma
3.
Lemma 3

For SACI algorithms, it holds for all t that
|Dα∗ ∩ Dht |
|Dα∗ |(1 − ǫUX ,t )
,
≥
|Dht |
|Dαt | + ǫUX ,t

where ǫUX ,t is the expected error rate of ht under UX .
Proof. For the numerator,
|Dα∗ ∩ Dht | = |Dα∗ | − |Dα∗ ∩ (Dαt ∆Dht )|
= |Dα∗ | − |Dα∗ | · |Dαt ∆Dht |
≥ |Dα∗ |(1 − ǫUX ,t ),
where the first equation is by Dα∗ ⊆ Dαt , and the second equality is by the error-target independence condition.
For the denominator, we consider the worst case that all errors are out of Dht and thus |Dht | ≤ |Dαt | + ǫUX ,t .

Similar to Theorem 2, we can bound from below the average success probability of sampling from the positive
area of the learnt hypothesis,
 |D ∗ |(1 − ǫ
1 − η XT
UX ,t )
α
− |Dα∗ |
mt
Prh ≥ PT
t=1
|Dαt | + ǫUX ,t
t=1 mt

r


1
DKL (Tht kUDht ) .
2

We compare the uniform search with the SACI algorithms using uniform sampling within Dht , i.e., DKL (Tht kUDht ) =
0, which is an optimistic situation. Then by Lemma 3,
 |D ∗ |(1 − ǫ

1 − η XT
α
UX ,t )
mt
Prh ≥ PT
.
t=1
|Dαt | + ǫUX ,t
t=1 mt
11

By plugging ǫUX ,t ≤

1−

ǫ Dt

√1

= Q · ǫDt , where ǫDt is the expected error rate of ht under the
q
and Q = (1 − 12 DKL (Dt kUX ))−1 ,

2 DKL (Dt kUX )

distribution Dt = λUDht + (1 − λ)UX

 |D ∗ |(1 − Q · ǫ ) 
1 − η XT
Dt
α
mt
Prh ≥ PT
.
t=1
|
+
Q
·
ǫ
|D
D
α
m
t
t
t
t=1

(1)

1
) ignoring other variables and logarithmic
Note from Lemma 2 that, the convergence rate of the error is Õ( m
1
terms from Lemma 2. We assume that SACI uses learning algorithms with convergence rate Θ̃( m
). We then find

that such SACI algorithms cannot exponentially improve the uniform search in the worst case, as Proposition 1.
Proposition 1
1
), ∀f, α∗ > 0 and 0 < δ < 1, with probability at least
Using learning algorithms with convergence rate Θ̃( m

1 − δ , if the query complexity of the uniform search is superpoly( α1∗ , n, δ1 ), the query complexity of SACI

algorithms is also superpoly( α1∗ , n, δ1 ) in the worst case.

Proof. The query complexity of the uniform search being superpoly( α1∗ , n, 1δ ) implies that
1
1
1
1
=
= superpoly( ∗ , n, ).
Pru
|Dα∗ |
α
δ
For the SACI algorithms, if we ask the learning algorithm to produce a classifier with error rate

1
,
superpoly( α1∗ ,n, 1δ )

it will require superpoly( α1∗ , n, 1δ ) number of samples in the worst case, so that the proposition holds. To
avoid this, we can only expect the error rate to be

1
poly( α1∗ ,n, δ1 )

in order to keep the query complexity at each

iteration small.
Meanwhile, we can only have T = poly( α1∗ , n, 1δ ) iterations otherwise we will have super-polynomial number
of samples.
Following the optimistic case of Eq.(1), since Q ≥ 1, we consider one more optimistic situation that Q = 1. Let
η = 0.5. Even though, in the worst case that |Dht | = |Dαt | + QǫDt , we can have that
Prh =

2

1
PT

t=1

mt

XT

t=1

mt

1

 |D ∗ |(1 − ǫ ) 
Dt
α
|Dαt | + ǫDt
1

1
1 superpoly( α1∗ ,n, δ1 )
=
1 poly( α∗ , n, δ )
1
1
poly( α∗ , n, δ )
poly( 1 ,n, 1 )
1
=
,
superpoly( α1∗ , n, 1δ )

α∗

δ

where it is noted that as long as ǫDt = poly( α1∗ , n, δ1 ) the value of |Dαt | cannot affect the result. Then substi-

tuting Prh into Theorem 1 obtains the total samples mΣ = superpoly( α1∗ , n, 1δ ) that proves the proposition.

12

The proposition implies that the SACI algorithms can face the same barrier as that of the uniform search. Nevertheless, the SACI algorithms can still improve the uniform search within a polynomial factor. We show this
by case studies.
On Sphere Function Class:
Given the solution space Xn = {(x1 , . . . , xn ) | ∀i = 1, . . . , n : xi ∈ [0, 1]}, the Sphere Function class is
∗

x ,n
n
Fsphere
= {fsphere
|∀x∗ ∈ Xn } where

n

∗

x ,n
fsphere
(x) =

1
1X
2
(xi − x∗i )2 .
kx − x∗ k2 =
n
n i=1
∗

x ,n
Obviously, |Xn | = 1, fsphere
∈ [0, 1] is convex, and the optimal value is 0. It is important to notice that
n
R∞
the volume of a n-dimensional hyper-sphere with radius r is Γ(πn 2+1) rn , where Γ(s) = 0 ts−1 e−t dt, so that
2
n

n √
|Dα | = Γ(πn 2+1) (nα)n/2 = Cn (α)n/2 for any α > 0, where Cn = Θ (2πe) 2 / πn , since the radius leading
2
√
2
x∗ ,n
to fsphere
(x) = n1 kx − x∗ k2 ≤ α is nα.

Note that Pru = |Dα∗ | = Cn (α∗ )n/2 > (α∗ )n/2 . It is straightforward to obtain that, minimizing any function
n
in Fsphere
using the uniform search, the PAA query complexity with approximation level α∗ > 0 is, with

probability at least 1 − δ,


1 n 1
2
O ( ∗ ) ln
.
α
δ
We assume Lsphere is a learning algorithm that searches in the hypothesis space Hn consisting of all the hyperspheres in Rn to find a sphere that is consistent with the training data, and meanwhile the sphere satisfies the

error-target independence condition. Then a SAC algorithm using Lsphere is a SACI algorithm. We simply
assume that the search of the consistent sphere is feasible. Note that V C(Hn ) = n + 1.
Lemma 4

For any ht , denote ǫUX as the error rate of ht under the uniform distribution over X and ǫDt as the error rate of
ht under the distribution Dt = λUDht + (1 − λ)UX , then it holds that
ǫUX ≤

1
ǫD ,
1−λ t

where λ ∈ [0, 1] and UDht is the uniform distribution over Dht .
+
Proof. Let I[·] be the indicator function and D6= be the area where ht makes mistakes. We split D6= into D6=
=
−
+
= D6= \D6=
. We can calculate the probability density that Dt (x) = λ |D1h | +(1−λ)
D6= ∩Dht and D6=
t

+
for any x ∈ D6=
, and Dt (x) = (1 − λ)

ǫDt =
=

Z

ZX

|X\Dht |
1
|X|
|X\Dht |

−
1
= (1 − λ) |X|
for any x ∈ D6=
. Thus,

Dt (x)I[ht makes mistake on x]dx
Z
Z
Dt (x)dx =
Dt (x)dx +
Dt (x)dx

D6=

+
D6=

−
D6=

13

|Dht | 1
|X| |Dht |

1
≥
(1 − λ)
dx +
+
|X|
D6=
Z

Z

−
D6=

(1 − λ)

1
dx
|X|

= (1 − λ)ǫUX ,
which proves the lemma.
We then obtain the PAA complexity as in Proposition 2.
Proposition 2
n
For any function in Fsphere
and any approximation level α∗ > 0, SACI algorithms can achieve the PAA query

complexity, for any n ≥ 2,


1 n−1
1
1
1
2
O ( ∗)
log √ ∗ (ln + n log √ ∗ )
α
δ
α
α
with probability at least 1 − δ .
Proof. We choose αt =

1
2t

for all t, and use the number of iterations T to approach |DαT | =

p
|Dα∗ |, for the
1
n

approximation level α∗ . Solving this equation with the sphere volume results in T = log (C√nα)∗ . We let the
SACI algorithm run T = log √1α∗ number of iterations. We assume log √1α∗ is an integer for simplicity, which
does not affect the generality.
In iteration t, using Lsphere , we want the error of the hypothesis ht , ǫDt , to be

1
2t .

Since the Lsphere produces a

hypothesis with zero training error, from
ǫDt =


1
≤ 2m−1 d log (2emd−1 ) + log (2η −1 ) ,
2t

we can solve the required sample size with η being a constant,


n
1
mt ≤ mT = O(nT 2T ) = O √ ∗ log √ ∗
α
α
using the inequality log x ≤ cx − (log c + 1) for any x > 0 and any c > 0. We thus obtain


O √nα∗ (log √1α∗ )2 .
We then follow Eq.(1). We use uniform sampling within Dht , then Q =
mT number of samples in every iteration, λ = 0.5 and η = 0.5, we have
Prh ≥

Xlog √1 ∗  |Dα∗ |(1 − QǫD ) 
1
t
α
1
t=1
|Dαt | + QǫDt
2 log √α∗

n
1 − 2 21t
Cn (α∗ ) 2 Xlog √1α∗
≥
n
1
t=1
2 log √α∗
Cn ( 21t ) 2 + 2 21t
n

Xlog √1 ∗
1
Cn (α∗ ) 2
α
≥
2t
1
t=2
2 log √α∗ 2(Cn + 2)
=

1
n

 (α∗ ) n−1
2
Cn (α∗ ) 2 ( √α∗ − 2)
.
=
Ω
2 log √1α∗ (Cn + 2)
log √1α∗

14

1
1−λ .

PT

t=1

mt =

Letting the SACI algorithms use

So we obtain the query complexity from Theorem 1

n 1 n−1
o
1
1 n
1
O m0 + max ( ∗ ) 2 log √ ∗ ln , √ ∗ (log √ ∗ )2
α
δ
α
α
α


n−1
which is O ( α1∗ ) 2 log √1α∗ (ln 1δ + n log √1α∗ ) using a constant m0 and the max is upper bounded by plus.
We can see that the SACI algorithms can accelerate the uniform search by a factor near

√1 / log √1 .
α∗
α∗

The

closer the approximation, the more the acceleration.
On Spike Function Class
As modeling EAs, SAL algorithms should be expected to be applied on the complex problems, while the Sphere
Function class only consists of convex functions. Inherited from EAs, SAL algorithms can handle problems
with some local optima. We show this by comparing SACI with the uniform search on the Spike Function class
defined below.
3k+2
3k−1 3k
Define regions A1,k = [ 3k
20 , 20 ] where 0 ≤ k ∈ N ≤ 6 and A2,k = ( 20 , 20 ) where 1 ≤ k ∈ N ≤ 6, and

define g(x) over [0, 1] that


x − k , x ∈ A1,k
10
g(x) =

−x + k , x ∈ A2,k
5

∗

x ,n
n
= {fspike
|∀x∗ ∈
Let Xn = [− 21 , 12 ]n be the n-dimensional solution space. The Spike Function class is Fspike

Xn }, where, for all x ∈ Xn
1
x∗ ,n
fspike
(x) = g( √ kx − x∗ k2 ).
n
n
. For any α > 0, we can
It is easy to know minx∈Xn f (x) = 0 and maxx∈Xn f (x) ≤ 1 for any f ∈ Fspike

n √
bound the area |Dα | ∈ [Cn αn , Cn (3α)n ], where Cn = Θ (2πe) 2 / πn .

The Spike functions are non-convex and non-differentiable with some local optima, as depicted in Figure 1.

n
Minimizing any function in Fspike
using the uniform search, the PAA query complexity with approximation

level α∗ > 0 is, with probability at least 1 − δ,


1
1
O ( ∗ )n ln
.
α
δ

We configure the SACI algorithm to use the learning algorithm Lspike that searches the smallest sphere covering
all the samples labeled as positive, of which the VC-dimension is n + 1. Note that since the function is nonconvex, the Lspike may output a sphere that also covers some negative examples, and thus with some training

n
error. Using this SACI algorithm to minimize any member in the function class Fspike
, we obtain the PAA query

complexity as in Proposition 3.
15

0.4

f(x)

0.3
0.2
0.1
0
−1

−0.5

0

0.5

1

x
0,1
(x) in [−1, 1].
Figure 1: The landscape of function fspike

Proposition 3
n
For any function in Fspike
and any approximation level α∗ > 0, SACI algorithms can achieve the PAA query

complexity


1
1
1
1
1 
,
O ( ∗ )n− 2 log √ ∗ ln + n log √ ∗
α
δ
α
α
with probability at least 1 − δ .

n
Proof. For any function in Fspike
, we note that the function is convex in Dα when α is smaller than 0.05.
1
2t ,

so that when t ≥ 5, the SACI algorithm with Lspike will deal with a convex function and
p
thus the training error is zero. We use the number of iterations T to achieve |DαT | = |Dα∗ |. Since |Dα | ∈
We set αt =

1
2n

)
√n
. We let the SACI algorithm run T = log √1α∗ number of
[Cn αn , Cn (3α)n ], we can obtain T ≥ log 3(C
α∗

iterations and assume that log

√1
α∗

is an integer.

In iteration t ≥ 5, we want the error of the hypothesis ht , ǫDt , to be 21t . Since the training error can be


PT
zero, we can solve the required sample size mt ≤ mT = O √nα∗ log √1α∗ . We thus obtain t=1 mt =


O √nα∗ (log √1α∗ )2 .
We then follow Eq.(1). We use uniform sampling within Dht , then Q =
mT number of samples in every iteration, λ = 0.5 and η = 0.5, we have
Prh ≥
≥
≥
=

Xlog √1 ∗  |Dα∗ |(1 − QǫD ) 
1
t
α
1
t=5
|Dαt | + QǫDt
2 log √α∗

1 − 2 21t
Cn (α∗ )n Xlog √1α∗
1
t=5
2 log √α∗
Cn ( 23t )n + 2 21t
15
Xlog √1 ∗
Cn (α∗ )n
α
16
2t
1
t=5
2 log √α∗ 3Cn + 2

2
5
 (α∗ )n− 21 
15 Cn (α∗ )n √α∗ − 2
=
Ω
.
32 log √1 ∗ 3Cn + 2
log √1 ∗
α

α

16

1
1−λ .

Letting the SACI algorithm use

So we obtain the query complexity from Theorem 1


1 n− 1
1
1
1 
O ( ∗ ) 2 log √ ∗ ln + n log √ ∗
α
δ
α
α
as the max is upper bounded by plus.

We observe from the proof that the non-convexity can result in non-zero training error for the learning algorithms
in SACI algorithms, and thus the search process is interfered. But as long as the non-convexity is not quite severe,
like the Spike Functions, SACI algorithms are not significantly affected, and can still be better than the uniform
search by a factor near

√1 / log √1 .
α∗
α∗

3.2. A Super-Polynomial Acceleration Condition
We have shown in Proposition 1 that SACI algorithms using common classification algorithms cannot superpolynomially improve from the uniform search in the worst case. An interesting question is therefore raised that
when the super-polynomial improvement is possible.
Learned from the proof of Proposition 1, a straightforward way is to use a powerful classification algorithm
with exponentially improved sample complexity, i.e., Õ(ln 1ǫ ), so that only a polynomial number of samples is
required to achieve a super-polynomially small error. Several active learning algorithms can do this in some
circumstances (e.g. [7, 39]). Applying active learning algorithms needs a small modification of SACI . In
iteration t, instead of sampling from the uniform distribution in Dht , the sampling is guided by the classifier.
Nevertheless, the achieved error is still evaluated under the original (uniform) distribution. Using such learning
algorithms denoted as Lln
sphere , we achieve Proposition 4 showing a super-polynomial acceleration from the
uniform search on Sphere Functions.
Proposition 4
n
For any function in Fsphere
and any approximation level α∗ > 0, SACI algorithms using Lln
sphere can achieve

the PAA query complexity, for any n ≥ 2,


1
1
1
O log ∗ (ln + n log ∗ )
α
δ
α
with probability at least 1 − δ .
Proof. We choose αt =

1
2t

for all t, and use the number of iterations T to approach |DαT | = |Dα∗ |, for the
1
n

approximation level α . Solving this equation with the sphere volume results in T = log (Cαn∗) . We let the
∗

SACI algorithm run T = log α1∗ number of iterations. We assume log α1∗ is an integer for simplicity, which does
not affect the generality.
In iteration t, using Lln
sphere , we want the error of the hypothesis ht , ǫDt , to be

1
.
2tn/2

Since the Lln
sphere has

the sample complexity O(ln 1ǫ ), we ask for a hypothesis with zero training error, which requires the sample size

mt = O(tn) = O(n log

1
α∗ )

with η being a constant.
17

We thus obtain


 
1 2
.
m
=
O
n
log
∗
t
t=1
α

PT

Following Eq.(1), we use uniform sampling within Dht , then Q =

1
1−λ .

Letting the SACI algorithms use mT

number of samples in every iteration, λ = 0.5 and η = 0.5, we have
Xlog α1∗  |Dα∗ |(1 − QǫD ) 
1
t
Prh ≥
1
t=1
|Dαt | + QǫDt
2 log α∗
n
n
1 − 2( 21t ) 2
Cn (α∗ ) 2 Xlog α1∗
≥
n
n
t=1
2 log α1∗
Cn ( 21t ) 2 + 2( 21t ) 2
n
Xlog α1∗ 1
Cn (α∗ ) 2
1
≥
n
1 2(C + 2)
t=2
2 log α∗
( 21t ) 2
n

n
n
n
 1 
Cn (α∗ ) 2 ( α1∗ ) 2 1 − (2α∗ ) 2
.
=
Ω
≥
2(Cn + 2)
2 log α1∗
log α1∗

So we obtain the query complexity from Theorem 1, letting m0 be a constant,


n
1
1 o
1
O max log ∗ ln , n(log ∗ )2
α
δ
α

which is O log α1∗ (ln 1δ + n log α1∗ ) .

Meanwhile, we are more interested in exploring conditions under which the super-polynomial improvement
is possible without requiring such powerful learning algorithms. For this purpose, we find the one-side-error
condition.
Condition 2 (One-Side-Error)

In SAC algorithms, for any t and any x ∈ X , if x ∈ Dht ∆Dαt , it must hold that x ∈ Dαt .
The condition implies that ht can only make false-negative errors, i.e., wrongly classifies positive samples
(inside Dαt ) as negative, but no false-positive errors. One practical way to approach this condition is through
the cost-sensitive classifiers [14, 46] with a very large mis-classification cost for negative samples. We call SACI
algorithms that are further under this condition as SACII algorithms.
Lemma 5

For SACII algorithms, it holds for all t that |Dht | ≤ |Dαt |.
Proof. Note that for training ht we label the samples from Dαt as positive and label the rest as negative. Since
ht only makes false-negative errors, i.e., every error is in Dαt , we have Dht ⊆ Dαt , which implies the lemma.

Lemma 5 shows that the one-side-error condition controls the size |Dht | to be bounded by |Dαt |. Thus we can
refine Lemma 3 as Lemma 6.
Lemma 6

For SACII algorithms, it holds for all t that
|Dα∗ ∩ Dht |
|Dα∗ |(1 − ǫUX ,t )
≥
,
|Dht |
|Dαt |
18

where ǫUX ,t is the expected error rate of ht under UX .
Proof. Since the SACII algorithm is also a SACI algorithm, incorporating Lemma 5 into Lemma 3 proves the
lemma.
We assume that L+
sphere is a learning algorithm that not only behaviors like Lsphere but also results a hypothesis
satisfying the one-side-error condition. Then a SACI algorithm using L+
sphere is a SACII algorithm. We again

assume that L+
sphere is feasible, of which V C(Hn ) = n + 1. We then use this SACII algorithm on the Sphere
Function class, on which SACI algorithms bear a super-polynomial PAA complexity, and obtain Proposition 5.
Proposition 5
n
For any function in Fsphere
and any approximation level α∗ > 0, SACII algorithms can achieve the PAA query

complexity


1
1
O log ∗ (ln + n) ,
α
δ
with probability at least 1 − δ .
Proof. By Lemma 6,
|Dα∗ |(1 − QǫDt )
|Dα∗ ∩ Dht |
≥
,
|Dht |
|Dαt |
where ǫDt is the error of ht under its original distribution Dt , and Q is the resulting factor of changing the
distribution.
1
2t

Let αt =

for all t, and use the number of iterations T to achieve |DαT | = |Dα∗ |, for the approximation
1
n

level α . Solving this equation with the sphere volume results in T = log (Cαn∗) . We let the SACII algorithm
∗

run T = log α1∗ number of iterations. We assume log α1∗ is an integer for simplicity, which does not affect the
generality.
+
1
In iteration t, using L+
sphere , we want the error of the hypothesis ht , ǫDt , to be a constant 2 . Since Lsphere

produces a hypothesis with zero training error, to achieve ǫDt ≤

PT
We thus obtain t=1 mt = O n log α1∗ .

1
2

it requires the number of samples in O(n).

We then follow Eq.(1). We use uniform sampling within Dht , then Q =
mT number of samples in every iteration, λ =
Prh ≥
≥
=

1
3

and η = 0.5, we have

Xlog α1∗  |Dα∗ |(1 − QǫD ) 
1
t
1
t=1
|Dαt |
2 log α∗
Xlog α1∗  1 |Dα∗ | 
1
4

2 log α1∗
∗

t=1

n
2

Cn (α )
8 log α1∗

Xlog α1∗
t=1

|Dαt |

1
n
Cn ( 21t ) 2

19

1
1−λ .

Letting the SACII algorithm use


n
n
 1 
Cn (α∗ ) 2 ( α1∗ ) 2 − 1
=
Ω
.
≥
Cn
8 log α1∗
log α1∗
So we obtain from Theorem 1 the query complexity of the SACII algorithm, letting m0 be a constant,



1
1
1
,
O max log ∗ ln , n log ∗
α
δ
α

which is O log α1∗ (ln 1δ + n) .
Proposition 5 shows a super-polynomial improvement from the complexity of the uniform search. It is interesting to note that we only ask for a random guess classification (i.e., error rate 21 ) in the proof of Proposition
5.

4. Discussions and Conclusions

This paper describes the sampling-and-learning (SAL) framework which is an abstract summary of a range of
EAs. The SAL framework allows us to investigate the general performance of EAs from a statistical view. We
show that the SAL framework directly admits a general upper bound on the PAA query complexity, which is the
number of fitness evaluations before an approximate solution is found with a probability.
Focusing on SAC algorithms, which are SAL algorithms using classification learning algorithms, we give a
more specific performance upper bound, and compare with uniform random search. We find two conditions that
drastically effect the performance of SAC algorithms. Under the error-target independence condition, which
assumes that the error of the learned classifier in each iteration is independent with the target approximation area,
the SAC algorithms can obtain a polynomial improvement over the uniform search, but not a super-polynomial
improvement. We demonstrate the improvement using the Sphere Function class consisting of convex functions
as well as the Spike Function class consisting of non-convex functions. Further incorporating the one-side-error
condition, which assumes that the classification only makes false-negative errors, the SAC algorithms can obtain
a super-polynomial improvement over the uniform search.
On the one hand, our results show that the property of classification error in SAC algorithms greatly impacts the
performance, which was never touched in previous studies, as far as we know. We expect the work could guide
the design of novel search algorithms. On the other hand, how to satisfy the conditions is a non-trivial practical
issue.
In the case study on the Sphere Function class, we find that a learning error rate no more than the random guess
is sufficient to achieve a super-polynomial improvement under the conditions. This implies that an accurate
learning algorithm may not be necessary for a good SAC algorithm. It is interesting that a recent work [4] also
noticed that a learnable concept is not necessary for the trial-and-error search with a computation oracle.
20

In this paper, the SAC algorithms are analyzed in continuous domains, while the main body of theoretical
studies of evolutionary algorithms focuses on the discrete domains. Thus understanding the performance of
SAC algorithms in discrete domains is our future work. Moreover, in the SAC algorithms analyzed in this
paper, the learning algorithm does not utilize the last hypothesis or the last data set. It would be interesting to
investigate whether considering them will bring any significant difference.

Acknowledgements

This work was supported by the National Science Foundation of China (61375061) and the Jiangsu Science
Foundation (BK2012303).

References
[1] G. Anil and R. P. Wiegand. Black-box search by elimination of fitness functions. In Proceedings of the 10th
ACM SIGEVO International Workshop on Foundations of Genetic Algorithms (FOGA’09), pages 67–78,
Orlando, FL, 2009.
[2] A. Auger and B. Doerr. Theory of Randomized Search Heuristics - Foundations and Recent Developments.
World Scientific, Singapore, 2011.
[3] T. Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996.
[4] X. Bei, N. Chen, and S. Zhang. On the complexity of trial and error. In Proceedings of the 45th Annual
ACM Symposium on Theory of Computing (STOC’13), pages 31–40, Palo Alto, CA, 2013.
[5] H.-G. Beyer and H.-P. Schwefel. Evolution strategies: A comprehensive introduction. Natural Computing,
1(1):3–52, 2002.
[6] T. Chen, J. He, G. Sun, G. Chen, and X. Yao. A new approach for analyzing average time complexity of
population-based evolutionary algorithms on unimodal problems. IEEE Transactions on Systems, Man,
and Cybernetics, Part B: Cybernetics, 39(5):1092–1106, 2009.
[7] S. Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. Journal of
Machine Learning Research, 10:281–299, 2009.
[8] B. Doerr and C. Winzen. Towards a complexity theory of randomized search heuristics: Ranking-based
black-box complexity. In A. Kulikov and N. Vereshchagin, editors, Computer Science – Theory and Applications, volume 6651 of Lecture Notes in Computer Science, pages 15–28. Springer Berlin Heidelberg,
2011.
21

[9] B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorithmica, 64:673–697, 2012.
[10] B. Doerr, D. Johannsen, T. Kötzing, F. Neumann, and M. Theile. More effective crossover operators for
the all-pairs shortest path problem. Theoretical Computer Science, 471:12–26, 2013.
[11] M. Dorigo, V, Maniezzo, and A. Colorni. Ant system: Optimization by a colony of cooperating agents.
IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1):29–41, 1996.
[12] S. Droste, T. Jansen, K. Tinnefeld, and I. Wegener. A new framework for the valuation of algorithms for
black-box optimization. In Proceedings of the 7th ACM SIGEVO International Workshop on Foundations
of Genetic Algorithms (FOGA’02), pages 253–270, Torremolinos, Spain, 2002.
[13] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical
Computer Science, 276(1-2):51–81, 2002.
[14] C. Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint
Conference on Artificial Intelligence (IJCAI’01), pages 973–978, Seattle, WA, 2001.
[15] H. Fournier and O. Teytaud. Lower bounds for comparison based evolution strategies using VC-dimension
and sign patterns. Algorithmica, 59(3):387–408, 2011.
[16] T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by
randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617–633,
2010.
[17] D. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley,
Reading, MA, 1989.
[18] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial
Intelligence, 127(1):57–85, 2001.
[19] J. He and X. Yao. An analysis of evolutionary algorithms for finding approximation solutions to hard
optimisation problems. In Proceedings of 2003 IEEE Congress on Evolutionary Computation (CEC’03),
pages 2004–2010, Canberra, Australia, 2003.
[20] T. Jansen. Analyzing Evolutionary Algorithms. Springer-Verlag, Berlin, Germany, 2013.
[21] T. Jansen and I. Wegener. The analysis of evolutionary algorithms – A proof that crossover really can help.
Algorithmica, 34(1):47–66, 2002.
[22] T. Jansen and C. Zarges. Fixed budget computations: A different perspective on run time analysis. In
Proceedings of the 14th International Conference on Genetic and Evolutionary Computation Conference
(GECCO’12), pages 1325–1332, Philadelphia, PA, 2012.

22

[23] T. Jansen, K. Jong, and I. Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13(4):413–440, 2005.
[24] M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA, 1994.
[25] J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International
Conference on Neural Networks (ICNN’95), volume 4, pages 1942–1948, Perth, Australia, 1995.
[26] J. Koza. Genetic programming as a means for programming computers by natural selection. Statistics and
Computing, 4(2):87–112, 1994.
[27] S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754–771, 2013.
[28] X. Lai, Y. Zhou, J. He, and J. Zhang. Performance analysis of evolutionary algorithms for the minimum
label spanning tree problem. IEEE Transactions on Evolutionary Computation, 2014.
[29] P. Larrañaga and J. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
[30] P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623–642, 2012.
[31] P. K. Lehre and X. Yao. Crossover can be constructive when computing unique input output sequences.
In Proceedings of the 7th International Conference on Simulated Evolution and Learning, pages 595–604,
Melbourne, Australia, 2008.
[32] F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their
Computational Complexity. Springer-Verlag, Berlin, Germany, 2010.
[33] C. Qian, Y. Yu, and Z.-H. Zhou. An analysis on recombination in multi-objective evolutionary optimization. Artificial Intelligence, 204:99–119, 2013.
[34] R. Y. Rubinstein and D. P. Kroese. The Cross-Entropy Method: A Unified Approach to Combinatorial
Optimization, Monte-Carlo Simulation, and Machine Learning. Springer-Verlag, New York, NY, 2004.
[35] J. Scharnow, K. Tinnefeld, and I. Wegener. Fitness landscapes based on sorting and shortest paths problems. In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature
(PPSN’02), pages 54–63, Granada, Spain, 2002.
[36] T. Storch. On the choice of the parent population size. Evolutionary Computation, 16(4):557–578, 2008.
[37] D. Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. IEEE
Transactions on Evolutionary Computation, 17(3):418–435, 2013.

23

[38] A. M. Sutton and F. Neumann. A parameterized runtime analysis of evolutionary algorithms for the euclidean traveling salesperson problem. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12), Toronto, Canada, 2012.
[39] W. Wang and Z.-H. Zhou. Multi-view active learning in the non-realizable case. In J. D. Lafferty, C. K. I.
Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 2388–2396. Curran Associates, Inc., 2011.
[40] C. Witt. Population size versus runtime of a simple evolutionary algorithm. Theoretical Computer Science,
403(1):104–120, 2008.
[41] D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary
Computation, 1(1):67–82, 1997.
[42] X. Yao. Unpacking and understanding evolutionary algorithms. In J. Liu, C. Alippi, B. Bouchon-Meunier,
G. Greenwood, and H. Abbass, editors, Advances in Computational Intelligence, volume 7311 of Lecture
Notes in Computer Science, pages 60–76. Springer Berlin Heidelberg, 2012.
[43] Y. Yu and Z.-H. Zhou. A new approach to estimating the expected first hitting time of evolutionary algorithms. Artificial Intelligence, 172(15):1809–1832, 2008.
[44] Y. Yu, X. Yao, and Z.-H. Zhou. On the approximation ability of evolutionary optimization with application
to minimum set cover. Artificial Intelligence, (180-181):20–33, 2012.
[45] D. Zhou, D. Luo, R. Lu, and Z. Han. The use of tail inequalities on the probable computational time of
randomized search heuristics. Theoretical Computer Science, 436:106–117.
[46] Z.-H. Zhou and X.-Y. Liu. Training cost-sensitive neural networks with methods addressing the class
imbalance problem. IEEE Transactions on Knowledge and Data Engineering, 18(1):63–77, 2006.
[47] M. Zlochin, M. Birattari, N. Meuleau, and M. Dorigo. Model-based search for combinatorial optimization:
A critical survey. Annals of Operations Research, 131:373–395, 2004.

24

