arXiv:1706.02887v1 [cs.NE] 9 Jun 2017

Global Convergence of the (1+1) Evolution Strategy
Tobias Glasmachers
Institute for Neural Computation
Ruhr-University Bochum, Germany
tobias.glasmachers@ini.rub.de

Abstract
We establish global convergence of the (1+1)-ES algorithm, i.e., convergence to a critical
point independent of the initial state.
The analysis is based on two ingredients. We establish a sufficient decrease condition
for elitist, rank-based evolutionary algorithms, formulated for an essentially monotonically
transformed variant of the objective function. This tool is of general value, and it is therefore
formulated for general search spaces. To make it applicable to the (1+1)-ES, we show that
the algorithm state is found infinitely often in a regime where step size and success rate are
simultaneously bounded away from zero, with full probability.
The main result is proven by combining both statements. Under minimal technical preconditions, the theorem ensures that the sequence of iterates has a limit point that cannot be
improved in the limit of vanishing step size, a generalization of the notion of critical points
of smooth functions. Importantly, our analysis reflects the actual dynamics of the algorithm
and hence supports our understanding of its mechanisms, in particular success-based step
size control.
We apply the theorem to the analysis of the optimization behavior of the (1+1)-ES on
various problems ranging from the smooth (non-convex) cases over different types of saddle
points and ridge functions to discontinuous and extremely rugged problems.

1

Introduction

Global convergence of an optimization algorithm refers to convergence of the iterates to a critical
point independent of the initial state—in contrast to local convergence, which guarantees this
property only for initial iterates in the vicinity of a critical point.1 For example, many first order
methods enjoy this property (Gilbert and Nocedal, 1992), while Newton’s method does not. In
the realm of direct search algorithms, mesh adaptive search algorithms are known to be globally
convergent (Torczon, 1997).
Evolution strategies (ES) are a class of randomized search heuristics for direct search in continuous domains. The covariance matrix adaptation evolution strategy (CMA-ES) by Hansen and Ostermeier
(2001) and its many variants mark the state-of-the-art. The algorithm maintains a multivariate
Gaussian search distribution parameterized by mean and covariance matrix, which allows for
adaptation to linear distortions of the search space, effectively resembling second order methods.
1

Some authors refer to global convergence as convergence to a global optimum. We do not use the term in
this sense.

1

A “global step size” parameter is maintained in addition. Adaptation of the step size is crucial,
since it enables linear convergence on scale invariant problems (e.g., convex quadratic objective
functions), while algorithms without step size adaptation converge as slowly as pure random
search. Furthermore, being rank-based methods, ESs are invariant to strictly monotonic transformations of objective values. ESs tend to be robust and suitable for solving difficult problems
(rugged and multimodal fitness landscapes), a capacity that is often attributed to the above
invariance properties.
To date, convergence guarantees for ESs are scarce. Some results exist for convex quadratic
problems, which essentially implies local convergence on twice continuously differentiable functions.
Jägersküpper (2003, 2005, 2006a,b) analyzed the (1+1)-ES2 on the sphere function as well as
general convex quadratic functions. His analysis ensures
 linear convergence with overwhelming
ε
probability, i.e., with a probability of 1 − exp Ω(d ) for some ε > 0, where d is the problem
dimension. In other words, the analysis is asymptotic in the sense d → ∞, and for fixed (finite)
dimension d ∈ N, no concrete value or bound is attributed to this probability. A dimensiondependent convergence rate of Θ(1/d) is obtained.
The analysis by Auger (2005) is based on the stability of the Markov chain defined by the
normalized state m/σ. Since the chain is shown to converge to a stationary distribution and the
problem is scale-invariant, linear convergence or divergence is obtained, with full probability.
There exists sufficient empirical evidence for convergence, however, this is not ensured by the
result.
The global convergence analyzed by Akimoto et al. (2010) is closest to the present paper.
The analysis is extremely general in the sense that it covers a broad range of algorithms including CMA-ES, with the sole condition of successful divergence on a linear function. Its main
restriction is that it applies only to continuously differentiable functions, a problem class where
gradient-based methods are often preferable.
In this paper we rigorously prove global convergence of the (1+1)-ES, with an emphasis
on covering the widest possible class of problems. To this end we introduce a novel regularity
condition ensuring proper function of success-based step-size control, which is much weaker than
continuous differentiability.
The paper and the proofs are organized as follows. In the next section we establish a sufficient
decrease condition for rank-based elitist algorithms. This condition is extremely general, and it
is in no way tied to continuous search spaces and the (1+1)-ES. Its role in the global convergence
proof is to ensure a sufficient rate of optimization progress as long as the step size is well adapted
and the progress rate is bounded away from zero. In section 3 we define the (1+1)-ES and
introduce the regularity condition. Based on this condition we show that the step size returns
infinitely often to a range where non-trivial progress can be concluded from the sufficient decrease
theorem. Based on these achievements we establish a global convergence theorem in section 4,
essentially stating that there exists a sub-sequence of iterates converging to a critical point, the
exact notion of which is defined in section 3. We also establish a negative result, showing that
a non-optimal critical point results in premature convergence with positive probability, which
excludes global convergence. In section 5 we apply the analysis to a variety of settings and
demonstrate their implications. We close with conclusions and open questions.
2

Jägersküpper analyzed a different step size adaptation rule. However, it exhibits essentially the same dynamics
as Algorithm 1.

2

2

Sufficient Decrease

In this section, we establish a general sufficient decrease condition for randomized rank-based
elitist algorithms. We consider a general search space X. This space is equipped with a σalgebra and a reference measure denoted Λ. The usual choice of the reference measure is the
counting measure for discrete spaces and the Lebesgue measure for continuous spaces. The
objective function f : X → R, to be minimized, is assumed to be measurable. The parent
selection and variation operations of the search algorithm are also assumed to be measurable;
indeed we assume that these operators give rise to a distribution from which the offspring is
sampled, and this distribution has a density with respect to Λ.
A rank-based optimization algorithm ignores the numerical fitness scores (f -values), and
instead relies solely on pairwise comparisons, resulting in exactly one of the relations f (x) <
f (x′ ), f (x) = f (x′ ), or f (x) > f (x′ ). This property renders it invariant to strictly monotonically
increasing (rank preserving) transformations of the objective values. Therefore it “perceives”
the objective function only in terms of its level sets, not in terms of the actual function values.
For f : X → R let
n
o
Lf (y) = x ∈ X f (x) = y
n
o
Sf< (y) = x ∈ X f (x) < y
n
o
Sf≤ (y) = x ∈ X f (x) ≤ y

denote the level set of f , and the sub-level sets below and including level y ∈ R. For m ∈ X we

≤
≤
<
<
<
define the short notations L<
f (m) := Lf f (m) , Sf (m) := Sf f (m) and Sf (m) := Sf f (m) .
Due to the assumption that the offspring generation distribution is Λ-measurable, with full
probability, the algorithm is invariant to the values of the objective function restricted to zero
sets. The following definition captures these properties. It encodes the “essential” level set
structure of an objective function.
Definition 1.

We call two measurable functions f, g : X → R equivalent and write
f ∼g

if there exists a zero
 set Z ⊂ X and a strictly monotonic function φ : f (X) → g(X) such
