Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search

• URL: http://arxiv.org/abs/2210.14016v4
• Date: Mon, 29 May 2023 03:30:28 GMT
• Title: Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search
• Authors: Xin Qiu, Risto Miikkulainen
• Abstract summary: Population-based search has emerged as a possible alternative to Reinforcement Learning (RL) for black-box neural architecture search (NAS) This paper presents the first theoretical analysis of the behaviors of mutation, crossover and RL in black-box NAS. It proposes a new crossover operator based on the shortest edit path (SEP) in graph space.
• Score: 20.948038514886377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Population-based search has recently emerged as a possible alternative to Reinforcement Learning (RL) for black-box neural architecture search (NAS). It performs well in practice even though it is not theoretically well understood. In particular, whereas traditional population-based search methods such as evolutionary algorithms (EAs) draw much power from crossover operations, it is difficult to take advantage of them in NAS. The main obstacle is believed to be the permutation problem: The mapping between genotype and phenotype in traditional graph representations is many-to-one, leading to a disruptive effect of standard crossover. This paper presents the first theoretical analysis of the behaviors of mutation, crossover and RL in black-box NAS, and proposes a new crossover operator based on the shortest edit path (SEP) in graph space. The SEP crossover is shown theoretically to overcome the permutation problem, and as a result, have a better expected improvement compared to mutation, standard crossover and RL. Further, it empirically outperform these other methods on state-of-the-art NAS benchmarks. The SEP crossover therefore allows taking full advantage of population-based search in NAS, and the underlying theory can serve as a foundation for deeper understanding of black-box NAS methods in general.

Related papers

• Diversity-Preserving Exploitation of Crossover [0.0]
  We introduce a new paradigm for utilizing crossover that reduces this antagonism, which we call diversity-preserving exploitation of crossover (DiPEC)<n>The resulting Diversity Exploitation Genetic Algorithm (DEGA) is able to still exploit the benefits of crossover, but preserves a much higher diversity than conventional approaches.
  arXiv  Detail & Related papers  (2025-07-02T09:28:06Z)
• Runtime Analysis of Evolutionary NAS for Multiclass Classification [25.67863839453669]
  We consider (1+1)-ENAS algorithms with one-bit and bit-wise mutations, and analyze their upper and lower bounds on the expected runtime.<n>We prove that the algorithm using both mutations can find the optimum with the expected runtime upper bound of $O(rMlnrM)$ and lower bound of $Omega(rMlnM)$.
  arXiv  Detail & Related papers  (2025-06-06T12:09:30Z)
• TopoNAS: Boosting Search Efficiency of Gradient-based NAS via Topological Simplification [11.08910129925713]
  TopoNAS is a model-agnostic approach for gradient-based one-shot NAS. It significantly reduces searching time and memory usage by topological simplification of searchable paths.
  arXiv  Detail & Related papers  (2024-08-02T15:01:29Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation [4.212663349859165]
  We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II. We show that immune-inspired hypermutations cannot avoid exponential optimisation times.
  arXiv  Detail & Related papers  (2023-01-31T15:03:34Z)
• $\beta$-DARTS++: Bi-level Regularization for Proxy-robust Differentiable Architecture Search [96.99525100285084]
  Regularization method, Beta-Decay, is proposed to regularize the DARTS-based NAS searching process (i.e., $beta$-DARTS) In-depth theoretical analyses on how it works and why it works are provided.
  arXiv  Detail & Related papers  (2023-01-16T12:30:32Z)
• Analyzing the Expected Hitting Time of Evolutionary Computation-based Neural Architecture Search Algorithms [29.385876073356044]
  The expected hitting time (EHT) is one of the most important theoretical issues, since it implies the average computational time complexity. This paper proposes a general method by integrating theory and experiment for estimating the EHT of ENAS algorithms. To the best of our knowledge, this work is the first attempt to establish a theoretical foundation for ENAS algorithms.
  arXiv  Detail & Related papers  (2022-10-11T12:16:06Z)
• $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search [85.84110365657455]
  We propose a simple-but-efficient regularization method, termed as Beta-Decay, to regularize the DARTS-based NAS searching process. Experimental results on NAS-Bench-201 show that our proposed method can help to stabilize the searching process and makes the searched network more transferable across different datasets.
  arXiv  Detail & Related papers  (2022-03-03T11:47:14Z)
• Pi-NAS: Improving Neural Architecture Search by Reducing Supernet Training Consistency Shift [128.32670289503025]
  Recently proposed neural architecture search (NAS) methods co-train billions of architectures in a supernet and estimate their potential accuracy. The ranking correlation between the architectures' predicted accuracy and their actual capability is incorrect, which causes the existing NAS methods' dilemma. We attribute this ranking correlation problem to the supernet training consistency shift, including feature shift and parameter shift. We address these two shifts simultaneously using a nontrivial supernet-Pi model, called Pi-NAS.
  arXiv  Detail & Related papers  (2021-08-22T09:08:48Z)
• Understanding the wiring evolution in differentiable neural architecture search [114.31723873105082]
  Controversy exists on whether differentiable neural architecture search methods discover wiring topology effectively. We study the underlying mechanism of several existing differentiable NAS frameworks.
  arXiv  Detail & Related papers  (2020-09-02T18:08:34Z)
• Weight-Sharing Neural Architecture Search: A Battle to Shrink the Optimization Gap [90.93522795555724]
  Neural architecture search (NAS) has attracted increasing attentions in both academia and industry. Weight-sharing methods were proposed in which exponentially many architectures share weights in the same super-network. This paper provides a literature review on NAS, in particular the weight-sharing methods.
  arXiv  Detail & Related papers  (2020-08-04T11:57:03Z)

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.