pith. sign in

arxiv: 2604.06976 · v1 · submitted 2026-04-08 · 💻 cs.NE

Anytime Analysis on BinVal: Adaptive Parameters Help

Timo K\"otzing , Jurek Sander This is my paper

Pith reviewed 2026-05-10 17:50 UTC · model grok-4.3

classification 💻 cs.NE
keywords evolutionary algorithmsruntime analysisBinValfixed-target runtimeself-adjusting parametersanytime performancemutation rate adaptationparameter control
0
0 comments X

The pith

A self-adjusting mutation rate in the (1+1) EA yields O(k^{1+ε}) fixed-target runtimes on BinVal for every k=o(n), independent of string length n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper measures how many fitness evaluations different algorithms need to optimize the leading k bits of a length-n bit string under the BinVal fitness function, with bounds that must hold simultaneously for all such k. The standard (1+1) evolutionary algorithm with mutation probability 1/n requires Θ(n log k) evaluations, while the sig-cGA needs Θ(k log n). Replacing the fixed mutation rate with a self-adjusting rule produces an algorithm whose runtime is O(k^{1+ε}) for any ε>0 arbitrarily close to zero. This bound does not grow with n and is close to the Θ(k log k) performance of the best fixed-rate (1+1) EA when the target k is known in advance.

Core claim

By replacing the fixed mutation rate in the standard (1+1) EA with a self-adjusting rate, the fixed-target run time for k ∈ o(n) and a constant ε >0 arbitrarily close to zero is in O(k^{1+ε}) for this algorithm. In particular, this run time is independent of n, holds simultaneously for all k ∈ o(n), and is close to the run time of Θ(k log k) for the (1+1) EA with the best fixed mutation rate if k is known.

What carries the argument

The self-adjusting mutation-rate rule inside the (1+1) EA that changes the mutation probability on the basis of recent success or failure.

Load-bearing premise

The specific self-adjusting mechanism for the mutation rate behaves exactly as modeled and the probabilistic analysis of fixed-target runtimes on BinVal holds without hidden dependencies on n or k.

What would settle it

A single run or a proof for some n and k=o(n) in which the self-adjusting (1+1) EA requires more than k^{1+ε} evaluations or whose runtime grows with n would falsify the claimed bound.

Figures

Figures reproduced from arXiv: 2604.06976 by Jurek Sander, Timo K\"otzing.

