# The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates

arXiv: https://arxiv.org/abs/1808.05566 · HTML: https://mlsanity.com/paper/1808.05566/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2018.

## Built on by (most cited first, 3 of 3)

- [Evolutionary Retrofitting](https://mlsanity.com/paper/2410.11330/) (2024)
- [Log-normal Mutations and their Use in Detecting Surreptitious Fake Images](https://mlsanity.com/paper/2409.15119/) (2024)
- [Tuning without Peeking: Provable Generalization Bounds and Robust LLM Post-Training](https://mlsanity.com/paper/2507.01752/) (2025)

## Abstract (arXiv)

We study unbiased (1+1) evolutionary algorithms on linear functions with an unknown number n of bits with non-zero weight. Static algorithms achieve an optimal runtime of O(n (ln n)2+ε), however, it remained unclear whether more dynamic parameter policies could yield better runtime guarantees. We consider two setups: one where the mutation rate follows a fixed schedule, and one where it may be adapted depending on the history of the run. For the first setup, we give a schedule that achieves a runtime of (1± o(1))β n ln n, where β ≈ 3.552, which is an asymptotic improvement over the runtime of the static setup. Moreover, we show that no schedule admits a better runtime guarantee and that the optimal schedule is essentially unique. For the second setup, we show that the runtime can be further improved to (1± o(1)) e n ln n, which matches the performance of algorithms that know n in advance. Finally, we study the related model of initial segment uncertainty with static position-dependent mutation rates, and derive asymptotically optimal lower bounds. This answers a question by Doerr, Doerr, and K"otzing.