Year: 2019

Abstract:
Neural Architecture Search (NAS) aims at automatically finding neural network architectures within an enormous designed search space. The search space usually contains billions of network architectures which causes extremely expensive computing costs in searching for the best-performing architecture. One-shot and gradient-based NAS approaches have recently shown to achieve superior results on various computer vision tasks such as image recognition. With the weight sharing mechanism, these methods lead to efficient model search. Despite their success, however, current sampling methods are either fixed or hand-crafted and thus ineffective. In this paper, we propose a learnable sampling module based on variational auto-encoder (VAE) for neural architecture search (NAS), named as VAENAS, which can be easily embedded into existing weight sharing NAS framework, e.g., one-shot approach and gradient-based approach, and significantly improve the performance of searching results. VAENAS generates a series of competitive results on CIFAR-10 and ImageNet in NasNet-like search space. Moreover, combined with one-shot approach, our method achieves a new state-of-the-art result for ImageNet classification model under 400M FLOPs with 77.4% in ShuffleNetlike search space. Finally, we conduct a thorough analysis of VAENAS on NASbench-101 dataset, which demonstrates the effectiveness of our proposed methods.

heading: 1 INTRODUCTION
text: Deep neural networks have greatly pushed the frontier of various influential applications by designing novel neural architectures (Krizhevsky et al. (2012); Goodfellow et al. (2014); He et al. (2016)). Automatic model design of neural network architectures without human intervention, known as neural architecture search (NAS), has drawn much attention of the community recently. It has resulted in state-of-the-art performance in the domain of image recognition (Zoph et al. (2018); Real et al. (2019)), object detection (Ghiasi et al. (2019); Chen et al. (2019)) and semantic segmentation (Liu et al. (2019)).
Generally, the magnitude of search space for NAS tasks is enormous. For example, NasNet (Zoph et al., 2018) presents a search space with 6 × 109 possible cells. Searching on such huge designed space cost 2400 GPU days. Weight sharing mechanism has shown to be a promising avenue for efficient NAS. Latest algorithms on efficient NAS fall into two categories: one-shot approaches (Bender et al. (2018)) and gradient-based approaches (Liu et al. (2018b)). In one-shot approaches, prior works focus on adopting a fixed sampling strategy (Guo et al. (2019); Bender et al. (2018); Chu et al. (2019)). In gradient-based approaches, search is typically performed without sampling procedure (Liu et al. (2018b); Xie et al. (2018)) or hand-crafted sampling (Liu et al. (2018a)). Despite the success of these NAS methods on various benchmarks, however, these sampling approaches do not interactively learn the architecture distribution as the search process goes along, which makes the sampling procedure ineffective.
In this paper, we propose a learnable and interactive architecture sampling module based on VAE for NAS, named as VAENAS. There are two advantages of VAENAS: 1) it learns the good-performing architecture distribution which could be used to reduce search space. 2) it can be embedded into existing NAS framework and improve the performance of current NAS methods.
After developing the generic VAENAS approach, we study in detail the application of VAENAS module via two mainstream NAS approaches: one-shot approach (Brock et al. (2017); Guo et al.
(2019)) and gradient-based approach (Liu et al. (2018b); Cai et al. (2018)), both of which have obtained state-of-the-art performance on neural architecture search tasks. We show how VAENAS module can be embedded in both approaches and make performance improvement consistently.
We validate VAENAS with various search space on two benchmark datasets (CIFAR-10 and ImageNet) for image recognition. On NASNET-like search space, we apply VAENAS on both gradientbased methods and one-shot methods. Specifically, combined with one-shot approach, VAENAS achieves 2.26% test error on CIFAR-10 and 75.8% accuracy on ImageNet, outperforming state-ofthe-art NAS methods. On a Shufflenet-like search space, VAENAS combined with one-shot achieves 77.4% top-1 accuracy with 365M FLOPs on ImageNet classification, outperforming state-of-the-art Efficient-B0 by 1.1% with 6.5% less computational complexity. Finally, we perform a thorough analysis of VAENAS on NAS-101 benchmark, to show the effectiveness of our proposed architecture sampling methods.

