Generative Adversarial Neural Architecture Search

1 Introduction

Neural architecture search (NAS) improves neural network model design by replacing the manual trial-and-error process with an automatic search procedure, and has achieved state-ofthe-art performance on many computer vision tasks [Elsken et al., 2018]. Since the underlying search space of architectures grows exponentially as a function of the architecture size, searching for an optimum neural architecture is like looking for a needle in a haystack. A variety of search algorithms have been proposed for NAS, including random search (RS) [Li and Talwalkar, 2020], differentiable architecture search (DARTS) [Liu et al., 2018], Bayesian optimization (BO) [Kandasamy et al., 2018], evolutionary algorithm (EA) [Dai et al., 2020], and reinforcement learning (RL) [Pham et al., 2018].

∗Equal Contribution. Correspondence to: Di Niu <dniu@ualberta.ca>, Seyed Rezaei <seyeds.rezaei@huawei.com>.

Despite a proliferation of NAS methods proposed, their sensitivity to random seeds and reproducibility issues concern the community [Li and Talwalkar, 2020], [Yu et al., 2019], [Yang et al., 2019]. Comparisons between different search algorithms, such as EA, BO, and RL, etc., are particularly hard, as there is no shared search space or experimental protocol followed by all these NAS approaches. To promote fair comparisons among methods, multiple NAS benchmarks have recently emerged, including NAS-Bench-101 [Ying et al., 2019], NAS-Bench-201 [Dong and Yang, 2020], and NASBench-301 [Siems et al., 2020], which contain collections of architectures with their associated performance. This has provided an opportunity for researchers to fairly benchmark search algorithms (regardless of the search space in which they are performed) by evaluating how many queries to architectures an algorithm needs to make in order to discover a top-ranked architecture in the benchmark set [Luo et al., 2020; Siems et al., 2020]. The number of queries converts to an indicator of how many architectures need be evaluated in reality, which often forms the bottleneck of NAS.

In this paper, we propose Generative Adversarial NAS (GANAS), a provably converging and efficient search algorithm to be used in NAS based on adversarial learning. Our method is first inspired by the Cross Entropy (CE) method [Rubinstein and Kroese, 2013] in importance sampling, which iteratively retrains an architecture generator to fit to the distribution of winning architectures generated in previous iterations so that the generator will increasingly sample frommore important regions in an extremely large search space. However, such a generator cannot be efficiently trained through back-propagation, as performance measurements can only be obtained for discretized architectures and thus the model is not differentiable. To overcome this issue, GA-NAS uses RL to train an architecture generator network based on RNN and GNN. Yet unlike other RL-based NAS schemes, GA-NAS does not obtain rewards by evaluating generated architectures, which is a costly procedure if a large number of architectures are to be explored. Rather, it learns a discriminator to distinguish the winning architectures from randomly generated ones in each iteration. This enables the generator to be efficiently trained based on the rewards provided by the discriminator, without many true evaluations. We further establish the convergence of GA-NAS

in a finite number of steps, by connecting GA-NAS to an importance sampling method with a symmetric Jensen-Shannon (JS) divergence loss.

Extensive experiments have been performed to evaluate GANAS in terms of its convergence speed, reproducibility and stability in the presence of random seeds, scalability, flexibility of handling constrained search, and its ability to improve already optimized baselines. We show that GA-NAS outperforms a wide range of existing NAS algorithms, including EA, RL, BO, DARTS, etc., and state-of-the-art results reported on three representative NAS benchmark sets, including NASBench-101, NAS-Bench-201, and NAS-Bench-301-it consistently finds top ranked architectures within a lower number of queries to architecture performance. We also demonstrate the flexibility of GA-NAS by showing its ability to incorporate ad-hoc hard constraints and its ability to further improve existing strong architectures found by other NAS methods. Through experiments on ImageNet, we show that GA-NAS can enhance EfficientNet-B0 [Tan and Le, 2019] and ProxylessNAS [Cai et al., 2018] in their respective search spaces, resulting in architectures with higher accuracy and/or smaller model sizes.

2 RelatedWork