that g(x) = φ f (x) for all x ∈ X \ Z. Here f (X) and g(X) denote the images of f and g,
respectively. We denote the corresponding equivalence class in the set of measurable functions
by [f ] := f / ∼.
It follows immediately from the definition that the sub-level sets of equivalent objective functions
f ∼ g coincide outside a zero set.
In the next step we construct a canonical representative for each equivalence class, which we
can think of as a “normal form” of an objective function.
Definition 2.

For f : X → R we define the spatial suboptimality functions

fbΛ< : X → R ∪ {∞}, x 7→ Λ Sf< (x)

fbΛ≤ : X → R ∪ {∞}, x 7→ Λ Sf≤ (x) .
3

If fbΛ< and fbΛ≤ coincide then we drop the upper index and simply denote the spatial suboptimality
function by fbΛ .

In the following, m ∈ X will denote the elite (or parent) point, and m(t) is the elite point in
iteration t ∈ N of an iterative algorithm, i.e., an evolutionary algorithm with (1 + λ) selection.
For two very different reasons, namely 1) to avoid divergence of the algorithm in the case
of unbounded search spaces, and 2) for simplicity of the technical
arguments in the proofs, we

≤
(0)
restrict ourselves to the case that the sub-level set Sf m
of the initial iterate m(0) is bounded
and has finite spatial sub-optimality. For most reasonable reference measures, boundedness
implies finite spatial sub-optimality. For X = Rd equipped with the Lebesgue measure this is
equivalently to its topological closure of Sf≤ m(0) being compact. The assumptions immediately

imply that Sf< (y) and Sf≤ (y) are bounded for all y ≤ f m(0) , and that restricted to Sf≤ (m(0) ) the


functions fbΛ< and fbΛ≤ take values in the bounded range 0, fbΛ m(0) . Since an elitist algorithm
never accepts points outside S ≤ (m(0) ), we will from here on ignore the issue of infinite fbΛ -values.3
f

The canonical representation in terms of spatial suboptimality is convenient for defining
essential optima (minima) of f , and actually of the whole class [f ].
−1
Definition 3. Consider a measurable function f : X → R. The set (fbΛ≤ ) (0) is called the set
of essential global optima of f . A point x ∈ X is called an essential local optimum of f if it is
a local optimum of fbΛ≤ , i.e., if it is minimal restricted to an (open) neighborhood N ⊂ Rd of x.

In the continuous case, a plateau is a level set of positive Lebesgue measure. Note that according
to this definition, an inner point of a plateau is a local optimum, which may not always be
intended. Anyway, when analyzing the (1+1)-ES we will not handle plateaus and instead assume
that level sets of f are zero sets. This also implies that fbΛ≤ and fbΛ< agree.

Lemma 4. Let f : X → R be measurable. If fbΛ≤ (x) is finite for all x ∈ X then it holds
fbΛ≤ ∼ f ∼ fbΛ< .

The proof is found in the appendix. We use fbΛ≤ and fbΛ< (or simply fbΛ if possible) as a “canonical”
representative of its equivalence class (if the function values are finite, but see the discussion
above). These functions have the remarkable property


fbΛ≤ (x) = Λ Sfb≤ (x)
fbΛ< (x) = Λ Sfb< (x)
Λ

Λ

i.e., fbΛ encodes the Lebesgue measure of its own sub-level sets. We will measure optimization
progress in terms of fbΛ -values. Decreasing the spatial suboptimality fbΛ by δ > 0 amounts to
reducing the volume of better points by δ.
Due to the rank-based nature of the algorithms under study we cannot expect to obtain
a sufficient decrease condition based on f -values. Instead, the following theorem establishes a
sufficient decrease condition measured in terms of the spatial suboptimality function fbΛ . It gets

3
An alternative approach to avoiding infinite values is to apply a bounded reference measure with full support,
e.g., a Gaussian on Rd . In the absence of a uniform distribution on X, the price to pay for a bounded and
everywhere positive reference measure is a non-uniform measure, which complicates matters. These technical
complications seem to outweigh the slightly increased generality of the results.

4

around the problem of inconclusive values in objective space (which, in case of single-objective
optimization, is just the real line) by considering a quantity in search space, namely the reference
measure of the sub-level set.
The algorithm is randomized, hence the decrease follows a distribution. The following theorem controls the expected value as well as the quantiles of the decrease distribution.
Theorem 5. Let P denote a probability distribution on X with a bounded density with
respect to Λ. Define the upper bound


P (A)
A ⊂ X measurable with Λ(A) > 0
u = sup
Λ(A)
on the density. Consider a measurable objective function f : X → R, as well as a sample x ∼ P .
Define the functions

r < : R → [0, 1],
z 7→ P f (x) < z

r ≤ : R → [0, 1],
z 7→ P f (x) ≤ z .


≤ s(q) for
We define s : [0, 1] → R as a measurable “inverse” function fulfilling r < s(q)
≤
q
≤
r

all q ∈ [0, 1]. We collect the discontinuities of r < and r ≤ in the set Z = z ∈ R r < (z) < r ≤ (z)
and define the sum
2
X
ζ=
r ≤ (z) − r < (z)
z∈Z

of squared jumps.

Fix a reference point m ∈ X and let p = r < f (m) denote the probability of strict improvement of x over m. Then for each q ∈ [0, p], the q-quantile of the fbΛ< -decrease is bounded from
below by
!
< s(q)
p
−
r
<
<
Pr fbΛ (m) − fbΛ (x) ≥
≥ q,
u

and the the q-quantile of the fbΛ≤ -decrease is bounded from below by

!


p − r ≤ s(q)
≤
≤
b
b
Pr fΛ (m) − fΛ (x) ≥
+ Λ Lf (m)
≥ q,
u

The expected fbΛ< -decrease is bounded from below by

i p2 + ζ
h

E max 0, fbΛ< (m) − fbΛ< (x) ≥
,
2u

and the expected fbΛ≤ -decrease is bounded from below by

i p2 − ζ
h


+ Λ Lf (m) .
E max 0, fbΛ≤ (m) − fbΛ≤ (x) ≥
2u
5


Proof By construction it holds P Lf (z) = r ≤ (z) − r < (z) for all z ∈ R.
For fixed q, define the level yq = s(q). Consider the distribution of f (x). If f (x) happens to
lie in the left tail of mass p, then f (x) is better than f (m). However, if the left tail is restricted
to mass q ≤ p, then f (x) is better than yp and has “overjumped” a probability mass of p − q.
The same holds for the distribution of x: if f (x) < yq , then fbΛ< has overjumped an area of

P -mass of at least p − q, and even of mass p − r < s(q) . Similarly, if f (x) ≤ yq , then fbΛ≤ has
overjumped an area of P -mass of at least p − r ≤ s(q) . Due to the very definition of u, this
probability mass corresponds to a Λ-measure which is larger by a factor of at least 1/u,
 and
≤
b
due to the fact that a strict improvement was sampled, fΛ is also reduced by Λ Lf (m) . This
proves the lower bounds on the q-quantiles.
The expected fbΛ< improvement is lower bounded by
i Z p p − r < s(q)
h

<
<
b
b
dq
E max 0, fΛ (m) − fΛ (x) ≤
u
0

