Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift

• URL: http://arxiv.org/abs/2005.00853v4
• Date: Tue, 20 Oct 2020 09:04:46 GMT
• Title: Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift
• Authors: Benjamin Doerr
• Abstract summary: We show that a simple negative drift theorem for multiplicative drift scenarios can simplify existing analyses. We discuss in more detail Lehre's (PPSN 2010) emphnegative drift in populations method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms.
• Score: 9.853329403413701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A decent number of lower bounds for non-elitist population-based evolutionary algorithms has been shown by now. Most of them are technically demanding due to the (hard to avoid) use of negative drift theorems -- general results which translate an expected progress away from the target into a high hitting time. We propose a simple negative drift theorem for multiplicative drift scenarios and show that it can simplify existing analyses. We discuss in more detail Lehre's (PPSN 2010) \emph{negative drift in populations} method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms for discrete search spaces. Together with other arguments, we obtain an alternative and simpler proof, which also strengthens and simplifies this method. In particular, now only three of the five technical conditions of the previous result have to be verified. The lower bounds we obtain are explicit instead of only asymptotic. This allows to compute concrete lower bounds for concrete algorithms, but also enables us to show that super-polynomial runtimes appear already when the reproduction rate is only a $(1 - \omega(n^{-1/2}))$ factor below the threshold. For the special case of algorithms using standard bit mutation with a random mutation rate (called uniform mixing in the language of hyper-heuristics), we prove the result stated by Dang and Lehre (PPSN 2016) and extend it to mutation rates other than $\Theta(1/n)$, which includes the heavy-tailed mutation operator proposed by Doerr, Le, Makhmara, and Nguyen (GECCO 2017). We finally apply our method and a novel domination argument to show an exponential lower bound for the runtime of the mutation-only simple genetic algorithm on \onemax for arbitrary population size.

Related papers

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  We show that two evolutionary algorithms can tolerate constant noise probabilities without increasing the runtime on the OneMax benchmark. Our results are based on a novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring.
  arXiv  Detail & Related papers  (2024-04-02T16:35:52Z)
• On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms [4.307128674848627]
  AdaPG$q,r$ is a framework that unifies and extends existing results by providing larger stepsize policies and improved lower bounds. Different choices of the parameters $q$ and $r$ are discussed and the efficacy of the resulting methods is demonstrated through numerical simulations.
  arXiv  Detail & Related papers  (2023-11-30T10:29:43Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes [4.553891255178496]
  We present a new framework and tools to generate smooth lower bounds on the sample complexity of differentially private algorithms. Our main technique is to apply a padding-and-permuting transformation to a fingerprinting code. We develop a new fingerprinting lemma that is stronger than those of Dwork et al. (FOCS 2015) and Bun et al. (SODA 2017)
  arXiv  Detail & Related papers  (2023-07-14T19:58:02Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  We study the prediction discriminability and diversity by studying the structure of the classification output matrix of a randomly selected data batch. We propose Batch Nuclear-norm Maximization and Minimization, which performs nuclear-norm on the target output matrix to enhance the target prediction ability. Experiments show that our method could boost the adaptation accuracy and robustness under three typical domain adaptation scenarios.
  arXiv  Detail & Related papers  (2021-07-13T15:08:32Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm [15.56430085052365]
  In the regime with no genetic drift, the runtime is roughly proportional to the population size. We propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size.
  arXiv  Detail & Related papers  (2020-04-15T15:12:01Z)
• Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
  We show that any of the algorithms randomized local search, algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function. We also prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark.
  arXiv  Detail & Related papers  (2020-04-13T00:24:33Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  We prove a stronger run time guarantee for the univariate distribution algorithm (UMDA) We show further run time gains from small selection rates. Under similar assumptions, we prove that a bound that matches our upper bound up to constant factors holds with high probability.
  arXiv  Detail & Related papers  (2020-04-10T10:20:05Z)

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.