Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax

Carsten Witt

Source-linked AI summary

Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax

Carsten Witt

arXiv:1704.00026v4Mar 31, 2017cs.NE

TL;DR

The paper asks how quickly UMDA optimizes OneMax across broad μ and λ regimes, where earlier bounds left an asymptotic gap. It analyzes frequency-level stochastic behavior and derives regime-dependent upper bounds. The expected runtime is O(μn) with borders for μ ≥ c′ log n and improves to O(μ√n) above μ ≥ c√n log n, while borders are typically unnecessary in the latter regime.

Problem
Earlier upper and lower bounds for UMDA on OneMax were separated by a Θ(log log n) factor.
Source: §1 · p. 2
Method
The paper analyzes the UMDA frequency process at bit level, including selection-induced bias and drift behavior.
Source: §2.2 · p. 10
Results
O(μ√n) holds above μ ≥ c√n log n, while O(μn) holds for μ ≥ c′ log n when frequencies use borders.
Source: §1 · p. 3
Takeaways & Limitations
The bounds close the previous asymptotic gap and show a phase transition in UMDA’s behavior near μ = Θ(√n log n).
Source: §1 · p. 3
The results assume λ = O(μ), and matching lower bounds remain unavailable in the intermediate regime μ = ω(log n) and μ = o(√n log n).
Source: Conclusions · p. 31

Abstract

from arXiv · show

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of its parameters $\mu$ and $\lambda$. If $\mu\ge c\log n$ for some constant $c>0$ and $\lambda=(1+\Theta(1))\mu$, a general bound $O(\mu n)$ on the expected runtime is obtained. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval $[1/n,1-1/n]$. If $\mu\ge c' \sqrt{n}\log n$ for a constant $c'>0$ and $\lambda=(1+\Theta(1))\mu$, the behavior of the algorithm changes and the bound on the expected runtime becomes $O(\mu\sqrt{n})$, which typically even holds if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound $\Omega(\mu\sqrt{n}+n\log n)$ by Krejca and Witt (FOGA 2017) and turn out as tight for the two very different values $\mu=c\log n$ and $\mu=c'\sqrt{n}\log n$. They also improve the previously best known upper bound $O(n\log n\log\log n)$ by Dang and Lehre (GECCO 2015).

1 Introduction

The paper analyzes UMDA on OneMax, closing a gap between prior upper and lower bounds by deriving general runtime bounds across parameter regimes. Its analysis tracks frequency-level stochastic behavior and identifies a phase transition around μ = Θ(√n log n).

Setting

UMDA samples λ solutions, selects the best μ, and updates each frequency to the selected individuals’ relative frequency of 1s.The paper situates this analysis within estimation-of-distribution algorithms that model search distributions rather than storing explicit populations.Source: §1 · pp. 1–2

Main results

The results close the Θ(log log n) gap between previous upper and lower runtime bounds for UMDA on OneMax.The prior upper bound was O(n log n log log n), while recent work established a lower bound of the form Ω(μ√n + n log n).Source: §1 · pp. 2–3
O(μ√n) is obtained above the phase transition, while O(μn) holds with borders for μ ≥ c′ log n.The faster bound applies when μ ≥ c√n log n; both results assume λ = (1 + Θ(1))μ.Source: §1 · p. 3

Phase transition

Around μ = Θ(√n log n), UMDA undergoes a phase transition from chaotic frequency movement to steadier progress.Below the threshold, many frequencies hit the lowest possible value; above it, frequencies move more steadily and typically avoid very low values.Source: §1 · p. 3
Removing borders can cause infinite optimization time below the phase transition, whereas bordered frequencies retain polynomial expected runtime for logarithmic μ.Borders confine frequencies to [1/n, 1 − 1/n], preventing them from becoming permanently fixed at 0 or 1.Source: §1 · p. 3

Method

The analysis uses a bit-level stochastic-process approach rather than the level-based theorem used by Dang and Lehre.It develops a negative drift theorem and analyzes the selection-induced bias of frequencies toward higher values.Source: §1 · p. 3

2 Preliminaries

This section introduces UMDA’s frequency-update process for OneMax and develops the probabilistic and drift tools used to analyze it. It focuses on how 1st-class and 2nd-class individuals and candidates influence selection bias, the abundance of 2nd-class individuals, and the resulting drift in frequencies and the expected number of ones.

2 Preliminaries

UMDA samples λ individuals from independent bit frequencies, selects the best µ, and updates each frequency to the selected fraction of ones, using borders [1/n,1−1/n].The initial frequencies are p_i=1/2; without borders, frequencies reaching 0 or 1 cannot change and UMDA* may lack finite expected runtime.Source: §2 · pp. 4–5
The analyses assume λ=(1+β)µ for constant β>0, so expected function evaluations equal λ times the generations until the optimum is sampled.The target is the all-ones string, and the analysis also applies to OneMax_a by symmetry.Source: §2 · pp. 4–5

