[name=Theorem,numberwithin=section]thm
[name=Corollary,numberwithin=section]cor

# Plus Strategies are Exponentially Slower for Planted Optima of Random Height

Johannes Lengler<EMAIL_ADDRESS>ETH ZürichZürichSwitzerland ,
Leon Schiller<EMAIL_ADDRESS>ETH ZürichZürichSwitzerland and
Oliver Sieberling<EMAIL_ADDRESS>ETH ZürichZürichSwitzerland

(2024)

###### Abstract.

We compare the $(1,\lambda)$-EA and the $(1+\lambda)$-EA on the recently
introduced benchmark DisOM, which is the OneMax function with randomly planted
local optima. Previous work showed that if all local optima have the same
relative height, then the plus strategy never loses more than a factor
$O(n\log n)$ compared to the comma strategy. Here we show that even small
random fluctuations in the heights of the local optima have a devastating
effect for the plus strategy and lead to superpolynomial runtimes. On the
other hand, due to their ability to escape local optima, comma strategies are
unaffected by the height of the local optima and remain efficient. Our results
hold for a broad class of possible distortions and show that the plus
strategy, but not the comma strategy, is generally deceived by sparse
unstructured fluctuations of a smooth landscape.

Evolutionary Algorithms, Evolutionary Optimization, Randomized Search
Heuristics, Run Time Analysis

††copyright: acmcopyright††journalyear: 2024††copyright:
acmlicensed††conference: Genetic and Evolutionary Computation Conference; July
14–18, 2024; Melbourne, VIC, Australia††booktitle: Genetic and Evolutionary
Computation Conference (GECCO ’24), July 14–18, 2024, Melbourne, VIC,
Australia††doi: 10.1145/3638529.3654088††isbn: 979-8-4007-0494-9/24/07††ccs:
Theory of computation Random search heuristics

##  1\. Introduction

A classical topic for Evolutionary Algorithms (EA) are the advantages and
disadvantages of elitism, i.e., whether best-so-far solutions should always be
kept in the population. Proponents of non-elitist strategies like comma
selection argue that the ability to discard the fittest solution may help in
escaping local optima. However, theoretical support for this claim has been
mixed (Auger et al., 2022), and comma selection does not give benefits in many
situations (Dang et al., 2021; Doerr, 2022). Until recently, the only
supportive theoretical pieces of evidence are for Cliff, where comma selection
can overcome a large plateau of local optima in polynomial time where plus
selection cannot (Hevia Fajardo and Sudholt, 2021), and for _Distorted Onemax_
DisOM, where a comma strategy outperforms plus strategies in a OneMax
landscape with planted local optima (Jorritsma et al., 2023).

However, both these results have some limitations. As Jorritsma, Lengler and
Sudholt argued in (Jorritsma et al., 2023), the Cliff function models a rather
peculiar type of landscape, and many local optima may not be represented well
by this landscape. Concretely, the Cliff function features a massive plateau
of local optima, and when an algorithm manages to escape this plateau, then
even a random walk ignoring fitness returns to the plateau with high
probability. This is arguably different from local optima in many natural
problems. It is certainly different from the global optimum (if unique), where
a random walk typically brings the algorithm further away from the optimum,
not back to it.

For these reasons, (Jorritsma et al., 2023) proposed DisOM as a new benchmark
with a different type of local optima. The benchmark is created from the
OneMax function by flipping a coin for each search point, and turning it into
a local optimum with some small probability $p$ by adding a distortion $D$ to
its fitness.111This can be seen as frozen Bernoulli noise. Frozen means that
two evaluations of the same search point return the same fitness. The paper
(Jorritsma et al., 2023) studied the case of constant $D$ (all distorted
points gain the same amount of fitness), and the results were mixed. On the
one hand, it was shown that the $(1,\lambda)$-EA can outperform the
$(1+\lambda)$-EA on DisOM for some parameter settings by a factor of almost
$O(n\log n)$. On the other hand, it was also shown for general parameter
settings that the factor can never exceed $O(n\log n)$. The reason was that
for constant $D$ the subset of distorted points still looks like a OneMax
landscape, just shifted by a constant $D$, and that the plus strategy can
still efficiently navigate in that landscape. Thus, in the setting of constant
$D$, the gain of comma selection is limited.

###  1.1. Our Result, briefly

In this paper, we also study the $(1,\lambda)$-EA and the $(1+\lambda)$-EA on
DisOM, and with the same parameter setting as in (Jorritsma et al., 2023), see
Section 2.3 for details. But, other than in (Jorritsma et al., 2023), for each
distorted point we choose the size $D$ of the distortion randomly from some
distribution $\mathcal{D}$, where we draw from the same distribution for all
distorted points. We make only the very mild assumptions on $\mathcal{D}$ that
it should not decay too extreme, $\text{Pr}\left[D\geq
d\right]/\text{Pr}\left[D\geq d+1\right]\leq n^{o(1)}$ for all $d>0$. This
includes all distributions with a polynomially or exponentially decaying tail,
like exponential distributions or power laws. Our results extend to
distributions like the Gaussian distribution, where the condition is only
satisfied for small values of $D$.

We have two main results: firstly, as expected, the local optima do not affect
the $(1,\lambda)$-EA, which stays efficient for settings that are efficient on
OneMax (see Section 2.3 for details on the parameter settings). This result is
not very surprising and is proved with similar techniques as in (Jorritsma et
al., 2023). The novel part is that the $(1+\lambda)$-EA is completely
deceived. Of course, it gets stuck in a local optimum, but that is not the
worst part. Optimistically, one might hope that it could escape from the local
optimum by sampling a search point with a larger OneMax. Although this would
need time, it might be tolerable. But before this happens, the algorithm will
likely find another distorted point with a slightly larger distortion. Thus it
trades its local optimum against another local optimum with a slightly higher
peak, which is even harder to escape. This leads to a vicious cycle in which
the algorithm entangles itself in increasingly worse local optima. Remarkably,
steps towards a higher local optimum typically also bring the algorithm
further away from the string $(1\ldots 1)$, so even if the $(1+\lambda)$-EA
manages to get close to the target region, it will get distracted and lose
this achievement.

For many natural distributions $\mathcal{D}$, including exponential and
Gaussian distributions, this leads to superpolynomial time for finding the
target fitness. To our best knowledge, this is the first theoretical
comparison between plus and comma strategies on “rugged” fitness landscapes
with local optima of random height.

###  1.2. Related Work

Apart from the paper (Jorritsma et al., 2023) discussed above, there is one
other theoretical study of a similar landscape by Friedrich, Kötzing, Neumann
and Radhakrishnan (Friedrich et al., 2022), which they call a
$\mathcal{D}$-rugged OneMax. They compare Random Local Search (RLS) and the
$(1+1)$-EA with the compact Genetic Algorithm (cGA) on a OneMax landscape with
frozen noise. The main differences in terms of landscape are that they add a
distortion to all search points, while we only plant a relatively small number
of local optima, and most search points are undistorted. Moreover, they only
consider Gaussian distributions (for cGA and RLS) and a geometric distribution
(for RLS and the $(1+1)$-EA), while we consider arbitrary distributions with a
tail which falls at most exponentially. For the cGA, an estimation-of-
distribution algorithm which does not rely on populations, they show that with
high probability, the algorithm never samples the same search point twice (in
a fixed-target setting with $k^{*}=\varepsilon n$). Thus, it is irrelevant
whether the noise is frozen or not, which allows them to apply previous
results about the cGA for non-frozen noise (Friedrich et al., 2016a). For the
$(1+1)$-EA, their results are similar in spirit as our more general result for
plus strategies: that the algorithm gets stuck after a few steps.

In another notable paper, Friedrich, Kötzing, Krejca and Sutton (Friedrich et
al., 2016b) also study different distributions $\mathcal{D}$, but in the
context of non-frozen noise, i.e., two different fitness evaluations of the
same search may give two different answers. They consider the $(\mu+1)$-EA and
ask what properties of $\mathcal{D}$ lead to _graceful scaling_ , i.e., to the
ability of the algorithm of overcoming even large amount of noise for
sufficiently large population size. Although the paper considers a rather
different setting (non-frozen noise, different algorithms), we suspect that
the classification of distributions that they find is similar to the classes
of distributions on which plus selection is also fast on DisOM. Similarly to
our result here, they find that exponentially decaying tails of the
distribution lead to large runtimes.222They only consider one particular
distribution with a single parameter, but from the exposition they make clear
that the exponentially decaying tails are the decisive property of the
distribution. On the other hand, truncated distributions (whose tail suddenly
drops to zero) like the uniform distribution on a small finite interval lead
to polynomial runtimes, and the proof intuition is similar to those in
(Jorritsma et al., 2023) showing that the $(1+\lambda)$-EA does not lose more
than a factor of $O(n\log n)$ over the $(1,\lambda)$-EA. Mind that the details
are quite different in many aspects, but nevertheless it might be worthwhile
to explore the similarities of both situations.

For further related work, especially on theoretical work on comma selection,
we refer the reader to the discussion in (Jorritsma et al., 2023).

##  2\. Setup and Formal Results

###  2.1. Distorted OneMax

In this paper, we consider optimization w.r.t. the objective function
_distorted One Max_ , which is a version of OneMax with randomly planted local
optima of variable height. More formally, we start with parameters
$p\in[0,1]$, and $\mathcal{D}$, which is a continuous probability distribution
over $\mathbb{R}^{+}$. We then define our objective function
$\textsc{DisOM}_{\mathcal{D}}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$ as

$\displaystyle\textsc{DisOM}_{\mathcal{D}}(x)=\begin{cases}|x|_{1}&\text{with
probability }1-p\\\ |x|_{1}+D&\text{with probability }p.\end{cases}$

where $D\sim\mathcal{D}$ is a sample from $\mathcal{D}$. We stress that we
draw the function $\textsc{DisOM}_{\mathcal{D}}$ only once before the run of
the algorithm (one independent sample for each distorted point). So, if the
algorithm queries the same search point twice, it will find the same fitness
value. This is different from noisy optimization, where two evaluations of the
same search point may yield different fitness values.

We require the following condition on the distribution $\mathcal{D}$, which
ensures that the tail of the distribution does not drop too fast. We remark
that this assumption is very weak and, in fact, met for almost all commonly
used distributions in practice, at least sufficiently close to $0$. The only
notable exception are distributions with a bounded support, i.e., such that
$\text{Pr}\left[D\geq d\right]=0$ for some $d\in\mathbb{R}$.

###### Assumption 1.

Let $\mathcal{D}$ be a continuous distribution and $D\sim\mathcal{D}$. There
is some $\sigma=n^{o(1)}$ and some $\hat{d}\in(0,\infty]$ such that for all
$d\leq\hat{d}$,

$\displaystyle\text{Pr}\left[D\geq d\right]\leq\sigma\text{Pr}\left[D\geq
d+1\right].$

Furthermore, $\text{Pr}\left[D\geq 0\right]=\Omega(1)$.

We assume the distribution $\mathcal{D}$ to be continuous because this allows
us to ignore the case that two distorted points have exactly the same
distortion, as this does not occur almost surely. Throughout the paper, we
will assume that $\mathcal{D}$ is fixed and does not depend on $n$. We further
remark that $\mathcal{D}$ may have a support over negative numbers as long as
it is positive with at least constant probability.

###  2.2. Main Results

We study the fixed target performance of the $(1+\lambda)$-EA and the
$(1,\lambda)$-EA with target $n-k^{*}$ on $\textsc{DisOM}_{\mathcal{D}}$,
where $k^{*}=o(n)$. To this end, we impose some assumptions on the choice of
parameters $k^{*},\lambda$ and $p$ which will be formally stated in the next
section but already referenced in the formal results here. To summarize them
very briefly, we have 2 which intuitively ensures that $p$ is sufficiently
large such that w.h.p., we find a distorted point before reaching the target
$n-k^{*}$ and the $(1+\lambda)$-EA will be inefficient, and we have 3 which is
sufficient for the $(1,\lambda)$-EA to be efficient on
$\textsc{DisOM}_{\mathcal{D}}$. More details are found in Section 2.3.

Our first main result states that the $(1+\lambda)$-EA is inefficient in this
setting if 1 is met and if $p$ is sufficiently large. This result is
established by showing that if the $(1+\lambda)$-EA ever comes close to the
optimum then it reaches a point of distortion at least $d\coloneqq
n^{\Omega(1)}$ and ZeroMax-value roughly $n^{1-\varepsilon}$ with high
probability. On the other hand, we show in Section 5 that the $(1,\lambda)$-EA
remains efficient in the same setting.

#### Inefficiency of the $(1+\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$.

Our first main result establishes that the $(1+\lambda)$-EA reaches a point of
high distortion that is still far away from the optimum.