A typical NAS method includes a search phase and an evaluation phase. This paper is concerned with the search phase, of which the most important performance criteria are robustness, reproducibility and search cost. DARTS [Liu et al., 2018] has given rise to numerous optimization schemes for NAS [Xie et al., 2018]. While the objectives of these algorithms may vary, they all operate in the same or similar search space. However, [Yu et al., 2019] demonstrates that DARTS performs similarly to a random search and its results heavily dependent on the initial seed. In contrast, GA-NAS has a convergence guarantee under certain assumptions and its results are reproducible.

NAS-Bench-301 [Siems et al., 2020] provides a formal benchmark for all 1018 architectures in the DARTS search space. Preceding NAS-Bench-301 are NAS-Bench-101 [Ying et al., 2019] and NAS-Bench-201 [Dong and Yang, 2020]. Besides the cell-based searches, GA-NAS also applies to macrosearch [Cai et al., 2018; Tan et al., 2019], which searches for an ordering of a predefined set of blocks.

On the other hand, several RL-based NAS methods have been proposed. ENAS [Pham et al., 2018] is the first Reinforcement Learning scheme in weight-sharing NAS. TuNAS [Bender et al., 2020] shows that guided policies decisively exceed the performance of random search on vast search spaces. In comparison, GA-NAS proves to be a highly efficient RL solution to NAS, since the rewards used to train the actor come from the discriminator instead of from costly evaluations.

Hardware-friendly NAS algorithms take constraints such as model size, FLOPS, and inference time into account [Cai et al., 2018; Tan et al., 2019], usually by introducing regularizers into the loss functions. Contrary to these methods, GA-NAS can support ad-hoc search tasks, by enforcing customized hard constraints in importance sampling instead of resorting to approximate penalty terms.

Algorithm 1 GA-NAS Algorithm

• 1: Input: An initial set of architectures X0; Discriminator D; Generator G(x; θ0); A positive integer k;
• 2: for t = 1, 2, . . . , T do
• 3: T ← top k architectures of ⋃t-1 i=0 Xi according to the performance evaluator S(.).
• 4: Train G and D to obtain their parameters

• 5: Let G(x; θt) generate a new set of architectures Xt.
• 6: Evaluate the performance S(x) of every x ∈ Xt.
• 7: end for

3 The ProposedMethod

In this section, we present Generative Adversarial NAS (GANAS) as a search algorithm to discover top architectures in an extremely large search space. GA-NAS is theoretically inspired by the importance sampling approach and implemented by a generative adversarial learning framework to promote efficiency.

We can view a NAS problem as a combinatorial optimization problem. For example, suppose that x is a Directed Acyclic Graph (DAG) connecting a certain number of operations, each chosen from a predefined operation set. Let S(x) be a real-valued function representing the performance, e.g., accuracy, of x. In NAS, we optimize S(x) subject to x ∈ X, where X denotes the underlying search space of neural architectures.

One approach to solving a combinatorial optimization problem, especially the NP-hard ones, is to view the problem in the framework of importance sampling and rare event simulation [Rubinstein and Kroese, 2013]. In this approach we consider a family of probability densities {p(.; θ)}θ∈Θ on the set X, with the goal of finding a density p(.; θ∗ ) that assigns higher probabilities to optimal solutions to the problem. Then, with high probability, the sampled solution from the density p(.; θ∗ ) will be an optimal solution. This approach for importance sampling is called the Cross-Entropy method.

3.1 Generative Adversarial NAS

GA-NAS is presented in Algorithm 1, where a discriminator D and a generator G are learned over iterations. In each iteration of GA-NAS, the generator G will generate a new set of architectures Xt, which gets combined with previously generated architectures. A set of top performing architectures T , which we also call true set of architectures, is updated by selecting top k from already generated architectures and gets improved over time.

Following the GAN framework, originally proposed by [Goodfellow et al., 2014], the discriminator D and the generator G are trained by playing a two-player minimax game whose corresponding parameters φt and θt are optimized by Step 4 of Algorithm 1. After Step 4, G learns to generate architectures to fit to the distribution of T , the true set of architectures.