Z p
Z p
q − r < s(q)
p−q
=
dq +
dq
u
u
0
0
Z p
X Z r≤ (z) q − r < (z)
p−q
=
dq +
dq
u
u
<
0
z∈Z r (z)
2
p2 X r ≤ (z) − r < (z)
+
=
2u
2u
z∈Z

=

p2

+ζ
.
2u

The proof of the expected fbΛ≤ improvement is analogous.

In a (1 + λ) evolutionary algorithm, the reference point m is usually the current best iterate
(parent), and the distribution P is the search distribution, from which the offspring are sampled.
Our main application is the (1+1)-ES introduced in the next section, where x corresponds to
the offspring point sampled from
a Gaussian centered on m.

Due to the term Λ Lf (m) in the decrease of fbΛ≤ , the theorem covers the fitness-level method
(Droste et al., 2002; Wegener, 2003). However, in particular for search distributions spreading
their probability mass over many level sets, the theorem is considerably stronger.
In the continuous case, in the absence of plateaus, the statement can be simplified considerably:
Corollary 6. Under the assumptions and with the notation of theorem 5 we assume in addition that all level sets of f have measure zero. Then for each q ∈ [0, p], the q-quantile of the
fbΛ -decrease is bounded from below by


p−q
b
b
≥ q,
Pr fΛ (m) − fΛ (x) ≥
u

and the expected fbΛ -decrease is bounded from below by
i
h

p2
.
E max 0, fbΛ (m) − fbΛ (x) ≥
2u
6

The following corollary is a broken down version for Gaussian search distributions N (m, C) with
mean m and covariance matrix C, which has the density


1
1
T −1
p
exp − (x − m) C (x − m) .
p(x) =
2
(2π)d/2 det(C)
Corollary 7. Consider the search space Rd and the Lebesgue measure Λ. Let f : Rd → R
denote a measurable objective function with level sets of measure zero. Consider a normally
distributed sample x ∼ N (m, C). Under the assumptions and with the notation of theorem 5,
for each q ∈ [0, p], the q-quantile of the fbΛ -decrease is bounded from below by


p
Pr fbΛ (m) − fbΛ (x) > (2π)d/2 · det(C) · (p − q) ≥ q,
and the expected fbΛ -decrease is bounded from below by
i
h
p

p2
E max 0, fbΛ (m) − fbΛ (x) > (2π)d/2 · det(C) · .
2

An isotropic distributions with component-wise standard deviation (step size) σ > 0 corresponds
has covariance matrix C = σ 2 I, where I ∈ Rd×d is the identity matrix; hence we have det(C) =
σ d . In the context of continuous search spaces, Jägersküpper (2003) refers to fbΛ -progress as
“spatial gain”. He analyzes in detail the gain distribution of an isotropic search distribution
on the sphere model. This result is much less general than the previous corollary, since we
can deal with arbitrary objective functions, which are characterized (locally) only by a single
number, the success probability. For the special case of a Gaussian mutation and the sphere
function, Jägersküpper’s computation of the spatial gain is more exact, since it is tightly tailored
to the geometry of the case, in contrast to being based on a general bound. Still, we lose only
a multiplicative factor of the gain, which does not impact the analysis significantly.
The above statements apply immediately to evolutionary algorithms with (1+1) selection.
Generalizing them to the best out of λ samples is rather straightforward (based on well-known
statements on the distribution of the minimum of λ i.i.d. samples), resulting in bounds for the
one-step behavior of elitist algorithms with (1 + λ) selection. This is not done here because we
are not primarily interested in the scaling with λ, which is usually non-essential for the question
whether a (1 + λ)-ES converges to an essential (local) optimum.

3

Success-bases Step Size Control in the (1+1)-ES

In this section we introduce the (1+1)-ES algorithm and provide an analysis of its success-based
step size adaptation rule that will allow us to derive global convergence theorems. To this end
we introduce a non-standard regularity property.
From here on, we consider the search space X = Rd , equipped with the standard Borel
σ-algebra, and Λ denotes the Lebesgue measure. We denote the d-dimensional (multivariate)
isotropic normal distribution with expectation m and (component-wise) standard deviation σ
by N (m, σ 2 ). The covariance matrix is σ 2 I, where I denotes the identity matrix in Rd .
In each iteration t ∈ N, the state of the (1+1)-ES is given by (m(t) , σ (t) ) ∈ Rd × R+ . It

samples one candidate offspring from the isotropic normal distribution x(t) ∼ N (m(t) , σ (t) )2 .
7

The parent is replaced by successful offspring, meaning that the offspring must perform at least
as good as the parent.
The goal of success-based step size adaptation is to maintain a stable distribution of the
success rate, for example concentrated around 1/5. This can be achieved with a number of
different mechanisms. Here we consider the maybe simplest such mechanism, namely immediate
adaptation based on “success” or “failure” of each sample. Pseudocode for the full algorithm is
provided in Algorithm 1.
The constants c− < 0 and c+ > 0 in Algorithm 1 control the change of log(σ) in case of failure
and success, respectively. They are parameters of the method. For c+ + 4 · c− = 0 we obtain
−
the
an implementation of Rechenberg’s classic 1/5-rule (Rechenberg, 1973). We call τ = c−c−c
+
target success probability of the algorithm, which is always assumed to be strictly less than 1/2.
This is equivalent to c+ > −c− . A reasonable parameter setting is c− , c+ ∈ Ω d1 .
Algorithm 1 (1+1)-ES
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

input m(0) ∈ Rd , σ (0) > 0, i.i.d. random vectors z (t)
t←0
repeat
x(t) ← m(t) + σ (t) · z (t)
if f x(t) ≤ f m(t) then
m(t+1) ← x(t)
σ (t+1) ← σ (t) · ec+
else
m(t+1) ← m(t)
σ (t+1) ← σ (t) · ec−
t←t+1
until stopping criterion is met



t∈N

∼ N (0, 1)

Two properties of the algorithm are central for our analysis: it is rank-based and it performs
elitist selection, ensuring that the best-so-far solution is never lost and the sequence f (m(t) ) is
monotonically decreasing.
Since step-size control depends crucially on the concept of successful offspring, we define the
success probability of the algorithm, which is the probability of a sampled point outperforming
the parent in the search distribution center.
Definition 8.
functions
p<
f

For a measurable function f : Rd → R, we define the “success probability”
d

+

: R × R → [0, 1],

(m, σ) 7→

d
+
p≤
f : R × R → [0, 1],

(m, σ) 7→

Z

Z

Sf< (m)

Sf≤ (m)



kx − mk2
1
dx,
· exp −
2σ 2
(2π)d/2 σ d


1
kx − mk2
· exp −
dx.
2σ 2
(2π)d/2 σ d

<
The function p≤
f computes the probability of sampling a point at least as good as m, while pf
≤
computes the probability of sampling a strictly better point. If p<
f and pf coincide (i.e., if there

8

are no plateaus), then we write pf . A nice property of the success probability is that it does not
drop too quickly when increasing the step size:
Lemma 9.

For all m ∈ Rd , σ > 0 and c ≥ 1 it holds
1
· p< (m, σ),
cd f
1
≤
p≤
f (m, c · σ) ≥ d · pf (m, σ).
c

p<
f (m, c · σ) ≥

The proof is found in the appendix; this is the case for a number of technical lemmas in this
section. The next step is to define a plausible range for the step size.
Definition 10.
lower bounds