heading: 2 RELATED WORK
text: Neural Architecture Search. Recently the design of efficient neural networks has largely shifted from leveraging human knowledge to automatic methods, which is known as neural architecture search(NAS). Early NAS methods adopt reinforcement learning (RL)(Zoph et al., 2018) or evolutionary strategy (Real et al., 2019) to search on thousands of individually evaluated networks, which is computational-consuming. Recent works focus on efficient search methods, which falls into two categories: one-shot approach (Guo et al. (2019); Chu et al. (2019)) and gradient-based approach (Liu et al. (2018b); Cai et al. (2018)), both achieve state-of-the-art results on a series of benchmark dataset (Chen et al. (2019); Ghiasi et al. (2019); Liu et al. (2019)) with various search space. We argue that sampling method matters in NAS and a learnable sampling algorithm can significantly improve the NAS performance.
Sampling. Some prior works have applied sampling methods to NAS framework. For one-shot approach, Bender et al. (2018) randomly zero out a subset of the operations during super-network training. Guo et al. (2019); Stamoulis et al. (2019) adopt uniform sampling and Chu et al. (2019) employ fair uniform sampling to reduce training bias in one-shot models. For gradient-based approach, Cai et al. (2018) propose a multinomial distribution sampling to alleviate large memory consumption issue in conventional gradient NAS methods (Liu et al. (2018b)). Our approach presents a new perspective of sampling methods of NAS application.
Algorithm 1 VAE Training Pipeline Input: Architectures and corresponding performance set S = {(αi, ACCi)}Ni , # of training itera-
tions niters, parameters of VAE encoder φ, parameters of VAE deocder θ, ranking ratio K. Output: Updated VAE parameters φ, θ 1: Rank S by the descending order of ACCi; 2: Select top K% architectures as VAE training dataset SK , SK ⊂ S ; 3: for j = 1, ..., niters do 4: Optimize φ and θ with SK . 5: end for

heading: 3 VAENAS

heading: 3.1 MOTIVATION
text: Many prior works in NAS have discussed modeling the architecture distribution Γ(α). The typical Γ(α) is to adopt either fixed architecture distribution (e.g., uniform distribution Bender et al. (2018); Guo et al. (2019)), or hand-crafted architecture distribution (e.g., Gumbel softmax distribution in Liu et al. (2018b); Xie et al. (2018)).
Conceptually, it is expected that the architecture distribution Γ(α) can interactively learn from the weight sharing super-network as the searching process goes along. To this end, we propose a learnable architecture distribution, where the distribution Γt(α) at time t is learned from the new incoming architecture α and prior architecture distribution at t− 1 time is Γt−1(α), we can formalize the distribution learning process as:
Γt(α)← T (Γt−1(α),Metrict−1(α)) (1)
where Metric denotes the predefined metric, e.g., accuracy or loss, and T denotes the stochastic process. In equation 1, the distribution of architectures at time t is learned by both the prior knowledge on architecture distribution Γ(α) and new architectures data α at t− 1 time, as in Figure 1. As the architecture search proceeds, we randomly sample multiple architectures, rank these architectures according to the predefined metric. The T incrementally refines the distribution of architectures by continually learning the good-performing architectures from the weight sharing network. Alternatively, the weight sharing network updates the architectures weights, where the architectures is sampled from T . There are many methods that can be used to model this distribution, and we choose VAE due to its training stability as well as the convenience to be embedded into the existing NAS frameworks.

