Improving Random-Sampling Neural Architecture Search by Evolving the Proxy Search Space
Authors: Yuhong Li
Cong Hao
Xiaofan Zhang
Jinjun Xiong
Wen-mei Hwu
Deming Chen
Venue:  (2021)
Keywords: Neural Architecture Search
AutoML
Computer Vision

Abstract: Random-sampling Neural Architecture Search (RandomNAS) has recently become a prevailing NAS approach because of its search efficiency and simplicity. There are two main steps in RandomNAS: the training step that randomly samples the weight-sharing architectures from a supernet and iteratively updates their weights, and the search step that ranks architectures by their respective validation performance. Key to both steps is the assumption of a high correlation between estimated performance(i.e., accuracy) for weight-sharing architectures and their respective achievable accuracy (i.e., ground truth) when trained from scratch. We examine such a phenomenon via NASBench-201, whose ground truth is known for its entire NAS search space. We observe that existing RandomNAS can rank a set of architectures uniformly sampled from the entire global search space(GS), that correlates well with its ground-truth ranking. However, if we only focus on the top-performing architectures (such as top 20\% according to the ground truth) in the GS, such a correlation drops dramatically.  This raises the question of whether we can find an effective proxy search space (PS) that is only a small subset of GS to dramatically improve RandomNAS’s search efficiency while at the same time keeping a good correlation for the top-performing architectures. This paper proposes a new RandomNAS-based approach called EPS (Evolving the Proxy Search Space) to address this problem. We show that, when applied to NASBench-201, EPS can achieve near-optimal NAS performance and beat all existing state-of-the-art. When applied to different-variants of DARTS-like search spaces for tasks such as image classification and natural language processing, EPS is able to robustly achieve superior performance with shorter or similar search time compared to some leading NAS works. The code is available at https://github.com/IcLr2020SuBmIsSiOn/EPS

Under review as a conference paper at ICLR 2021
IMPROVING RANDOM-SAMPLING NEURAL ARCHI- TECTURE SEARCH BY EVOLVING THE PROXY SEARCH SPACE
Anonymous authors Paper under double-blind review
ABSTRACT
Random-sampling Neural Architecture Search (RandomNAS) has recently be- come prevailing NAS approach because of its search efficiency and simplicity. There are two main steps in RandomNAS: the training step that randomly sam- ples the weight-sharing architectures from supernet and iteratively updates their weights, and the search step that ranks architectures by their respective validation performance. Key to both steps is the assumption of high correlation between estimated performance(i.e. accuracy) for weight-sharing architectures and their respective achievable accuracy (i.e., ground truth) when trained from scratch. We examine such a phenomenon via NASBench-201, whose ground truth is known for its entire NAS search space. We observe that existing RandomNAS can rank a set of architectures uniformly sampled from the entire global search space(GS), that correlates well with its ground-truth ranking. However, we only focus the top-performing architectures (such as top 20% according to the ground truth) in the GS, such a correlation drops dramatically. This raises the question of whether we can find an effective proxy search space (PS) that is only small subset of GS to dramatically improve RandomNAS's search efficiency while at the same time keeping a good correlation for the nop-performing architectures. This paper proposes a new RandomNAS- -aaaee approach called EPS (Evolving the Proxy Search Space) to address this problem. We show that, when applied to NASBench-201, EPS can achieve near-optimal NAS performance and surpass all existing state-of-the-arr When applied to different-variant of DARTS-like search spaces for tasks such as image classification and natural language process- ing, EPS is able to robustly achieve superior performance with shorter or simi- lar search time compared to some leading NAS works. Our code is available at http:///gitu...oom/////2222/////
INTRODUCTION
Neural architecture search (NAS) has been successfully utilized to discover novel DNN architec- tures in complex search spaces and outperformed human-crafted designs. Early NAS works like NASNet (Zoph al. (2018) and AmoebaNet (Real et al. (2019)) used reinforeement learning evolutionary algorithms to search for the DNN architectures by training substantial amount of inde- pendent network architectures from scratch. Although these searched architectures can deliver high accuracy, they come with tremendous computation and time costs. Therefore, researchers gradually shift their focuses to one-shot NAS, which is more efficient and can deliver satisfying outputs within a few GPU-days. There are two main types of one-shot NAS. One is the differentiable NAS (DNAS), such as Liu al. (2019b): Cai et al. (0188): y); Xie et al. (0188:: Dong & Yang (019b); Xu et al. 2019); Chen et al. (2019a), which uses a continuous relaxation of the architecture representations and intro- duces architecture parameters to distinguish the architectures. The other is Random- Random-Sammling Sampling NAS (RandomNAS), such as Li & Talwalkar (2019); Chen et al. (2019b); Zhang al. (2020); Guo et al. 20019; Bender (2019); Yang et al. (2020). RandomNAS approaches typically have two phases: (1) Training phase: each iteration, RandomNAS randomly samples one architecture
Cai
set of archi- tectures and updates their shared weights in the supernet; (2) Search phase: after supernet training, the desired architectures selected based on their performance ranking the validation dataset

---

Under review as a conference paper at ICLR 2021
using inherited weights from the supernet, which is called weight-sharing performance. Finally, the selected architectures will be retrained from scratch to get their actual (retrained) performance for deployment. Compared to DNAS, RandomNAS usually consumes less GPU memories by par- tially updating the weights. Also, it generates multiple target architectures, while DNAS generally retrieves single architecture based on the maxima of the representation distribution. There are, however, two major drawbacks preventing RandomNAS from achieving higher search efficiency. First, although RandomNAS achieves a promising ranking correlation between the weight-sharing estimation and the retrained performance over all architecture candidates, it delivers a low ranking correlation among "good" architectures (e.g.. space) that researchers are more interested in. Second, by following the RandomNAS approach, smaller network architectures (with less parameters) tend to converge faster than the larger ones, which significantly degrades the ranking correlation.
architectures among the search
To address the drawbacks of RandomNAS, we first introduce a proxy search space(PS): a subset of the architectures flexibly sampled from the global search space(GS) to study the features of Ran- domNAS, We then evaluate the RandomNAS with the proposed PS using the NASBench-201 bench- (1) When uniformly sampling a PS from a global search space, RandomNAS in the PS will maintain a similar ranking correlation with the one in the GS, even the size of the PS is extremely small (e.g. 16 architectures). (2) If the PS consists of the "good" architectures, the PS-hased search can significantly improve the ranking correlation among the PS compared to the RandomNAS trained in GS and validated in PS.
mark (Dong & Yang ) and notice two interesting phenomena:
Based on these observations, the PS constructed from "good" architectures can help overcome the first drawback of RandomNAS search for more promising architectures. So, the remaining ques- tion is how to find a suitable PS containing sufficient "better" architectures? In this paper, we consider it natural selection problem and solve by the evolutionary algorithm. The architectures in the initial PS are iteratively evolved and gradually upgraded, while the average ranking of the architectures in the PS is improved. Meanwhile, it also helps improve the ranking correlation of the PS. We propose new RandomNAS approach, named Evolving the Proxy Search Space (EPS). EPS runs in three stages iteratively: Training the supernet by randomly sampling from a PS; Vali- dating the architectures among the PS on a subset of the validation dataset in the training interval; Evolving the PS by a tournament selection evolutionary algorithm with the aging mechanism. In this way, EPS gradually includes more high quality architectures in the proxy search space, while improves its ranking correlation. To solve the second issue in which smaller architectures converge faster than larger ones, we introduce a simple sizel--ize-based regularization in the final selection stage. Our result on NASBench-201 shows 17. 17.2% improvement in ranking correlation measured by Spearman's p by adding the regularization on NAS
In the experiments, we demonstrate that EPS delivers a near-optimal performance on NASBench- 201. We also extend the EPS on DARTS search space. By using the 5-search-runs measurement, EPS demonstrates robust search ability compared with the previous works in 8 hours search time with little Syper-parameters fine-tuning effort. Also, EPS is evaluated in 4 DARTS sub search space (Zela et al. (2019)) using 3 datasets, on which DARTS easily fails. EPS surpasses the DARTS- ADA and DARTS-ES on most cases and can often find the global state-of-the-art architectures. EPS also shows a high performance on language modeling task which consolidates the generalization ability and robustness of EPS.
RANDOMNAS ON NASBENCH-201
In this section, we present two major drawbacks we found in the existing RandomNAS methods and investigate the ranking correlation using a proxy search space. Proxy search space (PS) is subset of the global search space (GS) and the RandomNAS is more flexible to be analyzed by training in the PS including different architectures from the GS. We run the following experiments on NASBench- 201, which is unified and fair benchmark designed for NAS algorithm evaluation and contains the ground-trum -ouun architecture accuracy on three datasets. The GS of NASBench-20 contains 15.625 architectures and they are constructed by 4 nodes and 5 associated operation options. (Please refer to Fig. in Dong & Yangl (2020) for details.)
2

---

