As Figure LABEL:fig:pipeline_details shows, model generation is divided into
two parts: search space and optimization methods. The search space defines the
model structures that can be designed and optimized in principle. The types of
model can be broadly divided into two categories: one is traditional ML
models, such as support-vector machine (SVM), k-nearest neighbors (KNN), and
decision tree, and the other is deep neural networks (DNNs). In terms of
optimization methods, it can also be categorized into two groups: hyper-
parameters that are used for training, like the learning rate and batch size,
and those used for model design, such as the number of neighbors for KNN or
the number of layers for DNN. In this section, we focus more on Neural
Architecture Search (NAS), which has got recently much attention. We refer the
readers who are interested in traditional model (e.g., SVM) to other reviews
[takeout_automl_survey, automl_benchmark].

Figure 1: An overview of NAS pipeline.

Figure 1 presents an overview of NAS pipeline, which is categorized into the
following three dimensions [nas_survey, nas_eval]: search space, architecture
optimization (AO) method111It may also be referred to as the ”search strategy
[nas_survey, nas_eval]”, ”search policy [eval_nas_phase]”, or ”optimization
method [a_nas_survey, takeout_automl_survey]”., and model estimation method.
To make the follow-up content easier to understand, we explain three concepts
as below.

  * •

Search Space. The search space defines the design principles of neural
architectures. Different scenarios require different search spaces. We
summarize four commonly used search space, including entire-structured, cell-
based, hierarchical, and morphism-based search space.

  * •

Architecture Optimization Method. The AO method defines how to guide the
search to efficiently find the model architecture with high performance after
the search space is defined.

  * •

Model Estimation Method. Once a model is generated, its performance needs to
be evaluated. The simplest way is to train the model to convergence on the
training set, and then do the evaluation on the validation set, whereas such
method is time-consuming and resource-intensive. Some advanced methods maybe
accelerate the process of estimation but loss fidelity. Thus, how to balance
efficiency and effectiveness of evaluation is a problem worth studying.

The search space and architecture optimization method are presented in this
section, while the methods of model estimation are included in the next
section.

##  0.1 Search Space

The neural architecture can be represented as a direct acyclic graph (DAG)
[enas, a_nas_survey], which is formed by ordered nodes $Z$ and by edges
connecting pairs of nodes, where each node indicates a tensor $z$ and each
edge represent an operation $o$ selected from a set of candidate operations
$O$. The in-degree of each node varies from the design of search space. Due to
the limitation of computational resources, a maximum threshold $N$ is manually
set for in-degree. Here, we give the formula for the computation at a node $k$
under the assumption that the index for nodes starts from 1:

Figure 2: Two simplified examples of the entire-structured neural
architectures. Each layer is specified with different operation, such as
convolution and max-pooling operations. The edge indicates the flow of
information. The skip-connection operation used in the right example can help
explore more deeper and complex neural architectures.

$z^{(k)}=\sum_{i=1}^{N}o^{(i)}(z^{(i)}),\,\,o^{(i)}\in O$ (1)

The set of candidate operations $O$ mainly includes the primitive operation
such as convolution, pooling, activation functions, skip connection,
concatenation, and addition. Besides, to further enhance the performance of
the model, many NAS methods use some advanced human-designed modules as the
primitive operations, such as depth-wise separable convolution
[chollet2017xception], dilated convolution[dilated_conv], and Squeeze-and-
Excitation (SE) Block [senet]. How to select and combine these operations
varies from the design search space. In other words, the search space defines
the structural paradigm that architecture optimization algorithms can explore,
thus designing a good search space is a promising but challenging problem. In
general, a good search space is expected to exclude human bias and be flexible
enough to cover a wider variety of model architectures. Based on the existing
NAS works, we detail the commonly used search spaces as follows.

###  0.1.1 Entire-structured Search Space

The space of entire-structured neural networks [nas_rl_zoph16, enas] is one of
the most intuitive and straightforward search space. Figure 2 presents two
simplified examples of the entire-structured models, which are built by
stacking a predefined number of nodes, where each node represents a layer and
has a specified operation. The simplest structure is the left model in Figure
2, while the right model is relatively complex, as it permits arbitrary skip
connections [resnet] to exist between the ordered nodes, and these connections
have been proven effective in practice [nas_rl_zoph16]. Although the entire
structure is easy to implement, it has several disadvantages. For example, it
is widely accepted that the deeper the model, the better the generalization
ability, but searching for such a deep network is onerous and computationally
expensive. Furthermore, the generated architecture lacks transferability:
i.e., a model generated on a small dataset may not fit a larger dataset, which
necessitates the generation of a new model for a larger dataset.

###  0.1.2 Cell-Based Search Space

Figure 3: (Left) An example of a cell-based model consisting of three motifs,
each with $n$ normal cells and one reduction cell. (Right) An example of
normal cell, which contains two blocks, each has two nodes. Each node is
specified with different operations and inputs, respectively.

Motivation. To enable the transferability of the generated model, many works
[nasnet_zoph17, blockqnn, enas] propose the cell-based search space, in which
the neural architecture is composed of a fixed number of repeating cell
structures. This design approach is based on the observation that many well-
performing human-designed models [resnet, densenet] are also built by stacking
a fixed number of modules. For example, The family of ResNet builds many
variants, such as ResNet50, ResNet101, and ResNet152, by stacking more
BottleNeck modules [resnet]. Throughout the literature, this repeated module
has been referred to as motif, cell, or block, while in this paper, we call it
cell.

Design. Figure 3 (left) presents an example of a final cell-based neural
network, which consists of two types of cells, namely normal and reduction
cell. Thus, the problem of searching for a full neural architecture is
simplified into searching for an optimal cell structure in the context of
cell-based search space. Besides, the output of the normal cell retains the
same spatial dimension as the input, and the number of normal cell repeats is
usually set manually based on the actual demand. The reduction cell follows
behind a normal cell and has a similar structure to the normal cell, but the
difference is that the width and height of output feature maps of the
reduction cell is half the input, and the number of channels is twice the
number of input. This design approach follows the common practice of manually
designing neural networks. Unlike the entire-structured search space, the
model built on cell-based search space can be expanded to form a larger model
by simply adding more cells, without re-searching for the cell structure. Many
approaches [darts_liu18, enas, nasnet_zoph17] also experimentally demonstrate
the transferability of the model generated in cell-based search space, as the
model built on the CIFAR-10 can also achieve comparable results to SOTA human-
designed models on the ImageNet.

