Analysis of Expected Hitting Time for Designing Evolutionary Neural Architecture Search Algorithms

Zeqiong Lv, Chao Qian, Gary G. Yen, Yanan SunarXiv 2022 · arXiv · OpenReview

Abstract

Evolutionary computation-based neural architecture search (ENAS) is a popular technique for automating architecture design of deep neural networks. In recent years, various ENAS algorithms have been proposed and shown promising performance on diverse real-world applications. In contrast to these groundbreaking applications, there is no theoretical guideline for assigning a reasonable running time (mainly affected by the generation number, population size, and evolution operator) given both the anticipated performance and acceptable computation budget on ENAS problems. The expected hitting time (EHT), which refers to the average generations, is considered to analyze the running time of ENAS algorithms. This paper proposes a general framework for estimating the EHT of ENAS algorithms, which includes common configuration, search space partition, transition probability estimation, and hitting time analysis. By exploiting the proposed framework, we consider the so-called (λ+λ)-ENAS algorithms with different mutation operators and manage to estimate the lower bounds of the EHT. Furthermore, we study the theoretical results on the NAS-Bench-101 architecture searching problem, and the results show that the one-bit mutation with "bit-based fair mutation" strategy needs less time than the "offspring-based fair mutation" strategy, and the bitwise mutation operator needs less time than the q-bit mutation operator. To the best of our knowledge, this is the first work focusing on the theory of ENAS, and the above observation will be substantially helpful in designing efficient ENAS algorithms.

Introduction

Neural Architecture Search (NAS) has revolutionized deep learning by automating the design of complex networks, moving away from manual trial-and-error. Among various NAS methodologies, Evolutionary Computation (EC) approaches—termed Evolutionary NAS (ENAS)—have proven highly effective in discovering state-of-the-art architectures. However, these algorithms have largely been treated as "black boxes." While empirical success is abundant, a theoretical foundation explaining their efficiency has been missing.

A critical question for practitioners is: How many iterations will an evolutionary algorithm require to find an optimal model? This paper addresses this by analyzing the Expected Hitting Time (EHT), which represents the average number of generations needed to reach a target architecture. By establishing theoretical lower bounds for EHT, the authors provide a much-needed guideline for resource allocation in automated deep learning design.

Theoretical Framework: Bridging EA and Markov Chains

To analyze ENAS theoretically, the authors propose the CEHT-ENAS (Combined Expected Hitting Time for ENAS) framework. This framework treats the evolutionary process as a Markov chain, where each state represents a population of architectures.

Mapping notations between Evolutionary Algorithms (EA) and Markov Chain theory.

As shown in the table above, the framework maps standard EA concepts—such as individuals, populations, and search spaces—onto Markovian states and state spaces. This mapping allows for the application of rigorous mathematical tools like Average Drift Analysis, which measures the expected progress toward the optimum in each generation.

Methodology: Encoding and Search Space Partitioning

A significant challenge in ENAS theory is the complexity of the search space. Unlike simple binary optimization problems, neural architectures are represented as directed acyclic graphs (DAGs).

Combination Encoding

The authors utilize a hybrid encoding strategy to represent these graphs. Each architecture is defined by a combination of an adjacency matrix (representing connections) and an integer vector (representing operations like 3x3 convolutions or max-pooling).

Conversion of a CNN architecture into an adjacency matrix and an operation vector.

This encoding, illustrated in the figure above, allows the search space to be partitioned based on Hamming distance. By dividing the massive space into subspaces based on how many "edits" (bit flips or operation changes) an architecture is from the global optimum, the authors can estimate transition probabilities between these levels.

Mutation Strategies and Surface Fitting

The study analyzes four distinct mutation operators:

  1. One-bit mutation (Bit-based fair): Flips a single bit in the encoding.
  2. One-bit mutation (Offspring-based fair): Ensures every potential child architecture has an equal probability of being generated, correcting for the "fairness paradox" where operation nodes might otherwise be over-sampled.
  3. q-bit mutation: Flips exactly q bits.
  4. Bitwise mutation: Each bit has a small, independent probability of flipping.

Because the exact distribution of a population in a complex NAS landscape is difficult to derive analytically, the authors employ least squares surface fitting. This "semi-theoretical" approach uses experimental sampling to model the population distribution (πt), which is then plugged back into the EHT formulas.

Key Insights and Results

The analysis yielded several groundbreaking insights into ENAS efficiency:

  • The Fairness Paradox: In non-binary encodings, standard mutation can be statistically biased. The "offspring-based fair mutation" was introduced to ensure unbiased exploration, though the "bit-based" variant was found to be faster in specific contexts.
  • Optimal Population Sizes: Both theory and experiments on the NAS-Bench-101 dataset (specifically the 7-node subset comprising ~85% of the data) showed that hitting time drops significantly as population size increases to 10–15. Beyond this range, the marginal gains in search speed diminish relative to the increased computational cost per generation.
  • Theoretical Validation: The derived lower bounds for EHT were consistently lower than actual experimental runtimes across various settings. This confirms that the proposed theorems provide a reliable "safe" baseline for the minimum time required to find an optimal architecture.

Conclusion

This work represents the first comprehensive theoretical analysis of ENAS. By providing a framework to estimate EHT, it moves the field toward a more principled approach to algorithm design. Future work will look to extend these bounds to include crossover operators and multi-objective search spaces, further closing the gap between the theory and practice of automated machine learning.

Summary updated

Abstract

Evolutionary computation-based neural architecture search (ENAS) is a popular technique for automating architecture design of deep neural networks. In recent years, various ENAS algorithms have been proposed and shown promising performance on diverse real-world applications. In contrast to these groundbreaking applications, there is no theoretical guideline for assigning a reasonable running time (mainly affected by the generation number, population size, and evolution operator) given both the anticipated performance and acceptable computation budget on ENAS problems. The expected hitting time (EHT), which refers to the average generations, is considered to analyze the running time of ENAS algorithms. This paper proposes a general framework for estimating the EHT of ENAS algorithms, which includes common configuration, search space partition, transition probability estimation, and hitting time analysis. By exploiting the proposed framework, we consider the so-called ($\lambda$+$\lambda$)-ENAS algorithms with different mutation operators and manage to estimate the lower bounds of the EHT {which are critical for the algorithm to find the global optimum}. Furthermore, we study the theoretical results on the NAS-Bench-101 architecture searching problem, and the results show that the one-bit mutation with "bit-based fair mutation" strategy needs less time than the "offspring-based fair mutation" strategy, and the bitwise mutation operator needs less time than the $q$-bit mutation operator. To the best of our knowledge, this is the first work focusing on the theory of ENAS, and the above observation will be substantially helpful in designing efficient ENAS algorithms.
BibTeX
@misc{lv2022analysis,
  author = {Zeqiong Lv and Chao Qian and Gary G. Yen and Yanan Sun},
  title = {{Analysis of Expected Hitting Time for Designing Evolutionary Neural Architecture Search Algorithms}},
  year = {2022},
  eprint = {2210.05397},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.05397},
}

Loading related content...

Figure