Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal

• URL: http://arxiv.org/abs/2606.13344v1
• Date: Thu, 11 Jun 2026 13:34:03 GMT
• Title: Improved Runtime Bound for the $(μ+ 1)$ EA on BinVal
• Abstract summary: We show that the $(+1)$ EA is at most a factor $O(log cdot log n)$ slower on BinVal than on OneMax.
• Score: 0.9298078773213346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the $(μ+1)$ EA on the Binary Value function BinVal. We show that it needs at most $O(μ\log μ\cdot n \log n)$ function evaluations to find the optimum when $μ= o(n/\log n)$. This substantially improves upon the recent upper bound of $O(μ^5 n \log(n/μ^4))$ by Krejca, Neumann and Witt. Our results hold for several mutation operators including standard bit mutation. In particular, our bound implies that the $(μ+1)$ EA is at most a factor $O(\log μ\cdot \log n)$ slower on BinVal than on OneMax.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation [17.156227790252526]
  The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = Oleft( T + fraclog (1/varepsilon)logleft(e + log (1/varepsilon)/(T) right)<n>We give an implementation of the same algorithm that retains its optimal query complexity and uses $$ Oleft[ q left( a + logleft (1 + fracT(+ T)varepsilon
  arXiv  Detail & Related papers  (2026-08-31T11:39:55Z)
• Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
  query complexity of a non min-nonconcave function $f$ $[0,1].<n>We show that queries to $f$ and its gradient point must make a point that is exponential in $1 ord$.
  arXiv  Detail & Related papers  (2026-05-13T17:34:24Z)
• Anytime Analysis on BinVal: Adaptive Parameters Help [0.0]
  We analyze the fixed-target run time of various algorithms using BinVal as fitness function.<n>We show that the fixed-target run time for $k in o(n)$ and a constant $varepsilon >0$ arbitrarily close to zero is in $mathcalOleft(k1+varepsilonright)$ for this algorithm.
  arXiv  Detail & Related papers  (2026-04-08T11:47:10Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions [9.044970217182117]
  decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function $f$, but instead optimize $N + 1$ single-objective subproblems of $f$ in a co-evolutionary manner. We analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark. Our overall bound for power-law suggests that the MOEA/D performs best for $N = O(nbeta - 1)$, resulting in an $O(n
  arXiv  Detail & Related papers  (2024-05-02T05:32:19Z)
• Hardest Monotone Functions for Evolutionary Algorithms [0.0]
  We revisit the question how hard it can be for the $(1+1)$ Evolutionary algorithm to optimize monotone pseudo-Boolean functions.<n>We show that our construction provides the first explicit example which realizes the pessimism of the poea model.
  arXiv  Detail & Related papers  (2023-11-13T16:13:30Z)
• 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)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• 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.