heading: 3.2 THE USAGE OF VAE
text: VAE approximates the marginal likelihood of architecture distribution log pθ(α) by maximizing variational lower bound:
−DKL(qφ(z|α)||pθ(z)) + Ez∼qφ(z|α)[log pθ(α|z)] (2)
Specifically, the left term is the Kullback-Leibler divergence between the approximated posterior (recognition model) qφ(z|α) and the prior p(z). And the right term is the expectation of reconstruction loss where pθ(α|z) denotes variational inference. As a result, to sample α from the marginal distribution pθ(α), VAE samples latent variable z according to the prior distribution pθ(z) and feed z into the inference model pθ(α|z). Commonly, the prior distribution pθ(z) can be set as standard Gaussian distribution N(0, I).
Let α = {oi}ni be a sequence of operation oi representing an architecture string, where n is the total number of nodes in a network or cell. We use an encoder E to take α as input and maps it into parameters µα and σα corresponding to a normal distribution N(µα,σα). Symmetrically, a decoderD is used to map ze to a reconstructed architecture ᾱ, where ze ∼ N (µe,σe). The encoder E corresponds qφ(z|α) and the decoder D corresponds pθ(α|z). Specifically, the encoder E and the decoder D are implemented by two LSTM networks.
Algorithm 2 VAENAS - One-Shot Input: Super-network training iterations nsupiters, VAE training iterations nvaeiters, interval to train
VAE nvae, # of sampled architectures (rank) Ns, # of architectures seed Nseeds, super-network G, search space A, network weightsW , exploitation increase parameter inc, ranking ratio K, parameters of VAE module φ and θ.
Output: The final architecture α∗ 1: Define Γ(α) = (1− ) ∗ U(α) + ∗ pθ(α|z); Set = 0; 2: for i = 1, ..., nsupiters do 3: Sample α ∼ Γ(α); 4: Update network weightsWα; 5: if i mod nvae == 0 then 6: Sample Ns number of architectures {α} from Γ(α), α ∼ Γ(α); 7: Evaluate {α}, obtain accuracy {ACC}; 8: Set S = {(αi, ACCi)}Nsi ; 9: Call algorithm 1 VAE(S, φ, θ, nvaeiters,K) to update VAE module; 10: end if 11: ← + inc; 12: end for 13: Sample Nseeds number of architectures {α} from pθ(α|z), α ∼ pθ(α|z); 14: Set Sseeds = {α}. 15: Derive the final architecture α∗ from Search(G,A, Sseeds);

heading: 4 VAENAS FOR NEURAL ARCHITECTURE SEARCH
text: In this section, we demonstrate how VAENAS is integrated into existing NAS frameworks. Section 4.1 gives the formal definition of weight sharing mechanism. Section 4.2 gives detailed description of VAENAS combined with one-shot framework. Section 4.3 shows VAENAS combined with gradient-based framework.

heading: 4.1 WEIGHT-SHARING MECHANISM
text: Weight sharing approaches construct a super-network G(α,W ) that contains all the valid architectures α with shared weights W . Any architecture α is a sub-graph in the super-network and inherits corresponding weights Wα. Thus we can formalize the training of weight sharing mechanism as solving a bi-level optimization problem:
W ∗α = arg min Wα Eα∼Γ(α)[Ltrain(G(α,Wα))] (3)
α∗ = arg min α∈α Lval(G(α,W ∗ α)) (4)
where Γ(α) is an architecture distribution. There are two main frameworks which utilize weightsharing mechanism: one-shot approach and gradient-based approach.

