Runtime Analysis of Evolutionary NAS for Multiclass Classification

• URL: http://arxiv.org/abs/2506.06019v1
• Date: Fri, 06 Jun 2025 12:09:30 GMT
• Title: Runtime Analysis of Evolutionary NAS for Multiclass Classification
• Authors: Zeqiong Lv, Chao Qian, Yun Liu, Jiahao Fan, Yanan Sun,
• Abstract summary: 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)$.
• Score: 25.67863839453669
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary neural architecture search (ENAS) is a key part of evolutionary machine learning, which commonly utilizes evolutionary algorithms (EAs) to automatically design high-performing deep neural architectures. During past years, various ENAS methods have been proposed with exceptional performance. However, the theory research of ENAS is still in the infant. In this work, we step for the runtime analysis, which is an essential theory aspect of EAs, of ENAS upon multiclass classification problems. Specifically, we first propose a benchmark to lay the groundwork for the analysis. Furthermore, we design a two-level search space, making it suitable for multiclass classification problems and consistent with the common settings of ENAS. Based on both designs, we consider (1+1)-ENAS algorithms with one-bit and bit-wise mutations, and analyze their upper and lower bounds on the expected runtime. We prove that the algorithm using both mutations can find the optimum with the expected runtime upper bound of $O(rM\ln{rM})$ and lower bound of $\Omega(rM\ln{M})$. This suggests that a simple one-bit mutation may be greatly considered, given that most state-of-the-art ENAS methods are laboriously designed with the bit-wise mutation. Empirical studies also support our theoretical proof.

Related papers

• A Pairwise Comparison Relation-assisted Multi-objective Evolutionary Neural Architecture Search Method with Multi-population Mechanism [58.855741970337675]
  Neural architecture search (NAS) enables re-searchers to automatically explore vast search spaces and find efficient neural networks. NAS suffers from a key bottleneck, i.e., numerous architectures need to be evaluated during the search process. We propose the SMEM-NAS, a pairwise com-parison relation-assisted multi-objective evolutionary algorithm based on a multi-population mechanism.
  arXiv  Detail & Related papers  (2024-07-22T12:46:22Z)
• DNA Family: Boosting Weight-Sharing NAS with Block-Wise Supervisions [121.05720140641189]
  We develop a family of models with the distilling neural architecture (DNA) techniques. Our proposed DNA models can rate all architecture candidates, as opposed to previous works that can only access a sub- search space using algorithms. Our models achieve state-of-the-art top-1 accuracy of 78.9% and 83.6% on ImageNet for a mobile convolutional network and a small vision transformer, respectively.
  arXiv  Detail & Related papers  (2024-03-02T22:16:47Z)
• A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search [24.056523078277053]
  This work goes preliminary steps toward the mathematical runtime analysis of ENAS. We define a binary classification problem $textscUNIFORM$, and formulate an explicit fitness function to represent the relationship between neural architecture and classification accuracy. The theoretical results show that the local and global mutations achieve nearly the same performance on $textscUNIFORM$.
  arXiv  Detail & Related papers  (2024-01-22T06:29:22Z)
• Asynchronous Evolution of Deep Neural Network Architectures [10.60691612679966]
  Many evolutionary algorithms (EAs) take advantage of parallel evaluation of candidates. If evaluation times vary significantly, many worker nodes (i.e., compute clients) are idle much of the time, waiting for the next generation to be created. This paper proposes a generic asynchronous evaluation strategy (AES) that is then adapted to work with ENAS.
  arXiv  Detail & Related papers  (2023-08-08T07:33:49Z)
• GPT-NAS: Evolutionary Neural Architecture Search with the Generative Pre-Trained Model [22.438001137031574]
  This work presents a novel architecture search algorithm, called GPT-NAS, that optimize neural architectures by Generative Pre-Trained (GPT) model.<n>In GPT-NAS, we assume that a generative model pre-trained on a large-scale corpus could learn the fundamental law of building neural architectures.<n>Our GPT-NAS method significantly outperforms seven manually designed neural architectures and thirteen architectures provided by competing NAS methods.
  arXiv  Detail & Related papers  (2023-05-09T11:29:42Z)
• 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)
• $\eta$-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)
• iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients [75.41173109807735]
  Differentiable ARchiTecture Search (DARTS) has recently become the mainstream of neural architecture search (NAS) We tackle the hypergradient computation in DARTS based on the implicit function theorem. We show that the architecture optimisation with the proposed method, named iDARTS, is expected to converge to a stationary point.
  arXiv  Detail & Related papers  (2021-06-21T00:44:11Z)
• OPANAS: One-Shot Path Aggregation Network Architecture Search for Object Detection [82.04372532783931]
  Recently, neural architecture search (NAS) has been exploited to design feature pyramid networks (FPNs) We propose a novel One-Shot Path Aggregation Network Architecture Search (OPANAS) algorithm, which significantly improves both searching efficiency and detection accuracy.
  arXiv  Detail & Related papers  (2021-03-08T01:48:53Z)
• DrNAS: Dirichlet Neural Architecture Search [88.56953713817545]
  We treat the continuously relaxed architecture mixing weight as random variables, modeled by Dirichlet distribution. With recently developed pathwise derivatives, the Dirichlet parameters can be easily optimized with gradient-based generalization. To alleviate the large memory consumption of differentiable NAS, we propose a simple yet effective progressive learning scheme.
  arXiv  Detail & Related papers  (2020-06-18T08:23:02Z)
• DDPNAS: Efficient Neural Architecture Search via Dynamic Distribution Pruning [135.27931587381596]
  We propose an efficient and unified NAS framework termed DDPNAS via dynamic distribution pruning. In particular, we first sample architectures from a joint categorical distribution. Then the search space is dynamically pruned and its distribution is updated every few epochs. With the proposed efficient network generation method, we directly obtain the optimal neural architectures on given constraints.
  arXiv  Detail & Related papers  (2019-05-28T06:35:52Z)

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.