Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

• URL: http://arxiv.org/abs/2006.04663v3
• Date: Sat, 31 Oct 2020 10:42:28 GMT
• Title: Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
• Authors: Benjamin Doerr
• Abstract summary: We prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO) takes an expected number of $Omega (2n / sqrt n)$ to find any particular target search point. Our result improves over the previous lower bound of $Omega(exp(ndelta/2))$ valid for population sizes $mu.
• Score: 9.853329403413701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected number of $\Omega(2^n / \sqrt n)$ iterations to find any particular target search point. This bound is valid for all population sizes $\mu$. Our result improves over the previous lower bound of $\Omega(\exp(n^{\delta/2}))$ valid for population sizes $\mu = O(n^{1/2 - \delta})$, $0 < \delta < 1/2$.

Related papers

• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  We study the problem of robustly estimating the edge density of ErdHos-R'enyi random graphs $G(n, dcirc/n)$. Our algorithm is based on the sum-of-squares hierarchy.
  arXiv  Detail & Related papers  (2025-03-05T21:45:17Z)
• Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs [2.9123921488295768]
  We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Our algorithm achieves an expected $ell$-error of $O(d_max0.5 n0.5) = O(n)$ for degeneracy-bounded graphs.
  arXiv  Detail & Related papers  (2024-09-25T07:23:58Z)
• Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem [10.506038775815094]
  We show that the $(mu+1)$EA achieves maximal diversity with an expected runtime of $O(mu2 m4 log(m))$ for the small gap case. The $2P-EA_D$ displays stronger performance, with bounds of $O(mu2 n2 log(m))$ for the small gap case, $O(mu3 m3)$ for paths.
  arXiv  Detail & Related papers  (2024-04-17T22:20:02Z)
• A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities [1.8434042562191815]
  We show that population diversity converges to an equilibrium of near-perfect diversity. Our work partially solves a problem that has been open for more than 20 years.
  arXiv  Detail & Related papers  (2024-04-10T14:50:43Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  We consider the sparsification of the attention problem. For any super large feature dimension, we can reduce it down to the size nearly linear in length of sentence.
  arXiv  Detail & Related papers  (2023-04-10T05:52:38Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  Genetic algorithm with population size $mu=O(n)$ optimize jump functions with gap size $k ge 3$ in time. We show that this diversity persist with high probability for a time exponential in $mu$ (instead of quadratic) We obtain stronger runtime guarantees, among them the statement that for all $cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  arXiv  Detail & Related papers  (2023-02-24T10:50:24Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• 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.