# Accelerating Evolutionary Neural Architecture Search via Multi-Fidelity
Evaluation ††thanks: Manuscript received –. This work was supported in part by
the National Key Research and Development Project under Grant 2018AAA0100105,
in part by the National Natural Science Foundation of China under Grant
61822301, 61876123, 61906001, and U1804262, in part by the Hong Kong Scholars
Program under Grant XJ2019035, in part by the Anhui Provincial Natural Science
Foundation under Grant 1808085J06 and 1908085QF271, and in part by the State
Key Laboratory of Synthetical Automation for Process Industries under Grant
PAL-N201805 (Corresponding author: Xiaoshu Xiang and Xingyi Zhang).

Shangshang Yang, Ye Tian, Xiaoshu Xiang, Shichen Peng, and Xingyi Zhang,
_Senior Member, IEEE_ S. Yang, S. Peng and X. Zhang is with the Key Laboratory
of Intelligent Computing and Signal Processing of Ministry of Education,
School of Artificial Intelligence, Anhui University, Hefei 230039, China
(email<EMAIL_ADDRESS><EMAIL_ADDRESS>xyzhanghust@gmail.com).Y. Tian and X. Xiang are with the Key Laboratory of
Intelligent Computing and Signal Processing of Ministry of Education,
Institutes of Physical Science and Information Technology, Anhui University,
Hefei 230601, China (email<EMAIL_ADDRESS>94xxs13@gmail.com).

###### Abstract

Evolutionary neural architecture search (ENAS) has recently received
increasing attention by effectively finding high-quality neural architectures,
which however consumes high computational cost by training the architecture
encoded by each individual for complete epochs in individual evaluation.
Numerous ENAS approaches have been developed to reduce the evaluation cost,
but it is often difficult for most of these approaches to achieve high
evaluation accuracy. To address this issue, in this paper we propose an
accelerated ENAS via multi-fidelity evaluation termed MFENAS, where the
individual evaluation cost is significantly reduced by training the
architecture encoded by each individual for only a small number of epochs. The
balance between evaluation cost and evaluation accuracy is well maintained by
suggesting a multi-fidelity evaluation, which identifies the potentially good
individuals that cannot survive from previous generations by integrating
multiple evaluations under different numbers of training epochs. For high
diversity of neural architectures, a population initialization strategy is
devised to produce different neural architectures varying from ResNet-like
architectures to Inception-like ones. Experimental results on CIFAR-10 show
that the architecture obtained by the proposed MFENAS achieves a 2.39% test
error rate at the cost of only 0.6 GPU days on one NVIDIA 2080TI GPU,
demonstrating the superiority of the proposed MFENAS over state-of-the-art NAS
approaches in terms of both computational cost and architecture quality. The
architecture obtained by the proposed MFENAS is then transferred to CIFAR-100
and ImageNet, which also exhibits competitive performance to the architectures
obtained by existing NAS approaches. The source code of the proposed MFENAS is
available at https://github.com/DevilYangS/MFENAS/.

###### Index Terms:

Neural architecture search, evolutionary algorithm, multi-fidelity evaluation,
convolutional neural networks.

††publicationid: pubid: 0000–0000/00$00.00 © 0000 IEEE

##  I Introduction

Deep learning has made significant success in tackling various machine
learning tasks such as classification [1], object detection [2], speech
recognition [3], natural language processing [4], among many others. For
achieving desirable performance, it is widely recognized that the architecture
of deep neural networks (DNNs) is very crucial and a number of researchers are
devoted to manually designing various neural architectures. Examples of this
category include the ResNet [5], DenseNet [6] and GoogLeNet [7, 8].
Nevertheless, the hand-craft designed architectures often require extensive
human expertise in both DNNs and the problem to be addressed, which is
unrealistic for common users. This challenge arises a hot research direction
in machine learning, called neural architecture search (NAS).

The NAS task was first reported by Zoph and Le in [9], where the reinforcement
learning was adopted as the optimization algorithm to automatically search for
the architecture of convolutional neural networks (CNNs). Based on the work in
[9], another famous NAS approach named NASNet was developed by Zoph and Le for
CNNs in [10], which can obtain neural architectures with extremely competitive
performance compared to the hand-craft ones. Basically, the task of NAS can be
considered as the problem of combination optimization of numerous components
in DNNs, which is often computationally very hard to be addressed due to the
large search space. In the past years, a variety of optimization techniques
have been adopted for NAS to yield high-performance architectures, including
reinforcement learning (RL) [11, 12], gradient optimization [13, 14], Bayesian
optimization [15], and evolutionary algorithm (EA) [16, 17].

Among existing optimization techniques for NAS, EAs have attracted increasing
attention due to their powerful abilities in dealing with various complex
application problems [18, 19, 20, 21]. The branch of NAS using EAs is usually
called evolutionary neural architecture search (ENAS) and a number of ENAS
approaches have been reported in the past three years [22, 23, 24, 25, 16, 26,
17]. For example, Real _et al._ [23] proposed a large-scale evolution approach
to search for the architecture of DNNs by taking about 2750 GPU days, by which
the best architecture achieved a 5.4% error rate on CIFAR-10 dataset [27]; In
[24], a novel hierarchical genetic representation was devised for EAs to
encode the architecture of DNNs, which can search for the architecture having
a 3.75% error rate within 300 GPU days; Xie and Yuille [22] suggested an EA
named Genetic-CNN to only optimize the topology of CNNs, where the best
architecture found in 17 GPU days achieved a 7.1% error rate; Sun _et al._
[26] suggested an AE-CNN algorithm to evolve CNN architectures based on two
types of effective blocks and it took 27 GPU days to obtain an optimized CNN
architecture with a 4.3% error rate.

In spite of the promising performance of found architectures, ENAS usually
suffers from high computation cost, making it impractical for real-world
applications. On the one hand, EAs are a population based stochastic
algorithm, where numerous individuals in the population need to be evaluated
at each generation. On the other hand, the evaluation of each individual is
computationally expensive for the task of NAS since the architecture encoded
by the individual requires to be trained for complete epochs. To address this
issue, a variety of approaches have been developed for ENAS, which can be
roughly divided into the following two categories. The first category of
approaches is developed based on the idea of reducing the number of individual
evaluations in the process of optimization, where the surrogate model [28, 29,
30, 31], early stopping [32], population reduction and memory [33, 17] are
three commonly used techniques. The other category of approaches focuses on
reducing the computational cost of training the architecture encoded by each
individual in individual evaluation, including weight inheritance [34], subset
training [35] and weight sharing [36].

Nevertheless, it still poses a great challenge for existing accelerated ENAS
approaches to achieve high evaluation accuracy when reducing evaluation cost,
which hinders these approaches from finding high-quality architectures at low
computational cost. In this paper, we propose an accelerated ENAS via multi-
fidelity evaluation, termed MFENAS, to achieve both low evaluation cost and
high evaluation accuracy in NAS. The proposed MFENAS uses a small number of
training epochs in individual evaluation to achieve low evaluation cost, and
employs multi-fidelity evaluation to balance evaluation cost and evaluation
accuracy in NAS. The main contributions of this paper are summarized as
follows:

  1. 1.

A novel idea of reducing evaluation cost of individuals is suggested to
accelerate ENAS, where the architecture encoded by an individual is trained
for only a small number of epochs rather than complete epochs. For balancing
evaluation cost and evaluation accuracy, we further propose a multi-fidelity
evaluation to identify potentially good individuals that cannot survive from
previous generations, where the idea of fidelity is introduced from
computational fluid dynamics simulations [37]. The proposed multi-fidelity
evaluation combines low-fidelity evaluation and high-fidelity evaluation that
are distinguished by the number of training epochs for individual evaluation.
In this case, the proposed multi-fidelity evaluation takes the advantages of
both low computational cost in low-fidelity evaluation and high evaluation
accuracy in high-fidelity evaluation, ensuring the balance between evaluation
cost and evaluation accuracy. Hence, the proposed multi-fidelity evaluation
can facilitate ENAS in achieving high-quality architectures at low
computational cost.

  2. 2.

Based on the proposed multi-fidelity evaluation, a multi-objective EA called
MFENAS is developed in the framework of NSGA-II [38] for fast neural
architecture search. The validation error rate and model complexity are
adopted as two optimization objectives with the aim of finding high-accuracy
neural architectures under different levels of complexity. For high diversity
of initial neural architectures, a population initialization strategy is
suggested to produce a set of neural architectures varying from Inception-like
architectures to ResNet-like ones. For maintaining diversity of neural
architectures during NAS, a variable-length integer vector is utilized to
encode neural architectures, and a genetic operator is devised to equip with
variable-length individuals in the proposed MFENAS.

  3. 3.

The performance of the proposed MFENAS is verified on three widely used
datasets, namely, CIFAR-10, CIFAR-100 and ImageNet. The search of neural
architectures is implemented on CIFAR-10 and the architectures found by the
proposed MFENAS are evaluated on CIFAR-10, CIFAR-100 and ImageNet. The best
architecture found by the proposed MFENAS achieves a 2.39% test error rate on
CIFAR-10 at the cost of only 0.6 GPU days on one NVIDIA 2080TI GPU, which is
superior over existing EA and non-EA based NAS approaches. The best
architecture is transferred to CIFAR-100 and ImageNet, which also holds a
promising performance in comparison with existing NAS approaches.

The rest of this paper is organized as follows. Section II presents
preliminaries and related work on ENAS. Section III elaborates the proposed
MFENAS and Section IV reports the experimental results for verifying the
performance of the proposed MFENAS. Finally, conclusions and future work are
given in Section V.

##  II Preliminaries and Related Work

In this section, we first briefly introduce some preliminaries of ENAS. Then,
we review existing work on reducing the computation cost of ENAS. Finally, we
present the motivation of this study.

###  II-A Evolutionary Neural Architecture Search

Given a data set $D=\\{D_{train},D_{val},D_{test}\\}$, the neural architecture
search can be formulated as the following single-objective optimization
problem.

$\min_{\mathbf{x}}\mathbf{F}(\mathbf{x})=1-f_{val\\_accruacy}(\mathbf{x},D),$
(1)

where $\mathbf{x}$ represents the architecture to be optimized,
$f_{val\\_accruacy}(\mathbf{x},D)$ denotes the validation accuracy of the
architecture $\mathbf{x}$ on $D_{val}$ after being trained for complete epochs
on the training dataset $D_{train}$.

Due to the enormous demand for small-sized networks in real-world
applications, the model complexity is also considered in the NAS task [39,
16], and thus NAS can be formulated as a bi-objective optimization problem as
follows.