[] Let $\varepsilon>0$ be a sufficiently small constant. Assume further that
$\mathcal{D}$ satisfies 1, and that $p$ is such that 2 is met. Then with high
probability, the $(1+\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$ either
spends $\mathcal{T}=\exp(n^{\varepsilon/8})$ iterations before reaching a
point $x$ with $\textsc{Zm}(x)\leq n^{1-\varepsilon}/4$, or visits a point $x$
of distortion at least $d\coloneqq\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$
before finding the first point with $\textsc{Zm}(x)<n^{1-4\varepsilon}$.

Using this, we derive the following general lower bound on the optimization
time of the $(1+\lambda)$-EA. It shows that the $(1+\lambda)$-EA already gets
stuck in local optima while it is still far from the optimum, that is, while
the number of zeros is still $n^{1-4\varepsilon}$ where $\varepsilon$ is an
arbitrarily small constant.

[$(1+\lambda)$-EA Lower Bound] Consider the $(1+\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ for a distribution $\mathcal{D}$ satisfying 1,
and $p$ satisfying 2. Fix any sufficiently small constant $\varepsilon>0$ and
let $T$ denote the number of function evaluations until the first point with
less than $n^{1-4\varepsilon}$ zeros is found. Let further $D$ be a random
variable with distribution $\mathcal{D}$ and let
$d\coloneqq\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$. Then, for any function
$g(n)=\omega(1)$, we have

$\displaystyle
T\geq\min\left\\{\exp(n^{\varepsilon/8}),\frac{1}{g(n)p\text{Pr}\left[D\geq
d\right]}\right\\}$

with high probability.

The proof of this theorem essentially relies on Section 2.2 which already
shows that we either spend $\exp(n^{\varepsilon/8})$ steps far from the
optimum, or find a point of large distortion, which requires
$(g(n)p\text{Pr}\left[D\geq d\right])^{-1}$ steps w.h.p. as said number
clearly dominates a geometric random variable with expectation
$(p\text{Pr}\left[D\geq d\right])^{-1}$.

Note that Section 2.2 result only gives a lower bound on the time required to
reach a point close to the all-ones-string, but not a lower bound on the time
required to find the first point of $\textsc{DisOM}_{\mathcal{D}}$-fitness at
least $n-k^{*}$. However, even in the latter case we can show a similar
statement, which we capture in the following remark.

###### Remark 1.

Section 2.2 also applies to the time required to find a point of
$\textsc{DisOM}_{\mathcal{D}}$-fitness $\geq n-k^{*}$. To see this, note that
the above theorem shows that we need time
$\min\\{\exp(n^{\varepsilon/8}),(p\text{Pr}\left[D\geq d\right])^{-1}\\}$
before finding the first point with less than $n^{1-4\varepsilon}$ zeros
w.h.p. In order to reach $\textsc{DisOM}_{\mathcal{D}}$-fitness $\geq n-k^{*}$
during this time, we would need to find a point of distortion at least
$d^{\prime}\coloneqq n^{1-4\varepsilon}-k^{*}$, which requires roughly
$(p\text{Pr}\left[D\geq d^{\prime}\right])^{-1}$ steps, which is already
greater than $(p\text{Pr}\left[D\geq d\right])^{-1}$ for sufficiently small
$\varepsilon>0$.

We sketch the implications of this general result for some common
distributions used in practice.

#### Exponential Distribution

Our illustrating example throughout this paper will be the exponential
distribution where $\text{Pr}\left[D\geq d\right]=\exp(-\varrho d)$ for some
constant $\varrho>0$. Here, we obtain a stretched exponential lower bound for
the $(1+\lambda)$-EA. We remark that it is not hard to extend this result to
the case of Laplacian noise as our proof techniques carry over even if some
points have negative distortion. [] Consider the $(1+\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ under 2 with $\mathcal{D}$ being an exponential
distribution. Then with high probability, the number of fitness evaluations
$T$ before the first point with less than $n^{1-4\varepsilon}$ zeros is found
satisfies

$\displaystyle T\geq\exp(n^{\Omega(1)}).$

#### Gaussian Distribution

In the case where $\mathcal{D}$ is a Gaussian distribution with density

$\displaystyle\rho(d)=\frac{1}{s\sqrt{2\pi}}\exp\left(-\frac{1}{2}\left(\frac{d}{s}\right)^{2}\right),$

where $s$ is the standard variation, we still obtain a super-polynomial lower
bound. The reason for this is that we can show that it satisfies 1 as long as
$d=o(\log(n))$, so our theorems show that we reach distortion
$d\geq\frac{\log(n)}{\log\log(n)}$ w.h.p. and the probability of sampling a
such distortion from $\mathcal{D}$ is

$\displaystyle\text{Pr}\left[D\geq\frac{\log(n)}{\log\log(n)}\right]\leq\exp\left(-\Omega\left(\frac{\log(n)}{\log\log(n)}\right)^{2}\right)=n^{-\omega(1)}.$

Hence, we obtain the following corollary.

[] Consider the $(1+\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$ under 2
with $\mathcal{D}$ being a Gaussian distribution. Then with high probability,
the number of fitness evaluations $T$ before the first point with less than
$n^{1-4\varepsilon}$ zeros is found satisfies

$\displaystyle T\geq n^{\Omega(\log(n)/(\log\log(n)^{2}))}=n^{\omega(1)}.$

#### Pareto Distribution

The third example we consider is the case where $\mathcal{D}$ is a Pareto
distribution where

$\displaystyle\text{Pr}\left[D\geq
x\right]=\left(\frac{x}{x_{0}}\right)^{1-\tau}$

for $x\in[x_{0},\infty]$ and $\tau>2$. That is, the tail decays polynomially
with exponent $\tau-1$. We show that in this case, the run time is at least
polynomial with an exponent that grows with $\tau$.

[] Consider the $(1+\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$ under 2
with $\mathcal{D}$ being a Pareto distribution. Then, for every sufficiently
small $\varepsilon>0$, there is a constant $c>0$ such that for every function
$g(n)=\omega(1)$, the number of fitness evaluations until the first point with
less than $n^{1-4\varepsilon}$ zeros is found satisfies

$\displaystyle T\geq\frac{n^{c(\tau-1)}}{g(n)p}$

with high probability.

We remark that we did not optimize the constants involved in the above
results. This is especially true for the maximally reachable distortion in
Section 2.2. We leave a further strengthening of our results in this regard
open for future work.

#### The $(1,\lambda)$-EA remains efficient

On the other hand, we show in Section 5 that the $(1,\lambda)$-EA remains
efficient on $\textsc{DisOM}_{\mathcal{D}}$ under the same assumptions on the
parameters $\lambda,p,$ and $k^{*}$ as in (Jorritsma et al., 2023) (these are
formally stated and explained in the next section). The analysis here is
largely identical to the one in (Jorritsma et al., 2023) with some technical
adjustments. [$(1,\lambda)$-EA Upper Bound] Consider the $(1,\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ under 3 and let $T$ be the number of function
evaluations until the first point with fitness $n-k^{*}$ is reached. Then,
with high probability,

$\displaystyle T=\Theta(n\log(n))$

We confirm our theoretical results with some empirical results on the run time
difference between the $(1+\lambda)$-EA and $(1,\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ which we present in Section 6.

#### Proof Techniques

The largest part of this work concentrates on proving Section 2.2 from which
most of our results follow. On a high level, we show that if the
$(1+\lambda)$-EA ever comes close to the optimum then it is very likely to
reach a point $x$ whose distortion is a sufficiently large constant and
$\textsc{Zm}(x)\approx n^{1-\varepsilon}$. This event “kickstarts” our
process: since the number of zeros is sub-linear in $n$, it is very likely
that we find a point of larger distortion before decreasing the number of
ones. The reason for this is that 1 ensures that the CDF of $\mathcal{D}$
decays slower than the probability of sampling an offspring that has more ones
than the current parent, i.e., the probability of increasing the number of
ones decays faster than the probability of increasing the distortion. This
discrepancy is so large that we can easily increase our distortion to
$\min\\{\hat{d}/2,n^{\Omega(1)}\\}$ without even once decreasing it.

The main difficulty in establishing this result is that we are dealing with
_frozen noise_ , i.e., we only sample the distortion of a point once,
regardless of how many times the algorithm “sees” it, and we do not get “fresh
randomness” at every visited point. This may induce dependencies between the
points the algorithm visits and the distribution of distorted points in the
neighborhood of a visited point, which make it difficult to establish a formal
argument. The problem here is that (1) using a union bound over all search
points in $\\{0,1\\}^{n}$ is too weak for our purposes, and that (2) the
neighborhood of a visited point may depend on the points visited and sampled
so far, so we cannot simply apply the union bound to only those points we
visit. We develop a novel technique to circumvent this problem by showing that
during the first $\mathcal{T}=\exp(n^{\varepsilon/8})$ iterations, the
algorithm never explores a large fraction of the neighborhood of a point
sufficiently close to the optimum before sampling said point itself. This
allows us to conclude that the neighborhood of a visited point $x$ is with
high probability largely unexplored when we first visit $x$, so we may defer
uncovering the distortion of most points close to $x$ until we visit $x$
itself. We refer the interested reader to Section 4.1 where this is
formalized.

###  2.3. Parameter Setup

We do not consider the time to find the optimum, but the time to find some
target fitness $n-k^{*}$. This is customary in the context of (frozen)
distortions or (non-frozen) noise (Prugel-Bennett et al., 2015; Jorritsma et
al., 2023; Friedrich et al., 2022) and has two reasons for us: first, the
global optimum may be attained by a distorted point which can only be found by
some exhaustive search among many candidates. Second, we want to balance two
requirements on $\lambda$: on the one hand, if $\lambda$ is too small then the
$(1,\lambda)$-EA is not even able to find the target fitness efficiently on
OneMax. On the other hand, if $\lambda$ is too large, then each generation is
very likely to create a clone of the parent, and the $(1,\lambda)$-EA loses
its ability to escape local optima. These two requirements are easier to
balance in a fixed-target setting with goal $n-k^{*}$, instead of asking for
the time to find the global optimum.

We continue by describing which parameter choices for $\lambda,k^{*}$, and $p$
are reasonable in our setting. These are essentially the same as in (Jorritsma
et al., 2023).

#### The population size $\lambda$.

We use the abbreviation $\eta=e/(e-1)$ such that $\eta^{-1}$ is approximately
equal to the probability of not cloning the parent when creating a single
offspring. We further define $q\coloneqq\eta^{-\lambda}$ to denote the
approximate probability of not cloning the parent when creating $\lambda$
offspring. This is a central quantity in the theory of the $(1,\lambda)$-EA as
it determines the probability of escaping a local optimum. Furthermore, it is
easy to see that if we choose $\lambda$ too large and thus $q$ too small (that
is $\lambda\geq C\log(n)$), then the $(1,\lambda)$-EA mimics the behavior of
the $(1+\lambda)$-EA for the first $n^{\Omega(1)}$ iterations. We therefore
consider the case where $\lambda$ is such that $q\geq n^{-1+\varepsilon}$,
i.e.,

$\displaystyle\lambda\leq(1-\varepsilon)\log_{\eta}(n)$

since this is known to be the regime where the $(1,\lambda)$-EA and the
$(1+\lambda)$-EA behave differently (Lehre, 2011).

#### The target $n-k^{*}$.

The reason why we consider optimization to $n-k^{*}$ instead of $n$ is that
the $(1,\lambda)$-EA is inefficient in finding the unique optimum of any
target function with unique optimum (such as OneMax) (Rowe and Sudholt, 2014),
but it is efficient in reaching a search point with fitness at least $n-k^{*}$
as long as

$\displaystyle\lambda\geq(1+\varepsilon)\log_{\eta}(n/k^{*})$

for some constant $\varepsilon>0$, as shown in (Antipov et al., 2019). In
total this means that we assume
$(1+\varepsilon)\log_{\eta}(n/k^{*})\leq\lambda\leq(1-\varepsilon)\log_{\eta}(n)$,
which is a non-empty range if $k^{*}=n^{\Omega(1)}$.

#### The distortion probability $p$

It is not hard to see that $p$ cannot be chosen too small, otherwise (more
precisely if $p=o(1/(n\log(n)))$), the $(1+\lambda)$-EA does not sample any
distorted point w.h.p. and thus remains fast. To make our results regarding
the inefficiency of the $(1+\lambda)$-EA applicable, we require a slightly
stronger assumption, which is needed to ensure that we reach a point of
sufficiently large distortion sufficiently close to the optimum, which is
needed to “kickstart” our process or reaching points of higher and higher
distortion.

###### Assumption 2 (Sufficient for Inefficiency of the $(1+\lambda)$-EA).

Let $\varepsilon>0$ be any constant. We assume that there is a constant $C>0$
such that $\lambda\leq C\log(n)$, and that for all constants $c>0$

$\displaystyle p\sigma^{-c}=\omega(1/(n\log(n))),$

where $\sigma=n^{o(1)}$ is the parameter from 1. In particular, this
assumption is satisfies when $p\geq n^{-1+\varepsilon}$ for some constant
$\varepsilon>0$.

We will further make two additional assumptions for the sake of technical
simplicity that will facilitate our proof that the $(1,\lambda)$-EA is
efficient on $\textsc{DisOM}_{\mathcal{D}}$. These are the same assumptions as
in (Jorritsma et al., 2023). First, we assume that $p=o(k^{*}/n)$ to ensure
that – at the target fitness – going closer to the optimum is more likely than
sampling another distorted point. Secondly, we make the assumption that
$q=\omega(p\lambda)$ to ensure that if there is no clone of the current
individual, it is likely to not sample a second distorted point. To make
matters simpler, we even require the slightly stronger condition $q\geq
p^{1-\varepsilon}$. We further need the condition
$q\leq(k^{*}/n)^{1+\varepsilon}$ to ensure a sufficiently large population
size to be efficient for optimizing to target $n-k^{*}$ on OneMax. Hence,
given a suitable value of $k^{*}$ and $\lambda$ to ensure that the
$(1,\lambda)$-EA is efficient on OneMax, we additionally require $p$ to be
sufficiently small to further ensure efficiency on
$\textsc{DisOM}_{\mathcal{D}}$. We remark that the latter is likely not
necessary, and we leave a study of the $(1,\lambda)$-EA without it open to
future work. Summarizing, we require the following for our analysis of the
$(1,\lambda)$-EA.

###### Assumption 3 (Sufficient for Efficiency of the $(1,\lambda)$-EA).

Let $\varepsilon>0$ be any constant and let $k^{*}=n^{\Omega(1)}$. We assume
that

$\displaystyle p^{1-\varepsilon}\leq q\leq(k^{*}/n)^{1+\varepsilon},$

or equivalently

$\displaystyle(1+\varepsilon)\log_{\eta}(n/k^{*})\leq\lambda\leq(1-\varepsilon)\log_{\eta}(1/p).$

##  3\. Preliminaries

#### General Notation.

We denote by $[n]$ the set of natural numbers at most $n$, i.e.,
$[n]=\\{1,\ldots,n\\}$, and we use standard Landau notation for expressing
asymptotic behavior with respect to $n$. Furthermore, we sometimes use the
notation $\tilde{\mathcal{O}}\mkern-2.0mu\left(g(n)\right)$ to hide
(poly-)logarithmic factors, i.e.,
$f(n)=\tilde{\mathcal{O}}\mkern-2.0mu\left(g(n)\right)$ if there is a constant
$c>0$ such that $f(n)\leq\log^{c}(n)g(n)$ for sufficiently large $n$. All
logarithms are with base $e$ if not indicated otherwise. An event holds _with
high probability_ (w.h.p.) if its probability tends to $1$ for $n\to\infty$.

We further denote by $\\{0,1\\}^{n}$ the set of all bit strings, and for any
$x\in\\{0,1\\}^{n}$, $\textsc{Om}(x),\textsc{Zm}(x)$ denotes the number of
one-bits and zero-bits of $x$, respectively. For two bit-strings
$x,y\in\\{0,1\\}^{n}$, we denote by $\textsc{HD}(x,y)$ the Hamming-distance of
$x$ and $y$, i.e., the number of positions in which $x,y$ differ. We further
denote by
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)=\\{y\in\\{0,1\\}^{n}\mid\textsc{HD}(x,y)=\ell\\}$
the set of all bit strings within Hamming-distance $\ell$ of $x$. We call the
set $\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ the _Hamming-layer_ $\ell$
of $x$. We further denote by
$\textsc{HL}^{\leq\ell}\mkern-3.0mu\left(x\right)=\bigcup_{i=1}^{\ell}\textsc{HL}^{i}\mkern-3.0mu\left(x\right)$
the union of all Hamming-layers within Hamming-distance at most $\ell$.

#### Algorithms

We consider the $(1+\lambda)$-EA and the $(1,\lambda)$-EA for
$\lambda\in\mathbb{N}$. See Algorithm 1 and Algorithm 2 for pseudocode. Both
algorithms aim to maximize a fitness function $f$ and maintain a solution
candidate $x_{t}$. In each iteration, they create $\lambda$ offspring
independently using standard mutation that flips each bit independently with
probability $1/n$. The only difference is that the $(1+\lambda)$-EA updates
its solution candidate only if there is an offspring of fitness at least
$f(x_{t})$ whereas the $(1,\lambda)$-EA always chooses $x_{t}$ to be the
offspring of largest fitness among all offspring generated in the previous
iteration (ties are broken uniformly at random in both algorithms).

Initialization: Choose $x_{0}\in\\{0,1\\}^{n}$ uniformly at random.

while  _$f(x_{t}) <n-k^{*}$_ do

Mutation: for  _$i=1$ to $\lambda$_ do

$y_{t}^{(i)}\leftarrow\text{mutate}(x_{t})$ by flipping each bit in $x_{t}$
independently with probability $1/n$.

end for

Selection:
$i_{\text{opt}}\leftarrow\operatorname*{arg\,max}_{i\in[\lambda]}f(y_{t}^{(i)})$
breaking ties uniformly at random

if  $f(y_{t}^{(i_{\text{opt}})})\geq f(x_{t})$ then $x_{t+1}\leftarrow
y_{t}^{(i_{\text{opt}})}$

end while

Algorithm 1 $(1+\lambda)$-EA for maximizing fitness function $f$ to target
$n-k^{*}$

Initialization: Choose $x_{0}\in\\{0,1\\}^{n}$ uniformly at random.

while  _$f(x_{t}) <n-k^{*}$_ do

Mutation: for  _$i=1$ to $\lambda$_ do

$y_{t}^{(i)}\leftarrow\text{mutate}(x_{t})$ by flipping each bit in $x_{t}$
independently with probability $1/n$.

end for

Selection:
$i_{\text{opt}}\leftarrow\operatorname*{arg\,max}_{i\in[\lambda]}f(y_{t}^{(i)})$
breaking ties uniformly at random.

$x_{t+1}\leftarrow y_{t}^{(i_{\text{opt}})}$

end while

Algorithm 2 $(1,\lambda)$-EA for maximizing fitness function $f$ to target
$n-k^{*}$

#### Auxiliary Lemmas.

We further use the following estimation of the factorial an the binomial
coefficient.

###### Lemma 3.1.

For every $k\in\mathbb{N}$ we have $k!=\Theta(k)^{k}$.

###### Proof.

By Stirling’s approximation, there is a constant $c>0$ such that

$\displaystyle k!$ $\displaystyle\leq c\sqrt{k}(k/e)^{k}$
$\displaystyle=\left(k\cdot c^{1/k}k^{1/(2k)}/e\right)^{k}$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(k\right)^{k}$

as $c^{1/k}k^{1/(2k)}=\Theta(1)$ for $k\geq 1$. The fact that
$k!=\Omega(k)^{k}$ can be shown analogously. ∎

###### Lemma 3.2.

If $k\leq n/2$ then

$\displaystyle\binom{n}{k}=n^{k}\Theta(k)^{-k}$

###### Proof.

It is immediate that

$\displaystyle\frac{n^{k}}{k!}\geq\binom{n}{k}\geq\frac{(n-k)^{k}}{k!}.$

By Lemma 3.1, we have $k!=\Theta(k)^{k}$ and we immediately conclude that
$\binom{n}{k}\leq n^{k}/k!=n^{k}\Omega(k)^{-k}$. For the other direction, we
use that

$\displaystyle\binom{n}{k}\geq\frac{(n-k)^{k}}{k!}=\frac{n^{k}(1-k/n)^{k}}{k!}.$

Due to our assumption $k\leq n/2$, the term $(1-k/n)^{k}$ is $\Omega(1)^{k}$
and thus $\binom{n}{k}=n^{k}\mathcal{O}\mkern-2.0mu\left(k\right)^{-k}$. ∎

We further need the following Chernoff bound.

###### Theorem 3.3 ((Dubhashi and Panconesi, 2009)).

Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables with range in $[0,1]$ and
let $X\coloneqq\sum_{i=1}^{n}X_{i}$. Then,

  1. (i)

$\text{Pr}\left[X\leq(1+\delta)\mathbb{E}\left[X\right]\right]\leq\exp\left(-\delta^{2}\mathbb{E}\left[X\right]/3\right)$
for $0<\delta<1$.

  2. (ii)

$\text{Pr}\left[X\leq(1-\delta)\mathbb{E}\left[X\right]\right]\leq\exp\left(-\delta^{2}\mathbb{E}\left[X\right]/2\right)$
for $0<\delta<1$.

  3. (iii)

$\text{Pr}\left[X\geq t\right]\leq 2^{-t}$ for all $t\geq
2e\mathbb{E}\left[X\right]$.

Moreover, we need the following multiplicative drift theorem with tail bounds
which we apply it in a slightly non-standard context in Lemma 4.1.

###### Theorem 3.4 (Theorem 2.5 in (Lengler and Steger, 2018)).

Let $(Z_{t})_{t\in\mathbb{N}}$ be a Markov chain with state space
$\mathcal{Z}$ and trace function
$\alpha:\mathcal{Z}\rightarrow\\{0\\}\cup[1,\infty)$ with $\alpha(Z_{0})=n$,
and assume that there is some $\delta>0$ such that for all $z\in\mathcal{Z}$

$\displaystyle\mathbb{E}\left[\alpha(Z_{t+1})\mid
Z_{t}=z\right]\geq(1-\delta)\alpha(z).$

Let further $T=\inf\\{t\geq 0\mid\alpha(Z_{t})=0\\}$. Then for any $k>0$,

$\displaystyle\text{Pr}\left[T\geq\left\lceil\frac{\log(n)+k}{|\log(1-\delta)|}\right\rceil\right]\leq
e^{-k}.$

Additionally, we use the following straightforward estimate of the maximum
number of bits flipped during a fixed time horizon.

###### Lemma 3.5.

Within the first $\mathcal{T}$ iterations of the algorithm, the maximum number
of bits flipped in a single mutation is at most
$\log_{2}(\mathcal{T})+\log^{2}{n}$ with probability at least
$1-n^{-\omega(1)}$.

###### Proof.

The number of bits flipped in a single mutation is a binomial random variable
$R\sim\text{Bin}(n,1/n)$. By a Chernoff bound (Theorem 3.3), we have that

$\displaystyle\text{Pr}\left[R\geq r\right]\leq 2^{-r}$

for $r\geq 2e$. Hence, by Markov’s inequality, the probability that we flip
more than $r$ bits at least once during $\mathcal{T}$ iterations is at most
$\mathcal{T}2^{-r}$. Setting $r=\log_{2}(\mathcal{T})+\log^{2}(n)$ this is at
most $n^{-\omega(1)}$ as desired. ∎

##  4\. Analysis of the $(1+\lambda)$-EA

We give a high level description of why plus selection takes super-polynomial
time before giving the formal proofs. The idea is as follows. The
$(1+\lambda)$-EA will very likely run into a distorted point while being
within distance roughly $n^{1-\varepsilon}$ to the optimum for any
sufficiently small constant $\varepsilon$. If we are at a point of distortion
$d$, then in order to accept a search point of lower distortion, we would have
to increase the number of ones in the current individual. However, as the
number of zeros is sub-linear, this is rather unlikely. Instead, if
$\mathcal{D}$ satisfies 1, it is much more likely to accept a point of
distortion at least $d+1$ because 1 ensures that the CDF of $\mathcal{D}$
decays slower than the probability of increasing the number of ones. Indeed,
if we uniformly sample a point in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$, then the probability of
finding an acceptable individual of distortion at least $d+1$ is at least
$p^{+}\coloneqq p\text{Pr}\left[D\geq d+\ell\right]$. On the other hand, the
probability of decreasing distortion by finding a point that increases the
number of ones is at most $p^{-}\coloneqq
n^{-\Omega(\varepsilon\ell)}p\text{Pr}\left[D\geq d-\ell\right]$. Hence, we
get that $p^{+}/p^{-}\geq n^{\Omega(\varepsilon\ell)}\sigma^{2\ell}$, which is
$n^{\Omega(1)}$ for all $\ell\geq 1$. Hence, the probability of not increasing
the current distortion by at least $1$ is only $n^{-\Omega(1)}$, which implies
that we can reach a distortion of $n^{\Omega(1)}$ w.h.p. without even once
going back to a smaller distortion.

However, the formal proof of this is significantly complicated by the fact
that the distortion of each search point is assigned only once and does not
change if we sample a given point multiple times, so we do not get “fresh
randomness” at each visited search point and potentially even introduce
dependencies between visited points and their neighborhoods. One way to remedy
this would be to use concentration bounds to show that the number of points of
a certain distortion in the neighborhood of a given point concentrates well
around its expectation. However, we would have to do this for all possible
distortions we are interested in and then apply union bounds over _all_ search
points in $\\{0,1\\}^{n}$, which are simply too many to make the statements
obtained this way meaningful. Another approach would be to apply the union
bound only to those individuals we actually visit. However, this does not
solve the first issue and – more importantly – it does not allow us to get rid
of possible dependencies between the set of visited points and their
neighborhoods. The problem here is that the number of search points close to
$x$ that have a certain distortion might depend on which search points we
visited before $x$; indeed if we visit many points close to $x$ before $x$
itself, then we know that all the points visited before $x$ (and the points
sampled and discarded before visiting $x$) have fitness at most as large as
that of $x$ and hence, the number of points with a certain distortion that are
close to $x$ might be very different than what we would expect to the case for
the “typicial” search point. For this reason, we use the following subsection
to develop a technique for largely getting rid of these dependencies. We
accomplish this by establishing that for every visited point $x$ sufficiently
close to the optimum during the first $\mathcal{T}=\exp(n^{\varepsilon/8})$
iterations, the algorithm has only “seen” a small fraction of the neighborhood
of $x$ before finding $x$ itself.

###  4.1. Ensuring uniform Exploration of the Search Space

Our argument consists of two steps. First – in Lemma 4.1 – we show that w.h.p.
from the set of all points with a certain number of ones, only a small number
of points is ever visited. To this end, we define the $k$-th OneMax-layer as
$\textsc{Ol}(k)=\\{x\in\\{0,1\\}^{n}\mid\textsc{Om}(x)=k\\}$ and show that
only roughly $\log(|\textsc{Ol}(k)|)$ points in $\textsc{Ol}(k)$ are visited.
Intuitively, for non-distorted points, this follows because a fitness
improvement is almost as easy to find as a search point of the same fitness.
For distorted points, we use the fact that once we found the first distorted
point in $\textsc{Ol}(k)$, we can only accept another individual in
$\textsc{Ol}(k)$ if this point has a larger distortion than before. However,
each time we accept a new individual, we cut the number of individuals with
even higher distortion in half (in expectation). See Figure 1 for an
illustration. In the second part of our argument (Lemma 4.2), we use this fact
to show that with high probability – during the first $\mathcal{T}$ steps – we
only uncover a sub-constant fraction of
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ before sampling $x$ itself for
the first time, for all points $x$ which are sufficiently close to the
optimum.

###### Lemma 4.1.

Let $x\in\\{0,1\\}^{n}$ be a fixed search point and let $k\in\mathbb{N}$. If
$\hskip 2.84544ptV_{k}$ denotes the set of accepted search points in
$\textsc{Ol}(k)$, then with probability at least $1-n^{-\omega(1)}$,

$\displaystyle|V_{k}(x)|=\mathcal{O}\mkern-2.0mu\left(\log(|\textsc{Ol}(k)|)+\log^{2}(n)\right).$

###### Proof.

Recall that $\textsc{Ol}(k)$ is the set of all bit strings with exactly $k$
ones. We show the statement in two parts. First, we show that only
$\log^{2}(n)$ non-distorted points with $k$ ones are visited. Afterwards, we
show that the number of visited points that are distorted is
$\mathcal{O}\mkern-1.0mu(\log(|\textsc{Ol}(k)|+\log^{2}(n)))$.

For the first part, we bound the number of visited search point $x$ in
$\textsc{Ol}(k)$ which are not distorted. To this end, we show that – once we
visit a non-distorted point in $\textsc{Ol}(k)$ – it is very likely that we
only sample few other points in $\textsc{Ol}(k)$ before finding a point of
strictly larger fitness than $x$. This implies that whenever we go back to an
individual in $\textsc{Ol}(k)$ at a later time, this point must be distorted
as the overall fitness never decreases. To show this, we note two things.
First, if the next point we visit has fewer one-bits than the current point,
then it must be distorted with fitness at least as large as $x$. Since the
distribution $\mathcal{D}$ is continuous, the probability of getting exactly
the same fitness is zero, so the offspring has _strictly_ larger fitness.
Secondly, if we sample a point with strictly more one-bits than $x$, then we
also strictly increase the fitness, regardless of whether or not said point is
distorted. Hence, it suffices to bound the number of times we create an
offspring with parent in $\textsc{Ol}(k)$ that is also in $\textsc{Ol}(k)$
before we sample the first point with more ones than $x$. To this end, note
that in order to sample offspring in $\textsc{Ol}(k)$, we need to flip the
same number of one- and zero-bits, so the probability of sampling such an
offspring is at most

$\displaystyle\sum_{\ell=1}^{n}\hskip
2.84544pt\binom{k}{\ell}\binom{n-k}{\ell}\hskip
2.84544ptn^{-2\ell}\leq\sum_{\ell=1}^{n}\left(\frac{k(n-k)}{n^{2}}\right)^{\ell}$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(\frac{k(n-k)}{n^{2}}\right)$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left((n-k)/n\right).$

On the other hand, the probability of increasing the number of one-bits by
flipping exactly one zero-bit to a one and not changing anything else is at
least $(n-k)/n(1-1/n)^{n-1}=\Omega((n-k)/n)$. Accordingly, conditional on the
event that a given offspring is either in $\textsc{Ol}(k)$ or increases the
number of one-bits, the latter case occurs with probability $\Omega(1)$.
Hence, by a Chernoff-bound as in Theorem 3.3, after $\log^{2}(n)$ such
samples, we created at least one offspring with more one-bits with probability
at least $1-\exp(-\Omega(\log^{2}(n))\geq 1-n^{-\omega(1)}$. We may still
create at most $\lambda-1$ offspring of the same generation afterwards, but
those are negligible since $\lambda=O(\log n)$.

For the second part, we bound the number of visited distorted points in
$\textsc{Ol}(k)$. To this end, we uncover for all bit-strings in
$\textsc{Ol}(k)$ if they are distorted or not, but without uncovering their
exact distortion. Then, every time we sample one of these distorted points
$z$, we only uncover which points have distortion larger and smaller than $z$
but without uncovering the exact distortion. This way – due to the elitist
behavior of the $(1+\lambda)$-EA– we cut the expected number of visitable
search points in half every time we sample one of them. To this end, let
$R_{0}$ be the set of distorted individuals obtained in this way. Clearly,
$|R_{0}|\leq|\textsc{Ol}(k)|$. Every time we sample an individual $y$ in
$R_{0}$, we uncover only which individuals in $R_{0}$ have strictly higher and
strictly lower distortion than $y$, respectively. Note that there are no
points of equal distortion because $\mathcal{D}$ is a continuous distribution.
We denote the set of individuals with strictly higher fitness than $y$ by
$R_{1}$ and repeat the same procedure whenever we sample the first individual
in $R_{1}$ to obtain $R_{2}$, then $R_{3}$ and so on. Now in every step $t$,
the expected size of $R_{t}$ is
$\mathbb{E}\left[R_{t}\right]=(|R_{t-1}|-1)/2\leq|R_{t-1}|/2$. Using
multiplicative drift with tail bounds as in Theorem 3.4, we get that the
number of steps $T$ until $R_{T}$ consists only of a single individual is
$\mathcal{O}\mkern-1.0mu(\log(|\textsc{Ol}(k)|)+\log^{2}(n))$ with probability
at least $1-n^{-\omega(1)}$. ∎

We now proceed with the second part of our exploration argument and show that
for search points relatively close to the optimum, only a small fraction of
its neighborhood is already uncovered when we first visit said point.

Figure 1. Illustration for the proof of Lemma 4.1. The circles represent all
distorted points in $\textsc{Ol}(k)$, the red ones are the ones visited by the
algorithm. Every time, we sample a new distorted point $y$ in
$\textsc{Ol}(k)$, we cut the set of points with distortion larger than $y$ in
half (in expectation). Hence, only
$\mathcal{O}\mkern-1.0mu(\log(|\textsc{Ol}(k)|))$ distorted points in
$\textsc{Ol}(k)$ are visited w.h.p. Figure 2. Illustration for the proof of
Lemma 4.2. We generate offspring from parent $y$ with $\textsc{HD}(x,y)=\ell$
in two steps: First decide which $k\sim\text{Bin}(\ell,1/n)$ bits to flip
among the bits that differ between $x$ and $y$ to create the intermediate
offspring $z^{(1)}$; then decide which bits to flip among the remaining bits
to create the final offspring $z^{(2)}$.

###### Lemma 4.2.

Let $\varepsilon,\delta>0$ be two sufficiently small constants, and set
$\mathcal{T}\coloneqq\exp(n^{\delta})$ and $r\coloneqq n^{2\delta}$. Then with
high probability, for all $1\leq s\leq r$ and for all points
$x\in\\{0,1\\}^{n}$ with at most $t\coloneqq n^{1-\varepsilon}$ zero-bits,
only a fraction of

$\displaystyle\mathcal{O}\mkern-2.0mu\left(r^{3}(t+r)\log^{2}(n)/n\right)+o(1)$

of $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ is uncovered during the first
$\mathcal{T}$ iterations before $x$ is first sampled.

###### Proof.

Let $y$ be an arbitrary search point that was visited before $x$ is first
sampled and let $I$ be the set of bits at which $x$ and $y$ differ. We further
define $\ell\coloneqq|I|=\textsc{HD}(x,y)$. We call $I$ the _first block_ and
$[n]\setminus I$ the _second block_ , respectively, and we think of the
process of creating an offspring with parent $y$ as follows. In the first
step, we decide which bits to flip within $I$ and we denote the (intermediate)
offspring generated this way by $z^{(1)}$. In the second step, we subsequently
decide which bits to flip in $[n]\setminus I$ and denote the final offspring
obtained this way by $z^{(2)}$. An illustration for this is given in Figure 2.
Note that in the first step, the Hamming distance to $x$ decreases while in
the second step it increases, i.e.,
$\textsc{HD}(x,z^{(1)})\leq\textsc{HD}(x,y)$ and
$\textsc{HD}(x,z^{(1)})\leq\textsc{HD}(x,z^{(2)})$. To bound the number of
search points uncovered in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ before
sampling $x$ itself for the first time, we distinguish two ways of uncovering
a search point in Hamming-layer $s$ around $x$.

Case 1: $\textsc{HD}(x,z^{(1)})=0$. Let $x$ be a fixed search point. Assuming
case 1, we already flipped all the bits in $I$ after the first sampling step.
In the second step, we then have a constant probability of not flipping any
other bit and thus sampling $x$ itself. This implies that the number of such
samples is bounded. More precisely, among $n/\log(n)$ samples in which
$z^{(1)}=x$, the probability that we have at least one sample for in which
also $z^{(2)}=x$ is at least

$\displaystyle 1-\exp(-\Omega(n/\log(n)))=1-\exp(-n^{1-o(1)}).$

Even if all these $n/\log(n)$ samples fall into
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ (for $1\leq s\leq r$), this only
corresponds to a fraction of $o(1)$ uncovered points as
$|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)|\geq n$ for all relevant $s$. Note
that this argument works regardless of how many points we visit before
sampling $x$. Furthermore, the number of bit strings with at most
$n^{1-\varepsilon}$ zero-bits is at most

$\displaystyle\sum_{k=0}^{n^{1-\varepsilon}}\binom{n}{k}\leq\sum_{k=0}^{n^{1-\varepsilon}}n^{k}\leq
n^{n^{1-\varepsilon}}\sum_{k=0}^{n^{1-\varepsilon}}n^{-k}=cn^{n^{1-\varepsilon}}$

where $c>0$ is a constant. By a union bound, we conclude that our statement
applies to all such strings $x$ with probability at least

$\displaystyle 1-cn^{n^{1-\varepsilon}}\exp\left(-n^{1-o(1)}\right)$
$\displaystyle\hskip
28.45274pt=1-c\exp\left(\log(n)n^{1-\varepsilon}-n^{1-o(1)}\right)=1-o(1).$

Case 2: $\textsc{HD}(x,z^{(1)})>0$. In this case, we show that (for suitable
$r,k$), the number of points in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$
that can be reached from a fixed parent $y$ in this way is sub-constant
_deterministically_. Afterwards, we use Lemma 4.1 to bound the number of
distinct parents $y$ and Lemma 3.5 to bound the maximal number of bits flipped
in a single iteration to show that all points visited sufficiently close to
$x$ combined can only uncover a small fraction of
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$. In the following, we assume that
$\ell\leq 2r$, because we will later show that at most $r$ bits are flipped in
a single iteration, so for $\ell$ larger than $2r$, we cannot reach
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$.

For the first part, consider a fixed parent $y$ and recall that
$\ell=|I|=\textsc{HD}(x,y)$. To reach a point in
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ from $y$, we need to flip at least
$k_{\min}=\max\\{0,\ell-s\\}$ and at most $k_{\max}=\ell-1$ bits in $I$ as
otherwise, we either do not reach $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$
or we are in case 1. We count all points in
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ that can be reached from parent
$y$ by flipping between $k_{\min}$ and $k_{\max}$ bits in $I$. To this end,
let $A_{k}(x,y)$ be the set of points that differ in $k$ bits from $y$ in $I$.
Note further that if we flip $k$ bits in $I$, then we need to additionally
flip $s-(\ell-k)$ bits in $[n]\setminus I$ to reach
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$. Accordingly, the fraction of
points in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ reachable from $y$ this
way is

$\displaystyle\sum_{k=k_{\min}}^{k_{\max}}\frac{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)\cap
A_{k}(x,y)|}{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)|}$
$\displaystyle=\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{k}\binom{n-\ell}{s-(\ell-k)}/\binom{n}{s}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{k}\binom{n}{s-(\ell-k)}/\binom{n}{s}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{k}\frac{(n-s)!s!}{(n-s+\ell-k)!(s-\ell+k)!}.$

It is easy to see that $\frac{s!}{(s-\ell+k)!}\leq s^{\ell-k}$ and that
$\frac{(n-s)!}{(n-s+\ell-k)!}\leq(n-s)^{-(\ell-k)}$. Accordingly,

$\displaystyle\sum_{k=k_{\min}}^{k_{\max}}\frac{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)\cap
A_{k}(x,y)|}{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)|}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{k}\left(n-s\right)^{k-\ell}s^{\ell-k}$
$\displaystyle=\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{k}\left(\frac{s}{n-s}\right)^{\ell-k}$
$\displaystyle=\sum_{k=k_{\min}}^{k_{\max}}\binom{\ell}{\ell-k}\left(\frac{s}{n-s}\right)^{\ell-k}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\mathcal{O}\mkern-2.0mu\left(\frac{\ell}{\ell-k}\right)^{\ell-k}\left(\frac{s}{n-s}\right)^{\ell-k}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\mathcal{O}\mkern-2.0mu\left(\frac{\ell
s}{(\ell-k)(n-s)}\right)^{\ell-k}$
$\displaystyle\leq\sum_{k=k_{\min}}^{k_{\max}}\mathcal{O}\mkern-2.0mu\left(\frac{\ell
s}{n-s}\right)^{\ell-k}.$

Now, because the sum is geometric, because $k\leq\ell-1$ and because $\ell
s\leq 2r^{2}=o(n)$ (for sufficiently small $\delta$, i.e., $\delta<1/4$), we
conclude that

$\displaystyle\sum_{k=k_{\min}}^{k_{\max}}\frac{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)\cap
A_{k}(x,y)|}{|\textsc{HL}^{s}\mkern-3.0mu\left(x\right)|}$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(\frac{\ell s}{n}\right).$

We have thus shown that for every visited point $y$ at Hamming distance $\ell$
of $x$, only a fraction of $\mathcal{O}\mkern-2.0mu\left(\ell s/n\right)$ of
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ is uncovered for all $1\leq s\leq
r$ under the prerequisites of case 2. However, there might be multiple points
$y$ we visit before sampling $x$ for the first time. To bound this number, we
use Lemma 4.1, and we denote by $\mathcal{E}_{\text{visit}}$ the event that
the number of visited points with exactly $t$ one-bits is

$\displaystyle\mathcal{O}\mkern-2.0mu\left(\log(|\textsc{Ol}(t)|)+\log^{2}(n)\right)$

for all $t\in[n]$. By Lemma 4.1 and a union bound, this occurs with
probability $1-n^{-\omega(1)}$. Furthermore, we let
$\mathcal{E}_{\text{flip}}$ be the event that the maximum number of bits
flipped in a single mutation during the first $\mathcal{T}=\exp(n^{\delta})$
iterations is $r=n^{2\delta}$. Note that by Lemma 4.1 and Lemma 3.5,
$\mathcal{E}_{\text{visit}}\cap\mathcal{E}_{\text{flip}}$ occurs with
probability $1-n^{-\omega(1)}$.

Assuming this, we bound the total fraction of the number of uncovered points
in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ under the prerequisites of case
2. To this end, note that conditional on $\mathcal{E}_{\text{flip}}$, only
points within Hamming distance $r+s\leq 2r$ of $x$ can uncover points in
$\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$, so we only have to take case
$\ell\leq 2r$ into account. Note that the set of points within hamming
distance $2r$ of $x$ covers at most $4r$ OneMax-layers. Furthermore, because
$x$ has at most $t\coloneqq n^{1-\varepsilon}$ zero-bits, the size of each
such level is at most

$\displaystyle\binom{n}{t+4r}\leq n^{t+4r},$

and since $\mathcal{E}_{\text{visit}}$ occurs, in each such level only

$\displaystyle\mathcal{O}\mkern-2.0mu\left(\log(n^{t+4r})+\log^{2}(n)\right)=\mathcal{O}\mkern-2.0mu\left((t+r)\log^{2}(n)\right)$

points are visited. Therefore, if
$\mathcal{E}_{\text{visit}}\cap\mathcal{E}_{\text{flip}}$ occurs, then the
fraction of uncovered points in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$
under the prerequisites of case 2 is at most

$\displaystyle\mathcal{O}\mkern-2.0mu\left(r(t+r)\log^{2}(n)\frac{\ell
s}{n}\right)=\mathcal{O}\mkern-2.0mu\left(\frac{r^{3}(t+r)\log^{2}(n)}{n}\right)$

where we bounded $\ell\leq 2r$ and $s\leq r$. ∎

###  4.2. Climbing up the Distortion Ladder

In this section, we prove our first main theorem stating that under 1 and with
high probability, the $(1+\lambda)$-EA reaches a point of large distortion
before coming close to the optimum. See 2.2

We prove this statement by showing that we likely reach a point that has
sufficiently large distortion and ZeroMax-value in the order of
$n^{1-\varepsilon}$ for arbitrarily small $\varepsilon>0$. When this happens,
it is very likely that the next accepted individual has larger distortion.

In the following, we will fix the time horizon
$\mathcal{T}=\exp(n^{\varepsilon/8})$ as in Section 2.2 mainly to ensure a
bounded number of bit-flips in a single iteration. We further denote by
$\mathcal{G}$ the event described in Lemma 4.2 for $\delta=\varepsilon/8$.
That is, $\mathcal{G}$ denotes the event that during the first $\mathcal{T}$
iterations, for all $x\in\\{0,1\\}^{n}$ with at most $t=n^{1-\varepsilon}$
zeros and for all $1\leq s\leq r=n^{\varepsilon/4}$, the fraction of points
uncovered in $\textsc{HL}^{s}\mkern-3.0mu\left(x\right)$ before first sampling
$x$ is at most

$\displaystyle\mathcal{O}\mkern-2.0mu\left(r^{3}(t+r)\log^{2}(n)/n\right)+o(1)=o(1).$

We note that $\mathcal{G}$ occurs with high probability, and we shall make it
clear when we condition on $\mathcal{G}$ in the following lemmas. We start
with the following auxiliary statement that bounds the probability of not
decreasing the number of ones for a search point with $k$ zeros.

###### Lemma 4.3.

Let $x$ be the current individual with $\textsc{Zm}(x)=k=o(n)$, and let
$\ell\leq n/2$. Let further $y$ be an offspring with parent $x$. Then for all
$t\in\mathbb{N}_{0}$,

$\displaystyle\text{Pr}\left[\textsc{Om}(y)\geq\textsc{Om}(x)+t\mid\ell\text{
bits flip in
}x\right]=\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\lceil\frac{\ell+t}{2}\rceil}$

