Evaluating The Search Phase of Neural Architecture Search
Authors: Kaicheng Yu
Christian Sciuto
Martin Jaggi
Claudiu Musat
Mathieu Salzmann
Venue:  (2020)
Keywords: Neural architecture search
parameter sharing
random search
evaluation framework

Abstract: 
Neural Architecture Search (NAS) aims to facilitate the design of deep networks for new tasks. Existing techniques rely on two stages: searching over the architecture space and validating the best architecture. NAS algorithms are currently compared solely based on their results on the downstream task. While intuitive, this fails to explicitly evaluate the effectiveness of their search strategies. In this paper, we propose to evaluate the NAS search phase.
To this end, we compare the quality of the solutions obtained by NAS search policies with that of random architecture selection. We find that: (i) On average, the state-of-the-art NAS algorithms perform similarly to the random policy; (ii) the widely-used weight sharing strategy degrades the ranking of the NAS candidates to the point of not reflecting their true performance, thus reducing the effectiveness of the search process.
We believe that our evaluation framework will be key to designing NAS strategies that consistently discover architectures superior to random ones.

Published as a conference paper at ICLR 2020
EVALUATING THE SEARCH PHASE OF NEURAL ARCHITECTURE SEARCH
Kaicheng Yu"
Christian Sciuto Daskell christian, stt.iinnnnctttttaskkllllll
Computer vision lab, EPFL ka kaicheng. yocliggyu@@eppp yu@epfl... .eepflcch
Martin Jaggi
Claudiu Musat
Machine learning and optimization lab, EPFL martin. jaggieepfl.cccmmmmmmommm
Swisscom Digital Lab claudiu www.mmttssssseeeemmmmmmm com
Mathieu Salzmann
Computer vision lab, EPFL mathieu. sal zmann@epfl.ccc
ABSTRACT
Neural Architecture Search (NAS) aims to facilitate the design of deep networks for new tasks. Existing techniques rely two stages: searching over the architecture space and validating the best architecture. NAS algorithms are currently compared solely based on their results the downstream task. While intuitive, this fails to explicitly evaluate the effectiveness their search strategies. In this paper, propose to evaluate the NAS search phase. To this end, compare the quality of the solutions obtained by NAS search policies with that of random architecture selection. We find that: (i) On average, the state-of-the-art NAS algorithms perform similarly to the random policy; (ii) the widely-used weight sharing strategy degrades the ranking of the NAS candidates to the point of not reflecting their true performance, thus reducing the effectiveness of the search process. We believe that our evaluation framework will be key to designing NAS strategies that consistently discover architectures superior to random ones.
INTRODUCTION
By automating the design of neural network for the task at hand, Neural Architecture Search (NAS) has tremendous potential to impact the practicality
deep learning (Zoph Le| 2017: Liu et al.
2018b/a at Tan et al. 2018 Baker et al. 2016), and has already obtained state-of-the-arr performance on many tasks. typical NAS technique (Zoph & Le 2017 Pham et al.] 20188) [iu et al.) [2018s (0) has two stages: the search phase, which aims find good architecture, and the evaluation one, where the best architecture is trained from scratch and validated on the test data.
In the literature, NAS algorithms compared based on their results in the evalua- tion phase. While this may seem intuitive, the search phase of these algorithms often differ in several ways, such as their architecture sam- pling strategy and the search space they use, and the impact of these individual factors cannot be identified by looking at the downstream task re- sults only. Furthermore, the downstream results are often reported for single random seed, which leaves unanswered the question of robustness of the search strategies.
typically
Table 1:
Comparison NAS algorithms with random sampling, We report results on PTB us- ing mean validation perplexity (the lower, the bet- ter) and on CIFAR- 10 using mean top accuracy. also provide the p-value of Student's t-tests against random sampling.
PTB (PPI.)
t-test
CIFAR- 10 (acc.)
1-test
ENAS
59.88 + 1.92
0.73
96.79 + 0.11
0.01
DARTS
60.61 2.54
0.62
96.62 0.23
0.20
NAO
61.99
0.02
96.86 0.17
0.00
Random
60.13 0.65
96.44 0.19
Equaal contribution
Work done Swisscom digital lab.

---

Published as a conference paper at ICLR 2020
In this paper, we therefore propose to investigate the search phase of existing NAS algorithms in controlled manner. To this end, we compare the quality of the NAS solutions with a random search policy, which uniformly randomly samples architecture from the same search space as the NAS algorithms, and then trains it using the same hyper-parameter as the NAS solutions. To reduce randomness, the search using each policy, i.e., random and NAS ones, is repeated several times, with different random seeds.
We perform a series of experiments on the Penn Tree Bank (PTB) (Marcus et al. 1994a) and CIFAR- 10 (Krizhevsky et al. 2009) datasets, in which we compared the state-of-the-art NAS algorithms whose code publicly available DARTS (Liu et al. 2019b), NAO (Luo et al.) 2018) and ENAS (Pham et al. 2018)-1 to our random policy. We reached the surprising conclusions that, as shown in Table [ none of them significantly outperforms random sampling. Since the mean performance for randomly- sampled architectures converges to the mean performance over the entire search space, we further conducted Welch Student's 1-fests (Welch 1947), which reveal that, in RNN space, ENAS and DARTS cannot be differentiated from the mean of entire search space, while NAO yields worse performance than random sampling. While the situation slightly better in CNN space, all three algorithms still perform similarly to random sampling. Note that this does not necessarily mean that these algorithms perform poorly, but rather that the search space has been sufficiently constrained so that even a random architecture in this space provides good results. To verify this, we experiment with search spaces where we can exhaustively evaluate all architectures, and observe that these algorithms truly cannot discover top-performen uo-pefforming architectures.
In addition to this, we observed that the ranking by quality of candidate architectures produced by the NAS algorithms during the search does not reflect the true performance of these architectures in the evaluation phase. Investigating this further allowed us to identify that weight sharing (Pham et al. 2018), widely adopted to reduce the amount of required resources from thousands of GPU days to a single one, harms the individual networks' performance. More precisely, using reduced search spaces, we make use of the Kendall Tau r metrid" to show that the architecture rankings obtained with and without weight sharing are entirely uncorrelated in RNN space (T = -0.004 over 10 runs); and have little correlation in the CNN space (T = 0. 195 over 10 runs). Since such a ranking is usually treated as training data for the NAS sampler in the search phase, this further explains the small margin between random search and the NAS algorithms. We also show that training samplers without weight sharing in CNN space surpasses random sampling by significant margin.
In other words, we disprove the common belief that the quality of architectures trained with and without weight sharing is similar. We show that the difference in ranking negatively impacts the search phase of NAS algorithms, thus seriously impeding their robustness and performance.
In short, evaluating the search phase of NAS, which is typically ignored, allowed us to identify two key characteristics of state-of of-the-art NAS algorithms: The importance of the search space and the negative impact of weight sharing. We believe that our evaluation framework will be instrumental in designing NAS search strategies that are superior to the random one. Our code is publicly available at filtttp::///o http:::///gttbb../ c kwwpkk14/ 20ap011//evaaaaaasa
2 RELATED WORK
Since its introduction in Zoph & Le 2017). NAS has demonstrated great potential to surpass the
human design of deep networks for both visual recognition (Liu al., 20186) Ahmed & Torresani]
2018, Chen et al. [0188] Pérez-Rūa et al. 2018 Liu et al., 2019a) and natural language process-
ing (Zoph & Le 2017; Pham et al. 2018 Luo et al.] 2018| Zoph et al.
2018 Liu et al. 2018b]
Cai et al. 2018ap. Existing search strategies include reinforcement learning (RL) samplers (Zoph)
& Le| 20 7| Zoph et al. 2018 Pham et al., 2018), evolutionary algorithms (ii & Yuille 2017 7
Real et 2017 Mo077|ikkkkkinnee et al. 2019 Liu al.
2018b Lu et al.
2018). gradient-descent (Liu
ct al. 2019b). bayesian optimization Kandasamy et al.
2018 Jin et al.
2019 Zhou et al.; 2019) and
performance predictors (Liu al., 201 Sa Luo et al.
(0188). Here, our goal is not to introduce new
search policy, but rather to provide the means to analyze existing ones. Below, we briefly discuss existing NAS methods and focus on how they are typically evaluated.
Neural architecture search with weight sharing. The potential of vanilla NAS comes with the drawback of requiring thousands of GPU hours even for small datasets, such as PTB and CIFAR-10.
TThe Kendall Tau (Kendall 1938) metric measures the correlation of ranking. Details in Appendix A.1
2

---

Published as a conference paper at ICLR 2020
Furthermore, even when using such heavy computational resources, vanilla NAS has restrict the number of trained architectures from a total of 10 to 10 and increasing the sampler accuracy can only be achieved by increasing the resources.
ENAS (Pham et al. 2018) was the first to propose training scheme with shared parameters, reducing the resources from thousands of GPU days to one. Instead of being trained from scratch each sampled model inherits the parameters from previously-trainee ones. Since then, NAS research has mainly focused on two directions: 1) Replacing the RL sampler with better search algorithm, such as gradient descent (Liu et al., 2019b), bayesian optimiziation (Zhou et al. 2019) and performance predictors (Luo et al. 2018); ; 2) Exploiting NAS for other applications. e.g., object detection (Ghiasi
et al., 2019; Chen et al., 2019), semantic segmentation (Liu et al., (2019a). and finding compact
networks (Cai al. 2018b Wu et al. 2018 Chu al.
2019 Guo et al. 2019).
Characterizing the search space. Ying et al. (2019); Dong & Yangl (2020) introduced a dataset that contains the ground-truth performance of CNN cells, and |Wang al. (2019) evaluated some traditional search algorithms on it. Similarly, Radosavovic et al. (2019) characterizes many CNN search spaces by computing the statistics of a set of sampled architectures, revealing that, for datasets such as CIFAR-10 10 or ImageNet, these statistics are similar. While these works support our claim that evaluation of NAS algorithms crucial, they do not directly evaluate the state-of-the-arts NAS algorithms as we do here.
Evaluation of NAS algorithms. Typically, the quality of NAS algorithms is judged based on the results of the final architecture they produce on the downstream task. In other words, the search and robustness of these algorithms are generally not studied, with (Liu et al. (019b] So et al.] 2019) the only exception for robustness, where results obtained with different random seeds were reported. Here, we aim to further the understanding of the mechanisms behind the search phase of NAS algorithms. Specifically, we propose doing by comparing them with simple random search policy, which uniformly randomly samples one architecture per run in the same search space as the NAS techniques.
While some works have provided partial comparisons to random search, these comparisons unfortu- nately did not give fair chance the random policy. Specifically, (Pham et al. 2018) reports the results of only single random architecture, and (Liu et al. 2018b) those of an architecture selected among 8 randomly sampled ones as the most promising one after training for 300 epochs only. Here, we show that fair comparison to the random policy, obtained by training all architectures, i.e., random and NAS ones, for 1000 epochs and averaging over multiple random seeds for robustness, yields different picture; the state-of- the-art search policies are better than the random one.
The motivation behind this comparison was our observation of only a weak correlation between the performance of the searched architectures and the ones trained from scratch during the evaluation phase. This phenomenon was already noticed by Zela et al. (2018), and concurrently to our work by Li & Talwalkar (2019); ; Xie al. (2019); Ying al. (2019). but the analysis of its impact or its causes went no further. Here, by contrast, we link this difference in performance between the search and evaluation phases the of weight sharing.
While this may seem to contradict the findings of Bender et al. (2018), which, on CIFAR-10, observed strong correlation between architectures trained with and without weight sharing when searching a CNN cell, our work differs from (Bender et al. (0188) in two fundamental ways: 1) The training scheme in (Bender al., 2018), in which the entire model with shared parameters is trained via random path dropping, is fundamentally different from those used by tftee-of-the-ane weight sharing NAS strategies (Pham et al. 2018 Liu al.) 2019b] Luo al., (018); 2) While the correlation in (Bender et al. 2018) was approximated using a small subset of sampled architectures, we make use of a reduced search space where we can perform complete evaluation of all architectures, thus providing an exact correlation measure in this space.
3 EVALUATING THE NAS SEARCH
In this section, we detail our evaluation framework for the NAS search phase. As depicted in Fig. [a.)), typical NAS algorithms consist of two phases:
3