For p ∈ [0, 1] and a measurable function f : Rd → R, we define upper and
n
o
+
<
= inf σ ∈ R pf (m, σ) ≤ p
o
n
(m,
σ)
≥
p
ηpf (m) = sup σ ∈ R+ p≤
f
ξpf (m)

on the step size guaranteeing lower and upper bounds on the probability of (strict) improvement.
We think of ξpf (m) with p > τ as a “too small” step size at m. Similarly, for p < τ , ηpd (m) is a
“too large” step size at m. We aim to establish that if the step size is outside this range then
step size adaptation will push it back into the range. The main complication is that the range
for σ depends on the point m.
The following lemma establishes a gap between lower and upper step size bound, i.e., a lower
bound on the size of the step size range.
√
√
Lemma 11. For 0 ≤ pH ≤ pT ≤ 1 it holds d pH · ξpfT (x) ≤ d pT · ηpfH (x) for all x ∈ Rd .
The following definition is central. It captures the ability of the (1+1)-ES to recover from a
state with a far too small step size. This property is needed to avoid premature convergence.
Definition 12. For p > 0, a function f : Rd → R is called p-improvable in x ∈ Rd if ξpf (x) is
positive. The function is called p-improvable on Y ⊂ Rd if ξpf Y is lower bounded by a positive,
lower semi-continuous function ξ˜pf : Y → (0, 1]. A point x ∈ Rd is called p-critical if it is not
p-improvable for any p > 0.
The property of p-improvability is a non-standard regularity condition. The concept applies
to measurable functions, hence we do not need to restrict ourselves to smooth or continuous
objectives. On the one hand side, the property excludes many measurable and even smooth
functions. On the other hand, it is far less restrictive than continuity and smoothness, since
it allows the objective function to jump and the level sets to have kinks. Intuitively, in the
two-dimensional case, if for each point the sub-level set opens up in an angle of more than 2πp,
then the function is p-improvable. This is the case for many discontinuous functions, however,
not for all smooth ones. The degree three polynomial f (x1 , x2 ) = x31 + x22 can serve as a counter
example, since every point of the form (0, x2 ) is p-critical. All of its contour lines form cuspidal
cubics. Local optima are always p-critical, but many critical points of smooth functions are

9

not (see below). The above example demonstrates that some saddle points share this property,
however, if x is p-critical but not essentially locally optimal then p<
f (x, σ) > 0 for all σ > 0. I.e.,
such a point can be improved with positive probability for each choice of the step size, but in
the limit σ → 0 the probability of improvement tends to zero.
We should stress the difference between point-wise p-improvability, which simply demands
that ξpf is positive, and set-wise p-improvability, which in addition demands that ξpf is lower
bounded by a lower semi-continuous positive function. The latter property ensures the existence
of a positive lower bound for ξpf on a compact set. In this sense, set-wise p-improvability is
uniform on compact sets. In sections 5.5 and 5.6 we will see examples where this makes a
decisive difference.
Intuitively, the value of p of a p-improvable function is critical: if it is below τ then the
algorithms may be endangered to systematically decrease its step size while it should better
do the contrary. However, with a covariance matrix adaptation mechanism in place, a small
angle representing the region of improvement can be opened up, which can bring the success
probability arbitrarily close to 1/2. Hence, for many (but not for all) cases this implies that
with a CMA-style mechanism in place the exact value of p does not matter, as long as a point
is not p-critical.
The next lemma establishes that smooth functions are p-improvable in all regular points,
and also in most saddle points.
Lemma 13. Let f : Rd → R be continuously differentiable.
1. For a regular point x ∈ Rd , f is p-improvable in x for all p < 21 .
2. Let Y denote the set of all regular points of f , then f is p-improvable on Y , for all p < 12 .
3. Let x ∈ Rd denote a critical point of f , let f be twice continuously differentiable in a
neighborhood of x, and let H = ∇2 f (x) denote the Hessian matrix. If H has at least one
negative eigen value, then x is not p-critical.
Similarly, we need to ensure that the step size does not diverge to ∞. This is easy, since the
spatial suboptimality is finite:
Lemma 14.

Consider the state (m, σ) of the (1+1)-ES. For each p ∈ (0, 1), if
s
fbΛ (m)
d
σ≥
p · (2π)d/2

then p<
f (m, σ) ≤ p.
Applying the above inequality to p < τ implies that for large enough step size σ, the expected
change of log(σ) is negative.
The following lemma is elementary. It is used multiple times in proofs, with the interpretation
of the event “1” meaning that a statement holds true. It has a similar role as drift theorems in an
analysis of the expected or high-probability behavior (Lehre and Witt, 2013; Lengler and Steger,
2016; Correa et al., 2016), however, here we aim for almost sure results.
Lemma 15. Let X (t) ∈ {0, 1} denote a sequence of independent binary random variables. If
there exists a uniform lower bound Pr(X (t) = 1) ≥ p > 0, then almost surely there exists an
infinite sub-sequence (tk )k∈N so that X (tk ) = 1 for all k ∈ N.
10

In applications of the lemma, the events of interest are not necessarily independent, however,
they can be “made independent” by considering a sequence of independent events with imply the
events of interest. This is always the case if the events of actual interest hold with probability of
at least p; then an i.i.d. sequence of of Bernoulli events implying corresponding sub-events subevents with probability of exactly p does the job. We imply this construction in all applications
of the lemma.
The following lemma establishes, under a number of technical conditions, that the step size
control rule succeeds in keeping the step size stable. If the prerequisites are fulfilled then the
result yields an impossible fact, namely that the overall reduction of the spatial suboptimality
is unbounded. So the lemma is designed with proofs by contradiction in mind.

Lemma 16. Let m(t) , σ (t) denote the sequence of states of the (1+1)-ES on a measurable
objective function f : Rd → R. Let pT , pH ∈ (0, 1) denote probabilities fulfilling pH < τ < pT
and ppHT ≤ ed·c− , and assume the existence of constants 0 < bT < bH such that
bT ≤ ξpfT (m(t) )

ec+ · ηpfH (m(t) ) ≤ bH

and

for all t ∈ N. Then, with full probability, there exists an infinite sub-sequence (tk )k∈N of iterations
fulfilling
h

i
σ (tk ) ∈ ξpfT m(tk ) , ηpfH m(tk )
(1)

for all k ∈ N.

4

Global Convergence

In this section we establish our main result. The theorem ensures the existence of a limit point of
the sequence m(t) in a subset of desirable locations. In many cases this amounts to convergence
of the algorithm to an essential (local) optimum.
Theorem 17. Consider a measurable objective function f : Rd → R with level sets of measure

zero. Assume that K0 = Sf≤ m(0) is compact, and let K1 ⊂ K0 denote a closed subset. If f is

p-improvable on K0 \ K1 for some p > τ , then the sequence m(t) t∈N has a limit point in K1 .
Proof Lemma 14 ensures the existence of 0 < pH < e−d·c− · τ and
s

fbΛ m(0)
d
bH =
pH · (2π)d/2