###### Proof.

To change OneMax-fitness by at least $t$, at least $\lceil(\ell+t)/2\rceil$ of
the flipped bits need to be among the current $0$-bits. As there are
$\binom{n}{\ell}$ possibilities of flipping $\ell$ bits in total, we have

$\displaystyle\text{Pr}\left[\textsc{Om}(y)\geq\textsc{Om}(x)+t\mid\ell\text{
bits flip in }x\right]$ $\displaystyle\hskip
85.35826pt=\sum_{i=\lceil\frac{\ell+t}{2}\rceil}^{\ell}\frac{\binom{k}{i}\binom{n-k}{\ell-i}}{\binom{n}{\ell}}$
$\displaystyle\hskip
85.35826pt\leq\sum_{i=\lceil\frac{\ell+t}{2}\rceil}^{\ell}\frac{k^{i}}{i!}\frac{\ell!(n-\ell)!}{(\ell-i)!(n-\ell+i)!}$
$\displaystyle\hskip
85.35826pt\leq\sum_{i=\lceil\frac{\ell+t}{2}\rceil}^{\ell}\frac{k^{i}}{(n-\ell)^{i}}\frac{\ell^{i}}{i!}$
$\displaystyle\hskip
85.35826pt\leq\sum_{i=\lceil\frac{\ell+t}{2}\rceil}^{\ell}\frac{k^{i}}{(n/2)^{i}}\frac{\ell^{i}}{\Omega(\ell)^{i}}$

