  Evolutionary computation-based neural architecture search (ENAS) is a popular
technique for automating architecture design of deep neural networks. Despite
its groundbreaking applications, there is no theoretical study for ENAS. 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, which includes common configuration, search space partition,
transition probability estimation, population distribution fitting, and hitting
time analysis. By exploiting the proposed method, we consider the
($\lambda$+$\lambda$)-ENAS algorithms with different mutation operators and
estimate the lower bounds of the EHT. Furthermore, we study the EHT on the
NAS-Bench-101 problem, and the results demonstrate the validity of the proposed
method. To the best of our knowledge, this work is the first attempt to
establish a theoretical foundation for ENAS algorithms.