such that it holds ηpfH (x) ≤ bH uniformly for all x ∈ K0 . In particular, bH is an upper bound
on ηpfH .
Let B(x, r) denote the open ball of radius r > 0 around x ∈ Rd and define the compact set
/ [
B(x, r).
K(r) = K0
x∈K1

11

S
It holds K(r) ⊂ K0 \ K1 and r>0 K(r) = K0 \ K1 ; hence K(r) is a compact exhaustion of
K0 \ K1 .
Fix r > 0, and assume for the sake of contradiction that all points m(t) , t > t0 , are contained
in K(r). We set pT = p. Let ξ̃pfT denote the lower semi-continuous lower bound on ξpfT , which
is guaranteed to exist due to the p-improvability of f . We define
n
o
bT = min ξ˜pfT (m) m ∈ K(r) > 0

and apply lemma 16 to obtain an infinite sub-sequence of states with step size lower boundedby
σ (t) ≥ bT > 0. According to lemma 9, the success probability is lower bounded by pf m(t) , σ (t) ≥
pI , pI = (bT /bH )d · pT > 0, for all m ∈ K(r) and σ ∈ [bT , bH ].
Corollary 7 ensures that in each such state the probability to decrease the fbΛ -value by at
least (2π)d/2 · bdT · pI /2 is lower bounded by pI /2 > 0. Then lemma 15 implies that the overall
fbΛ -decrease is almost surely infinite, which contradicts the fact that fbΛ (m(0) ) is finite and fbΛ is
lower bounded by zero. Hence, the sequence m(t) leaves K(r) after finitely many steps, almost

surely. For r = 1/n, let tn denote an iteration fulfilling m(tn ) 6∈ K(r). The sequence m(tn ) n∈N
does not have a limit point in K0 \ K1 (since that point would be contained in K(r) for some
r > 0), however, due to the Bolzano-Weierstraß theorem it has at least one limit point in K0 ,
which must therefore be located in K1 .
The above theorem is of primary interest if K1 is the set of essential (local) minima of f , or
at least the set of critical or p-critical points. Due to the prerequisites of the theorem we always
have
o
n
x ∈ K0 x is p-critical ⊂ K1 ,

i.e., p-critical points are candidate limit points.
In accordance with Akimoto et al. (2010), the following corollary establishes convergence to
a critical point for continuously differentiable functions.

Corollary 18. Let f : Rd → R be a continuously differentiable function with level sets of


measure zero. Assume that K0 = Sf≤ m(0) is compact. Then the sequence m(t) t∈N has a
critical limit point.
Proof Define K1 = {x ∈ Rd | ∇f (x) = 0} as the set of critical points. This set is closed.
Lemma 13 ensures that f is p-improvable on K0 \ K1 for all p < 1/2. Then the claim follows
immediately from theorem 17.
Technically the above statements do not apply to problems with unbounded sub-level sets.
However, due to the fast decay of the tails of Gaussian search distributions we can often approximate these problems by changing the function “very far away” from the initial search
distribution, in order to make the sub-level sets bounded. We may then even apply the theorem
with empty K1 , which implies that after a while the approximation becomes insufficient since
the algorithm diverges. In this sense we can conclude divergence, e.g., on a linear function. We
will use this argument several times in the next section, mainly to avoid unnecessary technical
complications when defining saddle points and ridge functions.

12

We may ask whether p-improvability for p > τ is not only a sufficient but also a necessary
condition for global convergence. This turns out to be wrong. The quadratic saddle point case
discussed below in section 5.2 is a counter example, where the algorithm diverges reliably even
if the success probability is far smaller than τ . In contrast, the ridge of p-critical saddle points
analyzed in section 5.3 results in premature convergence, despite the fact that the critical points
form a zero set, and this can even happen for a ridge of p-improvable points with p < τ , see
section 5.4. Drift analysis is a promising tool for handling all of these cases. Here we provide a
rather simple result, which still suffices for many interesting cases.
Theorem 19. Consider a measurable objective function f : Rd → R with level sets of measure
zero. Let m ∈ Rd be a p-critical point. If the success probability decays sufficiently quickly, i.e.,
∞
X
k=0

k·c−
p≤
)<∞
f (m, e

then for each given p < 1 there exists an initial condition such that the (1+1)-ES converges to
m with probability of at least p.
P
≤
k·c− ). For given p < 1, there exists a K
Proof Define the zero sequence SK = ∞
0
k=K pf (m, e
such that SK0 < 1 − p. By definition, the probability of never sampling a successful offspring
when starting the algorithm in the initial state m(0) = m, σ (0) = eK0 ·c− is given by SK0 ; in this
case we have m(t) = m for all t ∈ N.
The above theorem precludes global convergence to an essential (local) optimum in the presence
of a suitable non-optimal p-critical point.

5

Case Studies

In this section we analyze various example problems with very different characteristics, by applying the above convergence analysis. We characterize the optimization behavior of the (1+1)-ES,
giving either positive or negative results in terms of global convergence. We start with smooth
functions and then turn to less regular cases of non-smooth and discontinuous functions. On
the one hand side, we show that the theorem is applicable to interesting and non-trivial cases;
on the other hand we explore its limits.

5.1

The Rosenbrock Function

The two-dimensional Rosenbrock function is given by
f (x1 , x2 ) = 100(x21 − x2 )2 + (x1 − 1)2 .
This is a degree four polynomial. The function is unimodal, but not convex. Moreover, it does
not have critical points other than the global optimum x∗ = (1, 1).
The Rosenbrock function is a popular test problem since its solution requires a diverse set
of optimization behaviors: the algorithm must descend into a parabolic valley, follow the valley
while adapting to its curved shape, and finally converge into the global optimum, which is a
smooth optimum with non-trivial (but still moderate) conditioning.

13

Corollary 18 immediately implies convergence of the (1+1)-ES into the global optimum. It
does not say anything about the speed of convergence, however, Jägersküpper (2005) established
linear convergence in the last phase with overwhelming probability, and since divergence is
excluded, Auger (2005) proves linear convergence based on drift and stability of the Markov
chain.
Taken together, these results give a rather complete picture of the optimization process:
irrespective of the initial state we know that the algorithm manages to locate the global optimum
without getting stuck on the way. Once the objective function starts to look quadratic in
good enough approximation, the convergence is linear. The same analysis applies to all twice
continuously differentiable unimodal function without critical points other than the optimum.

5.2

Saddle Points—The p-improvable Case

We consider the quadratic objective function
f (x1 , x2 ) = a · x21 − x22

with parameter a > 0. The origin is a saddle point. It is p-improvable for all p < cot−1 (a2 )/π <
1/2. For small enough a, the success probability is larger than τ and corollary 18 applies, while
for large values of a the success probability decays to zero and we lose all guarantees.
Simulations show that the ES overcomes the zero level set containing the saddle point without
a problem, also for large values of a. We conclude that p-improvable saddle points are no obstacle
for the algorithm, irrespective of the value of p > 0. However, this statement is based on an
empirical observation, not on a rigorous proof.

5.3

Saddle Points—The p-critical Case

The cubic polynomial
f (x1 , x2 ) = x31 + x22
has p-critical saddle points on the line {0} × R ⊂ R2 , forming a ridge. For small σ we have
√
p≤
f (0, σ) ∈ O( σ). Hence, the cumulative success probability
!


∞
∞
X
X
1
≤
t·c− /2
t·c−
= O(1)
=O
e
pf (0, e ) = O
1 − ec− /2
t=0
t=0
is finite and theorem 19 implies (premature) convergence with arbitrarily high probability.

5.4

Linear Ridge

Consider the linear ridge objective
f (x1 , x2 ) = x1 + a · |x2 |

with parameter a > 0. The function is continuous, and its level sets contain a kink. Again,
the line {0} × R is critical; this is where the function is non-differentiable. The function is
p-improvable for p < cot−1 (a)/π < 1/2. For a → ∞ the success probability decays to zero.
As long as cot−1 (a)/π > τ we can conclude divergence of the algorithm (the intended
behavior) from theorem 17. Otherwise we lose this property, and it is well known and easy
to check with simulations that for large enough a the algorithm indeed converges prematurely.

14

5.5

Sphere with Jump

Our next example is an “essentially discontinuous” problem in the sense that in general no
function in the equivalence class [f ] is continuous. We consider objective functions of the form
f (x) = kxk2 + 1S (x),
where 1S denotes the indicator function of a measurable set S ⊂ Rd . If S has a sufficiently
simple shape then this problem is similar to a constrained problem where S is the infeasible
region (Arnold and Brauer, 2008), at least for σ ≪ 1. As long as m(t) ∈ S the (1+1)-ES
essentially optimizes the sphere function, and as soon as m(t) 6∈ S the (soft) constraint comes
into play.
If S is the complement of a star-shaped open neighborhood of the origin then it is easy to see
that the function is unimodal and p-improvable for all p < 1/2. Theorem 17 applied with K1 =
{0} yields the existence of a sub-sequence converging to the origin, which implies convergence
of the whole sequence due to monotonicity of f m(t) . Again, the results of Jägersküpper and
Auger imply linear convergence.
Other shapes of S give different results. For example, if S is a ball not containing the origin
then the function is still unimodal. E.g., define S as the open ball of radius 1/2 around the
first unit vector e1 = (1, 0, . . . , 0) ∈ Rd . Then at m = 3/2 · e1 we have ξpf (m) = 0 for all p > 0,
and according to theorem 19 the algorithm can converge prematurely if the step size is small.
Alternatively, if S is the closed ball, then all points except the origin are p-improvable for all
p < 1/2, however, there does not exist a positive lower semi-continuous lower bound on ξpf in any
neighborhood of m = 3/2 · e1 , and again the algorithm can converge to this point, irrespective
of the target success probability τ .
Now consider the strip S = (a, ∞) × (0, 1) ⊂ R2 with parameter a > 0. An elementary
calculation of the success rate at m = (a+ ε, 1) for σ → 0 shows that the (1+1)-ES is guaranteed
to converge to the optimum irrespective of the initial conditions if (a2 + 1)−1/2 < cos(2πτ ), i.e.,
if a is large enough; otherwise the algorithm can converge prematurely to a point on the edge
(a, ∞) × {1} of S.

5.6

Extremely Rugged Barrier

Let us drive the above discontinuous problem to the extreme. Consider the one-dimensional
problem
f (x) = x + 1S (x),
where S ⊂ [−1, 0] is a Smith-Volterra-Cantor set, also known as a fat Cantor set. S is closed, has
positive measure (usually chosen as Λ(S) = 1/2), but is nowhere dense. Counter-intuitively, the
function is unimodal in the sense that no point is optimal restricted to an open neighborhood
(which is what defines a local optimum). Still, intuitively, S should be able to act as a barrier
blocking optimization progress with high probability.
The function is point-wise p-improbable everywhere. However, similar to the closed ball case
in the previous section, there is no positive, lower semi-continuous lower bound on ξpf . Therefore

15

theorem 17 does not apply. Indeed, unsurprisingly, simulations4 show that the algorithm gets
stuck with positive probability when initialized with x(0) > 0, x(0) ≪ 1 and σ ≪ 1. When
√
removing 0 from C, then analogous to section 5.3 we obtain p≤
f (m, σ) ∈ O( σ)) for m = 0 and
small σ, and hence theorem 19 applies.
In contrast, if C is a Cantor set of measure zero then the algorithm diverges successfully,
since it ignores zero sets with full probability.