Figure 1
Figure 1. Figure 1: Comparison of the standard (1+1) EA, the (1+1) EA [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of the standard (1+1) EA (dashed lines) [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 2
Figure 2. Figure 2: The number of leading bits in relation to [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
read the original abstract

While most theoretical run time analyses of discrete randomized search heuristics provide bounds on the expected number of evaluations to find the global optimum, we consider the anytime performance of evolutionary and estimation-of-distribution algorithms. For this purpose, we analyze the fixed-target run time of various algorithms using BinVal as fitness function and bound the run time to optimize the most significant $k \in o(n)$ bits of a bit string with length $n$. We analyze the run times such that they hold not only for a fixed $k$, but simultaneously for all $k \in o(n)$. For the standard (1+1) EA with fixed mutation rate $1/n$, we show that the fixed-target run time for all $k \in o(n)$ is in $\Theta(n \log k)$. Using an EDA instead, we get an expected number of evaluations of $\Theta(k \log n)$ for the sig-cGA. Replacing in the standard (1+1) EA the fixed mutation rate with a self-adjusting rate, we show that the fixed-target run time for $k \in o(n)$ and a constant $\varepsilon >0$ arbitrarily close to zero is in $\mathcal{O}\left(k^{1+\varepsilon}\right)$ for this algorithm. In particular, this run time is independent of $n$, holds simultaneously for all $k \in o(n)$, and is close to the run time of $\Theta(k \log k)$ for the (1+1) EA with the best fixed mutation rate if $k$ is known.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper analyzes the anytime (fixed-target) performance of evolutionary algorithms and EDAs on the BinVal fitness function, deriving runtime bounds to optimize the k most significant bits for all k = o(n) simultaneously. For the standard (1+1) EA with fixed mutation rate 1/n the bound is Θ(n log k); for the sig-cGA it is Θ(k log n); and for a self-adjusting (1+1) EA the bound is O(k^{1+ε}) for any constant ε>0 arbitrarily close to zero, independent of n and close to the Θ(k log k) optimum achievable when k is known in advance.

Significance. If the derivations hold, the work provides a strong demonstration that self-adaptive mutation rates can deliver near-optimal fixed-target runtimes on BinVal without knowledge of k and without n-dependence, while maintaining simultaneous validity across all k = o(n). The explicit comparison to both fixed-rate EAs and EDAs, together with the emphasis on anytime behavior rather than only global optimization, adds value to the literature on parameter control in evolutionary computation.

major comments (2)
  1. [§4] §4 (analysis of the self-adjusting (1+1) EA): the claimed O(k^{1+ε}) bound independent of n requires an explicit, n-free upper bound on the initial adaptation phase in which the mutation rate moves from its standard initialization Θ(1/n) to the scale Θ(1/k) appropriate for the current leading-bit position. Multiplicative update rules typically require Θ(log(n/k)) successful steps; if the per-step waiting time while the rate remains too large is Ω(1) on average, this phase contributes an Ω(log n) term that, for k = o(log n), exceeds any fixed power k^{1+ε} and re-introduces n-dependence, contradicting the stated independence. The drift or concentration argument must therefore absorb or eliminate this cost for every k = o(n) simultaneously.
  2. [Theorem 3] Theorem 3 (or the main theorem on the self-adjusting EA): the simultaneous-for-all-k requirement is load-bearing for the central claim, yet the proof sketch does not appear to contain a uniform bound showing that the adaptation cost incurred while optimizing the first few bits does not degrade the runtime for later, larger k. A concrete test would be to verify whether the total expected time up to target k remains O(k^{1+ε}) when the process begins at rate 1/n and must cross all intermediate scales.
minor comments (2)
  1. [Abstract] The abstract states the self-adjusting result holds 'for k ∈ o(n) and a constant ε >0 arbitrarily close to zero'; the precise dependence of the hidden constant on ε should be stated explicitly in the theorem statement to clarify how close to the Θ(k log k) optimum the bound actually is.
  2. [§2] Notation for the self-adjusting mechanism (update factor, success-based rule) is introduced without a dedicated preliminary subsection; a short paragraph recalling the exact update rule and initialization would improve readability for readers unfamiliar with the 1/5-rule variants.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The concerns about the adaptation phase in the self-adjusting (1+1) EA analysis are valid and point to a place where the proof sketch in Section 4 can be strengthened. We will revise the manuscript to supply the missing explicit bounds while preserving the stated claims.

read point-by-point responses

  1. Referee: [§4] §4 (analysis of the self-adjusting (1+1) EA): the claimed O(k^{1+ε}) bound independent of n requires an explicit, n-free upper bound on the initial adaptation phase in which the mutation rate moves from its standard initialization Θ(1/n) to the scale Θ(1/k) appropriate for the current leading-bit position. Multiplicative update rules typically require Θ(log(n/k)) successful steps; if the per-step waiting time while the rate remains too large is Ω(1) on average, this phase contributes an Ω(log n) term that, for k = o(log n), exceeds any fixed power k^{1+ε} and re-introduces n-dependence, contradicting the stated independence. The drift or concentration argument must therefore absorb or eliminate this cost for every k = o(n) simultaneously.

    Authors: We agree that an explicit n-independent bound on the initial adaptation phase must be stated. In the revised manuscript we will insert a new lemma that applies multiplicative drift to the mutation-rate process. When the current rate r ≫ 1/k the success probability for improving the leading bit remains Ω(1/k) (by the same binomial-tail estimates already used for the main drift), so the expected time to obtain a successful step that triggers a rate decrease is O(k). Consequently the Θ(log(n/k)) rate-adjustment steps cost only O(k log(n/k)) in total, which is absorbed into O(k^{1+ε}) for any fixed ε>0. The constants are chosen uniformly in k=o(n) by fixing ε first and then taking n large enough; the resulting bound remains independent of n in the leading term. revision: yes

  2. Referee: [Theorem 3] Theorem 3 (or the main theorem on the self-adjusting EA): the simultaneous-for-all-k requirement is load-bearing for the central claim, yet the proof sketch does not appear to contain a uniform bound showing that the adaptation cost incurred while optimizing the first few bits does not degrade the runtime for later, larger k. A concrete test would be to verify whether the total expected time up to target k remains O(k^{1+ε}) when the process begins at rate 1/n and must cross all intermediate scales.

    Authors: We accept that the current sketch does not explicitly verify uniformity across scales. The revised proof of Theorem 3 will decompose the run time into successive phases, one for each bit position m=1…k. The time to reach target m is bounded by O(m^{1+ε}) by induction; the additional adaptation cost at scale m is O(m^ε) by the new lemma mentioned above. Summing over m≤k therefore yields at most O(k^{1+ε}) + O(∑_{m=1}^k m^ε) = O(k^{1+ε}), which is uniform in k. This directly answers the concrete test: the total expected time starting from rate 1/n and crossing all intermediate scales remains O(k^{1+ε}). revision: yes

Circularity Check

0 steps flagged

No significant circularity in runtime derivation

full rationale

The paper presents direct probabilistic analysis deriving fixed-target runtime bounds on BinVal for the fixed-rate (1+1) EA (Θ(n log k)), the sig-cGA EDA (Θ(k log n)), and the self-adjusting (1+1) EA (O(k^{1+ε}) independent of n, simultaneously for all k ∈ o(n)). These are obtained from modeling the algorithms' behavior, drift analysis, and waiting-time arguments rather than by fitting parameters to the target quantity, redefining the result into itself, or relying on load-bearing self-citations whose content reduces to the present claim. The adaptation-phase concern raised by the skeptic is a potential gap in the correctness of the n-independence proof, but does not constitute circularity because the bound is not presupposed or constructed from the final statement. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard probabilistic tools for analyzing randomized search heuristics such as expected-value calculations and concentration bounds. No free parameters are fitted to data and no new entities are introduced.

axioms (1)
  • standard math Standard asymptotic notation (big-O, Theta) and basic probability bounds for Markov chains and randomized algorithms
    Invoked throughout the runtime derivations for all three algorithms.

pith-pipeline@v0.9.0 · 5577 in / 1273 out tokens · 48503 ms · 2026-05-10T17:50:13.321748+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Aishwaryaprajna and Jonathan E. Rowe. 2025. Evolutionary Anytime Algorithms. InEvolutionary Computation in Combinatorial Optimization: 25th European Con- ference, Proceedings (EvoCOP ’25). Springer-Verlag, 18–32. doi:10.1007/978-3-031- 86849-8_2

    work page doi:10.1007/978-3-031- 2025

  2. [2]

    Maxim Buzdalov, Benjamin Doerr, Carola Doerr, and Dmitry Vinokurov. 2022. Fixed-Target Runtime Analysis.Algorithmica84, 6, 1762–1793. doi:10.1007/ S00453-021-00881-0

    work page 2022

  3. [3]

    Stephan Cathabard, Per Kristian Lehre, and Xin Yao. 2011. Non-uniform mu- tation rates for problems with unknown solution lengths. InProceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms (FOGA ’11). Association for Computing Machinery, 173–180. doi:10.1145/1967654.1967670

    work page doi:10.1145/1967654.1967670 2011

  4. [4]

    Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2015. Solving Problems with Unknown Solution Length at (Almost) No Extra Cost. InProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO ’15). Asso- ciation for Computing Machinery, 831–838. doi:10.1145/2739480.2754681

    work page doi:10.1145/2739480.2754681 2015

  5. [5]

    Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2018. Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables.Algorithmica80, 5 (May 2018), 1732–1768. doi:10.1007/s00453-017-0341-1

    work page doi:10.1007/s00453-017-0341-1 2018

  6. [6]

    Benjamin Doerr, Carola Doerr, and Johannes Lengler. 2021. Self-Adjusting Muta- tion Rates with Provably Optimal Success Rules.Algorithmica83, 10, 3108–3147. doi:10.1007/S00453-021-00854-3

    work page doi:10.1007/s00453-021-00854-3 2021

  7. [7]

    Benjamin Doerr and Leslie Ann Goldberg. 2010. Drift analysis with tail bounds. InProceedings of the 11th International Conference on Parallel Problem Solving from Nature: Part I (PPSN’10). Springer-Verlag, 174–183. doi:10.1007/978-3-642- 15844-5_18

    work page doi:10.1007/978-3-642- 2010

  8. [8]

    Benjamin Doerr and Leslie Ann Goldberg. 2013. Adaptive Drift Analysis.Algo- rithmica65, 1, 224–250. doi:10.1007/S00453-011-9585-3

    work page doi:10.1007/s00453-011-9585-3 2013

  9. [9]

    Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012. Multiplicative Drift Analysis.Algorithmica64, 4, 673–697. doi:10.1007/S00453-012-9622-X

    work page doi:10.1007/s00453-012-9622-x 2012

  10. [10]

    Benjamin Doerr and Martin S. Krejca. 2020. Significance-Based Estimation-of- Distribution Algorithms.IEEE Trans. Evol. Comput.24, 6, 1025–1034. doi:10.1109/ TEVC.2019.2956633

    work page arXiv 2020

  11. [11]

    Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+ 1) evolutionary algorithm.Theoretical Compututer Science276, 1–2 (April 2002), 51–81. doi:10.1016/S0304-3975(01)00182-7

    work page doi:10.1016/s0304-3975(01)00182-7 2002

  12. [12]

    Hafsteinn Einarsson, Marcelo Matheus Gauy, Johannes Lengler, Florian Meier, Asier Mujika, Angelika Steger, and Felix Weissenberger. 2019. The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates. Theoretical Computer Science785 (2019), 150–170. doi:10.1016/j.tcs.2019.05.021

    work page doi:10.1016/j.tcs.2019.05.021 2019

  13. [13]

    Jun He and Xin Yao. 2001. Drift analysis and average time complexity of evolu- tionary algorithms.Artificial Intelligence127, 1 (2001), 57–85. doi:10.1016/S0004- 3702(01)00058-3

    work page doi:10.1016/s0004- 2001

  14. [14]

    Jun He and Xin Yao. 2004. A study of drift analysis for estimating computation time of evolutionary algorithms.Natural Computing3, 1 (2004), 21–35. doi:10. 1023/B:NACO.0000023417.31393.c7

    work page arXiv 2004

  15. [15]

    Jens Jägersküpper. 2008. A Blend of Markov-Chain and Drift Analysis. InProceed- ings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN’08). Springer-Verlag, 41–51. doi:10.1007/978-3-540-87700-4_5

    work page doi:10.1007/978-3-540-87700-4_5 2008

  16. [16]

    Thomas Jansen and Christine Zarges. 2012. Fixed budget computations: a different perspective on run time analysis. InProceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO ’12). Association for Computing Machinery, 1325–1332. doi:10.1145/2330163.2330347

    work page doi:10.1145/2330163.2330347 2012

  17. [17]

    Timo Kötzing and Martin S. Krejca. 2019. First-hitting times under drift.Theoret- ical Computer Science796 (2019), 51–69. doi:10.1016/j.tcs.2019.08.021

    work page doi:10.1016/j.tcs.2019.08.021 2019

  18. [18]

    Johannes Lengler and Nicholas Spooner. 2015. Fixed Budget Performance of the (1+1) EA on Linear Functions. InProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA ’15). Association for Computing Machinery, 52–61. doi:10.1145/2725494.2725506

    work page doi:10.1145/2725494.2725506 2015

  19. [19]

    Eduardo Carvalho Pinto and Carola Doerr. 2018. Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms. arXiv:1812.00493 doi:10.48550/ arXiv.1812.00493

    work page arXiv 2018

  20. [20]

    Jonathan Rowe. 2024. A Theoretical Investigation Of Termination Criteria For Evolutionary Algorithms. InEvolutionary Computation in Combinatorial Optimization(1 ed.)(Lecture Notes in Computer Science). Springer, 162–176. doi:10.1007/978-3-031-57712-3_11

    work page doi:10.1007/978-3-031-57712-3_11 2024

  21. [21]

    Dirk Sudholt. 2013. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms.Transactions on Evolutionary Computation17, 3 (June 2013), 418–435. doi:10.1109/TEVC.2012.2202241

    work page doi:10.1109/tevc.2012.2202241 2013

  22. [22]

    Dmitry Vinokurov, Maxim Buzdalov, Arina Buzdalova, Benjamin Doerr, and Carola Doerr. 2019. Fixed-target runtime analysis of the (1 + 1) EA with resam- pling. InProceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ’19). Association for Computing Machinery, 2068–2071. doi:10.1145/3319619.3326906

    work page doi:10.1145/3319619.3326906 2019

  23. [23]

    Carsten Witt. 2013. Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions.Combinatorics, Probability and Computing 22, 2 (2013), 294–318. doi:10.1017/S0963548312000600

    work page doi:10.1017/s0963548312000600 2013

  24. [24]

    Carsten Witt. 2018. Domino convergence: why one should hill-climb on linear functions. InProceedings of the Genetic and Evolutionary Computation Conference (GECCO ’18). Association for Computing Machinery, 1539–1546. doi:10.1145/ 3205455.3205581

    work page arXiv 2018

  25. [25]

    Shlomo Zilberstein. 1996. Using Anytime Algorithms in Intelligent Systems.AI Magazine17, 3 (Mar. 1996), 73. doi:10.1609/aimag.v17i3.1232 Acknowledgements This research was (partially) funded by the HPI Research School on Foundations of AI (FAI). GECCO ’26, July 13–17, 2026, San Jose, Costa Rica xxx A Experimental Anytime Analysis ofBinV al To extend the e...

    work page doi:10.1609/aimag.v17i3.1232 1996