\section{Introduction}\label{section:introduction}
\subfile{introduction}



\section{Data Preparation}\label{section:data_preparation}
\subfile{data_preparation}


\section{Feature Engineering}
\label{section:feature_engineering}
\subfile{feature_engineering}



\section{Model Generation}\label{section:model_generation}
\subfile{model_generation}


\section{Model Estimation}\label{section:model_estimation}
\subfile{model_estimation}




\section{NAS Performance Summary}\label{section:nas_performance}
\subfile{nas_performance}



\section{Open Problems and Future Work}\label{section:open_problems}
\subfile{open_problems}


\section{Conclusions}\label{section:conclusion}
\subfile{conclusion}



\bibliographystyle{elsarticle-num} 


\subsection{Data Collection}

ML's deepening study has led to a consensus that good data must be available; as a result, numerous open datasets have emerged. In the early stages of ML's study, a handwritten digital dataset, i.e., MNIST \cite{mnist}, was developed. After that, several larger datasets like CIFAR-10 and CIFAR-100 \cite{cifar10} and ImageNet \cite{imagenet} were also developed. A variety of datasets can also be retrieved by entering the keywords into these websites: Kaggle \footnote{https://www.kaggle.com}, Google Dataset Search (GOODS) \footnote{https://datasetsearch.research.google.com/}, and Elsevier Data Search \footnote{https://www.datasearch.elsevier.com/}. 

However, it is usually challenging to find a proper dataset through the above approaches for some particular tasks, such as those related to medical care or other private matters. Two types of methods are proposed to solve this problem: data searching and data synthesis. 

\subsubsection{Data Searching}

As the Internet is an inexhaustible source of data, searching for Web data is an intuitive way to collect a dataset \cite{filter_web_data,chen2013neil,xia2014well,do2015automatic}. However, there are some problems with using Web data. 

First, the search results may not exactly match the keywords. Thus, unrelated data must be filtered. For example, Krause et al. \cite{krause2016unreasonable} separate inaccurate results as cross-domain or cross-category noise, and remove any images that appear in search results for more than one category. Vo et al. \cite{vo2017harnessing} re-rank relevant results and provide search results linearly, according to keywords. 

Second, Web data may be incorrectly labeled or even unlabeled. A learning-based self-labeling method is often used to solve this problem. For example, the active learning method \cite{collins2008towards} selects the most ‘‘uncertain'' unlabeled individual examples for labeling by a human, and then iteratively labels the remaining data. Roh et al. \cite{survey_data_collect} provide a review of semi-supervised learning self-labeling methods, which can help take the human out of the loop of labeling to improve efficiency, and can be divided into the following categories: self-training \cite{yarowsky1995unsupervised, triguero2014characterization}, co-training \cite{hady2010combining, blum1998combining}, and co-learning \cite{democratic_co_learn}. Moreover, due to the complexity of Web images content, a single label cannot adequately describe an image. Consequently, Yang et al. \cite{filter_web_data} assign multiple labels to a Web image, i.e., if the confidence scores of these labels are very close or the label with the highest score is the same as the original label of the image, then this image will be set as a new training sample.

However, the distribution of Web data can be extremely different from that of the target dataset, which will increase the difficulty of training the model. A common solution is to fine-tune these Web data \cite{chen2015webly,xu2015augmenting}. Yang et al. \cite{filter_web_data} propose an iterative algorithm for model training and Web data-filtering. Dataset imbalance is another common problem, as some special classes have a very limited number of Web data. To solve this problem, the synthetic minority over-sampling technique (SMOTE) \cite{chawla2002smote} is used to synthesize new minority samples between existing real minority samples, instead of simply up-sampling minority samples or down-sampling the majority samples. In another approach, Guo et al. \cite{guo2004learning} combine the boosting method with data generation to enhance the generalizability and robustness of the model against imbalanced data sets.

\subsubsection{Data Synthesis}

Data simulator is one of the most commonly used methods to generate data. For some particular tasks, such as autonomous driving, it is not possible to test and adjust a model in the real world during the research phase, due to safety hazards. Therefore, a practical approach to generating data is to use a data simulator that matches the real world as closely as possible. OpenAI Gym \cite{openai_gym} is a popular toolkit that provides various simulation environments, in which developers can concentrate on designing their algorithms, instead of struggling to generate data. Wang et al. \cite{irs} use a popular game engine, Unreal Engine 4, to build a large synthetic indoor robotics stereo (IRS) dataset, which provides the information for disparity and surface normal estimation. Furthermore, a reinforcement learning-based method is applied in \cite{ruiz2018learning} for optimizing the parameters of a data simulator to control the distribution of the synthesized data.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.3\textwidth]{GAN_image.png}
    \caption{The examples of human face images generated by GAN \cite{karras2018style}.}
    \label{fig:GAN}
\end{figure}

Another novel technique for derive synthetic data is \textit{Generative Adversarial Networks} (GANs) \cite{goodfellow2014generative}, which can be used to generate images \cite{goodfellow2014generative,oh2018learning,rendergan,gan_aug}, tabular \cite{table_gan, tabular_gan} and text \cite{text_gan_no_RL} data. Figure \ref{fig:GAN} shows some human face images, which are generated by GAN in the work of Karras et al. \cite{karras2018style}. Oh and Jaroensri et al. \cite{oh2018learning} build a synthetic dataset, which captures small motion for video-motion magnification. Bowles et al. \cite{gan_aug} demonstrate the feasibility of using GAN to generate medical images for brain segmentation tasks. In the case of textual data, applying GAN to text has proved difficult because the commonly used method is to use reinforcement learning to update the gradient of the generator, but the text is discrete, and thus the gradient cannot propagate from discriminator to generator. To solve this problem, Donahue et al. \cite{text_gan_no_RL} use an autoencoder to encode sentences into a smooth sentence representation to remove the barrier of reinforcement learning. Park et al. \cite{table_gan} apply GAN to synthesize fake tables that are statistically similar to the original table but do not cause information leakage. Similarly, in \cite{tabular_gan}, GAN is applied to generate tabular data like medical or educational records.



\subsection{Data Cleaning}

The collected data inevitably have noise, but the noise can negatively affect the training of the model. Therefore, the process of data cleaning \cite{dc_survey, jesmeen2018survey} must be carried out if necessary. Across the literature, the effort of data cleaning is shifting from crowdsourcing to automation. Traditionally, data cleaning requires specialist knowledge, but access to specialists is limited and generally expensive. Hence, Chu et al. \cite{katara} propose Katara, a knowledge-based and crowd-powered data cleaning system. To improve efficiency, some methods \cite{sampleclean, activeclean} propose only to clean a small subset of the data and maintain comparable results to the case of cleaning the full dataset. However, these methods require a data scientist to design what data cleaning operations are applied to the dataset. BoostClean \cite{boostclean} attempts to automate this process by treating it as a boosting problem. Each data cleaning operation effectively adds a new cleaning operation to the input of the downstream ML model, and through a combination of Boosting and feature selection, a good series of cleaning operations, which can well improve the performance of the ML model, can be generated. AlphaClean \cite{alphaclean} transforms data cleaning into a hyper-parameter optimization problem, which further increases automation. Specifically, the final data cleaning combinatorial operation in AlphaClean is composed of several pipelined cleaning operations that need to be searched from a predefined search space. Gemp et al. 

The data cleaning methods mentioned above are applied to a fixed dataset. However, the real world generates vast amounts of data every day. In other words, how to clean data in a continuous process becomes a worth studying problem, especially for enterprises. Ilyas et al. \cite{eval_continuous_dc} propose an effective way of evaluating the algorithms of continuously cleaning data. Mahdavi et al. \cite{auto_dc_workflow} build a cleaning workflow orchestrator, which can learn from previous cleaning tasks, and propose promising cleaning workflows for new datasets.



\subsection{Data Augmentation}


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/data_augmentation.png}
    \caption{A classification of data augmentation techniques.}
    \label{fig:data_augmentation}
\end{figure}

To some degree, data augmentation (DA) can also be regarded as a tool for data collection, as it can generate new data based on the existing data. However, DA also serves as a regularizer to avoid over-fitting of model training and has received more and more attention. Therefore, we introduce DA as a separate part of data preparation in detail. Figure \ref{fig:data_augmentation} classifies DA techniques from the perspective of data type (image, audio, and text), and incorporates automatic DA techniques that have recently received much attention. 

For image data, the affine transformations include rotation, scaling, random cropping, and reflection; the elastic transformations contain the operations like contrast shift, brightness shift, blurring, and channel shuffle; the advanced transformations involve random erasing, image blending, cutout \cite{cutout}, and mixup \cite{mixup}, etc. These three types of common transformations are available in some open source libraries, like torchvision \footnote{https://pytorch.org/docs/stable/torchvision/transforms.html}, ImageAug \cite{imgaug}, and Albumentations \cite{albumentations}. In terms of neural-based transformations, it can be divided into three categories: adversarial noise \cite{aug_an}, neural style transfer \cite{st_aug}, and GAN technique \cite{aug_gan}. For textual data, Wong et al. \cite{wong2016understanding} propose two approaches for creating additional training examples: data warping and synthetic over-sampling. The former generates additional samples by applying transformations to data-space, and the latter creates additional samples in feature-space. Textual data can be augmented by synonym insertion or by first translating the text into a foreign language and then translating it back to the original language. In a recent study, Xie et al. \cite{xie2017data} propose a non-domain-specific DA policy that uses noising in RNNs, and this approach works well for the tasks of language modeling and machine translation. Yu et al. \cite{yu2018qanet} propose the use of back-translation for DA to aid reading comprehension. NLPAug \cite{nlp_aug} is an open-source library that integrates many types of augmentation operations for both textual and audio data.

The above augmentation techniques still require human to select augmentation operations and then form a specific DA policy for specific tasks, which requires much expertise and time. Recently, there are many methods \cite{cubuk2019autoaugment,dada,fasteraa,fastaa,greedy_aa,population_aa,aug_policy,rs_aug,adv_aug,online_aug,uniform_aug} proposed to search for augmentation policy for different tasks. AutoAugment \cite{cubuk2019autoaugment} is a pioneering work to automate the search for optimal DA policies using reinforcement learning. However, AutoAugment is not efficient as it takes almost 500 GPU hours for one augmentation search. In order to improve search efficiency, a number of improved algorithms have subsequently been proposed using different search strategies, such as gradient descent-based \cite{dada,fasteraa}, Bayesian-based optimization \cite{fastaa}, online hyper-parameter learning \cite{online_aug}, greedy-based search \cite{greedy_aa} and random search \cite{rs_aug}. Besides, LingChen et al. \cite{uniform_aug} propose a search-free DA method, namely UniformAugment, by assuming that the augmentation space is approximately distribution invariant.
\end{document}

\subsection{Feature Selection}

Feature selection builds a feature subset based on the original feature set by reducing irrelevant or redundant features. This tends to simplify the model, hence avoiding overfitting and improving model performance. The selected features are usually divergent and highly correlated with object values. According to \cite{dash1997feature}, there are four basic steps in a typical process of feature selection (see Figure \ref{fig:fe_process}), as follows:

\begin{figure}[ht]
    \centering
   
    \includegraphics[width=0.3\textwidth]{images/feature_selection.pdf}
    \caption{The iterative process of feature selection. A subset of features is selected, based on a search strategy, and then evaluated. Then, a validation procedure is implemented to determine whether the subset is valid. The above steps are repeated until the stop criterion is satisfied.}
    \label{fig:fe_process}
\end{figure}

The search strategy for feature selection involves three types of algorithms: complete search, heuristic search, and random search. Complete search comprises exhaustive and non-exhaustive searching; the latter can be further split into four methods: breadth-first search, branch and bound search, beam search, and best-first search. Heuristic search comprises sequential forward selection (SFS), sequential backward selection (SBS), and bidirectional search (BS). In SFS and SBS, the features are added from an empty set or removed from a full set, respectively, whereas BS uses both SFS and SBS to search until these two algorithms obtain the same subset. The most commonly used random search methods are simulated annealing (SA) and genetic algorithms (GAs).

Methods of subset evaluation can be divided into three different categories. The first is the filter method, which scores each feature according to its divergence or correlation and then selects features according to a threshold. Commonly used scoring criteria for each feature are variance, the correlation coefficient, the chi-square test, and mutual information. The second is the wrapper method, which classifies the sample set with the selected feature subset, after which the classification accuracy is used as the criterion to measure the quality of the feature subset. The third method is the embedded method, in which variable selection is performed as part of the learning procedure. Regularization, decision tree, and deep learning are all embedded methods.




\subsection{Feature Construction}


Feature construction is a process that constructs new features from the basic feature space or raw data to enhance the robustness and generalizability of the model. Essentially, this is done to increase the representative ability of the original features. This process is traditionally highly dependent on human expertise, and one of the most commonly used methods is preprocessing transformation, such as standardization, normalization, or feature discretization. In addition, the transformation operations for different types of features may vary. For example, operations such as conjunctions, disjunctions and negation are typically used for Boolean features; operations such as minimum, maximum, addition, subtraction, mean are typically used for numerical features, and operations such as Cartesian product \cite{pazzani1998constructive} and M-of-N \cite{zheng1998comparison} are commonly used for nominal features. 

It is impossible to manually explore all possibilities. Hence, to further improve efficiency, some automatic feature-construction methods have been proposed and shown to achieve results as good as or superior to those achieved by human expertise. These algorithms are aimed to automate the process of searching and evaluating the operation combination. In terms of searching, algorithms such as decision tree-based methods \cite{gama2004functional,zheng1998comparison} and genetic algorithms \cite{vafaie1998evolutionary} require a pre-defined operation space, while annotation-based approaches do not, as the latter use domain knowledge (in the form of annotation), together with the training examples \cite{feat_cons_survey}. Such methods can be traced back to the interactive feature-space construction protocol introduced by \cite{roth2009interactive}. Using this protocol, the learner identifies inadequate regions of feature space and, in coordination with a domain expert, adds descriptiveness using existing semantic resources. Then, after selecting possible operations and constructing a new feature, feature-selection techniques are applied to measure the new feature.







\subsection{Feature Extraction}

Feature extraction is a dimensionality-reduction process performed via some mapping functions. It extracts informative and non-redundant features according to certain metrics. Unlike feature selection, feature extraction alters the original features. The kernel of feature extraction is a mapping function, which can be implemented in many ways. The most prominent approaches are principal component analysis (PCA), independent component analysis, isomap, nonlinear dimensionality reduction, and linear discriminant analysis (LDA). Recently, the feed-forward neural networks approach has become popular; this uses the hidden units of a pretrained model as extracted features. Furthermore, many autoencoder-based algorithms are proposed; for example, Zeng et al. \cite{meng2017relational} propose a relation autoencoder model that considers data features and their relationships, while an unsupervised feature-extraction method using autoencoder trees is proposed by \cite{irsoy2017unsupervised}.



\end{document}


\subsection{Low fidelity}

As model training time is highly related to the dataset and model size, model evaluation can be accelerated in different ways. First, the number of images or the resolution of images (in terms of image-classification tasks) can be decreased. For example, FABOLAS \cite{fabolas} trains the model on a subset of the training set to accelerate model estimation. In \cite{imagenet_variants}, ImageNet64$\times$64 and its variants 32$\times$32, 16$\times$16 are provided, while these lower resolution datasets can retain characteristics similar to those of the original ImageNet dataset. Second, low-fidelity model evaluation can be realized by reducing the model size, such as by training with fewer filters per layer \cite{nasnet_zoph17, amoebanet}. By analogy to ensemble learning, \cite{multi_fidelity} proposes the \textit{Transfer Series Expansion (TSE)}, which constructs an ensemble estimator by linearly combining a series of basic low-fidelity estimators, hence avoiding the bias that can derive from using a single low-fidelity estimator. Furthermore, Zela et al. \cite{towards_nas_hpo} empirically demonstrate that there is a weak correlation between performance after short or long training times, thus confirming that a prolonged search for network configurations is unnecessary (see Figure \ref{fig:short_time}). 



\subsection{Weight sharing} 

In \cite{nas_rl_zoph16}, once a network has been evaluated, it is dropped. Hence, the technique of weight sharing is used to accelerate the process of NAS. For example, Wong and Lu et al. \cite{wong2018transfer} propose Transfer Neural AutoML, which uses knowledge from prior tasks to accelerate network design. ENAS \cite{enas} shares parameters among child networks, leading to a thousand-fold faster network design than \cite{nas_rl_zoph16}. Network morphism based algorithms \cite{chen2015net2net,network_morphism_wei16} can also inherit the weights of previous architectures, and single-path NAS \cite{singlepath_nas} uses a single-path over-parameterized ConvNet to encode all architectural decisions with shared convolutional kernel parameters.


\subsection{Surrogate}

The surrogate-based method \cite{eggensperger2014surrogate,wang2014evaluation,eggensperger2015efficient,surrogate_evolv} is another powerful tool that approximates to the black-box function. In general, once a good approximation has been obtained, it is trivial to find the configurations that directly optimize the original expensive objective. For example, Progressive Neural Architecture Search (PNAS) \cite{pnas_liu18} introduces a surrogate model to control the method of searching. Although ENAS has been proven to be very efficient, PNAS is even more efficient, as the number of models evaluated by PNAS is over five times that evaluated by ENAS, and PNAS is eight times faster in terms of total computational speed. However, when the optimization space is too large and hard to quantify, and the evaluation of each configuration is extremely expensive \cite{smbo_vu17}, a surrogate-based method is not applicable. Luo et al. \cite{semi_NAS} propose \textit{SemiNAS}, a semi-supervised NAS method, which leverages amounts of unlabeled architectures to further improve searching efficiency. The accuracy of the generated model does not need to be evaluated after training the model, but can be obtained only by using the controller to predict the accuracy.


\subsection{Early stopping}

Early stopping was first used to prevent overfitting in classical ML. It is used in several recent studies \cite{learn_curve_Klein16,peephole,speedup_learn_curve} to accelerate model evaluation by stopping evaluations that are predicted to perform poorly on the validation set. For example, \cite{speedup_learn_curve} proposes a learning-curve model that is a weighted combination of a set of parametric curve models selected from the literature, thereby enabling the performance of the network to be predicted. Furthermore, \cite{earlystop_no_val} presents a novel approach for early stopping based on fast-to-compute local statistics of the computed gradients, which no longer relies on the validation set and allows the optimizer to make full use of all of the training data.


\subsection{Resource-aware}

Early NAS studies \cite{nas_rl_zoph16,nasnet_zoph17,amoebanet} pay more attention to searching for neural architectures that achieve higher performance (e.g., classification accuracy), regardless of the associated resource consumption (i.e., the number of GPUs and time required). Therefore, many follow-up studies investigate resource-aware algorithms to trade off performance against the resource budget. To do so, these algorithms add computational cost to the loss function as a resource constraint. These algorithms differ in the type of computational cost, which may be 1) the parameter size; 2) the number of Multiply-ACcumulate (MAC) operations; 3) the number of float-point operations (FLOPs); or 4) the real latency. For example, MONAS \cite{monas} considers MAC as the constraint, and as MONAS uses a policy-based reinforcement-learning algorithm to search, the constraint can be directly added to the reward function. MnasNet \cite{mnasnet} proposes a customized weighted product to approximate a Pareto optimal solution:

