Weak NAS Predictor Is All You Need
Authors: Junru Wu
Xiyang Dai
Dongdong Chen
Yinpeng Chen
Mengchen Liu
Ye Yu
Zhangyang Wang
Zicheng Liu
Mei Chen
Lu Yuan
Venue:  (2021)
Keywords: performance predictor
neural architecture search

Abstract: Neural Architecture Search (NAS) finds the best network architecture by exploring the architecture-to-performance manifold. It often trains and evaluates a large amount of architectures, causing tremendous computation cost. Recent predictor-based NAS approaches attempt to solve this problem with two key steps: sampling some architecture-performance pairs and fitting a proxy accuracy predictor. Existing predictors attempt to model the performance distribution over the whole architecture space, which could be too challenging given limited samples. Instead, we envision that this ambitious goal may not be necessary if the final aim is to find the best architecture. We present a novel framework to estimate weak predictors progressively. Rather than expecting a single strong predictor to model the whole space, we seek a progressive line of weak predictors that can connect a path to the best architecture, thus greatly simplifying the learning task of each predictor. It is based on the key property of the predictors that their probabilities of sampling better architectures will keep increasing. We thus only sample a few well-performed architectures guided by the predictive model, to estimate another better weak predictor. By this coarse-to-fine iteration, the ranking of sampling space is refined gradually, which helps find the optimal architectures eventually. Experiments demonstrate that our method costs fewer samples to find the top-performance architectures on NAS-Bench-101 and NAS-Bench-201, and it achieves the state-of-the-art ImageNet performance on the NASNet search space.

Under review as a conference paper at ICLR 2021
WEAK NAS PREDICTOR Is ALL YOU NEED
Anonymous authors
Paper under double-blind review
ABSTRACT
Neural Architecture Search (NAS) finds the best network architecture by explor- ing the paniieccurrttt-perffrmancc manifold. It often trains and evaluates a large amount of architectures, causing tremendous computation cost. Recent predictor- based NAS approaches attempt to solve this problem with two key steps: sam- pling some cechitecture-performmat Existing predictors attempt to model the performance distribution over the whole architecture space, which could be too challenging given limited samples. Instead, we envision that this ambitious goal may not be necessary if the final aim is to find the best architecture. We present novel framework estimate weak predictors progressively. Rather than expecting a single strong predictor to model the whole space, we seek progressive line of weak predictors that can connect a path to the best architecture, thus greatly simplifying the learning task of each predictor. is based on the key property of the predictors that their probabilities of sampling bet- ter architectures will keep increasing. We thus only sample few well-performer architectures guided by the predictive model, to estimate another better weak pre- dictor. By this coarse-to-fine iteration, the ranking of sampling space is refined gradually, which helps find the optimal architectures eventually. Experiments demonstrate that method costs fewer samples to find the oop-erformance ar- chitectures on NAS- AAS-Benchmark-101 and WAS-Benchmark-200 and it achieves the state-of-the-art ImageNet performance on the NASNet search space.
pairs and fitting proxy accuracy predictor.
INTRODUCTION
Neural Architecture Search (NAS) has become central topic in recent years with great progress (Liu
ct al.
2018b Luo et al. 2018 | Wu et al. 2019 Howard et al.) 2019 Ning et al. 2020 Wei et al.]
2020
Luo al. 2018 Wen et al. 2019
Chau al.) 2020 Luo al.) 2020). Methodologicallyy
all existing NAS methods try to find the best network architecture by exploring the architecture-to performance manifold, such as reinforeed-leamingg based (Zoph Le 2016). evolution- (Real
et al. 2019) or mendient-based]]
et al. (2018b) approaches. In order to cover the whole space, they often train and evaluate a large amount of architectures, thus causing tremendous computation cost.
Recently, predictor-based NAS methods alleviate this problem with two key steps: one sampling step to sample some
pairs, and another performance modeling step to fit the performance distribution by training a proxy accuracy predictor. An in-depth analysis of existing
methods (Luo et al. (018)) founds that most of those methods (Ning et al., 2020;; Wei et al.) 2020) Luo et al. 2018 Wen al.) 2019; Chau al. 2020 Luo et al. 2020) attempt to model the perfor- mance distribution over the whole architecture space. However, since the architecture space is often exponentially large and highly non-convex, modeling the whole space is very challenging especially given limited samples. Meanwhile, different types of predictors in these methods have to demand handcraft design of the architecture representations improve the performance.
In this paper, we envision that the ambitious goal of modeling the whole space may not be necessary if the final goal is find the best architecture. Intuitively, we assume the whole space could be divided into different sub-spaces, some of which are relatively good while some are relatively bad. We tend choose the good ones while neglecting the bad ones, which makes sure more samples will be used to model the good subspace precisely and then find the best architecture. From another perspective, instead of optimizing the predictor by sampling the whole space as well as existing methods, we propose to jointly optimize the sampling strategy and the predictor learning, which helps achieve better sample efficiency and prediction accuracy simultaneously.