heading: 4.2 ONE-SHOT FRAMEWORK
text: Review of One-Shot Architecture Search. Generally, one-shot approaches (Liu et al. (2018b); Cai et al. (2018); Xie et al. (2018)) consist of three steps: 1) train a weight sharing super-network. 2) rank architectures based on its performance on the super-network. 3) derive the final architecture via a search strategy. Previous methods typically adopt hand-crafted sampling methods (Bender et al., 2018; Guo et al., 2019; Chu et al., 2019).
Combine One-Shot Approach with VAENAS. Algorithm 2 shows the detailed pipeline of VAENAS combined with one-shot approach. VAENAS-OS utilizes one-shot framework and optimizes sampling distribution:
Γ(α) = (1− ) ∗ U(α) + ∗ pθ(α|z) (5) where U(α) is random uniform distribution, pθ(α|z) is variational distribution, and is exploitation parameter. On supernet training, architectures are sampled from pθ(α|z) and U(α) with probability
Algorithm 3 VAENAS - Gradient-Based Input: Ranking ratio K, network training iterations niters, VAE training iterations nvaeiters, interval
to train VAE nvae, # of sampled architectures (rank) Ns, network weights W , architecture weights w, parameters of VAE module φ and θ.
Output: The final architectures α∗ 1: for i = 1, ..., niters do 2: Sample α ∼ pθ(α|z); 3: Update architecture weights wα. 4: Update super-network weightWα 5: if i mod nvae == 0 then 6: Sample Ns number of architectures {α} from U(α), α ∼ U(α); 7: Evaluate {α}, obtain accuracy {ACC}; 8: set S = {(αi, ACCi)}Nsi ; 9: Call algorithm 1 VAE(S, φ, θ, nvaeiters,K) to update VAE module; 10: end if 11: end for 12: Derived the final architecture α∗ based on the learned w.
and 1− . As the search phase continues, the increases, thus the super-network trains more samples from VAENAS. The good-performing architectures, for example, with k% highest accuracy, are collected every nvae epochs and fed into the VAENAS module to train. As the training phase proceeds, the variational distribution pθ(α|z) would converge to generating good-performing architectures. On search phase, the initial seeds are sampled from pθ(α|z) and then search with genetic algorithm as Guo et al. (2019). Due to the weights of good-performing architectures are trained more adequately, intuitively, the super-network would be more predictive. Algorithm 2 shows the detailed pipeline of VAENAS combined with the one-shot approach.
Why Architecture-Dependent Sampling for One-Shot? The conventional sampling methods for one-shot NAS, such as zero out random operations (Bender et al. (2018)), uniform sampling (Guo et al. (2019)) and fair sampling (Chu et al. (2019)) are fixed sampling methods.
One issue of fixed architecture distribution in one-shot approach is its ineffectiveness to sample good-performing architectures, both during super-network training and architecture search. When train a super-network with architectures sampled from a pre-defined architecture distribution such as uniform distribution, it is likely that the best-performing architectures are not picked; thus the search algorithm fails to seek them out due to the low performance of best architectures on the super-network. Moreover, the search strategy usually adopts evolution/RL algorithms, where a set of architectures are selected as seeds via sampling method. Due to the evaluation process is expensive, only a small set of architectures are evaluated and ranked. Thereby the initialized set for search strategy can be sub-optimal. VAENAS resolve above issues by adopting an architecturedependent distribution on super-network training and search phase. By learning the distribution of good-performing architectures, VAENAS ensures the sampling procedure effective since the samples from the variational distribution pθ(α|z) are guaranteed to have good performance on the supernetwork.

heading: 4.3 GRADIENT-BASED FRAMEWORK
text: Review of Gradient-Based Architecture Search. Gradient-based approaches (Liu et al. (2018b); Cai et al. (2018); Xie et al. (2018)) employ an independent discrete architecture parameter to model the networks, thus we can follow the exact bi-level optimization process as we describe in equation 3 and 4. The common practice of gradient-based approach does not contain sampling process. Proxylessnas (Cai et al. (2018)) introduce a multinomial distribution sampling process prior to the optimization step of architecture weights.
Combine Gradient-Based Approach With VAENAS. Alternatively, we consider replacing the sampling procedure by VAENAS:
Γ(α) = pθ(α|z) (6)
Specifically, we sample an architecture αi from pθ(α|z), and update super-network weights Wαi and multinomial distribution parameters xi accordingly. Algorithm 3 shows the detailed pipeline.
Why Independent Sampling Module Necessary? Conventional gradient-based methods (Liu et al. (2018b)) do not contain the sampling process: all architecture operations are updated during training at each iteration. These methods bring overwhelming memory and computation consumption issue, such that direct model search and direct dataset search are incapable. Proxylessnas (Cai et al. (2018)) present multinomial distribution to sample the architectures in the search phase.
However, the probability of multinomial distribution is obtained by applying softmax to architecture weights. The principal limitation is that the model weights and architecture weights are mutually interactional. To be concrete, if an architecture gets more training, more likely it will be sampled again in the next iteration. This winner takes all effect causes premature convergence and reduces the diversity of architectures. Moreover, the gradient tends to flow through non-parameter operations, such as identity (the architectures derived by gradient-based method is typically small, i.e., 3.4M on CIFAR10 (Liu et al. (2018b)). The VAENAS sampling module, which serves as an independent sampling module, helps to 1) increase the diversity of architectures that can be exploited in the training process, as a result, alleviate the premature convergence phenomenon, 2) search for large models. Large models naturally obtain better performance than small models.