---

Published as a conference paper at ICLR 2020
One Architesture
Rispeat stop
Pepeet times
Trained Pokiyy Sampler
train
Param update
Search
Search spaco
Search space
sample
sample
Random model
Top model
Top model
DARTS
ENAS
update
evalutte
Train from
Policy Sampler
scretonn
scratin
(a) Search Phase
(b) Standard Evaluation Phase
(c) Our Evaluation Phase
Figure 1: Evaluating NAS. Existing frameworks consist of two phases: (a) The search phase, where sampler is trained to convergence trains the best model from scratch and evaluates it on the test data. Here, we argue that one should evaluate the search itself. To this end, shown in (c), compare the best architecture found by the NAS policy with a single uniformly randomly sampled architecture. For this comparison to be meaningful, we repeat it with different random seeds for both training the NAS sampler and our random search policy. We then report the mean and standard deviations over the different seeds.
pre-defined stopping criterion; (b) The evaluation phase that
The goal of this phase is to find the best candidate architecture from the search space" This is where existing algorithms, such as ENAS, DARTS and NAO, differ. Nevertheless. for all the algorithms, the search depends heavily initialization. In all the studied policies, initialization is random and the outcome thus depends on the chosen random seed.
Search:
Evaluation: In this phase, all the studied algorithms retrain the best model found in the search phase. The retrained model is then evaluated on the test data.
The standard evaluation of NAS techniques focuses solely on the final results on the test data. Here, by contrast, aim evaluate the search phase itself, which truly differentiates existing algorithms.
To do this, as illustrated Fig. [cc,, we establish a baseline; we compare the search phase existing algorithms with random search policy. An effective search algorithm should yield solution that clearly outperforms the random policy. Below, we introduce our framework to compare NAS search algorithms with random search. The three NAS algorithms that evaluated, DARTS (Liu al. 20195). NAO (Luo et al., 2018) and ENAS (Pham et al.) 2018). are representative the state of the art for different search algorithms: reinforcement learning, gradient-descent and performance prediction, and are discussed in Appendix
3.1 COMPARING TO RANDOM SEARCH
We implement our random search policy by simply assigning uniform probabilities to all operations. Then, for each node the Directed Acyelic Graph (DAG) that is typically used to represent an architecture, we randomly sample a connection to one previous node from the resulting distributions.
An effective search policy should outperform the random one. To evaluate this, we compute the validation results of the best architecture found by the NAS algorithm trained from scratch, as well as those single randomly sampled architecture. Comparing these values for a single random seed would of course not provide reliable measure. Therefore, we repeat this process for multiple random seeds used both during the search phase of the NAS algorithm and to sample one random architecture as described above. We then report the means and standard deviations of these results over the different seeds. Note that while we use different seeds for the search and random sampling, always use the same seed when training the models from scratch during the evaluation phase.
Our use of multiple random seeds and of the same number of epochs for the NAS algorithms and for random search policy makes the comparison fair. This contrasts with the comparisons performed in (Pham et al. 2018), where the results of only single random architecture were reported, and
Details about search spaces are provided Appendix
4