$\min_{\mathbf{x}}\mathbf{F}(\mathbf{x})=\left\\{\begin{aligned}
f_{1}(\mathbf{x})&=1-f_{val\\_accruacy}(\mathbf{x},D)\\\
f_{2}(\mathbf{x})&=f_{complexity}(\mathbf{x})\\\ \end{aligned}\right.,$ (2)

where $f_{1}(\mathbf{x})$ is the classification error rate of $\mathbf{x}$ on
validation dataset $D_{val}$ and $f_{2}(\mathbf{x})$ denotes the model
complexity of $\mathbf{x}$. The model complexity can be measured by the number
of model parameters, the number of floating-point operations and inference
time [16, 39]. In this paper, we adopt the bi-objective optimization problem
formulation for NAS, where the number of model parameters is used to measure
the model complexity.

To address multi-objective optimization problems, a variety of approaches have
been developed based on different ideas, e.g., Bayesian optimization [40],
simulated annealing [41], Tabu search [42] and EAs [43]. Among these
approaches, EAs are the most widely investigated approaches to multi-objective
optimization due to the fact that they maintain a population approximating the
set of optimal solutions. A large number of EAs have been developed to solve
multi-objective optimization problems in different research areas, such as
community detection [19], shelter location problem [20], and vehicle routing
problem [44].

Generally, an EA consists of five main steps as follows: (1) Population
initialization, by which an initial population is created at the beginning of
EA and each individual in the population encodes a solution of the problem to
be solved. (2) Mating pool selection, by which individuals are mated to select
parent individuals. (3) Genetic operation, where crossover and mutation
operators are used to create offspring individuals from the parent
individuals. (4) Fitness evaluation, where the quality of each individual in
the population is measured. (5) Environment selection, by which good
individuals in the parent and offspring population survive for next
generation. Fig. 1 gives the framework of EAs for NAS tasks. It is worth
noting that the fitness evaluation of each individual for NAS is achieved by
training the architecture encoded by each individual for complete epochs on
training dataset, which is often characterized with expensive computational
cost.

Figure 1: A general framework of EAs for NAS

###  II-B Related Work

To reduce the computational cost of ENAS, many approaches have been developed
and can be roughly divided into the following two categories.

####  II-B1 Reducing the Number of Individuals to Be Evaluated in Real

Three ideas are often adopted in existing ENAS to reduce the number of
individuals to be evaluated in real, namely, surrogate model, early stopping,
population reduction and memory.

Surrogate Model. The main idea of surrogate model based ENAS approaches is to
predict the quality of architectures encoded by some individuals by surrogate
models to reduce the number of individuals to be evaluated in real. A
representative belonging to this idea is the work reported by Sun _et al._ in
[31], where the random forest was adopted as the surrogate model to predict
the quality of newly created individuals at each generation of EAs.
Experimental results indicated that the surrogate model assisted ENAS saved
68.18% and 69.70% computational cost on CIFAR10 and CIFAR100, respectively.
Nevertheless, the best architecture found on CIFAR10 can still achieve 94.70%
test accuracy, which is only 0.06% worse than the version without surrogate
model. There also exist some surrogate assisted NAS approaches which are not
based on the framework of EAs [28, 30].

Early Stopping. The idea of early stopping is to terminate the training of
poor individuals based on the performance of architectures in the early
training stage to reduce the number of individuals to be evaluated. In [45],
Suganuma _et al._ developed an early stopping strategy based on a reference
curve to accelerate ENAS, where the reference curve is updated on the basis of
the best individual in population at each generation. A similar idea is also
adopted for accelerating ENAS in [46] and [47]. Despite that the idea of early
stopping can considerably reduce the computational cost of ENAS approaches, it
easily leads to inaccurate estimation on individual quality, especially for
complicated architectures as stated in [48]. This makes it hard for early
stopping based ENAS approaches to achieve competitive performance in NAS.

Population Reduction and Memory. The population reduction achieves the
accelerating of ENAS by recursively reducing the size of population [33, 49],
whereas the population memory avoids evaluating the same individuals that have
been evaluated in the evolution of population to solve this task [17, 50]. Fan
_et al._ [49] divided the whole optimization process of the ENAS approach into
different stages with different population sizes, where a large population is
used to ensure the global search ability in early stage and a small population
is adopted to reduce the number of individuals to be evaluated in population
in later stage. In [17], Sun _et al._ utilized a hashing method to record both
architecture information and fitness of each individual, so that the fitness
value for an individual can be directly obtained if this individual has been
recorded. Despite avoiding redundant individual evaluations in ENAS, these
strategies still consume expensive computational cost to achieve high-quality
architectures [48].

####  II-B2 Reducing the Evaluation Cost of Each Individual

The subset training, weight inheritance and weight sharing are three ideas
which are widely adopted in ENAS approaches to reduce the evaluation cost of
each individual.

Subset Training. The subset training is to train the architecture on a small
subset selected from the original dataset having a large number of data, by
which the computation cost on evaluating each individual can be effectively
reduced. Following this idea, Liu _et al._ [35] suggested an ENAS approach to
search for the optimal architecture for medical image denoising. To reduce the
training time without seriously degrading the performance, a small subset
having similar properties to those in the original dataset is randomly
selected for exploring promising CNN architectures. Despite that the subset
training can effectively reduce computational cost of ENAS, there exists a big
challenge of overfitting problem due to the difficulty of properly selecting a
subset.

Weight Inheritance. The weight inheritance is a technique that the
architectures encoded by offspring individuals inherit most weights in the
architectures encoded by parent individuals, since the genetic operators in
ENAS produce offspring individuals by inheriting most architectures encoded by
parent individuals [51, 34]. In this way, the training of architecture encoded
by each individual can be accelerated by means of initiating the training with
the inherited weights instead of starting from scratch, which accelerates the
evaluation cost of each individual. Zhang _et al._ [51] adopted the weight
inheritance in the evaluation of offspring individuals in ENAS, where the
architectures encoded by these individuals are trained for only one epoch
based on the weights inherited from parent individuals. In [34], a sampled
training strategy was designed to train all parent individuals at the
beginning of each iteration, and the offspring individuals at each iteration
can be directly evaluated on a validation dataset without any training based
on the weights inherited from the parent individuals.

Weight Sharing. The weight sharing is to reduce the evaluation cost of each
individual by directly obtaining the weights of the architecture encoded by
each individual from a set of weights stored in a SuperNet model. Hence, the
individuals in ENAS can be evaluated by training only one SuperNet model
instead of training all the architectures encoded by these individuals, which
thus considerably reduces the computational cost of ENAS [11]. In [36], Yang
_et al._ developed a continuous EA for efficient NAS approach based on weight
sharing, where all individuals generated in NAS share the same set of weights
in one SuperNet. The weights in the SuperNet are updated by training the
architectures encoded by non-dominated individuals at each generation of ENAS.

###  II-C Motivation

Different from existing accelerated ENAS approaches, the proposed MFENAS
reduces the evaluation cost of each individual by means of training the
architecture encoded by each individual for only a small number of epochs
rather than complete epochs. This idea is motivated from the observation that
the performance ranking of individuals at each generation will not change
considerably no matter whether the architectures encoded by the individuals
are trained for a small number of epochs or complete epochs. To illustrate
this fact, Fig. 2 shows the profiles of performance ranking on 1000
architectures under different numbers of training epochs, where 1,000 neural
architectures are randomly sampled in the cell based search space according to
the setting of training suggested in [10, 14, 16], and the number of nodes in
each cell ranges from $5$ to $12$. Specifically, Fig. 2 (a) presents the
validation accuracy of 10 architectures that are randomly selected from the
1000 architectures, where the architectures having high accuracy under a small
number of training epochs also hold high accuracy under complete epochs and
vice verse.

This observation also often holds when the accuracy difference between two
architectures is not significant as depicted in Fig. 2 (b), which gives the
profile of the Kendall Tau Rank Correlation Coefficient (Kendall’s $\tau$ for
short) between the performance ranking at each epoch and that of final epoch
on all of the 1,000 randomly sampled architectures. The Kendall’s $\tau$ is a
widely used indicator to measure the correlation between two different
rankings of items [52]. The $\tau\in[-1,1]$, where $\tau=1$ means the two
rankings are exactly the same and $\tau=-1$ means they are completely
opposite.

From Fig. 2 (b), we can find the following two results. On the one hand, the
performance ranking of architectures at any number of training epochs holds a
high correlation with the ranking at final epoch, where the Kendall’s $\tau$
value is larger than 0.45 and competitive in comparison with most of the
surrogate models used in ENAS [28, 30, 31]. On the other hand, the Kendall’s
$\tau$ value increases considerably as the number of training epochs
increases, which inspires us to consider the idea of multi-fidelity
optimization (MFO) [37] to ensure the performance of ENAS under a small number
of epochs. It is worth noting that the MFO is a popular idea for striking the
balance between effectiveness and efficiency of an algorithm by means of
combining high fidelity and low fidelity, where the high fidelity leads to
high-accuracy evaluation but low computation efficiency, and the low fidelity
leads to high computation efficiency but low-accuracy evaluation [53].

(a) Validation accuracy of 10 randomly selected architectures. (b) The Kendall
Tau Rank Correlation Coefficient on 1000 architectures

Figure 2: The performance ranking observation on 1000 randomly sampled
architectures in cell based architecture search space. It is worth noting that
the number of complete epochs for training models is set to 25 according to
NASNet[10] and NSGA-Net[16]. Figure 3: The overall framework of the proposed
MFENAS.

Following the above idea, we propose an accelerated ENAS approach via multi-
fidelity evaluation, named MFENAS, where each individual is evaluated by
training the architecture encoded by each individual for only a small number
of epochs. For balancing evaluation cost and evaluation accuracy, we suggest a
multi-fidelity evaluation combing high-fidelity evaluation and low-fidelity
evaluation, where high-fidelity evaluation indicates individual evaluation
under a large number of training epochs, and low-fidelity evaluation indicates
that under a small number of training epochs. Hence, the multi-fidelity
evaluation can identify potentially promising individuals that cannot survive
from previous generations by integrating multiple evaluations under different
numbers of training epochs.

##  III The Proposed MFENAS

In this section, we first present the overall framework of the proposed
MFENAS. Then, we elaborate the multi-fidelity evaluation in the proposed
MFENAS. Finally, further details in the proposed MFENAS are presented.

###  III-A Overall Framework of MFENAS

To start with, the formal notations used in this paper are listed in Table I.

To simultaneously optimize the accuracy and complexity of neural architecture
in NAS, the proposed MFENAS employs NSGA-II as the optimizer due to its high
competitiveness in solving bi-objective optimization problems [54]. Compared
with existing work on NSGA-II for NAS, the proposed MFENAS is characterized
with two key aspects: a small number of architecture training epochs for
individual evaluation, and a multi-fidelity evaluation for environment
selection at each generation. Specifically, Fig. 3 presents the overall
framework of MFENAS, which mainly consists of six steps.

First, a well-distributed population is initially generated by producing
diverse neural architectures that vary from ResNet-like architectures to
Inception-like ones. Second, the individuals in the generated population are
efficiently evaluated by training the neural architectures encoded by these
individuals for a certain number of epochs, which is initially set to one.
Third, binary tournament selection is applied to the generated population to
mate individuals in the population. Fourth, an offspring population is
produced from the parent population that is generated at last step by
implementing revised single-point crossover and mutation (described in Section
III-C3) in mated individuals of the parent population. Fifth, the individuals
in the offspring population are efficiently evaluated by training the neural
architectures encoded by these individuals for a certain number of epochs,
which will be updated according to the generation and the number of training
epochs. Finally, a multi-fidelity evaluation based selection is used to select
individuals from the union of parent population and offspring population,
where the multi-fidelity evaluation identifies and maintains potentially good
individuals that are eliminated by the environment selection in NSGA-II [38].
The second to the sixth step will repeat until the evolution termination
criteria is satisfied, after which the non-dominated individuals will be
output. For more details, Algorithm 1 presents main steps of the proposed
MFENAS.

TABLE I: Formal Notations Used in This Paper. Notation | Description
---|---
$\mathbf{P}$ ($\mathbf{Q}$) |  a population $\mathbf{P}=\\{\mathbf{P_{1}},\mathbf{P_{2}},\cdots,\\}$ (a offspring population)
$\mathbf{P}^{\prime}$ | a parent population for generating offsprings
$\mathbf{P^{S}}$ ($\mathbf{P^{E}}$) | a population surviving (eliminated) from selection
$\mathbf{E}$ | an archive storing potentially good individuals
$I$ ($\mathbf{P}_{i}$) |  the individual (the $i$-th individual in $\mathbf{P}$) $I=\mathbf{P_{i}}=\\{\mathbf{NC},\mathbf{RC}\\}$
$\mathbf{NC}$ ($\mathbf{RC}$) |  a normal cell (a reduction cell) $\mathbf{NC}(\mathbf{RC})=(\mathbf{n_{0}},\mathbf{n_{1}},\cdots)$
$\mathbf{n_{i}}$ |  the $i$-th node in $\mathbf{NC}(\mathbf{RC})$, $\mathbf{n_{i}}=(\mathbf{L},Op)$
$\mathbf{L}$ | a vector denotes the link information
$Op$ | a number refers to used operation
$Gen$, $Pop$ | maximum number of generations, Population size
$Node_{range}$ | range of the number of nodes in initialization
$MF$ | number of fidelities for multi-fidelity evaluation
$S$ | current number of epoch for training process
$SS_{counter}$ | count of surviving according to one evaluation
$MS_{counter}$ | count of surviving according to multi-fidelity evaluation
$ME_{counter}$ | count of being eliminated according to multi-fidelity evaluation
$H$ |  all previous outputs before node $k$
$H=\\{\widehat{h}[0],\widehat{h}[1],h[0],...,h[k-1]\\}$
$\hat{h}[0]$, $\hat{h}[1]$ | the outputs of two previous cells
$h[k]$, $in_{i}$ |  the output of node $k$, the $i$-the input of a node

1

0: $Gen$: Maximum number of generations; $Pop$: Population size;
$Node_{range}$: Range of the number of nodes in initialization; $MF$: Number
of fidelities for multi-fidelity evaluation;

0: $\mathbf{P}$: Population;

21: $\mathbf{P},\mathbf{E},S\leftarrow
Initialization(Pop,Node_{range}),\emptyset,1$; % Algorithm 3

32: Evaluate individuals in $\mathbf{P}$ by training the architectures encoded
by the individuals for $S$ epoch and compute the fitness by (2);

3: for $g=1$ to $Gen$ do

44: $\mathbf{P}^{\prime}\leftarrow$ Select $Pop$ parents according to the non-
dominated front number and crowding distance of individuals in $\mathbf{P}$;

5 % Mating pool selection

65: $\mathbf{Q}\leftarrow Genetic\ Operator(\mathbf{P}^{\prime})$;

76: Evaluate individuals in $\mathbf{Q}$ by training the architectures encoded
by the individuals for $S$ epoch(s) and compute the fitness by (2);

87: $\mathbf{P},\mathbf{E},S\leftarrow$ $Multi$-$Fidelity\ Evaluation\ Based\
Selection$

9 $(\mathbf{P},\mathbf{Q},\mathbf{E},g,MF,S)$; % Algorithm 2

8: end for

9: return $\mathbf{P}$;

Algorithm 1 Main Steps of MFENAS

###  III-B The Proposed Multi-Fidelity Evaluation

In the proposed MFENAS, it is expected that the evaluation cost of individuals
can be significantly reduced by training the architecture encoded by each
individual for only a small number of epochs, which will greatly accelerate
the entire ENAS process. Nevertheless, the evaluation cost reduction hinders
the architecture training from achieving high accuracy in the individual
evaluation, and thus leads to inappropriate elimination of good individuals in
the environment selection [31, 34, 35]. To address this issue, we propose a
multi-fidelity evaluation based selection for maintaining potentially good
individuals that cannot survive from the current environment selection by
multiple evaluations under different numbers of training epochs for each of
these individuals.

The proposed multi-fidelity evaluation based selection mainly consists of five
steps as shown in Fig. 4. At each generation of ENAS, the environment
selection of NSGA-II is first implemented to select a set of individuals from
parent and offspring populations as mentioned in Section III-A, and to
eliminate the remaining individuals in the two populations. Second, the
potentially good individuals are selected from the eliminated individuals by
multi-fidelity evaluation, which are stored in an archive that includes
previous potentially good individuals and their survival or elimination
information in previous environment selection. Third, the number of training
epochs updates according to the generation and the number of training epochs.
Fourth, the updated number of training epochs is adopted in training
architectures encoded by the individuals in the archive and those surviving in
the environment selection, and thus these individuals continue to be re-
evaluated based on their model parameters obtained from previous training.
Finally, the environment selection in NSGA-II is applied to the re-evaluated
individuals to maintain some good individuals as the parent population at next
generation, while the remaining individuals in the selection will be stored in
the archive.

Figure 4: The main procedure of multi-fidelity evaluation based selection.

Specifically, the detailed steps of the proposed multi-fidelity evaluation
based selection are presented in Algorithm 2. To begin with, the environment
selection of NSGA-II is applied to the union of parent population $\mathbf{P}$
and offspring population $\mathbf{Q}$, where surviving individuals and
eliminated individuals in the selection are denoted as $\mathbf{P^{S}}$ and
$\mathbf{P^{E}}$, respectively (Step 1).

Then a multi-fidelity evaluation is employed to select potentially good
individuals from $\mathbf{P^{E}}$ by making use of individual selection under
different numbers of epochs for training the architectures encoded by the
individuals. To record the individual selection under different numbers of
training epochs, we devise three counters for each individual in $\mathbf{P}$
and $\mathbf{Q}$:

  * •

The $SS_{counter}$ denotes the count of surviving according to one evaluation;

  * •

The $MS_{counter}$ denotes the count of surviving according to multi-fidelity
evaluation;

  * •

The $ME_{counter}$ denotes the count of being eliminated according to multi-
fidelity evaluation.

Based on the environment selection, the $SS_{counter}$ adds one for each
individual in $\mathbf{P^{S}}$, and the $ME_{counter}$ adds one for each
individual in $\mathbf{P^{E}}$ whose $ME_{counter}$ is zero (Step 2).

1

0: $\mathbf{P}$: Population; $\mathbf{Q}$: Offspring; $\mathbf{E}$: Archive;
$g$: Current generation; $MF$: Number of fidelities for multi-fidelity
evaluation; $S$: Current number of training epochs;

0: $\mathbf{P}$: Population; $\mathbf{E}$: Archive;

21: $\mathbf{P^{S}},\mathbf{P^{E}}\leftarrow$ Select $Pop$ individuals from
$\mathbf{P}+\mathbf{Q}$ by the environment selection of NSGA-II;

32: $SS_{counter}$ +1 for individuals in $\mathbf{P^{S}}$,

$ME_{counter}$ +1 for individuals in $\mathbf{P^{E}}$ whose $ME_{counter}$ ==
0;

3: $\mathbf{T}\leftarrow$ Sort the individuals in $\mathbf{E}$ and
$\mathbf{P^{E}}$ using four criteria;

44: $\mathbf{E}\leftarrow$ _Truncated operation_ ($\mathbf{T}$);

5: if $mod(g,\lfloor\frac{Gen}{MF}\rfloor)==0$ and $S\neq MF$ then

6: $S\leftarrow S+1$;

7: Continue training architectures encoded by individuals in
$\mathbf{P^{S}}+\mathbf{E}$ for $S$ epochs to re-evaluate these individuals by
(2);

8: $\mathbf{P},\mathbf{E}\leftarrow$ Select $Pop$ individuals from
$\mathbf{P^{S}}+\mathbf{E}$ by the environment selection of NSGA-II;

59: $MS_{counter}$ +1, $SS_{counter}$ = 0 for individuals in $\mathbf{P}$,

6$MS_{counter}$ +1 for individuals in $\mathbf{E}$ whose $ME_{counter}$ == 0,

$ME_{counter}$ +1 for individuals in $\mathbf{E}$;

10: else

11: $\mathbf{P}\leftarrow\mathbf{P^{S}}$;

712: end if

13: if $g==Gen$ then

14: Continue training architectures encoded by individuals in
$\mathbf{P^{S}}+\mathbf{E}$ for complete epochs to get final validation error
and number of model parameters in (2);

15: $\mathbf{P},\mathbf{E}\leftarrow$ Select $Pop$ individuals from
$\mathbf{P^{S}}+\mathbf{E}$ by the environment selection of NSGA-II;

816: end if

17: return $\mathbf{P}$, $\mathbf{E}$, $S$;

Algorithm 2 Multi-Fidelity Evaluation Based Selection
$(\mathbf{P},\mathbf{E},\mathbf{E}^{\prime},g,MF,S)$

Based on the three counters, four criteria is suggested to sort the
individuals in the union of $\mathbf{E}$ and $\mathbf{P^{E}}$ (Step 3):

$\small\left\\{\begin{aligned} &\ MS_{counter}-ME_{counter}\\\ &\
-(MS_{counter}+ME_{counter})\\\ &\ SS_{counter}\\\ &\ f_{2}(\mathbf{x})\\\
\end{aligned}\right.,$

where the first criteria holds the highest priority and aims to retain the
individuals that frequently survive according to multi-fidelity evaluation,
the second criteria holds the second highest priority and tends to maintain
the individuals that rarely experience evaluations under different fidelities,
the third criteria holds the third highest priority and is prone to keep the
individuals that frequently survive according to one evaluation, and the
fourth criteria holds the fourth highest priority and prefers the individuals
that are encoded from large and complex neural architectures. The individuals
in the union of $\mathbf{E}$ and $\mathbf{P^{E}}$ are sorted according to the
four criteria. Next, a truncated operation is used to select the former
$\mathbf{|E|}$ highest-criterion individuals and store these individuals to
the archive $\mathbf{E}$, where $\mathbf{|E|}$ denotes a predefined size of
$\mathbf{E}$ (Step 4).

To further evaluate the individuals in archive $\mathbf{E}$, we periodically
update the number of training epoch $S$ for the architectures encoded by the
individuals by adding 1 to $S$ for every $\lfloor\frac{Gen}{MF}\rfloor$
generations, where $Gen$ is the maximum number of generations and $MF$ is the
number of fidelities for multi-fidelity evaluation (also denoting the maximum
number of training epochs for each individual evaluation). With the updated
number of training epochs $S$, the individuals in both archive $\mathbf{E}$
and population $\mathbf{P^{S}}$ are re-evaluated by continuing training the
architectures encoded by these individuals for $S$ epochs based on model
parameters obtained from previous training (Step 7).

After the re-evaluation, the environment selection of NSGA-II is applied to
the union of $\mathbf{P^{S}}$ and $\mathbf{E}$ to obtain a surviving
population for a new parent population and an eliminated population stored in
the archive $\mathbf{E}$ at next generation (Step 8). The three counters are
then updated according to environment selection: the $MS_{counter}$ adds one,
the $SS_{counter}$ is set as zero for each individual in $\mathbf{P}$, the
$MS_{counter}$ adds one for the individuals that are stored in archive
$\mathbf{E}$ for the first time, and the $ME_{counter}$ adds 1 for each
individual in archive $\mathbf{E}$ (Step 2).

When it achieves the maximum number of generations, all architectures encoded
by the individuals in the union of $\mathbf{P^{S}}$ and $\mathbf{E}$ continue
to be trained for complete epochs to get their final fitness values in (2)
(Step 14). Based on the fitness values, the environment selection of NSGA-II
is used to acquire a final population consisting of non-dominated individuals
(Step 15).

Note that the number of fidelities for multi-fidelity evaluation $MF$ refers
to how many different types of evaluations in the proposed MFENAS, and one
type of evaluation indicates an individual evaluation under a specific number
of training epochs. For examples, $MF=1$ indicates that only one type of
evaluation is used for each individual, i.e., architecture training for one
epoch. When $MF=3$, it indicates that three types of evaluations can be used
for one individual, i.e., architecture training for one epoch, two epochs and
three epochs. A large value of $MF$ leads to an accurate individual
evaluation, while a small value of $MF$ leads to an efficient individual
evaluation for the proposed MFENAS. Hence, $MF$ plays an important role in
striking a balance between evaluation efficiency and accuracy, which will be
discussed in the experiments of Section IV-D.

###  III-C Related Details

In this section, we give further details of the proposed MFENAS, including
architecture search space, encoding strategy, genetic operator and population
initialization strategy.

####  III-C1 Architecture Search Space for NAS

Network. As illustrated in Fig. 5 (a), the cell based architecture search
space [10] is adopted to build the whole network, which consists of a stack of
several cells including normal cells and reduction cells. Either a normal cell
or a reduction cell regards the outputs of two previous cells as input. All
the normal cells share the same architecture but different weights. Similarly,
all the reduction cells share the same architecture but different weights.

Figure 5: The architecture search space used for the proposed MFENAS.

Cell. Each cell can be defined as a convolutional network mapping two $H\times
W\times F$ tensors (transformed from the two previous cells) to one
$H^{\prime}\times W^{\prime}\times F^{\prime}$ tensor. According to the study
in [55], operations with stride 1 are used for the normal cell, where
$H^{\prime}=H$, $W^{\prime}=W$ and $F^{\prime}=F$. Reduction cell applies
these operations with stride 2, where $H^{\prime}=H/2$, $W^{\prime}=W/2$ and
$F^{\prime}=2F$. As illustrated in Fig. 5 (b), a normal cell or a reduction
cell can be considered as a directed acyclic graph consisting of several
nodes, including two input nodes, one output node, $k$ ($k=6$ in Fig. 5 (b))
computation nodes and one concatenate node (denoted as Concat). For these
nodes, the outputs that are not used will be concatenated together for final
output of one cell.

Node. As shown in Fig. 5 (c), nodes are fundamental components for
constructing cells since links and operation in each node determine the
structure of a cell. There are three types of widely used nodes for existing
NAS approaches as shown in Fig. 6, namely, the node in NASNet search space
[10, 11, 16, 14], the node in one-shot NAS approaches [13, 56, 57, 58] and the
graph based node [15]. To be specific, the node in NASNet (called block) first
applies two operations $Op_{1}$ and $Op_{2}$ to its two input feature maps
$\\{in_{1},in_{2}\\}$ and then merges two obtained outputs via element-wise
addition to get the final output. The node in one-shot NAS approaches
represents a specific tensor and each edge denotes an operation, and all
previous outputs $H=\\{\widehat{h}[0],\widehat{h}[1],h[0],...,h[k-1]\\}$ are
passed to the node $k$ via the operations on edges, where the final output
$h[k]$ is obtained by a weighted element-wise addition. Differently, the graph
based node can flexibly receive $j$ ($j\leq k+2$) previous outputs
$\\{in_{1},in_{2},...,in_{j}\\}$ from $H$. After combining the received
outputs via an element-wise addition, an operation $Op$ is applied to achieve
its final output $h[k]$.

Particularly, the proposed MFENAS adopts the graph based node considering its
superiority in constructing neural architectures over the other two types of
nodes. Compared with the node in NASNet, the graph based node is able to
construct more flexible and diverse neural architectures. Compared with the
node in one-shot approaches, the graph based node can construct neural
architectures that are easier to extend, since adding an extra graph based
node brings much less additional operations and parameters than adding an
extra node in one-shot approaches.

(a) Node (block) in NASNet (b) Node in one-shot Approaches (c) Node in our
approach

Figure 6: The comparison of used nodes in NASNet, one-shot approaches, and our approach. Here $h[k]$ denotes the output of node $k$ and one of its inputs $in_{i}$ is selected from $H=\\{\widehat{h}[0],\widehat{h}[1],h[0],...,h[k-1]\\}$, where $\widehat{h}[0]$ and $\widehat{h}[1]$ are the outputs of two previous cells, and the others are the outputs of all precursor nodes. TABLE II: Predefined Operation Search Space As Used In [14, 10] and Their Encoding. Operation | Short name | Number
---|---|---
Identity mapping | Identity | 0
Convolution with kernel size 1*1 | Conv 1*1 | 1
Convolution with kernel size 3*3 | Conv 3*3 | 2
Convolution with kernel size 1*3 | Conv 1*3+3*1 | 3
and kernel size 3*1
Convolution with kernel size 1*7 | Conv 1*7+7*1 | 4
and kernel size 7*1
Max pooling with kernel size 2*2 | MaxPool 2*2 | 5
Max pooling with kernel size 3*3 | MaxPool 3*3 | 6
Max pooling with kernel size 5*5 | MaxPool 5*5 | 7
Average pooling with kernel size 2*2 | AvgPool 2*2 | 8
Average pooling with kernel size 3*3 | AvgPool 3*3 | 9
Average pooling with kernel size 5*5 | AvgPool 5*5 | 10

####  III-C2 Encoding Strategy

In the proposed MFENAS, a neural architecture is encoded by an individual
$I=\\{\mathbf{NC},\mathbf{RC}\\}$, where two vectors $\mathbf{NC}$ and
$\mathbf{RC}$ represent normal cell and reduction cell, respectively. Each of
the two vectors is composed of some sub-vectors, where each of these sub-
vectors represents a node. Specifically, the $\mathbf{NC}$ and $\mathbf{RC}$
are denoted as follows:

$\small\left\\{\begin{aligned}
\mathbf{NC}=&(\mathbf{n_{0}},\mathbf{n_{1}},\cdots,\mathbf{n_{k}},\cdots,\mathbf{n_{N-1}}),k=0,1,\cdots,\mathbf{N-1}\\\
\mathbf{RC}=&(\mathbf{\tilde{n}_{0}},\mathbf{\tilde{n}_{1}},\cdots,\mathbf{\tilde{n}_{m}},\cdots,\mathbf{\tilde{n}_{R-1}}),m=0,1,\cdots,\mathbf{R-1}\\\
\end{aligned}\right.,$ (3)

where the sub-vector $\mathbf{n_{k}}$ ($\mathbf{\tilde{n}_{m}}$) denotes the
node $k$ (node $m$) in the normal cell $\mathbf{NC}$ (reduction cell
$\mathbf{RC}$), and $\mathbf{N}$ ($\mathbf{R}$) denotes the number of sub-
vectors in $\mathbf{NC}$ ($\mathbf{RC}$). Each sub-vector consists of an
operation in the corresponding node and a set of links for connecting to some
precursor nodes of this node. Specifically, the sub-vector $\mathbf{n_{k}}$
can be denoted as follows:

$\small\left.\begin{aligned}
\mathbf{n_{k}}=&(\mathbf{L},Op)=(\widehat{l}_{0},\widehat{l}_{1},l_{0},l_{1},\cdots,l_{i},\cdots,l_{k-1},Op),\widehat{l}_{0},\widehat{l}_{1}\in\\{0,1\\}\\\
&i=0,1,\cdots,k-1,\ l_{i}\in\\{0,1\\},\ Op\in\\{0,1,\cdots,10\\}\\\
\end{aligned}\right.,$ (4)

where
$\mathbf{L}=(\widehat{l}_{0},\widehat{l}_{1},l_{0},l_{1},\cdots,l_{i},\cdots,l_{k-1})$
is a vector of links in the node $k$, the $\widehat{l}_{0}$
($\widehat{l}_{1}$) indicates whether the node $k$ links to the first (second)
input node, the $l_{i}$ indicates whether the node $k$ links to the node $i$,
and $Op$ denotes the number of a specific operation for the node $k$ according
to Table II.

For better understanding, Fig. 7 gives an illustrative example of the proposed
encoding strategy. As can be seen from Fig. 7, the encoding $\mathbf{NC}$ with
seven sub-vectors represents a normal cell consisting of seven nodes, where
each sub-vector represents a node with specific links and operation. For
example, the node 4 encoded by $(0,1,1,1,0,0,3)$ indicates that the node 4
links to the second input node $\widehat{h}[1]$, the node 0, the node 1, and
adopts the operation Conv 1*3+3*1.

Figure 7: An illustrative example of the proposed encoding strategy.

####  III-C3 Genetic Operator

Based on the suggested architecture search space, we specially design an
effective genetic operator consisting of crossover and mutation for offspring
generation in the proposed MFENAS.

Crossover. The crossover operator consists of two components: the inter-cell
crossover and the intra-cell crossover. The inter-cell crossover is to
exchange normal cells or reduction cells between two parent individuals. For
example, given two parent individuals
$\mathbf{P_{1}}=\\{\mathbf{NC_{1}},\mathbf{RC_{1}}\\}$ and
$\mathbf{P_{2}}=\\{\mathbf{NC_{2}},\mathbf{RC_{2}}\\}$, two offspring
individuals can be obtained by

$\small\left.\begin{aligned}
\mathbf{P_{1}}=\\{\mathbf{NC_{1}},\mathbf{RC_{1}}\\}\\\
\mathbf{P_{2}}=\\{\mathbf{NC_{2}},\mathbf{RC_{2}}\\}\\\
\end{aligned}\right.\Rightarrow\left.\begin{aligned}
\mathbf{Q_{1}}=\\{\mathbf{NC_{1}},\mathbf{RC_{2}}\\}\\\
\mathbf{Q_{2}}=\\{\mathbf{NC_{2}},\mathbf{RC_{1}}\\}\\\ \end{aligned}\right..$
(5)

The intra-cell crossover is to exchange links and operations in normal cells
or reduction cells between two parent individuals. Specifically, the intra-
cell crossover is executed based on a single-point crossover or a revised one-
way crossover. Take the following two normal cells $\mathbf{NC_{1}}$ and
$\mathbf{NC_{2}}$ as an example:

$\small\left\\{\begin{aligned}
\mathbf{NC_{1}}=&(\mathbf{n_{0}^{1}},\mathbf{n_{1}^{1}},\cdots,\mathbf{n_{k}^{1}}=(\widehat{l}_{0}^{1},\widehat{l}_{1}^{1},\cdots,\\\
&l_{i}^{1},\cdots,l_{k-1}^{1},Op^{1}),\cdots,\mathbf{n_{N_{1}-1}^{1}}),\
N_{1}\ \rm{nodes}\\\
\mathbf{NC_{2}}=&(\mathbf{n_{0}^{2}},\mathbf{n_{1}^{2}},\cdots,\mathbf{n_{k}^{2}}=(\widehat{l}_{0}^{2},\widehat{l}_{1}^{2},\cdots,\\\
&l_{i}^{2},\cdots,l_{k-1}^{2},Op^{2}),\cdots,\mathbf{n_{N_{2}-1}^{2}}),\
N_{2}\ \rm{nodes}\\\ \end{aligned}\right.,$ (6)

where the length of $\mathbf{NC_{1}}$ and $\mathbf{NC_{2}}$ are
$\frac{(N_{1}+5)N_{1}}{2}$ and $\frac{(N_{2}+5)N_{2}}{2}$, respectively.
Suppose $N_{1}\leq N_{2}$ and a random integer $RI$ is sampled from 0 to
$\frac{(N_{2}+5)N_{2}}{2}$, then two offspring cells $\mathbf{NC_{1}^{o}}$ and
$\mathbf{NC_{2}^{o}}$ can be generated by a single-point crossover [59]

$\left.\small\begin{aligned} \rm{when}\ RI\leq\
\frac{(N_{1}+5)N_{1}}{2}\Rightarrow\left\\{\begin{aligned}
&\mathbf{NC_{1}}[1:RI]\Leftrightarrow\mathbf{NC_{2}}[1:RI]\\\
&\mathbf{NC_{1}^{o}}\longleftarrow\ \mathbf{NC_{1}}\\\
&\mathbf{NC_{2}^{o}}\longleftarrow\ \mathbf{NC_{2}}\\\
\end{aligned}\right.\end{aligned}\right.$ (7)

or a revised one-way crossover

$\left.\small\begin{aligned} \rm{when}\ \frac{(k+5)k}{2}<RI\leq\
\frac{(k+6)(k+1)}{2}\\\ \Rightarrow\left\\{\begin{aligned} \mathbf{n_{k}^{2\to
1}}\ =\ &(\mathbf{n_{k}^{2}}[1:N_{1}+2],\mathbf{n_{k}^{2}}[end]),\\\ &\
\rm{where}\ N_{1}-1<k\leq N_{2}-1&\\\
\mathbf{NC_{1}^{o}}\longleftarrow&(\mathbf{NC_{1}},\mathbf{n_{k}^{2\to 1}})\\\
\mathbf{NC_{2}^{o}}\longleftarrow&\ \mathbf{NC_{2}}\\\
\end{aligned}\right.\end{aligned}\right.,$ (8)

where $\mathbf{NC_{1}}[1:RI]$ denotes the sub-vector clapped from the first
bit to the $RI$-th bit in $\mathbf{NC_{1}}$, and $\mathbf{n_{k}^{2}}[end]$ is
the last bit of $\mathbf{n_{k}^{2}}$.

The $RI\leq\ \frac{(N_{1}+5)N_{1}}{2}$ in Equation (7) ensures that the
crossover point $RI$ locates in one bit of the shorter parent cell between the
two parent cells. Then $\mathbf{NC_{1}}[1:RI]$ will be exchanged with
$\mathbf{NC_{2}}[1:RI]$ using a single-point crossover.

The $\frac{(k+5)k}{2}<RI\leq\ \frac{(k+6)(k+1)}{2}$ in Equation (8) indicates
that $RI$ locates in the sub-vector denoting node $k$. Then a revised one-way
crossover is designed to identify useful bits in the node $k$ and copy the
identified bits to $\mathbf{NC_{1}}$. As presented in Equation (8), the links
$\mathbf{n_{k}^{2}}[1:N_{1}+2]$ and the operation $\mathbf{n_{k}^{2}}[end]$ in
the node $k$ are identified as useful bits for $\mathbf{NC_{1}}$, and thus are
copied from $\mathbf{NC_{2}}$ to $\mathbf{NC_{1}}$.

Mutation. The mutation operator also consists of two parts: a single-point
mutation and an operator of adding an extra node. Note that the mutation
probability for links and that for operations are different in the single-
point mutation. The operator of adding an extra node to $\mathbf{NC_{1}}$ can
be denoted by

$\small\left\\{\begin{aligned}
&\mathbf{n_{N1}^{mutation}}\longleftarrow\rm{Random}(\mathbf{L},Op)\\\
&\mathbf{NC_{1}}\longleftarrow(\mathbf{NC_{1}},\mathbf{n_{N1}^{mutation}})\\\
\end{aligned}\right.,$ (9)

where $\mathbf{n_{N1}^{mutation}}$ is a new node generated in a random way,
and is then combined with cell $\mathbf{NC_{1}}$ into a new $\mathbf{NC_{1}}$.

####  III-C4 Population Initialization Strategy

1

2

30: $Pop$: Population size; $Node_{range}$: Range of the number of nodes in
the initialization;

40: $\mathbf{P}$: Population;

51: $\mathbf{P}\leftarrow\emptyset$;

2: for $i=1$ to $Pop$ do

3: $prob\leftarrow\frac{i}{Pop}$;

4: $node_{N},node_{R}\leftarrow$ Generate two random numbers from
$Node_{range}$;

65: $\mathbf{NC},\mathbf{RC}\leftarrow$ Generate two zero-vectors with length
$\frac{(node_{N}+5)node_{N}}{2}$ and $\frac{(node_{R}+5)node_{R}}{2}$;

6: Set the last bit of links in each node to 1 with the probability $1-prob$
for both $\mathbf{NC}$ and $\mathbf{RC}$;

7: Set the first two bits of links in each node to 1 with the probability
$prob$ for both $\mathbf{NC}$ and $\mathbf{RC}$;

8: Randomly set other bits to 1 for both $\mathbf{NC}$ and $\mathbf{RC}$

9: Randomly sample one operation from Table II for each node in $\mathbf{NC}$
and $\mathbf{RC}$;

10: Randomly replace operations of $\mathbf{NC}$ by randomly sampled
convolutional-like operations(encoding number from 1 to 4);

11: Randomly replace operations of $\mathbf{RC}$ by randomly sampled pooling-
like operations (encoding number from 5 to 10);

12: $\mathbf{P_{i}}\leftarrow\\{\mathbf{NC},\mathbf{RC}\\}$;

13: $\mathbf{P}\leftarrow\mathbf{P}\cup\mathbf{P_{i}}$;

714: end for

15: return $\mathbf{P}$;

Algorithm 3 Initialization$(Pop,Node_{range})$

The population initialization often has a great influence in convergence and
diversity of EAs [19, 21]. Therefore, we design an effective initialization
strategy for generating diverse architectures varying from ResNet-like
architectures to Inception-like ones. A ResNet-like architecture is
constructed by setting the last bit of links in each node to 1 with a high
probability, while an Inception-like architecture is constructed by setting
the first two bits of links in each node to 1 with a high probability. Hence,
it is intuitive to generate diverse architectures by controlling the
probability of setting some bits of individuals to 1.

Specifically, Algorithm 3 presents the detailed procedure of the
initialization strategy in the proposed MFENAS, where there is no
hyperparameter except for $Node_{range}$ controlling the range of generated
models. First, the probability of setting the first two bits to 1 is
determined for initial individuals, which ranges from $\frac{1}{Pop}$ to
$\frac{Pop}{Pop}$ for diversity. Then, two numbers $node_{N}$, $node_{R}$ are
randomly generated in a predefined range, by which the length of $\mathbf{NC}$
and that of $\mathbf{RC}$ are set to $\frac{(node_{N}+5)node_{N}}{2}$ and
$\frac{(node_{R}+5)node_{R}}{2}$, respectively. Two vectors $\mathbf{NC}$ and
$\mathbf{RC}$ are then generated by setting each bit to 0 based on their
length. Next, the last bit of links in each node for both $\mathbf{NC}$ and
$\mathbf{RC}$ can be set to 1 with a probability $1-prob$, whereas the first
two bits of links in each node for both $\mathbf{NC}$ and $\mathbf{RC}$ can be
set to 1 with a probability $prob$. The higher the probability $prob$, the
closer the decoding of the individual is to the Inception-like architecture.
The lower the probability $prob$, the closer the decoding of the individual is
to the ResNet-like architecture. Other bits of links in each node for both
$\mathbf{NC}$ and $\mathbf{RC}$ are randomly set to 1 or 0. The operations of
nodes in $\mathbf{NC}$ and $\mathbf{RC}$ are randomly sampled from number 0 to
number 10. Afterward, operations of $\mathbf{NC}$ and $\mathbf{RC}$ are
randomly replaced by sampled operations in convolution operations (from number
1 to number 4) and pooling operations (from number 5 to number 10),
respectively. The normal cells $\mathbf{NC}$ after the replacement tend to
equip with more convolution operations than those without the replacement,
while the reduction cells $\mathbf{RC}$ after the replacement tend to equip
with more pooling operations than those without the replacement. Finally, the
generated individual $\mathbf{P_{i}}$ will be added to population
$\mathbf{P}$.

##  IV Empirical Studies

In this section, we first validate the effectiveness of the proposed MFENAS.
Then, we demonstrate the superiority of the proposed MFENAS by comparing it to
22 state-of-the-art NAS approaches. Finally, we discuss the population
initialization and architecture search space that are suggested in the
proposed MFENAS.

###  IV-A Experiment Settings

####  IV-A1 Benchmark Datasets

As suggested in most existing ENAS works[10, 16, 17, 11], we conduct search
process of the proposed MFENAS on CIFAR-10 dataset and evaluate the best
architecture obtained by the proposed MFENAS on CIFAR-10, CIFAR-100 [27] and
ILSVRC 2012 ImageNet [60].

CIFAR-10 is a 10-class natural image dataset consisting of 50,000 training
images and 10,000 testing images, where the size of each color image is
$32\times 32$. CIFAR-100 is a dataset which is the same to CIFAR-10 except for
that CIFAR-100 has 100 classes. All images are whitened with the channel mean
subtracted and the channel standard deviation divided. All training images in
both search and training process are dealt with the following standard
augmentation: randomly crop $32\times 32$ patches from upsampled images of
size 40x40 and apply random horizontal flips at a probability of 0.5. Besides,
the cutout augmentation [61] is used for only the training process. Compared
to CIFAR-10 and CIFAR-100, the ImageNet is a more challenging classification
dataset which consists of various resolution images unevenly distributed in
1000 classes. Furthermore, there are 1.28 million images for the training set
and 50,000 images for the validation set in the ImageNet. According to
previous work on NAS, the input image size is set to $224\times 224$ [10, 14,
11]. Besides, we also utilize some commonly used augmentation techniques,
i.e., the random resize and crop, the random horizontal flip and the color
jitter.

####  IV-A2 Peer Competitors

In order to demonstrate the effectiveness and efficiency of the proposed
MFENAS, various state-of-the-art approaches are selected as peer competitors
to compare with MFENAS. The selected competitors can be roughly divided into
three different types [34]. The first type of competitors is the CNN
architectures manually designed, which contains Wide ResNet [62], DenseNet
[6], Inception-v1 [7], MobileNet [63] and ShuffleNet [64]. The second type of
competitors comprises various non-EA based NAS approaches, including the
reinforcement learning (RL) based approaches: NASNet [10], MetaQNN [65],
Block-QNN-S [66], EAS [67], E-NAS [11], and the gradient based approaches:
DARTS [13], NAO [14]. The third type of competitors refers to ENAS approaches,
including AmoebaNet [25], Large-scale Evolution [23], Hierarchical Evolution
[24], Genetic-CNN [22], NSGA-Net [16], CNN-GA [17], AE-CNN [26], E2EPP [31],
SI-ENAS [34] and CARS-E [36].

Moreover, we also employ another competitor MFENAS(baseline), which is the
MFENAS without multi-fidelity evaluation. In MFENAS(baseline), complete epochs
are adopted for neural architecture training.

####  IV-A3 Search Details

Dataset Details. According to suggestions in [10, 14, 17], the search process
is executed on CIFAR-10 dataset, where the original training set is divided
into a new training set and validation set (90%-10%).

Architecture Details. As suggested in [10, 16, 14], all generated
architectures are set to totally hold 5 ($N=1$) cells, and the number of
filters (channels) in each node is set to 16. The neural architectures will be
trained for 25 complete epochs ($S=25$) by the standard SGD optimizer with
momentum, where the learning rate, the momentum rate and the batch size are
set to 0.1, 0.9 and 128, respectively. In addition, a single period cosine
decay and L2 weight decay $3\times 10^{-4}$ are also utilized.

MFENAS Settings. We adopt the following setting for MFENAS(baseline) and
MFENAS: population size $Pop=20$, maximum generation $Gen=25$, range of the
number of nodes in initialization $Node_{range}=[5,12]$. The number of
fidelities for multi-fidelity evaluation $MF$ in MFENAS is set to 6 to obtain
a better trade-off between the performance and efficiency. The search process
of MFENAS(baseline) and MFENAS is executed on one NVIDIA 2080TI GPU.

####  IV-A4 Training Details

After obtaining Pareto optimal individuals, some promising individuals will be
selected to extend the architectures encoded by the individuals and train them
on CIFAR-10, CIFAR-100 and ImageNet. Here all training settings follow the
previous NAS approaches [10, 16, 14, 12].

CIFAR-10 and CIFAR-100. The architecture is set to hold 20 ($N=6$) cells in
total, and the numbers of channels are different in different individuals,
which are set to approximate 3 million architecture parameters based on
existing neural architectures [16]. When training the obtained architecture
for 600 epochs by a standard SGD optimizer with momentum, the following
settings are used: learning rate 0.025, momentum rate 0.9, batch size 128,
auxiliary classifier located at $\frac{2}{3}$ of the maximum depth weighted by
0.4, L2 weight decay $5\times 10^{-4}$, a single period cosine decay and
dropout of 0.4 in the final softmax layer. Besides, each path will be dropped
with a probability 0.2 for regularization introduced in [10].

ImageNet. $N$ is set to 4 to make the architecture hold 14 cells, where the
architecture will be trained for 250 epochs by the standard SGD optimizer with
the momentum rate that is set to 0.9. Similarly, a weight decay of $3\times
10^{-5}$ and an auxiliary classifier located at $\frac{2}{3}$ of the maximum
depth weighted by 0.4 are also used. The batch size is set to 512, the
learning rate is initially set to 0.1 and later decays by a factor of 0.97 in
each epoch.

The training process on both CIFAR-10 and CIFAR-100 is executed on one Tesla
P100 GPU, while the training process on ImageNet is executed two Tesla P100
GPUs. The source code of proposed MFENAS is available at
https://github.com/DevilYangS/MFENAS/.

###  IV-B Effectiveness of Multi-Fidelity Evaluation

TABLE III: The Performance Comparison of the Best Architecture Found by
MFENAS(Baseline) and MFENAS Validated on CIFAR-10, CIFAR-100 and ImageNet
Dataset, Respectively. Note that Test Error of ImageNet Refers to Error Rates
on Its Validation Dataset.

Dataset | Test | Parameters | Search
---|---|---|---
Error (%) | (M) | Cost
MFENAS(baseline) | CIFAR-10 | 2.30 | 2.87 | 2.55
CIFAR-100 | 16.18 | 2.89
ImageNet | 26.16 | 5.79
MFENAS | CIFAR-10 | 2.39 | 2.94 | 0.6
CIFAR-100 | 16.42 | 2.97
ImageNet | 26.06 | 5.98

  * •

“M” is short for “million” in “Parameters (M)”.

In this section, we will validate the effectiveness of multi-fidelity
evaluation in the proposed MFENAS . First, we verify the performance of the
best architecture obtained by MFENAS and MFENAS(baseline) on CIFAR-10,
CIFAR-100 and ImageNet. Table III summarizes comparison results between
MFENAS(baseline) and MFENAS in terms of test error rate, number of model
parameters and search cost. As can be seen from Table III, the search cost of
the proposed MFENAS is significantly less than that of MFENAS(baseline), which
takes only about $1/4$ search cost of MFENAS(baseline). Moreover, the
architecture found by the proposed MFENAS achieves a similar error rate to
that found by MFENAS(baseline) on each of the three datasets. Particularly,
the architecture obtained by the proposed MFENAS has a lower error rate than
that obtained by MFENAS(baseline) on the validation dataset ImageNet. This
validates that the multi-fidelity evaluation is capable of accelerating ENAS
while maintaining high architecture quality. To intuitively verify the final
architecture quality obtained by the proposed MFENAS, Fig. 8 presents the
validation error rate and the number of parameters in the architectures
achieved by the proposed MFENAS and MFENAS(baseline). It can be observed from
Fig. 8 that the proposed MFENAS finds high-quality architectures that are
similar to MFENAS(baseline) in terms of both architecture accuracy and model
complexity.

TABLE IV: The Comparison between The Proposed MFENAS and Existing Peer
Competitors in Terms of Test Error Rate and Search Cost on The CIFAR-10
Dataset.

Peer Competitors | Test Error (%) | Parameters (M) | Search Cost (GPU days) | Search Method
---|---|---|---|---
Wide ResNet | 4.17 | 36.5 | - | Manual
DenseNet-BC | 3.46 | 25.6 | - | Manual
NASNet-A | 2.65 | 3.3 | 2000 | RL
Block-QNN-S | 4.38 | 6.1 | 96 | RL
MetaQNN | 6.92 | 11.2 | 80 | RL
EAS | 4.23 | 23.4 | 10 | RL
E-NAS | 2.89 | 4.6 | 0.5 | RL+weight sharing
DARTS(first order) | 3.00 | 3.3 | 1.5 | Gradient based
DARTS(second order) | 2.76 | 3.3 | 4 | Gradient based
NAO | 3.18 | 10.6 | 200 | Gradient based
NAO+WS | 3.53 | 2.5 | 0.3 | Gradient based+weight sharing
AmoebaNet-A | 3.34 | 3.2 | 3150 | Evolution
Large-Scale Evolution | 5.40 | 5.4 | 2750 | Evolution
Hierarchical Evolution | 3.63 | 15.7 | 300 | Evolution
Genetic-CNN | 7.10 | - | 17 | Evolution
NSGA-Net | 2.75 | 3.3 | 4 | Evolution
CNN-GA | 4.78 | 2.9 | 35 | Evolution
AE-CNN | 4.30 | 2.0 | 27 | Evolution
E2EPP | 5.30 | - | 8.5 | Evolution
SI-ENAS | 4.07 | - | 1.8 | Evolution
CARS-E | 2.86 | 3.0 | 0.4 | Evolution+weight sharing
MFENAS | 2.39 | 2.94 | 0.6 | Evolution

  * •

’-’ represents that the corresponding result is not publicly available.

Figure 8: The validation error rate and the number of parameters in the
architectures achieved by the proposed MFENAS and MFENAS(baseline).

For a deeper insight into the multi-fidelity evaluation, we investigate the
effect of the number of fidelities $MF$ in the multi-fidelity evaluation by
recording reduction ratio of search cost and Kendall’s $\tau$ value at
different values of $MF$ ranging from 1 to 12, which is shown in Fig. 9. It is
seen from Fig. 9 that the reduction ratio of search cost decreases with the
increase of $MF$, indicating that the number of fidelities is effective in
controlling the search cost of the proposed MFENAS. The Kendall’s $\tau$ value
increases with the increase of $MF$, verifying that the number of fidelities
has an influence on the effectiveness of the proposed MFENAS. Therefore, we
set $MF$ to 6 for balancing the efficiency and effectiveness of the proposed
MFENAS, since $MF=6$ is the best trade-off between the reduction ratio of
search cost and Kendall’s $\tau$ value. It is also noteworthy that setting
$MF$ to 6 leads to over 0.7 Kendall’s $\tau$ value, which is better than the
Kendall’s $\tau$ value 0.66 achieved by the best known surrogate based ENAS
approach [31]. This reveals that the multi-fidelity evaluation is able to
balance effectiveness and efficiency of ENAS by tuning the number of
fidelities, which is attributed to the fact that the multi-fidelity evaluation
realizes a trade-off between evaluation cost and evaluation accuracy in NAS.

To summarize, the multi-fidelity evaluation is effective in accelerating ENAS
and maintaining high architecture quality for solving NAS.

Figure 9: Reduction ratio of search cost and Kendall’s $\tau$ with different
numbers of fidelities for multi-fidelity evaluation $MF$.

###  IV-C Competitiveness of the Proposed MFENAS

TABLE V: The Comparison between The Proposed MFENAS and Existing Peer
Competitors in Terms of Test Error Rate and Search Cost on The CIFAR-100
Dataset.

Peer | Test | Parameters | Search Cost | Search
---|---|---|---|---
Competitors | Error (%) | (M) | (GPU days) | Method
Wide ResNet | 20.50 | 36.5 | - | Manual
DenseNet-BC | 17.18 | 25.6 | - | Manual
NASNet-A | 16.58 | 3.3 | 2000 | RL
Block-QNN-S | 20.65 | 6.1 | 96 | RL
MetaQNN | 27.14 | 11.2 | 80 | RL
E-NAS | 17.27 | 4.6 | 0.5 | RL+weight sharing
NAO | 15.67 | 10.8 | 200 | Gradient based
AmoebaNet-B | 15.80 | 3.2 | 3150 | Evolution
Large-Scale Evolution | 23.00 | 40.4 | 2750 | Evolution
Genetic-CNN | 29.03 | - | 17 | Evolution
NSGA-Net | 20.74 | 3.3 | 8 | Evolution
CNN-GA | 20.53 | 4.1 | 40 | Evolution
AE-CNN | 20.85 | 5.4 | 36 | Evolution
E2EPP | 22.02 | - | 8.5 | Evolution
SI-ENAS | 18.64 | - | 1.8 | Evolution
MFENAS | 16.42 | 2.97 | 0.6 | Evolution

  * •

Note that only 15 peer competitors are adopted for comparison on CIFAR-100
since the architecture quality achieved by the remaining 7 peer competitors on
CIFAR-100 is not publicly available.

In this section, we discuss the competitiveness of the proposed MFENAS by
comparing it with 22 state-of-the-art NAS approaches. Tables IV, V and VI
present the architecture error rate, the number of parameters and the search
cost achieved by the proposed MFENAS and existing peer competitors on
CIFAR-10, CIFAR-100 and ImageNet.

As presented in Table IV, the architecture found by the proposed MFENAS holds
a 2.39% test error rate on CIFAR-10 dataset, which is better than test error
rates achieved by all the existing peer competitors including manual designed
architectures, non-EA based NAS approaches and ENAS approaches. For the search
cost, the proposed MFENAS takes only 0.6 GPU days to achieve the architecture
with 2.39% test error rate on CIFAR-10 dataset, which is faster than 18 peer
competitors but slower than 3 weight sharing-based NAS approaches.
Nevertheless, the search cost of the proposed MFENAS is very approximate to
that of 3 weight sharing-based NAS approaches, which is only $0.3$ GPU days
larger than the fastest weight sharing-based approach. The proposed MFENAS
outperforms 18 peer competitors and is competitive to 3 weight sharing-based
NAS approaches in terms of architecture performance and search cost. Hence,
the proposed MFENAS is overall superior over or competitive to state-of-the-
art NAS approaches in terms of effectiveness and efficiency on CIFAR-10.

To further investigate competitiveness of the proposed MFENAS, we transfer the
best architecture found by MFENAS from CIFAR-10 with 10 classes to CIFAR-100
with 100 classes. Table V presents the comparison results between the proposed
MFNEAS and existing peer competitors on CIFAR-100. As can be observed from
Table V, the transferred architecture of the proposed MFENAS achieves a 16.42%
test error rate on CIFAR-100, which performs better than 13 peer competitors
but worse than 2 peer competitors (i.e., NAO and AmoebaNet-B). The reason may
lie in the fact that NAO and AmoebaNet-B hold more model parameters than the
proposed MFENAS. However, the search cost of the proposed MFENAS is
significantly lower than that of NAO and AmoebaNet-B on CIFAR-100, indicating
that the proposed MFENAS is competitive to NAO and AmoebaNet-B when
considering both architecture performance and search cost. Furthermore, the
search cost of the proposed MFENAS is lower than 14 peer competitors but
higher than one competitor E-NAS. The proposed MFENAS still can be regarded as
competitive to E-NAS due to its superiority over E-NAS in terms of
architecture performance. Therefore, the proposed MFENAS overall has better or
competitive performance compared to state-of-the-art NAS approaches in terms
of effectiveness and efficiency on CIFAR-100.

TABLE VI: The Comparison between The Proposed MFENAS and Existing Peer
Competitors in Terms of Error Rate and Search Cost on The ImageNet Dataset.

Peer | Error (%) | Params | Search Cost | Search
---|---|---|---|---
Competitors | Top-1 | Top-5 | (M) | (GPU days) | Method
Inception-v1 | 30.20 | 10.10 | 6.6 | - | Manual
MobileNet | 29.40 | 10.50 | 4.2 | - | Manual
ShuffleNet (v1) | 29.10 | 10.20 |  5 | - | Manual
NASNet-A | 26.00 | 8.4 | 5.3 | 2000 | RL
NASNet-B | 27.2 | 8.7 | 5.3 | 2000 | RL
NASNet-C | 27.5 | 9 | 4.9 | 2000 | RL
DARTS | 26.70 | 8.70 | 4.7 | 4 | Gradient based
NAO | 25.70 | 8.20 | 11.4 | 200 | Gradient based
AmoebaNet-A | 25.50 | 8.00 | 5.1 | 3150 | Evolution
AmoebaNet-B | 26.00 | 8.50 | 5.3 | 3150 | Evolution
AmoebaNet-C | 24.30 | 7.60 | 6.4 | 3150 | Evolution
Genetic-CNN | 27.87 | 9.74 | 156.0 | 17 | Evolution
CARS-E | 26.30 | 8.40 | 4.4 | 0.4 | Evolution+
weight sharing
MFENAS | 26.06 | 8.18 | 5.98 | 0.6 | Evolution

  * •

Note that the table only compares the peer competitors whose architecture
quality is publicly available.

In addition to CIFAR-10 and CIFAR-100, we also evaluate the performance of the
proposed MFENAS on a more challenging dataset ImageNet, which holds much more
classes, much larger image size and much more images compared to CIFAR-10 and
CIFAR-100. Table VI provides the comparison results between the proposed
MFENAS and peer competitors on ImageNet, where the best architecture obtained
by the proposed MFENAS is transferred from CIFAR-10 to ImageNet. It can be
seen from Table VI that the transferred architecture of the proposed MFENAS
holds a 26.06% error rate, which is lower than 8 peer competitors but higher
than NASNet-A, NAO and AmoebaNet. Nevertheless, it can still be drawn from
Table VI that the proposed MFENAS is competitive to NASNet-A, NAO and
AmoebaNet on ImageNet, since the search cost of the proposed MFENAS is
significantly lower than that of NASNet-A, NAO and AmoebaNet. More
specifically, the search cost of the proposed MFENAS is lower than all the
competitors on ImageNet. Consequently, the performance of the proposed MFENAS
overall is better than or competitive to state-of-the-art peer competitors in
terms of effectiveness and efficiency on ImageNet.

For summary, the proposed MFENAS is demonstrated to be superior over or
competitive to state-of-the-art NAS approaches in terms of effectiveness and
efficiency.

(a) The initial populations obtained by random initialization and the proposed
population initialization strategy. (b) Convergence profiles of HV obtained by
random initialization and the proposed population initialization strategy.

Figure 10: Comparison between random initialization and the proposed
population initialization under the MFENAS(baseline) framework.

###  IV-D Discussions on Details of the Proposed MFENAS

In this section, we first verify the effectiveness of the population
initialization strategy suggested for the proposed MFENAS. Then we analyze the
efficacy of the architecture search space suggested in the proposed MFENAS.

Fig. 10 presents the initial populations and the convergence profiles of
hypervolume (HV) obtained by random initialization and the proposed population
initialization under the MFENAS(baseline) framework, where HV measures
convergence and diversity of a population and a large HV value indicates a
good convergence and diversity [68]. Note that the MFENAS(baseline) is adopted
as the framework to eliminate the effect of multi-fidelity evaluation in
performance of the two initialization strategies. As can be observed from Fig.
10, the suggested population initialization generates an initial population
with better diversity and thus leads to better convergence in MFENAS(baseline)
compared to random initialization. Therefore, the suggested initialization
strategy is effective in strengthening performance of the proposed MFENAS by
generating diverse architectures in initialization of MFENAS.

TABLE VII: Effectiveness Validation of Architecture Search Space by Comparing MFENAS(baseline) and NSGA-Net on CIFAR-10 and CIFAR-100 datasets. Dataset | Test | Parameters
---|---|---
Error (%) | (M)
CIFAR-10 | NSGA-Net | 2.75 | 3.3
MFENAS(baseline) | 2.30 | 2.87
CIFAR-100 | NSGA-Net | 20.74 | 3.3
MFENAS(baseline) | 16.18 | 2.89

(a) Normal cell found by MFENAS(baseline). (b) Reduction cell found by
MFENAS(baseline)

(c) Normal cell found by MFENAS. (d) Reduction cell found by MFENAS

Figure 11: The best architecture obtained by MFENAS(baseline) and MFENAS.

To investigate the effect of the suggested architecture search space in the
proposed MFENAS, Table VII compares the best architecture found by
MFENAS(baseline) with that found by NSGA-Net, which is a fair comparison since
the two approaches have the same number of sampled architectures.
MFENAS(baseline) shares the same architecture search space with the proposed
MFENAS as suggested in III-C1, while NSGA-Net utilizes the NASNet search
space. It can be seen from Table VII that MFENAS(baseline) can find a higher-
quality architecture than NSGA-Net. Specifically, Fig. 11 presents the best
architecture obtained by the proposed MFENAS and that obtained by
MFENAS(baseline). The two architectures obtained by the proposed MFENAS and
MFENAS(baseline) are quite different from each other under the suggested
search space, while under NASNet search space the best architecture obtained
by different NAS approaches are often similar to each other [55]. As a result,
the suggested search space facilitates NAS approaches in generating more
diverse and flexible architectures than NASNet search space for solving NAS
problems.

##  V Conclusions and Future Work

In this paper, we have developed an accelerated ENAS approach via multi-
fidelity evaluation named MFENAS, to achieve high-quality neural architectures
at a low computational cost in NAS. Empirical results on CIFAR-10 have shown
that the architecture found by the proposed MFENAS achieves a 2.39% test error
rate at the cost of only 0.6 GPU days on one NVIDIA 2080TI GPU. Compared with
22 state-of-the-art NAS approaches, the proposed MFENAS has exhibited superior
performance in terms of both computational cost and architecture quality on
CIFAR-10. The architecture transferred to CIFAR-100 and ImageNet has also
shown competitive performance to the architectures obtained by existing NAS
approaches.

In this paper, the proposed MFENAS mainly concentrates on efficiently finding
high-quality architectures, where the vulnerability of architectures is not
considered. The vulnerability of architectures plays an important role in
defensing adversarial attack [69]. Hence, in the future we would like to
develop new ENAS approaches to find robust architectures against various
adversarial attacks. Moreover, the binary neural network is characterized with
a low memory saving and a low inference latency [70], but few NAS studies have
been reported on searching for binary neural architectures. Therefore, it is
also interesting to design new ENAS approaches for searching high-quality
binary neural architectures.

## References

  * [1] M. Niepert, M. Ahmed, and K. Kutzkov, “Learning convolutional neural networks for graphs,” in _Proceedings of the 2016 International Conference on Machine Learning_ , 2016, pp. 2014–2023.
  * [2] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in _Proceedings of the 2016 European Conference on Computer Vision_. Springer, 2016, pp. 21–37.
  * [3] O. Abdel-Hamid, A.-r. Mohamed, H. Jiang, L. Deng, G. Penn, and D. Yu, “Convolutional neural networks for speech recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 22, no. 10, pp. 1533–1545, 2014.
  * [4] T. Young, D. Hazarika, S. Poria, and E. Cambria, “Recent trends in deep learning based natural language processing [review article],” _IEEE Computational Intelligence Magazine_ , vol. 13, no. 3, pp. 55–75, 2018.
  * [5] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 770–778.
  * [6] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in _Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 4700–4708.
  * [7] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 1–9.
  * [8] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 2818–2826.
  * [9] B. Zoph and Q. V. Le, “Neural architecture search with reinforcement learning,” _arXiv preprint arXiv:1611.01578_ , 2016.
  * [10] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learning transferable architectures for scalable image recognition,” in _Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8697–8710.
  * [11] H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean, “Efficient neural architecture search via parameters sharing,” in _Proceedings of the 2018 International Conference on Machine Learning_ , 2018, pp. 4095–4104.
  * [12] Y. Chen, G. Meng, Q. Zhang, S. Xiang, C. Huang, L. Mu, and X. Wang, “Renas: Reinforced evolutionary neural architecture search,” in _Proceedings of the 2019 IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4787–4796.
  * [13] H. Liu, K. Simonyan, and Y. Yang, “Darts: Differentiable architecture search,” in _Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * [14] R. Luo, F. Tian, T. Qin, E. Chen, and T.-Y. Liu, “Neural architecture optimization,” in _Proceedings of the 2018 Advances in Neural Information Processing Systems_ , 2018, pp. 7816–7827.
  * [15] K. Kandasamy, W. Neiswanger, J. Schneider, B. Poczos, and E. P. Xing, “Neural architecture search with bayesian optimisation and optimal transport,” in _Proceedings of the 2018 Advances in Neural Information Processing Systems_ , 2018, pp. 2016–2025.
  * [16] Z. Lu, I. Whalen, V. Boddeti, Y. Dhebar, K. Deb, E. Goodman, and W. Banzhaf, “Nsga-net: neural architecture search using multi-objective genetic algorithm,” in _Proceedings of the 2019 Genetic and Evolutionary Computation Conference_ , 2019, pp. 419–427.
  * [17] Y. Sun, B. Xue, M. Zhang, G. G. Yen, and J. Lv, “Automatically designing cnn architectures using the genetic algorithm for image classification,” _IEEE Transactions on Cybernetics_ , 2020.
  * [18] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” _Computers & Operations Research_, vol. 31, no. 12, pp. 1985–2002, 2004.
  * [19] Y. Tian, S. Yang, and X. Zhang, “An evolutionary multiobjective optimization based fuzzy method for overlapping community detection,” _IEEE Transactions on Fuzzy Systems_ , 2019.
  * [20] X. Xiang, Y. Tian, J. Xiao, and X. Zhang, “A clustering-based surrogate-assisted multiobjective evolutionary algorithm for shelter location problem under uncertainty of road networks,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 12, pp. 7544–7555, 2020.
  * [21] L. Zhang, S. Yang, X. Wu, F. Cheng, Y. Xie, and Z. Lin, “An indexed set representation based multi-objective evolutionary approach for mining diversified top-k high utility patterns,” _Engineering Applications of Artificial Intelligence_ , vol. 77, pp. 9–20, 2019.
  * [22] L. Xie and A. Yuille, “Genetic cnn,” in _Proceedings of the 2017 IEEE International Conference on Computer Vision_ , 2017, pp. 1379–1388.
  * [23] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin, “Large-scale evolution of image classifiers,” in _Proceedings of the 2017 International Conference on Machine Learning_ , 2017, pp. 2902–2911.
  * [24] H. Liu, K. Simonyan, O. Vinyals, C. Fernando, and K. Kavukcuoglu, “Hierarchical representations for efficient architecture search,” in _Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * [25] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, “Regularized evolution for image classifier architecture search,” in _Proceedings of the 2019 AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 4780–4789.
  * [26] Y. Sun, B. Xue, M. Zhang, and G. G. Yen, “Completely automated cnn architecture design based on blocks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 4, pp. 1242–1254, 2019.
  * [27] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” 2009.
  * [28] K. Swersky, J. Snoek, and R. P. Adams, “Freeze-thaw bayesian optimization,” _arXiv preprint arXiv:1406.3896_ , 2014.
  * [29] B. Baker, O. Gupta, R. Raskar, and N. Naik, “Accelerating neural architecture search using performance prediction,” _arXiv preprint arXiv:1705.10823_ , 2017.
  * [30] B. Deng, J. Yan, and D. Lin, “Peephole: Predicting network performance before training,” _arXiv preprint arXiv:1712.03351_ , 2017.
  * [31] Y. Sun, H. Wang, B. Xue, Y. Jin, G. G. Yen, and M. Zhang, “Surrogate-assisted evolutionary deep learning using an end-to-end random forest-based performance predictor,” _IEEE Transactions on Evolutionary Computation_ , vol. 24, no. 2, pp. 350–364, 2019.
  * [32] Y. Sun, B. Xue, M. Zhang, and G. G. Yen, “A particle swarm optimization-based flexible convolutional autoencoder for image classification,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 30, no. 8, pp. 2295–2309, 2018.
  * [33] F. Assunção, N. Lourenço, P. Machado, and B. Ribeiro, “Fast denser: Efficient deep neuroevolution,” in _Proceedings of the 2019 European Conference on Genetic Programming_. Springer, 2019, pp. 197–212.
  * [34] H. Zhang, Y. Jin, R. Cheng, and K. Hao, “Sampled training and node inheritance for fast evolutionary neural architecture search,” _arXiv preprint arXiv:2003.11613_ , 2020.
  * [35] P. Liu, M. D. El Basha, Y. Li, Y. Xiao, P. C. Sanelli, and R. Fang, “Deep evolutionary networks with expedited genetic algorithms for medical image denoising,” _Medical Image Analysis_ , vol. 54, pp. 306–315, 2019.
  * [36] Z. Yang, Y. Wang, X. Chen, B. Shi, C. Xu, C. Xu, Q. Tian, and C. Xu, “Cars: Continuous evolution for efficient neural architecture search,” in _Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 1829–1838.
  * [37] H. Wang, Y. Jin, and J. Doherty, “A generic test suite for evolutionary multifidelity optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 22, no. 6, pp. 836–850, 2017.
  * [38] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” _IEEE Transactions on Evolutionary Computation_ , vol. 6, no. 2, pp. 182–197, 2002.
  * [39] T. Elsken, J. H. Metzen, and F. Hutter, “Efficient multi-objective neural architecture search via lamarckian evolution,” in _Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * [40] M. Laumanns and J. Ocenasek, “Bayesian optimization algorithms for multi-objective optimization,” in _Proceedings of the 2002 International Conference on Parallel Problem Solving from Nature_. Springer, 2002, pp. 298–307.
  * [41] S. Bandyopadhyay, S. Saha, U. Maulik, and K. Deb, “A simulated annealing-based multiobjective optimization algorithm: Amosa,” _IEEE Transactions on Evolutionary Computation_ , vol. 12, no. 3, pp. 269–283, 2008.
  * [42] J. Pacheco and R. Martí, “Tabu search for a multi-objective routing problem,” _Journal of the Operational Research Society_ , vol. 57, no. 1, pp. 29–37, 2006.
  * [43] C. C. Coello, “Evolutionary multi-objective optimization: a historical view of the field,” _IEEE Computational Intelligence Magazine_ , vol. 1, no. 1, pp. 28–36, 2006.
  * [44] H. Zhang, Q. Zhang, L. Ma, Z. Zhang, and Y. Liu, “A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows,” _Information Sciences_ , vol. 490, pp. 166–190, 2019\.
  * [45] M. Suganuma, M. Kobayashi, S. Shirakawa, and T. Nagao, “Evolution of deep convolutional neural networks using cartesian genetic programming,” _Evolutionary Computation_ , vol. 28, no. 1, pp. 141–163, 2020.
  * [46] F. Assunção, J. Correia, R. Conceição, M. J. M. Pimenta, B. Tomé, N. Lourenço, and P. Machado, “Automatic design of artificial neural networks for gamma-ray detection,” _IEEE Access_ , vol. 7, pp. 110 531–110 540, 2019.
  * [47] D. R. So, C. Liang, and Q. V. Le, “The evolved transformer,” _arXiv preprint arXiv:1901.11117_ , 2019.
  * [48] Y. Liu, Y. Sun, B. Xue, M. Zhang, and G. Yen, “A survey on evolutionary neural architecture search,” _arXiv preprint arXiv:2008.10937_ , 2020.
  * [49] Z. Fan, J. Wei, G. Zhu, J. Mo, and W. Li, “Evolutionary neural architecture search for retinal vessel segmentation,” _arXiv_ , pp. arXiv–2001, 2020\.
  * [50] F. M. Johner and J. Wassner, “Efficient evolutionary architecture search for cnn optimization on gtsrb,” in _Proceedings of the 2019 (18th) IEEE International Conference On Machine Learning And Applications (ICMLA)_. IEEE, 2019, pp. 56–61.
  * [51] H. Zhang, S. Kiranyaz, and M. Gabbouj, “Finding better topologies for deep convolutional neural networks by evolution,” _arXiv preprint arXiv:1809.03242_ , 2018.
  * [52] Sen and P. Kumar, “Estimates of the regression coefficient based on kendall’s tau,” _Publications of the American Statal Association_ , vol. 63, no. 324, pp. 1379–1389, 1968.
  * [53] J. Ren, A. S. Thelen, A. Amrit, X. Du, L. T. Leifsson, Y. Tesfahunegn, and S. Koziel, “Application of multifidelity optimization techniques to benchmark aerodynamic design problems,” in _Proceedings of the 2016 (54th) AIAA Aerospace Sciences Meeting_ , 2016, p. 1542.
  * [54] G. B. Lamont, _Evolutionary Algorithms for Solving Multi-Objective Problems_. Evolutionary Algorithms for Solving Multi-Objective Problems, 2007.
  * [55] T. Elsken, J. H. Metzen, and F. Hutter, “Neural architecture search: A survey,” _Journal of Machine Learning Research_ , vol. 20, pp. 1–21, 2019\.
  * [56] A. Brock, T. Lim, J. M. Ritchie, and N. J. Weston, “Smash: One-shot model architecture search through hypernetworks,” in _Proceedings of the 6th International Conference on Learning Representations_ , 2018.
  * [57] S. Xie, H. Zheng, C. Liu, and L. Lin, “Snas: stochastic neural architecture search,” in _Proceedings of the 2018 International Conference on Learning Representations_ , 2018.
  * [58] X. Dong and Y. Yang, “One-shot neural architecture search via self-evaluated template network,” in _Proceedings of the 2019 IEEE International Conference on Computer Vision_ , 2019, pp. 3681–3690.
  * [59] Y. Tian, X. Zhang, C. Wang, and Y. Jin, “An evolutionary algorithm for large-scale sparse multi-objective optimization problems,” _IEEE Transactions on Evolutionary Computation_ , 2019.
  * [60] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition_. Ieee, 2009, pp. 248–255.
  * [61] T. DeVries and G. W. Taylor, “Improved regularization of convolutional neural networks with cutout,” _arXiv preprint arXiv:1708.04552_ , 2017.
  * [62] S. Zagoruyko and N. Komodakis, “Wide residual networks,” _arXiv preprint arXiv:1605.07146_ , 2016.
  * [63] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” _arXiv preprint arXiv:1704.04861_ , 2017.
  * [64] X. Zhang, X. Zhou, M. Lin, and J. Sun, “Shufflenet: An extremely efficient convolutional neural network for mobile devices,” in _Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6848–6856.
  * [65] B. Baker, O. Gupta, N. Naik, and R. Raskar, “Designing neural network architectures using reinforcement learning,” _arXiv preprint arXiv:1611.02167_ , 2016.
  * [66] Z. Zhong, J. Yan, W. Wu, J. Shao, and C.-L. Liu, “Practical block-wise neural network architecture generation,” in _Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 2423–2432.
  * [67] H. Cai, T. Chen, W. Zhang, Y. Yu, and J. Wang, “Efficient architecture search by network transformation,” in _Proceedings of the 2018 AAAI_ , 2018.
  * [68] L. While, P. Hingston, L. Barone, and S. Huband, “A faster algorithm for calculating hypervolume,” _IEEE Transactions on Evolutionary Computation_ , vol. 10, no. 1, pp. 29–38, 2006.
  * [69] N. Akhtar and A. Mian, “Threat of adversarial attacks on deep learning in computer vision: A survey,” _IEEE Access_ , vol. 6, pp. 14 410–14 430, 2018.
  * [70] K. P. Singh, D. Kim, and J. Choi, “Learning architectures for binary networks,” _arXiv preprint arXiv:2002.06963_ , 2020.