Specifically, after Step 4 in the t-th iteration, the generator G(.; θt) parameterized by θt learns to generate architectures from a family of probability densities {p(.; θ)}θ∈Θ such that p(.; θt) will approximate pT , the architecture distribution in true set T , while T also gets improved for the next iteration by reselecting top k from generated architectures.

We have the following theorem which provides a theoretical convergence guarantee for GA-NAS under mild conditions.

Theorem 3.1. Let α > 0 be any real number that indicates the performance target, such that maxx∈X S(x) ≥ α. Define γt as a level parameter in iteration t (t = 0, . . . , T ), such that the following holds for all the architectures xt ∈ Xt generated by the generator G(.; θt) in the t-th iteration:

Choose k, |Xt|, and the γt defined above such that γ0 < α, and

Then, GA-NAS Algorithm can find an architecture x with S(x) ≥ α in a finite number of iterations T .

Proof. Refer to Appendix* for a proof of the theorem.

Remark. This theorem indicates that as long as there exists an architecture in X with performance above α, GA-NAS is guaranteed to find an architecture with S(x) ≥ α in a finite number of iterations. From [Goodfellow et al., 2014], the minimax game of Step 4 of Algorithm 1 is equivalent to minimizing the Jensen-Shannon (JS)-divergence between the distribution pT of the currently top performing architectures T and the distribution p(x; θt) of the newly generated architectures. Therefore, our proof involves replacing the arguments around the Cross-Entropy framework in importance sampling [Rubinstein and Kroese, 2013] with minimizing the JS divergence, as shown in the Appendix.

3.2 Models

We now describe different components in GA-NAS. Although GA-NAS can operate on any search space, here we describe the implementation of the Discriminator and Generator in the context of cell search. We evaluate GA-NAS for both cell search and macro search in experiments. A cell architecture C is a Directed Acyclic Graph (DAG) consisting of multiple nodes and directed edges. Each intermediate node represents an operator, such as convolution or pooling, from a predefined set of operators. Each directed edge represents the information flow between nodes. We assume that a cell has at least one input node and only one output node.

Architecture Generator. Here we generate architectures in the discrete search space of DAGs. Particularly, we generate architectures in an autoregressive fashion, which is a frequent technique in neural architecture generation such as in ENAS. At each time step t, given a partial cell architecture Ct generated by the previous time steps, GA-NAS uses an encoder-decoder architecture to decide what new operation to insert and which previous nodes it should be connected to. The encoder is a multi-layer k-GNN [Morris et al., 2019]. The decoder consists of an MLP that outputs the operator probability distribution and a Gated Recurrent Unit (GRU) that recursively determines the edge connections to previous nodes.

* See https://arxiv.org/abs/2105.09356 for the Appendix.

Pairwise Architecture Discrimator. In Algorithm 1, T contains a limited number of architectures. To facilitate a more efficient use of T , we adopt a relativistic discriminator [Jolicoeur-Martineau, 2018] D that follows a Siamese scheme. D takes in a pair of architectures where one is from T , and determines whether the second one is from the same distribution. The discriminator is implemented by encoding both cells in the pair with a shared k-GNN followed by an MLP classifier with details provided in the Appendix.

3.3 Training Procedure

Generally speaking, in order to solve the minimax problem in Step 4 of Algorithm 1, one can follow the minibatch stochastic gradient descent (SGD) training procedure for training GANs as originally proposed in [Goodfellow et al., 2014]. However, this SGD approach is not applicable to our case, since the architectures (DAGs) generated by G are discrete samples, and their performance signals cannot be directly back-propagated to update θt, the parameters of G. Therefore, to approximate the JS-divergence minimization between the distribution of top k architectures T , i.e., pT , and the generator distribution p(x; θt) in iteration t, we replace Step 4 of Algorithm 1 by alternately training D and G using a procedure outlined in Algorithm 2. Figure 1 illustrates the overall training flow of GA-NAS.