where in the last step we used $i!=\Omega(i)^{i}$ by Lemma 3.1 and $l\leq
n/2$. Hence,

$\displaystyle\text{Pr}\left[\textsc{Om}(y)\geq\textsc{Om}(x)+t\mid\ell\text{
bits flip in }x\right]$
$\displaystyle=\sum_{i=\lceil\frac{\ell+t}{2}\rceil}^{\ell}\mathcal{O}\mkern-2.0mu\left(k/n\right)^{i}$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\lceil\frac{\ell+t}{2}\rceil}$

because $k=o(n)$ so the sum is geometric. ∎

We further need the following lemma ensuring that the number of points of a
certain distortion in $\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$
concentrates well if $\ell$ is of the same order as $d$.

###### Lemma 4.4.

Consider any fixed visited point $x$ during the first $\mathcal{T}$ iterations
with $\textsc{Zm}(x)\leq n^{1-\varepsilon}$. Assume that $\ell,d$ (with
$d\leq\hat{d}$) are such that there are constants
$\varepsilon_{1},\varepsilon_{2}>0$ such that

$\displaystyle\varepsilon_{1}d\leq\ell\leq r$

and

$\displaystyle\frac{\log(\ell)}{\log(n)}+\frac{\log(1/p)}{\ell\log(n)}\leq
1-\varepsilon_{2}.$

Let $z$ be a uniform sample from
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ and let
$Z\subseteq\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ be the set of points
with distortion $\geq d$. Then, we have

$\displaystyle\frac{|Z|}{|\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)|}=\Omega(p\sigma^{-d})$

with probability $1-n^{-\omega(1)}$.

###### Proof.

Conditional on $\mathcal{G}$, we can uncover a fraction of $(1-o(1))$ of
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ when first visiting $x$. We
show that $\mathbb{E}\left[|Z|\mid\mathcal{G}\right]=n^{\Omega(1)}$, then the
statement follows by a Chernoff bound. By Lemma 3.2 and 1, we note that the
expected number of points in $Z$ is

$\displaystyle\mathbb{E}\left[|Z|\mid\mathcal{G}\right]$
$\displaystyle\geq(1-o(1))\binom{n}{\ell}p\text{Pr}\left[D\geq d\right]$
$\displaystyle\geq
c_{2}p\left(\frac{n}{c_{1}\ell}\right)^{-\ell}\sigma^{-\ell/\varepsilon_{1}}$
$\displaystyle=c_{2}p\left(\frac{n\sigma^{-1/\varepsilon_{1}}}{c_{1}\ell}\right)^{\ell}=c_{2}p\cdot
n^{\ell(1-o(1))}\ell^{-\ell}$

where $c_{1}$ and $c_{2}$ are constants. To show that this is $\geq
n^{\Omega(1)}$, we note that

$\displaystyle\frac{\log(\mathbb{E}\left[|Z|\mid\mathcal{G}\right])}{\log(n)}$
$\displaystyle\hskip
28.45274pt\geq\ell\left(1-o(1)-\frac{\log(\ell)}{\log(n)}\right)-\frac{\log(1/p)}{\log(n)}+\frac{\log(c_{2})}{\log(n)}$
$\displaystyle\hskip
28.45274pt=\ell\left(1-\frac{\log(\ell)}{\log(n)}-\frac{\log(1/p)}{\ell\log(n)}-o(1)\right)\pm
o(1)$ $\displaystyle\hskip 28.45274pt\geq\ell(\varepsilon_{2}-o(1))\pm o(1)$
$\displaystyle\hskip 28.45274pt=\Omega(1).$

Thus, a Chernoff bound implies that
$|Z|=\Theta(\mathbb{E}\left[|Z|\mid\mathcal{G}\right])$ with probability
$1-n^{-\omega(1)}$ conditional on $\mathcal{G}$. This implies that

$\displaystyle\frac{|Z|}{|\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)|}$
$\displaystyle=\Theta(\mathbb{E}\left[|Z|\mid\mathcal{G}\right])/\binom{n}{\ell}$
$\displaystyle=\Theta(p\text{Pr}\left[D\geq d\right])=\Omega(p\sigma^{-d}).$

Now, because $\mathcal{G}$ occurs with probability $1-n^{-\omega(1)}$, this
also holds with probability $1-n^{-\omega(1)}$ unconditionally, as desired. ∎

Using this, we show that we likely reach an individual of sufficiently large
distortion and roughly $n^{1-\varepsilon}$ zeros. This will be needed to
kickstart our process.

###### Lemma 4.5.

