# Weak NAS Predictors Are All You Need

Junru Wu  Xiyang Dai  Dongdong Chen  Yinpeng Chen  Mengchen Liu  Ye Yu
Zhangyang Wang  Zicheng Liu  Mei Chen  Lu Yuan

# Weak NAS Predictors Are All You Need
Supplementary Material

Junru Wu  Xiyang Dai  Dongdong Chen  Yinpeng Chen  Mengchen Liu  Ye Yu
Zhangyang Wang  Zicheng Liu  Mei Chen  Lu Yuan

###### Abstract

Neural Architecture Search (NAS) finds the best network architecture by
exploring the architecture-to-performance manifold. It often trains and
evaluates a large number of architectures, causing tremendous computation
costs. 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. Given limited samples, these predictors, however,
are far from accurate to locate top architectures. In this paper, we shift the
paradigm from finding a complicated predictor that covers the whole
architecture space to a set of weaker predictors that progressively move
towards the high-performance sub-space. It is based on the key property of the
proposed weak predictors that their probabilities of sampling better
architectures keep increasing. We thus only sample a few well-performed
architectures guided by the previously learned predictor and estimate a new
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. The code is available at https://github.com/VITA-
Group/WeakNAS

Machine Learning, ICML

Figure 1: Comparison between using a set of weak predictors (our method) and
using one strong predictor (baseline) on the NAS-Bench-201 TinyImageNet
subset. Our method significantly reduces the sample amount required to find
the optimal architecture.

##  1 Introduction

Neural Architecture Search (NAS) has become a central topic in recent years
with great progress (Liu et al., 2018b; Luo et al., 2018; Wu et al., 2019;
Howard et al., 2019; Ning et al., 2020; Wei et al., 2020; Luo et al., 2018;
Wen et al., 2019; Chau et al., 2020; Luo et al., 2020). Methodologically, all
existing NAS methods try to find the best network architecture by exploring
the architecture-to-performance manifold, such as reinforced-learning-based
(Zoph & Le, 2016), evolution-based (Real et al., 2019; Yang et al., 2020) or
gradient-based (Liu et al., 2018b; Hong et al., 2020) 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 architecture-performance 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., 2018) founds that most of those methods (Ning et al., 2020; Wei
et al., 2020; Luo et al., 2018; Xu et al., 2019a; Wen et al., 2019; Chau et
al., 2020; Luo et al., 2020; Li et al., 2020) consider these two steps
independently and attempt to model the performance distribution over the whole
architecture space use a strong predictor. However, since the architecture
space is often exponentially large and highly non-convex, modeling the whole
space is very challenging even for strong predictor given limited samples.
Meanwhile, different types of predictors in these methods have to demand
handcraft design of the architecture representations to 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 to find the best architecture. We
investigate the approach of utilizing a few weak predictors on small local
spaces and progressively moving to the space where good architecture habits.
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 to 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.

Based on the above motivation, we present a novel framework that estimates a
series of weak predictors progressively. Rather than expecting a strong
predictor to model the whole space, we instead seek a line of progressive
evolving weak predictors that can connect a path to the best architecture. In
this way, it greatly simplifies the learning task of each predictor. 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 predictor
with better samples will be trained in the next iteration. We iterate until we
arrive at an embedding subspace where the best architectures reside. The weak
predictor achieved at the final iteration becomes the dedicated predictor
focusing on such a fine subspace and the best performed architecture can be
easily predicted.

Compared to existing predictor-based NAS, our method has several merits.
First, since only weak predictors are required to locate the good subspace, it
yields better sample efficiency. As shown in Figure 1, on existing NASBenches,
it costs significantly fewer samples to find the top-performance architecture
than existing strong predictor-based NAS methods and yields lower variance in
performance over multiple runs. Second, it is much less sensitive to the
architecture representation (e.g., different architecture embeddings) and the
predictor formulation design (e.g., Multilayer Perceptron (MLP), Gradient
Boosting Regression Tree, Random Forest). Experiments show our superior
robustness in all their combinations. Third, it is generalized to other search
spaces. Given a limited sample budget, it achieves the state-of-the-art
ImageNet performance on the NASNet search space.

Figure 2: An illustration of our progressive weak predictors approximation
(best viewed in color). Previous predictor-based NAS uniformly sampled in the
whole search space to fit a strong predictor; Ours progressively shrink the
sample space smaller based on predictions from previous weak predictors and
train new weak predictor towards subspace of better architectures

##  2 Our Approach

###  2.1 Revisit Predictor-based Neural Architecture Search