heading: 5 EXPERIMENTS

heading: 5.1 NASNET-LIKE SEARCH SPACE.
text: The detailed training strategy, search space and hyper-parameters settings can be found in Appendix A.1. Our VAENAS is evaluated on both gradient-based and one-shot approaches, and compared with the state-of-the-art NAS methods under the same search space. We use ’OS’ to denote one-shot approach and use ’G’ to denote gradient-based approach.
Performance on CIFAR-10. We present the results on Table 1. Combined with gradient-based method, our method achieves 2.4% test error with 4.4M parameters. Combined with one-shot approach, our method gives two results. The first one is searched with parameter constraint of 3.5M parameters, and obtain 2.5% test error, and the second one is trained without any constraint and obtain 2.26% test error with 5.2M parameters.
Performance on ImageNet. We present the results on Table 2. Combined with gradient-based approach, our method obtains 75.6% top-1 accuracy with 568M FLOPs. Combined with one-shot
approach, our method obtains 75.8% top-1 accuracy with 573M FLOPs. Both results surpass previous state-of-the-art results.

heading: 5.2 IMAGENET CLASSIFICATION UNDER MOBILE SETTING
text: Comparison with State-of-the-art methods. Table 3 lists a number of state-of-the-art models’ FLOPs on ImageNet dataset. We select models with the range of FLOPS from 200M to 400M. Notably, VAENAS-OS outperforms state-of-the-art models by a large margin. In particular, the accuarcy of VAENAS is 1.1% higher than EfficientNet-B0 (Tan & Le, 2019), recent state-of-theart method, while using 6.5% less computational budget. To best of our knowledge, VAENAS-OS is the first model surpass 77% under 400M FLOPs without using strong regularization and data augmentation techniques such as AutoAugment.

heading: 5.3 VAENAS ON NAS-BENCH-101 DATASET
text: NAS-Bench-101 dataset (Ying et al., 2019) is a carefully constructed architecture dataset for NAS research, including over 5 million already trained architectures on CIFAR-10. The ground-truth accuracy of architectures can be gotten from NAS-Bench-101 dataset directly. We compare VAENAS sampling with uniform sampling (also known as random search Li & Talwalkar (2019)).
We design two methods for training VAENAS. The weight-sharing method follows Section 4.1, where VAENAS is trained with a super-network on NAS-Bench-101 search space. The design of super-network is described in Appendix A.5. The non-weight-sharing method trains VAENAS with a set of high-accuracy architectures. 6000 trained architectures are sampled and the top-1500 models form the training set.
Influence of noise on accuracy. The training of VAENAS is based on high-accuracy architectures, while ground-truth accuracy of architectures is hard to be obtained in most cases. We add various levels of noise on the accuracy, then rank architectures and select high-accuracy architectures to train corresponding VAENAS module. As displayed in Table 4 and Fig. 2, VAENAS is robust to a certain extent of noise. Futhermore, the accuracy of architectures in weight-sharing methods have a noise on super-network, while the accuracy on super-network is inconsistent with ground-truth accuracy. The results of VAENAS trained by weight-sharing method proof that VAENAS works well with NAS frameworks.
Comparisons of sampling methods. We sample a number architectures by VAENAS and random method and evaluate the maximum accuracy of architectures, which is shown in Table 4. VAENAS, trained with super-network or clear ground-truth accuracy, outpeforms random sampling (+0.79% with 10 samples). In addition, we sample 5000 architectures with random sampling and VAENAS sampling, then display the distribution of samples in Fig. 2. The distribution of VAENAS covers high-accuracy architectures, while the distribution of random sampling is relatively dispersed.
Combination with evolution search. We execute evolution search on NAS-Bench-101 and replace random sampling by VAENAS during the initialization of population. The results are shown in Table 4. VAENAS outperforms uniform sampling by 0.7%. It proves that VAENAS is helpful to the search strategy, since the convergence of evolution search is accelerated.