We first train the GNN-based discriminator using pairs of architectures sampled from T and F based on supervised learning. Then, we use Reinforcement Learning (RL) to train G with the reward defined in a similar way as in [You et al., 2018], including a step reward that reflects the validity of an architecture during each step of generation and a final reward that mainly comes from the discriminator prediction D. When the architecture generation terminates, a final reward Rfinal penalizes the generated architecture x according to the total number of violations of validity or rewards it with a score from the discriminator D(x) that indicates how similar it is to the current true set T . Both rewards together ensure that G generates valid cells that are structurally similar to top cells from the previous time step. We adopt Proximal Policy Optimization (PPO), a policy gradient algorithm with generalized advantage estimation to train the policy, which is also used for NAS in [Tan et al., 2019].

Algorithm 2 Training Discriminator D and the Generator G

• 1: Input: Discriminator D; Generator G(x; θt-1); Data set T .
• 2: for t′ = 1, 2, . . . , T ′ do
• 3: Let G(x; θt-1) generate k random architectures to form the set F.
• 4: Train discriminator D with T being positive samples and F being negative samples.
• 5: Using the output of D(x) as the main reward signal, train G(x; θt) with Reinforcement Learning.
• 6: end for

Remark. The proposed learning procedure has several benefits. First, since the generator must sample a discrete architecture x to obtain its discriminator prediction D(x), the entire generator-discriminator pipeline is not end-to-end differentiable and cannot be trained by SGD as in the original GAN. Training G with PPO solves this differentiability issue. Second, in PPO there is an entropy loss term that encourages variations in the generated actions. By tuning the multiplier for the entropy loss, we can control the extent to which we explore a large search space of architectures. Third, using the discriminator outputs as the reward can significantly reduce the number of architecture evaluations compared to a conventional scheme where the fully evaluated network accuracy is used as the reward. Ablation studies in Section 4 verifies this claim. Also refer to the Appendix for a detailed discussion.

4 Experimental Results

We evaluate the performance of GA-NAS as a search algorithm by comparing it with a wide range of existing NAS algorithms in terms of convergence speed and stability on NAS benchmarks. We also show the capability of GA-NAS to improve a given network, including already optimized strong baselines such as EfficientNet and ProxylessNAS.

4.1 Results on NAS Benchmarks with or without Weight Sharing

To evaluate search algorithm and decouple it from the impact of search spaces, we query three NAS benchmarks: NASBench-101 [Ying et al., 2019], NAS-Bench-201 [Dong and Yang, 2020], and NAS-Bench-301 [Siems et al., 2020]. The goal is to discover the highest ranked cell with as few queries as possible. The number of queries to the NAS benchmark is used as a reliable measure for search cost in recent NAS literature [Luo et al., 2020; Siems et al., 2020], because each query to the NAS benchmark corresponds to training and evaluating a candidate architecture from scratch, which constitutes the major bottleneck in the overall cost of NAS. By checking the rank an algorithm can reach in a given number of queries, one can also evaluate the convergence speed of a search algorithm. More queries made to the benchmark would indicate a longer evaluation time or higher search cost in a real-world problem.

To further evaluate our algorithm when the true architecture accuracies are unknown, we train a weight-sharing supernet on NAS-Bench-101 and compare GA-NAS with a range of NAS schemes based on weight sharing. NAS-Bench-101 is the first publicly available benchmark for evaluating NAS algorithms. It consists of 423,624 DAG-style cell-based architectures, each trained and evaluated for 3 times. Metrics for each run include training time and accuracy. Querying NAS-Bench-101 corresponds to evaluating a cell in reality. We provide the results on two setups. In the first setup, we set |X0| = 50, |Xt| = |Xt-1| + 50, t ≥ 1, and k = 25, In the second setup, we set |X0| = 100, |Xt| = |Xt-1|+100, t ≥ 1, and k = 50. For both setups, the initial set X0 is picked to be a random set, and the number of iterations T is 10. We run each setup with 10 random seeds and the search cost for a run is 8 GPU hours on GeForce GTX 1080 Ti.

Table 1 compares GA-NAS to other methods for the best cell that can be found by querying NAS-Bench-101, in terms of the accuracy and the rank of this cell in NAS-Bench-101, along with the number of queries required to find that cell. Table 2 shows the average performance of GA-NAS in the same experiment over multiple random seeds. Note that Table 1 does not list the average performance of other methods except Random Search, since all the other methods in Table 1 only reported their single-run performance on NAS-Bench-101 in their respective experiments.