Let $d_{0},\varepsilon>0$ be constants. Then with high probability, the
$(1+\lambda)$-EA either reaches a point $x$ with distortion at least $d_{0}$
and $\textsc{Zm}(x)\in[n^{1-3\varepsilon},n^{1-\varepsilon}/2]$ within the
first $\mathcal{T}=\exp(n^{\varepsilon/8})$ iterations, or $\mathcal{T}$
iterations pass during which the current individual $x$ fulfills
$\textsc{Zm}(x)\geq n^{1-\varepsilon}/4$.

###### Proof.

We follow a strategy very similar to (Jorritsma et al., 2023, Section 5),
i.e., we show our statement in the following three parts. The difference is
that we have to ensure that we reach a point of _sufficiently large_
distortion instead of just any distorted point. As key steps, we shows that
the following three points hold w.h.p.

  1. (i)

Either $\mathcal{T}$ iterations pass and all visited points have Zm-value at
least $n^{1-\varepsilon}/4$ or a point $x$ with $\textsc{Zm}(x)\in
I\coloneqq[n^{1-2\varepsilon},n^{1-\varepsilon}/4]$ is visited.

  2. (ii)

If a point with $\textsc{Zm}(x)\in I$ is visited, then during the next
$\Omega(n\log(n))$ iterations, the current individual $x$ fulfills
$\textsc{Zm}(x)\geq n^{1-3\varepsilon}$.

  3. (iii)

During these $\Omega(n\log(n))$ iterations, only a sub-constant fraction of
iterations produces an offspring of higher fitness and smaller Zm-value. In
all iterations where this does not occur, we have a good probability of
sampling a point of distortion at least $d_{0}$ in the 2-neighborhood of $x$.

We start with part (i). To this end, note that by a Chernoff bound, we likely
start with an individual $x$ such that $\textsc{Zm}(x)=\Theta(n)$.
Furthermore, by Lemma 3.5 the maximum number of bit flips that occur within
the first $\mathcal{T}$ iterations is at most
$\mathcal{O}\mkern-1.0mu(\log(\mathcal{T})+\log^{2}(n))=\mathcal{O}\mkern-1.0mu(n^{\varepsilon/8})$
w.h.p. Hence, we do not jump over the interval $I$ as otherwise, this would
imply that we flip $\Theta(n^{1-\varepsilon})$ bits in a single iteration.

For part (ii), we show that once a point in $I$ is visited, the algorithm
spends $\mathcal{T}_{1}\coloneqq\Theta(n\log(n))$ iterations (with a suitably
small hidden constant) during which the current individual $x$ is such that
$\textsc{Zm}(x)\geq n^{1-3\varepsilon}$. To this end, we apply (Jorritsma et
al., 2023, Theorem 3.6) stating that our algorithm on any fitness function
takes time $\Omega(n\log(a/b))$ to reach a point with Hamming-distance $b$
from a fixed point $x^{*}$ when starting at a point $x$ with Hamming distance
$a$ from $x^{*}$. In our case, this means that we spend $\Omega(n\log(n))$
many iterations after visiting the first point in $I$ before the first point
with less than $n^{1-3\varepsilon}$ zeros is visited.

For part (iii), we show that we reach a point $x$ with distortion at least
$d_{0}$ and $\textsc{Zm}(x)\in[n^{1-3\varepsilon},n^{1-\varepsilon}/2]$ during
these $\Omega(n\log(n))$ iterations w.h.p. To this end, we start by
considering the first $\log(n)$ iterations after first visiting a point $x$
with $x\in I$, and we show that we escape potential strongly negative
distortions within this time. To see this, first note that during this time,
the maximum number of bits flipped is
$\tilde{\mathcal{O}}\mkern-2.0mu\left(1\right)$, so the number of zeros
remains $\leq n^{1-\varepsilon}/3$. Now, while the current individual $x$ has
distortion $d<-1$ the number of points in
$\textsc{HL}^{1}\mkern-3.0mu\left(x\right)$ that are not distorted or
distorted with positive distortion is $\Omega(n)$ w.h.p. To see this, note
that the probability that a point is either non-distorted or has distortion
$\geq 0$ is $\Omega(1)$, so if $\mathcal{G}$ happens, we get from a Chernoff
bound that the number of such points in
$\textsc{HL}^{1}\mkern-3.0mu\left(x\right)$ is $\Omega(n)$ w.h.p. As
$\mathcal{G}$ happens w.h.p. as well, the statement follows. Hence, we will
accept a point of distortion $d\geq 0$ if we sample one such point while all
other generated offspring decrease the number of ones. By Lemma 4.3 and since
$\lambda=\mathcal{O}\mkern-2.0mu\left(\log(n)\right)$ this occurs with
probability at least

(1) $\displaystyle\left(1-cn^{-\varepsilon/2}\right)^{\lambda}=\Omega(1).$

Accordingly, all this happens at least once during $\log(n)$ iterations w.h.p.

With this, we can now assume that we start at a point $x$ with distortion
$d\geq-1$ (this includes the case where $x$ is not distorted) and
$\textsc{Zm}(x)\leq n^{1-\varepsilon}/3$. We now consider the remaining
$\mathcal{T}_{1}-\log(n)=\Omega(n\log(n))$ iterations, and show that we reach
a point of distortion $\geq d_{0}$ w.h.p. during this time.

To this end, we let $x_{1},\ldots,x_{m}$ be the search points visited in this
time interval before the first point with distortion $d_{0}$ is reached.
Again, by Lemma 3.5, we note that we only flip at most
$\tilde{\mathcal{O}}\mkern-2.0mu\left(1\right)$ bits in a single mutation
during this time. This implies that we can assume that $\textsc{Zm}(x_{i})\leq
n^{1-\varepsilon}/2$ for all $x_{1},\ldots,x_{m}$ because we start at a point
$x$ with $\textsc{Zm}(x)\leq n^{1-\varepsilon}/3$ as well as distortion
$d\geq-1$ and every time we increase the number of zeros, this must be
compensated by an increase in distortion that is at least as large, so – since
the maximum number of bits flipped is
$\tilde{\mathcal{O}}\mkern-2.0mu\left(1\right)$ – before falling back to a
point with $\geq n^{1-\varepsilon}/2$ zeros, we reach a point of distortion at
least $d_{0}$.

With that in mind, we show that in every iteration, we have a probability of
$\omega(1/(n\log(n)))$ of sampling and accepting a point of distortion $\geq
d_{0}$ while visiting $x_{1},\ldots,x_{m}$. To this end, we apply Lemma 4.4
and a union bound over all the
$m=\mathcal{O}\mkern-2.0mu\left(n\log(n)\right)$ visited search points
$x_{1},\ldots,x_{m}$ to conclude that – while the current individual is any of
$x_{1},\ldots,x_{m}$ – the probability of sampling a point with distortion
$d_{0}+2$ in $\textsc{HL}^{2}\mkern-3.0mu\left(x\right)$ is

$\displaystyle\Omega(p\sigma^{-(d_{0}+2)})=\omega(1/(n\log(n)))$

by 2. Note that the prerequisites of Lemma 4.4 are met because that
$p=\omega(1/(n\log(n)))$, $\ell=2$ and because $d_{0}$ is constant. So in each
iteration, we have a chance of $\omega(1/(n\log(n)))$ that the first sample
has distortion $\geq d_{0}+2$ and is in
$\textsc{HL}^{2}\mkern-3.0mu\left(x\right)$. Furthermore – as noted before in
Equation 1 – the probability that all the other $\lambda-1$ offspring we
create have OneMax-value smaller than $x$ is at least $\Omega(1)$. Thus, in
each iteration, there is a probability of $\omega(1/(n\log(n)))$ of finding
and accepting a point of distortion $\geq d_{0}$, which implies that this
happens at least once during $\Omega(n\log(n))$ iterations w.h.p. ∎

We proceed by showing that if we visit a point $x$ with distortion $d$ and
$\textsc{Zm}(x)\leq n^{1-\varepsilon}$, then – among the points of higher
fitness than $x$ – the number of points of distortion at least $d+1$ is (in
expectation) much larger than the number of points that have distortion
$<d+1$. To this end, we estimate the number of points with fitness at least
$f(x)$ and distortion larger and smaller than $d+1$, respectively, in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$. To this end, we denote by
$D^{\ell}_{\pm}$ the set of points in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ with fitness at least $f(x)$.
Let further $D^{\ell}_{-}\subseteq D^{\ell}_{\pm}$ be the set of search points
in $D^{\ell}_{\pm}$ of distortion smaller than $d+1$, and let $D^{\ell}_{+}$
be the set of search points with distortion at least $d+1$.

###### Lemma 4.6.

Let $x$ be a point visited during the first $\mathcal{T}$ iterations with
$k\leq n^{1-\varepsilon}$ zeros and distortion $d>0$. Let further
$\hat{\ell}\coloneqq\min\\{r,\hat{d}-d\\}$. Then conditional on $\mathcal{G}$,
for all $\ell$ with $1\leq\ell\leq\hat{\ell}$, we have333Technically, the
statement refers to the conditional expectations
$\mathbb{E}\left[|D^{\ell}_{-}|\mid\mathcal{G}\right],\mathbb{E}\left[|D^{\ell}_{+}|\mid\mathcal{G}\right]$,
but we omit this notation for the sake of better readability

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|\right]/\mathbb{E}\left[|D^{\ell}_{+}|\right]\leq\begin{cases}\mathcal{O}\mkern-2.0mu\left(k\sigma^{4}/n\right)^{\ell/2}&\text{if
}\ell<d\\\
\mathcal{O}\mkern-2.0mu\left(k\sigma^{4}/n\right)^{\ell/2}/p&\text{otherwise.}\end{cases}$

###### Proof.

We start by calculating the expectation of $D^{\ell}_{-}$. To this end, note
that in order to not decrease fitness but decrease distortion, the number of
ones in any $y\in D^{\ell}_{-}$ must be at least as large as $|x|_{1}$. By
Lemma 4.3, the fraction of individuals in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ having this property is
$\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}$. Moreover, the number of
ones of any $y\in\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ increases by at
most $\ell$ as compared to $x$, so in order for $y$ to have higher fitness,
its distortion needs to be at least $\min\\{0,d-\ell\\}$. Hence, if $D$
denotes a random variable with distribution $\mathcal{D}$, we have that

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|\right]\leq\begin{cases}\binom{n}{\ell}\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}p\text{Pr}\left[D\geq
d-\ell\right]&\text{if }\ell<d\\\
\binom{n}{\ell}\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}&\text{otherwise.}\end{cases}$

To bound the expectation of $|D^{\ell}_{+}|$, we use the fact that we
condition on $\mathcal{G}$, so when $x$ is first visited, the algorithm has
only seen a sub-constant fraction of
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ before. We can now uncover all
the not-yet-uncovered points and not that with probability at least
$p\text{Pr}\left[D\geq d+\ell\right]$, a such point has distortion at least
$d+\ell$ and at the same time fitness at least $f(x)$ because the number of
ones is at least $\textsc{Om}(x)-\ell$. This shows that

$\displaystyle\mathbb{E}\left[|D^{\ell}_{+}|\right]\geq(1-o(1))\binom{n}{\ell}p\text{Pr}\left[D\geq
d+\ell\right].$

Now, recall that $\text{Pr}\left[D\geq a\right]/\text{Pr}\left[D\geq
a+b\right]\leq\sigma^{b}$ if $a+b\leq\hat{d}$ by 1. Furthermore, said
assumption yields a general lower bound of $\text{Pr}\left[D\geq
a\right]=\Omega(\sigma^{-a})$ for all $a\in[0,\hat{d}]$. Hence, dividing our
estimates for $\mathbb{E}\left[|D^{\ell}_{-}|\right]$ and
$\mathbb{E}\left[|D^{\ell}_{+}|\right]$ yields

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|\right]/\mathbb{E}\left[|D^{\ell}_{+}|\right]$
$\displaystyle\leq\begin{cases}\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}\sigma^{2\ell}&\text{if
}\ell<d\\\
\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}\sigma^{d+\ell}/p&\text{otherwise.}\end{cases}$
$\displaystyle\leq\begin{cases}\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}\sigma^{2\ell}&\text{if
}\ell<d\\\
\mathcal{O}\mkern-2.0mu\left(k/n\right)^{\ell/2}\sigma^{2\ell}/p&\text{otherwise.}\end{cases}$

∎

We the above lemma shows that the number of acceptable search points in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ for a point $x$ with
$\textsc{Zm}(x)\leq n^{1-\varepsilon}$ is larger than the number of acceptable
points with smaller distortion by a factor of $n^{\Omega(1)}$. We show that a
similar statement also applies with high probability if we instead consider
the expectation of the ratio $|D^{\ell}_{-}|/|D^{\ell}_{\pm}|$, which is equal
to the probability of sampling a point of distortion at most $d+1$ when
uniformly sampling among the points of fitness $\geq f(x)$ in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ if we factor in the randomness
both from the sampling and the distribution of the distorted points.

###### Lemma 4.7.

Let $x$ be any visited search point during the first $\mathcal{T}$ iterations
with $k=o(n)$ zero-bits and distortion $d>0$. Then, for any
$1\leq\ell\leq\hat{\ell}\coloneqq\min\\{r,\hat{d}-d\\}$ and conditional on
$\mathcal{G}$, we have 444Again, this technically applies to
$\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\mid\mathcal{G}\right]$, which
we avoid for the sake of simplicity.

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\right]=\begin{cases}\mathcal{O}\mkern-2.0mu\left(k\sigma^{4}/n\right)^{\ell/4}&\text{if
}\ell<d\\\
\mathcal{O}\mkern-2.0mu\left(k\sigma^{4}/n\right)^{\ell/4}/p&\text{otherwise.}\end{cases}$

###### Proof.

We use Lemma 4.6 and distinguish two cases.

Case 1: $\mathbb{E}\left[|D^{\ell}_{+}|\right]\leq(n/(k\sigma^{4}))^{\ell/4}$.
Assume for now that $\ell<d$. By Lemma 4.6, we have

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|\right]\leq\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/2}\left(\frac{k\sigma^{4}}{n}\right)^{-\ell/4}=\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4},$

so Markov’s inequality tells us that

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\right]\leq\text{Pr}\left[|D^{\ell}_{-}|>0\right]=\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}.$

The case $\ell\geq d$ works analogously.

Case 2:
$\mathbb{E}\left[|D^{\ell}_{+}|\right]>(n/(k\sigma^{4}))^{\ell/4}$.Again, we
assume first that $\ell<d$. Here, we can use a Chernoff bound to conclude that

$\displaystyle\text{Pr}\left[|D^{\ell}_{+}|\leq\mathbb{E}\left[|D^{\ell}_{\pm}|\right]/2\right]\leq\exp\left(-\Omega\left(\frac{n}{k\sigma^{4}}\right)^{\ell/4}\right).$

At the same time, we conclude using Markov’s inequality that

$\displaystyle\text{Pr}\left[|D^{\ell}_{-}|\geq\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}\mathbb{E}\left[|D^{\ell}_{+}|\right]\right]$
$\displaystyle\leq\left(\frac{n}{k\sigma^{4}}\right)^{\ell/4}\frac{\mathbb{E}\left[|D^{\ell}_{-}|\right]}{\mathbb{E}\left[|D^{\ell}_{+}|\right]}$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}.$

So in total,

$\displaystyle\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\right]$
$\displaystyle\leq
2\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}+\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}$
$\displaystyle\hskip
28.45274pt+\exp\left(-\Omega\left(\frac{n}{k\sigma^{4}}\right)^{\ell/4}\right)$
$\displaystyle=\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}.$

Again, the case $\ell\geq d$ works analogously. ∎

We finally use this statement to show that the next visited point has
distortion at least $d+1$ with probability $1-n^{-\Omega(1)}$ and is further
within distance $\tilde{\mathcal{O}}\mkern-2.0mu\left(d\right)$ of $x$. The
latter ensures that the number of zeros does not drastically change so that we
can repeatedly apply this statement afterwards.

###### Lemma 4.8.

