Generative Adversarial Neural Architecture Search with Importance Sampling
Authors: SEYED SAEED CHANGIZ REZAEI
Fred X. Han
Di Niu
Mohammad Salameh
Keith G. Mills
Shangling Jui
Venue:  (2021)
Keywords: Nueral Architecture Search
Deep Learning
Generative Adversarial Network
Graph Neural Network
Computer Vision

Abstract: Despite the empirical success of neural architecture search (NAS) in deep learning applications, the optimality, reproducibility and cost of NAS schemes remain hard to assess. The variation in search spaces adopted has further affected a fair comparison between search strategies. In this paper, we focus on search strategies in NAS and propose Generative Adversarial NAS (GA-NAS), promoting stable and reproducible neural architecture search. GA-NAS is theoretically inspired by importance sampling for rare event simulation, and iteratively refits a generator to previously discovered top architectures, thus increasingly focusing on important parts of the search space. We propose an efficient adversarial learning approach in GA-NAS, where the generator is not trained based on a large number of observations on architecture performance, but based on the relative prediction made by a discriminator, thus significantly reducing the number of evaluations required.
Extensive experiments show that GA-NAS beats the best published results under several cases on the public NAS benchmarks including NAS-Bench-101, NAS-Bench-201, and NAS-Bench-301. We further show that GA-NAS can handle ad-hoc search constraints and search spaces. GA-NAS can find new architectures that enhance EfficientNet and ProxylessNAS in  terms of ImageNet Top-1 accuracy and/or the number of parameters by searching in their original search spaces.