6

Conclusions and Future Work

We have established global convergence of the (1+1)-ES for an extremely wide range of problems.
Importantly, with the exception of a few proof details, the analysis captures the actual dynamics
of the algorithm and hence consolidates our understanding of its working principles.
Our analysis rests on two pillars. The first one is a probabilistic sufficient decrease condition
for rank-based evolutionary algorithms with elitist selection. In its simplest form, it bounds
the progress on problems without plateaus. It seems to be quite generally applicable, e.g., to
runtime analysis and hence to the analysis of convergence speed.
The second ingredient is an analysis of success-based step size control. The current method
barely suffices to show global convergence. It is not suitable for deducing stronger statements
like linear convergence on scale invariant problems. Control of the step size on general problems
therefore needs further work.
Many natural questions remain open, the most significant are listed in the following. These
open points are left for future work.
• The approach does not directly yield results on the speed of convergence. However, the
sufficient decrease condition of theorem 5 is a powerful tool for such an analysis. It can
provide us with drift conditions and hence yield bounds on the expected runtime and on
the tails of the runtime distribution. However, for that to be effective we need better tools
for bounding the tails of the step size distribution. Here, again, drift is a promising tool.
• The current results are limited to step-size adaptive algorithms and do not include covariance matrix adaptation. One could hope to extend the proceeding to the (1+1)-CMA-ES
algorithm (Igel et al., 2007), or to (1+1)-xNES (Glasmachers et al., 2010). Controlling
the stability of the covariance matrix is expected to be challenging. It is not clear whether
additional assumptions will be required. As an added benefit, it may be possible to relax
the condition p > τ for p-improvability, by requiring it only after successful adaptation of
the covariance matrix.
• Plateaus are currently not handled. Theorem 5 shows how they distort the distribution of
the decrease. Worse, they affect step size adaptation, and they make it virtually impossible
to obtain a lower bound on the one-step probability of a strict improvement. Therefore,
proper handling of plateaus requires additional arguments.
4

Special care must be taken when simulating this problem with floating point arithmetic. Our simulation is
necessarily inexact, however, not beyond the usual limitations of floating point numbers. It does reflect the actual
dynamics well. The fitness function is designed such that the most critical point for the simulation is zero, which
is where standard floating point numbers have maximal precision.

16

• In the interest of generality, our convergence theorem only guarantees the existence of
a limit point, not convergence of the sequence as a whole. We believe that convergence
actually holds in most cases of interest (at least as long as there are no plateaus, see above).
This is nearly trivial if the limit point is an isolated local optimum, however, it is unclear
for a spatially extended optimum, e.g., a low-dimensional variety or a Cantor set.
• Our current result requires a saddle point to be p-improvable for some p > τ , otherwise
the theorem does not exclude convergence of the ES to the saddle point. We know from
simulations that the (1+1)-ES overcomes p-improvable saddle points reliably, also for
p ≪ τ . A proper analysis guaranteeing this behavior would allow to establish statements
analogous to work on gradient-based algorithms that overcome saddle points quickly and
reliably, see e.g. Dauphin et al. (2014). However, this is clearly beyond the scope of the
present paper.
• We provide only a minimal negative result stating that the algorithm may indeed converge
prematurely with positive probability if there exists a p-critical point for which the cumulative success probability does not sum to infinity. In section 5.5 it becomes apparent
that this notion is rather weak, since the statement is not formally applicable to the case
of a closed ball, which however differs from the open ball scenario only on a zero set.
This makes clear that there is still a gap between positive results (global convergence) and
negative results (premature convergence). Theorem 19 can for sure be strengthened, but
the exact conditions remain to be explored. A single p-improvable point with p < τ is
apparently insufficient. A p-critical point may be sufficient, but it is not necessary.
Acknowledgments
I would like to thank Anne Auger for helpful discussions, and I gratefully acknowledge support
by Dagstuhl seminar 17191 “Theory of Randomized Search Heuristics”.

