All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm

• URL: http://arxiv.org/abs/2602.23573v1
• Date: Fri, 27 Feb 2026 00:52:59 GMT
• Title: All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm
• Authors: Andrew James Kelley,
• Abstract summary: For every real number $c geq 1$ and for all $varepsilon > 0$, there is a fitness function $f : 0,1n to mathbbR$ for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$, denoted $p_n$, satisfies $p_n approx c/n$ in that $|np_n - c| varepsilon$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For every real number $c \geq 1$ and for all $\varepsilon > 0$, there is a fitness function $f : \{0,1\}^n \to \mathbb{R}$ for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$, denoted $p_n$, satisfies $p_n \approx c/n$ in that $|np_n - c| < \varepsilon$. In other words, the set of all $c \geq 1$ for which the mutation rate $c/n$ is optimal for the $(1+1)$ EA is dense in the interval $[1, \infty)$. To show this, a fitness function is introduced which is called HillPathJump.

Related papers

• All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm [0.0]
  For every mutation rate $p in (0, 1)$, there is a fitness function $f : 0,1n to mathbbR$ with a unique maximum for which the optimal mutation rate for the $(p-varepsilon, p+varepsilon)$ evolutionary algorithm on $f$ is in $(p-varepsilon, p+varepsilon)$.
  arXiv  Detail & Related papers  (2026-02-22T00:30:45Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [52.95596504632859]
  This paper establishes the convergence rate $frac1Ksum_k=1KEleft[||nabla f(xk)||_1right]leq O(fracsqrtdCK1/4)$ for AdamW measured by $ell_1$ norm.<n>We extend our result to NAdamW, an AdamW variant that employs a double-momentum mechanism, and demonstrate that it maintains the same convergence rate.
  arXiv  Detail & Related papers  (2025-05-17T05:02:52Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity [1.8434042562191815]
  We show that population diversity in the $(mu+1)$-$lambda_c$-GA converges to an equilibrium of near-perfect diversity.<n>We also show that our analysis can be extended to other unitation functions such as JUMP$_k, delta$ and HURDLE.
  arXiv  Detail & Related papers  (2024-04-10T14:50:43Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
  We study the $(1,lambda)$-EA with mutation rate $c/n$ for $cle 1$, where the population size is adaptively controlled with the $(1:s+1)$-success rule. We show that this setup with $c=1$ is efficient on onemax for $s1$, but inefficient if $s ge 18$.
  arXiv  Detail & Related papers  (2022-04-01T15:46:12Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• Sharper bounds for online learning of smooth functions of a single variable [0.0]
  We show that $opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$, where the constants in the bound do not depend on $q$. We also show that $opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$, where the constants in the bound do not depend on $q$.
  arXiv  Detail & Related papers  (2021-05-30T23:06:21Z)
• Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
  The (1+1)-evolution strategy (ES) with success-based step-size adaptation is analyzed on a general convex quadratic function. The convergence rate of the (1+1)-ES is derived explicitly and rigorously on a general convex quadratic function.
  arXiv  Detail & Related papers  (2021-03-02T09:03:44Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.