Stronger NAS with Weaker Predictors
Authors: Junru Wu
Xiyang Dai
Dongdong Chen
Yinpeng Chen
Mengchen Liu
Ye Yu
Zhangyang Wang
Zicheng Liu
Mei Chen
Lu Yuan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Neural Architecture Search
Predictor
Bayesian Optimization

Abstract: Neural Architecture Search (NAS) often trains and evaluates a large number of architectures. Recent predictor-based NAS approaches attempt to alleviate such heavy computation costs with two key steps: sampling some architecture-performance pairs and fitting a proxy accuracy predictor. Given limited samples, these predictors, however, are far from accurate to locate top architectures due to the difficulty of fitting the huge search space. This paper reflects on a simple yet crucial question: if our final goal is to find the best architecture, do we really need to model the whole space well?. We propose a paradigm shift from fitting the whole architecture space using one strong predictor, to progressively fitting a search path towards the high-performance sub-space through a set of weaker predictors. As a key property of the weak predictors, their probabilities of sampling better architectures keep increasing. Hence we only sample a few well-performed architectures guided by the previously learned predictor and estimate a new better weak predictor. This embarrassingly easy framework, dubbed WeakNAS, produces coarse-to-fine iteration to gradually refine the ranking of sampling space. Extensive experiments demonstrate that WeakNAS costs fewer samples to find top-performance architectures on NAS-Bench-101 and NAS-Bench-201. Compared to state-of-the-art (SOTA) predictor-based NAS methods, WeakNAS outperforms all with notable margins, e.g., requiring at least 7.5x less samples to find global optimal on NAS-Bench-101. WeakNAS can also absorb their ideas to boost performance more. Further, WeakNAS strikes the new SOTA result of 81.3% in the ImageNet MobileNet Search Space. The code is available at: https://github.com/VITA-Group/WeakNAS.

