Title: VAENAS: SAMPLING MATTERS IN NEURAL ARCHI-TECTURE SEARCH

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 VAE-NAS, 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.

1. INTRODUCTION:

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 × 10 9 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.

Figure 1 : The illustration of VAENAS mechanism. VAENAS mechanism contains two modules, one is VAE model, and the other is an architecture search system. These two modules are updated alternately. Specifically, three steps are carried out on VAENAS mechanism. 1) Architectures are sampled from VAE model and fed into the architecture search system. 2) The architecture search system evaluates and sorts sampled architectures. 3) The VAE model is trained with top-50% architectures.

(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 Ima-geNet) 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.

2. RELATED WORK:

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. 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:

EQUATION

where M etric 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.

3.2. THE USAGE OF VAE:

VAE approximates the marginal likelihood of architecture distribution log p θ (α) by maximizing variational lower bound:

EQUATION

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 α = {o i } n i be a sequence of operation o i 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 decoder D is used to map z e to a reconstructed architecture ᾱ, where z e ∼ 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. 

1: Define Γ(α) = (1 -) * U (α) + * p θ (α|z); Set = 0; 2: for i = 1, ..., n sup iters do 3: Sample α ∼ Γ(α); 4:

Update network weights W α ;

5:

if i mod n vae == 0 then 6:

Sample N s number of architectures {α} from Γ(α), α ∼ Γ(α);

7:

Evaluate {α}, obtain accuracy {ACC};

8: Set S = {(α i , ACC i )} Ns i ; 9:

Call algorithm 1 VAE(S, φ, θ, n vae iters , K) to update VAE module;

10:

end if 11:

← + inc ; 12: end for 13: Sample N seeds number of architectures {α} from p θ (α|z), α ∼ p θ (α|z); 14: Set S seeds = {α}. 15: Derive the final architecture α * from Search(G, A, S seeds );

4. VAENAS FOR NEURAL ARCHITECTURE SEARCH:

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.

4.1. WEIGHT-SHARING MECHANISM:

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:

EQUATION

EQUATION

where Γ(α) is an architecture distribution. There are two main frameworks which utilize weightsharing mechanism: one-shot approach and gradient-based approach.

4.2. ONE-SHOT FRAMEWORK:

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 VAE-NAS combined with one-shot approach. VAENAS-OS utilizes one-shot framework and optimizes sampling distribution:

EQUATION

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 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 n vae 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.

4.3. GRADIENT-BASED FRAMEWORK:

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: Specifically, we sample an architecture α i from p θ (α|z), and update super-network weights W αi and multinomial distribution parameters x i accordingly. Algorithm 3 shows the detailed pipeline.

EQUATION

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.

5. EXPERIMENTS:



5.1. NASNET-LIKE SEARCH SPACE.:

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.

5.2. IMAGENET CLASSIFICATION UNDER MOBILE SETTING:

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.

5.3. VAENAS ON NAS-BENCH-101 DATASET:

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) ). 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. 

6. CONCLUSION:

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. 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. 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 8 2×14 , while normal cell and reduction cell are searched jointly.