---

Under review as a conference paper at ICLR 2021
Based the above motivation, we present novel framework that estimates a series of weak predictors progressively. Rather than expecting a strong predictor to model the whole space, instead seek a progressive evolving of weak
Weak Predictors
Best Vallidation Accuracy
46.4
predictors that can connect a path to the best ar- chitecture. this way, it greatly simplifies the
46.2
learning task of each predictor. To ensure mov-
46.0
Previous Strong Predictor
ing the best architecture along the path, we in- crease the sampling probability of better archi- tectures guided by the weak predictor at each iteration. Then, the consecutive weak predictor with better samples will trained in the next iteration. We iterate until we arrive at bedding subspace where the best architectures reside. The weak predictor achieved at the fi- nal iteration becomes the dedicated predictor focusing on such fine subspace and the best performed architecture can be easily predicted.
45.8
45.6
45.4
0
2000
4000
6000 8000 10000 12000 14000 Number Samples
Figure 1: Comparison between iterative weak pre- dictors and non-iterative strong predictor on NAS- Bench-201 ImageNet subset. Our method signif- icantly reduces the needed amount of samples to reach the optimal architecture.
Compared existing predictor-based NAS, our method has several merits. First, since only weak predictors are required locate the good subspace, it yields better sample efficiency. On NAS- WMS--enchhmark- 101 and MaSS-Benchmar--200 it costs significantly fewer samples to find the rop-performance architecture than existing predictor- based NAS methods. Second, it is much less sensitive to the architecture representation (e.g.. dif- ferent architecture embeddings) and the predictor formulation design (e.g.. MLP, Gradient Boosting Regression Tree, Random Forest). Experiments show our superior robustness in all their combina- tions. Third, it is generalized to other search spaces. Given a limited sample budget, it achieves the mate-of-the-art ImageNet performance the NASNet search space.
OUR APPROACH
2.1
REVISIT PREDICTOR BASED NEURAL ARCHITECTURE SEARCH
Neural Architecture Search (NAS) finds the best network architecture by exploring the architecture- to to-performance manifold. can be formulated as an optimization problem. Given a search space of network architectures X and discrete from architecture set X to performance set P, the objective is to find the best neural architecture xx with the highest performance fzx in the search space X:
-otecturr-tt-eeffomannee mapping function X - P
arg max f (xx xEX
naive solution is to estimate the performance mapping fax through the full search space, how- ever, is prohibitively expensive since all architectures have be exhaustively trained from scratch. To address this problem, predietor-based NAS learns proxy predictor f(x: to approximate f(x: using some architecture-performe performaccceeeeeeeeeeeeeee pairs, which significantly reduces the training cost. In general, predictor-based NAS can be formulated as:
x² = arg max / (x]S) zEX
s.t. f arg min Σ ((f(s). S./EF sES
where L is the loss function for the predictor f. F is a set of all possible approximation to f. S : {S C X [S] < C} is the training pairs for predictor ff given sample budget C. Here, C' is directly correlated to the total training cost. Our objective is to minimize the loss L of the predictor based on some sampled architectures S.
2

---

Under review as a conference paper at ICLR 2021
Previous:
Proposed:
Top 7 Samples
Sample Space S
Sample Space
Search Spaci
Search Space X
Sampling
learning
Sampling
Learning
Predicted
Weak Predictors fz
Strong Prodictor
Performance on
Iteration
Ground-Truie Trund--Trthhho Azzuraty
Gooide Irudh Aocuracy
Architecture
Architecture
Optimal A Sampled Sample Space
Excluded
Figure 2: An illustration of our progressive weak predictors approximation (best viewed in color). Previous predictor-based NAS uniformly sampled the whole search space to a strong predic- tor; Ours progressively shrink the sample space smaller based predictions from previous weak predictors and train new weak predictor towards subspace of better architectures
Previous predictor-baseeeeeeeeppeeeeeeaae NAS methods attempt to solve Equation with with two key steps: (1) sampling some architecture- perprrrmree-eeeoomaeeeeeeeee pairs and (2) learning proxy accuracy predictor. First, a common practice in previous work is sample training pairs S uniformly from the search space X to learn the predictor. Such a sampling is inefficient considering that the goal of NAS is to find a subspace of well-performed architectures in the search space. A biased sampling strategy towards the well- performed architectures can be more desirable. Second, given such pairs S, previous predictor-based
NAS uses a predictor f to model the performance distribution over the whole architecture space. Since the architecture space often enormously large and highly non-convex, is too challenging to model the whole space given the limited samples.
2.2 PROGRESSIVE WEAK PREDICTORS APPROXIMATION
We envision that the above ambitious goal may not be necessary if the final aim of NAS is to find the best architecture. We argue that sampling S and learning f should be co-evolving instead of time deal as done in existing predictor-based NAS. Demonstrated in Figure rather than expecting single strong predictor model the whole space at one time, we progressively evolve our weak predictors to sample towards subspace of best architectures, thus greatly simplifying the learning task of each predictor. With these coarse-to to-fine fine iterations, the ranking of sampling space refined gradually, which helps find the optimal architectures eventually.
Thus, we propose a novel coordinate descent way to jointly optimize the sampling and learning stages in predictor-based NAS progressively, which can be formulated as following:
Sampling Stage:
p = (fe(s)(s E X S*}
(3)
Sk+1 arg max (k) Sk 7
(4)
Learning Stage:
x² = arg max f(x]s++1) zex
(5)
s.t. s.t.fk+1 arg min
Σ ((f(s)
hef sESKI1
Suppose iterative methods has K iterations, k-th iteration where h: 2, K, initialize training set S by randomly sampling few samples from X to train an initial predictor fi- We then jointly optimize the sampling set S and predictor fr. in progressive manner for K iterations.
3

---

Under review as a conference paper at ICLR 2021
Sampling Stage We first sort all the architectures in the search space X according its predicted performance Ps at every iteration k. Given the sample budget, we then sample new architectures Sk+1 among the top T ranked architectures.
Learning Stage We learn a predictor f where we want minimize the the loss L of the predictor flr based on sampled architectures S We then evaluate all the architectures X in the search space using the learned predictor f to get the predicted performance pk:
Progressive Approximation Through the above alternative iteration, the predictor f would guide the sampling process to gradually zoom into the promising architecture samples. addition, the good performing samples 5 sampled from the promising architecture samples would in term improve the performance of the predictor fk+1 in the well-performed architectures.
To demonstrate the effectiveness of our iterative scheme, Figure (a) shows the progressive pro- cedure of finding the optimal architecture x" and learning the predicted best architecture ž over iterations, As we can see, the optimal architecture and the predicted best one are moving towards each other closer and closer, which indicates that the performance of predictor architecture(s) is growing better. In Figure 3)),, we use the error empirical distribution function (EDF) proposed in (Radosavovic al. 2020) visualize the performance distribution of architec- tures in the subspace. We plot the EDF F of the top-200 models based on the predicted performance over 5 iterations. As shown Figure 3 (b), the subspace of top-perfonee pe-peeformedd architectures is consis- tently evolving towards more promising architecture samples over 5 iterations. In conclusion, the probabilities of sampling better architectures through these progressively improved weak predictors indeed keep increasing, as we desire them to.
the optimal
Search Dynamics
EDF
1.0
73-
Ground-Trulh Accruacy
72
0.6
71
plob
0.4
Iteration
Iteration
Iteration
0.2
Iteration
Iteration
Optimal
Iteration
Iteration
Predicted Besi
Iteration
lteration
71
72
28
Predicted Accruacy
errar
(b)
Figure 3: Visualization of the search dynamics. (a): The trajectory of Predicted Best architecture and Global Optimal through out 5 iterations; (b): Error empirical distribution function (EDF) of predicted Top 200 architectures through out 5 iterations
2.3 GENERALIZABILITY ON PREDICTORS AND FEATURES
Here we analyze the generalizability of our method and demonstrate its robustness on different predictors and features. In predictor-based NAS, the objective of learning the predictor f can be formulated regression problem (Wen et al.] 2019) choice of predictors diverse, and usually critical to final performance (e.g. MLP (Ning al. 2020 Wei et al. 2020). LSTM (Luo al. 2018), GCN (Wen et al. 2019 Chau al. 2020). Gradient Boosting Tree (Luo et al. 20200). To illustrate our framework generalizable and robust to the specific choice of predictors, compare the following predictor variants.
ranking (Ning et al. (2020) problem. The

---

Under review as a conference paper at ICLR 2021
Multilayer perceptron (MLP): is the baseline commonly used in predictor-based NAS (Ning et al. 2020) due to its simplicity. Here we use a 4-layer MLP with hidden layer di- mension of 10000, 1000, 1000, 1000) which is sufficient to model the architecture encoding.
Gradient Boosting Regression Tree (GBRT): Tree-based methods have recently been pre- ferred in predictor-based NAS (Luo al. 2020: Siems al. 2020) since it is suitable to model discrete representation of the architectures. Here, we use the Gradient Boosting Regression Tree based on XGBoost (Chen & Guestrin, 2016) implementation.
Random Forest: Random Forrest is another variant of tree-based predictor, it differs from Gradient Boosting Trees in that combines decisions the end instead along each hierarchy, and thus more robust to noise.
The selection features to represent the architecture search space and learn the predictor is also sensitive to the performance. Previous methods tended hand craft the feature for the best perfor- mance (e.g., raw architecture encoding (Wei et al. 2020). supernet statistic (Hu et al.) 2020)). To demonstrate our framework is robust across different features, we compare the following features.
One-hot Vector: In NAS-Bench-201 (Dong & Yang 2020). its DART style search space fixed the graph connectivity, so one-hot vector used encode the choice of operator.
Adjacency Matrix: In MAS-Bench-lee 101c we used the encoding scheme as well (Ying) et al.) 2019; Wei et al., 2020), where 7x7 adjacency matrix represents the graph connec- tivity and 7-dimensional vector represents the choice of operator, every node.
4..6
97.1
Beet 10 Sccumnry
012
0..
90.6
00.6
RardowForet
Randorforeet
Rondorffome
00.
.... orace
NL*
orade
44.0
oncll
100
300
332
StD
200
500
420
1:0
202
Namtber of Sampphes
Number of Samrlee
Mumber Samp
(a) CIFARIO
(b) CIFARIO0
(c) ImageNet166120
Figure 4: Evaluations of robustness across different predictors on NAS-Bench-
94.3
Ted Aocuenty
06.3
95.4
Hardom Search
Random Search
CBRT
CBRT
BandorForee
Ran dorffforsst
01.2
stuci
1000
2003
1000
102b
5050
1003
2000
1201
$500
5200
Number Saimples
Mumbbor Samplies
(a) CIFARIO Validation Set
(b) CIFARIO Test Set
Figure 5: Evaluations of robustness across different predictors NAS-Bench- 101
We compare the robustness across different predictors under our framework shown in Figure We can see that all predictors perform similarly among different target datasets. As shown in Figure with Figure 5 although different architecture encoding methods are used, our method can perform similarly well among different predictors, which demonstrates that our proposed method is robust different predictors and features selection.
5

---

Under review as a conference paper at ICLR 2021
3 EXPERIMENTS
3.1 SETUP
NAS- MAS-Bench-101 (Ying al. 2019) is one of the first datasets used to benchmark NAS algorithms. The dataset provides a Directed Acyclic Graph (DAG) based cell structure, while (1) The connectiv- ity of DAG can be arbitrary with a maximum number of 7 nodes and edges (2) Each nodes on the DAG can choose from operator of 1 1xl convolution, x convolution or x max- max-pooling. After removing duplications, the dataset consists of 423,624 diverse architectures trained CIFAR10 dataset with each architecture trained for trials.
NAS-Rench-201 (Dong & Yang 2020) is another recent NAS benchmark with reduced DARTS- like search space. The DAG of each cell fixed similar to DARTS(Liu et al.] 2018b). however can choose from different operations (1x1 convolution, 3x3 convolution, 3x3 avg-pooling, skip, no connection) on each of the 6 edges totaling a search space of 15,625 architectures, The with each archi-
dataset trained on different datasets tecture trained for 3 trials.
For experiments on both benchmarks, we followed the same setting as (Wen et al. 2019). We use the validation accuracy search signal, while test accuracy is only used for reporting the accuracy on the model that was selected at the end of search. Since the best performing architecture on the validation and testing set does not necessarily match, we also report the performance on finding the oracle on the validation set of our NAS algorithm in the following experiments.
we follow the same NASNet search space used in (Zoph et al. 2018) to directly search for best-performing architectures on ImageNet. Due to the huge computational costs needed to train and evaluate architecture performance on ImageNet, we leverage weight-sharing supernet approach (Guo et al. 2019) and use supernet accuracy as a performance proxy indicator.
Open Domain Search:
3.2 COMPARISON
(SOTA) METHODS
We evaluate our method on both NAS-Bench- 101 and NAS- NAS-Bench-201. We also apply our method to open domain search directly ImageNet dataset using NASNet search space.
NAS-Bench-101
We conduct experiments the popular NAS- Ben--ennhhhhe 101 benchmark and compare with multiple popular methods (Real et al.) 2019: Wang et al. 2019b a Luo et al. 2018 Wen et al.] 2019). We first study the performance by limiting the number of queries. In Taall 1 vary the number of queries used in our method by changing the number of iterations. It is clear to see that, the searched performance consistently improves as more iterations are used. When compared to the results from popular predictor-based NAS methods, such as NAO (Luo et al. (018) and Neural Predictor (Wen) al. 2019), our method (a) reaches higher search performance provided with the same query budget for training; and (b) uses fewer samples towards the same accuracy goal.
We then plot the best accuracy against number of samples in Figure to show the sample efficiency on both validation and test set of MAS-Bench-1l we can see that our method consistently requires fewer sample reach higher accuracy, compared to Random Search and Regularized Evolution.
Finally, Table 2 shows that our method significantly outperforms baselines in terms of sample effi- ciency. Specifically, our method costs 44x, 20x, 17x, and 2.66 less samples to reach the optimal architecture, compared to Random Search, Regularized Evolution (Real et al. 2019). MCTS (Wang ct al. 2019b), LaNAS (Wang et al. 2019a). respectively.
NAS-Bench-201
We further evaluate our method on NAS-Bench-201. Since relatively newly released, we com- pare with two baseline methods Regularized Evolution (Real et al.) 2019) and random search using our own implementation. Shown in Table 3 we conduct searches on three subsets (CIFARIO, 10, CIFAR 100, ImageNet16- 120) and report the average number of samples needed reach global op- timal over 250 runs. It obvious to see that our method requires the minimum number of samples among all settings.