---

Published as a conference paper at ICLR 2020
in (Liu et al. 2019b), which selected single best random architecture among an initial set of 8 after training for 300 epochs only. As shown in Appendix [D2 some models that perform well in the early training stages may yield worse performance than others after convergence. Therefore, choosing the best random architecture after only 300 epochs for PTB and 100 for CIFAR-10, and doing so for a single random seed, might not be representative of the general behavior.
3.2 SEARCH IN A REDUCED SPACE
Because of the size of standard search spaces, one cannot understand the quality of the search by fully evaluating all possible solutions. Hence, we propose to make use of reduced search spaces with ground-truth architecture performances available to evaluate the search quality. For RNNs, simply reduce the number of nodes in the search space from 12 to 2. Given that each node is identified by two values, the ID of the incoming node and the activation function, the space has a nodes and O operations, thus yielding 32 possible
cardinality |S| n!! O n where solutions. To obtain ground truth, we train all of these architectures individually. Each architecture is trained 10 times with different seed, which therefore yields mean and standard deviation of its performance. The mean value is used as ground truth the actual potential of the given architecture. These experiments took around 5000 GPU hours.
For CNNs, we make use of NASBench- 101 (Ying et al. 2019), CNN graph-based search space with 3 possible operations, conv3x3, convlx1 and max3x3. This framework defines search spaces with between 3 and 7 nodes, with 423,624 architectures in 7-node case. To the best of our knowledge, we are the first to evaluate the NAS methods used in this paper on NASBench.
4 EXPERIMENTAL RESULTS
To analyze the search phase of the three state-of-the-art NAS algorithms mentioned above, we first compare these algorithms to our random policy when using standard search spaces for RNNs on (PTB) and CNNs on CIFAR-10. 10. Details about the experiment setting are in Appendix C.5 The surprising findings in this typical NAS use case prompted us to study the behavior of the search strategies in reduced search spaces. This allowed to identify factor that has significant impact on the observed results: Weight sharing. We then quantify this impact on the ranking of the NAS candidates, evidencing that it dramatically affects the effectiveness of the search.
4.1 NAS COMPARISON IN A STANDARD SEARCH SPACE
Below, we compare DARTS Liu et al. 2019b), NAO (Luo et al. 2018), ENAS (Pham et al. 2018) and BayesNAS (Zhou et al. 2019) with our random search policy, as discussed in Section 3.1 We follow (Liu et al. 2019b) to define an RNN search space of 12 nodes and a CNN ones of nodes. For each of the four search policies, run 10 experiments with different initialization of the sampling aaper-parameters and code for each
policy. During the search phase, we used the authors authors-provided provided policy. Once best architecture is identified by the search phase, is used for evaluation, i.e., train the chosen architecture from scratch for 1000 epochs for RNN and 600 for CNN.
RNN Results. In Figure we plot, on the left, the mean perplexity evolution over the 1000 epochs, obtained by averaging the results of the best architectures found using the 10 consec- utive seeds On the right, we show the per- plexity evolution for the best cell of each strat- egy among the 10 different runs. Random sam- pling is robust and consistently competitive. As shown in Table [ it outperforms average the DARTS and NAO policies, and yields the overall best cell for these experiments with perplexity
enas
Pelidattion ppA
nao
random
Average
Best
Figure 2: Validation perplexity evolution in the 12-node RNN search space. (Best viewed in color)
SStarting from 1268, which is right after 1267, the seed released by Liu et al. (2099h). Note that, using this seed, we can reproduce the DARTS RNN search and obtain validation PPI. of 55.7 in (Liu et al. 20196).
5

---

Published as a conference paper at ICLR 2020
of 57.60. Further training this cell for 4000 epochs, as in (Liu et al., 2019b), yields a perplexity of 55.93. The excellent performance of the random policy evidences the high expressiveness of the mamually-construuc
search space; even arbitrary policies in this space perform well, as evidenced by the relatively low standard deviation over the 10 seeds of the random architectures, shown in Table Figure Ileft).
CNN Results. In Table 2 we compare the NAS methods with our random policy in the search space of Liu et al. (2019b). We provide the accuracy reported in the original papers as well as the accuracy we reproduced using our implementation. Note that the NAS algorithms only marginally outperform random search, by less than 0.5% in top-1 accuracy. The best ar- chitecture was discovered by NAO, with an ac- curacy of 97.10%, again less than 0.5% higher than the randomly discovered one. Note that, our random sampling comes at no search cost, By contrast, [Li & Talwalkar (2019) obtained an accuracy of 97. 15% with a different random search policy having the same cost as DARTS,
Table 2: Top 1 accuracy in the 7-node DARTS Search space. We report the mean and best top-1 accuracy on the test sets of architectures found by DARTS, NAO, ENAS, BayesNAS, and our random policy. As sanity check, we also train from scratch the architectures reported in original papers, as well as their reported performance.
Our seed
Best reported result
Type
Mean test
Best
Original
Reproduced
DARTS
96.62 0.23
96.80
97.24
97.15
NAO
96.86 : 0.17
97.10
96.47
96.92
ENAS
96.76 0.10
96.95
96.46
96.87
BayesNAS
95.99 0.25
96.41
97.19
97.13
Random
96.48 0.18
96.74
97.15
Result took from & Talwalkar
2019
Observations:
The evaluated state-of-the-an NAS algorithms do not surpass random search by a significant margin, and even perform worse in the RNN search space.
The ENAS policy sampler has the lowest variance among the three tested ones. This shows that
ENAS is more robust to the variance caused by the random seed of the search phase.
The NAO policy is more sensitive to the search space; while it yields the best performance in CNN space, it performs the worst in RNN one.
The DARTS policy is very sensitive to random initialization, and yields the largest standard deviation across the 10 runs (2.54 in RNN and 0.23 in CNN space).
Such comparison of search policies would not have been possible without our framework. Never- theless, the above analysis does not suffice to identify the reason behind these surprising observations. As mentioned before, one reason could be that the search space has been sufficiently constrained so that all architectures perform similarly well. By contrast, we assume that the search space does contain significantly better architectures, then we can conclude that these search algorithms truly fail to find a good one. To answer this question, we evaluate these methods in a reduced search space, where we can obtain the true performance of all possible architectures.
4.2 SEARCHING REDUCED SPACE
The results in the previous section highlight the inability of the studied methods to surpass ran-
DARTS
dom search. Encouraged by these surprising results, we then dig deeper into their causes. Be- low, we make use of search spaces with fewer nodes, which we can explore exhaustively.
NAO
X
ENAS
10
15
20
25
Best
architecture rank
Worst
Reduced RNN space. We use the same search space as Section 3.2 but reduce the number of intermediate nodes to 2. In Table 3 (A), we provide the results of searching the RNN 2-node space. Its smaller size allows to exhaustively compute the results of all possible solutions, thus determining the upper bound for this case. In Figure 3, we plot the rank of the top 1 architecture discovered by the three NAS algorithms for each of the 10 different runs.
Figure 3: Architectures discovered by NAS algo- rithms. We rank all 32 architectures in the reduced search space based on their performance of individ- ual training, from left (best) to right (worst), and plot the best cell found by three NAS algorithms across the 10 random seeds.

---

Published as a conference paper at ICLR 2020
Table 3: Results in reduced search spaces. For RNNS (A), We report the mean and best perplexity on the validation and test sets at the end of training the architectures found using DARTS, NAO, ENAS, For CNNs (B), we show the mean and best top-1 accuracy on the test set. Instead of running random sampling in the reduced space, we compute the probability of the best model found by each method surpass the random one (details Appendix A.2). The mean and best statistics of the entire search space are reported as Space.
(A) RNN n=2(32) PPL.
(B) NASBench n=7(43
Type
Mean
Valid
Mean Test
Best Valid
Best Test
Mean Acc.
Best Acc.
Best Rank
p(srandom)
DARTS
71.29 1 2.45
68.74
2.42
68.05
65,55
92.21 0.61
93.02
S7079
0.24
NAO
68.66
2.50
66.03
2.40
66.22
63.59
92.59 0.59
93.33
19552
0.62
ENAS
69.99
0.0
66.61 + 0.0
69.99
66.61
91.83 + 0.42
92.54
96939
0.07
Space
69.69 1 2.44
67.21 2.52
65.38
62.63
90.93 5.84
95.06
We observe that: (i) All policies failed to find the architecture that actually performs best; (ii) The ENAS policy always converged to the same architecture. This further evidences the robustness of ENAS to the random seed: (ii) NAO performs better than random sampling on average because keeps ranking of architectures; (iv) DARTS never discovered top-5 architecture.
Reduced CNN space. In Table (B), we report the mean and best test top-1 I accuracy over 10 different runs on the NASBench- 101 7-node space. To assess the search performance, we also show the best architecture rank in the entire space. The best test accuracy found by these methods is 93.33, by NAO, which remains much lower than the ground-truth best of 95.06. In terms of ranking, the best rank of these methods across 10 runs is 19522, which is among the top 4% architectures and yields a probability of 0.62 to surpass a randomly-sample ENAS and DARTS only have 7% and 24% chance surpass the random policy. See Appendix A.2 for the definition of this probability, and Appendix [33 for detailed results.
one given the same search budget. Note that
NAO seems to constantly outperform random search in the reduced space. Nevertheless, the final architecture chosen by NAO is always one of the architectures from the initial pool, which were sampled uniformly randomly. This indicates that the ranking of NAO is not correctly updated throughout the search and that, in practice, in a reduced space, NAO is similar to random search.
4.3
IMPACT OF WEIGHT SHARING
Our previous experiments in reduced search spaces highlight that the ranking of the searched architectures does not reflect the ground-truth one. As we will show below, this can be traced back to weight sharing, which all the tested algorithms, and the vast majority of existing ones, rely on. To evidence this, we perform the following experiments:
Without WS: We make use of the reduced space, where we have the architecture's 's real performance.
With WS: We train the architectures in parallel, using the weight sharing strategy employed in NAO and ENAS. As DARTS does not have discrete representations of the solutions during the search, the idea of solution ranking does not apply. During training. each mini- is given to an architecture uniformly sampled from the search space. We repeat the process 10 times, with 10 random seeds and train the shared weights for 1000 epochs for the RNN experiments and 200 epochs for the CNN ones. Note that, this approach is equivalent to Single Path One Shot (SPOS) (Guo et al. 2019). It guarantees equal expectations of the number of times each architecture is sampled, thus overcoming the bias due to unbalanced training resulting from ineffective sampling policies.
We then compute the correlation between the architecture rankings found with WS and the ground truth (i.e., the architectures trained independently). For each of the 10 runs of the weight sharing strategy, we evaluate the Kendall Tau metric (defined in Appendix A.I of the final rankings with respect to the real averaged ranking.
In Figure aa), we depict the architecture performance obtained without WS (sorted in ascending order of average validation perplexity). ), and the corresponding performance with WS. In Figure (b), we show the rank difference, where the best and worst were found using the Kendall Tau metric, and show a concrete rank change example Figure
RNN Results.
7

---

Published as a conference paper at ICLR 2020
Ground-Truth
Pank with weight sharing
Avarage
Pank
33
10
out upei gdd PYP
19
12
24
Vala pol
nank positoo
21
17
17
17
2
offference
5
10
10
1.0
10
architecture
(0.004)
(4) Architecture performance with without
Rank difference due weight sharing
c) Example
Figure 4: Rank disorder due to weight sharing in RNN reduced space. (a) We report the average and std over 10 different runs. Note that the rankings significantly differ between using (line plot) and not using WS (bar plot), showing the negative impact of this strategy. (b) We visualize from left to right, the best, worst and average cases, and show the corresponding Kendall Tau value. A change ranking, indicated by the colors and numbers, is measured as the absolute position change between the WS ranking and the true one. For conciseness, we only show the top 10 architectures. (c) For example, in the average scenario, the 6-th best architecture is wrongly placed the best one, as indicated by the red arrow.
CNN Results, We report the average Kendall across 10 different runs. Note that pled up to 200 architectures for each experiment and fully evaluated on the entire test set use
Table 4: Search results w/o weight sharing, We report results from ENAS ans NAO on NASBench with nodes 10 runs.
Type
Mcan Acc.
Best Acc.
Best Rank
P(>random)
the test accuracy for ranking. The Kendall tau for search spaces from 3 to 7 nodes is, respec- tively, 0.441, 0.314 14,, 0.214, 0.195. We also pro- vide other statistics in Table of Appendix [D.3]
NAO ENAS
93.08 0.71
94,11
3543
0.92
93.54 + 0.45
94.04
4610
0.90
Since NAO and ENAS intrinsically disentangle the training of shared weights and sampler, to further confirm the negative effect of weight sharing, we adapt these algorithms to use the architecture's performance in the NASBench dataset to train their sampler. Table evidences evidenees that, after removing weight sharing, both ENAS and NAO consistently discover a good architecture, as indicated by a small difference between the best over 10 runs and the mean performance. More interestingly, for the 7-node case, the best cell discovered (94. 1111% by NAO and 94.04% by ENAS) are more than 1% higher than the best cells found with weight sharing (93.33 and 92.54, respectively, in Table
Observations:
The difference of architecture performance is not related to the use of different random seeds, as indicated by the error bars in Figure 4 a).
WS never produces the true ranking, evidenced by the Best case Figure (b).
The behavior of the WS rankings is greatly affected by changing the seed. In particular, the Kendall Tau for the plots Figure(41b) are 0.282, -0.004, 10.116 for Best, Average and Worst.
For RNNs, the Kendall Tau are close to which suggests a lack of correlation between the WS rankings and the true one. By contrast, for CNNs, the correlation is average higher than for RNNs. This matches the observation in Section that CNN results are generally better than RNN ones.
In a reduced CNN space, the ranking disorder increases with the space complexity, i.e., this disorder is proportional the amount of weight sharing
If we train NAO and ENAS without weight sharing in NASBench,, average the performance is 1 % higher than them with it. This further evidences that weight sharing negatively impacts the sampler, and with good ranking, the sampler be trained better. Furthermore, the probability to surpass random search increases from 0.62 to 0.92 for NAO and from 0.07 to 0.90 for ENAS.
"We also conduct another experiment regarding the amount of sharing Appendix D.I
8