The design paradigm of the internal cell structure of most works refers to
Zoph et al. [nasnet_zoph17], which is one of the first to propose an
exploration of cell-based search space. Figure 3 (right) shows an example of
the normal cell structure. Each cell contains $B$ blocks (here $B=2$), and
each block has two nodes. One can see that each node in the block can be
assigned different operations and can receive different inputs. The output of
two nodes in the block can be combined by addition or concatenation operation;
therefore, each block can be represented by a five-element tuple, i.e.,
$(I_{1},I_{2},O_{1},O_{2},C)$, where $I_{1},I_{2}\in\mathcal{I}_{b}$ indicates
the inputs to the block, $O_{1},O_{2}\in\mathcal{O}$ specifies the operations
applied to inputs, and $C\in\mathcal{C}$ describes how to combine $O_{1}$ and
$O_{2}$. As the blocks are ordered, the set of candidate inputs $I_{b}$ for
nodes in block $b_{k}$ contains the output of the previous two cells and the
set of the outputs of all previous blocks $\\{b_{i},i<k\\}$ of the same cell.
The first two inputs of the first cell of the whole model are set to the image
data by default.

In the actual implementation, there are essential details to be noted. First,
the number of channels may be different for different inputs. A commonly used
solution is to apply a calibration operation on each node’s input tensor to
ensure that all inputs have the same number of channels. The calibration
operation usually uses $1\times 1$ convolution filters such that it will not
change the size of the input tensor. Second, as mentioned above, the input of
a node in a block can come from the previous two cells or the previous blocks
within the same cell; hence, the cell’s output must have the same spatial
resolution. To this end, if input/output resolutions are different, the
calibration operation has stride 2, otherwise 1. Besides, all the blocks have
stride 1.

Complexity. Searching for a cell structure is more efficient than searching
for an entire structure. To illustrate this, supposing that there are $M$
predefined candidate operations, the number of layers for both the entire and
the cell-based structure is $L$, and the number of blocks in a cell is $B$.
Then, the number of possible entire structures is

$N_{entire}=M^{L}\times 2^{\frac{L\times(L-1)}{2}}$ (2)

The number of possible cells is $(M^{B}\times(B+2)!)^{2}$. However, there are
two types of cells (i.e., the normal cell and the reduction cell), so the
final size of the cell-based search space is

$N_{cell}=(M^{B}\times(B+2)!)^{4}$ (3)

Obviously, the complexity of searching for the entire structure grows
exponentially with the number of layers. For an intuitive comparison, we set
the values for the variables in the Equation 2 and 3 the typical value in the
literature, i.e. $M=5,L=10,B=3$, then $N_{entire}=3.44\times 10^{20}$ is much
larger than $N_{cell}=5.06\times 10^{16}$.

Two-stage Gap. Notably, the NAS methods of cell-based search space usually
consist of two phases: search and estimation. Specifically, the best-
performing model in the search phase is firstly selected, and then in the
estimation phase, this model is trained from scratch or fine-tuned. However,
there exists a large gap in the model depth between the two phases. As Figure
4 (left) shows, for DARTS [darts_liu18], the generated model in the search
phase only consists of 8 cells for reducing the consumption of GPU memory,
while in the estimation phase, the number of cells is extended to 20. Although
the search phase finds the best cell structure for the shallow model, it does
not mean that it is still suitable for the deeper model in the evaluation
phase. In other words, simply adding more cells may harm the model
performance. To bridge this gap, Chen et al. [pdarts] propose an improved
method based on DARTS, namely Progressive DARTS (P-DARTS), which divides the
search phase into multiple stages and increases the depth of the searched
networks gradually at the end of each stage, hence bridging the gap between
search and evaluation. However, increasing the number of cells in the search
phase may bring an issue of heavier computational overheads. Thus, for
reducing computational consumption, P-DARTS gradually reduces the number of
candidate operations from 5 to 3 and 2 via search space approximation methods,
shown in Figure 4. Experimentally, P-DARTS obtains a 2.50% error rate on the
CIFAR-10 test dataset, outperforming the 2.83% error rate of DARTS.

Figure 4: Difference between DARTS [darts_liu18] and P-DARTS [pdarts]. Both
methods search and evaluate networks on the CIFAR-10 dataset. As the number of
cell structures increases from 5 to 11 and 17, the number of candidate
operations is gradually reduced accordingly.

###  0.1.3 Hierarchical Search Space

[Network-level architecture used in Conv-Deconv.] [Network-level architecture
used in stacked hourglass networks. ]

Figure 5: The network-level search space (the figure is adopted
from[auto_deeplab]). Three gray nodes at the beginning indicate the fixed
“stem” structures, and each blue point is a cell structure, as described
above. The black arrows along the blue points indicate the final selected
network-level structure.

The cell-based search space enables the transferability of the generated
model, and most of the cell-based methods [enas, nasnet_zoph17, metaqnn,
blockqnn, large_scale_evolve, amoebanet] follow a two-level hierarchy: the
inner is the cell level, which selects the operation and connection for each
node in the cell, and the outer is the network level, which controls the
spatial-resolution changes. However, those approaches focus on the cell level
and ignore the network level. As shown in Figure 3, whenever a fixed number of
normal cells are stacked, the spatial dimension of feature maps is halved by
adding a reduction cell. To jointly learn a good combination of repeatable
cell and network structures, Liu et al. [auto_deeplab] define a general
formulation for a network-level structure, depicted in Figure 5, from which
many existing good network designs can be reproduced. In this way, we can
fully explore the different number of channels and the size of feature maps of
each layer in the network.