We present the cell searched by our methods in Fig. 4 and Fig. 5 . 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 = {a 1 , a 2 , ..., a 21 }, a i ∈ {0, 1}, and operations compose a vector op = {op 1 , op 2 , ..., op 5 }, op i ∈ {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 a i = 1 when a i ∈ IDX, and set a j = 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, a i = 1 and another index j, a j = 0 are selected randomly. Another new sample a is generated by exchanging a i and a j . We repeat this process until a satisfy connectivity.

For crossover, two edge lists a x and a y are selected randomly. Then an index i, a x i = 1, a y i = 0 and another index j, a x j = 0, a y j = 1 are selected. One new sample a is generated by exchanging a x i and a x j . If a does not maintain connectivity, it will be dropped, and the crossover process will be repeated.

:



Figures and Tables:

Figure 2: Compare the distribution of VAE Sampling with Random Sampling. (a) VAENAS trained with super-network. (b) VAENAS trained with ground truth accuracy. (c) VAENAS trained with 0.1% noise on accuracy. (d) VAENAS trained with 0.5% noise on accuracy.

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.

Figure 3: VAENAS-OS ShuffleNet architectures. We highlight the input and output tensor shape. Conv denotes convolution layer. SF denotes ShuffleNetV2 module. SE denotes Squeeze-and-Excitation module.

Figure 4: VAENAS-OS normal cell trained on CIFAR-10.

Figure 5: VAENAS-OS reduction cell trained on CIFAR-10.

Figure 6: One sampled cell on NAS-Bench-101 super-network. Every path contains 9 edges, while some edges may be useless in the cell.

Figure 7: One example of weight-shared tensors for convolution kernel. O × C × K × K is the size of kernel. The blue cube shows the whole tensor, and the green cube shows the part used for the O 2 × C 2 × K × K convolution operation.

Algorithm 1 VAE Training Pipeline Input: Architectures and corresponding performance set S = {(α i , ACC i )} N i , # of training iterations n iters , parameters of VAE encoder φ, parameters of VAE deocder θ, ranking ratio K. Output: Updated VAE parameters φ, θ 1: Rank S by the descending order of ACC i ; 2: Select top K% architectures as VAE training dataset S K , S K ⊂ S ; 3: for j = 1, ..., n iters do

Table content: <table><tr><td>4:</td><td>Optimize φ and θ with S K .</td></tr><tr><td colspan="2">5: end for</td></tr><tr><td colspan="2">3 VAENAS</td></tr><tr><td colspan="2">3.1 MOTIVATION</td></tr><tr><td colspan="2">Many prior works in NAS have discussed modeling the architecture distribution Γ(α). The typical</td></tr><tr><td colspan="2">Γ(α) is to adopt either fixed architecture distribution (e.g., uniform distribution Bender et al. (2018);</td></tr><tr><td colspan="2">Guo et al. (2019)), or hand-crafted architecture distribution (e.g., Gumbel softmax distribution in</td></tr><tr><td colspan="2">Liu et al. (2018b); Xie et al. (2018)).</td></tr></table>

Algorithm 2 VAENAS -One-Shot Input: Super-network training iterations n sup iters , VAE training iterations n vae iters , interval to train VAE n vae , # of sampled architectures (rank) N s , # of architectures seed N seeds , super-network G, search space A, network weights W, exploitation increase parameter inc , ranking ratio K, parameters of VAE module φ and θ. Output: The final architecture α *

Table content: <table/>

Algorithm 3 VAENAS -Gradient-Based Input: Ranking ratio K, network training iterations n iters , VAE training iterations n vae iters , interval to train VAE n vae , # of sampled architectures (rank) N s , network weights W, architecture weights w, parameters of VAE module φ and θ. Output: The final architectures α * 1: for i = 1, ..., n iters do

Table content: <table><tr><td>2:</td><td>Sample α ∼ p θ (α|z);</td></tr><tr><td>3:</td><td>Update architecture weights w α .</td></tr><tr><td>4:</td><td>Update super-network weight W α</td></tr><tr><td>5:</td><td>if i mod n vae == 0 then</td></tr><tr><td>6:</td><td>Sample N s number of architectures {α} from U (α), α ∼ U (α);</td></tr><tr><td>7:</td><td>Evaluate {α}, obtain accuracy {ACC};</td></tr><tr><td>8: 9:</td><td>set S = {(α i , ACC i )} Ns i ; Call algorithm 1 VAE(S, φ, θ, n vae iters , K) to update VAE module;</td></tr><tr><td>10:</td><td/></tr></table>

Comparison with state-of-the-art architectures on CIFAR-10 under the NASNET-like search space. * denotes model is trained with cutout. OS denotes one-shot approach. G denotes gradient-based approach. † indicates hard parameters constraint in search phase.

Table content: <table><tr><td>Architecture</td><td colspan="3">Test Error Params Search Method</td></tr><tr><td/><td>(%)</td><td>(M)</td><td/></tr><tr><td>NASNet-A * (Zoph et al. (2018))</td><td>2.65</td><td>3.3</td><td>RL</td></tr><tr><td>AmoebaNet-B  *  (Real et al. (2019))</td><td>2.55±0.05</td><td>2.8</td><td>Evolution</td></tr><tr><td>Hierarchical Evolution (Liu et al. (2017))</td><td>3.75±0.12</td><td>15.7</td><td>Evolution</td></tr><tr><td>PNAS (Liu et al. (2018a))</td><td>3.41±0.09</td><td>3.2</td><td>SMBO</td></tr><tr><td>ENAS * (Pham et al. (2018))</td><td>2.89</td><td>4.6</td><td>RL</td></tr><tr><td>NAO-weight-sharing * (Luo et al. (2018))</td><td>3.53</td><td>2.5</td><td>Gradient</td></tr><tr><td>DARTS * (Liu et al. (2018b))</td><td>2.76±0.09</td><td>3.4</td><td>Gradient</td></tr><tr><td>SNAS * (Xie et al. (2018))</td><td>2.76±0.09</td><td>3.4</td><td>Gradient</td></tr><tr><td>GraphHypernet * (Zhang et al. (2018a))</td><td>4.3±0.1</td><td>5.1±0.6</td><td>Gradient</td></tr><tr><td>DSO-share * (Zhang et al. (2018b))</td><td>2.84±0.07</td><td>3.0</td><td>Gradient</td></tr><tr><td colspan="2">BayesNAS * (Zhou et al. (2019)) + λ = 0.01 2.81±0.04</td><td>3.4</td><td>Gradient</td></tr><tr><td>VAENAS-G *</td><td>2.40</td><td>4.4</td><td>Gradient</td></tr><tr><td>VAENAS-OS *  †</td><td>2.50</td><td>3.4</td><td>Evolution</td></tr><tr><td>VAENAS-OS *</td><td>2.26</td><td>5.2</td><td>Evolution</td></tr></table>

Comparison with state-of-the-art architectures on ImageNet (mobile setting) under NASNET-like search space. † denotes direct search on ImageNet.

Table content: <table><tr><td>Architecture</td><td colspan="4">FLOPs Params Top-1 Acc. Top-5 Acc.</td></tr><tr><td/><td>(M)</td><td>(M)</td><td>(%)</td><td>(%)</td></tr><tr><td>NASNet-A (Zoph et al. (2018))</td><td>564</td><td>5.3</td><td>74.0</td><td>91.6</td></tr><tr><td>AmoebaNet-A (Real et al. (2019))</td><td>555</td><td>5.3</td><td>74.0</td><td>91.5</td></tr><tr><td>AmoebaNet-B (Real et al. (2019))</td><td>555</td><td>5.1</td><td>74.5</td><td>92.0</td></tr><tr><td>AmoebaNet-C (Real et al. (2019))</td><td>570</td><td>6.4</td><td>75.7</td><td>92.4</td></tr><tr><td>PNAS (Cai et al. (2018))</td><td>588</td><td>5.1</td><td>74.2</td><td>91.9</td></tr><tr><td>GraphHypernet (Zhang et al. (2018a))</td><td>569</td><td>6.1</td><td>73.0</td><td>91.3</td></tr><tr><td>BayesNAS (Zhou et al. (2019))</td><td>-</td><td>3.9</td><td>73.5</td><td>91.1</td></tr><tr><td>DARTS (Liu et al. (2018b))</td><td>574</td><td>4.7</td><td>73.3</td><td>91.3</td></tr><tr><td>SNAS (Xie et al. (2018))</td><td>522</td><td>4.3</td><td>72.7</td><td>90.8</td></tr><tr><td>VAENAS-G †</td><td>568</td><td>6.0</td><td>75.6</td><td>92.3</td></tr><tr><td>VAENAS-OS †</td><td>573</td><td>6.1</td><td>75.8</td><td>92.7</td></tr></table>

Comparison with state-of-the-art architectures on ImageNet (200M-400M FLOPs) under ShuffleNet-like search space. * denotes results reported using AutoAugment.

Table content: <table><tr><td>Architecture</td><td colspan="4">FLOPs Params Top-1 Acc. Top-5 Acc.</td></tr><tr><td/><td>(M)</td><td>(M)</td><td>(%)</td><td>(%)</td></tr><tr><td>ShuffleNet V2 1.5 (Ma et al. (2018))</td><td>300</td><td>-</td><td>72.6</td><td>-</td></tr><tr><td>MobileNet V2 1.0 (Sandler et al. (2018))</td><td>300</td><td>3.4</td><td>72.0</td><td>91.0</td></tr><tr><td>MobileNet V3 Large 1.0 (Howard et al. (2019))</td><td>219</td><td>5.4</td><td>75.2</td><td>92.2</td></tr><tr><td>MnasNet-A2 (Tan et al. (2019))</td><td>340</td><td>4.8</td><td>75.6</td><td>92.7</td></tr><tr><td>FBNet-B (Wu et al. (2019))</td><td>295</td><td>4.5</td><td>74.1</td><td>-</td></tr><tr><td>Proxyless GPU (Cai et al. (2018))</td><td>320</td><td>4.0</td><td>74.6</td><td>92.2</td></tr><tr><td>Single-Path NAS (Guo et al. (2019))</td><td>365</td><td>4.3</td><td>75.0</td><td>92.2</td></tr><tr><td>FairNAS-A (Chu et al. (2019))</td><td>388</td><td>4.6</td><td>75.3</td><td>92.4</td></tr><tr><td>EfficientNet-B0 * (Tan &amp; Le (2019))</td><td>390</td><td>5.3</td><td>76.3</td><td>93.2</td></tr><tr><td>Baseline</td><td>360</td><td>6.7</td><td>77.1</td><td>93.3</td></tr><tr><td>VAENAS-OS</td><td>365</td><td>6.7</td><td>77.4</td><td>93.6</td></tr></table>

Comparison of VAENAS and random search on NAS-Bench-101 dataset.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.

Table content: <table><tr><td>Methods</td><td colspan="4">Max accuracy for K samples (%) Evolution</td></tr><tr><td/><td>10</td><td>50</td><td>100</td><td>300</td></tr><tr><td>Random Search</td><td colspan="3">92.93 93.30 93.53</td><td>93.86</td><td>93.39</td></tr><tr><td>Weight-sharing</td><td colspan="3">93.72 93.95 93.98</td><td>94.23</td><td>94.12</td></tr><tr><td>Non-weight-sharing + noise 0</td><td colspan="3">93.56 93.71 93.95</td><td>94.13</td><td>94.14</td></tr><tr><td colspan="4">Non-weight-sharing + noise 0.1% 93.64 93.73 93.97</td><td>94.17</td><td>93.75</td></tr><tr><td colspan="4">Non-weight-sharing + noise 0.5% 92.24 93.35 93.63</td><td>93.83</td><td>93.33</td></tr></table>

The comparison of architectures searched with (w/) or without (w/o) 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. (

Table content: <table><tr><td>Model</td><td>Dataset</td><td colspan="2">w/o VAENAS</td><td/><td>w/ VAENAS</td></tr><tr><td/><td colspan="5">CIFAR-10 Params Top-1 Acc. Params Top-1 Acc.(gain.)</td></tr><tr><td>Gradient</td><td/><td>3.7M</td><td>2.84%</td><td>4.4M</td><td>2.40%(+0.44%)</td></tr><tr><td>One-Shot</td><td/><td>4.3M</td><td>3.33%</td><td>5.2M</td><td>2.26%(+0.93%)</td></tr><tr><td>Model</td><td>Dataset</td><td colspan="2">w/o VAENAS</td><td/><td>w/ VAENAS</td></tr><tr><td/><td>ImageNet</td><td colspan="2">FLOPs Top-1 Acc.</td><td colspan="2">FLOPs Top-1 Acc.(gain.)</td></tr><tr><td>Gradient</td><td/><td>519M</td><td>74.1%</td><td>568M</td><td>75.6%(+1.5%)</td></tr><tr><td>One-Shot</td><td/><td>553M</td><td>73.3%</td><td>573M</td><td>75.8%(+2.5%)</td></tr><tr><td>A APPENDIX</td><td/><td/><td/><td/></tr><tr><td colspan="4">A.1 IMPLEMENTATION DETAILS OF VAENAS</td><td/></tr></table>

NAS framework with different model depth on CIFAR-10.

Table content: <table><tr><td>Model</td><td colspan="3">Params Top-1 Acc. Search Depth</td></tr><tr><td>One-Shot Baseline</td><td>4.3M</td><td>3.33%</td><td>20</td></tr><tr><td>One-Shot Baseline</td><td>3.7M</td><td>2.89%</td><td>8</td></tr><tr><td>VAENAS-OS</td><td>5.2M</td><td>2.26%</td><td>20</td></tr><tr><td>One-Shot Baseline</td><td>3.4M</td><td>2.91%</td><td>8</td></tr><tr><td>One-Shot Baseline</td><td>3.7M</td><td>2.84%</td><td>20</td></tr><tr><td>VAENAS-Gradient</td><td>4.3M</td><td>2.40%</td><td>20</td></tr><tr><td>A.4 NETWORK ARCHITECTURE</td><td/><td/><td/></tr><tr><td colspan="4">This section shows the details of network structures which we searched for NASNet-like search</td></tr><tr><td>space and ShuffleNet-like search space.</td><td/><td/><td/></tr></table>

Peer review (iclr2020):
============ comments after rebuttal I would like to thank the authors for addressing some of my concerns. I believe the new results under Q2 and Q3 are useful additions to strengthen the paper. As for the authors* comments for Q1, I*d like to point out that a *larger* search space is not necessarily more difficult (a more meaningful metric would be the average accuracy of random architectures). It is still possible that the current search space is putting the proposed method at advantage, especially if having dense connections is a useful prior. Given the above, I would like to increase my score from 1 to 3 (weak reject). ============ previous comments Neural architecture search can be formulated as learning a distribution of promising architectures (the sampling policy). Such a distribution is usually represented in a fully factorized fashion (e.g., as a set of multinational distributions as in DARTS). This paper proposes to model the architecture distribution using a VAE instead, where the encoder and decoder are implemented using LSTMs. The authors argue that the increased flexibility of the sampling policy leads to improved performance on CIFAR-10, NASBench and ImageNet. The idea of representing the architecture distribution using VAEs is very natural, which in principle could offer better coverage over interesting regions in the search space as compared to traditional factorized distribution representation (which has a single mode only). While the method itself is interesting, I do not think it has been properly backed up by controlled experiments. This is largely due to the fact that the authors are comparing their method against baselines in fundamentally different search spaces. For instance: * For CIFAR-10 experiments, the authors mentioned in the appendix: *Different from DARTS, in our search space, one node could have more than two predecessors in one cell*. This makes the search space very different from the existing ones as used by NASNet/AmoebaNet/DARTS/SNAS, and it hence remains unclear to what degree the resulting architecture has benefited from the increased in-degrees per node. Note the searched densely connected cells in Figure 4 & 5 in Appendix A.4 are clearly not part of the search space for many of the baselines. * For ImageNet experiments, the authors are using a ShuffleNet-like search space which has fundamentally different building blocks than other architecture search baselines (commonly built on top of inverted bottleneck layers). It is unclear to what degree the 77.4 top-1 accuracy @ 365 MFlops results have benefited from this different search space. Without fair comparisons in a controlled setup, it is impossible for readers to draw any solid conclusion about the true empirical advantages of the method. I*m therefore unable to recommend acceptance for the paper at the moment, but am willing to raise my score if the authors can properly address those issues in the rebuttal. Additional question: How can we isolate it to tell whether the gains come from the LSTMs or the VAEs? Is there any intuition why incorporating a generative sampler based on VAEs is potentially superior to method like ENAS (which involves LSTMs decoders only)?