---

Published as a conference paper at ICLR 2020
Together with previous results, we believe that these results evidence the negative impact of weight sharing; dramatically affects the performance of the sampled architectures, thus complicating the overall search process and leading search policies that are better than the random one.
CONCLUSION
In this paper, have analyzed the effectiveness of the search phase of NAS algorithms via fair comparisons to random search. We have observed that, surprisingly, the search policies of state-of- the-art NAS techniques are no better than random, and have traced the reason for this the use of (i) a constrained search space and (ii) weight sharing, which shuffles the architecture ranking during the search, thus negatively impacting it.
In essence, our gained insights highlight two key properties of state-of -ft--o---ttt----- art NAS strategies, which had been overlooked in the past due the single-minded focus of NAS evaluation on the results on the target tasks. We believe that this will be key to the development of novel NAS algorithms. In the future, we will aim to do by designing relaxed weight sharing strategies.
ACKNOWLEDGEMENT
This work was supported in part by the Swiss National Science Foundation. We would also like to thank Rene Ranfil and Vladlen Koltun for the discussions and support.
REFERENCES
Karim Ahmed and Lorenzo Torresani. Maskconnect: Connectivity learning by gradient descent. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 349-365, 2018.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. arXiv preprint arXiv:1611.02167 2016.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. In International Conference Machine Learning, pp. 549-558, 2018.
Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. Efficient architecture search by network transformation. AAAI, 2018a.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware. arXiv: 081200033 /cs, stat), December 2018b. URL http:://ax::
Srg/abs/1812 00332
arXiv: 1812.00332.
Liang-Chies Chen, Maxwell Collins, Yukun Zhu, George Papandreou, Barret Zoph, Florian Schroff, Hartwig Adam, and Jon Shlens. Scarching for efficient multi-scale architectures for dense image prediction. In Advances in Neural Information Processing Systems, pp. 8713-8724, 2018.
Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Chunhong Pan, and Jian Sun. DetNAS: Neural Architecture Search on Object Detection. arXiv:1903.1 10979 [cs], March 2019, URL arXiv: 1903.10979.
httt:://arxxv.orgg/// hwtp:/g/abb/99999 10979
Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li. FairNAS: Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search. arXiv:1901 008411845 [cs, stat], July 2019. URL
http:://axiis org/ abs .001900..8855 arXiv: 1907.01845.
Terrance DeVries and Graham W. Taylor. Improved Regularization of Convolutional Neural Networks with Cutout. arXiv: 04552 [cs], August 2017. TRL.ttp:: httt:://axii.... www.wawwwwww.../a.aaaaaaaaaatape abg//b////// arXiv: 1708.04552.
04552
Xuanyi Dong and Yi Yang. Nas-bench- 102: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020. URL hctps:/
oppenreview http://wweee/ooommmmim.........e