[The level-one primitive operations are assembled into level-two cells.] [The
level-two cells are viewed as primitive operations and assembled into level-
three cells.]

Figure 6: An example of a three-level hierarchical architecture
representation. The figure is adopted from [liu_hierarchical_2018].

In terms of cell-level, the number of blocks ($B$) in a cell is still manually
predefined and is fixed in the search stage. In other words, $B$ is a new
hyper-parameter that requires tuning by human input. To address this problem,
Liu et al. [liu_hierarchical_2018] propose a novel hierarchical genetic
representation scheme, namely HierNAS, in which the higher-level cell is
generated by iteratively incorporating lower-level cells. As shown in Figure
6, the level-one cells can be some primitive operations, such as $1\times 1$
and $3\times 3$ convolution and $3\times 3$ max-pooling. The level-one cells
are the basic components of the level-two cells. Then, the level-two cells are
used as the primitive operations to generate the level-three cells. The
highest-level cell is a single motif corresponding to the full architecture.
Besides, a higher-level cell is defined by a learnable adjacency upper-
triangular matrix $G$, where $G_{ij}=k$ means that the $k$-th operation
$0_{k}$ is implemented between nodes $i$ and $j$. For example, the level-two
cell in Figure 6(a) is defined by a matrix $G$, where
$G_{01}=2,G_{02}=1,G_{12}=0$ (the index starts from 0). This method can
discover more types of cell structures with more complex and flexible
topologies. Similarly, Liu and Zoph et al. [pnas_liu18] also propose
Progressive NAS (PNAS) to search for the cell progressively, starting from the
simplest cell structure that is composed of only one block, and then expanding
to a higher-level cell by adding more possible block structures. Moreover,
PNAS improves the search efficiency by using a surrogate model to predict the
top-k promising blocks from the search space at each stage of cell
construction.

For both HierNAS and PNAS, once a cell structure is searched, it is used in
all layers of the network, which limits the layer diversity. Besides, many
searched cell structures are complex and fragmented, which is critical for
achieving both high accuracy and lower latency [mnasnet, fbnet]. To ease both
problems, Tan et al. [mnasnet] propose MnasNet, which uses novel factorized
hierarchical search space to generate different cell structures, namely
MBConv, for different layers of the final network. Figure 7 presents the
factorized hierarchical search space of MnasNet. The network consists of a
predefined number of cell structures. Each cell has a different structure and
contains a variable number of blocks, where each block has the same structure
in the same cell but differs from the blocks in other cells. Since a good
balance can be achieved between model performance and latency, many subsequent
works [fbnet, proxylessnas] also refer to this design method. Notably, due to
the large computational consumption, most of the differentiable NAS (DNAS)
works (e.g., DARTS) firstly search for a good cell structure on a proxy
dataset (e.g., CIFAR10), then transfer it to the larger target dataset (e.g.,
ImageNet). Han et al. [proxylessnas] propose ProxylessNAS that can directly
search for neural networks on the targeted dataset and hardware platforms by
using BinaryConnect [binaryconnect], which addresses the high memory
consumption issue.

Figure 7: The factorized hierarchical search space in MnasNet [mnasnet]. The
final network consists of different cells. The cell is composed of a variable
number of repeated blocks, where the block in the same cell shares the same
structure, but differs from the block in other cells.

###  0.1.4 Morphism-Based Search Space

Isaac Newton is reputed to have said that “If I have seen further, it is by
standing on the shoulders of giants.” Similarly, several training tricks have
been proposed, such as knowledge distillation [knowledgedistill] and transfer
learning [transferlearning]. However, these methods do not directly modify the
model structure. To this end, Chen et al. [chen2015net2net] propose the
Net2Net technique to design new neural networks based on the existing network
by inserting the identity morphism (IdMorph) transformations between neural
network layers. IdMorph transformation is function-preserving and has two
types: depth and width IdMorph, which makes it possible to replace the
original model with an equivalent model that is deeper or wider.

However, IdMorph is limited to width and depth changes, and can only modify
width and depth separately, and the sparsity of its identity layer can create
problems [resnet]. Therefore, an improved method is proposed, namely network
morphism [network_morphism_wei16], which allows a child network to inherit all
of the knowledge from its well-trained parent network, and continue to grow
into a more robust network in a shortened training time. Specifically,
compared with Net2Net, network morphism has the following advantages: 1) it
can embed non-identity layers and handle arbitrary non-linear activation
functions; 2) it can simultaneously perform depth, width, and kernel size-
morphing in a single operation, whereas Net2Net can only separately consider
depth and width changes. Experimental results show that network morphism can
significantly accelerate the training process, as it uses one-fifteenth of the
training time and achieves better results than the original VGG16.

Figure 8: Net2DeeperNet and Net2WiderNet transformations in [chen2015net2net].
”IdMorph” indicates identity morphism operation.

Several subsequent research works [lemonade, autokeras, modularized_morph,
eff_net_transform, nas_nn_mmar19, path_level_nm, fast_nm, Morphnet] are based
on network morphism. For instance, Jin et al. [autokeras] propose a framework
that enables Bayesian optimization to guide the network morphism for an
efficient neural architecture search. Wei et al [modularized_morph] further
improve network morphism at a higher level, i.e., by morphing a convolutional
layer into an arbitrary module of a neural network. Additionally, Tan and Le
[efficientnet] propose EfficientNet, which re-examines the effect of model
scaling for convolutional neural networks and proves that carefully balancing
network depth, width, and resolution can lead to better performance.

##  0.2 Architecture Optimization

After defining the search space, we need to search for the best-performing
architecture, a process we call architecture optimization (AO). Traditionally,
the architecture of a neural network is regarded as a set of static hyper-
parameters that are tuned based on the performance observed on the validation
set. However, this process highly depends on human experts and requires a lot
of time and resources for trial and error. Therefore, many AO methods are
proposed to free humans from this tedious procedure and to search for novel
architectures automatically. We detail the commonly used AO methods in the
following.

