  Population-based search has recently emerged as a possible alternative to
Reinforcement Learning (RL) for black-box neural architecture search (NAS). It
performs well in practice even though it is not theoretically well understood.
In particular, whereas traditional population-based search methods such as
evolutionary algorithms (EAs) draw much power from crossover operations, it is
difficult to take advantage of them in NAS. The main obstacle is believed to be
the permutation problem: The mapping between genotype and phenotype in
traditional graph representations is many-to-one, leading to a disruptive
effect of standard crossover. This paper presents the first theoretical
analysis of the behaviors of mutation, crossover and RL in black-box NAS, and
proposes a new crossover operator based on the shortest edit path (SEP) in
graph space. The SEP crossover is shown theoretically to overcome the
permutation problem, and as a result, have a better expected improvement
compared to mutation, standard crossover and RL. Further, it empirically
outperform these other methods on state-of-the-art NAS benchmarks. The SEP
crossover therefore allows taking full advantage of population-based search in
NAS, and the underlying theory can serve as a foundation for deeper
understanding of black-box NAS methods in general.