---

Published as a conference paper at ICLR 2020
Golnaz Ghiasi, Tsung- Yi Lin, Ruoming Pang, and Quoe V. Le. NAS-FPN: Learning Scalable Feature Pyramid Architecture for Object Detection. arXiv:1904.07392 [cs], April 2019. URL
http::/arxiv.. org wwtp::/.tg...../aoa. 07392 arXiv: 1904.07392.
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single Path One-Shot Neural Architecture Search with Uniform Sampling. arXiv:1904.00 00400000000000 [cs]. March 2019. URL
904. 00420 arXiv: 1904.00420.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compulation, 9(8):
1735-1780, 1997.
Haifeng Jin, Qingquan Song, and Xia Hu. Auto-keras: An efficient neural architecture search system. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1946-1956. ACM, 2019.
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-2025, 2018.
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). 2009.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv:1902.0700 2019.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 19-34, 2018a.
Chenxi Liu, Liang- Liang-Chich Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan Yuille, and Fei- Fei. Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation. urXiv:/901.00 02985 [cs], 2019a. URL
02985
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hier- archical representations for efficient architecture search. International Conference on Learning Representations (ICLR), Conference track, 2018b.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. JCLR, 2019b.
Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf. Neta-net: A multi-objective genetic algorithm for neural architecture search. arXiv preprint 18100033. 2018.
Rengian Luo, Fei Tian, Tao Qin, En-Hong Chen, and Tie- Yan Liu. Neural architecture optimization. In Advances neural information processing systems, 2018
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Fer- guson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop Human Language Technology, HLT '94, pp. 1 114-119, Stroudsburg, PA, USA, 1994a, Association for Computational Linguistics. ISBN 1-55860-357-3. doi: (033115/107581211075555
URL /tlL:tttt////o..oo///.o.o
5812.11111 111.11177111111111331111111 1075835
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop on Human Language Technology. pp. 114-119, Association for Computational Linguistics, 1994b.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. arXiv preprint arXiv: arXiv:/708.005 1708.02 2017.
10

---

Published as a conference paper at ICLR 2020
Risto Miikkulainen, Jason Liang. Elliot Meyerson, Aditya Rawal, Daniel Fink, Olivier Francon, Bala Raju, Hormoz Shahrzad, Arshak Navruzyan, Nigel Duffy, et al. Evolving deep neural networks. In Artificial Intelligence in the Age Neural Networks and Brain Computing, pp. 293-312. Elsevier, 2019.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 807-814, 2010.
Juan-Manuel Pérez-Rúa, Moez Baccouche, and Stephane Pateux. Efficient progressive neural architecture search. arXiv preprint arXiv:1808; arXiv:1888.00391, 2018.
Hieu Pham, Melody Y Guan, Barret Zoph, Quoc V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. ICML, 2018
Ilija Radosavovic, Justin Johnson, Saining Xie, Wan-Yen Lo, and Piotr Dollár. On Network Design Spaces for Visual Recognition. In International Conference on Computer Vision, May 2019.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alex Kurakin. Large-scale evolution of image classifiers. arXiv preprint arXiv: 1000. 00041,, 2017.
David R. So, Chen Liang, and Quoe V. Le. The evolved transformer. In ICML, 2019.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, and Quoc V Le. Mnasnet: Platform-aware neural architecture search for mobile. arXiv preprint /807. /626, 2018.
Linnan Wang, Yiyang Zhao, You Jinnai, Yuandong Tian, and Rodrigo Fonseca. AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search. arXiv preprint arXiv:1933.11059, 2019.
Bernard L Welch. The generalization ofstudent's' problem when several different population variances are involved. Biometrika, 34(1/2):28-33 1947.
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. arXiv: 11/2.0822333333 [es], December 2018. URL abs /
arXiv: 1812.03443.
L. Xie and A. Yuille. Genetic cnn. IEEE International Conference Compuler Vision (ICCV), 2017.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. arXiv preprint arXiv: 19X.:0990400169 2019.
Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W Cohen. Breaking the softmax 2017.
bottleneck: A high-rank rnn language model. arXiv preprint
Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter, Nas- bench-101: Towards reproducible neural architecture search. arXiv preprint 2019.
Arber Zela, Aaron Klein, Stefan Falkner, and Frank Hutter. Towards automated deep learning: Efficient joint neural architecture and hyperparameter search. ICML AutoML Workshop, 2018.
Hongpeng Zhou, Minghao Yang, Jun Wang. and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. In ICML., 2019.
Barret Zoph and Quoc V. Le. Neural Architecture Search with Reinforcement Learning. International Conference Learning Representations (ICLR), Conference track, 2017.
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