Let $\varepsilon>0$, and let $x$ be a search point visited during the first
$\mathcal{T}$ iterations with $k\leq n^{1-\varepsilon}$ zero-bits and
distortion $d$ such that
$\max\\{2,12/\varepsilon\\}<d\leq\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$. Let
$y$ be the first point accepted after $x$. Let $\mathcal{E}$ be the event that
the following two statements hold:

  1. (i)

$y$ has distortion at least $d+1$

  2. (ii)

$\textsc{HD}(x,y)\leq d\log^{2}(n)$.

Then, $\mathcal{E}$ occurs with probability at least $1-n^{-\varepsilon/8}$.

###### Proof.

Think of our process as follows. When we first visit $x$, we uncover all the
not-yet-uncovered points in $\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ for
$1\leq\ell\leq\lfloor d\rfloor$. If the next accepted point $y$ is in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$, then the probability that said
point has distortion $<d+1$ is exactly $|D^{\ell}_{-}|/|D^{\ell}_{\pm}|$.
Accounting for the fact that $|D^{\ell}_{-}|/|D^{\ell}_{\pm}|$ is again a
random variable, said probability (conditional on $\mathcal{G}$) is simply
$\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\right]$, so we can use the
previous lemma. Otherwise – i.e. if $\textsc{HD}(x,y)>\lfloor d\rfloor$ – a
different argument is required because 1 is only met up to a maximal
distortion of $\hat{d}$ and the previous lemma relies on the fact that there
are sufficiently many points of distortion $d+\ell$ in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$, which breaks down if $\ell>d$
as $d$ may be as large as $\hat{d}/2$.

We remedy this by showing that the number of samples until we find a point in
$\textsc{HL}^{\lfloor d\rfloor}\mkern-3.0mu\left(x\right)$ of fitness $>f(n)$
is at most

$\displaystyle\mathcal{T}_{1}\coloneqq\log(n)(c_{1}\sigma^{2}d)^{d}/p$

with high probability where $c_{1}>0$ is a constant to be fixed later. This
implies that we do not have enough time to find a point $z$ which has
$\textsc{HD}(x,z)>\lfloor d\rfloor$ and $\textsc{Om}(z)\geq\textsc{Om}(x)$, so
if the next accepted point is not in $\textsc{HL}^{\leq\lfloor
d\rfloor}\mkern-3.0mu\left(x\right)$, then it has distortion $\geq d+1$. The
same event further implies that we do not flip too many bits before accepting
a new point, so it will also yield part (ii) of the statement.

We let $\mathcal{E}_{1}$ be event that we sample a point of distortion $>2d$
in $\textsc{HL}^{\lfloor d\rfloor}\mkern-3.0mu\left(x\right)$ within
$\mathcal{T}_{1}$ samples (where the constant $c_{1}$ will be fixed later),
and we show that $\mathcal{E}_{1}$ occurs with probability $1-1/n$. To this
end, we apply Lemma 4.4 to with $\ell=\lfloor d\rfloor$ and disortion $2d$.
Note that with this choice – due to the assumption that $p$ – we have,

$\displaystyle\frac{\log(\ell)}{\log(n)}+\frac{\log(1/p)}{\ell\log(n)}\leq\frac{\varepsilon}{16}+\frac{1+o(1)}{2}\leq
1-\varepsilon,$

for sufficiently small $\varepsilon$, so we can indeed apply Lemma 4.4 to
conclude that – with probability $1-n^{-\omega(1)}$ – the neighborhood of $x$
is such that if we sample uniformly from
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$, we find a point of distortion
$>2d$ with probability at least $c_{2}p\sigma^{-2d}$, where $c_{2}$ is a
positive constant. Let $\mathcal{B}_{1}$ denote the “bad” event that this does
not occur555That is, $\mathcal{B}_{1}$ is the event that the
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ is such that the fraction of
points with distortion $\geq 2d$ is smaller than $c_{2}p\sigma^{-2d})$ and
note that $\text{Pr}\left[\mathcal{B}_{1}\right]\leq n^{-\omega(1)}$.

Note further that the probability of flipping exactly $\ell=\lfloor d\rfloor$
bits is at least

$\displaystyle\binom{n}{\ell}\hskip
2.84544pt\frac{1}{n^{\ell}}\left(1-\frac{1}{n}\right)^{n}\geq\frac{n^{\ell}\mathcal{O}\mkern-2.0mu\left(\ell\right)^{-\ell}}{2en^{\ell}}=\mathcal{O}\mkern-2.0mu\left(d\right)^{-d}$

by Lemma 3.2. Hence – conditional on $(\neg\mathcal{B}_{1})$ – the total
probability of sampling a point of distortion $>2d$ in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ is at least

$\displaystyle p_{1}\coloneqq p(c_{3}\sigma^{2}d)^{-d}$

for some constant $c_{3}>0$. The probability that this does not occur within
$2\log(n)/p_{1}\leq\mathcal{T}_{1}$ (for a suitable choice of $c_{1}$) samples
is at most

$\displaystyle\left(1-p_{1}\right)^{2\log(n)/p_{1}}\leq e^{-2\log(n)}=1/n^{2}$

Accordingly,

$\displaystyle\text{Pr}\left[\neg\mathcal{E}_{1}\right]\leq
1/n^{2}+\text{Pr}\left[\mathcal{B}_{1}\right]\leq 1/n.$

Now, we show the implications of the above, and we start by showing that
$\mathcal{T}_{1}$ samples are not enough to find a point with more ones than
$x$ at Hamming-distance $\geq\lceil d\rceil$. To this end, denote by
$\mathcal{E}_{2}$ the event that during $\mathcal{T}_{1}$ samples, we find a
point $z$ with $\textsc{HD}(x,z)\geq d$ and
$\textsc{Om}(z)\geq\textsc{Om}(x)$. Since $\textsc{Zm}(x)\leq
n^{1-\varepsilon}$ and due to Lemma 4.3 this happens in a single sample only
with probability $(c_{2}n^{-\varepsilon})^{d/2}$ (for some constant $c_{2}$),
so by Markov’s inequality,

$\displaystyle\text{Pr}\left[\neg\mathcal{E}_{2}\right]$
$\displaystyle\leq\log(n)p^{-1}(c_{1}\sigma^{2}d)^{d}(c_{2}n^{-\varepsilon})^{d/2}$
$\displaystyle\leq\log(n)p^{-1}n^{d(-\varepsilon/2+\varepsilon/16+o(1))}$
$\displaystyle\leq\log(n)p^{-1}n^{d(-\varepsilon/2+\varepsilon/16+o(1))}$
$\displaystyle\leq\log(n)p^{-1}n^{-d\varepsilon/4}.$

Due to our assumption that $d\geq 12/\varepsilon$ and
$p=\omega(1/(n\log(n)))$, we get

$\displaystyle\text{Pr}\left[\neg\mathcal{E}_{2}\right]\leq\log^{2}(n)nn^{-3}\leq
1/n.$

Finally, we show that the maximum number of bits flipped during
$\mathcal{T}_{1}$ samples is bounded. To this end, denote by $\mathcal{E}_{3}$
the event that more than $d\log^{2}(n)$ bits are flipped during
$\mathcal{T}_{1}$ samples. By Lemma 3.5, we get that with probability
$1-n^{-\omega(1)}$, the maximum number of bits flipped during this time is at
most

$\displaystyle
d\log_{2}(c_{1}\sigma^{2}d)+\log_{2}(\log(n))+\log_{2}(1/p)+\log^{2}(n)$
$\displaystyle\hskip
28.45274pt\leq\mathcal{O}\mkern-1.0mu(d\log(n)+\log\log(n)+\log(n))+\log^{2}(n)$
$\displaystyle\hskip 28.45274pt\leq d\log^{2}(n)$

because $d\geq 2$ and because we may assume $n$ to be large enough. In total,
this yields

$\displaystyle\text{Pr}\left[\neg(\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3})\right]$
$\displaystyle\leq n^{-1}+n^{-1}+n^{-\omega(1)}$ $\displaystyle\leq 2n^{-1}.$

With this, we bound the probability that the next accepted point has
distortion at least $d+1$ as follows. If
$\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$ occurs, then the next
point we accept can only have distortion smaller than $d+1$ if it is in
$\textsc{HL}^{\leq\lfloor d\rfloor}\mkern-3.0mu\left(x\right)$. In this
regime, Lemma 4.7 bounds the probability of sampling a point of distortion
$<d+1$ when sampling uniformly among the points of fitness $\geq f(x)$ in
$\textsc{HL}^{\ell}\mkern-3.0mu\left(x\right)$ (i.e. sampling in the set
$D^{\ell}_{\pm}$) when factoring in the randomness from both the sampling and
the distribution of distorted points in $D^{\ell}_{\pm}$ (conditional on
$\mathcal{G}$). To bound the final probability that $y$ has distortion $<d+1$
if $\textsc{HD}(x,y)\leq\lfloor d\rfloor$, we produce one sample $y_{\ell}$ in
$D^{\ell}_{\pm}$ for all $1\leq\ell\leq\lfloor d\rfloor$ and denote by
$\mathcal{B}$ the “bad” event that at least one of them has distortion $<d+1$.
We have

$\displaystyle\text{Pr}\left[\mathcal{B}\mid\mathcal{G}\right]$
$\displaystyle=\text{Pr}\left[\exists\ell:y_{\ell}\in
D^{\ell}_{-}\mid\mathcal{G}\right]$ $\displaystyle\leq\sum_{\ell=1}^{\lfloor
d\rfloor}\mathbb{E}\left[|D^{\ell}_{-}|/|D^{\ell}_{\pm}|\mid\hskip
1.42271pt\mathcal{G}\right]$
$\displaystyle\leq\sum_{\ell=1}^{\infty}\mathcal{O}\mkern-2.0mu\left(\frac{k\sigma^{4}}{n}\right)^{\ell/4}\leq
n^{-\varepsilon/4+o(1)}$

because $k\leq n^{1-\varepsilon}$ and because the sum is geometric. In total,
we have

$\displaystyle\text{Pr}\left[\neg\mathcal{E}\right]$
$\displaystyle\leq\text{Pr}\left[\mathcal{B}\mid\mathcal{G}\right]+\text{Pr}\left[\neg\mathcal{G}\right]+\text{Pr}\left[\neg(\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3})\right]$
$\displaystyle\leq n^{-\varepsilon/4+o(1)}+n^{-\omega(1)}+2n^{-1}$
$\displaystyle\leq n^{-\varepsilon/8}$

as desired. ∎

Plugging everything together, we can prove Section 2.2.

###### Proof of Section 2.2.

By Lemma 4.5, we either reach a point $x$ of distortion at least
$d_{0}\coloneqq\max\\{2,12/\varepsilon\\}$ and $\textsc{Zm}(x)\in
I\coloneqq[n^{1-3\varepsilon},n^{1-\varepsilon}/2]$, or $\mathcal{T}$
iterations pass without reaching a point $x$ with $\textsc{Zm}(x)\leq
n^{1-\varepsilon}/4$ w.h.p. In the latter case, our statement follows, so for
the rest of this proof, we assume that our process starts at a point $x_{0}$
with distortion at least $d_{0}$ and
$\textsc{Zm}(x_{0})\in[n^{1-3\varepsilon},n^{1-\varepsilon}/2]$.

Now, Lemma 4.8 tells us that – conditional on $\mathcal{G}$ – if we visit a
point $x$ during the first $\mathcal{T}$ iterations that has distortion $d\geq
d_{0}$ and $\textsc{Zm}(x)\leq n^{1-\varepsilon}$, then the next visited point
$y$ has distortion at least $d+1$ and $\textsc{HD}(x,y)\leq d\log^{2}(n))$
with probability at least $1-n^{-\varepsilon/8}$. We call jumps in which this
happens _good_ and jumps for which this does not hold _bad_.

We now show that our process reaches a point of distortion
$d_{1}\coloneqq\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$ and to this end, we
consider the next $m=d_{1}$ points visited after $x_{0}$, which we denote by
$x_{1},\ldots,x_{m}$ where $x_{i}$ has distortion $d_{i}$. We show that there
is a point with distortion $\geq d_{1}$ among these visited points w.h.p. To
this end, denote by $\mathcal{E}_{i}$ the event that the jump from $x_{i-1}$
to $x_{i}$ is good or that one of the points $x_{0},\ldots,x_{i-1}$ already
has distortion $\geq d_{1}$. Lemma 4.8 tells us that (conditional on
$\mathcal{G}$) the probability of $\mathcal{E}_{i}$ is least
$1-n^{-\varepsilon/8}$ but only if $\textsc{Zm}(x_{i-1})\leq
n^{1-\varepsilon}$. However, if
$\mathcal{E}_{1}\cap\ldots\cap\mathcal{E}_{i-1}$ hold, then we know that we
either already reached a point of distortion $\geq d_{1}$ or

$\displaystyle\textsc{Zm}(x_{i-1})$ $\displaystyle\leq
n^{1-\varepsilon}/2+id\log^{2}(n)$ $\displaystyle\leq
n^{1-\varepsilon}/2+mn^{\varepsilon/16}\log^{2}(n)\leq n^{1-\varepsilon}$

by the second statement in Lemma 4.8 and because $m,d\leq n^{\varepsilon/16}$.
By the same reasoning, we get that

$\displaystyle\textsc{Zm}(x_{i-1})$ $\displaystyle\geq
n^{1-3\varepsilon}-mn^{\varepsilon/16}\log^{2}(n)\geq n^{1-4\varepsilon},$

so if $\bigcap_{j=1}^{i-1}\mathcal{E}_{j}$ occurs, we either already found a
point $x$ of distortion $\geq d_{1}$ and
$\textsc{Zm}(x)\in[n^{1-4\varepsilon},n^{1-\varepsilon}]$ or we know that the
prerequisites of Lemma 4.8 are met. Hence, we conclude that

$\displaystyle\text{Pr}\left[\mathcal{E}_{i}\mid\left(\bigcap_{j=1}^{i-1}\mathcal{E}_{j}\right)\right]\geq
1-n^{-\varepsilon/8}$

and accordingly666It might be tempting to just use a union bound here.
However, in our situation, we can only bound the probability of
$\mathcal{E}_{i}$ if we know that we start at a point with ZeroMax-value at
most $n^{1-\varepsilon}$, so a classical union bound is not applicable,

$\displaystyle\text{Pr}\left[\bigcap_{i=1}^{m}\mathcal{E}_{i}\right]$
$\displaystyle=\prod_{i=1}^{m}\text{Pr}\left[\mathcal{E}_{i}\mid\left(\bigcap_{j=1}^{i-1}\mathcal{E}_{j}\right)\right]$
$\displaystyle\geq\left(1-n^{-\varepsilon/8}\right)^{n^{\varepsilon/16}}$
$\displaystyle\geq 1-n^{-\varepsilon/8}n^{\varepsilon/16}\geq
1-n^{-\varepsilon/16}$

where in the penultimate step we used Bernoulli’s inequality. Accordingly,
$\bigcap_{i=1}^{m}\mathcal{E}_{i}$ occurs with high probability when starting
at $x_{0}$, which – by the definition of $\mathcal{E}_{i}$ – implies that a
point of distortion at least $d_{1}=\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$ is
reached. ∎

###  4.3. Lower Bounds for the Run Time of the $(1+\lambda)$-EA

We continue by using the fact that the $(1+\lambda)$-EA likely finds a point
of very large distortion to derive explicit lower bounds for its runtime that
– in its most general form – depend explicitly on the CDF of our distribution
$\mathcal{D}$. We then sketch the implications of this bound for some common
distributions below.

See 2.2

###### Proof.

By Section 2.2, the following event occurs with high probability for some
sufficiently small constant $\varepsilon>0$: Either
$\mathcal{T}=\exp(n^{\varepsilon/8})$ iterations pass while
$\textsc{Zm}(x)\geq n^{1-\varepsilon}/4$ or we find a point $x$ of distortion
at least $d=\min\\{\hat{d}/2,n^{\varepsilon/16}\\}$ before finding the first
point with fewer than $n^{1-4\varepsilon}$ zeros.