2.1 Useful Tools from Probability Theory

The probability toolkit bounds central Poisson-binomial point probabilities by Ω(min{1,1/σ}) and combines this with generalized and variable drift theorems for hitting-time analyses.A further binomial lemma lower-bounds E(min{C,X}), supporting the analysis of selected individuals.Source: §2.1 · pp. 6–8

2.2 On the Stochastic Behavior of Frequencies

OneMax makes all frequencies identically distributed but dependent, while selection introduces a bias that can increase overall fitness even as an individual frequency decreases.Without selection, a frequency is a martingale; the analysis therefore isolates the selection-induced bias.Source: §2.2 · pp. 9–10

Ranking, 1st-class individuals, 2nd-class individuals and candidates

1st-class individuals are selected regardless of bit j, whereas 2nd-class individuals compete for selection and are consequently biased toward sampling a 1 at that position.The analysis focuses on candidates from level M−1, while possible 2nd-class individuals may also arise from levels M and M−2; Figure 2 illustrates this ranking and selection structure.Source: Ranking, 1st-class individuals,… · pp. 10–11, Illustration · pp. 11–12

Illustration

The number of 2nd-class individuals from level M−1 is binomially distributed, and the candidate overhang is represented by a shifted binomial distribution.Deferred decisions expose the relevant level counts through conditional binomial trials, enabling analysis of both C** and D*−C**.Source: Illustration · pp. 12–15
Conditioned on E∗, q=Ω(1/σt), E(C∗∗_{t+1}|σt)=Ω(µ/σt), and q′=Ω(1/σt); additionally, E(D∗_{t+1}−C∗∗_{t+1}|σt)=1+Ω((λ−µ−1)/σt).Source: Illustration · pp. 15–16
The overhang of 2nd-class candidates over selected 2nd-class individuals creates a positive selection bias toward higher frequencies at bit j.The analysis lower-bounds the expected number of ones in the µ selected offspring while ignoring additional 2nd-class individuals from levels M−2 and M, which can only increase the bias.Source: Illustration · p. 16
The resulting drift lemma lower-bounds E(X_{t+1}|X_t,σ_t) and, under p_t≤1−c/n, also lower-bounds the expected next marginal frequency.The proof uses independence from X_t, binomial stochastic bounds, and the assumption λ=(1+Θ(1))µ.Source: Illustration · pp. 17–18
The analysis follows in modeling the stochastic process and defining M, but differs because bounds 2nd-class individuals from above for running-time lower bounds.Here, the core argument instead establishes lower bounds needed for the drift analysis.Source: Illustration · p. 18

3 Above the Phase Transition

Above the phase transition, sufficiently large populations let UMDA reach the optimum in O(√n) generations while keeping frequencies away from the lower border with high probability. The analysis applies drift arguments to show an O(λ√n) optimization-time bound for both bordered UMDA and UMDA* under the stated parameter regime.

Main result

O(λ√n) optimization time holds for UMDA when λ=(1+β)µ, µ≥c√n log n, and µ=n^O(1).The result also provides an O(λ√n) bound for UMDA* under the same large-population setting.Source: §3 · p. 19

Drift mechanism

The proof uses positive drift of the summed frequencies, while showing that genetic drift rarely pushes frequencies below 1/4 when µ≥c√n log n.This keeps the process away from the lower border, where unfavorable frequency decreases could otherwise undermine progress.Source: §3 · p. 19

Success and failure phases

With probability Ω(1), either the optimum is sampled or a frequency falls below 1/4 after O(√n) generations.For UMDA, failures can be followed by recovery phases, whose contribution is controlled through drift and restart arguments.Source: §3 · pp. 21–22

Sampling the optimum

After O(√n) generations without failure, the probability of sampling the all-ones string is Ω(1).The argument drives the total distance of the frequencies from the upper border to O(1), which gives a constant probability of sampling the optimum.Source: §3 · pp. 22–23

Limitation

The analysis cannot straightforwardly strengthen the Ω(1) success probability to 1−o(1) after the potential first reaches its target range.Improving this probability would require analyzing the subsequent potential evolution when the optimum is not sampled immediately.Source: §3 · p. 23

4 Below the Phase Transition

Below the threshold Θ(√(n log n)), UMDA behavior is unstable: frequencies often reach the lower border, while UMDA* can have infinite optimization time; borders nevertheless yield an O(λn) bound for logarithmic µ.

4 Below the Phase Transition