---

Published as a conference paper at ICLR 2020
A METRICS TO EVALUATE NAS ALGORITHMS
A. KENDALL TAU METRIC
As correlation measure, we make use of the Kendall Tau (7) metric (Kendall 1938): number in the range [-1, 1] with the following properties:
-1: 1: Maximum disagreement. One ranking is the opposite of the other.
1: Maximum agreement. The two rankings are identical.
close O: A value close indicates the absence of correlation.
A.2 PROBABILITY SURPASS RANDOM SEARCH
As discussed in Section 3.2 the goal of NASBench is to search for CNN cell with to 7 nodes and 3 operations, resulting in total 423,624 architectures. Each architecture trained 3 times with different random initialization up 108 epochs on the CIFAR- 10 training set, and evaluated on the test split. Hence, the average test accuracy of these runs can be seen as the ground-truth performances. In our experiments, the best architecture's rank after n runs, and maximum rank Tmee equals to the total number of architectures, the probability that the best architecture discovered is better than randomly searched one given the same budget given by
this to rank the architectures, from 1 (highest accuracy) to 423,624. Given
p= (1 (r/Tmax)))*
(1)
We use this as a new metric to evaluate the search phase.
B NAS SEARCH SPACE REPRESENTATION
As discussed in the main paper, our starting point a neural search space for a neural architecture, as illustrated in Figure 5 A convolutional cell can be represented with a similar topological structures. Following common practice NAS (Zoph Le 2017). candidate architecture sampled from this space connects the input and the output nodes through sequence of intermediary ones. Each node is connected to others and has an operation attached
A way of representing this search space (Pham et al. 2018 Luo et al. 2018), depicted in Figure bJ)), is by using strings. Each character in the string indicates either the node ID that the current node is connected to, the operation selected for the current node. Operations include the identity, sigmoid, tanh and ReLU (Nair & Hinton 2010)).
Following the alternative way introduced in (Liu al. 2019b), make of vectorized represen- tation of these strings. More specifically, as illustrated by Figure a node ID, resp. an operation, encoded as vector of probabilities over all node IDs, resp. all operations. For instance, the connection between nodes i and is represented as y ((.)) (x) ooeo Poo(x), with O the set of all operations, and = sof tmax = exp(a.)/ Eoreo exp(a.)) the probability of each operation.
C NAS ALGORITHMS
Here, we discuss the three state-of-the-art NAS algorithms used in our experiments in detail, including their paraee-parsetters during the search phase. The current stale-of-the-arts NAS on CIFAR- is ProxylesNNAS (Cai et al. 2018b) with top-1 accuracy of 97.92. However, this algorithm inherits the sampler from ENAS and DARTS, but with different objective function, backbone model, and search space. In addition, the code is not publicly available, which precludes us from directly evaluating it.
C.I ENAS
adopts reinforcement learning sampling strategy that updated with the REINFORCE algorithm. The sampler is implemented two-layer LSTM Hochreiter & Schmidhuber (1997) and generates sequence of strings. In the training process, each candidate sampled by the ENAS controller is trained on individual mini-batch. At the end of each epoch, the controller samples new architectures
12

---

Published as a conference paper at ICLR 2020
(1-2) R
Operation
Node
@
@
Node to connect
0.2
Node
Node
0
Node
0
Output
p M
input
Node
(a) Search space
Node
2
(b) String representation
(c) Vector representation
Figure 5: Search space of NAS algorithms. Typically, the search space encoded as (a) directed acyclic graph, and an architecture can be represented as (b) string listing the node ID that each node connected to, or the operation ID employed by each node. (c) alternatively representation is list vectors a of size m(a++]]
2 OO), where n is the number nodes and is the set of all operations. Each vector, (6-3,, captures, via softmax, the probability po that operation is employed between node and j. Note that any node only takes one incoming edge, thus (b) and (c) represent the same search space and only differs in its formality.
that are evaluated on single batch of the validation dataset. After this, the controller is updated accordingly using these validation metrics. We refer the reader to (Pham et al. 2018) for details about the hyper--arameter settings.
C.2 DARTS
It vectorizes the aforementioned strings as discussed in Section and shown in Fig. (]c). The sampling process then parameterized by the vector a, which is optimized via gradient- descent in dual optimization scheme: The architecture is first trained while fixing a, and is then updated while the network fixed. This process repeated in an alternating manner. In the evaluation phase, DARTS samples the top-perf perpeeforming architecture by using the trained vector probability prior, i.e., the final model is not a soft average of all paths but one path in the DAG, which makes its evaluation identical to that of the other NAS algorithms. Note that as in the released code Liu et al. (2019)).
the same hyper-parameten
C.3 NAO
implements a gradient-descent algorithm, but instead of vectorizing the strings as in DARTS, makes use of variational auto-encoder (VAE) learn latent representation of the candidate architectures. Furthermore, it uses a performance predictor, which takes a latent vector as input to predict the corresponding architecture performance. In short, the search phase of NAO consists of first randomly sampling an initial pool of architectures and training them so as to obtain ranking. This ranking is then used train the encoder- encoder-predictor- predictor-dccode network. from which new candidates are sampled, and the process is repeated in an iterative manner. The best architecture is then taken as the top-1 in the NAO ranking. We directly use the code released by Luo et al. 2018).
C.4 BAYESNAS
Bayesian optimization was first introduced the neural architecture search field by Kandasamy et al. (2018) and Jin et al. (2019). We chose to evaluate BayesNAS (Zhou et al.) 2019) because it is more recent than Auto-Keras (Jin et al. 2019) and than the work of Kandasamy et al. (2018), and because these two works use different search spaces than DARTS, resulting in models with significantly worse performance than DARTS. BayesNAS adopts Bayesian optimization to prune the fully-commn collecccddeeeed DAG graph using the shared weights to obtain accuracy metrics. The search space follows that of DARTS (Liu et al.) (2019b) with minor modifications in connections, but exactly the same operations. Please (Zhou et al. 2019) for more details. Note that BayesNAS was only implemented in CNN
13

---