Neural Architecture Search (NAS) finds the best network architecture by
exploring the architecture-to-performance manifold. It can be formulated as an
optimization problem. Given a search space of network architectures $X$ and a
discrete architecture-to-performance mapping function $f:X\rightarrow P$ from
architecture set $X$ to performance set $P$, the objective is to find the best
neural architecture $x^{*}$ with the highest performance $f(x)$ in the search
space $X$:

$\displaystyle x^{*}=\operatorname*{arg\,max}_{x\in X}f(x)$ (1)

A naïve solution is to estimate the performance mapping $f(x)$ through the
full search space, however, it is prohibitively expensive since all
architectures have to be exhaustively trained from scratch. To address this
problem, predictor-based NAS learns a proxy predictor $\tilde{f}(x)$ to
approximate $f(x)$ using some architecture-performance pairs , which
significantly reduces the training cost. In general, predictor-based NAS can
be formulated as:

$\displaystyle\begin{split}\quad x^{*}&=\operatorname*{arg\,max}_{x\in
X}\tilde{f}(x|S)\\\ \textrm{s.t.}\
\tilde{f}&=\operatorname*{arg\,min}_{S,\tilde{f}\in\tilde{\mathcal{F}}}\sum_{s\in
S}\mathcal{L}(\tilde{f}(s),f(s))\,\end{split}$ (2)

where $\mathcal{L}$ is the loss function for the predictor $\tilde{f}$,
$\tilde{\mathcal{F}}$ is a set of all possible approximation to $f$,
$S:=\\{S\subseteq X\mid|S|\leq C\\}$ is the training pairs for predictor
$\tilde{f}$ given sample budget $C$. Here, $C$ is directly correlated to the
total training cost. Our objective is to minimize the loss $\mathcal{L}$ of
the predictor $\tilde{f}$ based on some sampled architectures $S$.

Previous predictor-based NAS methods attempt to solve Equation 2 with two key
steps: (1) _sampling_ some architecture-performance pairs and (2) _learning_ a
proxy accuracy predictor. First, a common practice in previous work is to
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 $\tilde{f}$ to model the performance distribution over the whole
architecture space. Since the architecture space is often enormously large and
highly non-convex, it 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 $\tilde{f}$ should be co-evolving instead of a one-time deal as done
in existing predictor-based NAS. Demonstrated in Figure 2, rather than
expecting a single strong predictor to 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-fine iterations, the ranking of sampling space is 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:

$\displaystyle\textrm{Sampling Stage:}\quad\quad\tilde{P}^{k}$
$\displaystyle=\\{\tilde{f}_{k}(s)|s\in X\setminus S^{k}\\}\ $ (3)
$\displaystyle S^{k+1}$ $\displaystyle=\\{s_{i}\\}_{i=1}^{M}\cup S^{k},$ where
$\displaystyle\,\,\tilde{f}_{k}(s_{i})\in\text{Top}_{N}(\tilde{P}^{k}),$
$\displaystyle\textrm{Learning Stage:}\quad\quad x^{*}$
$\displaystyle=\operatorname*{arg\,max}_{x\in X}\tilde{f}(x|S^{k+1})$ (4)
$\displaystyle\textrm{s.t.}\,\,\tilde{f}_{k+1}=\operatorname*{arg\,min}_{\tilde{f}_{k}\in\tilde{\mathcal{F}}}$
$\displaystyle\sum_{s\in S^{k+1}}{\mathcal{L}}(\tilde{f}(s),f(s))$

Suppose our iterative methods has $K$ iterations, at $k$-th iteration where
$k=1,2,\dots K$, we initialize our training set $S^{1}$ by randomly sampling a
few samples from $X$ to train an initial predictor $\tilde{f}_{1}$. We then
jointly optimize the sampling set $S^{k}$ and predictor $\tilde{f}_{k}$ in a
progressive manner for $K$ iterations.

(a)

(b)

(c)