In both tables, we find that GA-NAS can reach a higher accuracy in fewer number of queries, and beats the best published results, i.e., BANANAS [White et al., 2019] and SemiNAS [Luo et al., 2020] by an obvious margin. Note that 94.22 is the 3rd best cell while 94.23 is the 2nd best cell in NASBench-101. From Table 2, we observe that GA-NAS achieves superior stability and reproducibility: GA-NAS-setup1 consistently finds the 3rd best in 9 runs and the 2nd best in 1 run out of 10 runs; GA-NAS-setup2 finds the 2nd best in 5 runs and the 3rd best in the other 5 runs.

To evaluate GA-NAS when true accuracy is not available, we train a weight-sharing supernet on the search space of NASBench-101 (with details provided in Appendix) and report the true test accuracies of architectures found by GA-NAS. We use the supernet to evaluate the accuracy of a cell on a validation set of 10k instances of CIFAR10 (see Appendix). Search time including supernet training is around 2 GPU days.

We report results of 10 runs in Table 3, in comparison to other weight-sharing NAS schemes reported in [Yu et al., 2019]. We observe that using a supernet degrades the search performance in general as compared to true evaluation, because weight-sharing often cannot provide a completely reliable performance for the candidate architectures. Nevertheless, GA-NAS outperforms other approaches.

NAS-Bench-201

This search space contains 15,625 evaluated cells. Architecture cells consist of 6 searchable edges and 5 candidate operations. We test GA-NAS on NAS-Bench-201 by conducting 20 runs for CIFAR-10, CIFAR-100, and ImageNet-16-120 using the true test accuracy. We compare against the baselines from the original NAS-Bench-201 paper [Dong and Yang, 2020] that are also directly querying the benchmark data. Since no information on the rank achieved and the number of queries is reported for these baselines, we also compare GA-NAS to Random Search (RS-500), which evaluates 500 unique cells in each run. Table 4 presents the results. We observe that GA-NAS outperforms a wide range of baselines, including Evolutionary Algorithm (REA), Reinforcement Learning (REINFORCE), and Bayesian Optimization (BOHB), on the task of finding the most accurate cell with much lower variance. Notably, on ImageNet-16-120, GA-NAS outperforms REA by nearly 1.3% on average.

Compared to RS-500, GA-NAS finds cells that are higher ranked while only exploring less than 3.2% of the search space in each run. It is also worth mentioning that in the 20 runs on all three datasets, GA-NAS can find the best cell in the entire benchmark more than once. Specifically for CIFAR-10, it found the best cell in 9 out of 20 runs.

NAS-Bench-301