Published as a conference paper at ICLR 2020
space. We use the search and model code released by Zhou al. (2019) with training pipeline, since the authors did not release the training code.
C.5 EXPERIMENTAL SETUP
Following common practice in NAS, we make use of the word-level language modeling Penn Tree Bank (PTB) dataset (Marcus et al.) 1994b) and of the image classification CIFAR-I0 dataset (Krizhevsky al. 2009). For these datasets, the goals are, respectively, finding a recurrent cell that correctly predicts the next word given the input sequence, and finding convolutional cell that maximizes the classification accuracy. The quality of candidate then evaluated using the perplexity metric and top-1 accuracy, respectively.
In the evaluation phase, we always use the same model backbone and parameter initialization for all searched architectures, which ensures fairesss and reflects the empirical observation that the searched models are insensitive (accuracy variations less than 0.002 (Liu et al., 2019b) to initialization during evaluation. For our RNN comparisons, we follow the procedure used in (Liu et al. 2019b
Pham et al., 2018: Luo et al. 2018) for the final evaluation, consisting of keeping the connections found for the best architecture in the search phase but increasing the hidden state size (to 850 in practice), so as to increase capacity. Furthermore, when training an RNN architecture from scratch, follow (Yang al., 2017] Merity al., 2017) and first make the use of standard SGD to speed up training, and then change to average SGD to improve convergence. For all CNN architectures, we use RMSProp for fast optimization (Ying et al. 2019) and enable auxiliary head and cut-out (De & Taylor 2017) to boost the performance as in Liu et al. (011bb)
C.6 ADAPTATION TO REDUCED SEARCH SPACE
When changing reduced search spaces, we adapted the evaluated search algorithms to achieve the best performance. Below, we describe these modifications.
RNN reduced space
For DARTS, no changes are needed except modifying the number of nodes in the search space. For NAO, to mimic the behavior of the algorithm in the space of 12 nodes, randomly sample 20% of the possible architectures to define the initial candidate pool. We train the encoder- predictor-decoder network for 250 iterations every 50 epochs using the top-4 architectures in the NAO ranking. At each search iteration, we sample at most new architectures to added to the pool. The rest of the search logic remains unchanged.
For ENAS, we reduce the number of architectures sampled in one epoch to 20 and increase the number of batches to 10 for each architecture. All other typer-parameter are unchanged.
CNN reduced space
For DARTS, again, no changes are needed except modifying the number of nodes in the search space.
For NAO, since the topology of the NASBench space is very similar to the original search space, we kept most of the parameters unchanged, but only change the embedding size of the encoder proportionally to the number of nodes (12 x node 12).
For ENAS, we set the L.STM sampler size to 64 and keep the temperature as 5.0. The number of aggregation step of each sampler training is set to 10.
D SUPPLEMENTARY EXPERIMENTS
We provide additional experiments to support our claims.
D.1 INFLUENCE OF THE AMOUNT OF SHARING
Depending on the active connections in the DAG, different architectures are subject to different
amounts of weight sharing. In Figure (a), let consider the 3-node case, with node and node
14

---

Published as a conference paper at ICLR 2020
fixed and node 3 having node 1 as incoming node. In this scenario, the input node can be either directly node (i.e., the imput), or node I, or node In the first case, the only network parameters that the output of node 3 depends however, the output further depends on the parameters of node 1, and nodes and 2, respectively.
the weights of its own operation. In the second and third cases,
Yans!
Search space
shardd
(a) Search Space
(b) Impact of weight sharing
Figure 6: A toy search space to assess the influence weight sharing in RNN space, (a) Top: the reduced space. (a) Bottom: The amount of sharing depends on the activated path.
(b) Ranking obtained from weight sharing training, that best ranked architectures has weight matrix to share.
To study the influence of the amount of sharing the architecture ranking, we performed an experiment where we fixed the first two nodes and only searched for the third one. This represents a space of 12 architectures (3 possible connections to node 4 operations). We train them using the same setting in Section 4.3) The ranking of the 12 architectures shown in ( where color indicates the number of shared weight matrices, that is, matrices of nodes and 2 also used in the search for node 3. Note that the top-performing architectures do not share any weights and that the more weights are shared, the worse the architecture performs.
In CNN space, we conduct a similar experiment in NAS- Bench. With total node equals to we only permute the last node operation and comnection to one of the previous nodes. In short, we will have total 4 connection possibility and 3 operation choices, in total 12 architectures. We compute the Kendall Tau among the architectures with the same con- nection but different operations, and the results are reported in Table architectures decrease while the weight sharing matrices increase.
Table 5: Ranking disorder of weight sharing CNN.
of shared matrix
Kendall Tau
0.67.
0.33
-0.33
0.0
Clearly, the correlation of
D.2 RANDOM SAMPLING COMPARISON
As discussed before, the random policy (Liu al. 2019b) samples 8 architectures, and picks the best after training them for 300 epochs independently. seem contradictory that DARTS outperforms this ran- dom policy, but cannot surpass the much simpler one designed in our paper, which only randomly samples 10 architectures (1 per random seed), trains them to convergence and picks the best, However, the random policy in DARTS relies on the assumption that a model that performs well in the early training stage will re- main effective until the end of training. While this may sound intuitive, we observed a different picture with our reduced search space.
Random
Random
might
archilecture rank
16
20-
99
299
499
699
899
epoch
Figure Rank changes while training. Each line represents the evolution of the rank of single architecture. The mod- els are sorted based on their test perfor- mance after 1000 epochs, with the best- performing one at the top. The curves were averaged over 10 runs. They correspond to the experiment in Section 4.2. The verti- cal dashed lines indicate the epoch number where random sampling either by the random policy in Liu et al. (2019)), or by ours.
Since we obtained the ground-truth performance ranking, as discussed in Section 4.2 of the main paper, in Figure models' rank while training
we plot the evolution proceeds, based on the average validation perplexity over 10 runs. Clearly, there are significant variations during training: Good models in early stages drop lower in the ranking towards the end. As such, there a non-neglig chance that the random policy in DARTS
performed,
15

---

Published as a conference paper at ICLR 2020
Table 6: Comparison of
methods on NASBench-101 search space.
Search Space
NASDeach 101 CIFAR number nodes, total urchitecture choices, best: accuracy (8)
4 (91)
= (2,5K)
(64K)
(425K)
Best of
Method
Best
Micn
K-T
Mica
Sumpling monhods,
imnining
92.95
89.00
92.87
93.97
93.07
DARTS
91.54
1.93
91.71
93.63
91.12
1.86
93.92
92:21
93.02
93:02
FENET
91.55
1.89
93.21
92.51
1.51
93:90
91.76 = 1.26
92.98
92.29
1.25
93.98
93.98
Cloc shot merhods, train samyder ofter
optimicng
super-net
SPOS
91.14
1.47
94.24
0.441
91.55
1.76
93.72
0.314
90.56
1.03
92.20
0.214
89.85
3,80
91.84
0.105
94.24
FAIRNAS
39.08 1. 4.35
94.15
0.043
91.38
1.44
93.55
00,028
91.75
L. 2.20
94.47
0.221
91.10
1.84
93.55
0.232
94.47
picks a model whose performance will be sub-optimal. We therefore believe that our policy that simply samples one model and trains it until convergence yields more
fair baseline. Furthermore, the fact that we perform our comparison using 10 random seeds, for both approach and the NAS algorithms, vs single one in (Liu al. 2019b) makes our conclusions more reliable.
D.3 NASBENCH DETAILED RESULTS.
We provide additional evaluations on the NASBench dataset to benchmark the performance of the state-of-the-art NAS algorithms. In addition the three methods in the main paper, we re- implemented some recent algorithms. such as FBNet (Wu et al.) 2018), Single Path One Shot (SPOS) (Guo al. 2019), and FairNAS (Chu et al. 2019). Note that we removed the FBNet device look-up table and model latency from the objective function since the search for mobile model is not our primary goal. This also makes comparable with the other baselines.
To ensure fairness, after the search phase is completed, each method trains the top 1 architectures found by its policy from scratch to obtain ground- truth performance; we repeated all the experiments with 10 random seeds. We report the mean and best top I accuracy in 6 for number of nodes n E [4, 7], and the Kendall Tau (K-T) values for one-shot methods following Section 4.2 in the paper.
From the results, observe that: 1) Sampling-basse based NAS strategies always have better mean accuracy with lower standard deviation, meaning that they converge to a local minimum more easily but do not exploit the entire search space. 2) By contrast, one-shot methods explore more diverse solutions, thus having larger standard deviations but lower means, but are able to pick a better architecture than sampling-bon -based strategies (94.47 for FairNAS and 94.24 for SPOS, best of sampler based FBNet 93. 93.98). 3) ENAS constantly improves as the number of nodes increases. 4) FBNet constantly outperforms DARTS, considering the similarity, using Gumbel Softmax seems better choice. 5) The variance of these algorithms is large and sensitive to initialization. 6) Even one-shot algorithms cannot find the overall best architecture with accuracy 95.06.
16


