Analyzing the Expected Hitting Time of Evolutionary Computation-based Neural Architecture Search Algorithms
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Neural Architecture SearchSimilar Papers 제목 키워드 기반
Average Drift Analysis and Population Scalability
This paper aims to study how the population size affects the computation time of evolutionary algorithms in a rigorous way. The computation time of an evolutionary algorithm can be measured by either the expected number …
Evolutionary AlgorithmsMultiplicative Up-Drift
Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been…
Evolutionary AlgorithmsA Unified Markov Chain Approach to Analysing Randomised Search Heuristics
The convergence, convergence rate and expected hitting time play fundamental roles in the analysis of randomised search heuristics. This paper presents a unified Markov chain approach to studying them. Using the approach…
From random walks to distances on unweighted graphs
Large unweighted directed graphs are commonly used to capture relations between entities. A fundamental problem in the analysis of such networks is to properly define the similarity or dissimilarity between any two verti…
ClusteringMaximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward struct…
Informativeness