###  0.2.1 Evolutionary Algorithm

The evolutionary algorithm (EA) is a generic population-based metaheuristic
optimization algorithm that takes inspiration from biological evolution.
Compared with traditional optimization algorithms such as exhaustive methods,
an evolutionary algorithm is a mature global optimization method with high
robustness and broad applicability. It can effectively deal with the complex
problems that traditional optimization algorithms struggle to solve without
being limited by the problem’s nature.

Encoding Scheme. Different EAs may use different types of encoding schemes for
network representation. There are two types of encoding schemes: direct and
indirect. Direct encoding is a widely used method that explicitly specifies
the phenotype. For example, Genetic CNN [genertic_cnn] encodes the network
structure into a fixed-length binary string, e.g., $1$ indicates that two
nodes are connected, and vice versa. Although binary encoding can be performed
easily, its computational space is square of the number of nodes, and the
number of nodes is fixed-length, i.e., predefined manually. To represent
variable-length neural networks, the encoding of direct acyclic graph (DAG)
becomes a promising solution [cgp_suganuma17, large_scale_evolve,
liu_hierarchical_2018]. For example, Suganuma et al. [cgp_suganuma17] use
Cartesian genetic programming (CGP) [cgp_2, cgp_1] encoding scheme to
represent the neural network, built by a list of sub-modules that are defined
as DAG. Similarly, in [large_scale_evolve], the neural architecture is also
encoded as a graph, where vertices indicate rank-3 tensors or activations
(with batch normalization performed with rectified linear units (ReLUs) or
plain linear units), and edges indicate identity connections or convolutions.
NeuroEvolution of Augmenting Topologies (NEAT) [stanley_evolving_2002,
large_scale_evolve] also uses a direct encoding scheme, where every node and
every connection are stored. Indirect encoding specifies a generation rule to
build the network and allows for a more compact representation. Cellular
encoding (CE) [Gruau1993Cellular] is an example of a system that utilizes
indirect encoding of network structures. CE encodes a family of neural
networks into a set of labeled trees and is based on a simple graph grammar.
Recently, some studies [fernando2016convolution, kim2015deep,
pugh2013evolving, lemonade] describe the use of indirect encoding schemes to
represent the network. For example, the network in [lemonade] is encoded by
function, and each network can be modified using function-preserving network
morphism operators. Hence the capacity of the child network is increased and
is guaranteed to perform at least as good as the parent networks.

Figure 9: The overview of evolutionary algorithm.

Four Steps. A typical evolutionary algorithm consists of the following steps:
selection, crossover, mutation, and update (see Figure 9):

  * •

Selection: This step involves selecting a portion of the networks from all the
generated networks for the crossover, which aims to maintain well-performing
neural architectures while eliminating weak ones. There are three strategies
for selecting networks. The first is fitness selection, in which the
probability of a network being selected is proportional to its fitness value,
i.e., $P(h_{i})=\frac{Fitness(h_{i})}{\sum_{j=1}^{N}Fitness(h_{j})}$, where
$h_{i}$ indicates the $i$-th network. The second is rank selection, which is
similar to fitness selection, but with a network’s selection probability being
proportional to its relative fitness rather than its absolute fitness. The
third method is tournament selection [large_scale_evolve, lemonade, amoebanet,
liu_hierarchical_2018]. In each iteration, $k$ (tournament size) networks are
randomly selected from the population and sorted according to their
performance; then the best network is selected with a probability of $p$, the
second-best network has a probability of $p\times(1-p)$, and so on.

  * •

Crossover After selection, every two networks are selected to generate a new
offspring network, inheriting half of the genetic information of each of its
parents. This process is analogous to the genetic recombination that occurs
during biological reproduction and crossover. The particular manner of
crossover varies and depends on the encoding scheme. In binary encoding,
networks are encoded as a linear string of bits, where each bit represents a
unit, such that two parent networks can be combined via one-point or multiple-
point crossover. However, the crossover of data arranged in such a fashion can
sometimes lead to data damage. Thus Xie et al. [genertic_cnn] denote the basic
unit in the crossover as a stage rather a bit, where a stage is a higher-level
structure constructed by a binary string. For cellular encoding, a randomly
selected sub-tree is cut from one parent tree to replace a sub-tree cut from
the other parent tree. In another approach, NEAT performs an artificial
synapsis based on historical markings, allowing NEAT to add a new structure
without losing track of which gene is throughout a simulation.

  * •

Mutation As the genetic information of the parents is copied and inherited by
the next generation, gene mutation also occurs. A point mutation
[cgp_suganuma17, genertic_cnn] is one of the most widely used operations, and
consists of randomly and independently flipping each bit. Two types of
mutations are described in [evolve_dnn]: one enables or disables a connection
between two layers, and the other adds or removes skip connections between two
nodes or layers. In another approach, Real and Moore et al.
[large_scale_evolve] predefine a set of mutation operators, such as those that
alter the learning rate and filter size and remove skin connections between
nodes. By analogy with the biological process, although a mutation may look
like a mistake that causes damage to the network structure and leads to a loss
of functionality, the mutation also enables exploration of more novel
structures and ensures diversity.

  * •

Update Many new networks are generated by completing the above steps, and in
light of limitations on computational resources, some of these must be
removed. In [large_scale_evolve], the worst-performing network of two randomly
selected networks is immediately removed from the population. Alternatively,
in [amoebanet], the oldest networks are removed. Other methods [evolve_dnn,
genertic_cnn, cgp_suganuma17] discard all models at regular intervals.
However, Liu et al. [liu_hierarchical_2018] do not remove any networks from
the population; instead, they allow the network to grow with time. EENA [eena]
regulates the population number via a variable $\lambda$, i.e., removing the
worst model with probability $\lambda$ and the oldest one with $1-\lambda$.

###  0.2.2 Reinforcement Learning

Figure 10: An overview of NAS using reinforcement learning.