Figure 3: Visualization of the search dynamics in NAS-Bench-201 Search Space.
(best viewed in color) (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 (c)
Triangle marker: Probability of sampling Top 50 architectures through out 5
iterations; Star marker: Kendall’s Tau ranking of NAS predictor in Top 50
architectures through out 5 iterations

#### Sampling Stage.

At iteration $k+1$, we first sort all the architectures in the search space
$X$ (excluding all the samples already in $S^{k}$) according to its predicted
performance $\tilde{P}^{k}$ at every iteration $k$. Given the sample budget,
we then random sample $M$ new architectures from the top $N$ ranked
architectures in $\tilde{P}^{k}$. The newly sampled architectures together
with $S^{k}$ will be regarded as $S^{k+1}$.

#### Learning Stage.

We learn a predictor $\tilde{f}^{k+1}$, where we want to minimize the the loss
$\mathcal{L}$ of the predictor $\tilde{f}^{k+1}$ based on sampled
architectures $S^{k+1}$. We then evaluate all the architectures $X$ in the
search space using the learned predictor $\tilde{f}^{k+1}$ to get the
predicted performance $\tilde{P}^{k+1}$.

#### Progressive Approximation

Through the above alternative iteration, the predictor $\tilde{f}^{k}$ would
guide the sampling process to gradually zoom into the promising architecture
samples. In addition, the good performing samples $S^{k+1}$ sampled from the
promising architecture samples would in term improve the performance of the
predictor $\tilde{f}^{k+1}$ in the well-performed architectures.

To demonstrate the effectiveness of our iterative scheme, Figure 3 (a) shows
the progressive procedure of finding the optimal architecture ${x}^{*}$ and
learning the predicted best architecture $\tilde{x}_{k}^{*}$ over $5$
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 over the optimal architecture(s) is growing better.
In Figure 3 (b), we use the error empirical distribution function (EDF)
proposed in (Radosavovic et al., 2020) 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 $5$ iterations. As
shown in Figure 3 (b), the subspace of top-performed architectures is
consistently evolving towards more promising architecture samples over $5$
iterations. In Figure 3 (c), we validate the key property of our weak
predictors that _the probabilities of sampling better architectures within the
Top $N$ predictions will keep increasing._ Based on this property, we can only
sample a few well-performed architectures guided by the predictive model to
estimate another better weak predictor. Figure 3 (c) also suggest the NAS
predictor’s ranking among the top-performed models is gradually refined, due
to more and more architectures in the top region are sampled.

###  2.3 Relationship to Bayesian Optimization

Our method is loosely connected to Bayesian Optimization (BO), or can be
regarded as a simplified variant which does not have the typical acquisition
function based on explicit uncertainty-based modeling such as Gaussian Process
(which are often difficult to scale up). In contrast, we achieve the implicit
exploration-exploitation trade-off by the adaptive sampling strategy. In
details, at each iteration, instead of choosing all of Top $N$ models by the
latest predictor, we randomly sample $M$ models from Top $N$ models to explore
new architectures in a probabilistic manner. By varying the ratio
$\epsilon=M/N$ and the sampling strategy (e.g., uniform, linear-decay or
exponential-decay), an exploitation-exploration trade-off can be performed.
This scheme is very similar to the $\epsilon$-greedy (Sutton & Barto, 2018)
approach in the RL context. The detailed analysis will be shown in the
ablation part (Table 2).

The reason why our method is so effective even with such simplification is
presumably related to the inherently structured NAS search space. In details,
existing NAS spaces are created either by varying operators from a pre-defined
operator set (DARTS/NAS-Bench-101/201 Search Space) or by varying width or
depth (FBNet Search Space). Therefore, the architectures in the search space
often show highly clustered distribution and the best performers are often
gathered close to each other (as we visualize the distribution of NAS-
Bench-101/201 in the Figure 1 of Supplementary). This is also our work’s
underlying assumption: we can progressively connect a line from the
initialization to the finest subspace, where the best architecture resides. At
the beginning stage of the search, since the weak NAS predictor only roughly
fits the whole space, the sampling operation will induce more exploration and
guide the movement to better clusters. In contrast, in the later stages, as
the weak predictors fit better it will focus more on the good-performing
clusters, thus more exploitation is performed. In this sense, our weak NAS
predictors provide a natural evolution between the exploration and
exploitation.

###  2.4 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 $\tilde{f}$ can be formulated as a
regression problem (Wen et al., 2019) or a ranking (Ning et al., 2020)
problem. The choice of predictors is diverse, and usually critical to final
performance (e.g. MLP (Ning et al., 2020; Wei et al., 2020), LSTM (Luo et al.,
2018), GCN (Wen et al., 2019; Chau et al., 2020), Gradient Boosting Tree (Luo
et al., 2020)). To illustrate our framework is generalizable and robust to the
specific choice of predictors, we compare the following predictor variants.

  * •

Multilayer perceptron (MLP): MLP is the baseline commonly used in predictor-
based NAS (Ning et al., 2020) due to its simplicity. For each weak predictor,
we use a 4-layer MLP with hidden layer dimension of (1000, 1000, 1000, 1000)
which is sufficient to model the architecture encoding.

  * •

Gradient Boosting Regression Tree (GBRT): Tree-based methods have recently
been preferred in predictor-based NAS (Luo et al., 2020; Siems et al., 2020)
since it is more suitable to model discrete representation of the
architectures. For each weak predictor, we use the Gradient Boosting
Regression Tree based on XGBoost (Chen & Guestrin, 2016) implementation
consist of 1000 Trees.

  * •

Random Forest: Random Forrest is another variant of tree-based predictor, it
differs from Gradient Boosting Trees in that it combines decisions at the end
instead of along each hierarchy, and thus more robust to noise. For each weak
predictor, we use a Random Forrest consist of 1000 Forests.

The selection of features to represent the architecture search space and learn
the predictor is also sensitive to the performance. Previous methods tended to
hand craft the feature for the best performance (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 is used to encode the
choice of operator.

  * •

Adjacency Matrix: In NAS-Bench-101, we used the encoding scheme as well as
(Ying et al., 2019; Wei et al., 2020), where a 7$\times$7 adjacency matrix
represents the graph connectivity and a 7-dimensional vector represents the
choice of operator, on every node.

We compare the robustness across different predictors under our framework
shown in Figure 4. We can see that all predictors perform similarly among
different datasets. Comparing performances on NAS-Bench-101 and NAS-Bench-201,
although different architecture encoding methods are used, our method can
perform similarly well among different predictors, which demonstrates that our
proposed method is robust to different predictors and features selection.

(a)

(b)

Figure 4: Evaluations of robustness across different predictors on NAS-Bench-101 Test Set and NAS-Bench-201 on CIFAR10 subset. Central line demonstrates the average, shade demonstrates the confidence interval over 100 runs. Method |  #Queries |  Test Acc.(%) |  SD(%) |  Test Regret(%)
---|---|---|---|---
Random Search |  2000 |  93.64 |  0.25 |  0.68
Reg Evolution (Real et al., 2019) |  2000 |  93.96 |  0.05 |  0.36
Neural Predictor (Wen et al., 2019) |  2000 |  94.04 |  0.05 |  0.28
NAO (Luo et al., 2018) |  2000 |  93.90 |  0.03 |  0.42
Ours (1 Strong Predictor) |  2000 |  93.92 |  0.08 |  0.04
Ours (1 Weak Predictors) |  100 |  93.47 |  0.18 |  0.85
Ours (4 Weak Predictors) |  400 |  94.15 |  0.14 |  0.17
Ours (10 Weak Predictors) |  1000 |  94.21 |  0.07 |  0.11
Ours (20 Weak Predictors) |  2000 |  94.23 |  0.02 |  0.09
Table 1: Ablation on searching efficiency by limiting the total amount of
queries over 100 runs on NAS-Bench-101

##  3 Experiments

###  3.1 Setup

Sampling methods | M | TopN | #Queries | Test Acc.(%) | SD(%) | Test Regret(%)
---|---|---|---|---|---|---
Uniform | 100 | 10000 | 2000 | 93.98 | 0.12 | 0.34
Uniform | 100 | 1000 | 2000 | 94.23 | 0.02 | 0.09
Uniform | 100 | 100 | 2000 | 94.17 | 0.03 | 0.14
Uniform | 100 | 1000 | 2000 | 94.23 | 0.02 | 0.09
Linear-decay | 100 | 1000 | 2000 | 94.03 | 0.05 | 0.29
Exponential-decay | 100 | 1000 | 2000 | 93.83 | 0.08 | 0.49
Table 2: Ablation on exploitation-exploration trade-off over 100 runs on NAS-
Bench-101

NAS-Bench-101 (Ying et 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 connectivity of DAG can be arbitrary with
a maximum number of 7 nodes and 9 edges (2) Each nodes on the DAG can choose
from operator of 1$\times$1 convolution, 3$\times$3 convolution or 3$\times$3
max-pooling. After removing duplications, the dataset consists of 423,624
diverse architectures trained on CIFAR10 dataset with each architecture
trained for 3 trials.

NAS-Bench-201 (Dong & Yang, 2020) is another recent NAS benchmark with a
reduced DARTS-like search space. The DAG of each cell is fixed similar to
DARTS(Liu et al., 2018b), however we can choose from 5 different operations
(1$\times$1 convolution, 3$\times$3 convolution, 3$\times$3 avg-pooling, skip,
no connection) on each of the 6 edges totaling a search space of 15,625
architectures. The dataset is trained on 3 different datasets
(CIFAR10/CIFAR100/ImageNet16-120) with each architecture trained for 3 trials.

For experiments on both benchmarks, we followed the same setting as (Wen et
al., 2019). We use the validation accuracy as search signal, while test
accuracy is only used for reporting the accuracy on the model that was
selected at the end of a 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.

Open Domain Search: 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 a weight-sharing supernet approach (Guo
et al., 2019) and use supernet accuracy as a performance proxy to train our
Weak NAS predictors.

(a)

(b)

(c)

Figure 5: Comparison to SOTA on NAS-Bench-201 by varying number of samples.
Central line demonstrates the average, shade demonstrates the confidence
interval over 100 runs.

(a)

(b)

Figure 6: Comparison to SOTA on NAS-Bench-101 by varying number of samples on
Validation Set and Testing Set. Central line demonstrates the average, shade
demonstrates the confidence interval over 100 runs.

###  3.2 Ablation Studies

We conduct a series of ablation studies on the effectiveness of proposed
method on NAS-Bench-101.

We first validate the effectiveness of our iterative scheme by progressively
adding more weak predictors (from 1 to 20) and the performance is keep growing
as shown in Table 1, this demonstrates the key property of our method that
probability of sampling better architectures keeps increasing as more
iteration goes.

We also study the searching efficiency by limiting the number of queries.
Given the same number of queries, weak predictors are more competitive than a
single strong predictor, since the strong predictor’s training samples are
randomly sampled from the whole search space, while weak predictors’ samples
are guided by a series of predictors. When compared to the results from
popular predictor-based NAS methods, such as NAO (Luo et al., 2018) and Neural
Predictor (Wen et 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 study the exploitation-exploration trade-off in Table 2 by
investigating two settings: (a) We gradually increase $N$ to allow for more
exploration, similar to controlling $\epsilon$ in the epsilon-greedy (Sutton &
Barto, 2018) approach in the RL context; (b) We vary the sampling strategy
from Uniform, Linear-decay to Exponential-decay (top models get higher
probabilities by following either linear-decay or exponential-decay
distribution). We empirically observed that (a) The performance drops more
(0.25% vs 0.06%) when use more exploration (K=10000 vs K=100). This indicates
that extensive exploration is not optimal for NAS-Bench-101; (b) Uniform
sampling method yields better performance than sampling method that biased
towards top performing model (e.g. linear-decay, exponential-decay). This
indicates good architectures are evenly distributed within the Top 1000
prediction of Weak NAS, therefore a simple uniform sampling strategy for
exploration is more optimal in NAS-Bench-101. To conclude, our Weak NAS
Predictor strike a good balance between exploration and exploration.

###  3.3 Comparison to State-of-the-art (SOTA) Methods

We evaluate our method on both NAS-Bench-101 and NAS-Bench-201. We also apply
our method to open domain search directly on ImageNet dataset using NASNet
search space.

NAS-Bench-101

We conduct experiments on the popular NAS-Bench-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). Table 5 shows that our method significantly
outperforms baselines in terms of sample efficiency. Specifically, our method
costs 44$\times$, 20$\times$, 17$\times$, and 2.66$\times$ less samples to
reach the optimal architecture, compared to Random Search, Regularized
Evolution (Real et al., 2019), MCTS (Wang et al., 2019b), LaNAS (Wang et al.,
2019a), respectively.

We then plot the best accuracy against number of samples in Figure 6 to show
the sample efficiency on both validation and test set of NAS-Bench-101, we can
see that our method consistently requires fewer sample to reach higher
accuracy, compared to Random Search and Regularized Evolution.

Model | #Queries | Top-1 Err.(%) | Top-5 Err.(%) | Params(M) | FLOPs(M) | GPU Days
---|---|---|---|---|---|---
MobileNetV2 | - | 25.3 | - | 6.9 | 585 | -
ShuffletNetV2 | - | 25.1 | - | 5.0 | 591 | -
SNAS(Xie et al., 2018) | - | 27.3 | 9.2 | 4.3 | 522 | 1.5
DARTS(Liu et al., 2018b) | - | 26.9 | 9.0 | 4.9 | 595 | 4.0
P-DARTS(Chen et al., 2019) | - | 24.4 | 7.4 | 4.9 | 557 | 0.3
PC-DARTS(Xu et al., 2019b) | - | 24.2 | 7.3 | 5.3 | 597 | 3.8
DS-NAS(Xu et al., 2019b) | - | 24.2 | 7.3 | 5.3 | 597 | 10.4
NASNet-A (Zoph et al., 2018) | 20000 | 26.0 | 8.4 | 5.3 | 564 | 2000
AmoebaNet-A (Real et al., 2019) | 10000 | 25.5 | 8.0 | 5.1 | 555 | 3150
PNAS (Liu et al., 2018a) | 1160 | 25.8 | 8.1 | 5.1 | 588 | 200
NAO (Luo et al., 2018) | 1000 | 24.5 | 7.8 | 6.5 | 590 | 200
Weak NAS (Ours) | 1000 | 23.5 | 6.8 | 5.9 | 597 | 1.08$\star$

Table 3: Comparsion to SOTA results on ImageNet using NASNet search space. ⋆Measured on a single Tesla P100 GPU Method | CIFAR10 | CIFAR100 | ImageNet16-120
---|---|---|---
| valid | test | valid | test | valid | test
Random Search | 7873.98 | 7782.12 | 7716.85 | 7621.24 | 7776.55 | 7726.15
Reg Evolution (Real et al., 2019) | 478.41 | 563.25 | 399.78 | 438.24 | 802.57 | 715.12
Weak NAS (Ours) | 119.17 | 186.30 | 86.08 | 89.26 | 159.33 | 176.61
Table 4: Comparison on the number of samples required to find the global optimal over 250 runs on NAS-Bench-201 Method | #Queries
---|---
Random Search | 188139.8
Reg Evolution (Real et al., 2019) | 87402.7
MCTS (Wang et al., 2019b) | 73977.2
LaNAS (Wang et al., 2019a) | 11390.7
Weak NAS (Ours) | 4275.3
Table 5: Comparison on the number of samples required to find the global
optimal architecture over 100 runs on NAS-Bench-101.

We further evaluate our method on NAS-Bench-201. Since it is relatively newly
released, we compare with two baseline methods Regularized Evolution (Real et
al., 2019) and random search using our own implementation. Shown in Table 4,
we conduct searches on all three subsets (CIFAR10, CIFAR100, ImageNet16-120)
and report the average number of samples needed to reach global optimal over
250 runs. It is obvious to see that our method requires the minimum number of
samples among all settings.

We also conduct a controlled experiment by varing the number of samples. As in
Figure 5, our average performance over different number of samples yields a
clear gain over Regularized Evolution (Real et al., 2019) in all three
subsets. Our confidence interval is also tighter than Regularized Evolution,
showcasing our method’s superior stability/reliability.

Open Domain Search

In order to demonstrate our method’s generalizability, we further apply it 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 3, it is clear to see that, using
fewest samples among all methods using the same search space, our method
achieves state-of-the-art ImageNet top-1 error with similar number of
parameters and FLOPs. Our searched architecture is also competitive to expert-
design networks. Comparing with the previous SOTA predictor-based NAS method
(Luo et al., 2018), our method reduces 0.9% top-1 error, using the same number
of samples which is significant. The strong performance of our NAS-predictor
also compensate for the ranking mismatch introduced by using weight-sharing
supernet, we are able to achieve better performance with a fraction of GPU
hours compare to all other methods. Overall, this experiment well proves that
our method is robust, generalizable, and can be effectively applied to real-
world open domain search.

##  4 Conclusion

In this paper, we present a novel predictor-based NAS framework that
progressively shrinks the sampling space, by learning a series of weak
predictors that can connect towards the best architectures. We argue that
using a single strong predictor to model the whole search space with limited
samples may be too challenging and seemingly unnecessary. Instead, by co-
evolving the sampling 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. Extensive
experiments on popular NAS benchmarks prove that proposed method is both
sample-efficient and robust to various combinations of predictors and
architecture encoding means. We further apply our method to open domain search
and demonstrate its generalization. Our future work will investigate how to
jointly learn the predictor and encoding in our framework.

## References

  * Chau et al. (2020) Chau, T., Dudziak, Ł., Abdelfattah, M. S., Lee, R., Kim, H., and Lane, N. D.  Brp-nas: Prediction-based nas using gcns.  _arXiv preprint arXiv:2007.08668_ , 2020.
  * Chen & Guestrin (2016) Chen, T. and Guestrin, C.  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.
  * Chen et al. (2019) Chen, X., Xie, L., Wu, J., and Tian, Q.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1294–1303, 2019.
  * Dong & Yang (2020) Dong, X. and Yang, Y.  Nas-bench-201: Extending the scope of reproducible neural architecture search.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HJxyZkBKDr.
  * Guo et al. (2019) Guo, Z., Zhang, X., Mu, H., Heng, W., Liu, Z., Wei, Y., and Sun, J.  Single path one-shot neural architecture search with uniform sampling.  _arXiv preprint arXiv:1904.00420_ , 2019.
  * Hong et al. (2020) Hong, W., Li, G., Zhang, W., Tang, R., Wang, Y., Li, Z., and Yu, Y.  Dropnas: Grouped operation dropout for differentiable architecture search.  In _International Joint Conference on Artificial Intelligence_ , 2020\.
  * Howard et al. (2019) Howard, A., Sandler, M., Chu, G., Chen, L.-C., Chen, B., Tan, M., Wang, W., Zhu, Y., Pang, R., Vasudevan, V., et al.  Searching for mobilenetv3.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1314–1324, 2019.
  * Hu et al. (2020) Hu, Y., Liang, Y., Guo, Z., Wan, R., Zhang, X., Wei, Y., Gu, Q., and Sun, J.  Angle-based search space shrinking for neural architecture search.  _arXiv preprint arXiv:2004.13431_ , 2020.
  * Li et al. (2020) Li, Y., Dong, M., Wang, Y., and Xu, C.  Neural architecture search in a proxy validation loss landscape.  In _International Conference on Machine Learning_ , pp. 5853–5862. PMLR, 2020.
  * Liu et al. (2018a) Liu, C., Zoph, B., Neumann, M., Shlens, J., Hua, W., Li, L.-J., Fei-Fei, L., Yuille, A., Huang, J., and Murphy, K.  Progressive neural architecture search.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 19–34, 2018a.
  * Liu et al. (2018b) Liu, H., Simonyan, K., and Yang, Y.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018b.
  * Luo et al. (2018) Luo, R., Tian, F., Qin, T., Chen, E., and Liu, T.-Y.  Neural architecture optimization.  In _Advances in neural information processing systems_ , pp. 7816–7827, 2018.
  * Luo et al. (2020) Luo, R., Tan, X., Wang, R., Qin, T., Chen, E., and Liu, T.-Y.  Neural architecture search with gbdt.  _arXiv preprint arXiv:2007.04785_ , 2020.
  * Ning et al. (2020) Ning, X., Zheng, Y., Zhao, T., Wang, Y., and Yang, H.  A generic graph-based neural architecture encoding scheme for predictor-based nas.  _arXiv preprint arXiv:2004.01899_ , 2020.
  * Radosavovic et al. (2020) Radosavovic, I., Kosaraju, R. P., Girshick, R., He, K., and Dollár, P.  Designing network design spaces.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10428–10436, 2020.
  * Real et al. (2019) Real, E., Aggarwal, A., Huang, Y., and Le, Q. V.  Regularized evolution for image classifier architecture search.  In _Proceedings of the aaai conference on artificial intelligence_ , volume 33, pp. 4780–4789, 2019.
  * Siems et al. (2020) Siems, J., Zimmer, L., Zela, A., Lukasik, J., Keuper, M., and Hutter, F.  Nas-bench-301 and the case for surrogate benchmarks for neural architecture search.  _arXiv preprint arXiv:2008.09777_ , 2020.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Wang et al. (2019a) Wang, L., Xie, S., Li, T., Fonseca, R., and Tian, Y.  Sample-efficient neural architecture search by learning action space, 2019a.
  * Wang et al. (2019b) Wang, L., Zhao, Y., Jinnai, Y., Tian, Y., and Fonseca, R.  Alphax: exploring neural architectures with deep neural networks and monte carlo tree search.  _arXiv preprint arXiv:1903.11059_ , 2019b.
  * Wei et al. (2020) Wei, C., Niu, C., Tang, Y., and Liang, J.  Npenas: Neural predictor guided evolution for neural architecture search.  _arXiv preprint arXiv:2003.12857_ , 2020.
  * Wen et al. (2019) Wen, W., Liu, H., Li, H., Chen, Y., Bender, G., and Kindermans, P.-J.  Neural predictor for neural architecture search.  _arXiv preprint arXiv:1912.00848_ , 2019.
  * Wu et al. (2019) Wu, B., Dai, X., Zhang, P., Wang, Y., Sun, F., Wu, Y., Tian, Y., Vajda, P., Jia, Y., and Keutzer, K.  Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 10734–10742, 2019.
  * Xie et al. (2018) Xie, S., Zheng, H., Liu, C., and Lin, L.  Snas: stochastic neural architecture search.  _arXiv preprint arXiv:1812.09926_ , 2018.
  * Xu et al. (2019a) Xu, Y., Wang, Y., Han, K., Jui, S., Xu, C., Tian, Q., and Xu, C.  Renas: Relativistic evaluation of neural architecture search.  _arXiv preprint arXiv:1910.01523_ , 2019a.
  * Xu et al. (2019b) Xu, Y., Xie, L., Zhang, X., Chen, X., Qi, G.-J., Tian, Q., and Xiong, H.  Pc-darts: Partial channel connections for memory-efficient differentiable architecture search.  _arXiv preprint arXiv:1907.05737_ , 2019b.
  * Yang et al. (2020) Yang, Z., Wang, Y., Chen, X., Shi, B., Xu, C., Xu, C., Tian, Q., and Xu, C.  Cars: Continuous evolution for efficient neural architecture search.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1829–1838, 2020.
  * Ying et al. (2019) Ying, C., Klein, A., Christiansen, E., Real, E., Murphy, K., and Hutter, F.  Nas-bench-101: Towards reproducible neural architecture search.  In _International Conference on Machine Learning_ , pp. 7105–7114, 2019.
  * Zoph & Le (2016) Zoph, B. and Le, Q. V.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ , 2016.
  * Zoph et al. (2018) Zoph, B., Vasudevan, V., Shlens, J., and Le, Q. V.  Learning transferable architectures for scalable image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 8697–8710, 2018.

In this supplementary, we provide more evidence to support our assumption of
NAS-Bench space search in Section 2.3, showing that architectures in the NAS
search space often show highly clustered distribution and the best performers
are often gathered close to each other.

We provide the following:

  * •

Histogram Visualization of NAS-Bench Search Spaces

  * •

t-SNE Visualization of NAS-Bench Search Space

  * •

Comparsion to nearest neighbour sampling methods.

##  Appendix A Visualization of NAS-Bench Search Space

###  A.1 Histogram of NAS-Bench-101/201 Search Space

Figure 7 and 8 illustrates the histogram of architecture performance in NAS-
Bench-101(Ying et al., 2019) and NAS-Bench-201(Dong & Yang, 2020),
respectively. We can see both NAS-Bench-101 and NAS-Bench-201 search spaces
bias heavily towards good performing architectures, and the histogram show
highly clustered distribution on the good performers models.

Figure 7: Histogram of Architecture Performance in NAS-Bench-101

(a) CIFAR10

(b) CIFAR100

(c) ImageNet16-120

Figure 8: Histogram of Architecture Performance in NAS-Bench-201 Figure 9:
t-SNE Visualization of NAS-Bench-201 Search Space CIFAR100 Subset. The
accuracy of architectures is encoded by color. Best View in Color

###  A.2 t-SNE Visualization of NAS-Bench-201 Search Space

In Figure 9, We show the t-SNE Visualization of NAS-Bench-201 on CIFAR100
subset. The accuracy of architectures is encoded by color, where green color
denote better performance, orange denote color worse performance. We can see
that good performing models (accuracy $>$ 65%) are usually gathered close
together in the embedding space.

##  Appendix B Comparsion to nearest neighbour sampling method

We fixed $N=1000$ and $M=100$ and further replace the sampling methods from
Top$N$ models with the extreme case of nearest neighbour sampling. Given a
network architecture embedding $s$ in NAS-Bench-101 Search Space, we first
define a nearest neighbour function $N(s)$ as architecture that differ from
$s$ by a edge or a operation. At each iteration, we random sample a initial
sample $s_{i}$ from TopN predictions $\text{Top}_{N}(\tilde{P}^{k})$ and
sample all of its nearest neighbour architecture in $N(v_{0})$. We than let
the new $s_{i+1}=\operatorname*{arg\,max}_{s\in N(s_{i})}f(s)$. We repeat the
process iteratively until we reach a local maximum such that $\forall v\in
N(s),f(s)\geqslant f(v)$ or the sampling budget $M$ of the iteration is
reached. From the experiment in Table6, we found nearest neighbour sampling
has slight improvement from $94.23\%$ to $94.28\%$ when compare to uniform
sampling, the good performance of nearest neighbour further shows that in NAS-
Bench search spaces, good performers are often gathered close to each other.

Sampling methods | #Queries | Test Acc.(%) | SD(%)
---|---|---|---
Uniform | 2000 | 94.23 | 0.02
Linear-decay | 2000 | 94.03 | 0.05
Exponential-decay | 2000 | 93.83 | 0.08
Nearest neighbour | 2000 | 94.28 | 0.01
Table 6: Comparsion to nearest neighbour sampling method