References
Akimoto, Y., Nagata, Y., Ono, I., and Kobayashi, S. (2010). Theoretical analysis of evolutionary computation on continuously differentiable functions. In Genetic and Evolutionary Computation Conference,
pages 1401–1408. ACM.
Arnold, D. and Brauer, D. (2008). On the behaviour of the (1+1)-es for a simple constrained problem.
In Parallel Problem Solving from Nature (PPSN), pages 1–10. Springer.
Auger, A. (2005). Convergence results for the (1, λ)-SA-ES using the theory of ϕ-irreducible Markov
chains. Theoretical Computer Science, 334(1–3):35–69.
Correa, C., Wanner, E., and Fonseca, C. (2016). Lyapunov design of a simple step-size adaptation strategy
based on success. In Parallel Problem Solving from Nature (PPSN XIV), pages 101–110. Springer.
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. (2014). Identifying
and attacking the saddle point problem in high-dimensional non-convex optimization. In Ghahramani,
Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q., editors, Advances in Neural
Information Processing Systems 27, pages 2933–2941. Curran Associates, Inc.

17

Droste, S., Jansen, T., and Wegener, I. (2002). On the analysis of the (1+ 1) evolutionary algorithm.
Theoretical Computer Science, 276(1-2):51–81.
Gilbert, J. and Nocedal, J. (1992). Global Convergence Properties of Conjugate Gradient Methods for
Optimization. SIAM Journal on optimization, 2(1):21–42.
Glasmachers, T., Schaul, T., and Schmidhuber, J. (2010). A Natural Evolution Strategy for MultiObjective Optimization. In Parallel Problem Solving from Nature (PPSN) XI, pages 627–636. Springer.
Hansen, N. and Ostermeier, A. (2001). Completely derandomized self-adaptation in evolution strategies.
Evolutionary Computation, 9(2):159–195.
Igel, C., Hansen, N., and Roth, S. (2007). Covariance matrix adaptation for multi-objective optimization.
Evolutionary Computation, 15(1):1–28.
Jägersküpper, J. (2003). Analysis of a simple evolutionary algorithm for minimization in Euclidean
spaces. Automata, Languages and Programming, pages 188–188.
Jägersküpper, J. (2005). Rigorous runtime analysis of the (1+ 1) ES: 1/5-rule and ellipsoidal fitness
landscapes. In International Workshop on Foundations of Genetic Algorithms, pages 260–281. Springer.
Jägersküpper, J. (2006a). How the (1+ 1) ES using isotropic mutations minimizes positive definite
quadratic forms. Theoretical Computer Science, 361(1):38–56.
Jägersküpper, J. (2006b). Probabilistic runtime analysis of (1+, λ), ES using isotropic mutations. In
Proceedings of the 8th annual Conference on Genetic and Evolutionary Computation (GECCO), pages
461–468. ACM.
Lehre, P. K. and Witt, C. (2013).
arXiv:1307.2559.

General drift analysis with tail bounds.

Technical Report

Lengler, J. and Steger, A. (2016). Drift analysis and evolutionary algorithms revisited. Technical Report
arXiv:1608.03226.
Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technisher Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog.
Torczon, V. (1997). On the convergence of pattern search algorithms. SIAM Journal on optimization,
7(1):1–25.
Wegener, I. (2003). Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In
Evolutionary Optimization, pages 349–369. Springer.

18

Appendix
Here we provide the proofs of technical lemmas that were omitted from the main text in the
interest of readability.
Proof of lemma 4 It is immediately clear from definition 1 that the level sets of f are a
refinement of the level sets of fbΛ≤ and fbΛ< , i.e., f (x) = f (x′ ) implies fbΛ≤ (x) = fbΛ≤ (x′ ) and
fbΛ< (x) = fbΛ< (x′ ), and fbΛ≤ (x) < fbΛ≤ (x′ ) and fbΛ< (x) < fbΛ< (x′ ) both imply f (x) < f (x′ ). It remains
to be shown that fbΛ≤ and fbΛ< do not join f -level sets of positive measure. Let y ∈ R denote a
−1
level so that Y = fbΛ≤
(y) has positive measure Λ(Y ) > 0. We have to show that this measure
(not necessarily the whole set) is covered by a single f -level set.
Assume the contrary, for the sake of contradiction. Then we find ourselves in one of the
following situations:

1. There exist
x, x′ ∈ Y fulfilling a = f (x) < f (x′ ) = a′ and it holds Λ f −1 (a) > 0 and

Λ f −1 (a′ ) > 0. I.e., the mass of Y is split into at least two chunks of positive measure.

This implies fbΛ< (x′ ) − fbΛ< (x) ≥ Λ f −1 (a) > 0, which contradicts the assumption that x
and x′ belong to the same fbΛ< -level.

2. There exist x, x′ ∈ Y fulfilling a = f (x) < f (x′ ) = a′ and it holds Λ f −1 (I) > 0 for
the open interval I = (a, a′ ). I.e., a continuumof level sets of measure zero makes up Y .
Again, this implies fbΛ< (x′ ) − fbΛ< (x) ≥ Λ f −1 (I) > 0, leading to the same contradiction as
in the first case.
The argument for fbΛ≤ is exactly analogous.

Proof of lemma 9 It holds
p<
f (m, c



kx − mk2
· exp −
· σ) =
dx
d/2 cd σ d
2c2 σ 2
Sf< (m) (2π)


Z
1
1
kx − mk2
≥ d·
· exp −
dx
d/2 σ d
c
2σ 2
Sf< (m) (2π)
Z

=

1

1
· p< (m, σ).
cd f

The computation for p≤
f is analogous.
Proof of lemma 11 Fix x and define ξ = ξpfT (x). For c ≥ 1 it holds


Z
kx′ − xk2
1
exp −
dx′
pT ≤

2
d/2
d
<
2ξ
ξ
Sf f (x) (2π)


Z
1
kx′ − xk2
d
exp −
=c ·
dx′

2
d/2 cd ξ d
<
2ξ
(2π)
Sf f (x)


Z
kx′ − xk2
1
d
exp −
dx′ .
≤c ·

d/2 cd ξ d
2c2 ξ 2
Sf< f (x) (2π)
19

In other words, the success probability for step size c · ξ is at least pT /cd . Hence, in order to
push the success probability below pT /cd , the step size must be at least ξ · c, which therefore
bounds ηpf /cd (x) from below. The case pH = 0 is trivial. Applying the above argument with
T
p
c = d pT /pH completes the proof.
Proof of lemma 13 In a small enough neighborhood of a regular point x the function f can
be approximated arbitrarily well by a linear function, for which the probability of strict improvement is exactly 1/2. Hence we have
lim p< (x, σ)
σ→0 f

=

1
,
2