Zoph et al. [nas_rl_zoph16] were one of the first to apply reinforcement
learning (RL) for neural architecture search. Figure 10 presents an overview
of an RL-based NAS algorithm. The agent is usually a recurrent neural network
(RNN) that executes an action $A_{t}$ at each step $t$ to sample a new
architecture from the search space and receives an observation of the state
$S_{t}$ together with a reward scalar $R_{t}$ from the environment to update
the agent’s sampling strategy. Environment refers to the use of standard
neural network training procedure to train and evaluate the network generated
by the agent, after which the corresponding results (such as accuracy) are
returned. Many follow-up approaches [metaqnn, nasnet_zoph17, blockqnn, enas]
use this framework, but with different agent policies and neural-architecture
encoding. Zoph et al. [nas_rl_zoph16] first use the policy gradient algorithm
[policygradient] to train the agent, and sequentially sample a string to
encode the entire neural architecture. In subsequent work [nasnet_zoph17],
they use the Proximal Policy Optimization (PPO) algorithm [ppo] to update the
agent, and propose the method shown in Figure 11 to build the cell-based
neural architecture. MetaQNN [metaqnn] proposes a meta-modeling algorithm
using Q-learning and a $\epsilon$-greedy exploration strategy and experience
replay to search neural architectures sequentially.

Figure 11: An example of an agent generating a cell structure. Each block in
the cell consists of two nodes that are specified with different operations
and inputs. The index $-2$ and $-1$ indicates the input comes from prev-
previous and previous cell, respectively.

Although the above RL-based algorithms have achieved SOTA results on CIFAR-10
and Penn Treebank (PTB) [ptb] datasets, they spend much time and computational
resources. For instance, [nas_rl_zoph16] took 28 days and 800 K40 GPUs to
search for the best-performing architecture, and MetaQNN [metaqnn] also took
ten days and 10 GPUs to complete its search, which is unaffordable for
individual researchers, and even for some companies. To this end, some
improved RL-based algorithms are discussed. BlockQNN [blockqnn] proposes a
distributed asynchronous framework and an early-stop strategy to complete
searching on only one GPU within 20 hours. The efficient neural architecture
search (ENAS) [enas] is even better, as it adopts a parameter-sharing
strategy, in which all of the child architectures are regarded as sub-graph of
a super-net; this enables these architectures to share parameters, obviating
the need to train each child model from scratch. As a result, ENAS took only
approximately 10 hours using one GPU to search for the best architecture on
the CIFAR-10 dataset, which is nearly 1000$\times$ faster than
[nas_rl_zoph16].

###  0.2.3 Gradient Descent

The search strategies above sample neural architectures from a discrete search
space. A pioneering algorithm, namely DARTS [darts_liu18], propose to search
for neural architectures over the continuous and differentiable search space
by using a softmax function to relax the discrete space, as outlined below:

$\overline{o}_{i,j}(x)=\sum_{k=0}^{K}\frac{\exp\left(\alpha^{k}_{i,j}\right)}{\sum_{l=0}^{K}\exp\left(\alpha^{l}_{i,j}\right)}o^{k}(x)$
(4)

where $o(x)$ indicates the operation performed on input $x$,
$\alpha^{k}_{i,j}$ indicates the weight for the operation $o^{k}$ between a
pair of nodes ($i,j$), and $K$ is the number of predefined candidate
operations. After the relaxation, the task of searching for architectures is
transformed into a joint optimization of neural architecture $\alpha$ and the
weights of this neural architecture $\theta$. These two types of parameters
are optimized in an alternative way, suggestive of a bilevel optimization
problem. Specifically, $\alpha$ and $\theta$ are optimized with the validation
and the training set, respectively. The training and the validation loss are
denoted by $\mathcal{L}_{train}$ and $\mathcal{L}_{val}$, respectively. Hence,
the total loss function can be derived:

$\begin{array}[]{cl}{\min_{\alpha}}&{\mathcal{L}_{val}\left(\theta^{*},\alpha\right)}\\\
{\text{s.t.}}&{\theta^{*}=\operatorname{argmin}_{\theta}\,\mathcal{L}_{train}(\theta,\alpha)}\end{array}$
(5)

Figure 12: An overview of DARTS (the figure is adopted from [darts_liu18]).
(a) The data can only flow from lower-level nodes to higher-level nodes, and
the operations on edges are initially unknown. (b) The initial operation on
each edge is a mixture of candidate operations, each having equal weight. (c)
The weight of each operation is learnable and ranges from 0 to 1, but for
previous discrete sampling methods, the weight can only be 0 or 1. (d) The
final neural architecture is constructed by preserving the maximum weight-
value operation on each edge.

Figure 12 presents an overview of DARTS, where the cell is composed of $N$
(here $N=4$) ordered nodes, and the node $z^{k}$ ($k$ starts from 0) is
connected to the node $z^{i},i\in\\{k+1,...,N\\}$. The operation on each edge
$e_{i,j}$ is initially a mixture of candidate operations, each being of equal
weight. Therefore, the neural architecture $\alpha$ is a super-net, which
contains all possible child neural architectures. At the end of the search,
the final architecture is derived only by retaining the maximum-weight
operation for all mixed operations.

Although DARTS greatly reduces the search time, it has several problems.
Firstly, as Eq. 5 shows, DARTS describes jointly optimization of the neural
architecture and the weights as a bilevel optimization problem. However, this
problem is difficult to solve directly, because both architecture $\alpha$ and
weights $\theta$ are high dimensional parameters. Single-level optimization is
another solution and is formalized as:

$\min_{\theta,\alpha}\mathcal{L}_{\mathrm{train}}(\theta,\alpha)$ (6)

which optimizes both neural architecture and weights together. Although the
single-level optimization problem can efficiently solved as the regular
training, the searched architecture $\alpha$ commonly overfits on the training
set and its performance on the validation set may not be guaranteed. In
[MiLeNAS], the authors propose mixed-level optimization:

$\min_{\alpha,\theta}\,\,\left[\mathcal{L}_{train}\left(\theta^{*},\alpha\right)+\lambda\mathcal{L}_{val}\left(\theta^{*},\alpha\right)\right]$
(7)