Under review as a conference paper at ICLR 2021
2.1
RANKING CORRELATION IN DIFFERENT PROXY SEARCH SPACES
GLO0 top 100N
1-00000000
Preny
1-000
0.5-
PrEry (1p-524
0.2
-02
0.0
235
122
2049
0102
15625 (lobbl))
10000
20006
30000
4EC07
32990
83300
73000
50000
Procy
Aaradarn
(a)
(b)
Figure 1: (a) The comparison of the Spearman's p across 10 PS and the GS. The architectures in the PS are uniformly sampled from the GS. (b) Six different scenarios of Spearman's 's p through the RandomNAS training. "Global top-x%" stands for the RandomNAS trained the GS and evaluated by architectures in the the top-x% of the GS. "Proxy top-x%" stands for the RandomNAS trained and evaluated in a PS which consists of architectures the top-x% of the GS.
First, we want study whether RandomNAS in PS with architectures uniformly sampled from the GS can achieve a higher ranking performance than the RandomNAS in the GS. We design an exper- iment to train the RandomNAS in the PS with 10 different sizes from 2 to 2 independently and compare the results with the RandomNAS in the GS. The experiment for each scenario is conducted 10 times with different random seeds (10x 11 total runs). We calculate the Spearman's 's p ranking correlation between the RandomNAS validation loss and the ground-truth test accuracy with 16 architectures randomly sampled from each search space. Fig. [a shows the raw data with & one standard deviation error bar for different proxy search space. The ranking correlations are close and there no significant difference among them through statistical testing with a Pearson coefficient as -0.10. We observe that when the architectures are randomly sampled from the global search space, RandomNAS in PS maintains similar global-ranking performance with RandomNAS in the GS.
Second, although RandomNAS trained in the GS achieves 0.783 Spearman's when validating in the GS, shows a poor Spearman's s p (0.347) in top-20% of the GS (which consists of top-20%- performing architectures ranked by ground-truth accuracy from the GS). Hence, we' '''d like to see if RandomNAS in a PS can have a better ranking performance. Fig. shows another six different scenarios, demonstrating the ranking correlation differences when sampling from GS PS. The first three are: the RandomNAS trained in the GS with Spearman's 's calculated for 64 architec- randomly samples from top- 100% (global), top-60%, top-20% in the GS independently. The other three are from PS: the RandomNAS trained in a PS with 256 architectures sampled from top- 100%, top-60%, top-20% the from GS and Spearman's 's p calculated with 64 architectures randomly sampled from the same PS. It shows that the RandomNAS in the GS achieves 0.783 (the blue line) Spearman's p with the validation architectures sampled from global. However, it only achieves 0.347 (purple) with the validation architectures sampled from top-20%. On the contrast, the RandomNAS the shows that its Spearman's 's a curve under PS top-100% (orange, 0.785) is similar with the GS top- 100%, which is consistent with the Fig. Tb results. However, the Spearman's 's curve of the PS top-60% (red, 0.687) and top-20% (brown, 0.607) both surpass the GS top-60% (green, 0.530) and GS top-20%. We suspect that such an improvement may be due to the better constructed PS sampled from top performing GS, an insight we will take advantage of in designing our new solution below.
2.2 SMALL ARCHITECTURES GAIN LOWER LOSS
We observe another drawback of RandomNAS in that smaller architectures inside the supernet con- verge faster and tend to gain lower validation loss than the larger in the early training phase.
3

---

Under review as a conference paper at ICLR 2021
Pvakutedd archs
Parato-frrtt
0.40
0.35
1.8
1.6
0.25
1.4
0.20
10000
20000
30000
su000
Figure 2: Va)iidatoi losses vs. sizes for 4000 architectures after RandomNAS training. (b)
Pareto-from front architectures' average sizes via RandomNAS training.
shows the validation losses of 4000 architectures from RandomNAS in the GS after training. Although the architectures with model size of 1.05Mb achieves higher accuracy (queried from the ground truth in NASBench201), the Pareto front (shown orange dots) only reaches the 0.83Mb architecture. One possible explanation is that the light- operations converge faster. Fig. 2b shows the average size of the validation Pareto front among 320 architectures in each validation interval. We can see that the average sizes of the Pareto-front architectures are small the early search stage and will increase after more iterations, meaning that the larger architectures gradually begin to converge.
Fig. 2a
OUR METHOD
Motivated by the observations in 2.1 we propose simple yet effective random sampling approach, called EPS, to iteratively improve the architecture quality within the proxy search space. Our pro- posed solution can distinguish the "better" architec- tures with higher ranking correlation compared to the existing solutions using global search. Algo- rithm showss the overall flow EPS.
Algorithm 1: EPS
Initialize a supernct
Initialize empty architecture population queue, Q_pop Initialize an empty history
1, 2.... new www.atttcctueeee +-
RamdonlnniAcchheespernnt
EnqueeeeQ new new_archhitecuure)
(I) T iteer:: the number of iterations for supernet training. (2) I_al:: val- idation interval.
Main dlper-parameee
sample_set et RandomSamplel Q_pop, S.
for = 1, ................................ jiter
architecture RandomSamplec sample_set,
(3) P: maximum population size, a proxy search space. (4) S: sample size (the number of sampled architectures from population). (5) M: the number of mutated ar- chitectures. The ablation study on the search hyper- parameters will be discussed in Section
where the population
TrainOneBBachssppeerre. architecture) if % I_val = then for -,, do architecture + sample_set [k] vol_loss ValDnssanceeeeperett,, architecture)
architecture.fos val_loss end sample_set. archstecture.loee ascending order
Overall Flow.
EPS performs three major stages iteratively, as train- ing, validation and evolving, followed by final ar- chitecture selection and retraining. At the begin- ning, we build a supernet which contains all pos- sible architectures in the search space and initial- ize Popop and sample_set, RandomInitArch uni- formly select architecture from the GS, and then the architecture is enqueued into the Q_pop. Q_pop the proxy search space and sample_see set is ran- domly sampled from __pop for the tournament se- lection. (1) Training. The supernet is trained by
history.appente sample____eee for 1.2... do
new www.aitchhttureecco
Mutate( secll____ekk)))
Enqucual Q_pop, new.architecture
Dequeuel Q_pop)
sample set + RandomSampled Q_pop,
end
end
orchitectures
AcchntemneScccctoothisttoog.
4

---