Reviews:
[{"review_id": "ryx1A71lqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 studies an important problem, evaluating the performance of existing neural architecture search algorithms against a random sampling algorithm fairly. \n\nNeural architecture search usually involves two phases: model search and model tuning. In the search phase, best architectures after limited training are selected. In model tuning, the selected architectures are trained fully. However, it has been noticed that best architectures after limited training may not translate to globally best architectures. Although previous research has tried comparing to random sampling, such as Liu et al. 2019b, but the random architectures were not trained fully. The authors train random architectures fully before selecting the best one, which turns out to perform as well or better than the sophisticated neural architecture search methods. The paper also identifies that parameter sharing turns out to be a major reason why the sophisticated NAS methods do not really work well. \n\nThe insights are obviously important and valuable. The insight on parameter sharing is even a bit disheartening. Parameter sharing is the main reason why NAS can scale to very large domains. Without it, is NAS still practical or useful? On the other hand, it is a bit unsatisfactory that the paper does not provide or even suggest solutions to remedy the identified issues.\n\nAnother comment is it is a stretch to consider the evaluation done in the paper a new framework. It is simply a new baseline plus a new experiment design.\n\nAbout Equation (1) in Appendix A.2, it seems to simplify to p=(r/r_max)^n. Is the formula correct?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rklNiq1rqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 works studies the evaluation of search strategies for neural architecture search. It points out existing problems of the current evaluation scheme: (1) only compares the final result without testing the robustness under different random seeds; (2) lacking fair comparison with random baseline under different random seeds. The authors analyzed three popular NAS methods with weight sharing (ENAS, DARTS, NAO), and showed that they don't significantly improve upon random baseline on PTB and CIFAR-10. On a reduced search space of RNN and CNN (NASBench), they showed that the three methods fail to find the best performing architecture. Then they compared search with and without weight sharing and showed the correlation between architecture performance under the two conditions in a reduced search space, which indicates the weight sharing is a potential cause for the suboptimal performance.\n\nI recommend acceptance of the paper for the reasons below.\n\n(1) It pointed out some important issues in the evaluation of NAS methods: evaluating under different random seeds and fair comparison with random baseline.\n(2) The analysis is supported by experiments in the original search space and a reduced search space, which makes the result more convincing.\n(3) It proposed the weight sharing as a potential cause and supported the hypothesis with experiments in the reduced search space, although more experiments in a realistic search space are needed to make the conclusion more solid.\n\nWeakness:\n\n(1) The problem that the search space is over-optimized and constrained is not unnoticed before. For example, table 1 in (Liu et al, 2018) showed that the random search baseline performs not much worse than the DARTS (~0.53% difference), which is similar to the conclusions on CIFAR-10 presented in this work. \n(2) More recent works in NAS is already evaluating under multiple random seeds and performing fair comparison with random search baselines, for example, (So et al, 2019). There should be more discussions about such improvements in the rigorous evaluation of NAS. \n(3) The comparison between with and without weight sharing in section 4.3 is interesting, but there should be more support in a realistic search space, because the landscape could be very different. Otherwise, it is better to make clear the scope of the conclusion, for example, instead of \"in CNN space, the ranking disorder ...\", it is better to use \"in a reduced CNN space, ...\". \n\n\"Darts: Differentiable architecture search.\" Liu, Hanxiao, Karen Simonyan, and Yiming Yang.  ICLR, 2019\n\"The Evolved Transformer.\" David R. So, Chen Liang, and Quoc V. Le., International Conference on Machine Learning. 2019.\n\nTypos:\n\"based one their results on the downstream task.\" -> \"based on\"\n\"obtained an an accuracy\" -> \"obtained an accuracy\"\n\n====================================\n\nI have read the author response and would keep the same rating. The paper pointed out an important issue, but it has also been noticed before. The insight on weight sharing is interesting, although more experiments are needed to testify the claim over state-of-the-art NAS search space. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "rJx-uYwaFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 studies the effectiveness of several Neural Architecture Search (NAS) methods comparing it with that of random policy search. The paper concludes that none of these methods for a CNN (trained using CIFAR-10) and RNN model (trained using PTB) are statistically significantly better than the random search. The authors suggest that this is due to the weight sharing used by the NAS algorithms to accelerate the network training. \n\nThis paper is written well with a good discussion of the problem. The problem considered is important and authors have raised the effectiveness of NAS methods correctly. Before this paper, Li and Talwalkar, “Random Search and Reproducibility for Neural Architecture Search” have also compared some of the NAS methods with random search and reported similar concerns. \nIn this sense, the paper is not novel although I agree this paper has added an additional insight that “weight sharing” is the culprit.\n\nI have two concerns about the methodology used in this paper:\n\n(1)\tThe search space has been greatly, just 32 possible architectures. It is well known that in a small search space, difference between the performance of random search and any other systematic search algorithm is quite small. Only when the space gets larger, the power of systematic search starts to show up. Although, I completely understand the authors’ limitation of not having a ground truth for a large search space (infeasible due to a huge computational requirement), but without this, the claim of this paper is weak.\n\n(2)\tSecondly, among the NAS methods considered, I missed the whole class of methods based on Bayesian optimization. There are many such work, but I am listing just two of them here: Jin et al. (2018), “AUTO-KERAS: EFFICIENT NEURAL ARCHITECTURE SEARCH WITH NETWORK MORPHISM” and Kandasamy et al. (2018), “Neural Architecture Search with Bayesian Optimisation and Optimal Transport”. It would be useful to have them in the list of NAS methods considered here. \n\nPost Rebuttal:\nI have read the rebuttal. I appreciate the authors 'prompt comparison of their method with Bayesian NAS. However, I still think that using a reduced search space, it is not appropriate to compare NAS methods with random search. Moreover, all the claims are only empirical and more experimental evidence needs to be provided to reject the current NAS methods.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is one of several recent parallel papers that pointed out issues with neural architecture search (NAS). It shows that several NAS algorithms do not perform better than random search and finds that their weight sharing mechanism leads to low correlations of the search performance and final evaluation performance. Code is available to ensure reproducibility of the work.

After the discussion period, all reviewers are mildly in favour of accepting the paper. 

My recommendation is therefore to accept the paper. The paper's results may in part appear to be old news by now, but they were not when the paper first appeared on arXiv (in parallel to Li & Talwalkar, so similarities to that work should not be held against this paper).
Decision: Accept (Poster)