Below the threshold, frequencies move chaotically, and many hit the lowest possible value before optimization.Above the threshold, frequencies instead remain focused near their drift toward the upper border.Source: §4 · p. 24
The threshold complements prior results showing a coupon-collector lower bound Ω(n log n) and stuck frequencies for UMDA* when µ is below Θ(√(n log n)).Related EDAs exhibit analogous threshold behavior around √(n log n).Source: §4 · p. 24
UMDA* turns from efficient with at least constant probability to inefficient with overwhelming probability below µ = Θ(√(n log n)).In this regime, many frequencies reach the lower border; without borders, frequencies can become stuck at 0.Source: §4 · p. 24
With borders and µ ≥ c log n, UMDA has expected optimization time O(λn), whereas UMDA* has infinite optimization time with high probability for sufficiently small µ below the threshold.The border interval [1/n, 1 − 1/n] prevents frequencies from becoming permanently fixed at 0 or 1.Source: §4 · pp. 24, 28
The O(λn) result follows from frequencies near the upper border, a potential-function drift argument, and constant probability of sampling the optimum once the potential is small.Frequencies that reach the upper border typically return within a constant number of steps, preserving expected frequency 1 − O(1/n).Source: §4 · pp. 25, 26, 28, 29
The paper extracts µ = c′ log n as a parameter choice giving O(n log n), while suggesting—but not proving—a further polynomial-to-exponential transition below log n.The conjectured lower-µ transition is motivated by the coarse-grained frequency scale.Source: §4 · pp. 29–30

5 Experiments

Experiments reveal a multimodal relationship between UMDA’s average running time and λ, while lower-border hits decline exponentially and the empirical phase transition occurs near λ = 250–300 for n = 2000.

5 Experiments

For n = 2000 and µ = λ/2, average running time is multimodal across λ = 14 to 350, with minima near λ ≈ 20 and λ ≈ 280.The average uses 3000 runs per setting because variance is especially high for small λ.Source: §5 · p. 30
Lower-border hits decrease exponentially with λ, and the chaotic-to-stable phase transition is empirically located between λ = 250 and 300.The border-hit trend is shown on a semi-log plot.Source: §5 · p. 30
For n = 5000, similar experimental results occur, but the location of the maximum does not appear to increase linearly with n.The comparison is reported through Figure 4.Source: §5 · p. 30

Conclusions

The paper derives upper bounds O(µ√n) and O(µn) for UMDA on OneMax in different µ regimes, yielding O(n log n) for two asymptotic choices of µ. These results close the previous gap while leaving broader λ/µ regimes and an intermediate µ range unresolved.

Conclusions

For UMDA on OneMax, the expected running time is bounded by O(µ√n) when µ ≥ c√n log n and by O(µn) when µ ≥ c′ log n, for positive constants c and c′.These bounds imply an expected running time of O(n log n) for two asymptotic values of µ.Source: Conclusions · p. 30
O(n log n) expected runtime follows for two asymptotically different choices of µ, closing the previous gap between upper and lower bounds.The preceding gap included the earlier O(n log n log log n) upper bound and recent lower bounds.Source: Conclusions · pp. 30–31
The proofs provide tools for analyzing stochastic processes at individual UMDA frequencies, intended to support future EDA analyses.Source: Conclusions · p. 31
All results assume λ = O(µ), while formal analysis of other µ-to-λ ratios and sublogarithmic µ remains open.Matching lower bounds are also unavailable when µ is both ω(log n) and o(√n log n).Source: Conclusions · p. 31

A.1 Proof of Theorem 1

The proof applies a drift-based hitting-time theorem to a transformed stochastic process and establishes its moment-generating-function condition by separately bounding positive and negative steps. This yields constant auxiliary bounds and proves the theorem.

A.1 Proof of Theorem 1

The proof applies Theorem 5 to suitable variables for an interval of length ℓ = b − a, using a process transformation to compare hitting times.The transformed process is analyzed instead of the original process because its hitting time is stochastically no larger.Source: §A.1 · p. 32
The required drift condition is established by bounding the moment-generating function of truncated increments and separating positive from negative steps.Positive steps are bounded through the exponential series, while negative steps are overestimated using ∆′ and an exponential-moment bound.Source: §A.1 · pp. 32–33
Choosing λ = min{1/(2r), ǫ/(17r^2), 1/(κǫ)} gives p(ℓ) = O(r/ǫ + r^2/ǫ^2 + κ), establishing Condition (∗).Source: §A.1 · pp. 33–34
The success-probability analysis bounds D(ℓ) = max{1, E(e^−λ(Xt+1−b) | Xt ≥ b)} by O(1), completing the theorem.The bound uses the positive-step estimate and the same negative-step exponential-moment calculation.Source: §A.1 · p. 34