This is another recently proposed benchmark based on the same search space as DARTS. Relying on surrogate performance models, NAS-Bench-301 reports the accuracy of 1018 unique cells. We are especially interested in how the number of queries (#Q) needed to find an architecture with high accuracy scales in a large search space. We run GA-NAS on NAS-Bench-301 v0.9. We compare with Random (RS) and Evolutionary (EA) search baselines. Figure 2 plots the average best accuracy along with the accuracy standard deviations versus the number of queries incurred under the three methods. We observe that GA-NAS outperforms RS at all query budgets and outperforms EA when the number of queries exceeds 3k.

The results on NAS-Bench-301 confirm that for GA-NAS, the number of queries (#Q) required to find a good performing cell scales well as the size of the search space increases. For example, on NAS-Bench-101, GA-NAS usually needs around 500 queries to find the 3rd best cell, with an accuracy ≈ 94% among 423k candidates, while on the huge search space of NAS-Bench-301 with up to 1018 candidates, it only needs around 6k queries to find an architecture with accuracy approximately equal to 95%.

In contrast to GA-NAS, EA search is less stable and does not improve much as the number of queries increases over 3000. GA-NAS surpasses EA for #Q ≥ 3000 in Figure 2. What is more important is that the variance of GA-NAS is much lower than the variance of the EA solution over all ranges of #Q. Even though for #Q < 3000, GA-NAS and EA are close in terms of average performance, EA suffers from a huge variance.

Ablation Studies

A key question one might raise about GA-NAS is how much the discriminator contributes to the superior search performance. Therefore, we perform an ablation study on NASBench-101 by creating an RL-NAS algorithm for comparison. RL-NAS removes the discriminator in GA-NAS and directly queries the accuracy of a generated cell from NAS-Bench-101 as the reward for training. We test the performance of RLNAS under two setups that differ in the total number of queries made to NAS-Bench-101. Table 5 reports the results.

Compared to GA-NAS-Setup2, RL-NAS-1 makes 3× more queries to NAS-Bench-101, yet cannot outperform either of the GA-NAS setups. If we instead limits the number of queries as in RL-NAS-2 then the search performance deteriorates significantly. Therefore, we conclude that the discriminator in GA-NAS is crucial for reducing the number of queries, which converts to the number of evaluations in real-world problems, as well as for finding architectures with better performance. Interested readers are referred to Appendix for more ablation studies as well as the Pareto Front search results.

Table 5: Results of ablation study on NAS-Bench-101 by removing the discriminator and directly queries the benchmark for reward.

4.2 Improving Existing Neural Architectures

We now demonstrate that GA-NAS can improve existing neural architectures, including ResNet and Inception cells in NAS-Bench-101, EfficientNet-B0 under hard constraints, and ProxylessNAS-GPU [Cai et al., 2018] in unconstrained search.

For ResNet and Inception cells, we use GA-NAS to find better cells fromNAS-Bench-101 under a lower or equal training time and number of weights. This can be achieved by enforcing a hard constraint in choosing the truth set T in each iteration. Table 6 shows that GA-NAS can find new, dominating cells for both cells, showing that it can enforce ad-hoc constraints in search, a property not enforceable by regularizers in prior work. We also test Random Search under a similar number of queries to the benchmark under the same constraints, which is unable to outperform GA-NAS.

We now consider well-known architectures found on ImageNet i.e., EfficientNet-B0 and ProxylessNAS-GPU, which are already optimized strong baselines found by other NAS methods. We show that GA-NAS can be used to improve a given architecture in practice by searching in its original search space.

For EfficientNet-B0, we set the constraint that the found networks all have an equal or lower number of parameters than EfficientNet-B0. For the ProxylessNAS-GPU model, we simply put it in the starting truth set and run an unconstrained search to further improve its top-1 validation accuracy. More details are provided in the Appendix. Table 7 presents the improvements made by GA-NAS over both existing models. Compared to EfficientNet-B0, GA-NAS can find new single-path networks that achieve comparable or better top1 accuracy on ImageNet with an equal or lower number of trainable weights. We report the accuracy of EfficientNet-B0 and the GA-NAS variants without data augmentation. Total search time including supernet training is around 680 GPU hours on Tesla V100 GPUs. It is worth noting that the original EfficientNet-B0 is found using the MNasNet [Tan et al., 2019] with a search cost over 40,000 GPU hours.

For ProxylessNAS experiments, we train a supernet on ImageNet and conduct an unconstrained search using GANAS for 38 hours on 8 Tesla V100 GPUs, a major portion of which, i.e., 29 hours is spent on querying the supernet for architecture performance. Compared to ProxylessNAS-GPU, GA-NAS can find an architecture with a comparable number of parameters and a better top-1 accuracy.

5 Conclusion

In this paper, we propose Generative Adversarial NAS (GANAS), a provably converging search strategy for NAS problems, based on generative adversarial learning and the importance sampling framework. Based on extensive search experiments performed on NAS-Bench-101, 201, and 301 benchmarks, we demonstrate the superiority of GA-NAS as compared to a wide range of existing NAS methods, in terms of the best architectures discovered, convergence speed, scalability to a large search space, and more importantly, the stability and insensitivity to random seeds. We also show the capability of GA-NAS to improve a given practical architecture, including already optimized ones either manually designed or found by other NAS methods, and its ability to search under ad-hoc constraints. GA-NAS improves EfficientNet-B0 by generating architectures with higher accuracy or lower numbers of parameters, and improves ProxylessNAS-GPU with enhanced accuracies. These results demonstrate the competence of GANAS as a stable and reproducible search algorithm for NAS.