where $\alpha$ indicates the neural architecture, $\theta$ is the weights of
this neural architecture, and $\lambda$ is a non-negative regularization
variable that the weight of the training loss and validation loss.
Specifically, when $\lambda=0$, Eq. 7 degrades to the single-level
optimization (Eq. 6); while if $\lambda$ is close to infinity, then Eq. 7
becomes a bilevel optimization (Eq. 5). The experimental results in [MiLeNAS]
show that mixed-level optimization not only overcomes the overfitting issue of
single-level optimization, but also avoids the gradient error of bilevel
optimization.

Secondly, in DARTS, the output of each edge is the weighted sum of all
candidate operation (shown in Eq. 4) during the whole search stage, which
leads to a linear increase of the requirements of GPU memory with the number
of candidate operations. To reduce resource consumption, many subsequent
studies [gdas, snas, MiLeNAS, wu2018mixed, fbnet] develop a differentiable
sampler to sample a child architecture from the super-net by using a
reparameterization trick, namely Gumbel Softmax [gumbel_softmax].
Specifically, the neural architecture is fully factorized and modeled with a
concrete distribution [concrete_dist], which provides an efficient way to
sample a child architecture and allows gradient back-propagation. Therefore,
Eq. 4 is re-formulated as Eq. 8:

$\overline{o}^{k}_{i,j}(x)=\sum_{k=0}^{K}\frac{\exp\left(\left(\log{\alpha}_{i,j}^{k}+{G}_{i,j}^{k}\right)/\tau\right)}{\sum_{l=0}^{K}\exp\left(\left(\log{\alpha}_{i,j}^{l}+{G}_{i,j}^{l}\right)/\tau\right)}o^{k}(x)$
(8)

where ${G}_{i,j}^{k}=-log(-log(u_{i,j}^{k}))$ is the $k$-th Gumbel sample,
$u_{i,j}^{k}$ is a uniform random variable, and $\tau$ is the softmax
temperature. When $\tau\rightarrow\infty$, the possibility distribution of all
operations between each pair of nodes approximates to the one-hot
distribution. In GDAS [gdas], only the operation with the maximum possibility
for each edge is selected during the forward pass, while the gradient is back-
propagated according to Eq. 8. In other words, only one path of the super-net
is selected for training, thereby reducing GPU memory usage. On the other
hand, ProxylessNAS [proxylessnas] alleviates the huge consumption of resources
via path binarization. Specifically, ProxylessNAS transforms the real-valued
path weights [darts_liu18] to binary gates, which activates only one path of
the mixed operations and hence solve the memory issue.

Another problem is that optimizing different operations together is difficult,
as those operations may compete with each other, leading to a negative
influence. For example, several studies [darts+, pdarts] find that skip-
connect operation will dominate at a later search stage in DARTS, which causes
the network to be shallower and leads to a marked deterioration in
performance. To solve this problem, DARTS+ [darts+] uses an additional early-
stop criterion, such that when two or more skip-connects occur in a normal
cell, the search process stops. In another example, the solution in P-DARTS
[pdarts] is to regularize the search space, which executes operation-level
dropout to control the proportion of skip-connect operations occurring during
training and evaluation.

###  0.2.4 Surrogate Model-Based Optimization

Another group of architecture optimization method is surrogate model-based
optimization (SMBO) algorithms [towards_autotune, towards_nas_hpo, nasbot,
deeparchitect, mpas, bayenn, bananas, bayesian_incremental, epnas, pnas_liu18,
deeparchitect]. The core of SMBO is that it builds a surrogate model of the
objective function by iteratively keeping a record of past evaluation results,
and uses the surrogate model to predict the most promising architecture. In
this way, these methods can greatly shorten the time for searching and thus
improve efficiency.

SMBO algorithms differ from the surrogate models, which can be broadly divided
into Bayesian optimization methods (including Gaussian process (GP) [GP],
random forests (RF) [smbo_random_forest], Tree-structured Parzen Estimator
(TPE) [alg_hpo]), and neural networks [bananas, nao, pnas_liu18, epnas].

Bayesian optimization (BO) [bo, bo_review] is one of the most popular and
well-established methods for hyper-parameter optimization. Recently, many
follow-up works [towards_autotune, towards_nas_hpo, nasbot, deeparchitect,
mpas, bayenn, bananas, bayesian_incremental] make efforts to apply those SOTA
BO methods to architecture optimization. For example, In [scalable_bo,
snoek2012practical, nasbot, bayesian_incremental, smbo_gp_kernel, raiders_gp],
the validation results of the generated neural architectures are modeled as a
Gaussian process, which guides to search for the optimal neural architectures.
However, GP-based Bayesian optimization methods suffer from that the inference
time scales cubically in the number of observations, and they are not good at
dealing with variable-length neural networks. Camero et al. [bayesian_free]
propose three fixed-length encoding schemes to cope with variable-length
problems by employing a random forest as the surrogate model. Similarly, both
[towards_autotune] and [bayesian_free] also use a random forest as the
surrogate model, and [auto_weak] shows that random forest works better in the
setting of high dimensionality than GP-based methods.

Instead of using BO, some studies use a neural network as the surrogate model.
For example, in PNAS [pnas_liu18] and EPNAS [epnas], an LSTM is derived as the
surrogate model to predict variable-sized architectures progressively. At the
same time, NAO [nao] uses a simpler surrogate model, i.e., Multilayer
Perceptron (MLP), and NAO is more efficient and achieves better results on
CIFAR-10 compared with PNAS [pnas_liu18]. White et al. [bananas] train an
ensemble of neural networks to predict the mean and variance of validation
results for candidate neural architectures.

###  0.2.5 Grid and Random Search

