Which Individuals Carry the Drift? Leave-One-Out Influence for Population Runtime Bounds

Evolutionary algorithms keep a population of candidate solutions and improve it by mutating and selecting. Their theory lags badly behind their use. The best recent bound for one of the simplest population methods, the $(\mu+1)$ EA (keep $\mu$ solutions, make one mutated child per step, discard the worst), on the linear benchmark BinVal is $O(\mu^3 n \log(n/\mu^2))$. Experiments suggest the true dependence on $\mu$ is closer to linear. The extra powers of $\mu$ probably come from the proof, not the algorithm. The proof bounds the worst-case spread of the whole population as if every member mattered equally. In practice, progress may be carried by one leading lineage while the rest of the population is dead weight that selection soon removes.

This note proposes to measure and then exploit that asymmetry with leave-one-out (LOO) sensitivity analysis. LOO is the tool meta-analysts use to ask whether a pooled result survives dropping any one study. Here, "drift" means the expected one-step decrease of a distance-to-optimum potential. We would compute, for each population member, how much the drift changes when that member is removed. If a handful of individuals carry nearly all of it, a runtime proof only needs to control those individuals. That would give a concrete, checkable route to bounds with a lower power of $\mu$.

Core Claim

For elitist population EAs on linear functions, the population's drift is concentrated in an effective number of contributing individuals $m_{\mathrm{eff}}$. We expect $m_{\mathrm{eff}}$ to stay small, near constant, across $\mu$ once an initial takeover phase has passed. A drift argument that is conditioned on this concentration, instead of on worst-case population diversity, should give runtime bounds whose $\mu$-dependence is at least one power below the current $\mu^3$ on BinVal.

The object is exact and cheap for the $(\mu+1)$ EA, because the parent is chosen uniformly. The drift decomposes over parents:

$$\Delta(X) = \frac{1}{\mu}\sum_{j=1}^{\mu} g_j(X), \qquad I_j(X) = \Delta(X) - \Delta(X^{-j}),$$

where $X$ is the current population, $g_j(X)$ is the expected potential decrease when individual $j$ is the parent (including the effect of discarding the worst of the $\mu+1$), and $X^{-j}$ is the population with $j$ removed and the $(\mu-1)+1$ step run on it. We summarize concentration by the participation ratio $m_{\mathrm{eff}} = (\sum_j |I_j|)^2 / \sum_j I_j^2$. This equals $\mu$ when influence is spread evenly and $1$ when a single individual carries everything.

Relation to Prior Work

The theory side motivates the proposal and supplies the method. Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal bounds the maximum Hamming distance within bit blocks across the population and derives $O(\mu^3 n\log(n/\mu^2))$ for standard bit mutation and $O(\mu^3 n^{3/2}\log(n/\mu^2))$ for mutations that cannot copy a parent. The authors themselves call the $\mu$-dependence pessimistic. They also observe that the $(\mu+1)$ step already performs a leave-one-out on the multiset, since it drops the worst individual, but they never ask which individuals the drift depends on. We keep their potential functions and occupation-probability machinery. We replace the population-wide diversity bound with an influence-concentration condition.

Level-Based Analysis of Genetic Algorithms and Other Search Processes upper-bounds runtime through aggregate conditions on how the population spreads across fitness levels. It is deliberately macroscopic, so it cannot separate a leader's effect from the crowd's. Drift analysis and average time complexity of evolutionary algorithms supplies the basic drift theorem we would condition.

The sensitivity side supplies the lens but also constrains it. Testing Most Influential Sets shows that a maximum influence needs its own null distribution, because searching for the most influential point biases naive tests. Its extreme-value results, however, are derived only for least-squares regression. We therefore borrow the lesson and not the distributional result: excessive influence is judged against a simulated exchangeable-population null.

The Efron–Stein inequality used in An Exponential Efron-Stein Inequality for Lq Stable Learning Rules bounds a variance by summed leave-one-out differences. We use it only where its independence assumption actually holds. That is over the independent per-step random choices (parent index and mutation bits), to control fluctuation of the potential across a window of steps. It is not applied over population members, which are not independent.

Evolutionary Computation and Explainable AI calls for making evolutionary search dynamics interpretable, but it gives no formal influence quantity. This proposal is one concrete instance of that call, tied to a proof target.

Research Program

The first stage is measurement. We would instrument the $(\mu+1)$ EA with three mutation operators: standard bit mutation, 1-bit mutation, and "plus" mutation. The benchmarks are BinVal, INC (weights $w_i=i$), random linear functions, and OneMax, with $n$ up to 625 and $\mu$ swept from 2 to beyond the $(n/\log n)^{1/5}$ regime where current proofs stop. At each step we compute every $g_j$ exactly where the potential allows it and by Monte Carlo otherwise, then record $I_j$ and $m_{\mathrm{eff}}$. This tells us three things: whether concentration exists, how long the pre-concentration phase lasts as a function of $\mu$, and whether it differs between copy-capable and copy-incapable mutation. The last question matters because the BinVal paper attributes the slowdown of copy-incapable mutation to excess diversity.