Under review as a conference paper at ICLR 2021
total of T iter iterations. In each iteration, one architecture is sampled from the sample set and its weights are updated in the weight-sharing supernet by gradient descent. (2) Validation. Every I_val iterations of training, the architectures inside the sample_ set will be evaluated quentially. In each validation iteration, one architecture is evaluated on a batch of the randomly sampled validation data, and its validation loss is recorded. We validate the architecture gle batch instead of the whole validation dataset to find trade-off between the search time and completeness of validation. (3) Evolving. The architecture inside sample set are sorted in as- cending order according to their latest loss values, and the top-M architectures are mutated and en en-queued. Meanwhile, removes M oldest architecture from Q_pop. The mutation operation is described in Appendix B (4) Selection. After supernet training, we revisit the history of evo- lution and select all the "winner" architectures which get the lowest loss in the Q_rop in the each of last 7 validation intervals. However, if T is large, it still remains numerous number of "winners". Based on the observation from Section 2.2 we propose a simple size regularization: architecture. = architecture.loss + ar Beaseterchiteee waasetterchseeetree/mmes
sin-
maz_ maz_sizell is the max- imum architecture size in the global search space. The regularization imposes a penalty on small architectures, and the experiment results in Section 4
shows the significant improvement from the regularization. By adding the regularization, we select the one with the lowest regularized loss as the ideal architecture from winners.
4 ABLATION STUDY ON NASBENCH-201
We first apply EPS on NASBench-201 (Dong & Yang (2020) for ablation study. Fol- lowing the NASBench-201 settings, we con- struct supernet contains the same searchable cells. The number of iterations for training is T iter 80000. The main typer-parametert explored are the maximum population size P E (64, 128, 256), the sample size S E {32, 64). the mutation number M E {1, 4}, and the val- idation interval L_val selection, we set T = 10000 mod/ vvll. In the first round, the "winner" architectures which get the lowest loss in each of the last T validation interval are selected. If a "winner" dominates several validation intervals, its last loss will be adopted as the criterion. In the second round, the size regu- larization is added to all the "winner" architectures and we select the one with the lowest regularized loss.
Table 1: Comparison between the EPS, None- aging EA and RSPS on NASBench-201 validation dataset.
Setting woo SR w. SR 91.50=0.07
Non-aging
RSPS 89.64220.6
900000010
85.61
85.71+2211
10.00::..08
{50, 100, 2003. The number of total settings we explore is 36. For the
Size regularization. We use the iiidation-training split by NASBench-200 and analyze a and 3 in the size regularization (defined in Sec. 3). We compare the ranking correlation between the architecture's regularized loss and the validation accuracy in the final validation interval of the 36 settings. Each setting runs five times. The average Spearman's 's (in 36 x 5 runs) controlled by and B is shown in Fig. 3a We explore the a E [0. 4] and 3 E [0, 8] with the step 0.1. The average Spearman's 's p reaches 0.796 when a 1.4 and 33 = 5.2. Compared to the original Spearman's p 0.624, it gains 0. 0.1 improvement with the size regularization.
Search results. By adding the regularization, the setting (P- 256, S = 64, M = I, 50} achieves the best average validation accuracy of five found architectures. The detailed results of the 36 settings are in the Table 16 We compare the EPS with the RandomNAS (RSPS) and non-aging RandomNAS follows the same training settings as the EPS and evaluates 4000 architectures on all the validation data after training. Since the RandomNAS in the benchmark used 256-size data batch for validation of each architecture and only evaluated 100 architectures (please refer to Appendix B. Dong & Yang) (2020). our RandomNAS results higher. EPS surpasses the RandomNAS by large margin. Our experiment results support the idea that by properly evolving the proxy search space, it can gain a better performance compared to the global RandomNAS, Also, size regularization (SR) alleviates the slower convergence issue of larger architectures and shows the improvements on both EPS and RSPS. For the non-aging EA, architectures with the highest running loss removed out of Pop instead of the oldest ones. The results show that the non-aging EA is trapped by some poor-perfonee perforrrfem architectures. The underline reasons are: (1) A young architecture with high loss can be removed before well trained;
evolutionary algorithm (EA) in Table T
5

---

Under review as a conference paper at ICLR 2021
0.9
ranking
Spearman-A
0.78
0.8
0.76
0.74
0.72
0.70
0.5
0.68
0.4
0.3
Beta
10000 20000 30000 40000 50000 50000 70000
80000
Iteratons
(a)
(b)
Figure 3: (a) The average ranking correlation of EPS with size regularization NASBench-201 with a (y-axis) and / (x-axis). (b) Average ranking and Spearman's p of EPS's proxy search space when training.
(2) An aged architecture survives in the population when it performs well in the early stage and produces many mutations, which may dominate the population and mislead the search direction. We also compare EPS with other state-of-the-art NAS algorithms Table It shows that EPS delivers near-optimal results and surpasses NAS works referred in the original Benchmark regarding test accuracy on CIFAR-I0 and generalized test accuracy on CIFAR-IO0 and Imagenet-16. We also plot the average ranking of the proxy search space(population) and the Spearman's 's p of the population in Fig. 35 which shows that EPS successfully improve the average ranking and correlation Spearman's P when training.
Table Test accuracy comparisons between EPS and other state-of of-the--rt art NAS works reduplicated in the NASBench-201 paper Li & Talwalkar (2019); Liu et al. (2019b); Dong & Yangl (2019b a); Peng et al. 22019. Our results on three different datasets are respectively listed in the second block.
Method
Search cost hours)
Test ascumicy(S)
CIFAR-IO
CIFAR-100
Imagenet
RSPS
2.2
84.07:33.61
38.3344.34
26,2843.009
DARTS-VI
3.2
54.30:100.00
13.61:10.00
16.32:20.00
V2
54.30.10.00
16.32.10.00
GDAS
8.8
93.61-10.099
70.61-10.26
41.71:10.98
9.5
87.64440000
56.8777.777
32.52:40.21
ENAS
3.9
53,89-+0.58
15.61=00.00
14.84++2.10
GPS
1.8
94.34:1-0.04
73.03 0.33
46.25:10.29
Optimal
94.37
73.49
41.31
EXPERIMENTS ON DARTS SEARCH SPACE AND ITS VARIANTS
To further illustrate the generalizability of the DARTS search space and its variants without fine- tuning effort. Following the previous works, we build the network by stacking searchable cells, which contain N nodes as a directed acyclic graph. We first ap- ply EPS in the DARTS image classifica- tion search space and different DARTS sub search spaces proposed by Zela et al. (2019). Then extend the EPS DARTS language modeling search space, which is completely different from computer vision tasks.
EPS, we also evaluate
Table 3: Comparisons between EPS and Liu al.
(0019 Xu et al. (2019) via 5 search runs on CIFAR- 10. architectures reproduced by the work (Xu
et a 2019)).
Method
Runs
Avg. emi(%)
#1
#2
#3
84
DARTSVI
3.07.10.13
DARTSV2*
3.11
2.68
2.77
3.14
3.06
2.95::0.19
PC-DARTS
2.67
2.57
2.75
2.64
2.67-00.06
EPS
2.52
2.67
2.79
2.61
2.62
2.64:1.0099

---

Under review as a conference paper at ICLR 2021
5.1 DARTS IMAGE CLASSIFICATION SEARCH SPACE
We the consistent hyper- parerretreeterss settings from the NASBench-200 and transfer to the DARTS image search space. Utilizing the random sampling strategy, EPS directly searches on a supernet with 20 cells and 16 number of initial channels with less than 8GB GPU memories consumption. We follow the PC-DARTS evaluations of the searched architectures in five independent search runs, and the results are shown in Table 3 Among the runs,
able achieve the lowest average test error compared to DARTS and PC-DARTS, In addition, we make an extensive comparison to more recent NAS works on CIFAR-10 using the best network discovered by EPS within the runs. Also, we do the search follow the same settings on CIFAR-100 100, and the results are shown in Table shows that on CIFAR- 10/100, EPS is on par with the recent NAS works and is able to find state-of-the-art architectures.
We design another experiment to compare the EPS to RandomNAS on DARTS search space. The experiment conducted with cells and 16 number of initial chan-
R510
nels for both search and validation. We randomly sam- ple 27 architectures from the last validation interval (after 80,000 training iterations) for EPS. We train the archi- tectures 3 times independently follow the DARTS valida- tion settings. Furthermore, the Spearman's p between the EPS(with size regularization) loss and the ground truth is provided. Follow the same EPS training settings, train a global RandomNAS, and we show both Spearman's in Fig. 4 The randomly sampled 10 architectures aver- age accuracy is plotted by the red line (95.15%). Two ob- servations are made: 1) The architectures sampled from the final proxy search space surpass the random sampling baseline by large margin (the average accuracy of sam- ples 95.54% man's 's p while RandomNAS performs worse (0.41) at dis- tinguishing the difference between them. Note that due to the computational consumption, we could only afford a single repetition for the experiment.
Exmmario aaakin
95.0
95.2
95.4
95.5
55.8
50.0
59.2
Groundraath acouracy755
Figure 4: Rankings and ground-truth accuracy of searched architectures from EPS and RandomNAS(RS) on DARTS search space. P calculated by estimated ranking and ground-truth- accuracy ranking(descending). The red line is the average accuracy of random samples.
95.15%). 2) EPS delivers 0.68 Spear-
5.2 DARTS IMAGE CLASSIFICATION SUB SEARCH SPACES
In the work Zela et al. 2019) it proposed four sub search spaces from DARTS where original DARTS fails. The four search spaces are: S1: A search space contains the most confident opera- tions DARTS predicted each edge. S2: search space contains (3x3 SepCona, SkipConnect) on each edge. S3: A search space contains (3 x 3 SepCone, SkipConnect, N None} } on each edge.
Table 4: Comparison with the saate-of-the-aas methods (Peng et al. (2019) Liu al. (2019b) Dong
& Yangl (2019b); Xie et al. Talwalkar 2019 Yang et al. (2020) Zhang 2020 CIFAR R- 10/- 100. (Search time may be
(0088); Xu et al.] (0019; Zela et al. 2 Lu et al. (2019) Li &
varied using different GPUs.)
Test Em.1%)
Params (M)
Scarch cost (GPU days)
Scarch
Method
CIFAR-10
CIFAR-100
ENAS
2.89
18.91
4.6
0.45
RL
DARTSVI
3.00:0.14
3.3
1.5
DARTSV2
2.76=0.09
17.54*
3.3
GDAS
2,82
18.13
2.5
0.17
2.8
PC-DARTS
2.57=10.17
3.6
0.1
R-DARTS
2.95-0.21
18.01110.26
NSGANet
2.75
3.3
EA
RSPS
2.71
17.63
4.3
0.7
RS
CARS
2.62
3.6
RS&EA
RS-NSAS
2.6442.50)
17.56(16.85)
3.4
0.7
RS
0.0024000022441
(7.09:00161166000
3.5/3.6
RSKEA
7

---

Under review as a conference paper at ICLR 2021
Table 5: Comparison with the Liu al.
(2019b).
Zela et al. 2019 in DARTS sub search spaces
Setting
RSPS
DARIS
DARTS-ES
DARIS-ADA
EPS
3.17:0.13
4.66=0.71
5.05
3,03:0088
2.4
S2
3.46:-0.115
4.42=00.0
3,41
0,59
3.21-:0.066
CIFAR-IO
2.92:10.04
4.12:10.85
3.7111.114
2.99100.44
2.61::0.05
89.39-10.84
6.95:10118
4.17400.11
3.89100.77
3.82:10.15
SI
25.81=0.399
29.93400.41
28.90=0881
24.440081
13.85
22.88-00.16
28.75=+0.92
24.68=1.43
26.88+1.111
21.92-40.27
CIFAR-100
24.58=0061
29.01+:0.24
1.79
24.55:+0.63
22.38110.61
$4
30.01 1.552
24.77411.51
23.90-2001
13.66.0.09
23,93
2.64:00099
9,86=55.0
2.0000099
2.59:00:77
2.99
SVIIN
S2
2.57.10.04
3.69:10.12
2.6810.118
2.79:10.22
2.56.1..00
2.89.1..09
4.00=11001
2.78.10.29
2.58:10.07
2.53
3,42:00.4
2.90=:0.02
2.55
2.52::0,06
2.78:10.11
S4: A search space contains (3 x 3 SepCome, Noise) on each edge. Also, we noticed that Ran- domNAS tend to fail the S4 which suggests the method is difficult to distinguishes the Noise operation from 3 x 3 SepCone.
Here, we use similar settings for the EPS. We the DARTS maximum architecture's size as mar_size for the size regularization and set the size for Noise simply as negative 3 x 3 SepConv size since disrupts the information on its edge. Also, we notice that None operation as placeholder for the DNAS training and not in the final architecture. Thus, S3 is the same as S2 for EPS. The results are shown in Table For each setting, we report the 3 found architectures mean and std follow Table 6 in ZZela et al. (2019). EPS delivers better performance on the most of them. Even in the S4 where RandomNAS fragile, EPS still performs robustly and achieves the better performance on 2 settings out of three compared to DARTS- EPS even find an architectures on CIFAR- 10, S3 with 2.05 testing error, which is the state-of-the-ard the whole search space (In Table 13#1).
5.3 DARTS PTB SEARCH SPACE
We also evaluate EPS on the Penn Treebank (PTB) dataset, which targets natural language processing tasks and is completely different from computer vision tasks. The performance evaluation usually uses the perplexity score, the lower, the better. We use the DARTS PTB search space for the recurrent cells. During the recurrent cell search, the hidden and embed- ding sizes are both set to be 850, and the hyper- parameters settings tasks. Please refer to the Appendix [B.4 for the details. Since operations in the search space weight-free, we use simple selection strategy by training the last 10000 iteration's 's "winner" architectures for two epochs and evaluate the top-5 architectures for 20 epochs. So the training and selection take 8+4 hours (0.5 GPU day). After the search, we use the same settings as in DARTS train the best networks for 3600 epochs. The best model discovered by EPS achieves a validation perplexity of 58.4 and a test perplexity of 56.27, which is on a par with the state-of-the-ard approaches. The full comparisons are shown in Table
Table 6: Comparison with other statc-of-the-art methods PTB.
Methed
Porpiexity
Search cost (GPU days)
Scarch method
Valid
Test
ENAS
60.8
58.6
0.5
RL
DARTS-VI
60.2
0.5
DARTS-V2
58.1
55.7
|
G
GDAS
59.8
57.5
0.4
G
G-NSAS
59.74
57.24
0.5
G
similar to the previous
RSPS
57.8
55.5
0.25
RS
RS-NSAS
59.22
56.84
0.62
RS
EPS
58.4
36.27
0.5
RS&EA
6 CONCLUSION
We showed that RandomNAS had performed poorly in ranking good architectures and suffered from the lower validation loss for small architectures. Based on the proxy search space, we observed the ranking correlation between the prediction and the ground truth among good architectures could be improved if using a proxy search space consists of good architectures. Hence, we proposed an efficient way to Evolve the Proxy Search Space (EPS). We also designed simple size regularization to help RandomNAS- based algorithm jump out the small architecture traps. In the NASBench- 201 experiments, EPS delivered near-optimal solution and surpassed the existing methods. In the
8

---

Under review as a conference paper at ICLR 2021
extensive experiments DARTS search spaces and its variants, EPS outperformed was tied with the majority of recent NAS works. We believe such observations and insights as presented this paper can be useful to the community for the future NAS research with better interpretability.
REFERENCES
Gabriel Bender. Understanding and simplifying one-shot architecture search. 2019.
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understand- ing and simplifying one-shot architecture search. International Conference on Machine Learn- ing. pp. 550-559, 2018.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint 18Xiv:/8/222 /8/.:00/2..0,,, 2018.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. arXiv preprint arXiv: 097911, 2019.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Confer- ence on Computer Vision, pp. 1294-1303, 2019a.
Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun. Detnas: Backbone search for object detection. In Advances in Neural Information Processing Systems, pp. 6638-6648, 2019b.
Xuanyi Dong and Yi Yang. One-shot neural architecture search via self-evaluated template network. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3681-3690, 2019a.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In Proceed- ings the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 1761- 1770, 2019b.
Xuanyi Dong and Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.00326 2020.
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-sho shot neural architecture search with uniform sampling. arXiv preprint arXiv:1904.004200 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv: arXiv:1902.000 1902.0768, 2019.
Chenxi Liu, Liang- Chich Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei- Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 82-92, 2019a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In Proc. of ICLR, 2019b.
Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf. Nsga-net: neural architecture search using multi-objective genetic algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 419-427, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Devito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. Curran Associates, Inc., 2019. URL httpp:/paperrs http:/ppapprs...uuipsppss cc/paper/ 9015 111--yytorc--- an an--mperatiie--tytae high www.ohhheeeeoaeeeeeeeeeeeeeeeeee deepaanneedeee---eeee Learepp-earniin---- library. pdf

---

Under review as a conference paper at ICLR 2021
Junran Peng, Ming Sun, ZHAO-XIANG XIANG ZHANG, Tieniu Tan, and Junjie Yan. Efficient neural architecture transformation search in channel-level for object detection. In Advances in Neural Information Processing Systems, pp. 14313-14322, 2019.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proc. of AAAI, 2019.
Tonmoy Saikia, Yassine Marrakchi, Arber Zela, Frank Hutter, and Thomas Brox. Autodispnet: Improving disparity estimation with automl. In Proceedings of the IEEE International Conference Computer Vision, pp. 1812-1823, 2019.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zhigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2818-2826, 2016.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arXiv:1812.009966 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 differentiable architecture search. arXiv preprint 10X.::1977.05777, 2019.
Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. arXiv preprint arXiv: 2019.
Zhaohui Yang. Yunhe Wang. Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. Cars: Continuous evolution for efficient neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1829-1838, 2020.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. International Conference on Machine Learning, pp. 7105-7114 14,,, 2019.
Jiahui Yu, Linjie Yang. Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. arXiv preprint arXiv:1812.0892 2018.
Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoe Le. Bignas: Scaling up neural archi- tecture search with big single-stage models. arXiv preprint arXiv:2003.11142. 2020.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint 1rXiv:1902.000 08142, 2019.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. arXiv preprint arXiv:1909. 09656, 2019.
Arber Zela, Julien Siems, and Frank Hutter. Nas-bench-Ishott. Benchmarking and dissecting one- shot neural architecture search. arXiv preprint arXiv:2001.10422, 2020.
Miao Zhang, Huiqi Li. Shirui Pan, Xiaojun Chang, and Steven Su. Overcoming multi-model forget- ting in one-shot nas with diversity maximization. Proc. of CVPR, 2020.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. In Proc. of ICLR, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proc. of CVPR, 2018.
10

---

Under review as a conference paper at ICLR 2021
A BACKGROUND AND RELATED WORK
Neural Architecture Search. Neural Architecture Search has demonstrated its capability of auto- matic DNN architecture design and generated DNNs even better than handcrafted ones in several
tasks like object detection (Chen et al. (2019)); Peng et al. (019)), segmentation (Liu et al. (2019a)) and disparity estimation (Saikia et al. (019)). Early works, such as Zoph & Le (2017): Real et al.
(2019) use reinforcement learning in discrete search spaces but spend tremendous time on architecture searching and network training. Recently, more efficient methods, such one-shot and weight-sharing NAS, are widely adopted by the community to reduce the network search time. Previously published works (Liu et al. (2019b);
evolutionary algorithm to deliver optimal network structures
Cai et al. (0118): Xie et al. (2018); Dong & Yang (2019b;; Xu et al. (011)); Chen et al. (2019a)
start to use differentiable representation for the search space and focus on optimizing the archilecture
search speed. Other works (Li Talwalkar (2019); Chen et al. (2019b); Zhang et al. (0020); Guo
et al. (2019); [endder (2019; Yang et al. (2020) adopt discrete and random sampling strategies to explore architectures in a weight-sharing supernet. Recently, we have seen rising concern about the
evaluation and effectiveness of NAS (Yang et al. (2019); Yu et al. (2019): (Zela et al. (2019). There- fore, researchers started to launch benchmarks to provide fair and efficient NAS evaluations (Ying
ct al. (2019); Zela et al. (2020); Dong & Yang (2020)).
Random Sampling NAS. As one of the major approaches, random sampling NAS has been widely studied in recent years. [Bender et al. (2018) proposed one-shot network training strategy with the dropout of operations, which can be considered as an extreme case of the random sampling. Later, [i & Talwalkar (2019) explored the reproducibility issue of existing works and observed that the Random Sampling strategy creates a strong baseline on image classification and language modeling. Guo et al. (2019) proposed a strategy combine the uniformly random sampling training and post-training evaluation by an evolutionary algorithm to deliver more efficient solutions for image classification. To improve the search latency, Yang et al. (2020) used modified NSGA-III to generate the Pareto frontier with a fast search time; while Zhang et al. (2020) proposed general approach to maximize the search diversity and enhance the ranking correlation for both DNAS and RandomNAS. Also, RandomNAS has shown its strength in developing hardware-efficiee network Yuu designs (Cai et al. (2019):] Yu et al. (2020) Although most of the works have achieved the state-of- the-art performance in their domains, few of them have investigated the ranking correlation between the prediction of architectures by RandomNAS and the ground truth, which is the keystone for the success of the RandomNAS ranking estimator.
Differences between EPS and other works. Although we use the tournament selection EA and aging mechanism for the EPS, which is also adopted by Real al. (2019) (named regularized evo- lutionary algorithm), the motivation is different. We find the effectiveness of such a method for updating the proxy search space in weight-sharing supernet while Real et al. (2019) took it as a marr-from-seracch--rainni close to the time train an architecture from the search space. However, Real et al. (2019) takes more than 3,000 GPU days to find an architecture that leads to 9,000X consumption than ours. Also, we notice a recent work, the CARS et al. (2020) uses a modified NSGA-III for the selection in the training of a supernet. The main differences are 1. EPS motivates by several obser- vations of RandomNAS, which is very different from the CARS. 2. EPS uses a single object EA for minimizing the validation losses while CARS uses an NSGA-III based algorithm for two conflicting objectives (potentially): maximizing the performance while minimizing the architectures' parameter size. 3. EPS updates single architecture one time while CARS updates multiple architectures and leads to higher GPU memories consumption. 4. EPS uses a batch of data for validation of each architecture while CARS uses the whole validation dataset for architecture. Overall, EPS shows a higher accuracy on DARTS search space compared to CARS, and since CARS isn' 't open-sourced are unable to do the extensive experiments for it.
selection for independent architectures. Thus, EPS searching time is
B DETAILED SETTINGS
B. NASBENCH-200
Our works are done on Py PyTorch(Paszke et al. (2019). Works like Yu al. (2018); Liu et al. (2019b) point the global moving average of the batch normalization leads to fluctuation among the

---

Under review as a conference paper at ICLR 2021
weight-sharing architectures. In the EPS, we disable the learnable affine parameters in all the batch normalization layers. We strictly follow the NASBench-22 dataset into train/validation two (11)s( We use the SGD with the momentum as 0.9. The initial learning rate is 0.1. The weight decay is x 10-5 The scheduler is the cosine annealing from to O. The training batch size is 128 and the validation batch size is 250(1 % of the training data). et al. (2016)) cross entropy loss with asmmooth = 0.1 which contains more information of the prediction distribution than the one-hot criterion. The evo- lutionary algorithm only mutates the cells. The rule for mutation is: The current operation on the edge have P_ _ppuisse 0.5 as the probability to be mutated to a new operation(include itself) on the same edge. For the data augmentation we only use the random cropping with padding 4, the random horizontal flipping and image normalization based on the training dataset statistics.
settings to split the CIFAR-10 training
The loss function is a habel=smoothinngSSeeeeee
B.2 DARTS IMAGE CLASSIFICATION SEARCH SPACE
The settings are the same as B. except the mutation. Since the DARTS search space is larger than NASBench-201(10- vs. 15,625), we adopt a simple yet conservative mutation rule. 1. The current operation on the edge have P_ opurise (eeration(include itself) on the same edge. 2. If a node has the unconnected predecessors, one of its edges have P P_opurise- 0.1 as the probability to switch to an edge linked the unconnected predecessors, and the operation on the new edge will be chosen randomly. We apply this settings through all DARTS-search-space series. For the search supernet, we choose 16 initial channels and 20 stacked cells. For training architectures from the scratch, we strictly follow Liu et al. (2019b) settings to generate a fairly comparable results.
0.2 as the probability
be mutated to a new
B.3 DARTS IMAGE CLASSIFICATION SUB SEARCH SPACE
Follow Zela et al. 2019); ; Liu al. (019b), for CIFAR- 100 and SVHN we use 16 number of initial
channels and 8 cells when training architectures from scratch. For CIFAR-10 S1 and S3, we use 36 initial channels and 20 stacked cell. For S2 and $4 we use initial channels and 20 stacked cell. During the EPS searching, we use 16 number of initial channels and 8 cells for the supernet of CIFAR-100 and SVHN. we use 16 number of initial channels and 20 cells for the supernet of CIFAR-10.
B.4 DARTS PTB SEARCH SPACE
We use the settings for search as Liu et al. (2019b) except: 1. We choose the embedding and hidden dimension of 850 for the RNN. 2. We run the experiment for 80,000 iterations with 128 training batch size and uses the PP256, S:64, M:4, T_val:50) for EA. 3. The gradient clip is changed to 0.1. 4. We only use 1/4 validation dataset for the architecture validation. The settings for training an architecture from the scratch is exactly the same.
C ADDITIONAL EXPERIMENT
C.I OPTIONAL APPROACIIES ON NASBENCHI-201
Here we discuss two optional methods and evaluated them on NASBench-201. The first one is the progressive search. The algorithm is shown in Alg. The supernet is initialized with 3 searchable cells (NV = and total searchable cells are 3N). Please refer to the Figure 1 in the NASBench-200 paper(Dong & Yang (2020) for the defination of N). We gradually increase N by in each growth interval (G.al = 15000 iterations) until Nz, 5. The new cells are randomly initialized and stacked into the supernet. Other training settings are adopted from EPS. The second one is the EPS with multi layer perceptron(MIPP) The algorithm is shown in Alg. 3 The idea is to use the MLP learn the losses of architectures in the current Q_pop and to predict architectures in the GS. We use a 3-layer MLP with 100 as the embedding size. The input is the indexes of the operations In MLPPrrin, we use the architectures evaluated in current Q_pop as the input and their losses as the label to finetune the MLP for 20 epochs. In the MLPPredict, we use the current MLP to predict losses of 256 architectures randomly generated. Then it return the best predicted architecture. The five-run experiment results NASBench-200 are shown in the Table 7 Original EPS outperforms
6 edges.
12

---

Under review as a conference paper at ICLR 2021
other two methods CIFAR-10. 10. Since Progressive EPS speeds up 1.5x, considered it as good trade-off between the performance and the speed.
Algorithm 2: Progressive EPS
Initialize supernet with N
Inirialize an empty architecture popolation queue, Q_pop Initialize an empty history
for 1,2, ... PP do
new wep_architectrrr + Rundonfnnixrehtesspeerrnn) Enqueue((Q_pon new aem_oorchitecture
end
sample Saoppl__eec set +- RandonSample( Q_pop, S)
for
.................. T_iter do architecctre KandomSamplet sample_set,)
ThainOneBBlcchhspppeeeee architecture) i % ral ( then for =.2,....
architecture e- sample_see set [k]
val_foee ValOneBatchisupeee supernett. architecture)
archstecture.lor + val_loss
end
Sort sample_eet by orchitecture. in ascending order apppen[(smpple_e]))
for k in I.2...M do
www.hthhhheeeeeeeeo Mutate(samll__ee((]
Enquenet pop, nww__eeeeeeeee snw__errhhiteccure)) Dequeuel Q_pop)
end
sample set +- RandomSample( Q_pop, S)
%
OAND N < Nmax then
end
end
end
selected cec.ceedddrcchtetctueee AcciienrrrSccccooo/ksssssso... scchectukeemallssccteoooootttttd
Algorithm 3: EPS with MLP
Initiaiize supernet
Initialize an empty architecture popolation quene, Pop
Initialize 3-layer M.P
Initialize an empty kietory
new_ardh nee_archhteecurre
Enqueuel Q_pppp serpe
end
sample_see pet RandomSample( Q_pop, S)
for 1, ... ..., T-iter do architecture RandomSamplol eample_set, TrainOnneBachhhsupeerreee arcchtetrarhhhtttrrrr it's % f_val then for =1,2,-.., orchitecture <- somple set [k]
val_Joss ValOneBatchisupee supernet, architecture)
architecture.loss + val_loss
end
MLL.P
Son sample_set by architecture.los in ascending order
history appenddssmmplll
1.2...M do
new aww.acttcccureeeecooo +- MI PPrddict
Enqueuel popop. new_erchsteccure)
Dequeuel Q_pop)
sample set k- RandomSample( Q_pop, S)
and
end
selected archhtecccchhhteccrrreeess Aecaee/eeeeeeiiiiiiueeetttillssr buchieetneeeernnttettttedd..ro wwwpaaaeeddeddedodrddrdtttaaaaad
13

---

Under review as a conference paper at ICLR 2021
Table Comparison between EPS and two optional approaches NASBench-201
Method
Valid acc.
Test acc.
GPL ltrs.
Progressive
91.33
94.00
1.2
EPS with MLP EPS
89.17
92.57
2.0
91.50
94.34
1.8
C.2 4-RUN TRIAL ON DARTS PTB SEARCH SPACE
Similar to the work Li & Talwalkar 2019). we conduct an experiment to run EPS times and compare the 300-epoch validation perplexity of the selected architectures. The results are shown in Table g
Table 8: EPS is ran for 4 times with different random seeds. The best of these architectures for each run then trained from scratch for 300 epochs.
Method
Run
Run2
Run3
Run4
Avg. perplexity
DARTS
67.3
66.3
63.4
63.4
65.1
EPS
65.10
63.74
64.72
64.77
64.58
D MORE DETAILS
Table 9: The GPU benchmark of the EPS different search spaces on one Titan GPU,
Avg. load
Max. load
Settings
Train speed (batch/sec.)
speed (batch/scc.)
Train speed (batch/soc.)
speed
Mem. (GB)
(batch/soc.)
NASBench-200 201
26.11
45.79
15.55
24.09
2.27
DARTS Schanness,,,ss 16ceelss
DARTS DARTS(20ehmmel, (6cell))
3.91
11.51
3.68
6,83
8.01
DARTS-PTB
6.83
N/A
N/A
3.79
14

---

Under review as a conference paper at ICLR 2021
Table 10: Architectures searched on NASBench-201.
Setting
Architecture
conv 3x3-0|+ nor conv nxr
onv 3x3 nor www.._ecccc.__eee _______________1_________
#2
_oo__cov__ie_
n
onv - nor conv _ 3x3-21
|nor cwwv mxor conv nxr conv 3x3-1 | connect-0|
A3
onv oav_1x1-1| =
84
onv oov_333-1|ooccccon__333 cotv____oo_______
|ttp:///po.a.ooooooo/o/ooooooo/a ski co nor_c
A5
owv_333-11mot..oov_1112
15

---

Under review as a conference paper at ICLR 2021
Table 11: Architectures searched on DARTS image classification search space.
Setting
Architecture
Genotype (normal=[( max pool 3x3
('sep 5x5' 1), ('skip_ conn
ect 0). (' sep__cavv__a 1). ( ('sep_com 3x3" 0), Csse__covv_Sxt _5x5"
). C'éil__onv_5e5'' 1), ('dil_conv_Ste Sx5', 2)1, D), ('avg_pool_3x3'
0), ('dil__oov_3x33
CIFAR-I0
0). ('dil cosl___oo3_333 3x3", 2), ('sep_comy 3x3', 1), prav 3x3", 3), ('a
vo_pool 3x3', 1), C'ava_pool_33e 3x3"", 2)1. reduce_concat-rangeC.. 6))
Genotype [("pooaal((sssp_cooo..333
0), ('skip_conmect" D), ('sep_conv.
3x3 1), ('dil_conv _05___oow_333',, 2). (..0''' ('sep_conv _3x3" 0), ('sep_conv..5n
#2 ). ('max_pool 3x3 0), ("sep_come 5x5 101, normal_ comel___cctt-aageee.
). reduce=[("sep_conv___
0), ('dil_conv_5x5"
D), ('avg_pool_3x33
0). ('sep_come 3x3", 2), C'avg_pool 3x3' 0). ('sep conv 5x5", D) ('a
vg_pool_ 0), ('skip_connect! 1)1, reduce_ reduc__concat-rangeee.
Genotype (normall() (otpppocce""llltt"""itcoooee""""
0), C'stei_ D) ('sep_conv. conv.
0). ('dil conv 5x5' 2), ('sep 3x3 0), ("sep_conv conv
#3
). ('dil_coav_5te 5x5" 0), ("sep_conv 5x5 1)1, normal_ conal__cccctt-rage(...
[educe=[("sep_comm D), ('avg_pool_3xx _3x3',, 2), ('sep_conv_5tt) 5x5', 3), ('s
0), ('dil__cov__5x5"
1), ('skip_connect
0), ('dil_conv_5xx kip cinnect' 2), pnax_ppoll_aee
3)1, reduce_ ceduce_concat--aagee... 6))
Genotype (normal=[("skipppeia 1), ('sep_conv_3te
0). ('dil_cooov__x33 3x3', 1), ('dil_conv.
5x5' 0), (' cosep_conv_st
0), ('sep_conv_SEt)
#4
). ''skip.connect" 1), ('sep_ 3x3 3)1, (oncat
) reduce=[('sses seeee==("spppcoo conv 3x3', 0). pool 3x3', 1),
connect".
0), ('max_pool __x'__''''' 1), ('dil_com _x55 1). ('max_pool_3xx 1333' 2), C'a
vg_pool 3x3', 0), ('dil_com 3x3' 2)1. teduce_.cnnat-raanee
6))
Genotype (normal=[ (siippp connect', 0). ('sep
3x3', D), ('sep_conv
5x5 0), (osep_conv 3x3" ' 1), (' ('skip
2), c'sep_conv_SI55"
#5
) ('dil conv 3x3' 0), ('dil_ conv 5x5', 1)1, normal (on,at=
) (iice==[('di_com 3x3', 0). ('sep_conv_ 3x3', 1), ('avg_peol_3tt 3x3
0), ('skiipconnect's 2), ('sep_conv_ _o3v_3x3' 1), ('sep_conv_Sxff 3) ('s
ep-conv_3x3', 1), ('sep_comv_3x3'' 3)], ceduce_concat--aagee. 6))
0), ('skip_connect 1), ('dil_conv.
3x3 1), ('sep_conv 5x5" 2), ('dil_ccmm 5x5" 0), ('dil 5x5',
#1 ). C'sep_conv_3e2 3x3", 0). ('sep_cony. 5x5 1)1, normal coaaall-cactttageeeeeee
reduce=[(' (cdee-=('di_coov... 3333', 0), "onv_ 3x3', 1), ('sep_conv_ 3x3'.
CIFAR-100
1). ('dil_comv 3x3" 2). s'sep_cony 3x3 0). ('sep_conv 5x5', 3), ('s
kip_connect'. 0). ('skip_ ('skip_connect'. 3)1, reduce_ congat-
Genotype (nnottpp(normal11i (normal=[(" dil _il__ooo________________________
0), Cosneett 1), ('dil_com conv.
3x3 0). ('sep_come conv 5x5' 1). ('skip connect 0) ('dil_come conv 5x5',
#2 ). C'sep_conv_5x55 5x5" 1), "'se_ccon_5x$5
2)1,
reduce=[('s [onse__oooo
0), ('sep_conv_ _x33' 1), ('avg_pool_
0), ('sep_conv_$x55, 1), ('sep_conv_3xe ' 1), ('skip-connect', 2), ('s
cop_connet''... 2), ('sep_com conv 3x3', 4)], coauuce_oocattraaeee. 6))
Genotype (normal= [('skip_cconnect
0). (' ("sneip_comnett 0) ('sep_conv_
1), ('dil_conv.
2). ('dil_conv_5s) ). ('sep 5x5' 0), ('sep "on''3x33', 1)1, normal_ comaa__cnctt-aageee
5x5 0). ('dil_conv_
#3
). reduce=[(' (idd'(d''d_ooma 3x3" 0) ('sep_conv 5x5', 1), (' ('skip_eee connect"
0). ('sep_ conv_ 1), ('sep conv 3x3'
('dil 3x3', 3),
ax ss__pool_3x33 0), ('nax_pov faax__poo__3__ 3x3" 1)], reduce_ comuueeecccatt-aaee:2 6))
Genotype (normal=[C (iLl((ddll_cmmm din_coov.___oeeeoeeeeeeeele___ 3x3", 0). ('skip connect D), ('dil_conv.
5x5 0). ('sep_conv. 5x5" ", 2), ('sep_conv. 5x5 0) ('sep_conv_55e 5I15'
#4
). ('skip connect' 0), ('dil_cons
1)1, nornal congat=
) reduce=[( skip_connect" 0). ('dil_conv_5xt
1), C'sep_conv__a 5x5
0). ('max_pool_3x2) ep_conv_3x3'. d), ('sep_comv_3rd
1), ('sep_conv_Sxs" 2), ('skip_commect'. 3)
1)], deduce_concctt-rangeC 6))
Genotype (normal=[( wttssssspppopppeseeeeeeeeeeeeeee
0). ('skip_connect D), ('sep_coav.
3x3 0), (' ('sep_conv_ _ " 2), "),,(ss, ('sep_conv_ _oos" 0) "dii__covv$Sxs"
#5
), ('sep_conv_55x5"
2), ('dil_conv_5se
3)1, normal concatt-anna (2,
). reduce=[('ave pool 3x3" ", 0), ('sep conv 3x3 ' 1), ('nax pool 3x3'
0). ('avg_pool 3x3', D), (' C'sep_cony 5x5', 0), 3)1, (2
1). C'a
voop 3x3', 2), "sse_ccoe"
16

---

Under review as a conference paper at ICLR 2021
Table 12: Architectures searched on DARTS image classification sub search space (CIFAR-10).
Setting
Archatecture
Genotype (normal=[('' conv 3x3 , 0), ('skip connect', 1), ('dil conv
5x5 0). ( ('skip_connect connect', 2) (' ('skip_ connect 0), ('sep_cenv_ _3x3',,,,
), ('dil_conv_5x35 3), 9), ("max_pool_3x3 3333' 1), ('max_pool_3x3"
_ 4)1, normal_concat-rangee
SI
), maaxce=o("mx
0), ('dil.conv 5x5', 2), ('avg_pool 3x3", 0),
5x5", 3), ('u 6))
ax_pool "s__poo1_xx3", _x3"' 0), C'skip_connecs" 2)1. reduce_concat= seduee_concattrangeeC.
Genotype (""ipaa
0), ("skip_connect', 1), ('dil_conv. 5x5' 0), ('skip_comme connect', 2), ('sep_conv. 3x3" D. ('skip.connec"""
#2 ). ('sep_conv 3x3", 0), ('dil_ conv 3x3 2)1.
). rrduce=[["max__pol.
9), ("max__ool_3x33" "xoo__3x''. 1), ("max_pool_ix3"
1). doil_coov 5x5 2). ('sep conv 323", 1). 4)1. reduce_concat--angeee. 6))
conv 3x3". 2). ('d
i1_conv__5x_ 3), C'dil_ccnv_5x5
[Cormal[[[[lilll _a_____o____33'______________>" 0), ('dil_comy conv__xs"', , 1), ('sep_conv.
3x3', 1), ('dil conv 3x3 2). ('skip connect' 0), ('sep coav 3x3',
#3
). c'sep_canv_3x3 0),
2)1. normal_ cormal_concat-raagee]
) [educe=[((max_poo 3x3', 0), pnax__ool_ix]" 1), ('avg_ponl_
0) "'dil_conv_5555 2), ('max_pool_3r) _3x3''_33''" " 0), ('skip_connect'' 2), ('n
ex__pool__30 0), ('max ('max_pool
1)J. reduce__conatt-aangee
6))
Genotype (normal=((=kk connect'' 0), ('sep_com conv _333', 1), ('sep_ conv.
3x3" 0). ("skip_coanect connect' 1). ('skip ('skip_connect connect 0) ('sep conv 3x3"
"1 ). <'sep_canv_jxx3 2), ('sep_conv_3x3',
normal_coneatee (angee ), *educe-(""sep_cov___ 3x3'_ 0), ("sep_conv_3xx) - 1), ("skip_connect"
S2
0), ('sep_conv__ee
1), ('sep_conv__
2), ('sep_conv_3xx) 3), ('s 6))
op_conv_3xx", 1), ('skiis"............ ('skip_connect', 4)], reduce_concat
connect', 0), ('sep conv 3x3', 1), ('skip ect' 11, ('sep_conv_ 3x3 2). ('sep_canv_ _x3 0), ('sep_conv__ae 3x33'
renotype(norraa:
), C'sep_conv_3x3", 0). ("sep_conv_3x3"
1)1,
), reduce=(""sep_con_
0), ("skip-commect', 1), conv__on_3333
0), ('sep_come 3x3 2). ('skip_connec) connect', 0). ('sep conv 3x3', 3), ('s
kip_connect", 0), "skip_connect'. 4)1. reduce_concat-rangee.
6))
Genotype (onomyae (normal=[('sep) (ecc'sepcooo___3 _x33" 0), ('sep_conv_33
1), ('sep_conv.
3x3' 0), ('sep_conv 3x3" 1), ('sep_ 3x3 0), ('skip_ connect',
#3 ). C'skip_connect", 0), ('sep_come 3x3 1)1. normal_ comeal_eonna---angee 9), ('skip_conneet''
). (uiie=[["skipcccmnee
(' ('skip_connece
1). ('sep_com 3x3" 2). ('sep conv 3x3 1), ('sep_come conv 3x3 3), ('s
cp_conv__xx'. 2). ''sep_conv_3x3'' 3)]. reduce_comcat--angee2.
Genotype (normal=[("sep_coom
3x3' 3x3', 0), ('sep_conv 3x3', 1), c'sep_conv 3x3' 0), ('skip_connect' 1), ('sep_canv__te
0) ('sep_conv_ix3)
). ('sep_conv_3xx 0), ('sep_conv_3x3
1)], normal_comcat rangeat
). reduce=[('skip connect', 0), ('skip_ connect', 1). ( ('skip connect'.
1), ("skip_coanect', 2). ('skip_connect" ep_conv_lx3', 0), ('sep_conv_3x3" (faoo_aas...... 3x3'' 1)], reduce_concat-rangeee.
0). ('sep_conv__xx 3x3', 2), C's 6))
connect', 0), ('sep conv 3x3', 1), ('skip conn ect' 1). "'skip_cconee""
2). d'sep_canv 3x3 0) ('sep_ conv 3x3',
42 <'sep_canv_3x3> 0), ('sep_conv__k)
normal _engeatt
0), ('skip_connect' 1), 33n 0). ('sep_conv_jxx) 2), ('skip_coanect 1), ('sep_conv_ (twp:ssss""...sss_ssccccccmmmm
=educe-(("sep_con__3e
3), ('s 6))
op__oov_3x3'__ 0). ('skip_connect', 3)], caduce_concattrragee
conv 3x3' 0), ('sep conv 3x3', 1). ('skip ect' 0), ('sep_conv_ixi 1), ('sep_canv. 3x3' 0), ('sep_conv___) ce____eevv_________
renotype(norrma::e
), ('sep_conv_ixx"" 0). ('sep_conv_3x3' 2)1, germal_concat-rant
).
0), ('sep_conv_3xx3
1), ("skip_connect"
1). ('sep conv 3x3', 2). ('skip connect', D). ('skip_conned connect', 3), ('s
ep_conv_3x33 1), ('sep_conv_ 3x3', 4)1. reduce_ concutcrecctttrreeee22 6))
Genotype (hwrmal=[("sss_ccoo
3x3 0) ('sep_come conv 3333", 1). O'sep_conv
3x3' 0), ('sep_conv_he) _333' 1), ('sep_canv_ 3x33' 2), ('sop_conv_ixx)
#1 ). ('sep_conv_3x3" 0). ('sep_comv_3x33"
4)], normal_concat-rame
). [ostcc=(((sep_coov___
0), ('sep_conv_lx3". 1), (" ('sep_conv_lxx-
0), ('noise', 1). ('."('sppp ('sep_conv_3kx 3333', 2). ('sep_conv_3xk) 3x3'' 3), ('sep_conv
_3x3', 0), ('sep_conv_3es
3)], contteeconc
6))
Genotype (normal=[('sep_com _ 0), ('sep_conv_ar)" 3x33", 1), ('sep_conv. 3x3', 0), (' cosp__oov__x3""" 1), ('sep_canv_3x3' 0) ('noise', 3), ('se #2 px3" " 0), ("sep_conv_3x3" 2)1,
6), redu ce=[("sep conv 3x3', 0) ('noise', 1), ('noise', 0), ('sep_com 3x3',
1), ('noise", D). "...(esp ('sep_canv__se 3x33" 3), ('sep_conv_3x3" 0), ('sep_coav _3x3' 1)], reduce_concat-raageel.
6))
Genotype (normal=[('se) conv conv 3x3' 0), ('sep conv 3x3', 1), ('sep conv. 3x3" 0). see__coov_ix3 2) ('sep_ 3x3" 0) ('sep_conv__3 3x3"
#3 ), c'sop_canv__x33 0), ('sep_conv_3x3'
3)1, normal_coneet samaallconeat-ragee ). reduce=[('noise' 0), ('noise', 1), ("sep_conv_3x3" 0), (* ('sep_conv _3x3', 1), ('noise', 0), ('sep_conv_3xx) 1), ('aoise', 1), ('sep_conv -x33", 2)], reduce_.concat--ranne... 6))
17

---

Under review as a conference paper at ICLR 2021
Table 13: Architectures searched on DARTS image classification sub search space (CIFAR-100).
Setting
Architecture
(rrotype(normma[([[CC( skip connect', , 0), ('dil conv 5x5', 1), ('dil conv
5x5 0). ( (sep_coov 3x3 1). ('sep_canv 3x3" D) ('sep_conv_ 33_33333'' 2
), c'sep_conv_3x33 0), ('dil_conv__ae 5x5', 3)1, normal_concat-rangee
SI
),
3x33., 3x3', 9), ('dil_conv_3x3"' 1), ('max_pool_3x3"
0), ('dil conv_ 5x5', 2), ('avg_poo0 3x3", 0), ('dil conv 5x5", 3), ('a 6))
vg_pool_3xxx 3x3", D) C'dil_cony 5x5', 4)1. reduce_comcat-
Genotype Gemotype
0), ("skip_commect', 1), ('dil_conv.
5x5' 0), ('sep_cony comv_33'3'3 , D. ('max_pool _333" , 9) ('sep_conv__3e _333''
#2
). ('di1_ 5x5 3), ('dil_come 5x5 4)J. normal_ conaa__cnnct 9), ("max__ool_3x33 _oo1_3x3' 1), ("max_pool__x33
). [saucc=[[(avg_poo
0). ('dil conv 5x5 2). ('max_ pool 323", 0). ('dil conv _onv_ 3), ('d
i1_conv_5x55 3), C'dil__cov_5x55
4)1. reduce_ reduce_conctt-rangee2 6))
Genotype (noraal:(i dii_____o__x3',,, 0), ('dil_coms conv__xx'', , D), ('dil.conv.
5x5' 0), ('dil conv 3x3' 2). ("skip_connect connect' 0), ('skip_ connect',
#3
). <'sep_conv__x3 3x3 0), ('dil_ccov_55x5"
3)1, normal_ cormal_concat--aanee22
) (Clucc=(((avg_poll
0), ('dii__cov__xx""
1), ('avg_pool_
0), ("dil_comv_5tx) -5m5" 2), (0,(''aa ('max_pool 3x3', , 1), (' ('skip_connect'' 2). ('d
11. convo_____5 2), ('dil_conv... 5x5" 3)J. reduce_concat-range
6))
_ (0.)),) 0), "'sep_come _3x3', 1), ('sep_ conv
3x3' 0). (5.0"% ('sep_conv_ cop__33n3__ 1). ('sep_ canv 3x3 1), ('sep_com conv 3x3"
"1 ). <'sep_canv_ix3" 1). ('sep_conv_3x3"' 0), ("sep_conv_3xx) 3x3'" 1), sep__covv_3xx
normal_ conall_cnncatt-aneee2
S2
), reduce=(("skip_comee
0). ("skip_connecct 2). ('sep_conv_ _333', 0), conp__con_3333" 2). ('s 6))
kip_connect', 1), ('sep_conv_3x3". 3)], reduce_concat
(enoayyeenormaa=
conv 3x3' 0), ('sep conv 3x3', 1), ('sep conv
3x3" 0). ('sep_conv_ 3x3" 2). ('sep_canv_ 3x3 1), ('sep_conv__ke
). C'skip_connect'. 1), ('sep_conv_3x3'
4)], normal_concat-rangee
). (sice==("sep_comt
0), ( ('sep_conv_3r) 3x3', 1), "),((ee)) ('sep_conv_ 3333"
0), ('sep_conv conv 3x3' 2). ('skip_ connect', D). ('skip_connect connect', 3), ('s
cp__covv_xx3"_ D), C'sep_conv_3xx
3)1. sancee_ 6))
Genotype (mormal= (esppeeconv__
3x3' 0), ('sep_com, 323" 1), ('skip_ connect" 0), 1), ('sep_conv.
0), ('sep_
#3 ). ('skip_
0), ('sep_com _x33" 3)1, normal_ comeal_cnnct--
). sisce==("siipcccnnee
9), ('sep_conv_ 3x3', 1), ('sep_conv_ 3x3',
0). ('sep_conv 3x3" 1). ('sep_ conv 3x3 2). ('sep_come conv _x3'_3x3'' . 3), ('s
kip_connect',, 0), ('sep__onv_3x33 1)1. cancee_concat--angeee2 6))
Genotype [normal=[('ssppppaeee
3x3' 0), ('sep_conv 3333' 1), ('sep_conv_
3x3' 0), ('skip_connect 1), ('skip_comnect" 0) ('sop_conv_3x3)
3)], normal comnal._cctt-rageee ). (etuce=[('sep conv 3x3', 0), ('sep_ conv 3x3', 1). ('sep conv 323
). ('sep_conv_3x3 0), ('sep-conv_3x)
1), ('sep_conv__3) 3x3 2). "'skip_connec""
0). ('sep_conv__xx 3x3', 3), C's 6))
ep_canv_ix3', 0). ('sep_canv_3x3"
4)], reduce_concat-range
conv 3x3' . 0), ('sep conv 3x3', 1), "sep_.cov
3x3" 0). ('sep_conv
carp__con______ 3x3' 1). ('sep_cany canv coe___3___ 0) ('sep_ conv "os33_coo_333'......
). ('skip_connect', 0), ('skip_connect', 1)], normal rangeat-
#2
). "=duce=(("sep_cov___ cx3'' 0), ('sep_conv_3x3
1), 33
1), ('sep_conv_ kip_connect', 0). ('skip_connect', 3)], caduce_concat--ragee
0). ('skip_connect', 1), ('sep_canv__ae
2). ('s
6))
Cenotype(normaa::CC
conv 3x3' 0), ('sep_come conv 3x3', 1). ''se__covv
3x3' 0). ('skip_connect', 1), ('skip_conness
0), ('sep_cenv_äke 333'''33'
). ('skip_connect" 0), ('sep_conv_3t) 0), ('sep_conv_3x3" 1), ('skip_connect"
4)],
). (eecce==("sppcoore_
0). C'sep conv 3x3', 2). ('sep conv 3x3', 0). ('sep conv 3x3', 3), ('s
ep_conv_3x33 2), ''skip_connect'. 4)]. seduce_concat-rangee..
6))
Genotype [normal=[C"sep_ccom
3x3' ' 0), ('sep_conv. 3x3', 1). ('sep_cone
3x3' 0), ('sep_conv_ix3' 2), ('noise' 9), ('sep_conv_ 3333', 3), ('no #1 ise', 2), (" ("sep_conv_3x3", 4)],
6), reduce=[('s
cp__onv_ix3', 0). ('sep_conv_3x33 1), ('sep_conv_iee 0), ('noise',
1), ('sep_conv_3rd -xx3' 1), ("..('nos ('noise', 3), ('noise', 0), (' ('sep_conv_jx3", 3)],
6))
0), ('sep_conv_ixx] 1), ('sep_conv. 3x3', 0), (" ('sep_conv_3x3" 1), ('noise' 1), ("sep_conv_3x3" 3), ('se #2 p_conv_3x3'' 3), (' ("sep_conv_3x3" 4)], nornal concaatraeca 6), redu ce=l("sep_comm conv 3x3', 0). ('sep_com conv 3x3', D). (" ('sep_com conv 3x3', 0), ('s ap__cov__3x3' 2), ('sep_conv_ixx) 3x3', 2). ('noise', 3), cosep_conv_ix3" 0), ('noise', 1)]. reduce_.oncat--aagge
Genotype (normal=[("sep_com
6))
conv 3x3'_ 0), ('sep conv 323', 1), ('sep conv. 3x3" 0). ( ('sep_cov__iee 3x3'' 2). ('noise' 1), 2)], normal rangee 6), redu
Genotype (normal=
sep__cov__B3 3x3", 3), ('se
#3 p_conv_3x3" 3x3'. 0), ('sep_conv_3x3', 0), ('sep_conv_3x3" D,, ('noise', 0), ('sep_conv _3x3' 2), ('sep_conv_ 3x33' 2), ('noise', 3), ('sep_conv_3x33 D) ('n oise' 2)], reduce_ccocct 6))
ce- seppppssoc_o__33
18

---

Under review as a conference paper at ICLR 2021
Table 14: Architectures searched on DARTS image classification sub search space (SVHN).
Setting
Architecture
(rrooype(noomma=([[[([ dil conv 3x3 , 0), ('dil conv 5x5', 1), ('dil conv
5x5 0). ('dil_cony _333 2) ('sep_canv 3x3" D), ('sep_conv__xx
), c'sep_conv_3x33 0), ('dil_conv__ae 3x3', 3)1,
SI
), [ _x33', 9), (' "'dl__cowv33x3' 1), ('avg_pool_3x3"
0), c'dil 5x5', 2), ('max_ 3o0 0), conv 5x5", 3), ('d il_conv_ _x___ 2), C'dil_conv 5x5', 3)1. rantuee_c 6))
Genotype Genotype (normal=((""6iicooo
0), ('dil_conv_Se3)
1), ('dil_conv.
5x5' 0), tskip_connect" D) ('sep_coovv _onv_33x3' D. ('sep_conv_33e 3333''3',
#2
). ('dii_conv_3xx3 3x3", 2), ('dil_conv 3x3" 3)J. conea_l-enet--raeee
).
13x3'', 9), "max__ool_3x3', 1), ("max_pool_ix3"
0), ('dil conv. 5x5 2). ('max_por pool 323", 0). ('dil cony 5x5", 3), ('a
vg_pool_3x3" 10, C'skip_connect'. 4)1. cenuee_concat-rangee22 6))
Genotype (noonaliioor [cal==((Cd__oov______ 3x3', 0), ('dil_ cau___co___S"".., 1), ('dil_conv.
5x5', 0), ('sep_ conv. 3x3 D). ('skip_connech) connect' D) ('sep coay 3x3',
#3 ). <'skip_connect 0), d'dil_conv_Sxt
3)1,
mmaxee- pop_pooll''',_____________"_"''_ 0), ("max_pool_ixx) 1), ("max_pool_3xt
0), ('dil_comv_5tx
2), ().((aa)))) ('max_pool_33) 3x33" 0), ('dil_.onw_3xx3 2). ('d
11. clovo______ 2), ('skip_conneed
3)J. reduce_concatt-aagee2 6))
conv. "op_3"" 0), ('skip
1), ('sep_ conv.
3x3' 0). (..0"% ('sep_conv cop___on__ 1). d'skip_conned"
1), ('sep conv 3x3"
"1 ). <'sep_canv_ix3" 0), ('skip_connect'
normal_ ranall 0), ("sep_conv_3xx) 1), ("skip_connect" 2). d'skip_connect" 2), C'skip_comnect', 3), ('s op_conv_3x3', 2). ('sep_conv_3x3', 3)], caduce_. 6))
S2
), "=duce-(("sep_cov__3
0). ('sep_conv_
Genotype (nooovpe(nornaal(((sss13 connect', 0), ('skip connect', 1), ('sep conv
3x3' 0). ('sep_conv_iitt
2). ('skip_connect
0), ('sep_conv__ae _x3'"
42 ), C'sep_conv_3x33, 3), ('sep_conv_3xs' 4)], cormal__oncat-raee
). Deduce=[('sep_com)
0), ('sep_conv_3t) 3x3', 1), ('sep_conv_3tt 0), ('sep_conv conv 3x3' 2). ('sep_ conv 3x3 2). ('sep conv 3x3', 3). ('s
_p__oovv_3x""_ 0), C'sep_conv_ 3x3" 3)]. reduce_comcat-rangee.
6))
Genotype (no (Crss__coos__________
0), ("skip_comnect
1), ('sep_conv.
3x3' 0), ('sep_conv conv 3x3" 2). ('skip_ connect" 0), ('sep_com) conv 3x3',
#3 ). ('sep_conv_3x33 3), ('skip_conners
4)J.
). reduce=[('sep_ee _333'' 9), ('sep_conv_ 3x3', 1), ('sep_cony 3x3'.
1). ('sep_come 323" 2). ''se__conv 3x3 0). ('skip_comme connect', D) ('s
cp__onv__xx'. 30, C'skip_connect', 4)]. reduce_ (ange,,
(aatsspp((oommm=[((((((00 _op__xxoo___''_" 0), CO''C' c'skip_connect'
1), ('sep_conv_ O), ('skcip_connect'
3x3' 1), ('sep_conv_ixx" 2), ('skip_connect" 1)], normal_comcat-rame caneat-
). <'sep_conv_3x33 0), ('skip_connect'
). reduce=[('sep (eppt(("'ep_cooo conv 3x3', 0), ('sep conv 3x3', 1). ('sep conv 323
0), ('sep_conv__ss _x33" 2). ('sep_conv_ 3x3' 0). C'sep_canv srep_eenv_3x3- 2), C's 6))
ep_canv_3x3', 1), ('sep_cany_3xx
D _xx3 3)], reduce_concat-range
conv 3x3' 0), (' ('skip connect', 1), ('sep_com conv..
3x3' 0). ('sep_conv 3x3' 2) d'sep_canv 3x3 0) ('sep_comee conv "'s"3_conv33x3..
#2 ). ('skip_connect', 0). ('sep_conv_3x3" 3)], normal coaalll_oottttaageeee
), reduce-(("skip_comm
0), ('sep_conv_3x) 3x3', 1), cosnect
1). ('sep_conv_ ep_conv_3x3', 2), ('sep_conv_3x3' _xx3'' 4)], saduee_conccat
2), ('sep_conv__xx 0), ('sep_conv_jxt
3), ('s 6))
Genotype (moooull((crrall[(('sss conv 3x3' 0). ('skip connect', 1). ''sp_ccov
3x3' 0), ( ('sep_conv_ 3x3' 2). ('sep_canv. 3x3 2), ('sep_cenv__ae "oav_33x'',
). ('sep_conv__x3'_ 2). ('skip_connect' 3)1,
).
0), ('sep_conv_3x3' 1923',110 1), ("skip_connect"
1). ('skip connect', 2). ('sep conv 323', D). ('skip connect', 3), ('s
kip_connect', 1), ('sep_conv___ 3x3', 2)1. reduce_ congee_ 6))
Genotype (normal=[[' sepp'see_oo_____ 3x3', 0), "'sep_conv3xx"" 3x3" 0), ('naise', 2), ('sep_conv_3x)
1). ('sep_conv.
9), ('naise', 3), ('sep_.cov-
#1 3x3', 1), ("sep_conv_3x3' 3),, cormal__oncat-aaggee
6), reduce=[('s
ep_canv_3x3 0). ('noise' 1), ('sep_conv_3xx" 1), ('noise', 2), ('n
oise', 0), 'xx 2), ("sep_conv_3x3", 2), ('sep_conv_jx3', 4)],
6)) Genotype (normal==("" (espppc(cssp__
0), ['sep_conv_ix3] 1), ('sep_conv_ 0), ('sep_conv_3x3 3), ('no #2 ise", , 2), (' "om__coov_3x3"" 3)1, nornal (2,cattraagge 6), reduce=[('s ep. conv 3x3", 0), ('sep_ conv 3x3', 1), ('noise', 1), ('sep_comm conv 3x3', 2), ('sep_conv _o___ooo333'" 2). ('sep_conv_Bs) 3x3", 3), ('sep_conv_Bx3 2), C's 6))
3x3', 0), ('noise', 1). ('sep_conv___
ep_canv_3x3" 4)], reduce_coonatt-rageee..
Genotype (normal=[[ [[' seppp.pppeeee sep__conv 3x3', 0) ('noise', D. ('sep conv 3x3',
). ('sep_cony, _anv_axnvv""________eeeeecc 3x3', 2). ('noise'. 0), ('noise", 3), ('sep_conv_Be
#3
). ('sop_canv_3x3
4)],
rangeaa, 6), reduce=[[ ('sep_conv 1), ("sep_conv_3rz)
0), (' conp__oovv3x3"" 2), ('sep_conv 3x3" 0), ('sep_conv_ ex3', 2), ('sep_conv_3x33. , 2), ('s ep_conv_ 3x3', 3)], anduce_concat-range 6))
_3x3', 0), ('sep_conv_
19

---

Under review as a conference paper at ICLR 2021
Table 15: Architectures searched on DARTS PTB search space.
Setting
Architecture
Genotype (recurrettt
0), ('relu', 1), ('signoid', 1), ('relu',
Runl
1). t'tanh', 0). C' ('signoid', 0), (' t'tanh", 4), ( ('identity', 0)], concat -range(1, 9))
0), ('tanh', , 1), ('tanh', 1), ('relu', 3) ('relu', 1). ('tanh', 5), ('relu', 5), ("tanh", 4)1, concat-range 9))
Run2
('relu', 0) ('tanh' 1), ('relu', C' ('signoid", 4). ('tanh', 2), ('tanh", , 0), ('tanh', 0)], concat=range (1.
eentyyeereecureentt
Run3
(tannn', 0), C'relu', 1), ('identity', 1), ('relu' 2). ('signoid', 2), ('identity', ' 4), ('relu', D. ('relu', 0)1, conc at=range 9))
Run4
Table 16: NASBench validation accuracy across the 36 settings for EPS. "#i" stands for the ich search run.
Setting
42
Avg. Acc.
P16., 5:32, M.L, [_aa::0
91.21
88.00
91.21
91.30
90.85
90.69 + 0.91
P:64, 5:32, M:1. 1_aat:000
90.84
91.53
91.22
90.99
0.44
P164, 5:32, MFL, I 220:200
91.00
89.15
90.54
88.23
91.51
90.09
1.21
P:64, 5:32, M:4,1 1_vat:50
91.05
91.21
91.21
91.50
90.93
91.18 1: 0.19
P164, 5:32, M434 I_vat:100
91.19
90.78
90.85
89.90
90.93
90.73 :: 0.44
P164, S532, M.A. 2.00000
91.05
91.00
91.19
91.42
91.17 $1.77:0011
P:64, S164, M.. I_ __00:500
91.02
90.85
90.92
89.84
91.03
90.73
= 0.45
P164, 8164, MFL. I T_aaE100
91.03
90.81
91.48
88.90
90.84
90.61
0.89
Pat:200
90.99
91.12
91.22
90.87
91.02
91.04
0.12
P:64, 5:64. M.4, I_ __a0:50
90.33
91.35
91.55
91.55
91:48
91.37 0,23
P:64, S:64, M444 I 1_va0:100
91.55
90.92
91.21
91.55
90.84
91.22 1: 0.30
P164, S104, M. L_aat2000
90.55
90.99
91.35
90.93
89.31
90.63
0.71
P:128, 8:32, M:1. 90o:50
91.01
91.36
90.42
91.42
89.37
90.72 0.76
P:128, 8:32, M:1. I 10l:100
91.45
91.06
90.59
91.37
91.28
91.15 1: 0.31
P,128, 8:32, M.1. I 2o02220
91.12
84.69
91.51
91.02
91.19
89.91 1: 2.61
P:128, M:4,
Lval:50
91.30
91.42
91.03
91.28
90.93
0.68
P:128, 8:32, M.4, I w0o:1000
91.35
90.93
91.61
91.34
91.36
91.36
0.24
P.128, 8:32, M:4. 1 Lool:200
91.19
91.35
90.55
91.42
91.01
91.11 + 0.31
PT12,, 5564, M:1. 1 Lo00550
91.03
90.95
91.19
91.53
88.77
90.09 0.98
P:128, 8:64, M:1. I 001:10
91.30
90.79
91.46
91.02
91.36
91.19 0.25
P:128, 5:64, M:1 I 2.01000
888.88
84.23
91.55
90.79
88.62
88.81 2: 2.55
P.128, 5364, Mc4, Lo00550
89.34
91.42
91.50
91.19
89.08
90.35
1.03
P.128, M.4 011100
0.20
P:128, 8:64, Mc4, L0000200
91.16
91.55
90.87
90:95
90.87
91.08 + 0.26
P:256, 9:32, Mc1. I Lo0:50
91.03
90.84
88.94
91.42
91.40
90.73
0.92
P:256, S:32, M:1. Loal:100
90.16
91.12
91.30
90.34
90.36
0.86
P:256, 5:32, M:1. f val:200
90.51
90.90
91.07
84.15
91.19
89.56
2.72
P:256, 5:32, M:4, I vol.30
91.42
91.22
91.28
91.18
90.84
91.19 2: 0.19
P:256, S532, M:4, [_o22:000
91.00
91.12
91.00
90.84
90.87
90.97
0.10
P:256, S:32, M:4, f val:200
90.77
91.03
91.22
91.01
91,21
91.05
0.16
P:256, S:64, M:1. T_ v011:0
91.50
91.30
91.53
91.55
88.90
90.96 4: 1.03
17226, S:64, M:1. [_aa::00
91.44
91.04
91.03
91.00
91.21
91.15 0.16
P:256, M.11 I 200:2000
0.28
P:256, S:64, M:4, f vo01:0
91.55
91.42
91.50
91.42
91.61
91.50 + 0.07
1:256, S:64, M:4, [_eal:100
91.28
91.42
91.42
89.23
91.28
90.93 0.85
P:256, 5:64, 1_p0::200
91.36
90.99
90.93
0.16
Table 17: DARTS search space testing accuracy. "#i" stands for the ien search run. "run i" stands for the ish validation training run.
Seitings
#1
#2
43
44
45
97.59
97.23
97.30
97.54
97.52
CIFAR-10
run 2
97.40
97.38
97.19
97.38
97.30
97.46
97.38
97.14
97.26
97.32
81.71
82.28
81.33
82.60
82.54
CIFAR-100
run 2
80.99
81.49
81.51
82.22
83.10
81.66
82.28
82.15
82.57
83.07
20

---

Under review as a conference paper at ICLR 2021
Table 18: DARTS sub search space testing accuracy. "#i" stands for the ich search run. "run i" stands for the leh validation training run.
CIFAR-IO
CIFAR-II
Setting
#1
N2
8.
V1
N2
83
#1
42
#3
run
97.04
97.08
97.44
78.26
75.59
75.11
97.61
97.52
97.42
51
2
97.01
97.05
97.35
77.46 77.46
75.69
75.24
97.50
97.56
97.51
run 3
97.02
97.13
97.36
77.92
75.82
74.19
97.58
97.45
97.43
96.83
82
2
96.74
96.70
96.81
77.76
78.06
77.70
97.21
97.33
97.50
run 3
96.68
96.73
96.84
79.14
78.18
77.74
97.43
97.55
97.55
97.53
97.37
97.32
78.42
77.97
77.13
97.38
97.58
83
run 2
97.41
97.26
97.32
78.18
76.94
77.27
97.43
97.43
97.53
97.44
97.37
97.50
78.62
77.70
96.55
95.48
96.39
75.61
76.65
18
97.18
97.40
97.18
$4
run 2
96.14
96.21
96.40
75.19
76.90
76.88 88
97.18
97.25
97.07
96.49
95.79
96.18
74.60
76.43
21


Reviews:
[{"review_id": "br1_AZschfU", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary:\\\nThis paper finds an assumption in neural architecture search (NAS) where \"performance estimated in a weight-sharing setting translates to actualy achievable performance\" only holds for uniformly sampled architecture but breaks down when sampling from top-performing architectures. As a result a new sampling method based on tournament selection for NAS is proposed.\n-----\n+Strengths\\\n+Novel insights are revealed for NAS work which may be useful for future research.\n+Clear experiments are devised to demonstrate the insights.\n+Strong experiment and ablation results compared to prior NAS approaches.\n-----\n-Concerns\\\n-My biggest question here would be how the best architecture from EPS compare to other NAS-based models that are successfully adopted in a wide range of vision application, such as EFficientNet. It would be interesting to show performance on larger dataset.\n-I am also interested to know the range of performance between best and worst for top 100/60/20% of models to better understand how poorly correlated top architectures in GS actually translate to loss in performance beyond performance of the final architecture.\n-----\nRecommendation\\\nTo my best knowledge, this paper uncovers some interesting insight and show performance improvements. My main concern is the viability of the proposed structure in more practical vision problems such as recognition on larger dataset. My recommendation is leaning towards weak accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WTd3nt-wddt", "reviewer": "AnonReviewer1", "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": "This paper claims that random search-based NAS methods show a low ranking correlation among top-20% candidate architectures in the search phase. To address this issue, this paper proposes to introduce a proxy search space consisting of good architectures and evolve it using evolutionary algorithms. This paper also proposes a simple size regularization to help the NAS algorithm escape from the small architecture traps. The experimental results show that the proposed approach achieves competitive performance with baseline methods.\n\nPros\n- This paper analyzes the behavior in the random search-based NAS in detail and proposes a new strategy based on the observation to tackle the issue.\n\nCons\n- The proposed method should be compared with recent NAS methods to clarify the contribution of this paper. Many related studies are missing.\n- The details of the algorithm of EPS are unclear. For example, it's not clear what exactly is being done in the RandomInitArch and Mutate operations. Also, what is the reason for using sample_set instead of population queue?\n- What do you mean by the population is a proxy search space on page 4? Does the proxy search space mean a specific architecture without over parameterization or an over parameterized architecture? Please elaborate on the definition of the proxy search space and each population.\n- In section 2, the authors give an analysis on random search-based NAS, but does this hold for other conditions such as for the search space used in DARTS and Robust DARTS?\n\nOverall, the analysis in this paper is interesting, but there are some unclear points to be clarified for publication as mentioned above. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GXoIMZKdE4-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Motivated by exploring the ranking correlations of the existing RandomNAS in NASBench-201, this paper proposes EPS to improve the search efficiency and keep good ranking correlations by evolving the proxy search space (PS) in RandomNAS. Specially, EPS contains three stages: 1) training the supernet in PS, 2) validating the architectures among the PS and 3) evolving the PS by tournament selection with the aging mechanism. Furthermore, a model-size-based regularization is introduced in the selection stage. Experiments on some popular benchmarks demonstrate the effectiveness of the method.\n\nStrengths\n1) The paper is well written and easy to follow. The algorithm procedure is clearly provided and the code is released.\n2) Some empirical evidences are provided to explain the limitations of the existing RandomNAS.\n\nWeaknesses\n1) Lack of novelty. One the one hand, EPS seems a combination of [1] with a weight-sharing supernet, and the differences 2,3,4 with CARS do not convince me well. Except for the motivation and the fitness in EA, EPS and CARS are highly similar. One the other hand, the intuition of the solutions for the limitations which the authors presented in Sec. 2 is not clearly provided. From my view, Q_pop in Algorithm 1 is same with the population in EA methods. The proxy search space is not clearly explained.\n2) How to choose the 4000 architectures from RandomNAS in Fig. 2(a)?\n3) EPS validates each architecture only on a single batch. Dose one batch validation bring biases to the performance and the ranking evaluation of the architectures? Does the phenomenons in Sec. 2 are caused by one batch validation due to the biases? Comparison with Full batches validation (the whole validation set) should be considered.\n4) Results on PTB are not promising. RandomNAS (RSPS) achieves better perplexity with less search cost.\n5) “32 x 5 runs” and “32 settings” should be “36 x 5 runs” and “36 settings”, respectively.\n\nThe novelty and the similarity with previous works are my main concerns. I am currently leaning towards a negative score but would like to see the authors' responses and other reviewer's comments.\n\n[1] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0AZt0pjH9uJ", "reviewer": "AnonReviewer4", "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": "This paper proposes Evolving the Proxy Search Space (EPS) as a new RandomNAS-based approach. The goal is to find an effective proxy search space (PS) that is only a small subset of GS to dramatically improve RandomNAS’s search efficiency while at the same time keeping a good correlation for the top-performing architectures. EPS runs in three stages iteratively: Training the supernet by randomly sampling from a PS; Validating the architectures among the PS on a subset of the validation dataset in the training interval; Evolving the PS by a tournament selection evolutionary algorithm with the aging mechanism.\n\n\nThe paper is well written and easy to follow. The idea of efficiently sampling from the search space sounds interesting and the paper aims to bring the help of search strategies to construct the search space by itself. However, it is kind of incremental work since the EPS (Algorithm 1) is exactly similar to the aging evolution in Real et al. (2018, 2019) and this paper is using this search strategy to gradually build the search space on the fly. \n\nI think any of the existing search strategies 1) random search 2) Evolutionary algorithms (Real et al. (2018)) 4) progresive decision process (PNAS; Liu, et al 2018), etc can be used to find a proxy search space. While a random sample from GS is simply random search, proposed EPS is exactly the evolutionary strategy to build search space. One may even use progressive NAS algorithm as a proxy search space!  Comparing how these different proxy search spaces improve efficiency will improve the novelty and make the paper more strong.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes the behavior of random search-based NAS and provided new insights (e.g., a low ranking correlation among top-20% candidate architectures in the search phase). An extensive set of experiments were also conducted. However, most reviewers found the incremental nature and similarity with previous works to be a concern. I would encourage the authors to better position their work and better explain the novel methodological aspects.

Decision: Reject