Both grid search (GS) and random search (RS) are simple optimization methods
and have also been applied to several NAS studies [sharpdarts,
active_grid_nas, nas_random, eval_nas_phase]. For instance, in MnasNet
[mnasnet], the number of cells and blocks are predefined manually. To further
automate the NAS process, Geifman et al. [active_grid_nas] propose a modular
architecture search space
($\mathcal{A}=\\{A(B,i,j)|i\in\\{1,2,...,N_{cells}\\},j\in\\{1,2,...,N_{blocks}\\}\\}$)
that is spanned by the grid defined by the two corners $A(B,1,1)$ and
$A(B,N_{cells},N_{blocks})$, where $B$ is a searched block structure.
Obviously, the bigger $N_{cells}\times N_{blocks}$ is set, the larger space is
explored, but the more resources are also required.

In [nas_random], the authors conduct an effectiveness comparison between SOTA
NAS methods and random search. The results show that random search is a
competitive NAS baseline. Specifically, random search with early-stopping
strategy performs as well as ENAS [enas], which is a reinforcement learning-
based leading NAS method. Besides, the work by Yu et al. [eval_nas_phase] also
demonstrate that the SOTA NAS techniques are not significantly better than
random search.

###  0.2.6 Hybrid Optimization Method

The architecture optimization methods mentioned above have their own
advantages and disadvantages. 1) The evolutionary algorithm (EA) is a mature
global optimization method with high robustness. However, EA requires a lot of
computational resources [amoebanet, large_scale_evolve], and its evolution
operations (such as crossover and mutations) are performed randomly. 2)
Although the RL-based methods (e.g., ENAS [enas]) can learn complex
architectural patterns, the searching efficiency and stability of the RL agent
are not guaranteed, because the RL agent needs to try amounts of actions to
get a positive reward. 3) The gradient descent-based methods (e.g., DARTS
[darts_liu18]) greatly improve searching efficiency by relaxing the
categorical candidate operations to continuous variables. Nevertheless, in
essence, they all search for a child network from a super network, which
limits the diversity of neural architectures. Therefore, some methods propose
to incorporate different optimization methods to capture the best of their
worlds, and we summarize these methods as follows.

EA+RL. Chen et al. [reinf_evolv] integrate reinforced mutations into an
evolutionary algorithm, which avoids the randomness of evolution and improve
searching efficiency. Another similar method developed in parallel is
Evolutionary-Neural hybrid agent (Evo-NAS) [evolv_hyrid_agent], which also
captures the merits of both reinforcement learning-based methods and
evolutionary algorithm. The Evo-NAS agent’s mutations are guided by a neural
network trained with RL, which can explore a vast search space and sample
architectures efficiently.

EA+GD. Yang et al. [cars] combine the evolutionary algorithm and gradient
descent-based method. The architectures share parameters within one super
network and are tuned on the training set with a few epochs. Then the
populations and the super network are directly inherited in the next
generation, which greatly accelerates the evolution. [cars] only took 0.4 GPU
days for searching, which is more efficient than early EA methods (e.g.,
AmoebaNet [amoebanet] took 3150 GPU days and 450 GPUs for searching).

EA+SMBO. In [surrogate_evolv], the authors use the random forest as a
surrogate to predict model performance, which accelerates the fitness
evaluation in an evolutionary algorithm.

GD+SMBO. Different from DARTS, which learns weights for candidate operations,
NAO [nao] proposes a variational auto-encoder to generate neural architectures
and further build a regression model as a surrogate to predict the performance
of a generated architecture. Specifically, the encoder maps the
representations of the neural architecture to continuous space, then a
predictor network takes the continuous representations of the neural
architecture as input and predicts the corresponding accuracy. Finally, the
decoder is used to derive the final architecture from a continuous network
representation.

##  0.3 Hyper-parameter Optimization

Most NAS methods use the same set of hyper-parameters for all candidate
architectures during the whole search stage, so after finding the most
promising neural architecture, it is necessary to redesign a set of
hyperparameters, and use this set of hyperparameters to retrain or fine-tune
the architecture. Since some HPO methods (e.g., Bayesian optimization, and
evolutionary optimization) have also been applied in NAS, thus we will only
briefly introduce these methods. The commonly used hyper-parameter
optimization (HPO) methods include grid search, random search, Bayesian
optimization, gradient-based optimization, evolutionary optimization, and
population-based optimization.

###  0.3.1 Grid and Random Search

Figure 13 shows the difference between grid search (GS) and random search
(RS): GS divides the search space into regular intervals, and selects the
best-performing point after evaluating all points; in contrast, RS, as its
name suggests, selects the best point from a set of points drawn at random.

Figure 13: Examples of grid search (left) and random search (right) in nine
trials for optimizing a two-dimensional space function
$f(x,y)=g(x)+h(y)\approx g(x)$ [hpo_random]. The parameter in $g(x)$ (light-
blue part) is relatively important, but the parameter in $h(y)$ (light-yellow
part) is unimportant. In a grid search, nine trials cover only three different
important parameter values; however, random search can explore nine distinct
values of $g$. Therefore, random search is more likely to find the optimal
combination of parameters than grid search. (the figure is adopted from
[hpo_random])

GS is very simple and naturally supports parallel implementation, but it is
computationally expensive and inefficient when the hyper-parameter space is
very large, as the number of trials grows exponentially with the
dimensionality of hyper-parameters. To alleviate this problem, Hsu et al.
[hsu2003practical] propose coarse-to-fine grid search, i.e., first to inspect
a coarse grid to locate a good region, then implement a finer grid search on
the identified region. Similarly, Hesterman et al. [contracting_grid] propose
a contracting-grid search algorithm, which first computes the likelihood of
each point in the grid, and then generates a new grid centered on the maximum-
likelihood value. The separation of points in the new grid is reduced to half
of that on the old grid. Iterations of the above procedure are performed until
the results converge to a local minimum.

Although [hpo_random] empirically and theoretically shows that random search
is more practical and efficient than grid search, random search does not
promise an optimum. This means that although the longer the search, the more
likely it is to find the optimal hyper-parameters, it will consume more
resources. Li and Jamieson et al. [li_hyperband_2016] propose hyperband
algorithm to make a trade-off between the performance of hyper-parameters and
resource budgets. Hyperband allocates limited resources (such as time or CPUs)
to only the most promising hyper-parameters, by successively discarding the
worst half of configuration settings long before the training process is
finished.