In the first case, our statement follows. For the second case – if we find a
point of distortion $d$ – it is easy to see that the number of samples
required until the first point with distortion at least $d$ is found dominates
a geometric random variable with success probability $p\text{Pr}\left[D\geq
d\right]$. Thus the probability of finding not finding a such point after
$1/(g(n)p\text{Pr}\left[D\geq d\right])$ samples is at least

$\displaystyle\left(1-p\text{Pr}\left[D\geq
d\right]\right)^{\frac{1}{g(n)p\text{Pr}\left[D\geq d\right]}}\geq
1-1/g(n)=1-o(1)$

as desired. ∎

We show the implications of the above theorem for some common distributions.

#### Exponential Distribution

If $\mathcal{D}$ is an exponential distribution, i.e., if

$\displaystyle\text{Pr}\left[D\geq d\right]=\exp(-\varrho d)$

for some $\varrho>0$, we obtain a stretched exponential lower bound.

See 2.2

###### Proof.

Section 2.2 immediately implies that w.h.p.,

$\displaystyle T\geq\min\left\\{\exp(n^{\varepsilon/8}),\exp((1-o(1))\varrho
n^{\varepsilon/16})\right\\}=\exp(n^{\Omega(1)}).$

∎

#### Gaussian Distribution

We further consider the case where $\mathcal{D}$ is a Gaussian distribution
with density

$\displaystyle\rho(x)=\frac{1}{s\sqrt{2\pi}}\exp\left(-\frac{1}{2}\left(\frac{x}{s}\right)^{2}\right)$

for $x\in[0,\infty)$. It is not immediately obvious that this distribution
fulfills 1 up to a certain point, but we show in the following that 1 is in
fact met for $d=o(\log(n))$. To this end, we bound

$\displaystyle\frac{\text{Pr}\left[D\geq z\right]}{\text{Pr}\left[D\geq
z+1\right]}$
$\displaystyle=\frac{\int_{z}^{\infty}\rho(x)\text{d}x}{\int_{z+1}^{\infty}\rho(x)\text{d}x}$
$\displaystyle=\frac{\int_{z}^{z+1}\rho(x)\text{d}x+\int_{z+1}^{\infty}\rho(x)\text{d}x}{\int_{z+1}^{\infty}\rho(x)\text{d}x}$
$\displaystyle=1+\frac{\int_{z}^{z+1}\rho(x)\text{d}x}{\int_{z+1}^{\infty}\rho(x)\text{d}x}$
$\displaystyle\leq
1+\frac{\int_{z}^{z+1}\rho(x)\text{d}x}{\int_{z+1}^{z+2}\rho(x)\text{d}x}$
$\displaystyle\leq 1+\frac{\rho(z)}{\rho(z+2)}$

because

$\displaystyle(a-b)f(b)\leq\int_{a}^{b}f(x)\text{d}x\leq(a-b)f(a)$

for any monotonically decreasing function $f$. Plugging in the definition of
$\rho(x)$ yields.

$\displaystyle\frac{\text{Pr}\left[D\geq z\right]}{\text{Pr}\left[D\geq
z+1\right]}$ $\displaystyle\leq
1+\frac{\exp\left(-\frac{1}{2}\left(\frac{z}{s}\right)^{2}\right)}{\exp\left(-\frac{1}{2}\left(\frac{z+2}{s}\right)^{2}\right)}$
$\displaystyle=1+\exp\left(-\frac{1}{2s^{2}}\left(z^{2}-(z+2)^{2}\right)\right)$
$\displaystyle=1+\exp\left(\frac{4z+4}{2s^{2}}\right),$

which is $n^{o(1)}$ if $z=o(\log(n))$. Thus, 1 is met for
$\hat{d}=\frac{\log(n)}{\log\log(n)}$ and we obtain the following corollary.

See 2.2

###### Proof.

As shown above, the absolute value of a Gaussian distribution fulfills 1 for
$\hat{d}=\frac{\log(n)}{\log\log(n)}$. Thus, Section 2.2 yields a lower bound
of

$\displaystyle
T\geq\min\left\\{\exp(n^{\varepsilon/8}),\left(g(n)p\text{Pr}\left[D\geq\hat{d}/2\right]\right)^{-1}\right\\}$

w.h.p. By the definition of the Gaussian distribution, we have

$\displaystyle\text{Pr}\left[D\geq\hat{d}/2\right]$
$\displaystyle=\frac{1}{s\sqrt{2\pi}}\int_{\hat{d}/2}^{\infty}\exp\left(-\frac{1}{2}\left(\frac{x}{s}\right)^{2}\right)\text{d}x$
$\displaystyle\leq\frac{1}{s\sqrt{2\pi}}\int_{\hat{d}/2}^{\infty}\frac{x}{s^{2}}\exp\left(-\frac{1}{2}\left(\frac{x}{s}\right)^{2}\right)\text{d}x$
$\displaystyle=\frac{1}{s\sqrt{2\pi}}\left[-\exp\left(-\frac{1}{2}\left(\frac{x}{s}\right)^{2}\right)\right]_{\hat{d}/2}^{\infty}$
$\displaystyle=\frac{1}{s\sqrt{2\pi}}\exp\left(-\frac{1}{2}\left(\frac{\hat{d}}{2s}\right)^{2}\right)$
$\displaystyle=\exp\left(-\Omega\left(\frac{\log(n)}{\log\log(n)}\right)^{2}\right)=n^{-\omega(1)},$

where the second step holds for sufficiently large $n$ since
$\hat{d}/2=\omega(1)$. ∎

#### Pareto Distribution

If $\mathcal{D}$ is a Pareto distribution, i.e., if

$\displaystyle\text{Pr}\left[D\geq
x\right]=\left(\frac{x}{x_{0}}\right)^{1-\tau}$

for $x\in[x_{0},\infty)$ and $\tau\geq 2$, we show that the run time is
polynomial with exponent dependent on $\tau$. We start by verifying that 1 is
met. To this end, note that

$\displaystyle\frac{\text{Pr}\left[D\geq z\right]}{\text{Pr}\left[D\geq
z+1\right]}$ $\displaystyle=\left(\frac{z+1}{z}\right)^{\tau-1}$
$\displaystyle\leq\left(1+\frac{1}{x_{0}}\right)^{\tau-1}=\mathcal{O}\mkern-2.0mu\left(1\right).$

This immediately implies that See 2.2

###### Proof.

If $g(n)=\omega(1)$, then $x_{0}^{1-\tau}g(n)=\omega(1)$ as well. Hence,
Section 2.2 implies a lower bound of

$\displaystyle T$
$\displaystyle\geq\min\left\\{\exp(n^{\varepsilon/8}),\left(x_{0}^{1-\tau}g(n)p\text{Pr}\left[D\geq
n^{\varepsilon/16}\right]\right)^{-1}\right\\}$
$\displaystyle\geq\frac{n^{(\tau-1)\varepsilon/16}}{g(n)p}$

for every $g(n)=\omega(1)$, w.h.p. ∎

##  5\. Analysis of the $(1,\lambda)$-EA

In this section, we show that the $(1,\lambda)$-EA finds the optimum in
$\Theta(n\log(n))$ steps w.h.p. Our analysis is essentially the same as in
(Jorritsma et al., 2023, Section 4) with a minor technical modification. We
give an overview of the analysis and the novel parts without repeating all the
proofs. We use this section to prove the following theorem. See 2.2

Like in (Jorritsma et al., 2023, Section 4), the analysis is based on a drift
argument on an auxiliary dynamic version of our fitness function, which we
call $\textsc{DyDisOm}_{\mathcal{D}}$ and in which we reveal distorted and
clean points gradually, and where distorted points can become non-distorted
(but not vice versa). We adopt the terminology and notation from (Jorritsma et
al., 2023) and call non-distorted points “clean”. Formally, we let $x_{t}$ be
the parent individual in the $t$-th iteration, and for $s=\lambda t+j$ for
$j\in[\lambda]$, we let $y_{s}$ be the $j$-th offspring created in the $t$-th
iteration. Furthermore, we let $C_{s}$ be the set of clean points after
creating $y_{s}$, and iteratively define $C_{0}=\\{x_{0}\\}$ and

$\displaystyle C_{s}\coloneqq\begin{cases}C_{s-1}\cup\\{y_{s}\\}&\text{w.p.
}p,\text{ if }y_{s}\neq x_{t}\\\ C_{s-1}&\text{otherwise.}\end{cases}$

Then,

$\displaystyle\textsc{DyDisOm}_{\mathcal{D}}(x)=\begin{cases}\textsc{Om}(x)&\text{if
}x\in C_{s}\\\ \textsc{Om}(x)+D&\text{otherwise},\end{cases}$

where $D\sim\mathcal{D}$ is a sample from the distribution $\mathcal{D}$. To
define our potential function as in (Jorritsma et al., 2023), we abbreviate
$\textsc{Zm}(x)=k$ and let $Y_{1},\ldots,Y_{\lambda}\sim\text{Bin}(k,1/n)$. We
further define $Y^{*}\coloneqq\max\\{Y_{1},\ldots,Y_{\lambda}\\}$. Our
potential function is

$\displaystyle P(x)\coloneqq\textsc{Zm}(x)+\mathds{1}(x\notin
C_{s})\frac{\delta}{\lambda p}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right].$

The intuition behind this potential function is as follows. For a normal run
of the $(1,\lambda)$-EA on OneMax, it is not hard to see that the drift of the
potential $\textsc{Zm}(x)$ is
$\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right])$ (because our progress
is essentially governed by the maximum number of zero to one flips in a single
offspring). By adding a penalty of $\frac{\delta}{\lambda
p}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$ to distorted points, we
decrease said positive drift by a value in the same order of magnitude, since
a distorted point is sampled with probability at most $\lambda p$, so the
overall drift on clean points remains
$\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right])$ if we choose a suitable
constant $\delta$. If the algorithm starts at a distorted point, then we also
have a positive drift of the same order because we likely generate a set of
offspring that does not include a clone of the current individual and no
distorted point, while also incurring only a small increase in
$\textsc{Zm}(x)$. Hence, our potential decreases by approximately
$\frac{q}{\lambda
p}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\geq\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$
due to our assumption that $\frac{q}{\lambda p}=\omega(1)$. All this was
formally calculated in (Jorritsma et al., 2023), and most cases go through
without modifications, as we show below.

The only difference to the analysis in (Jorritsma et al., 2023) is that the
negative drift incurred by starting at a distorted point increases slightly
because we can now increase the potential function even if we clone our
current individual by finding a point of larger distortion and larger ZeroMax-
value, which was impossible in (Jorritsma et al., 2023) where all points had
the same distortion. However, this increase is still small enough to keep the
overall (asymptotic) drift unchanged. We show this formally by computing
explicit bounds on the drift

$\displaystyle\Delta(x)\coloneqq\mathbb{E}\left[P(x_{t})-P(x_{t+1})\mid
x_{t}=x\right]$

in the following lemma.

###### Lemma 5.1.

Consider a run of the $(1,\lambda)$-EA on $\textsc{DyDisOm}_{\mathcal{D}}$
under 1 and for a sufficiently small constant $\delta>0$. Then while
$\textsc{Zm}(x)\leq k^{*}$,

$\displaystyle\Delta(x)=\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]).$

For the proof we further need the following auxiliary lemma from (Jorritsma et
al., 2023).

###### Lemma 5.2.

Under 3 and for $k\geq k^{*}$, we have

  1. (1)

$\mathbb{E}\left[Y^{*}(k+\log(n))\right]=(1+o(1))\mathbb{E}\left[Y^{*}(k)\right]$.

  2. (2)

$\lambda p\log(n)=o(\mathbb{E}\left[Y^{*}(k)\right]).$

  3. (3)

$q\log(n)=o(\mathbb{E}\left[Y^{*}(k)\right]).$

  4. (4)

$1/n=o(\mathbb{E}\left[Y^{*}(k)\right]).$

  5. (5)

for all $k\leq n/\lambda$, we have
$\mathbb{E}\left[Y^{*}(k)\right]=\Omega(P(x)\frac{\lambda}{n})$.

###### Proof of Lemma 5.1.

As in (Jorritsma et al., 2023), we split the drift into a positive and
negative component

$\displaystyle\Delta^{+}(x)$
$\displaystyle\coloneqq\mathbb{E}\left[\max\\{P(x_{t})-P(x_{t+1}),0\\}\mid
x_{t}=x\right]$ $\displaystyle\Delta^{-}(x)$
$\displaystyle\coloneqq\mathbb{E}\left[\max\\{P(x_{t+1})-P(x_{t}),0\\}\mid
x_{t}=x\right]$

such that $\Delta(x)=\Delta^{+}(x)-\Delta^{-}(x)$. We further abbreviate
$r^{+}:=\max\\{r,0\\}$. Now, we distinguish the case that $x$ is clean and
distorted, respectively, and derive bounds on the positive and negative drift
in each case. The only case that is significantly different from the case
distinction in (Jorritsma et al., 2023) is the case of backward progress for
distorted points. For all other cases, we therefore only give a rough proof
sketch and refer the interested reader to (Jorritsma et al., 2023) for
details.

#### Forward progress, clean points.

Here, it suffices to consider the event that all $\lambda$ offspring we create
are clean. (I.e., we lower bound the forward progress of all other cases by
zero.) Clearly, this happens with probability at least $1-\lambda p=1-o(1)$.
Then, we can simply compute the expected maximal number of bits that flip from
0 to 1 in all offspring, which is
$\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$. If we additionally consider
the event that no bit flips from 1 to 0 in the offspring with the maximum
number of 0-to-1 flips, our expected potential decrease is
$\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right])$. As this occurs with
probability at least $1/e$, we get
$\Delta^{+}(x)\geq\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right])$ in
total.

#### Forward progress, distorted points.

In this case, we consider the event $\mathcal{E}_{1}$ that all offspring are
clean, the event $\mathcal{E}_{2}$ that there is no clone of $x$ among the
offspring, and the event $\mathcal{E}_{3}$ that there is an offspring that
flips at most one 1-bit to a 0. These events together imply that we accept a
clean point that increases the number of zeros by at most $1$ and thus the
potential decreases by at least $(\delta/(\lambda
p)\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right])-2$. Note that these events and
bounds hold regardless of whether we use constant distortions or not. In
total, as shown in (Jorritsma et al., 2023, Proof of Lemma 4.2), this argument
yields a drift of

(2) $\displaystyle\Delta^{+}(x)\geq\frac{\delta q}{4\lambda
p}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$

#### Backward progress, clean points.

Here, to upper bound the negative drift, we consider the event
$\mathcal{E}_{5}$ that all offspring differ in at most $\log(n)$ bits from
$x$. It is easy to show that

$\displaystyle\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\neg\mathcal{E}_{5})\right]=o(1/n)$

since $\neg\mathcal{E}_{5}$ is very unlikely. However, if $\mathcal{E}_{5}$
occurs, then we know that the ZeroMax-value of the next accepted point
increases by at most $\log(n)$. If there is additionally a distorted offspring
– we denote this event by $\mathcal{E}_{4}$ – then the potential increases by
at most $\log(n)+\delta/(\lambda
p)\mathbb{E}\left[Y^{*}(\textsc{Zm}(x)+\log(n))\right]$ and hence

$\displaystyle\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\mathcal{E}_{5})\mathds{1}(\mathcal{E}_{4})\right]$
$\displaystyle\hskip 85.35826pt\leq\log(n)\lambda
p+2\delta\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right].$

On the other hand, if $\neg\mathcal{E}_{4}$ occurs, i.e., if there is no
distorted offspring, then the potential can only increase if we do not create
a clone of $x$. Denote this event (that is the event of not cloning $x$) by
$\mathcal{E}_{2}$ and recall that
$\text{Pr}\left[\mathcal{E}_{2}\right]=(1+o(1))q$. As
$\neg\mathcal{E}_{4}\cap\mathcal{E}_{5}$ implies that there is no distorted
offspring and no offspring with more than $\log(n)$ bit flips, the potential
increases by at most $\log(n)$ if
$\neg\mathcal{E}_{4}\cap\mathcal{E}_{5}\cap\mathcal{E}_{2}$ occurs. Hence,

$\displaystyle\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\mathcal{E}_{5})\mathds{1}(\neg\mathcal{E}_{4})\mathds{1}(\mathcal{E}_{2})\right]\leq(1+o(1))q\log(n).$