Under review as a conference paper at ICLR 2021
GENERATIVE ADVERSARIAL NEURAL ARCHITECTURE SEARCH WITH IMPORTANCE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the empirical success of neural architecture search (NAS) in deep learning applications, the optimality, reproducibility and cost of NAS schemes remain hard to assess. The variation in search spaces adopted has further affected fair compar- ison between search strategies. this paper, we focus on search strategies NAS and propose Generative Adversarial NAS (GA-NAS), promoting stable and repro- ducible neural architecture search. GA-NAS is thcorctically inspired by importance sampling for rare event simulation, and iteratively refits generator to previously discovered top architectures, thus increasingly focusing on important parts of the search space. We propose an efficient adversarial learning approach in GA-NAS, where the generator is not trained based on a large number of observations on architecture performance, but based on the relative prediction made by discrimi- nator, thus significantly reducing the number of evaluations required. Extensive experiments show that GA-NAS beats the best published results under several cases on the public NAS benchmarks including NAS Be--B-nnchh-- 101, NAS-Bench and WASS-eench331. We further show that GA-NAS can handle ad-hoc search constraints and search spaces. GA-NAS can find new architectures that enhance EfficientNet and ProxylesSNAS terms of ImageNet Top-1 accuracy and/or the number of parameters by scarching in their original scarch spaces.
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-of-the-ar performance on many computer vision tasks (Elsken et al., 2018). Since the underlying search space of architectures grows exponentially as function of the architecture size, searching for an optimum neural architccture is like looking for needle in haystack. A variety of search strategies have been proposed for NAS. Typical search strategies include random search (Li & Talwalkar, 2020), differentiable architecture search and optimization (e.g., DARTS (Liu et al., 2018), SNAS (Xie et al., 2018), Bayesian optimization (e.g., NASBOT (Kandasamy et al., 2018)), and reinforcement learning (e.g..
ENAS (Pham et al.. 2018) NASNet (Zoph al., 2018)).
In spite of a proliferation of NAS strategies proposed. issues on the robustness and reproducibility of existing NAS methods are raised by Li & Talwalkar (2020), Yu al. (2019), and Yang al. (2019). Comparisons between different methods are hard, as there is no shared search space or experimental protocol followed by all (Yu al., 2019; Yang et al., 2019). To promote reproducibility and fair comparisons among methods, multiple NAS benchmarks have recently emerged, including NAS-Bench-100 101 (Ying et al., 2019), NAS-Bench-201 (Dong & Yang. 2020), and PAS-Bench-301 (Siems et al., 2020), which are datasets that map architectures to their evaluation metries. This provides an opportunity for researchers to fairly benchmark different search algorithms in terms of searching for the highest-ranked architectures within the least number of queries to architecture performance, the latter being a good indicator of the search cost. However, Yu et al. (2019) has evaluated several well-known search algorithms, including DARTS (Liu et al., 2018), ENAS (Pham et al., 2018) and NAO (Luo et al., 2018) on NAS-Bench- 101, and has concluded that these search random policy (Yu et al., 2019).
algorithms perform similarly
In this paper, we revisit the NAS problem with importance sampling, a robust method for rare event discovery with theoretical guarantees (Rubinstein & Kroese, 2016; 2013). Our method stems from the

---

Under review as a conference paper at ICLR 2021
Cross Entropy (CE) method (Rubinstein & Kroese, 2013), which iteratively retrains architecture generator to mimic the winning architectures generated in previous iterations so that the generator will increasingly focus on more important regions of the large search space. However, as the generator obtains performance measurements only after architectures, which are discretized graphs, are sampled and evaluated, the performance signal cannot be backpropagated train the generator directly with SGD. Another challenge is the large search space an algorithm, e.g., reinforcement learning (RL), must explore before it can learn a policy to generate better performing architectures, which leads to high search cost.
To solve these challenges, we propose Generative Adversarial NAS (GA-NAS), an efficient and robust search algorithm for NAS. GA-NAS uses RL to train an architecture generator network based on RNN and GNN, avoiding the end-to-end differentiability issue. In contrast to other RI.-based NAS schemes, GA-NAS does not obtain rewards from the performance metrics of the generated architectures, a costly procedure if a large number of architectures are explored. Instead, it iteratively updates discriminator that can distinguish the currently top architectures from randomly generated ones, and uses the relative prediction from the discriminator to train the generator to sample even better architectures in the next round. This enables the generator to be efficiently trained without many queries to true architecture performance. We point out the theoretical connection between GA-NAS and a CE method with symmetric Jensen-Shannon (JS) divergence loss, for which we establish the convergence guarantee.
Results from extensive search experiments show that GA-NAS outperforms state-of-the-arr results reported the public benchmark sets on NAS-Bench-101 that it consistently finds lop ranked architectures fewer number of queries. We also demonstrate the ability of GA-NAS to incorporate hard ad- hoc constraints and can be used to improve existing models. Through experiments on ImageNet, we show that GA-NAS can enhance EfficientNet-Bi (Tan & Le, 2019) and ProxylessNAS (Cai et al., 201 8) in their respective original search spaces, resulting in architectures with higher accuracy and/or smaller models.
and
in
RELATED WORK
typical NAS method consists of the search phase and the evaluation phase (Yu et al., 2019). This paper is concerned with the search phase, of which the most important performance criteria are robustness, reproducibility (Li & Talwalkar, 2020) and search cost (Yu et al., 2019).
DARTS (Liu et al., 2018) has given rise to numerous optimization schemes for NAS (Xic et al., 2018; Chen et al., 2019; Xu et al., 2020; Chen & Hsich, 2020; Li ct al., 2020). 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 search results heavily dependent the initial random seed. Furthermore, DARTS is criticized for converging to architectures with smooth loss landscapes which may not generalize well (Shu et al., 2019; Chen & Hsich, 2020). In contrast, GA-NAS aims to train an architecture generator using the GAN framework while using importance sampling to gradually shift toward more important parts of the search space. GA-NAS has a convergence guarantee under certain assumptions. Its results are reproducible and are not sensitive to initial seeds.
MAS-Bench-301 (Siems et al., 2020) provides a formal benchmark for all 1 architectures in the DARTS search space using surrogate trained on subset of 50k architectures. Preceding NAS-Bench- 301 are MAS--Bnnch-101 (Ying et al., 2019) and MASS-Bench-201 (Dong & Yang, 2020). Both of these benchmarks provide performance metrics in tabular format and perform a fully exhaustive evaluation across all architectures in their search spaces, which contain 423k and 15k architectures. respectively. GA-NAS can find high-performing architectures in all three benchmarks and proves to be a highly robust algorithm that is not sensitive to search spaces.
search strategy, also applies to macro- macro- (Cai et al., 2018; Wu et al., 2019; Tan et al., 2019), which searches for an ordering of predefined set of blocks. We show that GA-NAS can be used to improve EfficientNer (Tan & Le, 2019) by iteratively generating better ordering of the same set of MBCony blocks adopted in original EfficientNet.
Besides the cell-based scarch spaces (Pham et al., 2018: Liu et al., 2018), GA-NAS,
2

---

Under review as a conference paper at ICLR 2021
On the other hand, number of 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. AlphaX (Wang et al., 2020) uses Monte Carlo Tree Search to balance exploration with exploitation during search. Unlike these approaches, GA-NAS proves to be highly efficient RL solution to NAS, since the rewards used to train the generator network comes from the relative performance prediction of the discriminator instead of from architecture evaluation. Our ablation studies show that the use of a discriminator can lower the number of architecture evaluations tremendously, which is typically a bottleneck in any NAS method.
Hardware-friendie NAS algorithms may take constraints such as model size, FLOPS, and inference time into account (Cai et al., 2018; Tan et al., 2019; Wu et al., 2019; Chen al., 2020; Yu et al., 2020), usually by introducing regularizers into the loss functions (Wu et al., 2019; Cai et al., 2018) Contrary to these methods, GA-NAS can support ad-hoc search tasks, by enforcing customized hard constraints in importance sampling instead of resorting approximate penalty terms.
THE PROPOSED METHOD
We describe importance sampling for rare event simulation, followed by a description of a particular implementation of it on NAS, which is the proposed GA-NAS method.
3.1 IMPORTANCE SAMPLING
We can view NAS as a combinatorial optimization problem. For example, suppose that x is a Directed Acyelic Graph (DAG) connecting certain number of operations, each chosen from a predefined operation set. Let S(x) be real-valued function representing the performance, e.g., accuracy, of In NAS, we aim to optimize S(z) subject to x E X, where X denotes the underlying large 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 (De Boer et al., 2005; Rubinstein & Kroese, 2013). In this approach we consider a family of probability densities {p(:; reee the set X, with the goal of finding density p(.; 07)) that assigns higher probabilities to the optimal solutions to the problem.
Assume X is random variable, taking values in X' and has prior probability density function (pdf) p(:; X) for fixed E O. Let S(X) be the objective function to be maximized, and a be a level parameter. Note that the event & := (S(X)= a} is a rare event for an that is equal to close the optimal value of S(X). The goal of rare-event probability estimation is to estimate
1= [[a = (S(X) 2 a) = E, [Us(x]aa] - f Is(w)za p(a; d)dr,
where Ieeg is an indicator function that is equal to I if E & and 0 otherwise.
In fact, I is called the rare-event probability (or expectation) which is very small, e.g., less than 10-1 (Botev et al., 2013). The general idea of importance sampling is to estimate the above rare-event probability by drawing samples from important regions of the search space with both large density p(z; X) and a large Is(a) ie., Is(=)aa = 1. In other words, we aim to find x such that S(x) 2 a with high probability.
Importance sampling estimates 1 by sampling from distribution (x X) that should be proportional to [lsz))aP((;; X) (see (Murphy, 2012) page 820). Specifically, define the proposal sampling density (2)) as a function such that q(x) = 0 implies [5(=)2aP(1; X) = for every x (see (Botev et al., 2013) page 2). Then we have
(())de= = E, ((())2o((X -= g(z)
[s(e)2a((<; A) ((1)
1 1=
(1)
x(X)
Rubinstein & Kroese (2016) shows that the optimal importance sampling probability density g which minimizes the variance of the empirical estimator of is the density of X conditional on the event
3

---

Under review as a conference paper at ICLR 2021
Algorithm IS-divereence minimization for rare-event estimation
1: L + 1, po + P. 00 + X
2: while 1 < do
3: 0g E arg mingee J [S( 7-11 {)1lp(z;0)) ()), where 7- = min(a, ((0)-1, and
q(2, ((s,n-1::)
[1ls(w)27)- p(a; X)dx
4: Set P such that 7(t,, 2 min(a, 7(0, Pt Pt- + 6) for some fix O, and increment t.
S(X) 2 a, that is
p(a; A)llst)2aa
o (x,,,;;)) J [s(=)2a p(æ; X)dz
However, noting that the denominator of (2) is the quantity I that aim estimate in the first place, we cannot obtain an explicit form of (-) directly. To overcome this issue, Homem-de Mello & Rubinstein (2002) proposes the Cross-Entropy (CE) method estimate q²(() by generating a sequence of probability densities p(:; 01), p(.; 02) that approaches q" (.) in terms of KL divergence (Homem-de Mello & Rubinstein, 2002), with details included in the Appendix.
Furthermore, motivated by the well-known fact that the symmetric Jensen- Shannon (JS) divergence is more robust than the asymmetric KL divergence (Nowozin et al., 2016), we replace the KL divergence with the IS divergence in our application of importance sampling (see the Appendix). Denote the threshold sequence by "(t, 2 O, and sampling distribution parameters by 6.,
O. Initially, choose and 7(x, p) so that (X, p) is the (1 (1-po -)-uantllle of S(X) under p(-; X), and generally, let ((,,, Pt) be the (1 - -quuntilee S(X) under the the sampling density p(1; 0,) iteration t.
We have the following JS JS-divergence minimization rare-event estimation algorithm to generate a solution x such that S(x) 2 a with high probability (with theoretical convergence guarantee presented in the Appendix):
In each iteration, we 0g to minimize the JS divergence between the sampling density p(æ; 0,) and q 7/-1; A), the density of X conditioned on that S(X) 7h-1. Since "/-1 is typically the (1 - (r-1)-quantill of S(X) under the previous sampling density p(:; ft-1), we are essentially fitting 9, to the top candidates that had highest S(x) in the previous iteration. Once the final sampling density is obtained, we can use that to generate a solution x such that (zz) 2 a with high probability.
3.2 GENERATIVE ADVERSARIAL NEURAL ARCHITECTURE SEARCH
We now propose generative adversarial training method named Generative Adversarial NAS (GA- NAS), described Algorithm replace the JS- diveiveree minimization (Step 3) Algorithm 1, which is otherwise hard to implement. The GAN framework, as originally proposed by Goodfellow between true and generated data and
et al. (2014), alternates between training a discriminator training generator G to minimize the probability that the discriminator distinguishes generated data from truth data. In other words, adversarial lcarning. D and G play a two-player minimax game, which Ieads to the minimization of the JS divvereggenee between the distribution of truth data and that of the generator model (see Theorem in (Goodfellow et al., 2014)). GA-NAS in Algorithm alternates
Algorithm 2 GA-NAS Algorithm
1: Input: An initial set of architectures Xo; Discriminator D; Generator G(z; 0o);
2: for = 1, , do
3:
T T+ top K architectures of U X, according to the performance evaluator S(.). Let G(z; 6,-1) generate l random architectures to form the set F.
4:
5:
Train discriminator D with T being positive samples and F being negative samples.
6:
Train generator G(æ; 0,) using the output of D(x) the loss.
7:
Let G(æ; 0.) generate a new set architectures Xt. Evaluate the performance S(x) of every & E Xt.
8:
4

---

Under review as a conference paper at ICLR 2021
between training D (Step 5) and G (Step 6) to approximate the JS divereegeece minimization between the distribution of top K architectures T in iteration and the generator distribution G(x; ft). If G(r;; 0t) corresponds to p(a;; lt), and the distribution of architectures in T, i.e., the distribution of top architectures in prior iteration, corresponds to q( 7t-1) 1) in Algorithm 1, GA-NAS algorithm is essentially an implementation of the JS-divergence rare-event estimation. It replaces the JS minimization (Step 3) in Algorithm 1 by alternately learning D and G, and instead of keeping track Ft. using the top architectures as positive samples in each itcration. Roughly speaking, and ,/: is chosen so that the (1 - -quantile is %/e-
of P: and
Pa | x!I"
GA-NAS can operate on any search space. Here, we describe the implementation of the discriminator and generator in the context of cell search, whereas we evaluate GA-NAS on both cell search and macro search experiments. A cell architecture is a Directed Acyclic Graph (DAG) consisting of multiple nodes and directed edges. Each intermediate node represents an operator, such convolution or pooling, from 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.
Pairwise Architecture Discriminator. In the context of NAS, we often have a limited number of architectures with true accuracies. To efficiently use the truth data points, we construct the discriminator D following pairwise Siamese (Koch et al., 2015) scheme. For a pair of architectures, the discriminator D determines the likelihood that the second architecture is from the same distribution as the first truth architecture. Thus, D is variant of the relativistic discriminator 2018). The discriminator implemented by encoding both cells in the pair with shared k-GNN model (Morris et al., 2019) followed by an MLP classifier with details provided in the Appendix.
Dolicoeur-Martinens
Architecture Generator. An architecture is generated in an autoregressive fashion, which is a frequent technique in neural architecture generation such as in ENAS (Pham et al., 2018), NAO (Luo et al., 2018) and D-VAE (Zhang et al., 2019). At cach time step t, given a partial cell architecture C, generated by the previous time steps, GA-NAS uses encoder-decoder architecture to decide what new operation to insert and which previous nodes it should be connected to. Similarly, the encoder is multi-layer k-GNN. The decoder consists of a Sendfoowwrd-Softnaan setup that outputs the operator probability distribution and a uni-directional Gated Recurrent Unit (GRU) (Chung et al., 2014) that recursively determines the edge connections previous nodes.
Training Procedure. We train the GNN-based discriminator using pairs of architectures sampled from T and F based on supervised learning. We use Reinforcement Learning (RL) to train the architecture generator G in similar way to (You et al., 2018) for molecular generation. We associate the action at each time step (including the operation type and its connections previous nodes) with an immediate reward Rstep based on its validity given the search space constraints. When the architecture generation terminates, a final reward Ryimal penalizes the generated architecture according to the total number of violations of validity rewards it with score from the discriminator D(x) that indicates how similar it is to the truth architectures. 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) (Schulman et al., 2017), a policy gradicnt algorithm with generalized advantage estimation to train the policy.
The proposed learning procedure has several benefits. First, using the discriminator as a feedback mechanism can significantly reduce the number of architecture evaluations that are otherwise required in an RL-only scheme. Ablation studies demonstrate the effectiveness of the proposed discriminator in reducing the number of evaluations. Second, since the generator must sample discrete architecture x to obtain its loss on the discriminator (zx). the entire generator-diseriminee -isscrimintoorr pipeline is not end-to- end differentiable and cannot be trained by SGD. Training G with PPO solves this non-iifferentiability issue. Third, in PPO loss, there is an entropy loss term that encourages variations in the generated actions. By tuning the multiplier for the entropy loss, we can balance exploration/exploitttioo, which is crucial for large search space. Please refer to the Appendix for detailed discussion.
4 EXPERIMENTAL RESULTS
We verify the effectiveness of GA-NAS in scenarios. First, we conduct experiments on several public NAS benchmarks under both non-weight-sharing and weight-sharing settings in order to fairly compare the powers of the search algorithms. Second, we demonstrate the use of GA-NAS to
5

---

Under review as a conference paper at ICLR 2021
improve given neural architecture, including EfficientNet and ProxylessNAS, to achieve higher accuracy and/or a lower number of parameters. We also refer interested readers to the Appendix for the ablation studies showing the effects of different components of GA-NAS its performance.
4.1 PERFORMANCE ON NAS BENCHMARKS WITH OR WITHOUT WEIGHT SHARING
To evaluate search strategy alone and decouple it from vari- ations of search spaces, query three NAS benchmarks: NAS-Bench-IDe 101 (Ying et al., 2019), NAS-Bench-200 (Dong & Yang, 2020), and HAS-Benchh331 (Siems et al., 2020) and aim to find the best performing cell within the least number of queries. To further evaluate our algorithm when the true ar- chitecture accuracies are unknown, we train a weight-sharing 101 and compare GA-NAS with range of NAS schemes based on weight sharing.
Algorithm
Acc (%)
#Q
Random Search
93.66
2000
RE
93.97
2000
NAO
93.87
2000
BANANAS
94.23
800
SemiNAS
94.09
2100
supernet on
SemiNAS
93.98
300
GA-NAS-sctupl
94.22
150
GA-NAS-setup2
94.23
378
NAS-Bench-101 the first publicly available benchmark for evaluating NAS algorithms. It consists of 423,624 DAG- style cell-based architectures, each trained and evaluated on CIFAR-10 (Krizhevsky, 2009) for times. Metrics for each rum include training time and accuracy. Querying NAS- Bench-101 corresponds to evaluating cell in reality. We provide the results on two setups. In the first setup, we set | 50, | [ 1 50, > 1, and K 25, In the second setup, we set Xn = 100, & = X2
Table 1: The best accuracies found by different search algorithms on NAS- Bench-101 without weight sharing. Note that 94.23% and 94.22% are the accuracies of the 2nd and 3rd best cells. f: taken from (Luo et al., 2020)
100, t 2 1, and K = 50. For both setups, the initial set Xo is picked be random set, and the number of iterations 7 10. We run each setup with 10 random seeds and average the results. The search cost is 8 GPU hours.
Algorithm
Mean Acc (%)
Mean Rank
Average #Q
Random Search
93.84 0.13
498.80
648
Random Search
93.92 + 0.11
211.50
1562
GA-NAS
94.22 + 4.45e-5
2.90
647.50 +: 433.43
GA-NAS-Setupp
94.23 7.43e-5
2.50
1561.80
802.
Table 2: The average statistics of the best cells found on NAS-Bench-10 without weight sharing, averaged over runs (with std shown). Note that we set the number queries (Q) for Random Search to be the same the average number of queries incurred by GA-NAS.
Table 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 TAS-Bench-101 along with the number of queries required to find that cell. Table 2 shows the average performance of GA-NAS in the experiment performance of other methods except Random Search, since all the other methods in Table 1 only reported their single-run performance on JAS--ennh--oe in their respective experiments.
multiple random seeds. Note that Table does not list the average
In both tables, we find that GA-NAS can reach higher accuracy in fewer number of queries, and beats the best published re- sults, i... BANANAS (White al., 2019) and SemiNAS (Luo et al., 2020) by an obvi- ous margin. Note that 94.22 is the 3rd best cell while 94.23 is the 2nd best cell in NAS- Bench-101. From Table 2, we observe that GA-NAS achieves superior stability and re- producibility: GGA-NAS-stupp consistently finds the 3rd best in 9 runs and the 2nd best in finds the 2nd best in 5 runs and the 3rd best in the other runs.
Algorithm
Mean Acc
Best Acc
Best Rank
DARTS
92.21 +: 0.61
93.02
57079
NAO
92.59 + 0.59
93.33
19552
ENAS i
91.83 + 0.42
92.54
96939
GA-NAS
92.80 = 0.54
93,46
5386
Table 3: Searching on NAS-Bench- 101 with weight- sharing, with the mean true test accuracy of the best cells from 10 runs, and the best accuracy/rank found by a single run. t: taken from (Yu et al., 2019)
1 run out of 10 runs; GA--NAS-ettln
To evaluate GA-NAS when true accuracy is not available, we train a weight-sharing supernet on the search space of NAS-Bench-101 (with details provided in Appendix) and report the true test.

---

Under review as a conference paper at ICLR 2021
R-FA
CIFAR-100 100
ImageNet-16-120
Algorithm
Mean Acc
Rank
#Q
Mean Acc
Rank #Q
Mean Acc
Rank
#Q
REA
93.92 + 0.30
71.84 = 0.99
45.54 = 1.03
RS
93.70 + 0.36
71.04 = 1.07
44.57 = 1.25
REINFORCE
93.85 0.37
71.71 = 1.09
45.24 = 1.18
BOHB
93.61 0.52
70.85 = 1.28
44.42 = 1.49
RS-500
94.11 0.16
30.81
500
72.54 = 0.54
30.89
500
46.34 = 0.41
34.18
500
GA-NAS
94.34 + 0.05
4.05
444
73.28 = 0.17
3.25
444
46.80 = 0.29
7.40
445
i The results are taken directly from NAS- M0S-Bench-220 (Dong & Yang, 2020).
Table Searching on NAS-Bench-201 without weight sharing, with the mean accuracy and rank of the best cell found reported. #Q represents the average number of queries per run. We conduct 20 runs for GA-NAS.
accuracies of architectures found by GA-NAS. We use the supernet to evaluate the accuracy cell on validation set of 10k instances of CIFARIO (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 completely reliable performance for the candidate architectures. Nevertheless, GA-NAS outperforms other approaches.
NAS-Bench-20 contains 15,625 evaluated cells with DARTS- like (Liu et al., 2018) structures. The search space consists of 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-166 16-120 using the true test accuracy. We compare against the baselines from the original NAS-Bench-201 paper (Dong & 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 all basclines on the task of finding the most accurate cell. Compared to RS-500, GA-NAS finds cells that are higher ranked while only exploring less than 3.2% of the entire search space in each run (querying only 445 out of 15,625 cells). It is also worth mentioning that the 20 runs on all three datasets, GA-NAS can find the best cell the entire search space more than once. Specifically for CIFAR-10, it found the best cell in 9 out of 20 runs
95.3
NAS-Bench-300 (Siems et al., 2020) is another recently proposed benchmark based on the same search space DARTS. Relying surrogate performance models, NAS-Bench-301 reports the accuracy of 1018 unique cells. We are espe-
95.2
95
VALIDATION ACC
cially 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 MAS--ench-3301 v0.9. We com- pare with Random (RS) and Evolutionary (EA) search baselines. Figure plots the average best accuracy along with the accuracy standard de- viations 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 ex- ceeds 3k. The results on NAS-Bench-301 con- firm that for GA-NAS, the number of queries
04.8
94.7
94.5
94.4
-d-EA
GA-NAS
0
2000
4000
6000
8000
10000
NQ. TOTAL
Figure 1: NAS-Bench-301 results comparing the means/standard deviations of the highest accuracy found at different total query limits.
(#Q) required to find a good performing cell scales well as the size of the search space increases. For example, on NAS-Bench-100 GA-NAS usually needs around 500 queries to find the 3rd best cell, with an accuracy x 94% among 423k candidates, while on the huge search space of NAS- MAS--Bench-30) with up 10 candidates, only needs around 6k queries to find an architecture with accuracy approximately equal to 95%.
TThere are two cells in NAS-Bench-201 with the same, highest CIFAR-10 test accuracy of 94.37. We record that GA-NAS finds the best cell if either one found.
7

---

Under review as a conference paper at ICLR 2021
ResNet Train Seconds
Inception Train Seconds
Algorithm
Best Ace
#Weights (M)
Best Acc
#Weights (M)
Hand-crafted
93.18
2251.6
20.35
93.09
1156.0
2.69
Random Search
93.84
1836.0
10.62
93.14
1080.4
2.18
GA-NAS
93.96
1993.6
11.06
93.28
1085.0
2.69
Table 5: Constrained search results NAS-Bench-101. GA-NAS find cells that superior the ResNet and Inception cells in terms of test accuracy, training time, and the number of weights.
4.2 IMPROVING EXISTING NEURAL ARCHITECTURES
We now demonstrate that GA-NAS can improve existing neural architectures, including ResNet (He et al., 2016) and Inception (Szegedy et al., 2016) cells in NAS-Bench- 101, Efficien(Net-BO (Tan & Lc, 2019) under hard constraints, and ProxylesSNAS-GPU (Cai et al., 2018) in unconstrained search.
For ResNet and Inception cells, we use GA-NAS find better cells from NAS-Bench-101 under a lower or equal training time and number of weights. This can achieved by enforcing a hard constraint in choosing the truth set T in each iteration. Table 5 shows that GA-NAS can find new, dominating cells for both cells, showing that it can enforce ad-hoc constraints in search, a property enforceable by regularizers in prior work. We also test Random Search under similar number of queries to the benchmark under the same constraints, which is unable to outperform GA-NAS.
We GA-NAS improve the accuracy of well-known architectures found on ImageNet (Russakovsky et al., 2015), including Net-cie and ProxylesNNA--GP, which are already optimized strong baselines. For ElficientNet BO, we the constraint that the found networks all have an equal or lower number of trainable weights than EfficientNet-BB model, we simply put in the starting truth and run an unconstrained search to further improve its top-1 validation accuracy. More details are provided in the Appendix. Table 6 presents the improvements made by GA-NAS over both existing models. Compared to EllicientNet-B00 GA-NAS can find new single-path networks that achieve comparable better top-1 accuracy ImageNet with an equal or lower number of trainable weights. We report the accuracy of EfficientNet- and the GA-NAS variants without data augmentation. Total search time including supernet training is around 21 GPU days on Tesla V100 GPUs (20 GPU days for supernet training and GPU day for the search). For ProxylessNAS experiments, supernet on ImageNet (Russakovsky et al., 2015) for around 20 GPU days, and conduct an unconstrained search using GA-NAS for around 38 hours on 8 Tesla V100 GPUs in the search space of ProxylessNAS (Cai al., 2018), a major porition 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 better top-1 accuracy ImageNet.
For the ProxylesNNAS-GHE
train
Network
#Params
Top-1 Acc
ElficientNet-BO (no augment)
5.3M
76.7
GA-NAS-ENet-1
4.6M
76.5
GA-NAS-ENet-2 GA-NAS-ENet-3
5.2M
76.8
5.3M
76.9
ProXylesSNAS-GUU
4.4M
75.
GA-NAS--PrxyyesNNASS
4.9M
75.5
Table 6: Search results on the EfficientNet search space and ProxylessNAS search space.
CONCLUSION
In this paper, propose Generative Adversarial NAS (GA-NAS), search strategy for NAS problems, based on generative adversarial learning framework and importance sampling. Based extensive search experiments performed NAS-Bench- 101, 201, and 301 benchmarks, demonstrate the superiority of GA-NAS in finding more accurate architectures with much fewer queries which convert evaluations in reality, as compared range of well-known NAS methods. We also show the capability of GA-NAS to improve existing architectures and its ability to search under ad-hoc hard constraints. GA-NAS improves EfficientNet-Bo by generating architectures in the same search space with higher accuracy and/or lower number of parameters and improves ProxylesNNAS- GPU with enhanced accuracies and slightly increased model size. These results indicate that GA-NAS generalizes well to diverse types of search spaces and can improve already optimized and scale image classification lasks.
neural architectures in their respective search spaces for large-
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Arjovsky and Léon Bottou. Towards principled methods for training generative adversarial networks. arXiv preprint arXiv: 1701. 040622 2017.
Gabriel Bender, Hanxiao Liu, Bo Chen. Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoc V Le. Can weight sharing outperform random architecture search? an investigation with tunas. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14323-14332, 2020.
Zdravko I Botev, Dirk P Kroese, Reuven Y Rubinstein, and Pierre L'Ecuyer. The cross-entropy method for optimization. In Handbook of statistics, volume 31, pp. 35-59. Elsevier, 2013.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXiv:/812.00333 2018.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. arXiv preprint arXiv:2002.05288 2020.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings the IEEE International Conference on Computer Vision, pp. 1294-1303, 2019.
Zewei Chen, Fengwei Zhou, George Trimponias, and Zhenguo Li. Multi-objective neural architecture search via non-stationary policy gradient. arXiv preprint arXiv:2001.000 08437,, 2020.
Junyoung Chung, Caglar Gulcchre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67, 2005.
Xuanyi Dong and Yang. Nas-bench-22 Extending the scope reproducible neural architecture search. In International Conference on Learning Representations, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, arXiv preprint arXiv: wwt.:0008800.80008 2018.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Ian Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprint
mrXivv1701.00100 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pp. 2672-2680, 2014.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Tito Homem-de Mello and Reuven Y Rubinstein. Rare event estimation for static models via cross-entropy and importance sampling. 2002.
Alexia Jolicoeur-Martinenee The relativistic discriminator: a key element missing from standard gan. arXiv preprint arXiv: 2018.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. In Advances in neural information processing systems, pp. 2016 6 6-2025, 2018.
Yuri M Kaniovski, Alan J King, and Roger JB Wets. Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems. Annals of Operations Research, 56(1):189-208, 1995.

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In /CML deep learning workshop, volume 2. Lille, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, pp. 367-377. PMLR, 2020.
Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient
algorithms for neural architecture search. arXiv preprint arXiv:2004.0777 007800 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search, arXiv preprint arXiv:1806.0900 2018.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Yan Liu. Neural architecture optimization. In Advances neural information processing systems, pp. 7816-7827, 2018.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu. Semi-supervised neural architecture search. arXiv preprint arXiv:2002.1038) 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Kevin P Murphy. Machine learning: a probabilistic perspective. MIT press, 2012.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan:
Training generative neural samplers using variational divergence minimization. Advances in neural information processing systems, pp. 271-279, 2016.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint arXiv: (0v::8000 1802.03288, 2018
Reuven Y Rubinstein and Dirk Kroese. The cross entsopy method: unified approach to combina- torial optimization, Monte-Carlo simulation and machine learning. Springer Science & Business Media, 2013.
Reuven Y Rubinstein and Dirk Kroese. Simulation and the Monte Carlo method, volume 10. John Wiley & Sons, 2016.
Reuven Y Rubinstein and Alexander Shapiro. Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method. John Wiley & Sons Inc, 1993.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255 2015.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 17Xiv:1707.06337,, 2017.
Alexander Shapiro and Tito Homem-de Mello. On the rate of convergence of optimal solutions of monte carlo approximations of stochastic programs. SIAM journal on optimization, 11(1):70-86. 2000.
10

---

Under review as a conference paper at ICLR 2021
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyúski. Lectures stochastic program- ming: modeling and theory. SIAM, 2014.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference Learning Representations, 2019.
Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008.099 097777 2020.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826. 2016.
Mingxing Tan and Quoc V Lc. Efficientnct: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv: 1946, 2019.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1820-2828. 2019.
Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. Neural architecture search using deep neural networks and monte carlo tree search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 9983-9991, 2020.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. arXiv preprint arXiv: 18858, 2019.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 10734-10742, 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arviv: 18/2.09926, 2018
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-efficient architecture search. In International Conference on Learning Representations, 2020.
Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. arXiv preprint arxiv: 1912. 12522, 2019.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-101. 101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pp. 7105-7114, 2019.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in neural information processing systems, pp. 6410-6421, 2018.
Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Picter-Jan Kindermans. Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le. Bignas: Scaling up neural architec- ture search with big single-stage models. arXiv preprint arXiv:2003. /1 2020.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the scarch phase of neural architccture scarch. 2019.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: A variational autoencoder for directed acyclic graphs. In Advances in Neural Information Processing Systems, pp. 1586-1598, 2019.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018
11


Reviews:
[{"review_id": "a7T_RMO0S7y", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce a NAS technique with an adversarial component. The discriminator learns to tell the difference between a set of good networks and randomly generated ones. This is quite a nice idea.\n\nA few comments. I don’t think Section 3.1 adds anything and would be better off in an appendix. The connection between Algorithm 1 and Algorithms 2 seems fairly tenuous to me (although I could be wrong).\n\nThe bibliography is unacceptable. All papers with more than two authors are written as “et al.”, and there are glaring inconsistencies. arXiv is mentioned in multiple different ways and different fonts are used for different entries.\nOn a formatting issue, the text in the paper doesn’t look right compared to other ICLR submissions (it’s too pale). It would be worth looking in to this. The paper is otherwise fairly well written. Referring to EfficientNet as “Google’s EfficientNet” is quite odd. ResNet is not written as “Microsoft’s ResNet”.  I would recommend crediting the authors and not the institution. Table 2 appears above Table 1.\n\nThe details regarding training and the generator architecture are relegated to the appendix. These are very elaborate, which makes it very difficult to tell what is exactly contributing to the algorithm working. Table 7 seems to indicate that the discriminator itself can be removed for quite a small change in mean accuracy (94.2ish to 94.1ish). Without the discriminator the algorithm appears to be REINFORCE but with a more complicated generator network. On a related note, the comparison to REINFORCE is missing in table 1 which makes me suspect that this algorithm is basically the same thing in outcome, if not in effect.\n\nTable 9 in the appendix (minor note — it’s not really an appendix when it’s in a separate file!) seems to show that different means of varying the size of the pool of networks over training has very little effect. (Having 94.227 in bold above 94.22 doesn’t change the fact that we are talking about 0.007%!)\n\nThe evaluation in Table 1 is very odd, as the authors are reporting the best acc instead of mean+-std as is common practice. This is unreliable, as when deploying these algorithms in the wild we are far more interested in how they do in expectation (particularly if they fail completely some of the time).\n\n Although the idea of using an adversarial framework to tell apart architectures in a search space is nice, the implementation has many moving parts, and doesn’t appear noticeably different to the standard REINFORCE NAS approach (which just has a generator as an RNN).  The presence of a discriminator has a very minimal effect, which is a shame. Some evaluation choices are very questionable. I am inclined towards rejection.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_M14xJ2uVkh", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a Neural Architecture Search algorithm (GA-NAS) based on adversarial learning. The generator constructs architectures auto-regressively, which receives feedback from a GNN discriminator. Reinforcement learning (PPO) is used for training, to solve non-differentiability. GA-NAS’s effectiveness is demonstrated on several architecture search benchmarks for CIFAR-10 and 100, and is shown to improve EfficientNet for ImageNet.\n\nDisclosure: I’m only vaguely familiar with the neural architecture search literature.\n\nPros:\n1.\tGA-NAS appears to consistently find high ranking architectures compared to the baselines, often at the cost of fewer queries.  \n2.\tA fairly extensive set of experiments are included in the Experiments section and Appendix.\n3.\tGA-NAS is able to incorporate constraints into search. The authors demonstrate that GA-NAS is able to find a variation that slightly outperforms EfficientNet-B0.\n\nCons:\n1.\tAs the name implies, the goal of NAS is search. GANs have proven excellent over the years at interpolation, but not extrapolation, which is what search/exploration requires. I’m concerned that a GAN-based approach is therefore limited in its search ability. How would GA-NAS compare with a random search policy constrained to be close to known “good” architectures?\n2.\tThe GA-NAS generator and discriminator are initialized with an initial set of good architectures X_0. In the experiments, X_0 takes on the value of 50 and 100. The assumption that such a large number of “good” architectures are available ahead of time seems rather strong.\n3.\tThe authors state that previous work has determined that other architecture search methods are not any better than random search. The gains in accuracies of the architectures produced by GA-NAS over the baseline seem moderate at best.\n\nQuestions:\n1.\tWhere in the f-GAN paper is it stated that the JS divergence is more robust than the assymetric KL? Can you demonstrate this claimed advantage in GA-NAS by comparing objectives? \n2.\tIs X_0 counted in the number of queries reported? How were these initial architectures chosen? What rank are they?\n\nMiscellaneous:\n1.\tThis paper doesn’t adhere to the ICLR citation guidelines; citations in the text should include the first author’s last name and year. Additionally, the entire author list should appear in the references, not just “[First author] et al.” Please correct this during the rebuttal phase.\n2.\tTable 1: Typically, values in a table are bolded to represent the best values. BANANAS has the same accuracy value as GA-NAS.\n3.\tWhy is the variance of GA-NAS’s accuracy so small in Table 1? \n4.\tTable 2 caption could be more descriptive. Besides the columns, how is this table differ from Table 1?\n5.\tThere’s an extra space between “ImageNet” and footnote 2.\n\nRating:\nWhile the results seem good, I’m not entirely convinced that a generative adversarial approach can effectively explore a neural architecture space, as the discriminator will inherently disincentivize deviating from previously seen architectures. I’m also concerned about the validity of the assumption that an initial set of known “good” architectures would be available to a search algorithm; the authors should clarify how these were selected. I lean toward rejection for now, but would be willing to raise my score if the authors could address my concerns.\n\n\n========\nPost-rebuttal\n========\n\nI thank the authors for answering my questions. While I am satisfied with the authors response to my concern about the \"initial good architectures\" assumption, I still remain unconvinced that adversarial learning can help search find new good architectures. I keep my score.\n\nI also encourage the authors to carefully re-read the f-GAN paper, which explains exactly how any f-divergence (including the KL) can be implemented for adversarial learning. Switching to any f-divergence requires only a simple change to the loss function. It also appears that the authors significantly misunderstand VAEs. The difference between GANs and VAEs is not JS-divergence vs KL-divergence. Using a KL loss for adversarial learning does not require switching to a VAE. Given the central role they play in this paper's motivation, a better understanding of these subjects is important.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9Z-a9SdW3XV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A flexible but complex and expensive NAS method.\n\nSummary:\nThe authors introduce a method for NAS that repeatedly trains a generator to sample candidate architectures. The method is evaluated on three NAS oracle benchmarks as well as constrained NAS settings. While there are some promising experimental results, I lean slightly against acceptance due to poor presentation, limited comparisons on most evaluations, and what seems like fairly limited benefits of the approach given its complexity and cost.\n\nStrengths:\n1. The method can easily incorporate constraints on computation and memory.\n2. The method outperforms existing non-weight-sharing methods on several benchmarks.\n\nWeaknesses:\n1. The method introduces a lot of complexity such as a graph NN, a recurrent NN, and a full round of generative adversarial training in each search iteration. The computational cost of the latter is not discussed.\n2. As with most non-weight-sharing methods, GA-NAS requires several hundred queries on each benchmark, which translates to GPU-weeks of search time. It is not clear that the benefits over weight-sharing methods, which are not quantified for most cases, outweigh this large search cost.\n3. The results section for unconstrained search is confusing and it is hard to make comparisons (see notes 4-7 below).\n4. From a look at the NAS-Bench-301 paper, it seems that BANANAS was the best non-weight-sharing method evaluated, but the authors compare only to EA and RS.\n5. In the constrained search section, there are no comparisons to any other NAS methods. For example, random search is just as easy to apply to constrained problems as GA-NAS and should be used as a baseline.\n6. There is no code in the supplementary materials. Will code be released?\n\nNotes:\n1. “Remain hard to be assessed” -> “Remain hard to assess”\n2. The citation style does not follow ICLR guidelines.\n3. “architectures are sampled, which are discretized graphs” -> “architectures, which are discretized graphs, are sampled”\n4. What does it mean to “discover the Nth best architecture in Q queries”? Is “best” here according to test or validation? Why is Q a good metric for speed given that the algorithm doesn’t know to stop after query Q since in practice it won’t know the rank N of the current architecture?\n5. Many numbers in paragraph 4 for Section 4.1 do not correspond to any number in any table.\n6. Why isn’t the BANANAS performance bolded in Table 1?\n7. Table 4 should include at least one weight-sharing method such as GDAS (Dong & Yang, 2019), which is much faster and performs reasonably well. \n\n# Post-response update\nThank you to the authors for answering some of my questions and clarifying the search and evaluation of GA-NAS. I believe my original assessment that the contributed method was complex remains accurate; while the authors note that other methods like ENAS also use an RNN controller, in my view those methods are also complex. This paper increases this complexity with a GNN and an adversarial training setup. Use of such additions require showing significant improvements over baselines like random search, which I do not believe is achieved. I thus stand by my initial rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "682dk9Acqt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Thanks for your informative response addressing my comments. After the revision, the description of the method is clearer (Sec 3.2), and the experimental results are clearer (Sec 4). I'll stay with my original accept-score.\n\n===============\n\nSummary:\n\nThe paper provides interesting results for neural architecture search. In particular, this paper proposes a search strategy for NAS problems, Generative Adversarial NAS (GA-NAS), using importance sampling, which can be applied to micro/macro, constrained/unconstrained search problems. GA-NAS beats the state-of-the-art search algorithms proposed for NAS on public benchmarks, including NAS-Bench-101, NAS-Bench-201, and NAS-Bench-301. Also, on the EfficientNet macro search space, GA-NAS finds a new architecture with higher ImageNet accuracy and a lower number of parameters than EfficientNet-B0.\n\n\nPros: \n\n1. The proposed method achieves higher performance to compare to previous methods with better robustness, reproducibility, and efficiency.\n\n2. The idea of NAS based on importance sampling for rare event simulation in the method seems interesting. The proposed method at the same time could be broadly applied to micro/macro, constrained/unconstrained search problems. \n\n3. This paper provides comprehensive experiments, including various ablation studies, to show the effectiveness of the proposed framework. \n\n\nCons: \n\n1. I suggest the authors conduct further ablation studies to enhance the understanding of the approach and readability of the paper: \n\n(1) Comparison of computational resources (e.g. wall clock inference time) required for each query in Table 1 and Table 3. To be a fair comparison, it would be better to compare [number of queries * resource consumed per query].\n\n(2) For the update algorithm of the generator, the proposed method uses JS-divergence minimization referring to [29]. Section 3.1 mentions that JS-divergence is more robust than KL-divergence, but I think a further analysis could strengthen the point.\n\n(3) Adding FLOPs or inference speed to Table 5 and Table 6 would be helpful in explaining the performance of the new architecture found by GA-NAS.\n\n2. Section 3, 4 need to be polished for better readability. For example, an explanation about the method and the concept of evaluation metric \"rank\" should be improved for the readers.\n\n\nSome typos: \n\n(1) In the section 3.2 “\\tau=\\{C_0,C_1,\\ldotsC_{N-1}\\}” -> “\\tau=\\{C_0,C_1,\\ldots,C_{N-1}\\}” \n(2) In the equation (10) of appendix, “-(1-\\rho) + P(X\\leq \\zeta^*)\\geq 0.” -> “-(1-\\rho) + P(X\\leq \\zeta^*)\\geq 0,”\n\nSome suggestions:\n\"\\cdots\"s are used in the expression such as \"X_1,\\cdots, X_N\" and \"S(X_1),\\cdots, S(X_N)\" in the proof of the theorem 6.2 in the appendix. I think \"\\ldots\" is more syntactically typical here.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for neural architecture search (NAS) based on adversarial methods. It uses a discriminator trained to distinguish between random vs. good architectures, letting the discriminator's scores serve as a reward signal for an autoregressive generator. I agree with AR1: this is a nice and clever idea. Reviewers generally agreed that the method was interesting, e.g. it's quite flexible in that it's able to incorporate constraints, and that the evaluation is rather extensive and shows that the method performs well across the board. Many minor criticisms were raised and addressed well by the authors in their responses and manuscript updates.

The major criticism shared by most reviewers was the high methodological complexity of the proposed approach, and the proportionally small gains shown over much simpler baselines. This criticism remained despite the authors' responses. The method is indeed complex: the same method without any adversarial component already performs well, and many important details of the model are relegated to Appendix A.2. (I would recommend, for example, moving Fig. 2 to the main text if at all possible. Also, the Appendix can/should be included in the main PDF for ICLR, rather than in supplementary material, as AR1 mentions.) It was not clear to reviewers that the adversarial component of the approach has a significant benefit. The authors respond by pointing to Table 7 showing that the discriminator reduces the number of queries and points out that in reality these queries correspond to expensive evaluations. If this is a major selling point of the method (it sounds like it could be), it should be highlighted and analyzed far more -- at least moved to the main text rather than an Appendix -- ideally with a real-world evaluation showing a practical large improvement in overall wall-clock time, rather than a benchmark where these evaluations are free. Perhaps the exclusive reliance on these benchmarks, though undoubtedly useful for quick experimentation, in the end holds back the paper and prevents the method's benefits from becoming apparent to the readers.

As a minor point (also raised by AR1), the paper is formatted incorrectly for ICLR: the font color is off, and more importantly the PDF is unsearchable (text cannot be selected, ctrl-F does not work), which makes it very difficult to quickly reference and review. Please try not to stray from the conference-provided style file for future submissions.

I appreciate the cleverness of the method, the extent of the evaluation, and the thorough responses to the reviews. However, unfortunately with the current presentation, it is too difficult to discern the benefit of the proposed approach from the manuscript. The approach is nonetheless intuitively appealing and seems quite promising, and I hope the authors will take the reviewers' good feedback into account and resubmit the paper in the future.
Decision: Reject