###  0.3.2 Bayesian Optimization

Bayesian optimization (BO) is an efficient method for global optimization of
expensive blackbox functions. In this part, we will only provide a brief
introduction to BO. For an in-depth discussion for BO, we recommend readers to
refer to these excellent surveys [bo_review, bo, hpo_chapter, hpo_survey].

BO is a surrogate model-based optimization (SMBO) method, which builds a
probabilistic model mapping from hyperparameters to the objective metrics
evaluated on the validation set. It well balances exploration (evaluating as
many sets of hyperparameters as possible) and exploitation (allocating more
resources to those promising hyperparameters).

Sequential Model-Based Optimization $\text{INPUT:}\,f,\Theta,S,\mathcal{M}$
${\mathcal{D}\leftarrow\text{INITSAMPLES}(f,\Theta)}$ $i$ in $[1,2,..,T]$
${p(y|\theta,\mathcal{D})\leftarrow\text{FITMODEL}(\mathcal{M},\mathcal{D})}$
${\theta_{i}\leftarrow\arg\max_{\theta\in\Theta}S(\theta,p(y|\theta,\mathcal{D}))}$
${y_{i}\leftarrow
f\left(\theta_{i}\right)}\,\,\,\,\,\,\triangleright\text{Expensivestep}$
$\mathcal{D}\leftarrow\mathcal{D}\cup\left(\theta_{i},y_{i}\right)$

The steps of SMBO are expressed in Algorithm 0.3.2 (adopted from [bo]), which
presents that several inputs need to be predefined at initial, including
evaluation function $f$, search space $\Theta$, acquisition function
$\mathcal{S}$, probabilistic model $\mathcal{M}$, and the records dataset $D$.
Specifically, $D$ is a dataset that records many sample pairs
($\theta_{i},y_{i}$), where $\theta_{i}\in\Theta$ indicates a sampled neural
architecture and $y_{i}$ is the evaluation result of the sampled neural
architecture. After the initialization, the steps of SMBO are as follows:

  1. 1.

The first step is to tune the probabilistic model $\mathcal{M}$ to fit the
records dataset $D$.

  2. 2.

The acquisition function $\mathcal{S}$ is used to select the next promising
neural architecture from the probabilistic model $\mathcal{M}$.

  3. 3.

After that, the performance of the selected neural architecture will be
evaluated by $f$, which is an expensive step as it involves training the
neural network on the training set and evaluating it on the validation set.

  4. 4.

The records dataset $D$ is updated by appending a new pair of result
$(\theta_{i},y_{i})$.

The above four steps are repeated for $T$ times, where $T$ needs to be
specified according to the total time or resources available. The commonly
used surrogate models for BO method are Gaussion process (GP), random forest
(RF), and Tree-structured Parzen Estimator (TPE). Table 1 summarize existing
open-source BO methods, where GP is one of the most popular surrogate model.
However, GP scales cubically with the number of data samples, while RF can
natively handle large spaces and scales better to many data samples. Besides,
Falkner and Klein et al. [bohb] propose the BO-based Hyperband (BOHB)
algorithm, which combines the strengths of TPE-based BO and Hyperband, and
hence perform much better than standard BO methods. Furthermore, FABOLAS
[fabolas] is a faster BO procedure, which maps the validation loss and
training time as a function of dataset size, i.e., trains a generative model
on a sub-dataset that gradually increases in size. As a result, FABOLAS is 10
to 100 times faster than other SOTA BO algorithms and identifies the most
promising hyper-parameters.

Library | Model
---|---
Spearmint |
https://github.com/HIPS/Spearmint | GP
MOE |
https://github.com/Yelp/MOE | GP
PyBO |
https://github.com/mwhoffman/pybo | GP
Bayesopt |
https://github.com/rmcantin/bayesopt | GP
SkGP |
https://scikit-optimize.github.io | GP
GPyOpt |
http://sheffieldml.github.io/GPyOpt | GP
SMAC |
https://github.com/automl/SMAC3 | RF
Hyperopt |
http://hyperopt.github.io/hyperopt | TPE
BOHB |
https://github.com/automl/HpBandSter | TPE
Table 1: The open-source Bayesian optimization libraries. GP, RF, and TPE
represent Gaussian process [GP], random forests [smbo_random_forest], Tree-
structured Parzen Estimator [alg_hpo], respectively.

###  0.3.3 Gradient-Based Optimization

Another group of HPO methods are gradient-based optimization (GO) algorithms
[go_hpo, generic_opt, gd_hpo_revers, hpo_appro_gd, forward_gd_hpo,
gd_ultimate_hpo]. Different to above blackbox HPO methods (e.g, GS,RS, and
BO), GO methods use the gradient information to optimize hyperparameters, and
greatly improve the efficiency of HPO. Maclaurin et al. [gd_hpo_revers]
propose a reversible-dynamics memory-tape approach to handle thousands of
hyperparameters efficiently through gradient information. However, optimizing
many hyperparameters is computationally challenging. To alleviate this issue,
[hpo_appro_gd] use approximate gradient information rather than true gradient
to optimize continuous hyperparameters, in which case the hyperparameters can
be updated before the model is trained to converge. Franceschi et al.
[forward_gd_hpo] study both the reverse-mode and forward-mode GO methods. The
reverse-mode method differs from [gd_hpo_revers] and does not require
reversible dynamics, whereas it needs to store the entire training history for
computing the gradient with respect to hyperparameters. The forward-mode
method overcomes this problem by real-time updating hyperparameters, and is
demonstrated to significantly improve the efficiency of HPO on large datasets.
Chandra [gd_ultimate_hpo] propose the gradient-based ultimate optimizer, which
can not only optimize the regular hyperparameters (e.g., learning rate), but
also optimize the hyperparameters of optimizer (e.g., Adam optimizer
[kingma2014adam]’s moment coefficient $\beta_{1},\beta_{2}$).