  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.