which immediately implies the first statement.
To show the second statement, we claim that ξpf itself is lower-semi-continuous. We have to
show that (ξpf )−1 ([0, r]) is closed for all r > 0. Due to limσ→0 p<
f (x, σ) = 1/2 > p, this is the case
< −1
if (pf ) ([0, q]) is closed for all q ∈ [0, 1/2]. This again follows from the fact that for continuous
f the function p<
f is lower semi-continuous, and even continuous in its second parameter (the
step size).
To show the last statement, let v denote an eigen vector of H fulfilling v T Hv < 0. For
σ → 0, the objective function is well approximated by the quadratic Taylor expansion
f (x′ ) ≈ g(x′ ) = f (x) + (x − x′ )T H(x − x′ ).
Hence, Sf< (x) is locally well approximated by Sg< (x), which is a cone centered on x. Whether a
ray x+R·z belongs to Sg< (x) or not depends on whether z T Hz < 0 or not. Now, the eigen vector
v has this property, and due to continuity of g, the same holds for an open neighborhood v ∈ N .
The cone x + R · N is contained in Sg< (x) and has the same positive probability s<
g (x, σ) = p > 0
2
under N (x, σ ) for all σ > 0. We conclude
lim p< (x, σ)
σ→0 f

= p > 0,

which completes the proof.
Proof of lemma 14 Let S = Sf< (m) denote the area of improvement, with Lebesgue measure
fbΛ (m). The probability of sampling from this area is bounded by


Z
1
kx − mk2
<
pf (m) =
exp
−
dx
d/2 σ d
2σ 2
S (2π)


Z
kx − mk2
1
exp −
dx
=
2σ 2
(2π)d/2 σ d S
Z
1
dx
<
(2π)d/2 σ d S
fbΛ (m)
=
(2π)d/2 σ d
≤ p,
where the last inequality is equivalent to the assumption.

20

Proof of lemma 15 Assume the contrary, for the sake of contradiction. Then
∞
X
t=1

X (t) < ∞.

Fix N ∈ N. Hoeffding’s inequality applied with ε = p/2 and n ≥
Pr

n
X
t=1

X

(t)

≤N

!



p2
≤ exp −n ·
2



2N
p

yields

−→ 0.

n→∞

Hence, for n → ∞, with full probability the infinite sum exceeds N . Since N was arbitrary, we
arrive at a contradiction.
Proof of lemma 16 In each iteration, the step size σ is multiplied by either ec− or ec+ . According to Lemma 11, the condition ppHT ≤ ed·c− yields

ηpfH m(tk )
 ≥ e−c− .
f
(t
)
k
ξp T m

An unsuccessful step of the (1+1)-ES in iteration t result in a reduction of the step size by
(t+1)
the factor σσ(t) = ec− < 1 and leaves m(t+1) = m(t) unchanged. We conclude that no such




step can overjump the interval ξpfT m(t) , ηpfH m(t) , in the sense of σ (t) ≥ ηpfH m(t) and

σ (t+1) ≤ ξpfT m(t) . The above property also implies bbHT ≥ e−c− .
First we show that there exists an infinite sub-sequence of iterations t fulfilling σ (t) ∈ [bT , bH ].
Assume for the sake of contradiction that there exists t0 such that σ (t) ≤ bT for all t ≥ t0 . The
logarithmic step size change δ(t) = log(σ (t+1) )−log(σ (t) ) takes the values c+ > 0 with probability
at least pT > τ and c− < 0 with probability at most 1 − pT < 1 − τ , hence
 
E δ(t) ≥ ∆ := pT · c+ + (1 − pT ) · c− > 0.

P 1 −1 (t)
For t1 > t0 we consider the random variable log(σ (t1 ) ) = log(σ (t0 ) ) + tt=t
δ . The variables
0
(t)
δ are not independent. We create independent variables as follows. For each candidate state
(m, σ) fulfilling σ < bT we fix a set I(m, σ) ⊂ Sf< (m) of improving steps with probability mass
exactly pT under the distribution N (m, σ 2 ). Let δ̃(t) denote the step size change corresponding
to δ(t) for which the step size is increased only if the iterate m(t+1) is contained in I(m, σ).
Note that these hypothetical step size changes do not influence the actual sequence of algorithm
states. Therefore the sequence
i.i.d.,
and it holds δ̃(t) ≤ δ(t) . From Hoeffding’s inequality
Pt1 −1 is
P
1 −1 (t)
applied with ε = ∆/2 to t=t0 δ̃(t) ≤ tt=t
δ we obtain
0




∆2
∆
(t1 )
(t0 )
,
≤ exp −(t1 − t0 ) ·
Pr log(σ ) ≤ log(σ ) + (t1 − t0 ) ·
2
2(c+ − c− )2

i.e., the probability that the log step size grows by less than ∆/2 per
 iteration on average is
(t
)
0
exponentially small in t1 − t0 . For t1 ≫ t0 + 2/∆ · log(bT ) − log(σ ) the probability becomes
minuscule, and for t1 → ∞ it vanishes completely. Hence, with full probability, we arrive at a
21

contradiction. The same logic contradicts the assumption that σ (t) ≥ bH for all t ≥ t0 . Hence,
with full probability, sub-episodes of very small and very large step size are of finite length, and
according to lemma 15 the sequence of step sizes returns infinitely often to the interval [bT , bH ].
Next we show that there exists an infinite sub-sequence of iterations fulfilling equation (1).
Again, assume the contrary. We know already that σ (t) does not stay below bT or above bH for
an infinite time. Hence, there must exist an infinite sub-sequence fulfilling either
h
i
(t)
f
(t)
σ ∈ bT , ξ p T m
(2)
or

h
i

σ (t) ∈ ηpfH m(t) , bH .

(3)

Assume an infinite sub-sequence fulfilling equation (2). For each of these iterations, the success
probability is lower bounded by pT . Consider the case of consecutive successes. Until the event

σ (t) ≥ ξpfT m(t)
(4)

the probability of success remains
 lower bounded by pT > 0. The condition is fulfilled after at
+
most n = log(bH ) − log(bT ) c+ successes in a row, hence the probability of such an episode
+
occurring is lower bounded by pnT > 0. Lemma 15 ensures the existence of an infinite subsequence of iterations with this property. Each such episode contains a point fulfilling either
equation (1) or equation (4). By assumption, the former happens only finitely often, which
implies that the latter happens infinitely often.
Hence, this case as well as the alternative assumption of an infinite sequence fulfilling equation (3) result in an infinite sub-sequence with the property
h
i

σ (t) ∈ ηpfH m(t) , ec+ · bH .


Following the same line of arguments as above, as long as σ (t) ≥ ηpfH m(t) , the probability of
an
unsuccessful step is lower bounded by 1−pH > 0. After at most n− = log(bT )−log(bH )+e+ c−

unsuccessful steps in a row, the step size must have dropped below bT ≤ ηpfH m(t) , hence the
−
probability of such an episode occurring is lower bounded by (1 − pH )n > 0. According to
lemma 15, an infinite number of such episodes
these episodes do not
h occurs. By construction,

f
f
(t)
(t)
(t)
change m and, and they cross the interval ξpT m , ηpH m
. Therefore there exists an
infinite sub-sequence of iterations within this interval, in contradiction to the assumption.

22

