The $(1 + 1)$-EA in Dynamic Environments

• URL: http://arxiv.org/abs/2606.13360v1
• Date: Thu, 11 Jun 2026 13:46:10 GMT
• Title: The $(1 + 1)$-EA in Dynamic Environments
• Abstract summary: We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,dots,2n-1$.<n>We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time.
• Score: 0.9298078773213346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the $(1 + 1)$-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,\dots,2^{n-1}$, and a Uniform weight variant, where the weights are drawn independently from $\mathrm{Unif}(0,1)$. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter $χ$ for mutation rate $χ/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{Ω(n)}$. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.

Related papers

• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  We study the feedback in a Gaussian single-index model with $r*(x) = *(langle *, xrangle)$ and $x sim N(0, I_d)$.<n>We analyze a two-stage neural reward model that first learns the hidden direction $*$ from reward-weighted samples and then fits the readout layer by weighted ridge regression.
  arXiv  Detail & Related papers  (2026-05-23T22:00:38Z)
• Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization [0.6015898117103067]
  We analyze a simultaneous learning-and-optimization algorithm that jointly estimates the conditional expectation and optimize the outer objective.<n>We establish that the method achieves a convergence rate of order $mathcalObig (1/sqrtNbig)$, where $N$ denotes the number of observed pairs.
  arXiv  Detail & Related papers  (2026-03-13T14:53:35Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
  We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. We also use this method to analyze the runtime of the $(1+1)$ evolutionary algorithm on a new benchmark consisting of $n/ell$ plateaus of effective size $2ell-1$.
  arXiv  Detail & Related papers  (2023-02-16T01:46:06Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  We show how to significantly reduce the number of neurons required for two-layer ReLU networks. We also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.
  arXiv  Detail & Related papers  (2022-06-26T06:51:31Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function [0.0]
  We study evolutionary algorithms in a dynamic setting, where for each generation a different fitness function is chosen. In particular, the hardest region for optimization is NOT around the optimum.
  arXiv  Detail & Related papers  (2020-10-26T08:55:53Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
  We extend the analysis of optimal mutation rates to two variants of the OneMax problem. We compute for all population sizes $lambda in 2i mid 0 le i le 18$ which mutation rates minimize the expected running time. Our results do not only provide a lower bound against which we can measure common evolutionary approaches.
  arXiv  Detail & Related papers  (2020-06-20T01:23:14Z)

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.