heading: 6 CONCLUSION
text: In this paper, we argue sampling matters in NAS and present a learnable sampling method based on VAE. The VAENAS learns the architecture distribution and is interactive with NAS search process. As a result, by embedding into the existing efficient NAS framework, we achieve a series of state-ofthe-art results on various dataset and search space. Overall, we believe that the VAENAS approach provides a practical new perspective on sampling methods in neural architecture search.

heading: A APPENDIX
text: A.1 IMPLEMENTATION DETAILS OF VAENAS
VAENAS-OS ShuffleNet training details. VAENAS-OS is trained for 480 epochs with batch size 1024 on 8 2080-Ti GPUs. It is based on the Pytorch (Paszke et al. (2017)). The network parameters are optimized using an SGD optimizer with an initial learning rate of 0.5 (decayed linearly after each iteration), a momentum of 0.9 and a weight decay of 3 × 10−5. Additional enhancements including label smoothing (Szegedy et al. (2016)) and Dropout with 0.5 on last FC layer. We follow the common practice to use inception augmentation. No other data augmentation method is used.
VAENAS-OS/VAENAS-G NASNet training details: ImageNet. The model is trained for 300 epochs with batch size 512 on 8 2080-Ti GPUs. It is based on the Pytorch (Paszke et al. (2017)). The network parameters are optimized by using an SGD optimizer with an initial learning rate of 0.5 (decayed linearly after each iteration), a momentum of 0.9 and a weight decay of 3× 10−5. Additional enhancements include label smoothing (Szegedy et al. (2016)) and auxiliary tower with 0.4. We follow the common practice to use inception augmentation. The initial width is 48 and depth is 14, which follows the same setting as Liu et al. (2018b).
CIFAR-10. The model is trained by following the common pipeline (Liu et al. (2018b); Real et al. (2019); Zoph et al. (2018); Pham et al. (2018); Liu et al. (2018a)). it is trained for 600 epochs with batch size 48 on single GPU. Additional enhancements include label smoothing (Szegedy et al. (2016)), auxiliary tower with 0.4, drop path with 0.2 and Cutout (DeVries & Taylor (2017)).
A.2 IMPORTANCE OF VAENAS
More ablation study will be available in the Appendix A.3. In this section, we use gradient-based NAS approach and one-shot NAS approach as two baseline framework, and compare the result with VAENAS and without VAENAS using the same search and training strategy. The baseline method of gradient-based approach is re-implemented based on Cai et al. (2018) and one-shot approach is re-implemented based on Guo et al. (2019). The results are shown in Table 5. We can observed that the the framework with VAENAS achieve significantly better performance on both CIFAR-10 and ImageNet.
A.3 ABLATION STUDY
Influence of Depth Gap between Search and Evaluation. One issue encountered in prior works with both one-shot NAS approach and gradient-based approach is the challenge of search on the network with the same depth as the evaluated models. We therefore study the effect of VAENAS from the perspective of direct model search. Table 6 shows the results of baseline with different depth that one-shot method fails to find the good architecture when directly search on target model. One explanation is that the search space is too large for the conventional uniform sampling.
A.4 NETWORK ARCHITECTURE
This section shows the details of network structures which we searched for NASNet-like search space and ShuffleNet-like search space.
ShuffleNet-like search space. We designed a search space based on ShuffleNetV2. Specifically, we construct a over-parameterized network with 20 layers, each layer can choose between four operations:
• Shuffle Convolution 3x3 • Shuffle Convolution 5x5 • Shuffle Convolution 7x7 • Shuffle Xception 3x3
ReLU non-linearity are replaced by Swish if conv 5x5, conv 7x7 or Xception are chosen. Squeezeand-Exited module are also adopted if conv 7x7 and Xception are chosen. We utilized VAENAS combined with one-shot framework to do the search.
NASNet search space. We modify the search space of DARTS (Liu et al., 2018b). A cell is a directed acyclic graph, and every edge in the graph represents a kind of computation operation. Different from DARTS, in our search space, one node could have more than two predecessors in one cell. The maximum number of edges in one cell is 2 + 3 + 4 + 5 = 14, while ’None’ is an available operation in our search space. The list of candidate operations is listed as follows:
• None • Average Pooling 3x3 • Max Pooling 3x3 • Skip Connect • Separate Convolution 3x3 • Separate Convolution 5x5 • Separate Convolution 7x7 • Dilated Convolution 3x3
The magnitude of search space is 82×14, while normal cell and reduction cell are searched jointly. We present the cell searched by our methods in Fig.4 and Fig.5.
A.5 SUPER-NETWORK AND VAENAS ON NAS-BENCH-101 SEARCH SPACE
Super-network. NAS-Bench-101 is a cell-based search space, and the details of NAS-Bench-101 search space is introduced in Ying et al. (2019). While NAS-Bench-101 is not proposed for weightsharing NAS methods, we design one super-network which covers architectures in NAS-Bench-101.
The output of one cell in NAS-Bench-101 search space is the concatenation of input nodes. The illustration Fig.6 shows one sampled cell on the super-network. However, the output channels of
one middle node is not fixed, so weight-shared tensor is utilized to save the parameters of convolutional operations. The illustration Fig.7 shows one example of dividing convolutional kernel for computation.
Representation and Sampling. In NAS-Bench-101 dataset, one architecture can be represented as a 7x7 upper-triangle adjacent matrix and 5 operations. To simply the representation of architectures, the adjacent matrix is converted to a list of edges a = {a1, a2, ..., a21}, ai ∈ {0, 1}, and operations compose a vector op = {op1, op2, ..., op5}, opi ∈ {conv1×1, conv3×3,maxpool}. The integrated architecture is a vector α = concat(a,op).
Two constraints of edges determine the validity of one sampled cell. One is the number of edges in one cell is no more than 9 in a cell. The other is that at least one path connect the input node and output node in a cell, which indicate the connectivity of the cell. Under these two constraints, we design the following sampling strategy. 21 number in range [0, 1] is sampled by random sampling or VAE sampling, then the indexes of top-9 numbers is selected as IDX . We set ai = 1 when ai ∈ IDX , and set aj = 0 when j /∈ IDX . If the sampled cell is not connected, we perform above sampling process again.
Evolution Search on NAS-Bench-101. The setting of evolution search follows (Guo et al. (2019)). In addition, to make sure the validity of descendants, the mutation and crossover of the edge list a should be planned carefully.
For mutation, an index i, ai = 1 and another index j, aj = 0 are selected randomly. Another new sample a′ is generated by exchanging ai and aj . We repeat this process until a′ satisfy connectivity.
For crossover, two edge lists ax and ay are selected randomly. Then an index i, axi = 1, a y i = 0 and another index j, axj = 0, a y j = 1 are selected. One new sample a
′ is generated by exchanging axi and axj . If a
′ does not maintain connectivity, it will be dropped, and the crossover process will be repeated.

Review summaries:
This paper proposed to use VAE to learn a sampling strategy in neural architecture search. The main idea is to use the currently high-performing networks to train a VAE from which the sampled architectures for the next iteration will likely supply both high-performing networks and better diversity coverage. The experiments are extensive, including results under various settings.