Stronger NAS with Weaker Predictors
Junru Wu', Xiyang Dai², Dongdong Chen², Yinpeng Chen', Mengchen Liu', Ye Yu?, Zhangyang Wang'. Zicheng Liu², Mei Chen?, Lu Yuan²
Texas A&M University, Microsoft Corporation, UUniversity of Texas at Austin sandbozmaster@ttmm.c {xidai, dochen, dochen,yilche yilche, wwwgmmlinmmmiieeeee.e...ee crosoft. com, atlaswangdutexas.cmmm edu, {yeyu1, zliu, mei. chen, luyuan emicrosot.. com
Abstract
Neural Architecture Search (NAS) often trains and evaluates a large number of ar- chitectures. Recent predictor-based NAS approaches attempt to alleviate such heavy computation costs with two key steps: sampling some cetittecture-peffommmat pairs and fitting a proxy accuracy predictor. Given limited samples, these predictors, however, are far from accurate to locate top architectures due to difficulty fitting the huge search space. This paper reflects on a simple yet crucial question: if our sinal goal is to find the best architecture, do we really need model the whole space well?. We propose paradigm shift from fitting the whole architecture space using one strong predictor, to progressively fitting a search path towards the nigh-performance sub-space through set of weaker predictors. As key property the weak predictors, their probabilities of sampling better architectures keep increasing. Hence only sample few well-performed architectures guided by the previously learned predictor and estimate a new better weak predictor. This em- barrassingly easy framework, dubbed WcakNAS, produces coarse-to-fine iteration to gradually refine the ranking of sampling space. Extensive experiments demon- strate that WeakNAS costs fewer samples to find top-performance architectures on NAS-Bench- 101 and NAS-Bench-201. Compared to state-of-the-an (SOTA) predictor- based NAS methods, WeakNAS outperforms all with notable margins, e.g., requiring at least 7.5x less samples to find global optimal on NAS-Bench-101 WeakNAS can also absorb their ideas boost performance more. Further, Weak- NAS strikes the new SOTA result of 81.3% in the ImageNet MobileNet Search Space. The code is available at: https:: /tt///gtttt/.///////// com Coan/VITA-Gra GraTTAA-rroo/Weee /eakup/
Introduction
47.0
oost-iillttoon accurscy
Neural Architecture Search (NAS) [H22] methods aim
to find the best network architecture by exploring the
46.0
cechitecuuretto-pefffrmmee
manifold, using reinforced-
beanenng-based [13,, evolution-baat based [4 [5] or gradient-
based [6] approaches. In order to cover the entire search space, they often train and evaluate large number of archi- tectures, leading to tremendous computation cost.
Weel Freckthor
grade
16.5
Figure 1: Comparison hetween method using set of weak predictors (it- erative sampling). and single strong pre- dictor (random sampling) on MAS-Bench- 201. For fair comparison, the NAS predic- tor in both methods adtops the same type MLP described in 22.4] Solid lines and shadows denote the mean and standard deviation (std), respectively.
Recently, predictor-based NAS methods alleviate this prob- lem with two key steps: one sampling step to sample some caniieecture-eeffommnncc pairs, and another performance modeling step to fit the performance distribution by training proxy accuracy predictor. An in-depth analysis of existing methods (2 found that most of those methods [5, 6. I7 7 [1] consider these two steps independently and attempt model the performance distribution over the whole architec-
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Previous:
Proposed:
Top Semples
Sample Spare 5
Sample Space S
Search Space X
Search Space X
Sort
Sampling
Learning
Sampling
Learning
Pradicted Performance on X/5*
Weak Prodictors fx
Strong Predictor
Iteration
Iteration 2
Iteration
Ground-Trcft Soundd-ruath Accuracy
Gronn I Accuracy
Architocture
Architecture
Optimal &ampled
Sample Space
Excluded
Figure 2: An illustration of WeakNAS's progressive approximation. Previous rrdictor-based NAS uniformly sample in the whole search space to fit a strong predictor. Instead, our method progressively shrinks the sample space based on predictions from previous weak predictors, and update new weak predictors towards subspace of better architectures, hence focusing on fitting the search path.
ture space using strong predictor. However, since the architecture space is often exponentially large and highly non-convex, even very strong predictor model has difficulty fitting the whole space given limited samples. Meanwhile, different types of predictors often demand handcraft design of the architecture representations to improve their performance.
This paper reflects on a fundamental question for predictor-based NAS: best architecture, do really need to model the whole space well?". We investigate the alternative of utilizing a few weak- predictors to fit small local spaces, and to progressively move the search space towards the subspace where good architecture resides. 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 discarding the bad ones. which makes sure more samples will be focused on modeling only the good subspaces and then find the best architecture. It greatly simplifies the learning task of each predictor. Eventually, a line of progressively evolving weak predictors can connect a path to the best architecture.
"if our final goal is to find the
We present novel, general framework that requires only to estimate series of weak predictors progressively along the search path, we denoted it as WeakNAS in the rest of the paper. To ensure moving towards the best architecture along the path, at each iteration, the sampling probability of better architectures keep increasing through the guidance of the previous weak predictor. Then, the consecutive weak predictors with better samples will be trained the next iteration. We iterate until we arrive at an embedding subspace where the best architectures reside and can be accurately assessed by the final weak predictor.
Compared to the existing predictor-based NAS, our proposal represents a new line of attack and has several merits. First, since only weak predictors required, it yields better sample efficiency. As shown in Figure it costs significantly fewer samples to find the top-performance architecture than using one strong predictor, and yields much lower variance in performance over multiple runs. Second, it is flexible to the choices of architecture representation (e.g., different architecture embeddings) and predictor formulation (e.g.. multilayer perceptron (MLP), gradient boosting regression tree, or random forest). Experiments show our framework performs well in all their combinations. Third, it highly generalizable to other open search spaces, e.g. given a limited sample budget, we achieve the state-of-the -hht---rtt ImageNet performance on the NASNet and MobileNet search spaces. Detailed comparison with state-of-the thette-rt predictor-ban based NAS 19 21
is presented in Section 4.
'"Strong" vs "Weak" predictors: name a "weak" predictor if it only predicts a local subspace of the search space thus can be associated with our iterative sampling scheme; such predictors therefore usually do demand very heavily parameterized models. the contrary, "strong" predictors predict the global search space and are often associated with uniform sampling. The terminology of strong versus weak predictors does not represent their number of parameters or the type of NAS predictor used. An overparameterized NAS predictor with our iterative sampling scheme may still be considered a "weak" predictor.

---

2 Our Framework
2.1
Reformulating Predictor-based NAS as Bi-Level Optimization
Given a search space of network architectures X and an architecture-tor tonprctrr--t---rffmmmancc mapping function f X + P from the architecture set X to the performance set P, the objective is to find the best neural architecture x² with the highest performance f (xx) in the search space X:
x² arg max (xx
xēX
A naive solution is to estimate the performance mapping fax through the full search space. However, this is prohibitively expensive since all architectures have to be exhaustively trained from scratch. To address this problem, predictor-based NAS learns proxy predictor f(xx to approximate f(x) by using some
pairs, which significantly reduces the training cost. In general, predictor-based NAS can be re-cast as a bi-level optimization problem:
arg max f (x][S), s.L. f arg min S.jEF
Σ [((()),
=EX
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| S C} all architectures satisfying the sampling budget C. C' is directly related to the total training cost, e.g.. the total number of queries. Our objective is to minimize the loss L based on some sampled architectures S.
Previous predictor-basee NAS methods attempt to solve Equation 2 with two sequential steps: (I) sampling some architecture- -erfformrreeeeooomance pairs and (2) learning a proxy accuracy predictor. For the first step, a common practice is to sample training pairs S uniformly from the search space X to fit the predictor. Such sampling however inefficient considering that the goal of NAS only to find well architectures without caring for the bad ones.
2.2 Progressive Weak Predictors Emerge Naturally as A Solution to the Optimization
Optimization Insight: Instead of first (uniformly) sampling the whole space and then fitting the
predictor, we propose to jointly evolve the sampling S and fit the predictor f. which helps achieve better sample efficiency by focusing on only relevant sample subspaces. That could be mathematically formulated as solving Equation in a new coordinate descent way, that iterates between optimizing the architecture sampling and predictor fitting subproblems:
(Sampling)
ph (fa(s)]s e X\ \ SM C Topw(PP), s
Sas U.
(3)
where Top (Pt) denote the set of top N architectures in Pb
(Predictor Fitting)
x arg max f(a)stt1), s.t. fu+1 = arg min =EX
Σ c(f(s),
(4)
f2eF sESt+1
In comparison, existing predictor-based NAS methods could be viewed as running the above coordi- nate descent for just one iteration special case of our general framework.
As well known in optimization, many iterative algorithms only need to solve (subsets of) their subproblems inexactly 24 for properly ensuring convergence either theoretically or empirically, Here, using a strong predictor to the whole space could be treated as solving the predictor fitting subproblem relatively precisely, while adopting weak predictor just imprecisely solves that. Previous methods solving Equation truncate their solutions to "one shot" and hinge on solving subproblems with higher precision. Since
take a joint optimization view and allow for multiple iterations, we can afford to only use weaker predictors for the fitting subproblem per iteration.
Implementation Outline: The above coordinate descent solution has clear interpretations and is straightforward to implement. Suppose our iterative methods has K iterations. We initialize S by randomly sampling a few samples from X, and train an initial predictor f. Then at iterations = 2.... K, we jointly optimize the sampling set S and predictor fa in an alternative manner.
Subproblem 1: Architecture Sampling. At iteration i ++1 1, we first sort all architectures in the search space X (excluding all the samples already in 5*) according to its predicted performance pok at
"One only exception is the Section 3.2 domain experiments: we will sub-sample all architectures in the search space before sorting. More details can be found in Appendix Section H

---

Search Dynemics
0.00
50
0.02
0.4
0.41
Heral
Eamtion
Beraton Reratie 2
0--
0022
Iten on
taniion
Rematiee
nanore
Optimal Weddmted
Itrot in
Zerioon
Recotiie
Earstion
Ranation
602
60
C0
70
72
73
27
29
Accruacy
Hole
(a)
(h)
(c)
Figure 3: Visualization of the search dynamics in NAS-Bench-201 Search Space. (best viewed in
color) (a) The trajectory of the predicted best architecture and global optimal through out 5 iterations;
(b) Error empirical distribution function (EDF) of the predicted top-200 architectures throughout iterations (c) Triangle marker: probability of sampling top-50 architectures throughout 5 iterations; Star marker: Kendall's Tau ranking of NAS predictor Top 50 architectures through out iterations.
Sampling Space (Top,, (P*)
4000
mi--h Ramking
5000
8000
Optanal
Sprimal
Ootimal
14000
35625
(8) 1 iteration
(b) 2dd Iteration
(c) 3 iteration
(d) Last iteration
Sampled Architectures (5*))
2000
4000
m00h Rankknn
8000
10000
12000
Oostinal Prediited kest
Optiral Preckced
Optinal
Optiral
Reddcted
Prediced Bext
Iteration
(f) 2n Ittration
Iteration
Last Iteration
Figure 4: Visualization of search dynamics in NAS MAS--Bnnh-225 201 Search Space via t-SNE. At i-th iteration, we randomly sample M = 40 new architectures from the top N 400 ranked architectures in Pk The top row from (a)-(d) show the sampling space I T'op'N (P²),, and the bottom row from (c)-(h) show the sampled architectures 5* The performance ranking of architectures is encoded by color, and those not-sampled architectures colored in grey.
every iteration We then randomly sample M new architectures from the top N ranked architectures in ph Note this step both reduces the sample budget, and controls the exploitation-exploriie trade-off (see Section 3.1p. The newly sampled architectures together with S become S
Subproblem 2: (Weak) Predictor Fitting. We learn a predictor fh+1, by minimizing the loss C of the predictor f++11 based on sampled architectures gk++1, We then evaluate architectures using the learned predictor fa++1 to get the predicted performance p4++1
As illustrated in Figure 2 through alternating iterations, we progressively evolve weak predictors to focus on sampling along the search path, thus simplifying the learning workload each predictor. With these coarse-to-Ne tone iterations, the predictor f* would guide the sampling process to gradually zoom into the promising architecture samples. In addition, the promising samples S*+11 would in turn improve the performance of the updated predictor fk+1 among the well-performed architectures, hence the ranking of sampling space also refined gradually. other words, the solution quality to the subproblem 2 will gradually increase as natural consequence of the guided zoom-in. For

---

derivation, we simply choose the best architecture predicted by the final weak predictor. This idea is related to the classical ensembling (25]. yet a new regime NAS.
Experiment. Figure (a) shows the progressive procedure of finding the optimal architecture x² and learning the predicted best architecture म over 5 iterations. As we can see from
Figure 3 (a), the optimal architecture and the predicted best one are moving towards each other
closer and closer, which indicates that the performance of predictor over the optimal architecture(s) is growing better. In Figure we use the error empirical distribution function (EDF) [26] to visualize the performance distribution of architectures in the subspace. We plot the EDF of the top-200 models based on the predicted performance over iterations. As is shown, the subspace of top-performed architectures is consistently evolving towards more promising architecture samples over iterations. Then in (3 we validate that the probabilities of sampling better architectures within the top N predictions keep increasing. Based this property, we can just sample few well-performing architectures guided by the predictive model to estimate another better weak predictor. The same plot also suggests that the NAS predictor's ' ranking among the top-performed models gradually refined, since more and more architectures in the top region are sampled.
In Figure 4 we also show the t-SNE visualization of the search dynamic in space. We can observe that: (1) NAS- Bench-201 search space is highly structured: (2) the sam- pling space T Topx (Pt) and sampled architectures 5 are both consistently evolving towards more promising regions, can be noticed by the increasingly warmer color trend.
search
2.3 Relationship to Bayesian Optimization: A Simplification and Why It Works
Our method can be alternatively regarded vastly simplified variant of Bayesian Optimization (BO). It does not refer to any explicit uncertainty- based modeling such as Gaussian Process (which often difficult to scale up); instead it adopts a very simple step function as our acquisition function. For a sample x in the search space X, our special "acquisition function" can be written as:
acq(x) = u(x - 0)
(5)
where the step function u(x) is i 2 0, and 0 otherwise; e a random variable from the uniform distribution (0, 1); and 0 is the threshold to split Top. from the rest, according to their predicted performance pk (z)) We then choose the samples with the M largest acquisition values:
SM arg max (z)
(6)
Top
Why such "oversimplified BO" can be effectively for our framework? We consider the reason to be the inherently structured NAS search space. Specifically, existing NAS spaces are created either by varying operators from a pre-defined operator set (DARTS/NAS-Beil) 1002110 Search Space) or by varying kernel size, width or depth (MobileNet Search Space). Therefore, as shown in Figure 4 the search spaces are often highly-structured, and the best performers gather close to each other.
Here comes our underlying prior assumption: we can progressively connect a piecewise search path from the initialization, to the finest subspace where the best architecture resides. At the beginning, since the weak predictor only roughly fits the whole space, the sampling operation will be "noisier", inducing more exploration. When it comes to the later stage, the weak predictors fit better the current well-performing clusters, thus performing more exploitation locally. Therefore our progressive weak predictor framework provides a natural evolution between exploration and exploitation, without explicit uncertainty modeling, thanks to the prior of special NAS space structure.
Another exploration-expllottiii trade-off is implicitly built in the adaptive sampling step of our subproblem 1 solution. To recall, at each itcration, instead of choosing all Top N models by the latest predictor, randomly sample M models from Top N models to explore new architectures in a stochastic manner. By varying the ratio = M/N and the sampling strategy (e.g., uniform, linear-decay or exponential-decay), we can balance the sampling exploitation and exploration per step, in a similar flavor to the e-greedy (27 approach in reinforcement learning.
2.4 Our Framework is General to Predictor Models and Architecture Representations
Our framework is designed to be generalizable to various predictors and features. In predictor-
NAS, the objective of fitting the predictor í is often cast as a regression 7 or ranking 5 problem.
The choice of predictors is diverse, and usually critical to final performance 5 6 7-9. To
illustrate our framework is generalizable and robust to the specific choice of predictors, we compare the following predictor variants.
5

---

01.0
47.
86.0
00.0
00.6
GEIT
Random Search
Random Search
GENT
Randomfores
43.0
GORT
Ransem Search
Fondamt
MPP
RLP
MLF
onci
diacle
4419
orace
230
300
330
200
200
200
502
120
200
200
402
Number of Sarppine
Kumber of Samplee
Namber of Sarrples
CIFARIO
(b) CIFARIO0
(c) ImageNet166
Figure 5: Evaluations of robustness across different predictors shadow regions denote the mean and std, respectively.
Solid lines and
Multilayer perceptron (MLP): MLP is the common baseline in predictor-based NAS [5] due to its simplicity. For our weak predictor, we use a 4-layer MLP with hidden layer dimension of (1000, 1000, 1000, 1000).
Regression Tree: tree-based methods are also popular 9
28 since they suitable for
categorical architecture representations. As our weak predictor, we use the Gradient Boosting Regression Tree (GBRT) based XGBoost 29 consisting of 1000 Trees.
Random Forest: random forests differ from GBRT in that they combines decisions only the end rather than along the hierarchy, and are often more robust to noise. For each weak predictor, we use random forest consisting of 1000 Forests.
The features representations to encode the architectures are also instrumental. Previous methods hand-craft various features for the best performance, e-g., raw architecture encoding (6], supernet statistics [30]. and graph convolutional network encoding 7 5 g 19 Our framework is also agnostic
various architecture representations, and compare the following:
One-hot vector: NAS-Bench-201 31. its DARTS-style search space has fixed graph connectivity, hence the one-hot vector commonly used to encode the choice of operator.
Adjacency matrix: In NAS-Bench-101,
used the same encoding scheme in [32 6).
where a x adjacency matrix represents the graph connectivity and a 7-dimensional vector represents the choice of operator on every node.
As shown Figure all predictor models perform similarly across different datasets. Comparing per- formance JAS-Bench-IDe 101 and NAS-Bench-201 although they different architecture encoding methods, our method still performs similarly well among different predictors. This demonstrates that our framework robust various predictor and feature choices.
3 Experiments
Setup: For all experiments, use Intel Xeon E5-2650v4 CPU and single Tesla P100 GPU, and use the Multilayer perceptron (MLP) as our default NAS predictor, unless otherwise specified.
NAS-Bench-101 332 provides Directed Acyelic Graph (DAG) based cell structure. The connectiv- ity of DAG can be arbitrary with a maximum number of nodes and 9 edges. Each nodes on the DAG can choose from operator of 1 x convolution, 3x3 convolution or 3x3 max-pooling. After removing duplicates, the dataset consists of 423,624 diverse architectures trained on CIFAR 10
NAS-Bench-201 31 is more recent benchmark with reduced DARTS-like search space. The DAG of each cell is fixed, and one can choose from different operations (1x1 convolution, 3x3 convolution, 3x3 avg-pooling, skip, connection), on each of the 6 edges, totaling 15,625 architectures. It is trained on different datasets: CIFARIO, CIFARIO8 and ImageNet16- [34].
For experiments on both NAS- NAS-Benches, followed the same setting (8).
Open Domain Search: We follow the same NASNet search space used
and MobileNet
Search Space used in (36] to directly search for the best architectures on ImageNet 37 Due to
the huge computational cost to evaluate sampled architectures on ImageNet, we leverage weight- sharing supernet approach. On NASNet search space, we use Single- One-shot [38 approach to train our SuperNet, while on MobileNet Search Space we reused the pre-trained supernet from [F.] We then use the supernet accuracy as the performance proxy to train weak predictors. We clarify that despite using supernet, our method more accurate than existing differentiable weight-sharing methods, meanwhile requiring less samples than evolution based weight-sharing

---

methods, as manifested in Table and 7 We adopt Py and image models library (timm) [39 to implement our models and conduct all ImageNet experiments using 8 Tesla V100 GPUs. For derived architecture, we follow similar training from scratch strategies used in LaNAS 21
3.1 Ablation Studies
We conduct series of ablation studies the effectiveness of proposed method NAS-Bench- 101. To validate the effectiveness of our iterative scheme, Table we initialize the initial Weak Predictor f1 with 100 random samples, and set M 10, after progressively adding more weak predictors (from 1 to 191), we find the performance keeps growing. This demonstrates the key property of our method that probability of sampling better architectures keeps increasing more iteration goes. It's worth noting that the quality of random initial samples Mo may also impact on the performance of WeakNAS, but if MMl sufficiently large, the chance of hitting good samples (or its neighborhood) is high, and empirically we found JMMo=110 to already ensure highly stable performance NAS-Bencha 101: a more detailed ablation can be found the Appendix.
Sampling
#Predictor
#Queries
Test Acc.(%)
SD(%)
Test Regret %))
Avg. Rank
Uniform
Strong Predictor
2000
93.92
0.08
0.40
135.0
Weak Predictor
100
93,42
0.37
0.90
6652.1
11 Weak Predictors
200
94.18
0.14
0.14
5.6
Iterative
91 Weak Predictors
1000
94.25
0.04
0.07
1.7
191 Weak Predictors
2000
94.26
0.04
0.06
1.6
Optimal
94.32
0.00
1
Table 1: Ablation the effectiveness of our iterative scheme NAS-Bench-101
Sampling from TopN)
M
TopN
#Queries
Test Acc.(%) (%)
SD(%)
Test Regret(%)
Avg. Rank
Exponential-decaa
10
100
1000
93.96
0.10
0.36
85.0
Linear-decay
10
100
1000
94.06
0.08
0.26
26.1
Uniform
10
100
1000
94.25
0.04
0.07
1.7
Uniform
10
1000
1000
94.10
0.19
0.22
14.1
Uniform
10
100
1000
94.25
0.04
0.07
1.7
Uniform
10
10
1000
94.24
0.04
0.08
1.9
Table 2: Ablation on exploiaation-exploraiio trade-off on NAS- NAS-Bench-100
Method
#Queries
Test Acc.(%)
SD(%))
Test Regret(S)
Avg. Rank
WcakNAS
1000
94.25
0.04
0,07
WeakNAS (BO Variant)
1000
94.12
0.15
0.20
Optimal
94.32
0.00
1.0
Table 3: Comparing to the BO variant of WeakNAS on MAS-Bench-
We then study the exploitation-exploaaiie off in Table NAS-Bench-10d 101 (a similar ab- lation in Mobilenet Search space on ImageNet also included in Appendix Table 6 by inves- tigating two settings:
trade-
94.2
Best Test Accuracy
(a) We gradually increase N allow for more exploration, similar to con- trolling in the opsilon-greedy
BONAS
(27) approach in the RL context; (b) We vary the sampling strat- egy from Uniform, Linear-decay to Exponential- decay (top models get higher probabilities by fol- lowing either linear-decay or exponential-dess distribution). We empirically observed that: (a) The performance drops more (Test Regret 0.22% vs 0.08%) when more exploration (TopN=1000 vs TopN=10) is used. This indicates that exten- sive exploration is not optimal for NAS-Bench- 101; (b) Uniform sampling method yields better performance than sampling method that biased
93.8
BANANAS
NAO
93.6
NASBOT
WeakNAS
oracle
200
400
600
800
1000
Number of Samples
Figure 6: Comparison with SoTA methods NAS-Bench-101. Solid lines and shadow regions denote the mean and std, respectively.

---

towards top performing model (e.g. linear- decar, aeponential-decay This indicates good architec- tures are evenly distributed within the Top 100 predictions of Weak NAS, therefore simple uniform sampling strategy for exploration is more optimal in NAS-Bench-IDe 101. To conclude, our Weak NAS Predictor strikes a good balance between exploration and exploration.
Apart from the above exploitation-explraaiiie trade-off of WeakNAS, we also explore the possibility of integrating other setal-ampling methods. We found that the local search algorithm could achieve comparable performance, while using Semi-NAS 20] as meta sampling method could further boost the performance of WeakNAS: more details are Appendix Section
3.2 Comparison to State-of-the-ae (SOTA) Methods
NAS-Bench-001: On NAS Bench- 101 benchmark, we compare our method with several popular 41 44 Table that our method significantly outperforms baselines terms of sample efficiency. Specifically, our method costs 964 x, 447x, 378x, 245 x, 58x, and 7.5x less samples to reach the optimal architecture, compared to Random Search, Reg- ularized Evolution 14. MCTS [40], Semi-NAS
methods [14 40 21 7 20 19
LaNAS BONAS [9], respectively. We then plot the best accuracy against number of samples in Table 4 and Figure to show the sample efficiency on the NAS-Bench- B--B-Bennn... from which we can see that our method consistently costs fewer sample to reach higher accuracy.
Method
# #Queries
Test Acc.(% (%)
SD(%)
Test Regret (%)
Avg. Rank
Random Search
2000
93.64
0.25
0.68
1750.0
NAO [2]
2000
93.90
0.03
0.42
168.1
Reg Evolution
14
2000
93.96
0.05
0,36
85.0
Semi-NAS 20
2000
94.02
0,05
0.30
42.1
Neural Predictor
2000
94.04
0.05
0.28
33.5
WeakNAS
2000
94.26
0.04
0.06
1.6
Semi-Assessor
42
1000
94.01
0.31
47.1
LaNAS 21
1000
94.10
0,22
14.1
BONAS 19
1000
94.22
0.10
3.0
WeakNAS
1000
94.25
0.04
0.07
1.7
Arch2vec 41
400
94.10
0.22
14.1
WeakNAS
400
94.24
0.04
0.08
1.9
LaNAS 21
200
93.90
0.42
168.1
BONAS [19
94.09
0.23
18.0
WeakNAS
200
94.18
0.14
0.14
5.6
NASBOWI.r 45
94.09
0.23
18.0
CATE (cate-DNGO-LS) 43
150
94.10
0.22
12.3
WeakNAS
150
94.10
0.19
0.22
12.3
Optimal
94.32
0.00
1.0
Table Comparing searching efficiency by limiting the total query amounts on NAS-Bench-100
Method
NAS-Bench-
NAS-Bench-20
Dataset
CIFARIO
CIFARIO
CIFARI00
I
Random Scarch
188139,8
7782.1
7621.2
7726.1
Reg Evolution
11
87402.7
563.2
438.2
715.1
MCTS 40
73977.2
1528.3
t405.4
f578.2
Semi-NAS
20
147932.3
LaNAS 21
11390.7
1247.1
118.5
1292.4
BONAS 19
1465.4
WeakNAS
195.2
182.1
78.4
268.4
Table 5: Comparison on the number samples required to find the global optimal on NAS-Bench-1ue and BAS-Bench-201. denote reproduced results using adapted code.
JAS-Bench-201 We further evaluate on JAS-Bench-201 and compare with random search, Regu- larized Evolution [4], Semi-NAS (0), LaNAS BONAS(T). As shown in Table we conduct searches all three subsets (CIFARIO, CIFAR 100, ImageNet16-1200) and report the average number

---

of samples needed to reach global optimal on the testing set over 100 runs. It shows that our method has the smallest sample cost among all settings.
we further apply our method to open domain search without ground-truth 48 21 As shown in Tables 6 and using the fewest samples (and only fraction of GPU hours) among all, our method can achieve state-of-the-ard ImageNet top-1 accuracies with comparable parameters and FLOPs. Our searched architecture is also competitive to expert-design networks. On the NASNet Search Space, compared with the SoTA predictor-ban based NAS method LaNAS (Oneshot) 211, our method reduces 0.6% top-1 error while using less GPU hours. On the MobileNet Search Space, we improve the previous SoTA LaNAS [1 81.3% top-1 accuracy on ImageNet while costing less FLOPs.
Open Domain Search:
and compare with several popular methods [35] 14 46
3.3 Discussion: Further Comparison with SOTA Predictor-based NAS Methods
BO-based NAS methods [19 45 BO-based methods in general treat NAS as a black-box optimiza- tion problem, for example, BONAS [9| customizes the classical BO framework in NAS with GCN embedding extractor and Bayesian Sigmoid Regression to acquire and select candidate architectures. The latest BO-based NAS approach, NASBOWL [45], combines the Weisfeiler-Lehman graph kernel in BO capture the topological structures of the candidate architectures.
Compare with those BO-based method, our WeakNAS is an "oversimplified" version of BO as explained in Section 2.3 Interestingly, results in 4 that WeakNAS is able to outperform BONAS [9]. and is comparable to NASBOWLr [45] on MAS--ench--01. showcasing that the simplification does not compromise NAS performance. We hypothesize that the following factors might be relevant: (1) the posterior modeling and uncertainty estimation in BO might be noisy; (2) the inherently structured NAS search space (shown in Figure could enable "shorteut" simplification to explore and exploit. In addition, the conventional uncertainty modeling in BO, such as the Gaussian Process used by (45), is not as scalable when the number of queries is large. In comparison, the complexity of WeakNAS scales almost linearly, as can be verified in Appendix Table [ In our experiments, we observe WeakNAS to perform empirically more competitively than current BO-based NAS methods at larger query numbers, besides being way more efficient.
To further convince that WeakNAS is indeed effective simplification compared to the explicit posterior modeling in BO, we report an apple-to-apple comparison, by use the same weak predictor from WeakNAS, plus obtaining its uncertainty estimation by calculating its variance using deep ensemble of five model [4 we then use the classic Expected Improvement (EI) [50] acquisition function. Table 3 confirms that such BO variant of WeakNAS is inferior our proposed formulation.
Advanced Architecture Encoding 41 43
We also compare WeakNAS with NAS using custom architecture representation either in unsupervised way such as arch2vee [41, or a supervised way such as CATE 43). We show our WeakNAS could achieve comparable performance to both methods. Further, those architecture embedding are essentially complementary our method to further boost the performance of WcakNAS, as shown in Appendix Section C
LaNAS (21]: LaNAS and our framework both follow the divide-and-conquee idea, yet with two methodological differences: (a) How to split the search space: LaNAS learns a classifier to do binary "hard" partition on the search space (no ranking information utilized) and split it into two equally sized subspaces. Ours uses a regressor to regress the performance of sampled architectures, and utilizes the ranking information to sample percentage of the top samples ("soft" partition), with the sample size N being controllable. (b) How to do exploration: LaNAS uses Upper Confidence Bound (UCB) to explore the search space by not always choosing the best subspace (left-most node) for sampling, while ours always chooses the best subspace and explore new architectures by adaptive sampling within it, via adjusting the ratio M/N to randomly sample M models from Top N. Tables 4 and 5 shows the superior sample efficiency of WeakNAS over LaNAS on BAA--Benc--Be 101/211
Semi-NAS 20 and Semi-Assessor 42]:
Both our method and Demi-NAS/Semi-AAe
use an
iterative algorithm containing prediction and sampling. The main difference lies in the use of pseudo labels: Semi-NAS and Semi-Assessor use pseudo labels as noisy labels to augment the training set, therefore being able to leverage "unlabeled samples" (e.g., architectures without true accuracies, but with only accuracies generated by the predictors) to update their predictors. Our method explores an orthogonal innovative direction, where the "pseudo labels" " generated by the current predictor guide sampling procedure, but are never used for training the next predictor.

---

That said, we point out that our method can be complementary to those semi- cumi-supervised methods (20 42], thus they can further be integrated as one, For example, Semi-NAS can be used meta sampling method, where each iteration we further train a Semi-NAS predictor with pseudo labeling strategy to augment the training set of our weak predictors. We show Appendix Table that that the combination of our method with Semi-NAS can further boost the performance of WeakNAS.
BRP-NAS 8 BRP-NAS uses stronger GCN-based binary relation predictor which utilize extra lopological prior, and leveraged a different scheme to control exploitation and exploration trade-off compare to our WeakNAS. Further, BRP-NAS also use somehow unique setting, i.e. evaluating Top-40 predictions by the NAS predictor instead of the more common setting of Top- [2 19 21 20 Therefore, we include our comparison BRP-NAS and more details Appendix Section
Model
Queries(ff) Top-1 (ir.
'Top-5 (mr.
Params(M)
FLOPs(M)
GPU Days
MobileNetV2
25.3
6.9
585
ShuffletNetV2
25.1
5.0
591
SNAS
27.3
9.2
4,3
522
1.5
DARTS
26.9
9.0
4.9
595
4.0
P-DARTS 52
24.4
7.4
4.9
557
0.3
PC-DARTS
24.2
7.3
597
3.8
DS-NAS(53
24.2
7.3
10.4
NASNet-A [35
20000
26.0
8.4
5,3
564
2000
AmoebaNet-A
14
10000
25.5
8.0
555
3150
PNAS 46
1160
25.8
8.1
NAO
1000
24.5
7.8
LaNAS
21
(Oneshot)
800
24.1
5,4
567
3
LaNAS
21
23.5
150
WeakNAS
800
23.5
6.8
5,5
591
2.5
Table 6: Comparison to SOTA results on ImageNet using NASNet search space.
Model
Queries(4)
Top-1 Acc.(%)
Top-5 Acc.(%)
FLOPP(M)
GPU Days'
Proxyless NAS 54
75.1
92.9
Semi-NAS 20
300
76.5
93.2
599
BigNAS
76.5
586
FBNetv3
20000
80.5
95.1
557
OFA 36
16000
80.0
595
1.6
LaNAS[21
800
80.8
598
0.3
1000
81.3
95.1
WeakNAS
800
81.2
95.2
593
0.13
Table 7: Comparison to SOTA results on ImageNet using MobileNet search space. *Does not include
supernet training cost.
Conclusions and Discussions of Broad Impact
In this paper, present novel predictor-based NAS framework named WeakNAS that progressively shrinks the sampling space, by learning a series of weak predictors that can connect towards the best architectures. By co-evolving the sampling stage and learning stage, our weak predictors progressively evolve to sample towards the subspace of best architectures, thus greatly simplifying popular NAS benchmarks prove that
the learning task of each predictor. Extensive experiments the proposed method is both sample-efficient and robust to various combinations of predictors and architecture encoding means. However, WeakNAS is still limited by the human-designed encoding of neural architectures, and our future work plans to investigate how to jointly learn the predictor and encoding in framework.
For broader impact, the excellent sample-efficinnyy of WeakNAS reduces the resource and energy consumption needed to search for efficient models, while still maintaining SoTA performance. That can effectively serve the goal GreenAI, from model search model deployment. It might meanwhile be subject to the potential abuse of searching for models serving malicious purposes.
Acknowledgment
Z.W W. is in part supported by NSF CCRI project (42016727).
10

---

References
[1] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 1806. 09050,005550 2018.
[2] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Liu. Neural architecture optimiza- tion. In Advances neural information processing systems, pages 7816-7827, 2018.
[3] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer, Fbnet: Hardware-awar aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 10734-10742, 2019.
[4] Andrew Howard, Mark Sandler, Grace Chu, Liang- Ching Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Proceedings of the IEEE International Conference Computer Vision, 2019.
[5] 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 .xXv922004001899, 2020.
[6] Chen Wei, Chuang Niu, Yiping Tang, and Jimin Liang. Npenas: Neural predictor guided evolution for neural architecture search. arXiv preprint (:Xiv:2003.12850 2020.
[7] Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. arXiv preprint
2019.
[8] Lukasz Dudziak, Thomas Chau, Mohamed Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas Lane. Brp-nas: iiciicttoo-bbasee nas using gens. Advances in Neural Information Processing Systems, 33, 2020.
[9] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tic-Yan Liu. Neural architecture search with gbdt. arXiv preprint 2rXiv:2007.04785, 2020.
[10] Yunhe Wang, Yixing Xu, and Dacheng Tao. De-nas: Divide-and-conquer neural architecture search. arXiv preprint arXiv:2005. 1120005.144555 /4456, 2020.
[11] Xiyang Dai, Dongdong Chen, Mengehen Liu, Yinpeng Chen, and Lu Yuan. Da-nas: Data adapted pruning for efficient neural architecture search. ECCV 2020, 2020.
[12] Zhaohui Yang. Yunhe Wang, Xinghao Chen, Jianyuan Guo, Wei Zhang, Chao Xu, Chunjing Xu, Dacheng Tao, and Chang Xu. Hournas: Extremely fast neural architecture search through an hourglass lens. arXiv preprint arXiv:2005. 14044446,.4 2020.
[13] Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv: 161110178,, 2016
[14] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pages 4780 4789, 2019.
[15] 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 IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 1829-1838, 2020.
[16] Weijun Hong, Guilin Li, Weinan Zhang, Ruiming Tang, Yunhe Wang. Zhenguo Li, and Yong Yu. Dropnas: Grouped operation dropout for differentiable architecture search. International Joint Conference on Artificial Intelligence, 2020.
[17] Yixing Xu, Yunhe Wang. Kai Han, Shangling Jui, Chunjing Xu, Qi Tian, and Chang Xu. Renas: Relativistic evaluation of neural architecture search. arXiv preprint
2019.

---

[18] Yanxi Li, Minjing Dong, Yunhe Wang, and Chang Xu. Neural architecture search in proxy validation loss landscape. In International Conference on Machine Learning, pages 5853-5862. PMLR, 2020.
[19] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sumpl--baedd and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 33, 2020.
[20] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie- Yan Liu, Semi-supervised neural architecture search. arXiv preprint 200X::2000..1389,, 2020.
[21] Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning actions for monte carlo tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[22] Rachael Tappenden, Peter Richtárik, and Jacek Gondzio. Inexact coordinate descent: complexity and preconditioning. Journal of Optimization Theory and Applications,
2016.
[23] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. arXiv preprint arXiv: 109.2415, 2011.
[24] William W Hager and Hongchho Zhang. Convergence rates for an inexact admm applicd to separable convex optimization. Computational Optimization and Applications, 2020.
[25] Zhi-Hua Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.
[26] Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Design- ing network design spaces. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10428-10436, 2020.
[27] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[28] 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. 09777, 2020.
[29] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference knowledge discovery and data mining, pages 785-794, 2016.
[30] 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.13331, 2020.
[31] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
[32] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pages 7105-7114, 2019.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[34] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint 10X7.07777.88/199 2017.
[35] 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, pages 8697-8710, 2018
[36] 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 1xXiv
12

---

[37] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255 leee, 2009.
[38] 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 1rXiv:1904.04420 2019.
[39] Ross Wightman. Pytorch image models. pytorch-Image-model. 2019.
https://github. hwwpthuub..om//wwggttaat.
[40] Linnan Wang. Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv: 2019.
[41] Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? Advances in Neural Information Processing Systems, 33, 2020.
[42] Yehui Tang, Yunhe Wang, Yixing Xu, Hanting Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. A semi-supervised assessor of neural architectures. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1810-1819, 2020.
[43] Shen Yan, Kaiqiang Song, Fei Liu, and Mi Zhang. Cate: Computation-aware neural architecture encoding with transformers. arXiv preprint arXiv:2102.077 108, 2021.
[44] Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10293-10301, 2021.
[45] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Interpretable neural ar- chitecture search via bayesian optimisation with weisfeiler-lehman kernels. In International Conference on Learning Representations, 2021.
[46] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision (ECCV), pages 19-34, 2018.
[47] Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le. Bignas: Scaling up neural architecture search with big single-stage models. In European Conference on Computer Vision, pages 702-717. Springer, 2020.
[48] Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Bichen Wu, Zijian He, Zhen Wei, Kan Chen, Yuandong Tian, Matthew Yu, Peter Vajda, et al. Fbnetv3: Joint rechttecture-reippe search using neural acquisition function. arXiv preprint arXiv:2006.0000 02049, 2020.
[49] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. arXiv preprint arXiv:1612.01477 2016.
[50] Donald R Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-492, 1998.
[51] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprini arXiv:1812.0000 099266, 2018
[52] 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 Conference Computer Vision, pages 1294-1303. 2019.
[53] 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. 2019.
arXiv preprint
13

---

[54] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXi:18112.03332. 2018.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 4
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 4
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code and instructions are released in htttps//ggituub com Swtp//VIAA--ee VITA-GGrop/WeeaWAA...
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See main paper Section 2.4 for predictor setup, and Section 3 for detailed setup in each dataset, and the suppiemental material for ImageNet training details.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Experiments times, see confidence interval in Figure 6 and Standard Deviation in Table [2 ImageNet experiments in Table
MAS--ench-100 101/201 are all ran multiple
ran only once due to the high computational cost (#=600 GPU hours) re-training each searched model, However, we will continue running more ImageNet experiments and report the confidence intervals in future versions.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We used pub- licly available data and cited the corresponding papers, including CIFARI0[3) CIFAR 130 ImageNet16 1-166-10200 (2((4)) ImageNet (37. NAS-Bench-101 32 NAS-
Bench-201 31]. (F) TIMM Library (39]
(b) Did you mention the license of the assets? [Yes] We double check and make sure that the publication for the data and code we use include the corresponding licenses, See
Appendix for more details.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you's re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ziHwGCN6V6y", "reviewer": "Reviewer_NXMZ", "summary": "This paper proposes a novel method for the Neural Architecture Search problem. The authors reinterpret the NAS problem as a bilevel optimization problem, and show that the presented solution follows naturally from this formulation. Its main idea is to iteratively train a proxy model (performance predictor) based on the current iteration's best knowledge about the search space, and make new predictions on the search space, adding them to the training set, motivated from Bayesian Optimization. This allows evaluating fewer samples to reach the same accuracy, while also being less dependent on the design and performance of the proxy model. They show that the proposed method works well on NAS-Bench-101, -201, and in OFA search space, using fewer architecture samples and achieving higher accuracy than SOTA methods.", "questions": "", "limitations": "", "rating": 7, "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": "The proposed neural architecture search method (WeakNAS) offers an alternative approach to proxy model-based NAS. Pros:\n- Better sample efficiency\n- Finds higher accuracy models\n- Lower variance in performance over multiple runs\n\nThe claims are well-supported by the experimental results. The paper is generally well-written, but it would have been better if the algorithm was also presented concisely in the form of pseudocode.\n\nIt is not clear if the results are meaningful, though. In Table 2, It shows that with the same number of queries, WeakNAS shows nearly the same performance as Local Search, a very simple baseline. This is perhaps because the NAS-Bench-101 space is very small, but given no comparison between WeakNAS and Local Search in other settings, I have no other choice to believe that WeakNAS is no better than Local Search.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is not clear how the predictor models are trained. In the case of MLP, do the authors start SGD from random weights at each iteration? If so, it seems to me that the algorithm needs at least $O(n)$ SGD steps at each iteration, where $n$ is the number of samples in the training set so far. This makes the entire algorithm have the time complexity of $O(n^2)$. This means that the cost of training the proxy model could quickly outweigh the cost of evaluating the samples if $n$ gets large enough.\n\nTo me, it seems vital in proving WeakNAS' superiority to show how much actual (wall-clock) time is saved compared to other methods in the overall search process. However, there is no plot with the elapsed wall-clock time. Instead, only the iteration number or the number of samples is provided as the x-axis. This raises the question of whether this algorithm is realistic in saving the actual search time. It would also be helpful to provide how much time is spent on training the proxy models and predicting the samples' performances vs. actually evaluating the selected architectures' performances. I suspect that running the predictor on all of the architectures is somewhat costly, in addition to the training cost.\n\nIn the footnote of page 3, the authors reveal that only 1,000 random samples' performances are predicted at each iteration, from which 100 best-performing samples are evaluated. They also state that (1) \"the probability of some good examples in the total 1000 samples is very high\", and (2) \"progressive evolving will make this probability even larger\". However, the size of the OFA search space is on the order of $10^{18}$. From my understanding of the method, this means that even if after 10,000 iterations, the algorithm only \"sees\" $10^{-9}$ percent of the entire search space. It is extremely likely that the optimal architecture lies outside this tiny subspace since the candidate samples were sampled entirely randomly. I suspect that Local Search might even do better than WeakNAS in this case, since unlike WeakNAS, Local Search utilizes the knowledge of the current samples to decide which architectures to sample next. Therefore I am not convinced that assertion (1) is true. Moreover, since the method of sampling the candidates is entirely random, I do not see how (2) is true, either. From my understanding, the progressive evolving should only increase the probability of selecting the 100 samples that perform better than the other 900 from the 1000 candidates, not the probability of there being a better model in the 1000 samples from the $10^{18}$ search space. I hope to get some clarification on this part.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "fOc_1Xzt3d5", "reviewer": "Reviewer_Lp96", "summary": "This submission suggests a novel search strategy for NAS.  \nWhile suggested search method takes the form of BO-like iterative procedure, exploration is done by acquiring only a portion of top-K architectures scored by an on-the-fly accuracy predictor.  \nSuch a search scheme is simple and novel in NAS literature, but achieved SOTA performance and search efficiency in NAS-Bench-101, NAS-Bench-201, and ImageNet@NASNet search space.", "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 Review\nI still have unresolved questions about the relationship vs BO-based NAS.\nI'm willing to vote for acceptance if my questions are resolved.\n\n### Pros\n- Proposed search strategy is simple but shown to be powerful and efficient in NAS benchmarks\n\n### Cons\n- The relationship with respect to BO-based NAS is not clearly written.\n- I have remaining questions which can be resolved during the rebuttal period. \n\n### Questions\n1. According to Line117, the newly sampled architectures are accumulated. But doesn't it contradict the main \"weak predictor\" idea and Figure2? If the predictor is considered to be getting \"weaker\" because architectures will be sampled more and more only from the high accuracy predicted region, how does it differ from other BO-based methods (ex. BONAS)?\n\n2. Because I'm not understanding the gap vs BO-based NAS in terms of its iterative procedure as in Question 1, the part that sounds novel is its acquisition strategy.\nThis simple acquisition strategy can be solely enough contribution if the effectiveness is justified.\nHowever, I can't find the full justification of why the new exploration strategy is better than others.\n   - Section 2.3 Line148-161 seems to be justifying all BO for me because of Question 1.\n   - Section 2.3 Line162-167 is so finally what I have found for the only difference from other BO methods.\nThe lines (162-167) are explaining the substantial idea, but not addressing why it is superior.\n   - Comparisons to LaNAS and BONAS in Section 3.4 are addressing the advantage, but there's no strict experimental support.\nex. What if only UCB acquisition is adopted while keeping every other setup (ex. predictor architecture, architecture representation)?   \n\n3. Is there an alternative version of table 3 but with NAS-Bench-201 results? Table 4 reports the required number of sampling only if each method had reached the global optimum.\n\n## Minor Comments\n- Algorithm would be helpful for readers. (ex. how was $\\tilde{f}^{k+1}$ initialized. Random or $\\tilde{f}^{k}$?)\n- BONAS reference should be updated to NeurIPS 2020 publication.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### Limitations\nOptimal convergence is not guaranteed and well-designed architecture encoding is necessary, although those are general limitations of NAS literature.\n\n### Societal Impact\nI agree with the impact what the authors mentioned: better NAS can lead GreenAI.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "MgVvFU8jQFx", "reviewer": "Reviewer_tHc2", "summary": "This paper proposes a progressive method to implicitly shrink the search space by updating the new weak predictors given the prediction results from the previous weak predictors. Experiments show that the proposed method costs fewer samples to find top-performance architectures on various search spaces.", "questions": "", "limitations": "", "rating": 6, "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": "+: Results on NAS-Bench-101, NAS-Bench-201 are good. Results on NASNet and MobileNet look promising. \n+: Simple and effective. \n\n-:\nNovelty. Since one-time fitting as used in neural predictor costs much initialization time (since it needs k = 172 architectures to fit a strong GCN predictor) and easily causes overfitting, iteratively refining predictors starting with a small portion of initialized architectures in active learning way has been used in many previous works. Could the author[s] state their novelty more clearly?\n\nRelated works and experimental comparison. There are some performance prediction works are missing, from the seminal work https://arxiv.org/pdf/1705.10823.pdf to https://arxiv.org/pdf/1910.11858.pdf, https://arxiv.org/pdf/2005.06821.pdf,  https://arxiv.org/pdf/2007.04785.pdf, https://arxiv.org/pdf/2104.01177.pdf. Architecture encodings/representation works https://arxiv.org/pdf/2006.06936.pdf, https://arxiv.org/pdf/2007.04965.pdf, https://arxiv.org/pdf/2102.07108.pdf. Local search work is proposed in https://arxiv.org/pdf/2004.08996.pdf, https://arxiv.org/pdf/2005.02960.pdf.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Show proof of concepts of Figure 2 in the paper, and why it is novel compared to previous related works. \n\n2. Provide more discussions/ablation results on different predictors with different encodings in the main text and Table 3, 4, Figure 4, 5. \n\n3. Add results comparison or discussion with https://arxiv.org/pdf/2004.01899.pdf and https://arxiv.org/pdf/2006.08573.pdf.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9 hours"}, "extra_text": {}}, {"review_id": "3dp4FtS8s-l", "reviewer": "Reviewer_vUV5", "summary": "This paper describes a predictor-based NAS scheme called weak NAS. Rather than finding a sophisticated predictor to fit the whole architecture space, it is a better idea to have a series of weaker predictors, that progressively narrows down the search and move towards the best sub-space. The empirical results are very strong and comprehensive, outperforming some very recent strong SOTAs such as LaNAS (TPAMI 2021). ", "questions": "", "limitations": "", "rating": 8, "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": "The main insight of this paper is that, due to the special structure of NAS search space, its search strategy can be accordingly simplified. Specifically, a line of progressively evolving weak predictors can be found to connect a path to the best architecture. Hence, WeakNAS requires only to estimate a series of weak predictors to fit small local spaces and to progressively move the search space towards the subspace where good architecture resides.\n\nThis paper used a principled re-formulation of predictor-based NAS to motivate their method. The bi-level form leads to a coordinate descent-like heuristic algorithm, that is further interpreted as the alternating iteration of sampling and local fitting. The framework is general and can be used with various predictors or architecture encodings. Section 2.3 also discussed its relationship to BO and shows WeakNAS to be an efficient BO variant with a simple implicit acquisition function. It can work thanks to the special structure-property of NAS space. \n\nAs an empirical paper, this paper benefits from the high completeness of its empirical comparison. The comparison is  comprehensive and covers the latest predictor-based and other NAS methods. Particularly, Section 3.4 presents a very helpful discussion on the similarities and differences, between WeakNAS and Semi-NAS, LaNAS, and BONAS. It makes WeakNAS’s contribution clear to comprehend. \n\nThe results surpasses the recent SOTAs. In general, WeakNAS can find better models with fewer queries; it also has a significant speedup on the search time, compared to SOTAs. In the open-domain NASNet space, WeakNAS is able to reduce 0.6% top-1 error from the latest LaNAS [21], using much fewer GPU hours and at similar parameter counts. When it comes to the more challenging MobileNet open space, WeakNAS also beats LaNAS by 0.5% top-1 error, using even fewer FLOPs.\n\nThe paper writing is also good.  Fig 2 and Fig 3 are  informative and extensive ablation studies are conducted. \n\nQuestions:\n-\tLine 294: “Table 2 shows that the combination of our method with 295 Semi-NAS can further boost the performance of WeakNAS”. I never found this result. I suspect there might be some typo, but this combination makes a critical claim and the authors must clarify that.\n-\tThe authors in general confused the usage of “less” and “fewer”, e.g. “less samples” should be “fewer samples”. Similar happens many times in the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have sufficiently discussed this aspect.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}, {"review_id": "0jtmbFC6qJX", "reviewer": "Reviewer_chmj", "summary": "This paper presents a method that trains neural architecture predictors by focusing on the high-performing sub-space. Specifically, the authors start from a weak predictor and sample a set of promising architectures from the previous predictor to learn a better predictor. Extensive experiments on NAS-Bench-101, NAS-Bench-201, NASNet and MobileNet search spaces demonstrate the effectiveness of the proposed method. However, some important details are missing. My details comments are as follows.", "questions": "", "limitations": "", "rating": 7, "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": "Positive points:\n1. The authors point out that it is not necessary to fit all architectures in the whole search space while training predictors, which is very interesting.\n2. The authors proposed an iterative training scheme to learn a set of gradually improved predictors.\n3. The experimental results show the superiority of the proposed method over the existing ones.\n\nNegative points:\n1. The experimental results in Table 6 (81.3% Top-1 accuracy on ImageNet) are quite impressing. However, some implementation details are missing, including the details of the search space, the details of retraining strategy and so on. These details have a huge influence on the performance. \n2. Will the authors publish the code and pretrained models for better reproduction?\n3. In Table 6, it would be better to report the search cost for clearer comparisons.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a Neural Architecture Search method which utilizes a series of weak performance predictors, that are trained to focus on the samples that are more likely to perform better by the previous weak predictor. This is done by alternating between the learning of the weak predictor based on the sampled architectures, and the sampling with this weak predictor. The authors validate their method with a proof-of-concept experiment, as well as experimental validation on the NAS-Bench-101 and NAS-Bench-201 benchmarks, against relevant predictor-based and BO-based NAS baselines. The results show that the proposed alternating scheme with the weak predictors are significantly more effective and sample-efficient.

The reviewers in general found the high-level idea of using a series of weak predictors to narrow down the search space, and the proposed alternating search scheme, to be novel and reasonable. Also, they find the experimental validation convincing, and the proposed scheme to be highly effective and efficient. 

However, at the same time, the reviewers had the following concerns.
- The paper lacks many details, such as the pseudo-code of the algorithm, complexity analysis, implementation details, and the details of the retraining strategy.
- The proposed method is not validated against some of the SOTA methods for NAS. 
- The novelty of the method over existing iterative search space refining strategies, or NAS based on Bayesian optimization, has not been sufficiently discussed.

During the discussion period, the authors provided the code, discussion on the computational complexity, the results of the SOTA methods, and the discussion on the novelty of the proposed method over existing methods. This cleared away most of the concerns from the reviewers, resulting in a unanimous agreement to accept the paper. 

However, I have additional concerns, which I want the authors to clearly address in the revision. Most come from the lack of formal definitions and analysis. 

- There is no formal definition of “weak” and “strong” performance predictors. This should be formally defined in order to clarify what are weak and what are strong predictors. 
- There is no visualization of the actual search space while running the proposed algorithm, that is similar to Figure 2, which makes it difficult to see what happens there during the iterative search process.
- There is no analysis of the failure case - in what cases does the weak predictor miss out high-performing architectures?
- There is no theoretical or empirical analysis on how many steps, or weak predictors, are necessary to find an optimal architecture from a pool of $N$ architectures, which seems crucial in the use of the proposed algorithm.

I recommend accepting the paper since the proposed idea is interesting and seems to work well in practice, and all reviewers are unanimously positive toward it. Yet, I believe that a lot of effort should be put into analyzing how the proposed method works. The paper is too informal and looks half-baked at its current state, and I strongly recommend the authors to incorporate the discussions with the reviewers, as well as the answer to my concerns above.
Decision: Accept (Poster)