In total, this yields

$\displaystyle\Delta^{-}(x)\leq
2\delta\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$ $\displaystyle\hskip
56.9055pt+\mathcal{O}\mkern-2.0mu\left(\lambda
p\log(n)\right)+\mathcal{O}\mkern-2.0mu\left(q\log(n)\right)+o(1/n).$

Due to our parameter setup and $\textsc{Zm}(x)\geq k^{*}$, this term is
$(1+o(1))2\delta\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]$ by Lemma 5.2 (we
refer to (Jorritsma et al., 2023)) for the computation details), which is
smaller than our lower bound on $\Delta^{+}(x)$ for clean points if we choose
$\delta$ small enough. Hence, for clean points, we conclude that

$\displaystyle\Delta(x)\geq\Delta^{+}(x)-\Delta^{-}(x)=\Omega(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x)\right])).$

#### Backward progress, distorted points.

In this case our analysis will slightly divert from that of (Jorritsma et al.,
2023). To this end, recall that $\mathcal{E}_{2}$ is the event that there is
no clone of $x$ among the offspring, and that $\mathcal{E}_{5}$ is the event
that there is no offspring with more than $\log(n)$ bit flips. If
$\mathcal{E}_{2}\cap\mathcal{E}_{5}$ occurs, the reasoning is just like in
(Jorritsma et al., 2023): In the worst case, the next accepted point is
distorted and its ZeroMax-value changes by at most $\log(n)$. Thus,

$\displaystyle\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\mathcal{E}_{2})\mathds{1}(\mathcal{E}_{5})\right]$
$\displaystyle\hskip
14.22636pt\leq\text{Pr}\left[\mathcal{E}_{2}\right](\log(n)$
$\displaystyle\hskip 22.76228pt+\delta/(\lambda
p)\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x)+\log(n))\right]-\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right))$
$\displaystyle\hskip 14.22636pt\leq 2q\left(\log(n)+\frac{\delta}{\lambda
p}o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)\right)$

because $\text{Pr}\left[\mathcal{E}_{2}\right]\leq 2q$ and because of Lemma
5.2 item (1). The new part in our analysis is the case where there is a clone
among the offspring. In our case, we can increase the potential in this case
as well, namely, when we find a point of larger distortion that has a greater
ZeroMax-value. However, this is only possible if we sample a distorted
offspring, which happens only with probability at most $\lambda p$. So
similarly as above, we have

$\displaystyle\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\neg\mathcal{E}_{2})\mathds{1}(\mathcal{E}_{5})\right]$
$\displaystyle\hskip 28.45274pt\leq\lambda
p\left(\log(n)+\frac{\delta}{\lambda
p}o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)\right).$

In total,

$\displaystyle\Delta^{-}(x)$
$\displaystyle=\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\mathcal{E}_{2})\mathds{1}(\mathcal{E}_{5})\right]$
$\displaystyle\hskip
28.45274pt+\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\neg\mathcal{E}_{2})\mathds{1}(\mathcal{E}_{5})\right]$
$\displaystyle\hskip
28.45274pt+\mathbb{E}\left[(P(x_{t+1})-P(x_{t}))^{+}\mathds{1}(\neg\mathcal{E}_{5})\right]$
$\displaystyle\leq(2q+\lambda p)\left(\log(n)+\frac{\delta}{\lambda
p}o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)\right)+o(1/n).$

By items (2) - (4) in Lemma 5.2, this implies that

$\displaystyle\Delta^{-}(x)$ $\displaystyle\leq\left(\frac{(2q+\lambda
p)\delta}{\lambda
p}+1\right)o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)$
$\displaystyle=\left(\frac{2q\delta}{\lambda
p}+\delta+1\right)o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right).$

Using the bound in Equation 2, we conclude that for distorted points, we have
a total drift of

$\displaystyle\Delta(x)$ $\displaystyle\geq\frac{\delta q}{\lambda
p}\left(\frac{1}{4}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]-o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)\right)$
$\displaystyle\hskip
28.45274pt-\left(\delta+1\right)o\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)$
$\displaystyle=\Omega\left(\frac{q}{\lambda
p}\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)=\Omega\left(\mathbb{E}\left[Y^{*}(\textsc{Zm}(x))\right]\right)$

because $q=\omega(p\lambda)$. ∎

Overall, we use this to prove Section 2.2.

###### Proof of Section 2.2.

The proof is identical to the proof of (Jorritsma et al., 2023, Theorem 1.1)
using Lemma 5.1 instead of (Jorritsma et al., 2023, Lemma 4.3). ∎

##  6\. Experiments

We confirm our theoretical results empirically in multiple settings777The code
is available at https://github.com/OliverSieberling/DistortedOneMax. First of
all, Figure 3 shows how the total fitness, OneMax-fitness, and the distortion
evolve over a single run on $\textsc{DisOM}_{\mathcal{D}}$ with an exponential
distribution. We can clearly see that the $(1+\lambda)$-EA quickly reaches a
local optimum and then tends to increase distortion further while decreasing
OneMax-fitness. Furthermore, progress becomes extremely slow, note the
logarithmic $x$-axis. After one billion generations the $(1+\lambda)$-EA is
still moderately far away from the optimum while not having accepted a single
offspring in the prior $975$ million generations. On the other hand, the
$(1,\lambda)$-EA escapes the local optima it encounters quickly and reaches
fitness $n-k^{*}$ in less than $400$ generations.

${10^{1}}$${10^{3}}$${10^{5}}$${10^{7}}$${10^{9}}$t0153045607590105120135150165$n-k^{*}$$(1+\lambda)$-EA
Run: Total Fitness$(1+\lambda)$-EA Run: OneMax Fitness$(1+\lambda)$-EA Run:
Distortion$(1,\lambda)$-EA Run: Total Fitness$(1,\lambda)$-EA Run: OneMax
Fitness$(1,\lambda)$-EA Run: Distortion

Figure 3. Total fitness, OneMax-fitness, and distortion of one run of the
$(1+\lambda)$-EA and the $(1,\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$
with $\mathcal{D}$ being an exponential distribution with rate parameter
$0.4$. We use $n=150$, $\lambda=8$, $p=0.0245$ and $k^{*}=2.12$ with a cutoff
of $10^{9}$ generations. The x-axis is scaled logarithmically.

This behavior is predominant even for smaller problem sizes. In Figure 4 we
plot the median number of generations required by the $(1+\lambda)$-EA and the
$(1,\lambda)$-EA to optimize $\textsc{DisOM}_{\mathcal{D}}$. For distortions
sampled from an exponential distribution we observe that already for $n=90$ a
majority of the elitist runs exceed the cutoff of one million generations,
while the $(1,\lambda)$-EA optimizes efficiently in every single run. This
illustrates the exponential slowdown proven in Section 2.2. We remark that for
small problem sizes the sampled distortions have an significant impact on the
total fitness. Hence, the $(1+\lambda)$-EA can find a point of sufficient
fitness without being close to the optimum in terms of OneMax fitness simply
by increasing distortion. For distortions sampled from a uniform distribution,
which also satisfies Assumption 1 but is much less “heavy-tailed”, we see a
smaller slowdown. This indicates that the governing factor of the run time of
the $(1+\lambda)$-EA on $\textsc{DisOM}_{\mathcal{D}}$ is indeed controlled by
the “heavy-tailedness” of $\mathcal{D}$ as predicted by Section 2.2.

6080100120140160180200n${10^{2}}$${10^{3}}$${10^{4}}$${10^{5}}$${10^{6}}$Median
Number of GenerationsCutoff$(1+\lambda)$-EA with $\mathcal{D}\sim$
Exp($0.4$)$(1,\lambda)$-EA with $\mathcal{D}\sim$ Exp($0.4$)$(1+\lambda)$-EA
with $\mathcal{D}\sim$ U($0,4$)$(1,\lambda)$-EA with $\mathcal{D}\sim$
U($0,4$)

Figure 4. Number of generations required by the $(1+\lambda)$-EA and the
$(1,\lambda)$-EA to optimize $\textsc{DisOM}_{\mathcal{D}}$ with $\mathcal{D}$
being an exponential distribution with rate parameter $0.4$ and a uniform
distribution from $0$ to $4$. We take the median over $49$ runs. We set
$\lambda=\lfloor 1.5\log{n}\rceil$, $p=0.3n^{-0.5}$ and $k^{*}=n^{0.15}$ with
a cutoff of $10^{6}$ generations. The y-axis is scaled logarithmically.

In Figure 5, we investigate this question further and conclude that the tern
$(p\text{Pr}\left[D\geq d\right])^{-1}$ predicted by Section 2.2 as a lower
bound for the run time of the $(1+\lambda)$-EA can be empirically observed.
For this purpose, we compare the performance of the $(1+\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ with distortions sampled from different
truncated exponential distributions for different $p$, and we plot the run
time, rescaled by $(p\text{Pr}\left[D\geq d\right])^{-1}$ (where $d$ is the
cutoff) in Figure 5. We observe that the curves are grouped closely together
as we would expect, although the run times seem to grow slightly faster than
by a factor of $1/p$. The same figure also shows that the optimization time
increases significantly when truncating the distribution $\mathcal{D}$ at
higher values. This slowdown seems to be roughly $1/Pr[D\geq d]$ as we would
expect.

246810$1/p$010002000300040005000$T\cdot p\cdot P[D\geq d]$Truncated
$0-8$Truncated $0-4\sqrt{2}$Truncated $0-4$Truncated $0-2\sqrt{2}$

Figure 5. Normalized number of generations required by the $(1+\lambda)$-EA to
optimize $\textsc{DisOM}_{\mathcal{D}}$ for different distortion probabilities
$p$. The distortions are sampled from an exponential distribution with rate
parameter $0.4$ truncated at different cutoffs $d$. We set $n=300$,
$\lambda=9$, $k^{*}=2.35$ and average over $49$ runs. Note that the $y$-axis
shows the (averaged) run time re-scaled by a factor of $(p\text{Pr}\left[D\geq
d\right])^{-1}$. This gives evidence that the run time is indeed proportional
to $(p\text{Pr}\left[D\geq d\right])^{-1}$ as predicted by Section 2.2.

##  7\. Conclusion

We have shown that plus strategies are prone to get stuck in randomly placed
local optima of random height, modeled by the benchmark function
$\textsc{DisOM}_{\mathcal{D}}$. We gave a sufficient condition (1) on the
distribution $\mathcal{D}$ ensuring that – sufficiently close to the optimum –
once we find a distorted point, things only get worse and the $(1+\lambda)$-EA
accepts points of higher and higher distortion, which leads to super-
polynomial run times for multiple natural choices of $\mathcal{D}$ including
the exponential and the Gaussian distribution. This holds even if the local
optima are planted relatively sparsely, for example $p=n^{-1+\varepsilon}$.
Our illustrating example is the exponential distribution, for which we obtain
a stretched exponential lower bound of $\exp(n^{\Omega(1)})$. Our results
hence indicate that plus strategies on natural “rugged” fitness landscapes are
unsuitable for practical applications.

On the other hand, for some parameter choices for which plus strategies need
super-polynomial time, we showed that comma strategies optimize
$\textsc{DisOM}_{\mathcal{D}}$ asymptotically in the same time as OneMax,
i.e., in only $\Theta(n\log(n))$ fitness evaluations. Our analysis here relies
on the assumption that local optima are planted sufficiently sparsely, i.e.,
that $p$ is sufficiently small. While this is exactly the same assumption as
in previous work (Jorritsma et al., 2023), it is likely not needed to ensure
efficiency of the $(1,\lambda)$-EA, as indicated by our experimental
evaluation (Figure 3) which takes place in a setting where the assumption
$p=o(k^{*}/n)$ is not met. We leave it as an open question for future work to
extend the theoretical study of the $(1,\lambda)$-EA on
$\textsc{DisOM}_{\mathcal{D}}$ for a less restrictive parameter regime.

While we studied a distorted version of OneMax, any other benchmark function
can be distorted in the same way. It would be interesting to study whether
comma strategies remain efficient on distorted versions of other benchmarks,
for example LeadingOnes, linear functions, or monotone functions. Finally,
there are many other non-elitist selection strategies than comma selection,
like tournament selection or, and there are situations in which those other
strategies are preferable (Dang et al., 2021). It would be important to know
which other non-elitist selection strategies can also deal well with
distortions.

## References

  * (1)
  * Antipov et al. (2019) Denis Antipov, Benjamin Doerr, and Quentin Yang. 2019.  The efficiency threshold for the offspring population size of the $(\mu,\lambda)$ EA. In _Proceedings of the Genetic and Evolutionary Computation Conference_ _(GECCO ’19)_. ACM, 1461–1469.  https://doi.org/10.1145/3321707.3321838
  * Auger et al. (2022) Anne Auger, Carlos M. Fonseca, Tobias Friedrich, Johannes Lengler, and Armand Gissler. 2022.  Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081).  _Dagstuhl Reports_ 12, 2 (2022), 87–102.
  * Dang et al. (2021) Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre. 2021.  Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021)_. 1133–1141.
  * Doerr (2022) Benjamin Doerr. 2022.  Does comma selection help to cope with local optima?  _Algorithmica_ 84 (2022), 1659–1693.
  * Dubhashi and Panconesi (2009) Devdatt P. Dubhashi and Alessandro Panconesi. 2009.  _Concentration of Measure for the Analysis of Randomized Algorithms_.  Cambridge University Press.  Google-Books-ID: UUohAwAAQBAJ.
  * Friedrich et al. (2016a) Tobias Friedrich, Timo Kötzing, Martin S Krejca, and Andrew M Sutton. 2016a.  The compact genetic algorithm is efficient under extreme gaussian noise.  _IEEE Transactions on Evolutionary Computation_ 21, 3 (2016), 477–490.
  * Friedrich et al. (2016b) Tobias Friedrich, Timo Kötzing, Martin S Krejca, and Andrew M Sutton. 2016b.  Graceful scaling on uniform versus steep-tailed noise. In _International Conference on Parallel Problem Solving from Nature_. Springer, 761–770.
  * Friedrich et al. (2022) Tobias Friedrich, Timo Kötzing, Frank Neumann, and Aishwarya Radhakrishnan. 2022.  Theoretical Study of Optimizing Rugged Landscapes with the cGA. In _Parallel Problem Solving from Nature (PPSN 2022)_. Springer, 586–599.
  * Hevia Fajardo and Sudholt (2021) Mario Alejandro Hevia Fajardo and Dirk Sudholt. 2021.  Self-Adjusting Offspring Population Sizes Outperform Fixed Parameters on the Cliff Function. In _Foundations of Genetic Algorithms (FOGA 2021)_ , Vol. 5. 1–5.
  * Jorritsma et al. (2023) Joost Jorritsma, Johannes Lengler, and Dirk Sudholt. 2023.  Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima. In _Proceedings of the Genetic and Evolutionary Computation Conference_ _(GECCO ’23)_. ACM, 1602–1610.  https://doi.org/10.1145/3583131.3590488
  * Lehre (2011) Per Kristian Lehre. 2011.  Fitness-levels for non-elitist populations. In _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011)_. ACM, Dublin Ireland, 2075–2082.  https://doi.org/10.1145/2001576.2001855
  * Lengler and Steger (2018) J. Lengler and A. Steger. 2018.  Drift Analysis and Evolutionary Algorithms Revisited.  _Combinatorics, Probability and Computing_ 27, 4 (July 2018), 643–666.  https://doi.org/10.1017/S0963548318000275
  * Prugel-Bennett et al. (2015) Adam Prugel-Bennett, Jonathan Rowe, and Jonathan Shapiro. 2015.  Run-time analysis of population-based evolutionary algorithm in noisy environments. In _Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII_. 69–75.
  * Rowe and Sudholt (2014) Jonathan E. Rowe and Dirk Sudholt. 2014.  The choice of the offspring population size in the $(1,\lambda)$ evolutionary algorithm.  _Theoretical Computer Science_ 545 (Aug. 2014), 20–38.  https://doi.org/10.1016/j.tcs.2013.09.036

##  Appendix A Appendix