---

Under review as a conference paper at ICLR 2021
Table 1: Comparsion SOTA on NAS-Bench- 101 by limiting the total amount of queries
Method
#Queries
Test Acc.(%)
SD(%)
Test Regret(%)
Random Search
2000
93.64
0.25
0.68
NAO (Luo et al.
2018
2000
93.90
0.03
0.42
Reg Evolution Real et al.
2019
2000
93.96
0.05
0.36
Neural Predictor (Wen et
2019
2000
94.04
0.05
0.28
Ours (Non-iterative)
2000
93.92
0.082
0.04
Ours (1 iteration)
100
93.47
0.183
0.85
Ours (4 iterations)
400
94.15
0.146
0.17
Ours (10 iterations)
1000
94.20
0.077
0.12
Ours (20 iterations)
2000
94.22
0.028
0.10
95.2
93.0
94.2
Bes: Vea d8000 Accumicy
Accurace
04.2
94.0
54.6
94.0-
Searth
Search
legularteed Evalution Dur
45.
Regularteed Evalution Curs
orode
93.6
oracle
500
1300 1500 2000 2500 3000 3000 4000
500
1000
1300 2000
2500 3000 3300 4000 Number of Samples
Number of Samples
(a) CIFAR10 Validation
(b) CIFAR10 Testing
Figure 6: Comparison to SOTA on NAS-Bench-101 by varying number of samples. Central lines demonstrate the average, and the shade regions depict the confidence intervals
Table Comparison on the number of samples required to find the global optimal architecture over 100 runs on NAS-Bench-100
Method
#Queries
Random Search
188139.8
Reg Evolution (Real et al.
2019
87402.7
MCTS (Wang et al. 201 9b)
73977.2
LaNAS Wang et al.
2019a
11390.7
Ours
4275.3
We also conduct controlled experiment by varing the number of samples. As Figure 7 our average performance over different number of samples yields clear gain over Regularized Evolu- tion (Real et al., 2019) in three subsets. Our confidence interval is also tighter than Regularized Evolution, showcasing our method's superior stability/reliabiiity.
Open Domain Search
In order to demonstrate our method's generalizability. we further apply to open domain search without ground-truth We adopt the popular search space from NASNet and compare with several
popular methods (Zoph et al.] 2018 Real et al. 2019 Liu et al. 2018a Luo et al. 2018) with the utilization of number of samples reported. Shown in Table 5 it is clear to see that, using fewest samples among all, method achieves state-of-te of-te-of-the-ar ImageNet top-1 emro with similar number of parameters and FLOPs. Our searched architecture also competitive to expert-design networks. Comparing with the previous SOTA predictor-based NAS method (Luo al. 2018), method

---

Under review as a conference paper at ICLR 2021
Table Comparison on the number of samples required to find the global optimal over 250 runs on NAS-Bench-201
Method
CIFARIO
CIFARI00
ImageNet16-122)
valid
test
valid
test
valid
test
Random Search
7873.98
7782.12
7716.85 399.78
7621.24 438.24
7776.55
7726.15
Reg Evolution (Real al. 2019
478.41
563.25
802.57
715.12
Ours
119.17
186.30
86.08
89.26
159.33
176.61
01.7
66.4
46.0
12.0
65.8
Bardam Search Regularteed
Barden Search
40.6
Bardan Sourch
Regularond Sycletion
Regularbed
45.4
250
.012
2001
(a) CIFARIO
(b) CIFAR100
(c) ImageNet16-120
Figure 7: Comparison to SOTA on NAS-Bench-200 by varying number of samples. Central line demonstrates the average, shade demonstrates the confidence interval
reduces 0.9% top-1 error, using the same number of samples, which is significant. This experiment well proves that our method robust, generalizable, and can effectively applied to real-world open domain search.
Table 4: Compared to SOTA results on ImageNet using NASNet search space
Method
#Qucries
Top-1 Err.
Top-5 Err.
Params(M)
FLOPs(M)
MobileNetV2 ShuffletNetV2 EfficieenNett-OO
Manual
25.3
6.9
585
Manual
25.1
5.0
Manual
23.7
6.8
5.3
390
NASNet-A (Zoph et al.
2018
20000
5.3
564
AmochaNct-A (Real et a
2019
10000
25.5
8.0
5.1
555
PNAS (Lu ct al. 201 8a
1160
25.8
8.1
5.1
588
NAO (uuo 2018
1000
24.5
7.8
6.5
590
Ours
1000
23.6
6.8
5.9
597
4 CONCLUSION
In this paper. we present novel predictor-based NAS framework that progressively shrinks the sampling space, by learning series of weak predictors that can connect towards the best architec- tures. We argue that using a single strong predictor to model the whole search space with limited samples may be too challenging a task and seemingly unnecessary. Instead by co-evolving the sam- pling stage and learning stage, our weak predictors can progressively evolve to sample towards the subspace of best architectures, thus greatly simplifying the learning task of each predictor. Exten- sive experiments on popular NAS benchmarks prove that proposed method is sample-efficies robust various combinations of predictors and architecture encoding means. We further apply method to open domain search and demonstrate its generalization. Our future work will investigate how to jointly the predictor and encoding in our framework.
and
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Thomas Chau, Lukasz Dudziak, Mohamed S Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas D Lane. Brp-nas: Prediction-basee nas using gens. arXiv preprint arXiv:2007.0886 2020.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
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, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architec- ture search. In International Conference on Learning Representations, 2020. URL https:
77 //openreview net festt/foummme (ttp//ooommm...--yYYXXXXA
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 preprint 1rXh::1904.00420, 2019.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chiel Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Pro- ceedings of the IEEE International Conference on Computer Vision, pp. 1314-1324, 2019.
Yiming Hu, Yuding Liang, Zichao Guo, Ruosi Wan, Xiangyu Zhang, Yichen Wei, Qingyi Gu, and Jian Sun. Angle-based search space shrinking for neural architecture search. arXiv preprint arXiv:2004. 13431, 2020.
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 Proceed- ings of the European Conference on Computer Vision (ECCV), pp. 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 1006.0005, 2018b.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. In Advances in neural information processing systems, pp. 7816-7827, 2018.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu. Neural architecture search with gbdt. Xrxiv preprint arXh::2007.0478. 2020.
Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-based neural architecture encoding scheme for predictor-based nas. arXiv preprint urXiv:2004.0189% 2020.
Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10428-10436, 2020.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780 4789, 2019.
Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008. 009772008.09777. 2020.
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning action space, 2019a.
Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. Alphax: explor- ing neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv: 1903. 1059, 2019b.

---

Under review as a conference paper at ICLR 2021
Chen Wei, Chuang Niu, Yiping Tang. and Jimin Liang. Npenas: Neural predictor guided evolution for neural architecture search. arXiv preprint arXiv:2003. 12857. 2020.
Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. arXiv preprini
2019.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang. Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangging Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 10734-10742, 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint 1tti:/./2229920.. 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 FrXiv:1907.0573:3 2019.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- b0nch-101: Towards reproducible neural architecture search. International Conference on Machine Learning, pp. 7105-7114, 2019.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint 16110155 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc 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.
10

---

Under review as a conference paper at ICLR 2021
A MORE COMPARSION ON NASNET SEARCH SPACE
In Table we show more comparsion to representative Gradient-based methods including
XNA al. 2018), DARTS et al. 2019), DS-NAS et al. 2019).
2018b), P-DARTS al. 2019), PC-DARTS(XU
Table 5: More Comparsion to SOTA results on ImageNet using NASNet search space. WS denote Weight-Sharing
Model
Methods
*Queries
Top-1 (m((S)
Top-5 Em((%)
Params(M)
FLOPsMM
GPU Days
MobileNetV2
25.3
6.9
585
ShariletNerV2
Manual
25.1
5.0
591
EloccienNet-B0
6.8
SNASOXie all
2018
27.3
9.2
4.3
522
DARTS
20TX0
26.9
9.0
4.9
595
4.0
Gradicut-bosed
PC-DART Stall di 2019
24.2
7.3
597
3.8
DS-NAS
2019
24.2
7.3
5,3
597
10.4
Zaph
AmochaNet-A Real
2019
Sample hased
10000
25.5
8.0
5.1
555
3150
PNAS Liu
1160
25.8
8.1
5.1
588
200
Ours
Sample-bsed WS
1000
23.6
6.8
5,9
597
1.08
B VISUALIZATION OF NASBENCH SEARCH SPACE
Figure illustrates the histogram of architecture performance in NASBench-101/22 also company a zoomed in view of the histogram, those histograms clearly show that the NAS search spaces bias heavily towards good performing architectures.
Kntlbach Olavved
8ww.berch ISBIAA (Zeared
1200
1300
4330
2330
125.
12.0
NASBench-101
(b) NASBench-201
Figure 8: (a) Histogram of Architecture Performance in NASBench-101 (b) Histogram of Architec-
ture Performance NASBench-201 (CIFAR10)


Reviews:
[{"review_id": "xptymNNtxpa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall this work moves into the right direction of trying to improve the performance of predictors. \n\nPros:\n\n- The paper provides experiments on different datasets, and evaluates different predictors to validate the approach. \n\n- The approach seems to have a significant speedup on the search time, but I would also like to see the results in terms of GPU days which is a common metric. \n\nCons:\n\n- In a space where there is rapid progress and accuracy alone is not a practical metric for real-world applications since neural networks are used widely today from data centers to mobile devices. More effort should be towards this multi-objective problems considering also memory and computational cost. In this respect I find this a weakness of the paper in that it does not address these factors which would make the problem much more interesting, even though the proposed approach is appealing. \n\n- A broader comparison should be made with DARTs approaches that have been shown to be generally faster. Also how does the approach compare with DSNAS: Direct Neural Architecture Search without Parameter Retraining in terms of efficiency?\n\n- The setup and hardware used to evaluate the approach is not reported. \n\n- Please correct for typos and grammatical mistakes, e.g., end of page 2 \"the the loss\", page 5 \"our method can performs\"\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kUFXa0Os92c", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros:\n- A progressive method for neural predictor-based NAS is proposed, and it shows better performance than previous methods.\n- Experiments on the NAS-bench-101 and NAS-bench-201, as well as on the NASNet search space to validate the effectiveness of the method.\n- The proposed method is conceptually simple and efficient.\n\nCons:\n- This work is more like an incremental improvement to the neural predictor. It gets a small performance improvement by learning in a maybe better subspace.\n- Is it effective to simply choose TopK models? As the author said, the learning space is not convex thus TopK samples may contain many local-optima and make the learning of predictor difficult even failure (all the predicted Accs fall within a small range).\n- In Fig. 1, why is there a sudden increase for the strong predictor (at near 15625 samples.)\n- What if the search space is huge, like 10^20 in many SOTA NAS search space, rather than the small models in NAS-Benchs, the proposed method seems inefficient in this case. Will it still work?\n- What's the difference and advantages between the proposed model, and choosing the top 10% of the models and training a single predictor?", "extra_scores": {}, "extra_text": {}}, {"review_id": "flTv2z2U-bl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an idea of jointly optimizing the sampling policy and predictor in NAS. With this method, we avoid to train a predictor which performs well on the whole search space and search a model with less queries.\n\n### advantages\nThe authors propose that training a good accuracy predictor for models in the whole search space is difficult. Thus, the paper focuses on a predictor that works in a small range, then optimizes the sampling policy as well as the predictor to yield a good structure.\n\nCompared with some evolution-based and RL-based methods, the algorithm observes a better model with less queries.\n\nTotally speaking, the idea is very interesting and it does ease the search process. \n\n### Weaknesses\nA weakness of the paper is that it does not compare with differentiable methods such as DARTS. It is well known that differentiable methods are nearly the fastest methods now and yield not bad results.\n\nAs the results show, the algorithm finds a good model on ImageNet with 1000 queries, which seems to take more time than differentiable methods.\n\n### Question\n1. For each query, do we need to train the model till convergence?\n2. How much time it takes to yield a good model (i.e., time for 1000 queries)?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_Dw94RpI7SE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of contribution: The authors propose an interesting approach to address the sample-efficiency issue in Neural Architecture Search (NAS). Compared to other existing predictor based methods, the approach distinguishes itself by progressive shrinking the search space. The paper correctly identifies the sampling is an important aspect in using a predictor based NAS method;\n\nThe writing is clear and easy to follow. The author provided an explanation of how their algorithm works, evaluate the algorithm on both NASBench-101 and NASBench-201, and show their methods work in practice on both\n\nSome critiques:\n\n1. Questions on predictor methods:\n\nI understand the NAS community has accepted many predictor based paper in major conferences, but it seems NAS is re-making the wheel in derivative-free optimizations, e.g. Bayesian Optimization, Evolutionary Algorithm, and MCTS. The predictor is essentially the surrogate model in Bayesian Optimizations, however, the current predictor methods simply ignore the acquisition function in BO that makes the trade-off between exploration and exploitation. These predictor paper in NAS basically suggest the acquisition functions are not necessary, and we can achieve great performance without that (e.g. on NASBench, I will come to this later). Apparently this predictor trend in NAS community is against the decades of development of Bayesian Optimization. If the authors believe the development in BO community is wrong, please justify that using acquisition is indeed not important, i.e. exploration is not necessary, with extensive experiments.\n\nIf the new experiment can persuade me, I believe this paper can be top 1% paper, and I will argue for accepting it.\n\nHere I'd like to list a set of predictor based paper that I have seen in the NAS community: \n\n[1] Bridging the Gap between Sample-based and One-shot Neural Architecture Search with BONAS, NeurIPS-2020 \n\n[2] Brp-nas: Prediction-based nas using gcns, NeurIPS-2020 \n\n[3] Neural predictor for neural architecture search, ECCV-2020\n\nI understand these paper have been accepted but do not necessarily mean these approaches expand the frontier of knowledge. \n\n2. Evaluations on NASBench. \n\nThe reason why predictor works well on NASBench simply because it can predict every architectures. The largest dataset has 4.2*10^5 architectures, it won't be hard to predict them all. However, I believe the original NASBench paper has set baselines for us to compare (though currently published paper fail to follow these baselines and setup). I strongly encourage the authors to take look at the following repository, to see how original NASBench-101 setup the comparisons. I admit the design of NASBench might have some glitch in evaluations, but it is important to follow the same standard.\nhttps://github.com/automl/nas_benchmarks\n\n3. Evaluations on ImageNet. \n\nGetting a good results on CIFAR10 and ImageNet can be tricky. Given the current ImageNet accuracy is 76.4@597 MFLOPS, while the SoTA top1 accuracy for a 600 MFLOPS model is 80.8. I understand these models use different search spaces, but the results on CIFAR-10 is missing. There are too many tricks to hack the network accuracy on ImageNet. Therefore, it will be better to judge NASNet search space on CIFAR-10.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In line with recent work in the NAS literature, the authors consider a weak NAS performance strategy to filter out bad architectures and narrow down the exploration to the most promising region of the search space. The authors propose to estimate weak predictors progressively by learning a series of weak predictors that can connect towards the best architectures. The authors provided a number of additional experiments during rebuttal, addressing most of the reviewers' comments convincingly and further showing the strong performance of their method. However, the authors should relate their work to Bayesian optimization, which comes in many flavors, and black-box optimization techniques in general as their work shows a number of similarities, but is less principled.
Decision: Reject