The second stage is theory. We would state a conditional drift theorem of the following shape. Suppose that, after a burn-in of $T_0(\mu)$ steps, the top-$k$ individuals carry at least a constant fraction of the drift with high probability. Then the runtime is bounded by $T_0$ plus $\mu/k$ times a $(1+1)$-type drift time on the leaders' block structure. We would then try to prove that the concentration condition holds on BinVal, starting with standard bit mutation, where copying makes concentration plausible. We would use Efron–Stein over per-step randomness to keep the leaders' potential concentrated over windows.

A modest success would be a $\mu^2$ bound. The real target is near-linear, and we state it as a conjecture, not a promise. If concentration fails provably for 1-bit mutation, that failure is itself an explanation of the $n^{3/2}$ gap.

The third stage is transfer. The same instrumentation would be run across IOHprofiler problems F1–F23 to see where concentration breaks: rugged LeadingOnes variants, LABS, and the Ising models. This locates where influence-based proofs could and could not reach arbitrary linear functions, which the file lists as an open generalization.

Baselines

The naive reference point is the $(1+1)$ EA's $n\log n$ scaled by $\mu$. This asks whether the population behaves like $\mu$ serial copies of one climber and is what "linear in $\mu$" means operationally. The strongest existing result is the proven bound of Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal: $O(\mu^3 n\log(n/\mu^2))$ for standard bit mutation and $O(\mu^3 n^{3/2}\log(n/\mu^2))$ for 1-bit and plus mutation. That paper reports empirically only that standard and 1-bit mutation outperform plus mutation at larger $\mu$. No reported result was found on Lacuna for numeric empirical $(\mu+1)$ EA runtimes on BinVal, so we generate those ourselves, with at least 100 runs per configuration logged through IOHprofiler.

For the empirical side, the fair comparison is between predictors, each fitted on the same runs with the same regression model and held-out $(n,\mu)$ configurations. The first predictor is the block-wise maximum Hamming distance the BinVal paper uses. The second is the number of distinct genotypes. The third is the level occupancy profile used by level-based analysis. The fourth is our $m_{\mathrm{eff}}$. The targets are both the next-window potential decrease and the remaining runtime. Beating the baselines means lower held-out prediction error for remaining runtime by a clear margin across operators, not just on BinVal.

The ablation that isolates the key ingredient is $m_{\mathrm{eff}}$ computed from fitness rank alone, that is, assuming the best-ranked individuals carry the drift. If rank does as well as true LOO influence, the LOO computation is unnecessary and the theorem should be phrased in terms of rank.

On the theory side, beating the baseline means a proven bound with a smaller power of $\mu$ on at least one operator.

Why not just…?

Why not just run large sweeps and fit the exponent of $\mu$? We will run them; they are the first baseline. A fitted exponent confirms the gap exists but says nothing about which quantity a proof should control. The influence measurements are meant to name that quantity. If the sweeps show the true exponent is already near 3, the whole premise collapses, and that is a decisive early check.

Why not just use the Hamming-diversity statistic the existing proof already tracks? This is the real threat. Diversity and influence concentration are correlated: a converged population has both low diversity and trivially concentrated influence. The two can come apart when the population is diverse but only one lineage is making progress, which is exactly the situation the BinVal paper describes for copy-incapable mutation. The predictor comparison settles the question. If Hamming diversity predicts remaining runtime as well as $m_{\mathrm{eff}}$ on held-out settings, we abandon the influence framing and instead try to tighten the existing diversity bound directly.

Why not a classical takeover-time argument, bounding how fast copies of the best individual fill the population? Takeover reasoning assumes the leader stays the leader. On BinVal, a lower-ranked individual can overtake it by flipping a heavier bit, so leadership changes hands and a plain takeover argument over-counts. LOO influence handles leadership changes automatically, because it measures who currently carries the drift. The experiments would still report the fraction of steps where the top-ranked individual is not the top-influence one. If that fraction is negligible, the takeover argument is the simpler proof route and we would take it.

Why not apply the extreme-value test from Testing Most Influential Sets directly? Its limiting distributions are derived for least-squares regression with independence between features and residuals. Neither assumption holds for a selected, correlated population. We use its methodological point, that a maximum influence must be judged against a null for maxima, and build that null by simulation.

Decisive Checks

Four results would decide the project. The first is whether empirical runtime on BinVal scales near-linearly in $\mu$ well beyond the $(n/\log n)^{1/5}$ regime; if not, there is no gap to close. The second is whether $m_{\mathrm{eff}}$ stays bounded in $\mu$ after a burn-in that grows at most like $\mu\log\mu$. The third is whether $m_{\mathrm{eff}}$ beats block Hamming diversity and the rank-only ablation at predicting remaining runtime, with the largest advantage for 1-bit and plus mutation. The fourth is whether the conditional drift theorem, once its concentration hypothesis is proven for standard bit mutation, yields a bound below $\mu^3$.

A clean negative result would also be informative. That would be diffuse influence under copy-incapable mutation, matching its slower $n^{3/2}$ behavior. It would show that the pessimism in current bounds is partly real for those operators.