\begin{equation}
\underset{m}{\operatorname{maximize}} \quad A C C(m) \times\left[\frac{L A T(m)}{T}\right]^{w}
\end{equation}

\noindent where $LAT(m)$ denotes measured inference latency on the target device, $T$ is the target latency, and $w$ is the weight variable defined as:

\begin{equation}
w=\left\{\begin{array}{ll}
\alpha, & \text { if } LAT(m) \leq T \\
\beta, & \text { otherwise }
\end{array}\right.
\end{equation}

\noindent where the recommended value for both $\alpha$ and $\beta$ are $-0.07$.

In terms of a differentiable neural architecture search (DNAS) framework, the constraint (i.e., loss function) should be differentiable. To do so, FBNet \cite{fbnet} uses a latency lookup table model to estimate the overall latency of a network based on the runtime of each operator. The loss function is defined as: 

\begin{equation}
\mathcal{L}\left(a, \theta_{a}\right)=\operatorname{CE}\left(a, \theta_{a}\right) \cdot \alpha \log (\operatorname{LAT}(a))^{\beta}
\end{equation}

\noindent where $CE(a,\theta_a)$ indicates the cross-entropy loss of architecture $a$ with weights $\theta_a$. Like MnasNet \cite{mnasnet}, this loss function has two hyper-parameters that need to be set manually: $\alpha$ and $\beta$ control the magnitude of the loss function and the latency term, respectively. In SNAS \cite{snas}, the cost of time for the generated child network is linear to the one-hot random variables, such that the resource constraint's differentiability is ensured.


\end{document}

\subsection{Search Space}


The neural architecture can be represented as a direct acyclic graph (DAG) \cite{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:

\begin{figure}[ht]
    \centering
   
   
    \includegraphics[width=0.36\textwidth]{images/entire_structure.pdf}
    \caption{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.}
    \label{fig:whole_structure}
\end{figure}

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


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 \cite{chollet2017xception}, dilated convolution\cite{dilated_conv}, and Squeeze-and-Excitation (SE) Block \cite{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.

\subsubsection{Entire-structured Search Space} 

The space of entire-structured neural networks \cite{nas_rl_zoph16,enas} is one of the most intuitive and straightforward search space. Figure \ref{fig:whole_structure} 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 \ref{fig:whole_structure}, while the right model is relatively complex, as it permits arbitrary skip connections \cite{resnet} to exist between the ordered nodes, and these connections have been proven effective in practice \cite{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.




\subsubsection{Cell-Based Search Space}

\begin{figure}[!ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/cell_structure.pdf}
    \caption{(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. }
    \label{fig:cell_structure}
\end{figure}



\textbf{Motivation}. To enable the transferability of the generated model, many works \cite{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 \cite{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 \cite{resnet}. Throughout the literature, this repeated module has been referred to as motif, cell, or block, while in this paper, we call it \textit{cell}. 


\textbf{Design}. Figure \ref{fig:cell_structure} (left) presents an example of a final cell-based neural network, which consists of two types of cells, namely \textit{normal} and \textit{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 \cite{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. \cite{nasnet_zoph17}, which is one of the first to propose an exploration of cell-based search space. Figure \ref{fig:cell_structure} (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\times1$ 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.

\textbf{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 


\begin{equation}
N_{entire}=M^L\times 2^{\frac{L\times(L-1)}{2}}
\label{eq:entire}
\end{equation}


\noindent 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 

\begin{equation}
N_{cell}=(M^B\times (B+2)!)^4
\label{eq:cell}
\end{equation}


\noindent 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 \ref{eq:entire} and \ref{eq:cell} the typical value in the literature, i.e. $M=5, L=10, B=3$, then $N_{entire}=3.44\times10^{20}$ is much larger than $N_{cell}=5.06\times10^{16}$.

\textbf{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 \ref{fig:pdarts} (left) shows, for DARTS \cite{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. \cite{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 \ref{fig:pdarts}. Experimentally, P-DARTS obtains a 2.50\% error rate on the CIFAR-10 test dataset, outperforming the 2.83\% error rate of DARTS. 


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/pdarts.pdf}
    \caption{Difference between DARTS \cite{darts_liu18} and P-DARTS \cite{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.}
    \label{fig:pdarts}
\end{figure}


\subsubsection{Hierarchical Search Space}

 \begin{figure}[ht]
    \centering
    \subfigure[Network-level architecture used in Conv-Deconv.]{\includegraphics[width=0.48\textwidth]{images/unet.png}}
    \subfigure[Network-level architecture used in stacked hourglass networks. ]{\includegraphics[width=0.48\textwidth]{images/glass.png}}
    \caption{The network-level search space (the figure is adopted from\cite{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.}
    \label{fig:two_level_hier}
\end{figure}

The cell-based search space enables the transferability of the generated model, and most of the cell-based methods \cite{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 \ref{fig:cell_structure}, 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. \cite{auto_deeplab} define a general formulation for a network-level structure, depicted in Figure \ref{fig:two_level_hier}, 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.

\begin{figure}[ht]
    \centering
    \subfigure[The level-one primitive operations are assembled into level-two cells.]{\includegraphics[width=0.48\textwidth]{images/hierachical1.png}}
    \subfigure[The level-two cells are viewed as primitive operations and assembled into level-three cells.]{\includegraphics[width=0.48\textwidth]{images/hierachical2.png}}
    \caption{An example of a three-level hierarchical architecture representation. The figure is adopted from \cite{liu_hierarchical_2018}.}
    \label{fig:hier_cell}
\end{figure}

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. \cite{liu_hierarchical_2018} propose a novel hierarchical genetic representation scheme, namely \textit{HierNAS}, in which the higher-level cell is generated by iteratively incorporating lower-level cells. As shown in Figure \ref{fig:hier_cell}, 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 \ref{fig:hier_cell}(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. \cite{pnas_liu18} also propose \textit{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 \cite{mnasnet,fbnet}. To ease both problems, Tan et al. \cite{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 \ref{fig:mnasnet} 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 \cite{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. \cite{proxylessnas} propose ProxylessNAS that can directly search for neural networks on the targeted dataset and hardware platforms by using BinaryConnect \cite{binaryconnect}, which addresses the high memory consumption issue.


\begin{figure}[!ht]
    \centering
    \includegraphics[width=0.35\textwidth]{images/mnasnet.pdf}
    \caption{The factorized hierarchical search space in MnasNet \cite{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.}
    \label{fig:mnasnet}
\end{figure}



\subsubsection{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 \cite{knowledgedistill} and transfer learning \cite{transferlearning}. However, these methods do not directly modify the model structure. To this end, Chen et al. \cite{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 \cite{resnet}. Therefore, an improved method is proposed, namely network morphism \cite{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. 

\begin{figure}[!ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/net2net.pdf}
    \caption{Net2DeeperNet and Net2WiderNet transformations in \cite{chen2015net2net}. "IdMorph" indicates identity morphism operation.}
    \label{fig:net2net}
\end{figure}

Several subsequent research works \cite{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. \cite{autokeras} propose a framework that enables Bayesian optimization to guide the network morphism for an efficient neural architecture search. Wei et al \cite{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 \cite{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.



\subsection{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.

\subsubsection{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. 

\textbf{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 \cite{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 \cite{cgp_suganuma17,large_scale_evolve,liu_hierarchical_2018}. For example, Suganuma et al. \cite{cgp_suganuma17} use Cartesian genetic programming (CGP) \cite{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 \cite{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)  \cite{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) \cite{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 \cite{fernando2016convolution,kim2015deep,pugh2013evolving, lemonade} describe the use of indirect encoding schemes to represent the network. For example, the network in \cite{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.


\begin{figure}
    \centering
    \includegraphics[width=0.32\textwidth]{images/ea.pdf}
    \caption{The overview of evolutionary algorithm.}
    \label{fig:ea}
\end{figure}

\textbf{Four Steps.} A typical evolutionary algorithm consists of the following steps: selection, crossover, mutation, and update (see Figure \ref{fig:ea}):

\begin{itemize}
    \item \textbf{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 \textit{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 \textit{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 \textit{tournament selection} \cite{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. 

    \item \textbf{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. \cite{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. 
    
    
    \item \textbf{Mutation}
    As the genetic information of the parents is copied and inherited by the next generation, gene mutation also occurs. A point mutation \cite{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 \cite{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. \cite{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. 
    
    
    \item \textbf{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 \cite{large_scale_evolve}, the worst-performing network of two randomly selected networks is immediately removed from the population. Alternatively, in \cite{amoebanet}, the oldest networks are removed. Other methods \cite{evolve_dnn,genertic_cnn,cgp_suganuma17} discard all models at regular intervals. However, Liu et al. \cite{liu_hierarchical_2018} do not remove any networks from the population; instead, they allow the network to grow with time. EENA \cite{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$.
    
    
\end{itemize}



\subsubsection{Reinforcement Learning}


\begin{figure}[ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/rl_nas.pdf}
    \caption{An overview of NAS using reinforcement learning.}
    \label{fig:rl_nas}
\end{figure}


Zoph et al. \cite{nas_rl_zoph16} were one of the first to apply reinforcement learning (RL) for neural architecture search. Figure \ref{fig:rl_nas} 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 \cite{metaqnn,nasnet_zoph17,blockqnn,enas} use this framework, but with different agent policies and  neural-architecture encoding. Zoph et al. \cite{nas_rl_zoph16} first use the policy gradient algorithm \cite{policygradient} to train the agent, and sequentially sample a string to encode the entire neural architecture. In subsequent work \cite{nasnet_zoph17}, they use the Proximal Policy Optimization (PPO) algorithm \cite{ppo} to update the agent, and propose the method shown in Figure \ref{fig:rl_cell} to build the cell-based neural architecture. MetaQNN \cite{metaqnn} proposes a meta-modeling algorithm using Q-learning and a $\epsilon$-greedy exploration strategy and experience replay to search neural architectures sequentially. 

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.48\textwidth]{images/rl_cell.pdf}
    \caption{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.}
    \label{fig:rl_cell}
\end{figure}

Although the above RL-based algorithms have achieved SOTA results on CIFAR-10 and Penn Treebank (PTB) \cite{ptb} datasets, they spend much time and computational resources. For instance, \cite{nas_rl_zoph16} took 28 days and 800 K40 GPUs to search for the best-performing architecture, and MetaQNN \cite{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 \cite{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) \cite{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 \cite{nas_rl_zoph16}. 



\subsubsection{Gradient Descent}

The search strategies above sample neural architectures from a discrete search space. A pioneering algorithm, namely DARTS \cite{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:


\begin{equation}
\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)
\label{eq:darts_softmax}
\end{equation}

\noindent 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{equation}
\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}
\label{eq:bilevel}
\end{equation}


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/darts.png}
    \caption{An overview of DARTS (the figure is adopted from \cite{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.}
    \label{fig:darts}
\end{figure}

Figure \ref{fig:darts} 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. \ref{eq:bilevel} 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:

\begin{equation}
    \min _{\theta, \alpha} \mathcal{L}_{\mathrm{train}}(\theta, \alpha)
    \label{eq:single_level}
\end{equation}

\noindent 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 \cite{MiLeNAS}, the authors propose mixed-level optimization:

\begin{equation}
\min _{\alpha, \theta}\,\,\left[\mathcal{L}_{train}\left(\theta^{*}, \alpha\right)+\lambda \mathcal{L}_{val}\left(\theta^{*}, \alpha\right)\right]
\label{eq:mixed_level}
\end{equation}

\noindent 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. \ref{eq:mixed_level} degrades to the single-level optimization (Eq. \ref{eq:single_level}); while if $\lambda$ is close to infinity, then Eq. \ref{eq:mixed_level} becomes a bilevel optimization (Eq. \ref{eq:bilevel}). The experimental results in \cite{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. \ref{eq:darts_softmax}) 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 \cite{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 \cite{gumbel_softmax}. Specifically, the neural architecture is fully factorized and modeled with a concrete distribution \cite{concrete_dist}, which provides an efficient way to sample a child architecture and allows gradient back-propagation. Therefore, Eq. \ref{eq:darts_softmax} is re-formulated as Eq. \ref{eq:gumbel_softmax}:



\begin{equation}
    \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)
    \label{eq:gumbel_softmax}
\end{equation}


\noindent 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 \cite{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. \ref{eq:gumbel_softmax}. In other words, only one path of the super-net is selected for training, thereby reducing GPU memory usage. On the other hand, ProxylessNAS \cite{proxylessnas} alleviates the huge consumption of resources via path binarization. Specifically, ProxylessNAS transforms the real-valued path weights \cite{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 \cite{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+ \cite{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 \cite{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.


\subsubsection{Surrogate Model-Based Optimization}


Another group of architecture optimization method is surrogate model-based optimization (SMBO) algorithms \cite{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 \textit{Gaussian process (GP)} \cite{GP}, \textit{random forests (RF)} \cite{smbo_random_forest}, \textit{Tree-structured Parzen Estimator (TPE)} \cite{alg_hpo}), and neural networks \cite{bananas,nao,pnas_liu18,epnas}. 

Bayesian optimization (BO) \cite{bo,bo_review} is one of the most popular and well-established methods for hyper-parameter optimization. Recently, many follow-up works \cite{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 \cite{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. \cite{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 \cite{towards_autotune} and \cite{bayesian_free} also use a random forest as the surrogate model, and  \cite{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 \cite{pnas_liu18} and EPNAS \cite{epnas}, an LSTM is derived as the surrogate model to predict variable-sized architectures progressively. At the same time, NAO \cite{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 \cite{pnas_liu18}. White et al. \cite{bananas} train an ensemble of neural networks to predict the mean and variance of validation results for candidate neural architectures.
 

\subsubsection{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 \cite{sharpdarts,active_grid_nas,nas_random,eval_nas_phase}. For instance, in MnasNet \cite{mnasnet}, the number of cells and blocks are predefined manually. To further automate the NAS process, Geifman et al. \cite{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 \cite{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 \cite{enas}, which is a reinforcement learning-based leading NAS method. Besides, the work by Yu et al. \cite{eval_nas_phase} also demonstrate that the SOTA NAS techniques are not significantly better than random search.



\subsubsection{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 \cite{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 \cite{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 \cite{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.


\textbf{EA+RL}. Chen et al. \cite{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) \cite{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. 

\textbf{EA+GD}. Yang et al. \cite{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. \cite{cars} only took 0.4 GPU days for searching, which is more efficient than early EA methods (e.g., AmoebaNet \cite{amoebanet} took 3150 GPU days and 450 GPUs for searching). 

\textbf{EA+SMBO}. In \cite{surrogate_evolv}, the authors use the random forest as a surrogate to predict model performance, which accelerates the fitness evaluation in an evolutionary algorithm. 

\textbf{GD+SMBO}. Different from DARTS, which learns weights for candidate operations, NAO \cite{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.

\subsection{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.




\subsubsection{Grid and Random Search}

Figure \ref{fig:grid_random} 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. 

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/grid_random.pdf}
   
   
    \caption{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)$ \cite{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 \cite{hpo_random})}
    \label{fig:grid_random}
\end{figure}

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. \cite{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. \cite{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 \cite{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. \cite{li_hyperband_2016} propose \textit{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.

\subsubsection{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 \cite{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). 

\begin{algorithm}
\caption{Sequential Model-Based Optimization}
\label{alg:SMBO}
\begin{algorithmic}
\STATE $\text{INPUT:} \, f, \Theta, S, \mathcal{M}$
\STATE ${\mathcal{D} \leftarrow \text { INITSAMPLES }(f, \Theta)}$
\FOR {$i$ in $[1,2,..,T]$}
\STATE ${p(y | \theta, \mathcal{D}) \leftarrow \text { FITMODEL }(\mathcal{M}, \mathcal{D})}$
\STATE ${\theta_{i}\leftarrow\arg\max _{\theta\in \Theta} S(\theta, p(y|\theta, \mathcal{D}))}$
\STATE ${y_{i} \leftarrow f\left(\theta_{i}\right)} \,\,  \,\,  \,\, \triangleright \text{Expensive step}$
\STATE $\mathcal{D} \leftarrow \mathcal{D} \cup\left(\theta_{i}, y_{i}\right)$
\ENDFOR
\end{algorithmic}
\end{algorithm}


The steps of SMBO are expressed in Algorithm \ref{alg:SMBO} (adopted from \cite{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:

\begin{enumerate}
    \item The first step is to tune the probabilistic model $\mathcal{M}$ to fit the records dataset $D$.
    \item The acquisition function $\mathcal{S}$ is used to select the next promising neural architecture from the probabilistic model $\mathcal{M}$.
    \item 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.
    \item The records dataset $D$ is updated by appending a new pair of result $(\theta_i,y_i)$.
\end{enumerate}


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 \ref{table:bo_models} 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. \cite{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 \cite{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.


\begin{table}[]
    \centering
    \begin{tabular}{|c|c|}
    \hline
    Library  & Model      \\ \hline
    \makecell{ Spearmint\\ https://github.com/HIPS/Spearmint}   & GP \\\hline
    \makecell{ MOE\\ https://github.com/Yelp/MOE}   &  GP\\\hline
    \makecell{ PyBO\\ https://github.com/mwhoffman/pybo}   & GP \\\hline
    \makecell{ Bayesopt\\ https://github.com/rmcantin/bayesopt}   &GP  \\\hline
    \makecell{ SkGP\\ https://scikit-optimize.github.io}   & GP \\\hline
    \makecell{ GPyOpt\\ http://sheffieldml.github.io/GPyOpt}   & GP \\\hline
    
    \makecell{SMAC      \\ https://github.com/automl/SMAC3}   & RF    \\\hline
    \makecell{Hyperopt  \\ http://hyperopt.github.io/hyperopt} & TPE  \\ \hline
    \makecell{BOHB\\https://github.com/automl/HpBandSter}&TPE \\\hline
\end{tabular}
    \caption{The open-source Bayesian optimization libraries. GP, RF, and TPE represent \textit{Gaussian process} \cite{GP}, \textit{random forests} \cite{smbo_random_forest}, \textit{Tree-structured Parzen Estimator} \cite{alg_hpo}, respectively. }
    \label{table:bo_models}
\end{table}

\subsubsection{Gradient-Based Optimization}


Another group of HPO methods are \textit{gradient-based optimization (GO)} algorithms \cite{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. \cite{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, \cite{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. \cite{forward_gd_hpo} study both the reverse-mode and forward-mode GO methods. The reverse-mode method differs from \cite{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 \cite{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 \cite{kingma2014adam}'s moment coefficient $\beta_1,\beta_2$).



\end{document}

\subsection{NAS performance comparison}

Notably, many NAS studies may propose several neural architecture variants, where each variant is designed for different scenarios (e.g., some architectures perform better but with large size, while some are lightweight for a mobile device but with a performance penalty), so we only report the representative results for each work. Besides, to ensure a valid comparison, we take the accuracy and the algorithm efficiency as comparison indices. As the number and types of GPUs used vary from different studies, we use \textit{GPU Days} to approximate the efficiency, which is defined as:

\begin{equation}
    \text{GPU Days}=N \times D
    \label{eq:gpu_days}
\end{equation}

\noindent where $N$ represents the number of GPUs, and $D$ represents the actual number of days spent searching. 

Table \ref{table:NAS_cifar_perf} and Table \ref{table:NAS_imagenet_perf} present the performance of different NAS studies on CIFAR-10 and ImageNet, respectively. Besides, since most NAS methods first search for the neural architecture based on a small dataset (CIFAR-10), then transfer the architecture to a larger dataset (ImageNet), the search time for both datasets may be the same. It can be seen from the table that the early work of EA and RL based NAS methods pay more attention to high performance, regardless of the resource consumption. For example, although AmoebaNet \cite{amoebanet} achieved excellent results on both CIFAR-10 and ImageNet, it took 3,150 GPU days with 450 GPUs for searching. The subsequent NAS studies make efforts to improve searching efficiency while ensuring the searched model's high performance. For instance, EENA \cite{eena} elaborately designs the mutation and crossover operations, which can reuse the learned information to guide the evolution process and hence greatly improve the efficiency of EA-based NAS method. ENAS \cite{enas} is one of the first RL-based NAS methods to propose the parameter-sharing strategy, which reduces the number of GPU budgets to 1 and shortens the searching time to less than one day. We also observe that gradient descent-based architecture optimization methods can greatly reduce computational resource consumption for searching and achieve SOTA results. A lot of follow-up work is to make further improvement and optimization in this direction. Interestingly, random search-based methods can also obtain comparable results. The authors of \cite{nas_random} demonstrate that random search with weight-sharing can outperform a series of powerful methods, such as ENAS \cite{enas} and DARTS \cite{darts_liu18}. 


\subsubsection{Kendall Tau metric}

Since random search is comparable to those more sophisticated methods (e.g., DARTS and ENAS), one natural question is: what are the advantages and significance of the other architecture optimization algorithms compared with the random search? The researchers try to use other metrics to answer this question, not just considering the final accuracy of the model. Most NAS methods consist of two stages: 1) search for a best-performing architecture on the training set; 2) then expand it to a deeper one and estimate it on the validation set. However, there usually exists a large gap between the two stages. In other words, the architecture that achieves the best result in the training set is not necessarily the best one on the validation set. Therefore, instead of merely considering the final accuracy and search time cost, many NAS studies \cite{hu2020dsnas,istrate2018tapas,nsas,eval_nas_phase,nas_eval} make use of Kendall Tau ($\tau$) metric \cite{kendall_tau} to measure the correlation of the model performance between the search and estimation stages. The value of $\tau$ is defined as:

\begin{equation}
    \tau=\frac{N_C-N_D}{N_C+N_D}
\end{equation}

\noindent where $N_C$ and $N_D$ indicate the number of concordant and discordant pairs. $\tau$ is a number in the range [-1,1] with the following properties:

\begin{itemize}
    \item $\tau=1$: two rankings are identical
    \item $\tau=-1$: two rankings are completely opposite.
    \item $\tau=0$: there is no relationship between two rankings.
\end{itemize}



\begin{figure}
    \centering
    \subfigure[Two-stage NAS consists of the searching stage and evaluation stage. The best-performing model of the searching stage will be further retrained in the evaluation stage.]{\includegraphics[width=0.48\textwidth]{images/two-stage.pdf}}
    \subfigure[One-stage NAS can directly deploy a well-performing model without extra retraining or fine-tuning. The two-way arrow indicates that the process of architecture optimization and parameter training run simultaneously. ]{\includegraphics[width=0.48\textwidth]{images/one-stage.pdf}}
    \caption{Illustration of two-stage and one-stage NAS flow.}
    \label{fig:nas_stage}
\end{figure}

\subsubsection{NAS-Bench Dataset}


Although Table \ref{table:NAS_cifar_perf} and Table \ref{table:NAS_imagenet_perf} presents a clear comparison between different NAS methods, the results of different methods are obtained under different settings, such as training-related hyper-parameters (e.g., batch size and training epochs), data augmentation (e.g., Cutout \cite{cutout}). In other words, the comparison is not quite fair. In this context, NAS-Bench-101 \cite{ying2019nasbench} is a pioneering work to alleviate the problem of non-reproducibility. It provides a tabular dataset that contains 423,624 unique neural networks, which are generated and evaluated from a fixed graph-based search space, and mapped to their trained and evaluated performance on CIFAR-10. Besides, Dong et al. \cite{nasbench201} further build NAS-Bench-201, which is an extension to NAS-Bench-101 and has different search space, results on multiple datasets (CIFAR-10, CIFAR-100, and ImageNet-16-120 \cite{imagenet_variants}), and more diagnostic information. Similarly, Klyuchnikov et al. \cite{nasbenchnlp} propose a NAS-Bench for the NLP task. These datasets enable NAS researchers to focus solely on verifying the effectiveness and efficiency of their proposed architecture optimization algorithms, avoiding repetitive training for selected architectures, and greatly helping the NAS community develop.

\subsection{One-stage vs. Two-stage}

The NAS methods can be roughly divided into two classes according to the flow: two-stage and one-stage, as shown in Figure \ref{fig:nas_stage}.

\textbf{Two-stage NAS} consists of the \textit{searching stage} and \textit{evaluation stage}. The \textit{searching stage} involves architecture optimization and parameter training. The simplest idea is to train all possible architectures from scratch and then choose the optimal one. However, it requires many resources (e.g., NAS-RL \cite{nas_rl_zoph16} took 22,400 GPU days with 800 K40 GPUs for searching) infeasible for most companies and institutes. Therefore, most NAS methods (such as ENAS \cite{enas} and DARTS \cite{darts_liu18}) sample and train a large number of candidate architectures in the searching stage, and then the best-performing one will be further retrained in the evaluation stage.

\textbf{One-stage NAS} refers to a class of NAS methods that can export a well-designed and well-trained neural architecture without extra retraining by running architecture optimization and parameter training simultaneously. In this way, it can greatly improve efficiency. However, it is currently the main challenge of any general NAS problem. Several recent studies  \cite{OFA,yoso,yu2020bignas,atomnas} have tried to overcome this challenge. For instance, in \cite{OFA}, the authors propose \textit{progressive shrinking} algorithm to post-process the weights after training is finished. Specifically, they first pre-train the full neural network, then progressively fine-tune the smaller networks that share weights with the full network. Based on well-designed constraints, the performance of all sub-networks is guaranteed. Thus, given a target deployment device, a specialized sub-network can be directly exported without fine-tuning. However, \cite{OFA} still requires many computational resources, as the whole process took 1,200 GPU hours with V100 GPUs. BigNAS \cite{yu2020bignas} revisits conventional training techniques of stand-alone networks, and empirically proposes several techniques to handle a wider set of models, ranging in size from 200M FLOPs to 1G FLOPs, while \cite{OFA} only handles models under 600M FLOPs. Both AtomNAS \cite{atomnas} and DSNAS \cite{hu2020dsnas} propose an end-to-end one-stage NAS framework to further boost the performance and simplify the flow.




\subsection{One-shot/Weight-sharing}




\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/one-shot.pdf}
    \caption{(Left) One-shot models. (Right) Non one-shot models. Each circle indicates a different model, and the area of the circle indicates the size of the model. We use concentric circles to represent one-shot models, as they share the weights with each other.}
    \label{fig:one-shot}
\end{figure}


\textbf{One-shot$\neq$one-stage.} We need to know that one-shot is not exactly equivalent to one-stage. As mentioned above, we divide NAS studies into one-stage and two-stage methods according to the flow (Figure \ref{fig:nas_stage}), while whether a NAS algorithm belongs to the one-shot method or not depends on whether candidate architectures share the same weights (Figure \ref{fig:one-shot}). We observe that most of one-stage NAS methods are based on one-shot paradigm. 

\textbf{ What is One-shot NAS?} One-shot NAS methods embeds the search space into an over-parameterized supernet. As a result, all possible architectures can be derived from the supernet. Figure \ref{fig:nas_stage} shows the difference between the search space of one-shot and non-one-shot NAS. Each circle indicates a different architecture, where the architectures of one-shot NAS methods share the same weights among each other. One-shot NAS methods can be divided into two categories, which differ in how to handle architecture optimization and weights training: coupled and decoupled optimization \cite{chu2019fairnas,you2020greedynas}.

\textbf{Coupled optimization.} The first category of one-shot NAS methods optimizes the architecture and weights in a coupled manner \cite{enas,darts_liu18,gdas,proxylessnas,snas}. For instance, ENAS \cite{enas} proposes to use an LSTM network to discretely sample a new architecture, and then uses a few batches of the training data to optimize the weight of this architecture. After repeating the above steps many times, a collection of architectures and their corresponding performance will be recorded. Finally, the best-performing architecture is selected for further retraining. DARTS \cite{darts_liu18} also uses a similar weight sharing strategy, but the architecture distribution is continuously parameterized. The supernet contains all candidate operations, each with learnable parameters. The best architecture can be directly derived from the distribution. However, since DARTS \cite{darts_liu18} directly optimizes the supernet weights and the architecture distribution, it suffers from the vast GPU memory consumption. Although DARTS-like methods \cite{proxylessnas,gdas, snas} have proposed different approaches to reduce resource requirements, coupled optimization inevitably introduces a bias in both architecture distribution and supernet weights \cite{singlepath_nas,chu2019fairnas}, as they treat all sub-networks unequally. Specifically, the quickly-converged architectures can easily obtain more chances to be optimized \cite{darts_liu18,darts+}, and those architectures are only a small portion of the whole candidates; therefore, it is very harsh to find the best-architecture. 

Another disadvantage of coupling optimization is that when new architectures are sampled and trained continuously, the weights of previous architectures will be negatively impacted, leading to performance degradation. \cite{multimodel_forget} defines this phenomenon as \textit{multi-model forgetting}. To overcome this problem, Zhang et al. \cite{oneshot_forget} model the supernet training as a constrained optimization problem of continual learning, and propose \textit{novel search based architecture selection} (NSAS) loss function. They apply the proposed method to RandomNAS \cite{nas_random} and GDAS \cite{gdas}, and the experimental result demonstrates that the method is effective to reduce the multi-model forgetting and boost the predictive ability of the supernet as an evaluator.


\textbf{Decoupled optimization}. The second category of one-shot NAS methods \cite{oneshot_self,under_oneshot,chu2019fairnas,OFA} solves the problem of above one-shot methods by decoupling the optimization of architecture and weights into two sequential phases: 1) training the supernet; 2) using the trained supernet as a predictive performance estimator of different architectures to select the most promising architecture. 



In terms of the phase of supernet training, the supernet cannot be directly trained like a regular neural network, because \textit{the weights of the supernet are also deeply coupled} \cite{singlepath_nas}. The work by Yu et al. \cite{eval_nas_phase} experimentally shows that weight sharing strategy harms the individual architecture's performance and negatively impacts the real performance ranking of the candidate architectures. To reduce weight coupling, many one-shot NAS methods \cite{singlepath_nas,oneshot_self,smash_onehot,GHN} propose the random sampling policy, which uniformly randomly samples an architecture from the supernet, and only the weights of this architecture are activated and optimized. RandomNAS \cite{nas_random} also demonstrates that a random search policy is a competitive baseline method. Although the strategy of sampling and training only one path of the supernet each time is already adopted in previous one-shot approaches \cite{gdas,enas,snas,proxylessnas,fbnet}, they sample the path according to RL controller \cite{enas}, Gumbel Softmax \cite{gdas,snas,fbnet}, or BinaryConnect network \cite{proxylessnas}, which instead highly couples the architecture and supernet weights. SMASH \cite{smash_onehot} proposes an auxiliary hypernetwork to generate the weights for randomly sampled architectures. Similarly, Zhang et al. \cite{GHN} propose a computation graph representation, and use the graph hypernetwork (GHN) to predict the weights for all possible architectures faster and more accurately than regular hypernetworks (SMASH \cite{smash_onehot}). However, Bender et al. \cite{under_oneshot} conduct a careful experimental analysis to understand the mechanism of weight sharing strategy, and show that neither a hypernetwork nor an RL controller is required to find the optimal architecture. In \cite{under_oneshot}, the authors propose a \textit{path dropout} strategy to alleviate the problem of weight coupling. During training the supernet, each path of the supernet is randomly dropped with gradually increasing probability. GreedyNAS \cite{you2020greedynas} propose a multi-path sampling strategy to train the greedy supernet. The strategy can focus on more potentially-good paths, and is demonstrated to be effective in achieving a fairly high rank correlation of candidate architectures compared with random search.



The second phase involves how to select the most promising architecture from the trained supernet, which is the primary purpose of most NAS tasks. Both SMASH \cite{smash_onehot} and \cite{under_oneshot} randomly select a set of architectures from the supernet, and rank them according to their performance. SMASH can obtain the validation performance of all selected architectures at the cost of a single training run for each architecture, as these architectures are assigned with the weights generated by the hypernetwork. Besides, \cite{under_oneshot} observe that the architectures with smaller symmetrized KL divergence value are more likely to perform better. The equation is as follows:

\begin{equation}
\begin{split}
    D_{\mathrm{SKL}} = D_{\mathrm{KL}}(p \| q)+D_{\mathrm{KL}}(q \| p) \\
   s.t. \,\, D_{\mathrm{KL}}(p \| q) =\sum_{i=1}^{n} p_{i} \log \frac{p_{i}}{q_{i}}
\end{split}
\end{equation}


\noindent where $(p_1,...,p_n)$ and $q_1,...,q_n$ indicates the prediction of the sampled architecture and one-shot model, and $n$ is the number of classes. The cost of calculating the KL value is very small; in \cite{under_oneshot}, only 64 random training data examples are used. Evolutionary algorithm (EA) is also a promising search solution \cite{singlepath_nas,you2020greedynas}. For instance, SPOS \cite{singlepath_nas} makes use of EA to search for architectures from the supernet. It is more efficient than the EA methods introduced in Section \ref{section:model_generation}, because each sampled architecture only performs inference. Self-Evaluated Template Network (SETN) \cite{oneshot_self} proposes an \textit{estimator} to predict the probability of each architecture being likely to have a lower validation loss. The experimental results show that SETN can potentially find the architecture with better performance than random search based methods \cite{under_oneshot,smash_onehot}.


\subsection{Joint Hyper-parameter and Architecture Optimization}

Most NAS methods fix the same setting of training-related hyper-parameters during the whole search stage. After the search, the hyper-parameters of the best-performing architecture will be further optimized. However, this paradigm may result in sub-optimal results as different architectures tend to fit different hyper-parameters, making the ranking of the models unfair \cite{dong2020autohas}. Therefore, a promising solution is the joint \textit{hyper-parameter and architecture optimization (HAO)} \cite{towards_nas_hpo,tabular_hao,dong2020autohas,dai2020fbnetv3}. For instance, Zela et al. \cite{towards_nas_hpo} casts NAS as a hyperparameter optimization problem. In this way, the search spaces of NAS and standard hyper-parameters are combined, and BOHB \cite{bohb}, an efficient HPO method, is applied to optimize the architecture and hyper-parameters jointly. Similarly, Dong et al. \cite{dong2020autohas} propose a differentiable method, namely AutoHAS, which builds a Cartesian product of the search spaces of both NAS and HPO by unifying the representation of all candidate choices for architecture (e.g., the number of layers) and hyper-parameters (e.g., learning rate). The challenge is that the candidate choices for architecture search space are usually categorical, while hyper-parameters choices can be categorical (e.g., the type of optimizer) and continuous (e.g., learning rate). To overcome this challenge, AutoHAS discretizes the continuous
hyperparameters into a linear combination of multiple categorical bases. For example, the categorical bases for the learning rate are $\{0.1,0.2,0.3\}$, then the final learning rate is defined as $lr=w_1\times 0.1+w_2\times 0.2+w_3\times 0.3$. FBNetv3 \cite{dai2020fbnetv3} also proposes to jointly search both architectures and the corresponding training recipes (i.e., hyper-parameters). The architectures are represented with one-hot categorical variables and integral (min-max normalized) range variables, and the representation is fed to an encoder network to generate the architecture embedding. Then the concatenation of architecture embedding and the training hyper-parameters is used to train the accuracy predictor, which will be applied to search for promising architectures and hyper-parameters at the later stage.


\end{document}

\subsection{Flexible Search Space}

As summarized in Section \ref{section:model_generation}, there are several types of search spaces, where the primitive operations can be roughly classified into pooling and convolution. Some even use a more complex module (MBConv \cite{mnasnet}) as the primitive operation. Although these search spaces have been proven effective to generate well-performing neural architectures, they all based on human knowledge and experience, which inevitably introduces human bias and hence still does not break away from the human design paradigm. AutoML-Zero \cite{real2020automlzero} uses very simple mathematical operations (e.g., $\cos,\sin,\text{mean,std}$) as the primitive operations of the search space to minimize the human bias, and applies the evolutionary algorithm to discover complete machine learning algorithms. AutoML-Zero successfully designs two-layer neural networks based on those basic mathematical operations. Although the network searched by AutoML-Zero is much simpler compared to both human-designed and NAS-designed networks, the experimental results show the potential to discover a new model design paradigm with minimal human design. Therefore, how to design a more general, flexible, and free of human bias search space and how to discover novel neural architectures based on this search space would be challenging and advantageous.



\subsection{Applying NAS to More Areas}

 

As described in Section \ref{section:nas_performance}, the models designed by NAS algorithms have achieved comparable results in image classification tasks (CIFAR-10 and ImageNet) to manually-designed models. Additionally, many recent studies have also applied NAS to other CV tasks (shown in Table \ref{table:nas_apps}). 

However, in terms of the NLP task, most NAS studies only implement experiments on the PTB dataset. Besides, a few NAS studies also try to apply NAS to other NLP tasks (shown in Table \ref{table:nas_apps}). However, as Figure \ref{fig:auto_vs_manual} shows, there is still a large gap between the performance of NAS-designed models (\cite{enas,darts_liu18,nas_rl_zoph16}) and human-designed models (GPT-2 \cite{GPT}, FRAGE AWD-LSTM-Mos \cite{frage}, adversarial AWD-LSTM-Mos \cite{adversarial_awd} and Transformer-XL \cite{transformerxl}) on the PTB dataset. Therefore, the NAS community still has a long way to go to achieve comparable results to those models designed by experts on NLP tasks.

In addition to the CV and NLP tasks, Table \ref{table:nas_apps} also shows that NAS has been applied to a variety of tasks, such as network compression, federate learning, image caption, recommendation system, and even searching for loss function. Therefore, these interesting work also indicates the potential for NAS to be applied in other fields.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.48\textwidth]{images/ptb_nas_human.pdf}
    \caption{The SOTA models on the PTB dataset. The lower the perplexity, the better the performance. The green bar represents the automatically generated model, and the yellow bar represents the model designed by human experts. Best viewed in color.}
    \label{fig:auto_vs_manual}
\end{figure}






\subsection{Interpretability}

Although AutoML algorithms can find promising configuration settings more efficiently than humans, there is a lack of scientific evidence to illustrate why the found settings perform better. For example, in BlockQNN \cite{blockqnn}, it's not clear why the NAS algorithm tends to select the ‘‘Concatenation’’ operation to process the output of each block in the cell, instead of the element-wise addition operation. Some recent studies \cite{under_oneshot,under_das,wong2016understanding} The explanation for these occurrences is usually hindsight and lacks rigorous mathematical proof. Therefore, increasing the mathematical interpretability of AutoML is also an important future research direction.


\subsection{Reproducibility}

It is well known that a major challenge with ML is reproducibility. AutoML is no exception, especially for NAS, because most of the existing NAS algorithms still have many parameters that need to be set manually at the implementation level, but the original papers do not cover too much detail. For instance, Yang et al. \cite{nas_eval} experimentally demonstrate that the seed plays an important role in NAS experiments, while most NAS methods didn't mention the seed set by their experiments in the papers. Besides, huge resource consumption is another obstacle to reproduction. In this context, several NAS-Bench datasets are proposed, such as NAS-Bench-101 \cite{ying2019nasbench}, NAS-Bench-201 \cite{nasbench201}, and NAS-Bench-NLP \cite{nasbenchnlp}. These datasets allow NAS researchers to focus on the design of optimization algorithms without wasting a lot of time on model estimation.


\subsection{Robustness}

NAS has been proven effective in searching for promising architectures on many open datasets (e.g., CIFAR-10 and ImageNet). Those datasets are usually for the research purpose; therefore, most of the images are well-labeled. However, in real-world situations, the data inevitably contains noise (e.g., mislabeling and inadequate information). Even worse, the data might be modified to be adversarial data with carefully designed noises. Deep learning models are easily fooled by adversarial data, and so is NAS. Currently, there are a few studies \cite{is_nas_robust,NAS_Meets_Robustness,Chen2020OnRO,vargas2019evolving} making efforts to boost the robustness of NAS against adversarial data. Guo et al. \cite{NAS_Meets_Robustness} experimentally explore the intrinsic impact of network architectures on network robustness against adversarial attacks, and observe that densely connected architectures tend to be more robust. They also find that the flow of solution procedure (FSP) matrix \cite{FSP_matrix} is a good indicator of network robustness, i.e., the lower the FSP matrix loss more robust the network is. Chen et al. \cite{Chen2020OnRO} propose a robust loss function to alleviate the performance degradation under symmetric label noise effectively. In \cite{vargas2019evolving}, the authors adopt an evolutionary algorithm to search for robust architectures from a well-designed and vast search space, where many types of adversarial attacks are used as the fitness function to evaluate the robustness of neural architectures.


\subsection{Joint Hyperparameter and Architecture Optimization}

Most NAS studies consider hyperparameter optimization (HPO) and architecture optimization (AO) as two separate processes. However, as noted already in Section \ref{section:model_generation}, there is a tremendous overlap between the methods used in HPO and AO, e.g., both of them apply random search, Bayesian optimization, and gradient-based optimization methods. In other words, it would be feasible to jointly optimize both hyperparameters and architectures. Several studies \cite{tabular_hao,dong2020autohas,dai2020fbnetv3} also confirm this possibility experimentally. Thus, how to solve the problem of joint hyperparameter and architecture optimization (HAO) elegantly is a worthy studying issue.


\subsection{Complete AutoML Pipeline}

There are already many AutoML pipeline libraries proposed, but most of them only focus on some parts of the AutoML pipeline (Figure \ref{fig:pipeline_details}). For instance, TPOT \cite{Olson2016EvoBio}, Auto-WEAK \cite{auto_weak}, and Auto-Sklearn \cite{eff_automl_nips15} are built on top of scikit-learn \cite{sklearn} for building classification and regression pipelines, but they only search for the traditional ML models (like SVM and KNN). Although TPOT involves neural networks (using Pytorch \cite{PyTorch} backend), it only supports a multi-layer perception network. Besides, Auto-Keras \cite{autokeras} is an open-source library developed based on Keras \cite{Keras}. It focuses more on searching for deep learning models and supports multi-modal and multi-task. NNI \cite{nni} is a more powerful toolkit of AutoML, as its built-in capability contains automated feature engineering, hyper-parameter optimization, and neural architecture search. Additionally, the NAS module in NNI supports both Pytorch \cite{PyTorch} and Tensorflow \cite{abadi2016tensorflow} and reproduces many SOTA NAS methods \cite{enas,darts_liu18,proxylessnas,pdarts,singlepath_nas,nas_random,ying2019nasbench}, which is very friendly for NAS researcher and developer. Besides, NNI also integrates the features of scikit-learn \cite{sklearn}, which is one step closer to achieving a complete pipeline. Similarly, Vega \cite{vega} is another AutoML algorithm tool, which constructs a complete pipeline covering a set of highly decoupled functions: data augmentation, HPO, NAS, model compression, and fully train. In a word, designing an easy-to-use and complete AutoML pipeline system is a promising research direction.
 





\subsection{Lifelong Learning}

Last but not least, most AutoML algorithms focus only on solving a specific task on some fixed datasets, e.g., image classification on CIFAR-10 and ImageNet. However, a high-quality AutoML system should have the capability of lifelong learning, i.e., it can 1) efficiently \textbf{learn new data}; 2) meanwhile \textbf{remember old knowledge}.


\subsubsection{Learn new data}



Firstly, the system should be able to reuse prior knowledge to solve new tasks (i.e., learning to learn). For example, a child can quickly identify tigers, rabbits, and elephants after seeing several pictures of these animals, but current DL models must be trained on a large number of data before they can correctly identify images. A hot topic in this area is meta-learning, which aims to design models for new tasks using previous experience.

\textbf{Meta-learning.} Most of the existing NAS methods can search a well-performing architecture for a single task. However, for the new task, they have to search for a new architecture; otherwise, the old architecture might not be optimal. Several studies \cite{continual_nas,Auto-meta,transferNAS,meta_NAS_fewshot} combine meta-learning and NAS to solve this problem. A recent work by Lian et al. \cite{transferNAS} proposes a novel and meta-learning based \textit{transferable neural architecture search (T-NAS)} method to generate a meta-architecture, which can be adapted to new tasks easily and quickly through a few gradient steps. Another challenge of learning new data is few-shot learning scenarios, where there is only a limited number of data for the new tasks. \cite{Auto-meta} and \cite{continual_nas} apply NAS to few-shot learning to overcome this challenge, while they only search for the most promising architecture and optimize it to work on multiple few-shot learning tasks. Elsken et al. \cite{meta_NAS_fewshot} propose a gradient-based meta-learning NAS method, namely METANAS, which can generate \textit{task-specific} architectures more efficiently as it does not require meta-retraining.


\textbf{Unsupervised learning.} Meta-learning based NAS methods focus more on labeled data, while in some cases, only a portion of the data may have labels or even none at all. Liu et al. \cite{UnNAS} propose a general problem setup, namely \textit{unsupervised neural architecture search (UnNAS)}, to explore whether labels are necessary for NAS. They experimentally demonstrate that the architectures searched without labels are competitive with those searched with labels; therefore, the results show that labels are not necessary for NAS and provoke people to think about what exactly affects NAS.


\subsubsection{Remember old knowledge}

In addition, an AutoML system must be able to constantly acquire and learn from new data, without forgetting the knowledge from old data. However, when we use new datasets to train a pretrained model, the performance of the model on the previous data sets will be greatly reduced. Incremental learning may alleviate this problem. For example, Li and Hoiem \cite{lwf} propose the \textit{learning without forgetting} (LwF) method, which trains the model using only new data, while preserving its original capabilities. In addition, iCaRL \cite{icarl} makes progress based on LwF. It only uses a small part of old data for pretraining, and then gradually increases the proportion of a new class of data that is used to train the model.



\end{document}

\section{Introduction}\label{section:introduction}
\subfile{introduction}



\section{Data Preparation}\label{section:data_preparation}
\subfile{data_preparation}


\section{Feature Engineering}
\label{section:feature_engineering}
\subfile{feature_engineering}



\section{Model Generation}\label{section:model_generation}
\subfile{model_generation}


\section{Model Estimation}\label{section:model_estimation}
\subfile{model_estimation}




\section{NAS Performance Summary}\label{section:nas_performance}
\subfile{nas_performance}



\section{Open Problems and Future Work}\label{section:open_problems}
\subfile{open_problems}


\section{Conclusions}\label{section:conclusion}
\subfile{conclusion}



\bibliographystyle{elsarticle-num} 


\subsection{Data Collection}

ML's deepening study has led to a consensus that good data must be available; as a result, numerous open datasets have emerged. In the early stages of ML's study, a handwritten digital dataset, i.e., MNIST \cite{mnist}, was developed. After that, several larger datasets like CIFAR-10 and CIFAR-100 \cite{cifar10} and ImageNet \cite{imagenet} were also developed. A variety of datasets can also be retrieved by entering the keywords into these websites: Kaggle \footnote{https://www.kaggle.com}, Google Dataset Search (GOODS) \footnote{https://datasetsearch.research.google.com/}, and Elsevier Data Search \footnote{https://www.datasearch.elsevier.com/}. 

However, it is usually challenging to find a proper dataset through the above approaches for some particular tasks, such as those related to medical care or other private matters. Two types of methods are proposed to solve this problem: data searching and data synthesis. 

\subsubsection{Data Searching}

As the Internet is an inexhaustible source of data, searching for Web data is an intuitive way to collect a dataset \cite{filter_web_data,chen2013neil,xia2014well,do2015automatic}. However, there are some problems with using Web data. 

First, the search results may not exactly match the keywords. Thus, unrelated data must be filtered. For example, Krause et al. \cite{krause2016unreasonable} separate inaccurate results as cross-domain or cross-category noise, and remove any images that appear in search results for more than one category. Vo et al. \cite{vo2017harnessing} re-rank relevant results and provide search results linearly, according to keywords. 

Second, Web data may be incorrectly labeled or even unlabeled. A learning-based self-labeling method is often used to solve this problem. For example, the active learning method \cite{collins2008towards} selects the most ‘‘uncertain'' unlabeled individual examples for labeling by a human, and then iteratively labels the remaining data. Roh et al. \cite{survey_data_collect} provide a review of semi-supervised learning self-labeling methods, which can help take the human out of the loop of labeling to improve efficiency, and can be divided into the following categories: self-training \cite{yarowsky1995unsupervised, triguero2014characterization}, co-training \cite{hady2010combining, blum1998combining}, and co-learning \cite{democratic_co_learn}. Moreover, due to the complexity of Web images content, a single label cannot adequately describe an image. Consequently, Yang et al. \cite{filter_web_data} assign multiple labels to a Web image, i.e., if the confidence scores of these labels are very close or the label with the highest score is the same as the original label of the image, then this image will be set as a new training sample.

However, the distribution of Web data can be extremely different from that of the target dataset, which will increase the difficulty of training the model. A common solution is to fine-tune these Web data \cite{chen2015webly,xu2015augmenting}. Yang et al. \cite{filter_web_data} propose an iterative algorithm for model training and Web data-filtering. Dataset imbalance is another common problem, as some special classes have a very limited number of Web data. To solve this problem, the synthetic minority over-sampling technique (SMOTE) \cite{chawla2002smote} is used to synthesize new minority samples between existing real minority samples, instead of simply up-sampling minority samples or down-sampling the majority samples. In another approach, Guo et al. \cite{guo2004learning} combine the boosting method with data generation to enhance the generalizability and robustness of the model against imbalanced data sets.

\subsubsection{Data Synthesis}

Data simulator is one of the most commonly used methods to generate data. For some particular tasks, such as autonomous driving, it is not possible to test and adjust a model in the real world during the research phase, due to safety hazards. Therefore, a practical approach to generating data is to use a data simulator that matches the real world as closely as possible. OpenAI Gym \cite{openai_gym} is a popular toolkit that provides various simulation environments, in which developers can concentrate on designing their algorithms, instead of struggling to generate data. Wang et al. \cite{irs} use a popular game engine, Unreal Engine 4, to build a large synthetic indoor robotics stereo (IRS) dataset, which provides the information for disparity and surface normal estimation. Furthermore, a reinforcement learning-based method is applied in \cite{ruiz2018learning} for optimizing the parameters of a data simulator to control the distribution of the synthesized data.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.3\textwidth]{GAN_image.png}
    \caption{The examples of human face images generated by GAN \cite{karras2018style}.}
    \label{fig:GAN}
\end{figure}

Another novel technique for derive synthetic data is \textit{Generative Adversarial Networks} (GANs) \cite{goodfellow2014generative}, which can be used to generate images \cite{goodfellow2014generative,oh2018learning,rendergan,gan_aug}, tabular \cite{table_gan, tabular_gan} and text \cite{text_gan_no_RL} data. Figure \ref{fig:GAN} shows some human face images, which are generated by GAN in the work of Karras et al. \cite{karras2018style}. Oh and Jaroensri et al. \cite{oh2018learning} build a synthetic dataset, which captures small motion for video-motion magnification. Bowles et al. \cite{gan_aug} demonstrate the feasibility of using GAN to generate medical images for brain segmentation tasks. In the case of textual data, applying GAN to text has proved difficult because the commonly used method is to use reinforcement learning to update the gradient of the generator, but the text is discrete, and thus the gradient cannot propagate from discriminator to generator. To solve this problem, Donahue et al. \cite{text_gan_no_RL} use an autoencoder to encode sentences into a smooth sentence representation to remove the barrier of reinforcement learning. Park et al. \cite{table_gan} apply GAN to synthesize fake tables that are statistically similar to the original table but do not cause information leakage. Similarly, in \cite{tabular_gan}, GAN is applied to generate tabular data like medical or educational records.



\subsection{Data Cleaning}

The collected data inevitably have noise, but the noise can negatively affect the training of the model. Therefore, the process of data cleaning \cite{dc_survey, jesmeen2018survey} must be carried out if necessary. Across the literature, the effort of data cleaning is shifting from crowdsourcing to automation. Traditionally, data cleaning requires specialist knowledge, but access to specialists is limited and generally expensive. Hence, Chu et al. \cite{katara} propose Katara, a knowledge-based and crowd-powered data cleaning system. To improve efficiency, some methods \cite{sampleclean, activeclean} propose only to clean a small subset of the data and maintain comparable results to the case of cleaning the full dataset. However, these methods require a data scientist to design what data cleaning operations are applied to the dataset. BoostClean \cite{boostclean} attempts to automate this process by treating it as a boosting problem. Each data cleaning operation effectively adds a new cleaning operation to the input of the downstream ML model, and through a combination of Boosting and feature selection, a good series of cleaning operations, which can well improve the performance of the ML model, can be generated. AlphaClean \cite{alphaclean} transforms data cleaning into a hyper-parameter optimization problem, which further increases automation. Specifically, the final data cleaning combinatorial operation in AlphaClean is composed of several pipelined cleaning operations that need to be searched from a predefined search space. Gemp et al. 

The data cleaning methods mentioned above are applied to a fixed dataset. However, the real world generates vast amounts of data every day. In other words, how to clean data in a continuous process becomes a worth studying problem, especially for enterprises. Ilyas et al. \cite{eval_continuous_dc} propose an effective way of evaluating the algorithms of continuously cleaning data. Mahdavi et al. \cite{auto_dc_workflow} build a cleaning workflow orchestrator, which can learn from previous cleaning tasks, and propose promising cleaning workflows for new datasets.



\subsection{Data Augmentation}


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/data_augmentation.png}
    \caption{A classification of data augmentation techniques.}
    \label{fig:data_augmentation}
\end{figure}

To some degree, data augmentation (DA) can also be regarded as a tool for data collection, as it can generate new data based on the existing data. However, DA also serves as a regularizer to avoid over-fitting of model training and has received more and more attention. Therefore, we introduce DA as a separate part of data preparation in detail. Figure \ref{fig:data_augmentation} classifies DA techniques from the perspective of data type (image, audio, and text), and incorporates automatic DA techniques that have recently received much attention. 

For image data, the affine transformations include rotation, scaling, random cropping, and reflection; the elastic transformations contain the operations like contrast shift, brightness shift, blurring, and channel shuffle; the advanced transformations involve random erasing, image blending, cutout \cite{cutout}, and mixup \cite{mixup}, etc. These three types of common transformations are available in some open source libraries, like torchvision \footnote{https://pytorch.org/docs/stable/torchvision/transforms.html}, ImageAug \cite{imgaug}, and Albumentations \cite{albumentations}. In terms of neural-based transformations, it can be divided into three categories: adversarial noise \cite{aug_an}, neural style transfer \cite{st_aug}, and GAN technique \cite{aug_gan}. For textual data, Wong et al. \cite{wong2016understanding} propose two approaches for creating additional training examples: data warping and synthetic over-sampling. The former generates additional samples by applying transformations to data-space, and the latter creates additional samples in feature-space. Textual data can be augmented by synonym insertion or by first translating the text into a foreign language and then translating it back to the original language. In a recent study, Xie et al. \cite{xie2017data} propose a non-domain-specific DA policy that uses noising in RNNs, and this approach works well for the tasks of language modeling and machine translation. Yu et al. \cite{yu2018qanet} propose the use of back-translation for DA to aid reading comprehension. NLPAug \cite{nlp_aug} is an open-source library that integrates many types of augmentation operations for both textual and audio data.

The above augmentation techniques still require human to select augmentation operations and then form a specific DA policy for specific tasks, which requires much expertise and time. Recently, there are many methods \cite{cubuk2019autoaugment,dada,fasteraa,fastaa,greedy_aa,population_aa,aug_policy,rs_aug,adv_aug,online_aug,uniform_aug} proposed to search for augmentation policy for different tasks. AutoAugment \cite{cubuk2019autoaugment} is a pioneering work to automate the search for optimal DA policies using reinforcement learning. However, AutoAugment is not efficient as it takes almost 500 GPU hours for one augmentation search. In order to improve search efficiency, a number of improved algorithms have subsequently been proposed using different search strategies, such as gradient descent-based \cite{dada,fasteraa}, Bayesian-based optimization \cite{fastaa}, online hyper-parameter learning \cite{online_aug}, greedy-based search \cite{greedy_aa} and random search \cite{rs_aug}. Besides, LingChen et al. \cite{uniform_aug} propose a search-free DA method, namely UniformAugment, by assuming that the augmentation space is approximately distribution invariant.
\end{document}

\subsection{Feature Selection}

Feature selection builds a feature subset based on the original feature set by reducing irrelevant or redundant features. This tends to simplify the model, hence avoiding overfitting and improving model performance. The selected features are usually divergent and highly correlated with object values. According to \cite{dash1997feature}, there are four basic steps in a typical process of feature selection (see Figure \ref{fig:fe_process}), as follows:

\begin{figure}[ht]
    \centering
   
    \includegraphics[width=0.3\textwidth]{images/feature_selection.pdf}
    \caption{The iterative process of feature selection. A subset of features is selected, based on a search strategy, and then evaluated. Then, a validation procedure is implemented to determine whether the subset is valid. The above steps are repeated until the stop criterion is satisfied.}
    \label{fig:fe_process}
\end{figure}

The search strategy for feature selection involves three types of algorithms: complete search, heuristic search, and random search. Complete search comprises exhaustive and non-exhaustive searching; the latter can be further split into four methods: breadth-first search, branch and bound search, beam search, and best-first search. Heuristic search comprises sequential forward selection (SFS), sequential backward selection (SBS), and bidirectional search (BS). In SFS and SBS, the features are added from an empty set or removed from a full set, respectively, whereas BS uses both SFS and SBS to search until these two algorithms obtain the same subset. The most commonly used random search methods are simulated annealing (SA) and genetic algorithms (GAs).

Methods of subset evaluation can be divided into three different categories. The first is the filter method, which scores each feature according to its divergence or correlation and then selects features according to a threshold. Commonly used scoring criteria for each feature are variance, the correlation coefficient, the chi-square test, and mutual information. The second is the wrapper method, which classifies the sample set with the selected feature subset, after which the classification accuracy is used as the criterion to measure the quality of the feature subset. The third method is the embedded method, in which variable selection is performed as part of the learning procedure. Regularization, decision tree, and deep learning are all embedded methods.




\subsection{Feature Construction}


Feature construction is a process that constructs new features from the basic feature space or raw data to enhance the robustness and generalizability of the model. Essentially, this is done to increase the representative ability of the original features. This process is traditionally highly dependent on human expertise, and one of the most commonly used methods is preprocessing transformation, such as standardization, normalization, or feature discretization. In addition, the transformation operations for different types of features may vary. For example, operations such as conjunctions, disjunctions and negation are typically used for Boolean features; operations such as minimum, maximum, addition, subtraction, mean are typically used for numerical features, and operations such as Cartesian product \cite{pazzani1998constructive} and M-of-N \cite{zheng1998comparison} are commonly used for nominal features. 

It is impossible to manually explore all possibilities. Hence, to further improve efficiency, some automatic feature-construction methods have been proposed and shown to achieve results as good as or superior to those achieved by human expertise. These algorithms are aimed to automate the process of searching and evaluating the operation combination. In terms of searching, algorithms such as decision tree-based methods \cite{gama2004functional,zheng1998comparison} and genetic algorithms \cite{vafaie1998evolutionary} require a pre-defined operation space, while annotation-based approaches do not, as the latter use domain knowledge (in the form of annotation), together with the training examples \cite{feat_cons_survey}. Such methods can be traced back to the interactive feature-space construction protocol introduced by \cite{roth2009interactive}. Using this protocol, the learner identifies inadequate regions of feature space and, in coordination with a domain expert, adds descriptiveness using existing semantic resources. Then, after selecting possible operations and constructing a new feature, feature-selection techniques are applied to measure the new feature.







\subsection{Feature Extraction}

Feature extraction is a dimensionality-reduction process performed via some mapping functions. It extracts informative and non-redundant features according to certain metrics. Unlike feature selection, feature extraction alters the original features. The kernel of feature extraction is a mapping function, which can be implemented in many ways. The most prominent approaches are principal component analysis (PCA), independent component analysis, isomap, nonlinear dimensionality reduction, and linear discriminant analysis (LDA). Recently, the feed-forward neural networks approach has become popular; this uses the hidden units of a pretrained model as extracted features. Furthermore, many autoencoder-based algorithms are proposed; for example, Zeng et al. \cite{meng2017relational} propose a relation autoencoder model that considers data features and their relationships, while an unsupervised feature-extraction method using autoencoder trees is proposed by \cite{irsoy2017unsupervised}.



\end{document}


\subsection{Low fidelity}

As model training time is highly related to the dataset and model size, model evaluation can be accelerated in different ways. First, the number of images or the resolution of images (in terms of image-classification tasks) can be decreased. For example, FABOLAS \cite{fabolas} trains the model on a subset of the training set to accelerate model estimation. In \cite{imagenet_variants}, ImageNet64$\times$64 and its variants 32$\times$32, 16$\times$16 are provided, while these lower resolution datasets can retain characteristics similar to those of the original ImageNet dataset. Second, low-fidelity model evaluation can be realized by reducing the model size, such as by training with fewer filters per layer \cite{nasnet_zoph17, amoebanet}. By analogy to ensemble learning, \cite{multi_fidelity} proposes the \textit{Transfer Series Expansion (TSE)}, which constructs an ensemble estimator by linearly combining a series of basic low-fidelity estimators, hence avoiding the bias that can derive from using a single low-fidelity estimator. Furthermore, Zela et al. \cite{towards_nas_hpo} empirically demonstrate that there is a weak correlation between performance after short or long training times, thus confirming that a prolonged search for network configurations is unnecessary (see Figure \ref{fig:short_time}). 



\subsection{Weight sharing} 

In \cite{nas_rl_zoph16}, once a network has been evaluated, it is dropped. Hence, the technique of weight sharing is used to accelerate the process of NAS. For example, Wong and Lu et al. \cite{wong2018transfer} propose Transfer Neural AutoML, which uses knowledge from prior tasks to accelerate network design. ENAS \cite{enas} shares parameters among child networks, leading to a thousand-fold faster network design than \cite{nas_rl_zoph16}. Network morphism based algorithms \cite{chen2015net2net,network_morphism_wei16} can also inherit the weights of previous architectures, and single-path NAS \cite{singlepath_nas} uses a single-path over-parameterized ConvNet to encode all architectural decisions with shared convolutional kernel parameters.


\subsection{Surrogate}

The surrogate-based method \cite{eggensperger2014surrogate,wang2014evaluation,eggensperger2015efficient,surrogate_evolv} is another powerful tool that approximates to the black-box function. In general, once a good approximation has been obtained, it is trivial to find the configurations that directly optimize the original expensive objective. For example, Progressive Neural Architecture Search (PNAS) \cite{pnas_liu18} introduces a surrogate model to control the method of searching. Although ENAS has been proven to be very efficient, PNAS is even more efficient, as the number of models evaluated by PNAS is over five times that evaluated by ENAS, and PNAS is eight times faster in terms of total computational speed. However, when the optimization space is too large and hard to quantify, and the evaluation of each configuration is extremely expensive \cite{smbo_vu17}, a surrogate-based method is not applicable. Luo et al. \cite{semi_NAS} propose \textit{SemiNAS}, a semi-supervised NAS method, which leverages amounts of unlabeled architectures to further improve searching efficiency. The accuracy of the generated model does not need to be evaluated after training the model, but can be obtained only by using the controller to predict the accuracy.


\subsection{Early stopping}

Early stopping was first used to prevent overfitting in classical ML. It is used in several recent studies \cite{learn_curve_Klein16,peephole,speedup_learn_curve} to accelerate model evaluation by stopping evaluations that are predicted to perform poorly on the validation set. For example, \cite{speedup_learn_curve} proposes a learning-curve model that is a weighted combination of a set of parametric curve models selected from the literature, thereby enabling the performance of the network to be predicted. Furthermore, \cite{earlystop_no_val} presents a novel approach for early stopping based on fast-to-compute local statistics of the computed gradients, which no longer relies on the validation set and allows the optimizer to make full use of all of the training data.


\subsection{Resource-aware}

Early NAS studies \cite{nas_rl_zoph16,nasnet_zoph17,amoebanet} pay more attention to searching for neural architectures that achieve higher performance (e.g., classification accuracy), regardless of the associated resource consumption (i.e., the number of GPUs and time required). Therefore, many follow-up studies investigate resource-aware algorithms to trade off performance against the resource budget. To do so, these algorithms add computational cost to the loss function as a resource constraint. These algorithms differ in the type of computational cost, which may be 1) the parameter size; 2) the number of Multiply-ACcumulate (MAC) operations; 3) the number of float-point operations (FLOPs); or 4) the real latency. For example, MONAS \cite{monas} considers MAC as the constraint, and as MONAS uses a policy-based reinforcement-learning algorithm to search, the constraint can be directly added to the reward function. MnasNet \cite{mnasnet} proposes a customized weighted product to approximate a Pareto optimal solution:

\begin{equation}
\underset{m}{\operatorname{maximize}} \quad A C C(m) \times\left[\frac{L A T(m)}{T}\right]^{w}
\end{equation}

\noindent where $LAT(m)$ denotes measured inference latency on the target device, $T$ is the target latency, and $w$ is the weight variable defined as:

\begin{equation}
w=\left\{\begin{array}{ll}
\alpha, & \text { if } LAT(m) \leq T \\
\beta, & \text { otherwise }
\end{array}\right.
\end{equation}

\noindent where the recommended value for both $\alpha$ and $\beta$ are $-0.07$.

In terms of a differentiable neural architecture search (DNAS) framework, the constraint (i.e., loss function) should be differentiable. To do so, FBNet \cite{fbnet} uses a latency lookup table model to estimate the overall latency of a network based on the runtime of each operator. The loss function is defined as: 

\begin{equation}
\mathcal{L}\left(a, \theta_{a}\right)=\operatorname{CE}\left(a, \theta_{a}\right) \cdot \alpha \log (\operatorname{LAT}(a))^{\beta}
\end{equation}

\noindent where $CE(a,\theta_a)$ indicates the cross-entropy loss of architecture $a$ with weights $\theta_a$. Like MnasNet \cite{mnasnet}, this loss function has two hyper-parameters that need to be set manually: $\alpha$ and $\beta$ control the magnitude of the loss function and the latency term, respectively. In SNAS \cite{snas}, the cost of time for the generated child network is linear to the one-hot random variables, such that the resource constraint's differentiability is ensured.


\end{document}

\subsection{Search Space}


The neural architecture can be represented as a direct acyclic graph (DAG) \cite{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:

\begin{figure}[ht]
    \centering
   
   
    \includegraphics[width=0.36\textwidth]{images/entire_structure.pdf}
    \caption{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.}
    \label{fig:whole_structure}
\end{figure}

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


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 \cite{chollet2017xception}, dilated convolution\cite{dilated_conv}, and Squeeze-and-Excitation (SE) Block \cite{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.

\subsubsection{Entire-structured Search Space} 

The space of entire-structured neural networks \cite{nas_rl_zoph16,enas} is one of the most intuitive and straightforward search space. Figure \ref{fig:whole_structure} 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 \ref{fig:whole_structure}, while the right model is relatively complex, as it permits arbitrary skip connections \cite{resnet} to exist between the ordered nodes, and these connections have been proven effective in practice \cite{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.




\subsubsection{Cell-Based Search Space}

\begin{figure}[!ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/cell_structure.pdf}
    \caption{(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. }
    \label{fig:cell_structure}
\end{figure}



\textbf{Motivation}. To enable the transferability of the generated model, many works \cite{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 \cite{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 \cite{resnet}. Throughout the literature, this repeated module has been referred to as motif, cell, or block, while in this paper, we call it \textit{cell}. 


\textbf{Design}. Figure \ref{fig:cell_structure} (left) presents an example of a final cell-based neural network, which consists of two types of cells, namely \textit{normal} and \textit{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 \cite{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. \cite{nasnet_zoph17}, which is one of the first to propose an exploration of cell-based search space. Figure \ref{fig:cell_structure} (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\times1$ 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.

\textbf{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 


\begin{equation}
N_{entire}=M^L\times 2^{\frac{L\times(L-1)}{2}}
\label{eq:entire}
\end{equation}


\noindent 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 

\begin{equation}
N_{cell}=(M^B\times (B+2)!)^4
\label{eq:cell}
\end{equation}


\noindent 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 \ref{eq:entire} and \ref{eq:cell} the typical value in the literature, i.e. $M=5, L=10, B=3$, then $N_{entire}=3.44\times10^{20}$ is much larger than $N_{cell}=5.06\times10^{16}$.

\textbf{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 \ref{fig:pdarts} (left) shows, for DARTS \cite{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. \cite{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 \ref{fig:pdarts}. Experimentally, P-DARTS obtains a 2.50\% error rate on the CIFAR-10 test dataset, outperforming the 2.83\% error rate of DARTS. 


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/pdarts.pdf}
    \caption{Difference between DARTS \cite{darts_liu18} and P-DARTS \cite{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.}
    \label{fig:pdarts}
\end{figure}


\subsubsection{Hierarchical Search Space}

 \begin{figure}[ht]
    \centering
    \subfigure[Network-level architecture used in Conv-Deconv.]{\includegraphics[width=0.48\textwidth]{images/unet.png}}
    \subfigure[Network-level architecture used in stacked hourglass networks. ]{\includegraphics[width=0.48\textwidth]{images/glass.png}}
    \caption{The network-level search space (the figure is adopted from\cite{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.}
    \label{fig:two_level_hier}
\end{figure}

The cell-based search space enables the transferability of the generated model, and most of the cell-based methods \cite{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 \ref{fig:cell_structure}, 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. \cite{auto_deeplab} define a general formulation for a network-level structure, depicted in Figure \ref{fig:two_level_hier}, 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.

\begin{figure}[ht]
    \centering
    \subfigure[The level-one primitive operations are assembled into level-two cells.]{\includegraphics[width=0.48\textwidth]{images/hierachical1.png}}
    \subfigure[The level-two cells are viewed as primitive operations and assembled into level-three cells.]{\includegraphics[width=0.48\textwidth]{images/hierachical2.png}}
    \caption{An example of a three-level hierarchical architecture representation. The figure is adopted from \cite{liu_hierarchical_2018}.}
    \label{fig:hier_cell}
\end{figure}

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. \cite{liu_hierarchical_2018} propose a novel hierarchical genetic representation scheme, namely \textit{HierNAS}, in which the higher-level cell is generated by iteratively incorporating lower-level cells. As shown in Figure \ref{fig:hier_cell}, 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 \ref{fig:hier_cell}(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. \cite{pnas_liu18} also propose \textit{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 \cite{mnasnet,fbnet}. To ease both problems, Tan et al. \cite{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 \ref{fig:mnasnet} 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 \cite{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. \cite{proxylessnas} propose ProxylessNAS that can directly search for neural networks on the targeted dataset and hardware platforms by using BinaryConnect \cite{binaryconnect}, which addresses the high memory consumption issue.


\begin{figure}[!ht]
    \centering
    \includegraphics[width=0.35\textwidth]{images/mnasnet.pdf}
    \caption{The factorized hierarchical search space in MnasNet \cite{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.}
    \label{fig:mnasnet}
\end{figure}



\subsubsection{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 \cite{knowledgedistill} and transfer learning \cite{transferlearning}. However, these methods do not directly modify the model structure. To this end, Chen et al. \cite{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 \cite{resnet}. Therefore, an improved method is proposed, namely network morphism \cite{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. 

\begin{figure}[!ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/net2net.pdf}
    \caption{Net2DeeperNet and Net2WiderNet transformations in \cite{chen2015net2net}. "IdMorph" indicates identity morphism operation.}
    \label{fig:net2net}
\end{figure}

Several subsequent research works \cite{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. \cite{autokeras} propose a framework that enables Bayesian optimization to guide the network morphism for an efficient neural architecture search. Wei et al \cite{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 \cite{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.



\subsection{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.

\subsubsection{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. 

\textbf{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 \cite{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 \cite{cgp_suganuma17,large_scale_evolve,liu_hierarchical_2018}. For example, Suganuma et al. \cite{cgp_suganuma17} use Cartesian genetic programming (CGP) \cite{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 \cite{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)  \cite{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) \cite{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 \cite{fernando2016convolution,kim2015deep,pugh2013evolving, lemonade} describe the use of indirect encoding schemes to represent the network. For example, the network in \cite{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.


\begin{figure}
    \centering
    \includegraphics[width=0.32\textwidth]{images/ea.pdf}
    \caption{The overview of evolutionary algorithm.}
    \label{fig:ea}
\end{figure}

\textbf{Four Steps.} A typical evolutionary algorithm consists of the following steps: selection, crossover, mutation, and update (see Figure \ref{fig:ea}):

\begin{itemize}
    \item \textbf{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 \textit{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 \textit{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 \textit{tournament selection} \cite{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. 

    \item \textbf{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. \cite{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. 
    
    
    \item \textbf{Mutation}
    As the genetic information of the parents is copied and inherited by the next generation, gene mutation also occurs. A point mutation \cite{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 \cite{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. \cite{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. 
    
    
    \item \textbf{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 \cite{large_scale_evolve}, the worst-performing network of two randomly selected networks is immediately removed from the population. Alternatively, in \cite{amoebanet}, the oldest networks are removed. Other methods \cite{evolve_dnn,genertic_cnn,cgp_suganuma17} discard all models at regular intervals. However, Liu et al. \cite{liu_hierarchical_2018} do not remove any networks from the population; instead, they allow the network to grow with time. EENA \cite{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$.
    
    
\end{itemize}



\subsubsection{Reinforcement Learning}


\begin{figure}[ht]
    \centering
   
    \includegraphics[width=0.48\textwidth]{images/rl_nas.pdf}
    \caption{An overview of NAS using reinforcement learning.}
    \label{fig:rl_nas}
\end{figure}


Zoph et al. \cite{nas_rl_zoph16} were one of the first to apply reinforcement learning (RL) for neural architecture search. Figure \ref{fig:rl_nas} 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 \cite{metaqnn,nasnet_zoph17,blockqnn,enas} use this framework, but with different agent policies and  neural-architecture encoding. Zoph et al. \cite{nas_rl_zoph16} first use the policy gradient algorithm \cite{policygradient} to train the agent, and sequentially sample a string to encode the entire neural architecture. In subsequent work \cite{nasnet_zoph17}, they use the Proximal Policy Optimization (PPO) algorithm \cite{ppo} to update the agent, and propose the method shown in Figure \ref{fig:rl_cell} to build the cell-based neural architecture. MetaQNN \cite{metaqnn} proposes a meta-modeling algorithm using Q-learning and a $\epsilon$-greedy exploration strategy and experience replay to search neural architectures sequentially. 

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.48\textwidth]{images/rl_cell.pdf}
    \caption{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.}
    \label{fig:rl_cell}
\end{figure}

Although the above RL-based algorithms have achieved SOTA results on CIFAR-10 and Penn Treebank (PTB) \cite{ptb} datasets, they spend much time and computational resources. For instance, \cite{nas_rl_zoph16} took 28 days and 800 K40 GPUs to search for the best-performing architecture, and MetaQNN \cite{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 \cite{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) \cite{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 \cite{nas_rl_zoph16}. 



\subsubsection{Gradient Descent}

The search strategies above sample neural architectures from a discrete search space. A pioneering algorithm, namely DARTS \cite{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:


\begin{equation}
\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)
\label{eq:darts_softmax}
\end{equation}

\noindent 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{equation}
\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}
\label{eq:bilevel}
\end{equation}


\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/darts.png}
    \caption{An overview of DARTS (the figure is adopted from \cite{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.}
    \label{fig:darts}
\end{figure}

Figure \ref{fig:darts} 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. \ref{eq:bilevel} 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:

\begin{equation}
    \min _{\theta, \alpha} \mathcal{L}_{\mathrm{train}}(\theta, \alpha)
    \label{eq:single_level}
\end{equation}

\noindent 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 \cite{MiLeNAS}, the authors propose mixed-level optimization:

\begin{equation}
\min _{\alpha, \theta}\,\,\left[\mathcal{L}_{train}\left(\theta^{*}, \alpha\right)+\lambda \mathcal{L}_{val}\left(\theta^{*}, \alpha\right)\right]
\label{eq:mixed_level}
\end{equation}

\noindent 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. \ref{eq:mixed_level} degrades to the single-level optimization (Eq. \ref{eq:single_level}); while if $\lambda$ is close to infinity, then Eq. \ref{eq:mixed_level} becomes a bilevel optimization (Eq. \ref{eq:bilevel}). The experimental results in \cite{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. \ref{eq:darts_softmax}) 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 \cite{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 \cite{gumbel_softmax}. Specifically, the neural architecture is fully factorized and modeled with a concrete distribution \cite{concrete_dist}, which provides an efficient way to sample a child architecture and allows gradient back-propagation. Therefore, Eq. \ref{eq:darts_softmax} is re-formulated as Eq. \ref{eq:gumbel_softmax}:



\begin{equation}
    \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)
    \label{eq:gumbel_softmax}
\end{equation}


\noindent 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 \cite{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. \ref{eq:gumbel_softmax}. In other words, only one path of the super-net is selected for training, thereby reducing GPU memory usage. On the other hand, ProxylessNAS \cite{proxylessnas} alleviates the huge consumption of resources via path binarization. Specifically, ProxylessNAS transforms the real-valued path weights \cite{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 \cite{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+ \cite{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 \cite{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.


\subsubsection{Surrogate Model-Based Optimization}


Another group of architecture optimization method is surrogate model-based optimization (SMBO) algorithms \cite{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 \textit{Gaussian process (GP)} \cite{GP}, \textit{random forests (RF)} \cite{smbo_random_forest}, \textit{Tree-structured Parzen Estimator (TPE)} \cite{alg_hpo}), and neural networks \cite{bananas,nao,pnas_liu18,epnas}. 

Bayesian optimization (BO) \cite{bo,bo_review} is one of the most popular and well-established methods for hyper-parameter optimization. Recently, many follow-up works \cite{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 \cite{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. \cite{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 \cite{towards_autotune} and \cite{bayesian_free} also use a random forest as the surrogate model, and  \cite{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 \cite{pnas_liu18} and EPNAS \cite{epnas}, an LSTM is derived as the surrogate model to predict variable-sized architectures progressively. At the same time, NAO \cite{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 \cite{pnas_liu18}. White et al. \cite{bananas} train an ensemble of neural networks to predict the mean and variance of validation results for candidate neural architectures.
 

\subsubsection{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 \cite{sharpdarts,active_grid_nas,nas_random,eval_nas_phase}. For instance, in MnasNet \cite{mnasnet}, the number of cells and blocks are predefined manually. To further automate the NAS process, Geifman et al. \cite{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 \cite{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 \cite{enas}, which is a reinforcement learning-based leading NAS method. Besides, the work by Yu et al. \cite{eval_nas_phase} also demonstrate that the SOTA NAS techniques are not significantly better than random search.



\subsubsection{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 \cite{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 \cite{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 \cite{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.


\textbf{EA+RL}. Chen et al. \cite{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) \cite{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. 

\textbf{EA+GD}. Yang et al. \cite{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. \cite{cars} only took 0.4 GPU days for searching, which is more efficient than early EA methods (e.g., AmoebaNet \cite{amoebanet} took 3150 GPU days and 450 GPUs for searching). 

\textbf{EA+SMBO}. In \cite{surrogate_evolv}, the authors use the random forest as a surrogate to predict model performance, which accelerates the fitness evaluation in an evolutionary algorithm. 

\textbf{GD+SMBO}. Different from DARTS, which learns weights for candidate operations, NAO \cite{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.

\subsection{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.




\subsubsection{Grid and Random Search}

Figure \ref{fig:grid_random} 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. 

\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/grid_random.pdf}
   
   
    \caption{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)$ \cite{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 \cite{hpo_random})}
    \label{fig:grid_random}
\end{figure}

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. \cite{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. \cite{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 \cite{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. \cite{li_hyperband_2016} propose \textit{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.

\subsubsection{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 \cite{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). 

\begin{algorithm}
\caption{Sequential Model-Based Optimization}
\label{alg:SMBO}
\begin{algorithmic}
\STATE $\text{INPUT:} \, f, \Theta, S, \mathcal{M}$
\STATE ${\mathcal{D} \leftarrow \text { INITSAMPLES }(f, \Theta)}$
\FOR {$i$ in $[1,2,..,T]$}
\STATE ${p(y | \theta, \mathcal{D}) \leftarrow \text { FITMODEL }(\mathcal{M}, \mathcal{D})}$
\STATE ${\theta_{i}\leftarrow\arg\max _{\theta\in \Theta} S(\theta, p(y|\theta, \mathcal{D}))}$
\STATE ${y_{i} \leftarrow f\left(\theta_{i}\right)} \,\,  \,\,  \,\, \triangleright \text{Expensive step}$
\STATE $\mathcal{D} \leftarrow \mathcal{D} \cup\left(\theta_{i}, y_{i}\right)$
\ENDFOR
\end{algorithmic}
\end{algorithm}


The steps of SMBO are expressed in Algorithm \ref{alg:SMBO} (adopted from \cite{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:

\begin{enumerate}
    \item The first step is to tune the probabilistic model $\mathcal{M}$ to fit the records dataset $D$.
    \item The acquisition function $\mathcal{S}$ is used to select the next promising neural architecture from the probabilistic model $\mathcal{M}$.
    \item 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.
    \item The records dataset $D$ is updated by appending a new pair of result $(\theta_i,y_i)$.
\end{enumerate}


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 \ref{table:bo_models} 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. \cite{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 \cite{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.


\begin{table}[]
    \centering
    \begin{tabular}{|c|c|}
    \hline
    Library  & Model      \\ \hline
    \makecell{ Spearmint\\ https://github.com/HIPS/Spearmint}   & GP \\\hline
    \makecell{ MOE\\ https://github.com/Yelp/MOE}   &  GP\\\hline
    \makecell{ PyBO\\ https://github.com/mwhoffman/pybo}   & GP \\\hline
    \makecell{ Bayesopt\\ https://github.com/rmcantin/bayesopt}   &GP  \\\hline
    \makecell{ SkGP\\ https://scikit-optimize.github.io}   & GP \\\hline
    \makecell{ GPyOpt\\ http://sheffieldml.github.io/GPyOpt}   & GP \\\hline
    
    \makecell{SMAC      \\ https://github.com/automl/SMAC3}   & RF    \\\hline
    \makecell{Hyperopt  \\ http://hyperopt.github.io/hyperopt} & TPE  \\ \hline
    \makecell{BOHB\\https://github.com/automl/HpBandSter}&TPE \\\hline
\end{tabular}
    \caption{The open-source Bayesian optimization libraries. GP, RF, and TPE represent \textit{Gaussian process} \cite{GP}, \textit{random forests} \cite{smbo_random_forest}, \textit{Tree-structured Parzen Estimator} \cite{alg_hpo}, respectively. }
    \label{table:bo_models}
\end{table}

\subsubsection{Gradient-Based Optimization}


Another group of HPO methods are \textit{gradient-based optimization (GO)} algorithms \cite{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. \cite{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, \cite{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. \cite{forward_gd_hpo} study both the reverse-mode and forward-mode GO methods. The reverse-mode method differs from \cite{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 \cite{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 \cite{kingma2014adam}'s moment coefficient $\beta_1,\beta_2$).



\end{document}

\subsection{NAS performance comparison}

Notably, many NAS studies may propose several neural architecture variants, where each variant is designed for different scenarios (e.g., some architectures perform better but with large size, while some are lightweight for a mobile device but with a performance penalty), so we only report the representative results for each work. Besides, to ensure a valid comparison, we take the accuracy and the algorithm efficiency as comparison indices. As the number and types of GPUs used vary from different studies, we use \textit{GPU Days} to approximate the efficiency, which is defined as:

\begin{equation}
    \text{GPU Days}=N \times D
    \label{eq:gpu_days}
\end{equation}

\noindent where $N$ represents the number of GPUs, and $D$ represents the actual number of days spent searching. 

Table \ref{table:NAS_cifar_perf} and Table \ref{table:NAS_imagenet_perf} present the performance of different NAS studies on CIFAR-10 and ImageNet, respectively. Besides, since most NAS methods first search for the neural architecture based on a small dataset (CIFAR-10), then transfer the architecture to a larger dataset (ImageNet), the search time for both datasets may be the same. It can be seen from the table that the early work of EA and RL based NAS methods pay more attention to high performance, regardless of the resource consumption. For example, although AmoebaNet \cite{amoebanet} achieved excellent results on both CIFAR-10 and ImageNet, it took 3,150 GPU days with 450 GPUs for searching. The subsequent NAS studies make efforts to improve searching efficiency while ensuring the searched model's high performance. For instance, EENA \cite{eena} elaborately designs the mutation and crossover operations, which can reuse the learned information to guide the evolution process and hence greatly improve the efficiency of EA-based NAS method. ENAS \cite{enas} is one of the first RL-based NAS methods to propose the parameter-sharing strategy, which reduces the number of GPU budgets to 1 and shortens the searching time to less than one day. We also observe that gradient descent-based architecture optimization methods can greatly reduce computational resource consumption for searching and achieve SOTA results. A lot of follow-up work is to make further improvement and optimization in this direction. Interestingly, random search-based methods can also obtain comparable results. The authors of \cite{nas_random} demonstrate that random search with weight-sharing can outperform a series of powerful methods, such as ENAS \cite{enas} and DARTS \cite{darts_liu18}. 


\subsubsection{Kendall Tau metric}

Since random search is comparable to those more sophisticated methods (e.g., DARTS and ENAS), one natural question is: what are the advantages and significance of the other architecture optimization algorithms compared with the random search? The researchers try to use other metrics to answer this question, not just considering the final accuracy of the model. Most NAS methods consist of two stages: 1) search for a best-performing architecture on the training set; 2) then expand it to a deeper one and estimate it on the validation set. However, there usually exists a large gap between the two stages. In other words, the architecture that achieves the best result in the training set is not necessarily the best one on the validation set. Therefore, instead of merely considering the final accuracy and search time cost, many NAS studies \cite{hu2020dsnas,istrate2018tapas,nsas,eval_nas_phase,nas_eval} make use of Kendall Tau ($\tau$) metric \cite{kendall_tau} to measure the correlation of the model performance between the search and estimation stages. The value of $\tau$ is defined as:

\begin{equation}
    \tau=\frac{N_C-N_D}{N_C+N_D}
\end{equation}

\noindent where $N_C$ and $N_D$ indicate the number of concordant and discordant pairs. $\tau$ is a number in the range [-1,1] with the following properties:

\begin{itemize}
    \item $\tau=1$: two rankings are identical
    \item $\tau=-1$: two rankings are completely opposite.
    \item $\tau=0$: there is no relationship between two rankings.
\end{itemize}



\begin{figure}
    \centering
    \subfigure[Two-stage NAS consists of the searching stage and evaluation stage. The best-performing model of the searching stage will be further retrained in the evaluation stage.]{\includegraphics[width=0.48\textwidth]{images/two-stage.pdf}}
    \subfigure[One-stage NAS can directly deploy a well-performing model without extra retraining or fine-tuning. The two-way arrow indicates that the process of architecture optimization and parameter training run simultaneously. ]{\includegraphics[width=0.48\textwidth]{images/one-stage.pdf}}
    \caption{Illustration of two-stage and one-stage NAS flow.}
    \label{fig:nas_stage}
\end{figure}

\subsubsection{NAS-Bench Dataset}


Although Table \ref{table:NAS_cifar_perf} and Table \ref{table:NAS_imagenet_perf} presents a clear comparison between different NAS methods, the results of different methods are obtained under different settings, such as training-related hyper-parameters (e.g., batch size and training epochs), data augmentation (e.g., Cutout \cite{cutout}). In other words, the comparison is not quite fair. In this context, NAS-Bench-101 \cite{ying2019nasbench} is a pioneering work to alleviate the problem of non-reproducibility. It provides a tabular dataset that contains 423,624 unique neural networks, which are generated and evaluated from a fixed graph-based search space, and mapped to their trained and evaluated performance on CIFAR-10. Besides, Dong et al. \cite{nasbench201} further build NAS-Bench-201, which is an extension to NAS-Bench-101 and has different search space, results on multiple datasets (CIFAR-10, CIFAR-100, and ImageNet-16-120 \cite{imagenet_variants}), and more diagnostic information. Similarly, Klyuchnikov et al. \cite{nasbenchnlp} propose a NAS-Bench for the NLP task. These datasets enable NAS researchers to focus solely on verifying the effectiveness and efficiency of their proposed architecture optimization algorithms, avoiding repetitive training for selected architectures, and greatly helping the NAS community develop.

\subsection{One-stage vs. Two-stage}

The NAS methods can be roughly divided into two classes according to the flow: two-stage and one-stage, as shown in Figure \ref{fig:nas_stage}.

\textbf{Two-stage NAS} consists of the \textit{searching stage} and \textit{evaluation stage}. The \textit{searching stage} involves architecture optimization and parameter training. The simplest idea is to train all possible architectures from scratch and then choose the optimal one. However, it requires many resources (e.g., NAS-RL \cite{nas_rl_zoph16} took 22,400 GPU days with 800 K40 GPUs for searching) infeasible for most companies and institutes. Therefore, most NAS methods (such as ENAS \cite{enas} and DARTS \cite{darts_liu18}) sample and train a large number of candidate architectures in the searching stage, and then the best-performing one will be further retrained in the evaluation stage.

\textbf{One-stage NAS} refers to a class of NAS methods that can export a well-designed and well-trained neural architecture without extra retraining by running architecture optimization and parameter training simultaneously. In this way, it can greatly improve efficiency. However, it is currently the main challenge of any general NAS problem. Several recent studies  \cite{OFA,yoso,yu2020bignas,atomnas} have tried to overcome this challenge. For instance, in \cite{OFA}, the authors propose \textit{progressive shrinking} algorithm to post-process the weights after training is finished. Specifically, they first pre-train the full neural network, then progressively fine-tune the smaller networks that share weights with the full network. Based on well-designed constraints, the performance of all sub-networks is guaranteed. Thus, given a target deployment device, a specialized sub-network can be directly exported without fine-tuning. However, \cite{OFA} still requires many computational resources, as the whole process took 1,200 GPU hours with V100 GPUs. BigNAS \cite{yu2020bignas} revisits conventional training techniques of stand-alone networks, and empirically proposes several techniques to handle a wider set of models, ranging in size from 200M FLOPs to 1G FLOPs, while \cite{OFA} only handles models under 600M FLOPs. Both AtomNAS \cite{atomnas} and DSNAS \cite{hu2020dsnas} propose an end-to-end one-stage NAS framework to further boost the performance and simplify the flow.




\subsection{One-shot/Weight-sharing}




\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{images/one-shot.pdf}
    \caption{(Left) One-shot models. (Right) Non one-shot models. Each circle indicates a different model, and the area of the circle indicates the size of the model. We use concentric circles to represent one-shot models, as they share the weights with each other.}
    \label{fig:one-shot}
\end{figure}


\textbf{One-shot$\neq$one-stage.} We need to know that one-shot is not exactly equivalent to one-stage. As mentioned above, we divide NAS studies into one-stage and two-stage methods according to the flow (Figure \ref{fig:nas_stage}), while whether a NAS algorithm belongs to the one-shot method or not depends on whether candidate architectures share the same weights (Figure \ref{fig:one-shot}). We observe that most of one-stage NAS methods are based on one-shot paradigm. 

\textbf{ What is One-shot NAS?} One-shot NAS methods embeds the search space into an over-parameterized supernet. As a result, all possible architectures can be derived from the supernet. Figure \ref{fig:nas_stage} shows the difference between the search space of one-shot and non-one-shot NAS. Each circle indicates a different architecture, where the architectures of one-shot NAS methods share the same weights among each other. One-shot NAS methods can be divided into two categories, which differ in how to handle architecture optimization and weights training: coupled and decoupled optimization \cite{chu2019fairnas,you2020greedynas}.

\textbf{Coupled optimization.} The first category of one-shot NAS methods optimizes the architecture and weights in a coupled manner \cite{enas,darts_liu18,gdas,proxylessnas,snas}. For instance, ENAS \cite{enas} proposes to use an LSTM network to discretely sample a new architecture, and then uses a few batches of the training data to optimize the weight of this architecture. After repeating the above steps many times, a collection of architectures and their corresponding performance will be recorded. Finally, the best-performing architecture is selected for further retraining. DARTS \cite{darts_liu18} also uses a similar weight sharing strategy, but the architecture distribution is continuously parameterized. The supernet contains all candidate operations, each with learnable parameters. The best architecture can be directly derived from the distribution. However, since DARTS \cite{darts_liu18} directly optimizes the supernet weights and the architecture distribution, it suffers from the vast GPU memory consumption. Although DARTS-like methods \cite{proxylessnas,gdas, snas} have proposed different approaches to reduce resource requirements, coupled optimization inevitably introduces a bias in both architecture distribution and supernet weights \cite{singlepath_nas,chu2019fairnas}, as they treat all sub-networks unequally. Specifically, the quickly-converged architectures can easily obtain more chances to be optimized \cite{darts_liu18,darts+}, and those architectures are only a small portion of the whole candidates; therefore, it is very harsh to find the best-architecture. 

Another disadvantage of coupling optimization is that when new architectures are sampled and trained continuously, the weights of previous architectures will be negatively impacted, leading to performance degradation. \cite{multimodel_forget} defines this phenomenon as \textit{multi-model forgetting}. To overcome this problem, Zhang et al. \cite{oneshot_forget} model the supernet training as a constrained optimization problem of continual learning, and propose \textit{novel search based architecture selection} (NSAS) loss function. They apply the proposed method to RandomNAS \cite{nas_random} and GDAS \cite{gdas}, and the experimental result demonstrates that the method is effective to reduce the multi-model forgetting and boost the predictive ability of the supernet as an evaluator.


\textbf{Decoupled optimization}. The second category of one-shot NAS methods \cite{oneshot_self,under_oneshot,chu2019fairnas,OFA} solves the problem of above one-shot methods by decoupling the optimization of architecture and weights into two sequential phases: 1) training the supernet; 2) using the trained supernet as a predictive performance estimator of different architectures to select the most promising architecture. 



In terms of the phase of supernet training, the supernet cannot be directly trained like a regular neural network, because \textit{the weights of the supernet are also deeply coupled} \cite{singlepath_nas}. The work by Yu et al. \cite{eval_nas_phase} experimentally shows that weight sharing strategy harms the individual architecture's performance and negatively impacts the real performance ranking of the candidate architectures. To reduce weight coupling, many one-shot NAS methods \cite{singlepath_nas,oneshot_self,smash_onehot,GHN} propose the random sampling policy, which uniformly randomly samples an architecture from the supernet, and only the weights of this architecture are activated and optimized. RandomNAS \cite{nas_random} also demonstrates that a random search policy is a competitive baseline method. Although the strategy of sampling and training only one path of the supernet each time is already adopted in previous one-shot approaches \cite{gdas,enas,snas,proxylessnas,fbnet}, they sample the path according to RL controller \cite{enas}, Gumbel Softmax \cite{gdas,snas,fbnet}, or BinaryConnect network \cite{proxylessnas}, which instead highly couples the architecture and supernet weights. SMASH \cite{smash_onehot} proposes an auxiliary hypernetwork to generate the weights for randomly sampled architectures. Similarly, Zhang et al. \cite{GHN} propose a computation graph representation, and use the graph hypernetwork (GHN) to predict the weights for all possible architectures faster and more accurately than regular hypernetworks (SMASH \cite{smash_onehot}). However, Bender et al. \cite{under_oneshot} conduct a careful experimental analysis to understand the mechanism of weight sharing strategy, and show that neither a hypernetwork nor an RL controller is required to find the optimal architecture. In \cite{under_oneshot}, the authors propose a \textit{path dropout} strategy to alleviate the problem of weight coupling. During training the supernet, each path of the supernet is randomly dropped with gradually increasing probability. GreedyNAS \cite{you2020greedynas} propose a multi-path sampling strategy to train the greedy supernet. The strategy can focus on more potentially-good paths, and is demonstrated to be effective in achieving a fairly high rank correlation of candidate architectures compared with random search.



The second phase involves how to select the most promising architecture from the trained supernet, which is the primary purpose of most NAS tasks. Both SMASH \cite{smash_onehot} and \cite{under_oneshot} randomly select a set of architectures from the supernet, and rank them according to their performance. SMASH can obtain the validation performance of all selected architectures at the cost of a single training run for each architecture, as these architectures are assigned with the weights generated by the hypernetwork. Besides, \cite{under_oneshot} observe that the architectures with smaller symmetrized KL divergence value are more likely to perform better. The equation is as follows:

\begin{equation}
\begin{split}
    D_{\mathrm{SKL}} = D_{\mathrm{KL}}(p \| q)+D_{\mathrm{KL}}(q \| p) \\
   s.t. \,\, D_{\mathrm{KL}}(p \| q) =\sum_{i=1}^{n} p_{i} \log \frac{p_{i}}{q_{i}}
\end{split}
\end{equation}


\noindent where $(p_1,...,p_n)$ and $q_1,...,q_n$ indicates the prediction of the sampled architecture and one-shot model, and $n$ is the number of classes. The cost of calculating the KL value is very small; in \cite{under_oneshot}, only 64 random training data examples are used. Evolutionary algorithm (EA) is also a promising search solution \cite{singlepath_nas,you2020greedynas}. For instance, SPOS \cite{singlepath_nas} makes use of EA to search for architectures from the supernet. It is more efficient than the EA methods introduced in Section \ref{section:model_generation}, because each sampled architecture only performs inference. Self-Evaluated Template Network (SETN) \cite{oneshot_self} proposes an \textit{estimator} to predict the probability of each architecture being likely to have a lower validation loss. The experimental results show that SETN can potentially find the architecture with better performance than random search based methods \cite{under_oneshot,smash_onehot}.


\subsection{Joint Hyper-parameter and Architecture Optimization}

Most NAS methods fix the same setting of training-related hyper-parameters during the whole search stage. After the search, the hyper-parameters of the best-performing architecture will be further optimized. However, this paradigm may result in sub-optimal results as different architectures tend to fit different hyper-parameters, making the ranking of the models unfair \cite{dong2020autohas}. Therefore, a promising solution is the joint \textit{hyper-parameter and architecture optimization (HAO)} \cite{towards_nas_hpo,tabular_hao,dong2020autohas,dai2020fbnetv3}. For instance, Zela et al. \cite{towards_nas_hpo} casts NAS as a hyperparameter optimization problem. In this way, the search spaces of NAS and standard hyper-parameters are combined, and BOHB \cite{bohb}, an efficient HPO method, is applied to optimize the architecture and hyper-parameters jointly. Similarly, Dong et al. \cite{dong2020autohas} propose a differentiable method, namely AutoHAS, which builds a Cartesian product of the search spaces of both NAS and HPO by unifying the representation of all candidate choices for architecture (e.g., the number of layers) and hyper-parameters (e.g., learning rate). The challenge is that the candidate choices for architecture search space are usually categorical, while hyper-parameters choices can be categorical (e.g., the type of optimizer) and continuous (e.g., learning rate). To overcome this challenge, AutoHAS discretizes the continuous
hyperparameters into a linear combination of multiple categorical bases. For example, the categorical bases for the learning rate are $\{0.1,0.2,0.3\}$, then the final learning rate is defined as $lr=w_1\times 0.1+w_2\times 0.2+w_3\times 0.3$. FBNetv3 \cite{dai2020fbnetv3} also proposes to jointly search both architectures and the corresponding training recipes (i.e., hyper-parameters). The architectures are represented with one-hot categorical variables and integral (min-max normalized) range variables, and the representation is fed to an encoder network to generate the architecture embedding. Then the concatenation of architecture embedding and the training hyper-parameters is used to train the accuracy predictor, which will be applied to search for promising architectures and hyper-parameters at the later stage.


\end{document}

\subsection{Flexible Search Space}

As summarized in Section \ref{section:model_generation}, there are several types of search spaces, where the primitive operations can be roughly classified into pooling and convolution. Some even use a more complex module (MBConv \cite{mnasnet}) as the primitive operation. Although these search spaces have been proven effective to generate well-performing neural architectures, they all based on human knowledge and experience, which inevitably introduces human bias and hence still does not break away from the human design paradigm. AutoML-Zero \cite{real2020automlzero} uses very simple mathematical operations (e.g., $\cos,\sin,\text{mean,std}$) as the primitive operations of the search space to minimize the human bias, and applies the evolutionary algorithm to discover complete machine learning algorithms. AutoML-Zero successfully designs two-layer neural networks based on those basic mathematical operations. Although the network searched by AutoML-Zero is much simpler compared to both human-designed and NAS-designed networks, the experimental results show the potential to discover a new model design paradigm with minimal human design. Therefore, how to design a more general, flexible, and free of human bias search space and how to discover novel neural architectures based on this search space would be challenging and advantageous.



\subsection{Applying NAS to More Areas}

 

As described in Section \ref{section:nas_performance}, the models designed by NAS algorithms have achieved comparable results in image classification tasks (CIFAR-10 and ImageNet) to manually-designed models. Additionally, many recent studies have also applied NAS to other CV tasks (shown in Table \ref{table:nas_apps}). 

However, in terms of the NLP task, most NAS studies only implement experiments on the PTB dataset. Besides, a few NAS studies also try to apply NAS to other NLP tasks (shown in Table \ref{table:nas_apps}). However, as Figure \ref{fig:auto_vs_manual} shows, there is still a large gap between the performance of NAS-designed models (\cite{enas,darts_liu18,nas_rl_zoph16}) and human-designed models (GPT-2 \cite{GPT}, FRAGE AWD-LSTM-Mos \cite{frage}, adversarial AWD-LSTM-Mos \cite{adversarial_awd} and Transformer-XL \cite{transformerxl}) on the PTB dataset. Therefore, the NAS community still has a long way to go to achieve comparable results to those models designed by experts on NLP tasks.

In addition to the CV and NLP tasks, Table \ref{table:nas_apps} also shows that NAS has been applied to a variety of tasks, such as network compression, federate learning, image caption, recommendation system, and even searching for loss function. Therefore, these interesting work also indicates the potential for NAS to be applied in other fields.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.48\textwidth]{images/ptb_nas_human.pdf}
    \caption{The SOTA models on the PTB dataset. The lower the perplexity, the better the performance. The green bar represents the automatically generated model, and the yellow bar represents the model designed by human experts. Best viewed in color.}
    \label{fig:auto_vs_manual}
\end{figure}






\subsection{Interpretability}

Although AutoML algorithms can find promising configuration settings more efficiently than humans, there is a lack of scientific evidence to illustrate why the found settings perform better. For example, in BlockQNN \cite{blockqnn}, it's not clear why the NAS algorithm tends to select the ‘‘Concatenation’’ operation to process the output of each block in the cell, instead of the element-wise addition operation. Some recent studies \cite{under_oneshot,under_das,wong2016understanding} The explanation for these occurrences is usually hindsight and lacks rigorous mathematical proof. Therefore, increasing the mathematical interpretability of AutoML is also an important future research direction.


\subsection{Reproducibility}

It is well known that a major challenge with ML is reproducibility. AutoML is no exception, especially for NAS, because most of the existing NAS algorithms still have many parameters that need to be set manually at the implementation level, but the original papers do not cover too much detail. For instance, Yang et al. \cite{nas_eval} experimentally demonstrate that the seed plays an important role in NAS experiments, while most NAS methods didn't mention the seed set by their experiments in the papers. Besides, huge resource consumption is another obstacle to reproduction. In this context, several NAS-Bench datasets are proposed, such as NAS-Bench-101 \cite{ying2019nasbench}, NAS-Bench-201 \cite{nasbench201}, and NAS-Bench-NLP \cite{nasbenchnlp}. These datasets allow NAS researchers to focus on the design of optimization algorithms without wasting a lot of time on model estimation.


\subsection{Robustness}

NAS has been proven effective in searching for promising architectures on many open datasets (e.g., CIFAR-10 and ImageNet). Those datasets are usually for the research purpose; therefore, most of the images are well-labeled. However, in real-world situations, the data inevitably contains noise (e.g., mislabeling and inadequate information). Even worse, the data might be modified to be adversarial data with carefully designed noises. Deep learning models are easily fooled by adversarial data, and so is NAS. Currently, there are a few studies \cite{is_nas_robust,NAS_Meets_Robustness,Chen2020OnRO,vargas2019evolving} making efforts to boost the robustness of NAS against adversarial data. Guo et al. \cite{NAS_Meets_Robustness} experimentally explore the intrinsic impact of network architectures on network robustness against adversarial attacks, and observe that densely connected architectures tend to be more robust. They also find that the flow of solution procedure (FSP) matrix \cite{FSP_matrix} is a good indicator of network robustness, i.e., the lower the FSP matrix loss more robust the network is. Chen et al. \cite{Chen2020OnRO} propose a robust loss function to alleviate the performance degradation under symmetric label noise effectively. In \cite{vargas2019evolving}, the authors adopt an evolutionary algorithm to search for robust architectures from a well-designed and vast search space, where many types of adversarial attacks are used as the fitness function to evaluate the robustness of neural architectures.


\subsection{Joint Hyperparameter and Architecture Optimization}

Most NAS studies consider hyperparameter optimization (HPO) and architecture optimization (AO) as two separate processes. However, as noted already in Section \ref{section:model_generation}, there is a tremendous overlap between the methods used in HPO and AO, e.g., both of them apply random search, Bayesian optimization, and gradient-based optimization methods. In other words, it would be feasible to jointly optimize both hyperparameters and architectures. Several studies \cite{tabular_hao,dong2020autohas,dai2020fbnetv3} also confirm this possibility experimentally. Thus, how to solve the problem of joint hyperparameter and architecture optimization (HAO) elegantly is a worthy studying issue.


\subsection{Complete AutoML Pipeline}

There are already many AutoML pipeline libraries proposed, but most of them only focus on some parts of the AutoML pipeline (Figure \ref{fig:pipeline_details}). For instance, TPOT \cite{Olson2016EvoBio}, Auto-WEAK \cite{auto_weak}, and Auto-Sklearn \cite{eff_automl_nips15} are built on top of scikit-learn \cite{sklearn} for building classification and regression pipelines, but they only search for the traditional ML models (like SVM and KNN). Although TPOT involves neural networks (using Pytorch \cite{PyTorch} backend), it only supports a multi-layer perception network. Besides, Auto-Keras \cite{autokeras} is an open-source library developed based on Keras \cite{Keras}. It focuses more on searching for deep learning models and supports multi-modal and multi-task. NNI \cite{nni} is a more powerful toolkit of AutoML, as its built-in capability contains automated feature engineering, hyper-parameter optimization, and neural architecture search. Additionally, the NAS module in NNI supports both Pytorch \cite{PyTorch} and Tensorflow \cite{abadi2016tensorflow} and reproduces many SOTA NAS methods \cite{enas,darts_liu18,proxylessnas,pdarts,singlepath_nas,nas_random,ying2019nasbench}, which is very friendly for NAS researcher and developer. Besides, NNI also integrates the features of scikit-learn \cite{sklearn}, which is one step closer to achieving a complete pipeline. Similarly, Vega \cite{vega} is another AutoML algorithm tool, which constructs a complete pipeline covering a set of highly decoupled functions: data augmentation, HPO, NAS, model compression, and fully train. In a word, designing an easy-to-use and complete AutoML pipeline system is a promising research direction.
 





\subsection{Lifelong Learning}

Last but not least, most AutoML algorithms focus only on solving a specific task on some fixed datasets, e.g., image classification on CIFAR-10 and ImageNet. However, a high-quality AutoML system should have the capability of lifelong learning, i.e., it can 1) efficiently \textbf{learn new data}; 2) meanwhile \textbf{remember old knowledge}.


\subsubsection{Learn new data}



Firstly, the system should be able to reuse prior knowledge to solve new tasks (i.e., learning to learn). For example, a child can quickly identify tigers, rabbits, and elephants after seeing several pictures of these animals, but current DL models must be trained on a large number of data before they can correctly identify images. A hot topic in this area is meta-learning, which aims to design models for new tasks using previous experience.

\textbf{Meta-learning.} Most of the existing NAS methods can search a well-performing architecture for a single task. However, for the new task, they have to search for a new architecture; otherwise, the old architecture might not be optimal. Several studies \cite{continual_nas,Auto-meta,transferNAS,meta_NAS_fewshot} combine meta-learning and NAS to solve this problem. A recent work by Lian et al. \cite{transferNAS} proposes a novel and meta-learning based \textit{transferable neural architecture search (T-NAS)} method to generate a meta-architecture, which can be adapted to new tasks easily and quickly through a few gradient steps. Another challenge of learning new data is few-shot learning scenarios, where there is only a limited number of data for the new tasks. \cite{Auto-meta} and \cite{continual_nas} apply NAS to few-shot learning to overcome this challenge, while they only search for the most promising architecture and optimize it to work on multiple few-shot learning tasks. Elsken et al. \cite{meta_NAS_fewshot} propose a gradient-based meta-learning NAS method, namely METANAS, which can generate \textit{task-specific} architectures more efficiently as it does not require meta-retraining.


\textbf{Unsupervised learning.} Meta-learning based NAS methods focus more on labeled data, while in some cases, only a portion of the data may have labels or even none at all. Liu et al. \cite{UnNAS} propose a general problem setup, namely \textit{unsupervised neural architecture search (UnNAS)}, to explore whether labels are necessary for NAS. They experimentally demonstrate that the architectures searched without labels are competitive with those searched with labels; therefore, the results show that labels are not necessary for NAS and provoke people to think about what exactly affects NAS.


\subsubsection{Remember old knowledge}

In addition, an AutoML system must be able to constantly acquire and learn from new data, without forgetting the knowledge from old data. However, when we use new datasets to train a pretrained model, the performance of the model on the previous data sets will be greatly reduced. Incremental learning may alleviate this problem. For example, Li and Hoiem \cite{lwf} propose the \textit{learning without forgetting} (LwF) method, which trains the model using only new data, while preserving its original capabilities. In addition, iCaRL \cite{icarl} makes progress based on LwF. It only uses a small part of old data for pretraining, and then gradually increases the proportion of a new class of data that is used to train the model.



\end{document}
