Multi-objective Neural Architecture Search via Predictive Network Performance Optimization
Authors: Han Shi
Renjie Pi
Hang Xu
Zhenguo Li
James T. Kwok
Tong Zhang
Venue:  (2020)

Abstract: Neural Architecture Search (NAS) has shown great potentials in finding a better neural network design than human design. Sample-based NAS is the most fundamental method aiming at exploring the search space and evaluating the most promising architecture. However, few works have focused on improving the sampling efficiency for a multi-objective NAS. Inspired by the nature of the graph structure of a neural network, we propose BOGCN-NAS, a NAS algorithm using Bayesian Optimization with Graph Convolutional Network (GCN) predictor. Specifically, we apply GCN as a surrogate model to adaptively discover and incorporate nodes structure to approximate the performance of the architecture. For NAS-oriented tasks, we also design a weighted loss focusing on architectures with high performance. Our method further considers an efficient multi-objective search which can be flexibly injected into any sample-based NAS pipelines to efficiently find the best speed/accuracy trade-off. Extensive experiments are conducted to verify the effectiveness of our method over many competing methods, e.g. 128.4x more efficient than Random Search and 7.8x more efficient than previous SOTA LaNAS for finding the best architecture on the largest NAS dataset NasBench-101.

Under review as a conference paper at ICLR 2020
MULTI-OBJECTIVE NEURAL ARCHITECTURE SEARCH VIA PREDICTIVE NETWORK PERFORMANCE OPTI- MIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
Neural Architecture Search (NAS) has shown great potentials in finding a better neural network design than human design. Sample-based NAS is the most fun- damental method aiming at exploring the search space and evaluating promising architecture. However, few works have focused on improving the sam- pling efficiency for a multi-objectivv NAS. Inspired by the nature of the graph structure of a neural network, propose BOGCN-NAS, a NAS algorithm us- ing Bayesian Optimization with Graph Convolutional Network (GCN) predictor. Specifically, we apply GCN as a surrogate model to adaptively discover and in- corporate nodes structure to approximate the performance of the architecture. For NAS-oriented tasks, we also design a weighted loss focusing on architectures with high performance. Our method further considers an efficient multi multi-objective search which can be flexibly injected into any sample-based NAS pipelines efficiently find the best speed/accuracy trade-off. Extensive experiments are con- ducted to verify the effectiveness of our method over many competing methods, e.g. 128.4x more efficient than Random Search and 7.8x more efficient than pre- vious SOTA LaNAS for finding the best architecture on the largest NAS dataset NASBench-101..
most
INTRODUCTION
Recently Neural Architecture Search (NAS) has aroused surge of interest by its potentials of free- ing the researchers from tedious and time-consuming architecture tuning for each new task and dataset. Specifically, NAS has already shown some competitive results comparing with hand-crafted architectures in computer vision: classification (Real et al. 2019b), detection, segmentation (Ghiasi (Chu et al. 2019). Meanwhile, NAS has also achieved remarkable results in natural language processing tasks (Luong al.) 2018
jet al. 2019 Chen et al., 2019 Liu et al. 2019a) and
So et al. 2019).
A variety of search strategies have been proposed, which may be categorized into groups: shot NAS algorithms (Liu et al.] 2019b [ham et al., 2018 Luo et al.] 2018), and sample-based algorithms (Zoph & Le] 2017] Liu et al. 2018a Real et al. 2019b). One-shot NAS algorithms em- bed the architecture searching process into the training stage by using weight sharing, continuous relaxation or network morphisms. However, those methods cannot guarantee the optimal perfor- mance of the final model due to those approximation tricks and is usually sensitive to the initial seeds (Sciuto et al. 2019). On the other hand, sample-base algorithms are relatively slower but reliable. They explore and exploit the search space using some general search algorithms by provid- ing potential candidates with higher accuracy. However, requires fully training of huge amounts of candidate models.
Typically, the focus of most existing NAS methods has been on the accuracy of the final searched model alone, ignoring the cost spent in the search phase. Thus, the comparison between existing search algorithms for NAS is very difficult. (Wang et al., 2019b) gives us an example of evaluating the NAS algorithms from this view. They compare the number of training architectures sampled until finding the global optimal architecture with the top accuracy in the NAS datasets. Besides accuracy, in real applications, there many other objectives we should concern, such speed/accuracy

---

Under review as a conference paper at ICLR 2020
Hence, in this paper, we aim designing efficient multi-objectivv NAS algorithm to adaptively explore the search space and capture the structural information of architectures related to the performance.
trade-off.
The common issue faced by this problem is that optimizing objective functions is computationally expensive and the search space always contains billions of architectures. To tackle this problem, we present BOGCN-NAS, a NAS algorithm that utilizes Bayesian Optimization (BO) together with Graph Convolutional Network (GCN). BO is an efficient algorithm for finding the global optimum of costly black-box function (Mockus et al. 1978). In our method, we replace the popular Gaus- sian Processes model with a proposed GCN model the surrogate function for BO [Jones] (00T). We have found that GCN can generalize fairly well with just few architecture-accune its training set. As BO balances exploration and exploitation during searching and GCN extracts embeddings that can well represent model architectures, BOGCN-NAS is able to obtain the opti- mal model architecture with only few samples from the search space. Thus, our method is more resource-efficient than the previous ones. Graph neural network has been proposed in previous work for predicting the parameters of the architecture using a graph hypernetwork (Zhang et al. 2019). However, it's still one-shot NAS method and thus cannot ensure the performance of the final found model. In contrast, we use graph embedding to predict the performance directly and can guarantee performance as well.
pairs as
The proposed BOGCN-NAS outperforms current state-of-the-ar searching methods, including Evo- lution (Real et al.) 2019b), MCTS (Wang et al.] 20195), LaNAS (Wang et al. (019a). We observe consistent gains on multiple search space for CV and NLP tasks, i.e., NASBench- 101 (denoted NAS- Bench) (Ying et al. 2019) and LSTM-12K (toy dataset). In particular, our method BOGCN-NAS is 128.4x more efficient than Random Search and 7.8x more efficient than previous SOTA LaNAS on NASBench (Wang al. 2019a). We apply our method multi-objective NAS further, considering adding more search objectives including accuracy and number of parameters. Our method can find more superior Pareto front on NASBench. Our algorithm applied on open domain search with NASNet search space and ResNet Style search space, which finds competitive models in both sce- narios. The results of experiment demonstrate our proposed algorithm can find a more competitive Pareto front compared with other sample-based methods.
2 RELATED WORK
2.1 BAYESIAN OPTIMIZATION
Bayesian Optimization aims to find the global optimal over a compact subset X' (here we consider maximization problem):
x² arg max fz)
(1)
#Ex
Bayesian Optimization considers prior belief about objective function and updates posterior prob- ability with online sampling. Gaussian Processes (GPs) is widely used as surrogate model to approximate the objective function (Jones) 200T). And Expected Improvement acquisition function often adopted (Mockus et al. 1978). For the hyperparameters of the surrogate model G, we define
((x) p(x; D, θ) - [Ibest
(2)
o (x; (z;
where μxx;; D,O) O) is the predictive mean, (x; D, θ) is the predictive variance and f(rest the maximal value observed. The Expected Improvement (EI) criterion is defined as follows.
azr(x; D) = o(:; (())()) 1 +,
(3)
where (N::; 0, 1) is the probability density function of standard normal and +(;; 0,; 1) is its cumu- lative distribution.
2.2 MULTI-OBIECTIVE OPTIMIZATION
Without loss of generality about mar mán, given search space X' and objectives fi X + R, ..., fm : X + variable X, e X' dominates variable X₂ E X' (denoted X, > X²) if (i) [((x)) > f1(x2) Vi {1,...,m) and (ii) fx() > fx2) for at least one (1....mm). X*
2

---

Under review as a conference paper at ICLR 2020
Updatt GCN Predictor
Sampling Training..
Teluain GCN Tuined Archo
Frnieadi
Gkdbl
Bayessinn
SON Predictor
ongression
Handomie
Embreddings with
Caloslate
batimated waluee
Upddete Beyrosan Rear Trained
Anzle from vadimatied Parelu front, Irained Archs
Estimate Parelo Frunt sempled
Trained Archs
Exlimated
Bayesian Regression
Actual Training.
Input
Perimared f2
Figure The overview of our proposed algorithm. BOGCN-NAS is integrated by GCN and Bayesian Linear Regression, including iterative phases: 1) Sampling and Training; 2) Update GCN predictor. During phase-one, we randomly sample a group of architectures from the search space as candidate pool and calculate predicted objective f. Then estimated Pareto front is constructed by and Pareto optimal points are selected as proposed architectures. Then we fully train them and add into trained architecture During phase-two, we further retrain the GCN predictor with U. When there is only one objective, the Pareto front reduces to one optimal architecture.
(U). The Bayesian regression is updated with U.
Pareto optimal if there is no X X' that domaines X* The set all Pareto optimal architectures consitutes the Pareto front Py. A multi-objective optimization problem (MOP) aims at finding such input E X that cannot dominated by any variable in (Marler Arora 2004).
2.3 GRAPH CONVOLUTIONAL NETWORK
Let the graph be G E). where V is set of N nodes, and E is the set of edges. Let its adjacency matrix be A and feature matrix be X. The graph convolutional network (GCN) learning model for graph-stre -tructutr data (Kipf & Welling 2016). For a L-layer GCN, the layer-wise propagation rule is given by:
H -(H0) = A
(4)
where Ā + is the identity matrix, D) diagonal matrix with D Σラ= A.j H()
and (1))) are the feature map and weight at the (-th layer respectively, and ReLU(.) is the ReLU activation function. (0) is the original feature matrix X, and (4) is the graph embedding matrix.
BOGCN-NAS
To search for the optimal architecture more efficiently, we proposed BOGCN-NAS by using pre- dictive network performance Optimization with the GCN (Section[..2) while utilizing the Bayesian Optimization. Figure shows the overview of the proposed algorithm.
3.1 MULTI-OBIECTIVE NAS
We formulate NAS problem as a multi-objective optimization problem over the architecture search space A where objective functions be accuracy, latency, number of parameters, etc. We aim to find architectures on the Pareto front of AA. Specifically, when m = 1, it reduces to single-objective (usually accuracy) NAS and the corresponding Pareto front reduces
optimal architecture.
3

---

Under review as a conference paper at ICLR 2020
3.2 GCN PREDICTOR
GCN predictor predicts the performance (like accuracy) of an architecture. Compared with MLP and LSTM predictors proposed before (Wang et al. 2019b), GCN can preserve the context of graph data better. Another important characteristic of GCN is its ability to handle variable number of nodes, while an MLP cannot take larger architecture as the input. Even though the LSTM can handle variable-length sequences, its performance is not competitive because of the flat string encoding.
A neural network can be viewed as directed attributed graph, in which each node represents an operation (such as convolution operation) and each edge represents a data flow. As concrete illustration, we use the architectures in the NASBench dataset (Ying et al. 2019) as example. The idea can be casily extended to other architectures. In NASBench, each architecture is constituted by stacking multiple repeated cells. Thus, we will focus searching the cell architecture. An example cell in NASBench illustrated on the left side of Figure where "input" represents the input of the cell, "output" represents the output of the cell, "1 Conv, Conv, Max Pooling" are three different operations (5 operations totally).
We propose encode the cell into an adjacency matrix A (asymmetric) and feature matrix X, as the input of our GCN predictor. Note that the vanilla GCN only extracts the node embeddings, while we want obtain graph embedding. Following (Scarselli et al. 2008), we add global node to the original graph of the cell and let every node point at the global node. The adjacency matrix can be obtained directly from the graph structure. For the feature matrix, we use the one-hot coding scheme for each operation. Besides the original 5 different operations defined in NASBench, we add another operation (global node) into coding scheme.
We feed A and X a multi-layer GCN model obtain the embedding of every node (L) by (Eq. 4p. For high-level prediction, we leave original nodes out and take the embedding of global node solely because already has the overall context of the architecture. Followed by one fully-connected layer with sigmoid activation function, we can get the predicted accuracy. In training phase, we use MSE loss for regression optimization.
3.3 INCORPORATING BO INTO GCN
Bayesian Optimization is an efficient model for search and optimization problems, which considers balancing both exploitation and exploration balanced. It depends on updating the posterior distribu- tion with the samples drawn from the search space based on one cheap surrogate model.
GPs is one of the most popular choices because Gaussian distribution is self- cofjjcoeee such that a posterior distribution is also the same form as the prior. (Kandasamy et al. 2018) and (Jin et al.) 2019) both define the heuristic distance between neural architectures and use GPs with defined distence for searching. However, since the computation increases cubically with the number of samples (Snock al.) 2015), GPs is costly for NAS problem, whose search space is always huge. Another drawback for GPs is that it cannot handle graph-data directly without a special encoding scheme. In this work, we replace the popular surrogate model with our GCN predictor and take the uncertainty into consideration.
Inspired by previous work (Snock al. 2015). we train the GCN predictor first with the trained architecture set DD containing architectures {(A,, X.) with their actual performances ( then during searching, we replace the last fully connected layer with Bayesian Linear Regressor (BLR) for Bayesian estimation and retain GCN related layers for point estimation. We only consider the uncertainty of the weights on the last fully-comnected layer. We denote the embedding function of global node by o(.,-) = [chn (: :), o2((; )..,, Gal., ")[T" We can get the embedding of every architecture ([ X,) from the trained architecture set DD and treat them as the basis functions for BO. For clarifying, define & to be the design matrix where D. (A,,
Different from typical Bayesian Linear Regression (BLR) (Bishop) 2006), the final layer of our GCN predictor contains non-linear activation function. Here we use the inverse function trick to avoid the non-trivial variant. Without fitting the true accuracy t, we prefer to estimate the value before the activation function logit(t) such that we convert non-linear regression to linear regression problem. The key of BO is the order of the acquisition function over all sampled architectures rather than true values. Due to the monotonicity of sigmoid function, the order property still holds.
4

---

Under review as a conference paper at ICLR 2020
The predicted mean and variance given by our model without the last activation function shown below.
(5)
0² ,'(,.X:D.a,))=
B - + Sxx(A,))
(6)
where
mN - 35x
a Toeso"loggtt logil((), = a - 3.5
(7)
Here, B precisions of the prior, which hyperparameters of the Bayesian Optimization model. We can estimate them by maximizing the log marginal likelihood as following (Snoek et al, 2012).
M
N
3 log 3 |logit(t) 1m
logg(logit(t))a,
3) log a +
2
1 2
N
2 m
log |S
log 2n.
(8)
3.4 SEARCH WITH ALTERNATE LEARNING
NAS is process of online learning during which sampled from the search space. Therefore, the GCN model and BLR in BOGCN-NAS should be updated with the increasing number of samples for better generalization. In this work, for the reason that GCN retraining is more expensive than BLR updating, we update BLR more frequently than GCN predictor.
utilize new fully-trained architectures
The algorithm of our proposed BOGCN-NAS is illustrated in Algorithm I Given the search space A. initialize trained architecture sets containing architectures (A,, with their performance t [ffi..... fmii.. We train GCN predictor firstly with U and replace the last fully-connected layer with BLR described in Section 3.33 Then we randomly sample a subspace R following can- didate pool if AA is such huge that we cannot cover every architecture. After obtaining the candidate pool, we can calculate every candidate model's Expected Improvement as their estimated objective values E, = [fig..... fmyl }. Based on Ey and multi mujti-objecttiv formulation (Section 3.1, we can generate estimated Pareto Front and sample estimated Pareto optimal models set S and fully- train them to obtain the true objective values 1,- The trained architecture sets is then updated by U U S. Accumulating certain amount of new data, we update GCN and BLR alternately for next periodic sampling until satisfying the stop criteria.
3.5 EXPONENTIAL WEIGHTED Loss
For GCN predictor alone, MSE loss can achieve competitive performance for fitting all data, How- ever, when it comes to the surrogate function for finding the rop-performance model, we should pay more attention to architectures with high performance compared others.
In the search phase of BO, we select samples with top values of acquisition function. Specifically, we expect to predict architectures with high performance as accurately as possible, while distin- guishing low-performance architecture is sufficient for our purpose. For adapting NAS task, we propose Exponential Weighted Loss for the surrogate GCN model and replace common MSE loss with weighted loss completely in Algorithm I
N Σ
Leep = N(e -)
(cxp(0) 1)lly - 31,12
(9)
1) i=1
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1 BOGCN-NAS Search Procedure. A is the given search space, is the number of samples every iteration, is the ratio of GCN/BLR update times, Py is the optimal Pareto front and threshold is the criteria for search stopping.
Initialize trained architecture sets
U = {A,, X, & P from A and current Pareto front py;
function sample(GGNN ILR, embeddings = (A);
2: Train GCN and BLR initially;
13:
3: while PyslP//PPpl threshold do
16:
Predict mean and variance of models in
4:
for iteration= 1,2,.... do
R with BLR and embeddings by (Eq. 5 and (Fq-16);
5:
R =random sample(A)):
6:
S = =samppee(CC) (GCN, BLR, R);
17:
Calculate corresponding Expected Im- provement by 3);
Fully train sampled models S: Update U U U S;
8:
18: Sample top / Pareto optimal models
9:
Update Py in set U: B.Rdaee (GCN,
sorted by Expected Improvement into set
10:
S:
11: end for
19:
return
12:
GC. (CCN.etrrain(U)
20: end function
13:
end while
return Py
here y/ is the predicted accuracy, Di is the ground truth and e is normalization factor (e is the base the natural logarithm). Thus, our predictor will focus on predicting for those models with higher accuracy.
4 EXPERIMENT
Dataset and Search Space In this section, we validate the performance of the proposed BOGCN- NAS on NASBench (Ying et al. 2019). This is the largest benchmark NAS dataset for computer vision task currently, with 420K architectures. To show the generalization of our method, we collect 12K LSTM models trained on PTB dataset (MARCUS et al. 1993) aiming NL.P task. We also compare our method in open domains with NASNet search space (ooph al. 2018) and ResNet style search space (Li et al. 2019). We will provide the detail of the search space and collection method in Appendices Section.
Specifically, we prove the performance of single proposed GCN Predictor firstly and then vali- date the whole framework paggle-ojjcciivemutttoooooe search problems compared with other baselines (with default settings). The results of the experiment illustrate the efficiency of BOGCN- NAS.
4.1 COMPARISON INDIVIDUAL PREDICTORS
We use a four-layed GCN, with 64 hidden units in each layer, the surrogate model for BO. During training, we use the Adam optimizer (Kingma & Ba 2014), with learning rate of 0.001 and a mini- batch size of 128. The proposed GCN predictor compared with an MLP predictor and LSTM predictor (Liu et al. 2018a Wang et al. 2019b). Here we apply MSE loss because we compare the stand-alone predictors, while replace with Exponential Weighted Loss for subsequent NAS problems. For the evaluation metric, we follow (Wang et al. 2019b) and use the correlation between the predicted accuracy and true accuracy. One difference between et al. (001b) is that we compare predictor's performance training on fewer architectures rather than whole search space, because NAS start with little training data and cannot train such a large number of architectures in practice. We used 1000 architectures in NASBench for training, 100 architectures for validation, and 10000 architectures for testing.
evaluation method and (Wang
Table Table|[show shows the correlation result of various predictors and the number of predictors' parameters. The prediction result of three predictors is also illustrated in Figure] and the value means the

---

Under review as a conference paper at ICLR 2020
0.82
008
0.90
UM 046
0.7
0.75
0.33
0.83
5400
0.05
0.35
0.80
0:35
1.5
0.1
0.75
0.60
1.00
0.90
0.35
(a) GCN.
(b) MLP.
(c) LSTM.
Figure 2: Correlation of predicted accuracy versus ground truth for various predictors on NASBench. It can be found that our GCN predictor has better correlation performance than the competing pre- dictors.
Gaussian kemel-density estimation. As can be seen, the GCN predictor can predict the performance of architectures more accurately than the other two predictors, In addition, the GCN predictor has fewer parameters compared with them.
Table I: Performance of predictors training on small dataset. Our method has much better cor- relation with less predictor parameters.
Table Comparison of samples required to find the global optimal over 50 rounds.
NASBench
LSTM-12K
Correlation
No. of parameters
Random
188139.8
6182.6
MLP
0.400
6326K
Reg Evolution
87402.7
5670.9
LSTM
0.460
92K
MCTS
73977.2
4687.4
GCN
0.607
14K
LaNAS
11390.7
2464.4
BOGCN-NAS
1465.4
558.8
4.2 SINGLE-ORIECTIIG SEARCH
Single-objective (accuracy) search is a special case of BOGCN-NAS, we randomly sample architectures to fully train and use them the initial trained architecture sets, which is counted into the total sample numbers. Since the whole NASBench and LSTM datasets can inferred easily (less than 0.01s), we set R A in the experiment, which means take total search space as the candidate pool. During the search phase, we use GCN to obtain embeddings and use the Bayesian regressor to compute El scores for all architectures in the search domain, rank them based on the score and select the top ten models to fully train, obtain the accuracies and add them to trained architecture sets, update the best accuracy observed. The process is repeated for l 10 times. The GCN predictor is then retrained with updated trained architecture sets. This is repeated until the target model is found over 50 rounds. Note that GCN model trained using Exponential Weighted Loss instead in NAS procedure.
search. For the proposed
BOGCN-NAS is compared with the following state-of-the-art sample-based NAS baselines: (i) Ran- dom Search, which explores the search space without performing exploitation; (ii) Regularized Evolution (Real et al. 2019b), which uses heuristic evolution process for exploitation but is still constrained by the available human prior knowledge; (iii) Monte Carlo tree search (MCTS) (Wang al. (019b); and (iv) LaNAS (Wang et al.) 2019a). Both MCTS and LaNAS only estimate the performance of models
coarse subspace, and then select models randomly that subspace. In contrast, Bayesian optimization conducts more fine-grained search and predicts the expected improvement of candidate pool.
Figure 3 and Table 2 show the number of samples until finding the global optimal architecture using different methods. The proposed algorithm outperforms the other baselines consistently on the two different datasets. On NASBench, BOGCN-NAS is 128.4x, 59.6x, 50.5x, 7.8x more sample-efficient than Random Search, Regularized Evolution, MCTS and LaNAS respectively. On the smaller NI.P dataset, BOGCN-NAS still search and find the optimal architecture with fewer samples.
7

---

Under review as a conference paper at ICLR 2020
400000
12500
10000
300000
Samples
7500
200000
5000
100000
2500
Random
Keg Evolution
MCTS
LaNes
BOGGN
Random
Reg Evolution
MCTS
LaNAS
BOGGN
(a) NASBench dataset
(h) LSTMM dataset
Figure 3: Comparison of number of architecture samples truly evaluated to find the globally optimal architecture over 50 rounds. On NASBench, BOGCN-NAS is 128.4x, 59.6x, 50.5x, 7.8x more sample-efficient than Random Search, Regularized Evolution, MCTS and LaNAS.
We predict all architectures (420K; 12K) together on NASBench and LSTM dataset because the sampling methods as
cost of inference all once is negligible. For larger search space, mentioned in Section 3.4 instead. every iteration, we randomly sample a subset architectures R candidate pool from the search space for performance prediction and select top models among this pool. The performance of BOGCN versus the pool sampling ratio (
is shown in Table 3 As can be seen, the overall performance of our BOGCN can still find the optimal model with less samples compared with other baselines. Even though random sampling is good enough, an alternative sampling method can Evolutionary Algorithm.
Table 3: The performance with different pool sampling ratio.
Sampling ratio
NASBench dataset
LSTM dataset
1465.4
558.8
0.1
1564.6
1483.2
0.01
2078.8
1952.4
0.001
4004.4
2984.0
4.3 MULTI-OBJECTIVE SEARCH
In this section, we focus on multi-objective (accuracy and number parameters) search. As same settings of BOGCN-NAS with Section 4.2 the only difference is the criteria for updating the best urchitecture observed. Here we extend baselines in Section 4.2 to multi-objective form for comparison. In detail, sample 2, 000 architectures in total and compare the found Pareto front Py with the optimal Pareto front Py on NASBench dataset.
As shown in Figure the grey dots are the overall architectures of NASBench, the red dots sam- ples selected by BOGCN and the blue dots are architectures undominated by our selected samples. Based on them, we can make sure the respective Pareto fronts the green dashed line is the opti- mal Pareto front and the red dashed line is the estimated Pareto front. Figure 4b shows the Pareto fronts estimated by different algorithms, which demonstrates the superiority of BOGCN mothod.
Compared with other baselines, the models sampled by our method are gathered near the optimal Pareto front, and the found Pareto front is also closer to the optimal Pareto front. This validates the efficiency of algorithm this multi-objective search task.
4.4 OPEN DOMAIN SEARCH
In this section, we validate the propose method on the open domains NASNet search space and ResNet style search space (described in Appendices Section). Since the size of open domain is
8

---

Under review as a conference paper at ICLR 2020
0.94
0.94
0.92
0.92
0.90
Accuracy
Accuracy
0.88
0.90
0.86
0.88
0.84
True Pareto ected
BOGON
0.82
Domilaated Undom acted Archiaeturee
0.86
Random
Reg EVO
0.80
0.84
Latent Action
0.2
0.4
0.6
0.8
100
0.2
0.4
0.6
0.8
1.0
No. of Parameters
No. of Parameters
(a) BOGAN-NAS
(h) Comparison with other baselines
Figure 4: The result of multi-ohjective search with 2000 architecture samples. find more competitive Pareto optimal architectures.
BOGAN-NAS can
enormous, we set the size of R equals to 1M every iteration for both search spaces. And the found architectures by BOGCN-NAS can be found in Appendices Section.
4.4.1 NASNET SEARCH SPACE
For NASNet search space, we consider single-objective (accuracy) search on Cifar-10, 10. For effi- ciency, we train the sampled architectures by early stopping at 100 epochs rather than fully training. It's remarkable that we stop the algorithm after certain number of samples [S] rather than until finding the optimal architecture beacuse we don't know the optimal architecture and the open do- main contains billions of architectures. And other experiment settings the same with Section 4.2 as well.
We pick two best performing architectures VI and V2 within 200 and 400 samples respectively and fully train them. Table compares our results with other baselines on CIFAR-10. As can be seen, though one-shot NAS methods don't need any architecture evaluated directly, the performance of the final found models is not as good as sample-based methods averagely. Compared with other sample-based NAS method, BOGCN outperforms all methods except for AmoebaNet-B, which costs 07.5x more evaluating samples.
Table 4: Comparison of different methods on CIFAR-10.
Model
Params
Top-I err
No. of samples truly evaluated
NAcueu-A+cutout (Zoph et al. 2018)
3.3 M
2.65
20000
AmoebaNet-B+cutour (Real et al. (019b)
2.8 M
2.55
27000
PNASNet-5 (Liu et all 201 8a)
3.2 M
3.41
1160
NAO (Luo et al. 2018)
10.6 M
3.18
1000
ENAS+cutouu (Pham ci al.
20088)
4.6 M
2.89
+ LLu
2019b
3.3 M
2.76
BayesNAS+cuutout (Zhou et al. ASNG-NAS+cutout (Akımoto al. 2019)
2019)
3.4 M
2.81
3,9 M
2.83
BOGCN+cutout (V1)
3.08M
2.74
200
BOGCN+cutout (V2)
3.48M
2.61
400
4.4.2 RESNET STYLE SEARCH SPACE
For ResNet style search space, we validate the proposed method for multi-objective search on Ima- geNet (Deng et al. 2009). Here we consider classification accuracy and the number of parameters of the model at the same time. Due to the large volume of the dataset, train the sampled archi- tectures by early stopping at 40 epochs rather than fully training. And other experiment settings are well.
the same with Section 4.

---

Under review as a conference paper at ICLR 2020
BOGOX Bandom B0G22 Samples Samples
0.80
MI
0.76
0.78
(10 119-990...7661
NO
0.74
Accuracy
Accuracy
0.76
(13. 13..oMM.ccco d000)
Resnett 34
0.72
0.74
(25 233.560...-7000
Risreck S0a
0.70
0.72
0.68
0.70
0.66
10
15
20
25
30
35
40 50
10 15 20 25 30 40 45 50
No. of Parameters (M)
No. of Parameters (M)
(a) Comparison of BOGCN-NAS and Random Search.
(b) Comparison of the found models and ResNets.
Figure 5: Open domain multi-objective search on ResNet style search space with 500 samples.
Compared with Random Sampling, BOGCN-NAS achieves competitive Pareto front.
The accuracy and number of parameters of the sampled model are illustrated Figure Compared random sampling. BOGCN-NAS achieves more competitive Pareto front. We fully train every model on the estimated Pareto front and pick three models (M1, M2, M3), which can dominate ResNets. The comparison of our found models and famous ResNet family models are shown in Figure 5b It shows that ResNets can be dominated by our found models seriously.
4.5 SEARCH SPCAE EXTENSION TRANSFER
In this section, we discover the ability of our proposed algorithm on search speae extension transfer. Most NAS algorithms only focus static search space. In contrast, how to adapt the methods for extension of search space is still an open problem. For instance, after searching in one small search space A1, how to transfer the obtained knowledge to larger search space A2. For validation, split NASBench into two sub-datasets: architectures with nodes (62K) and architectures with nodes (359K).
Using the same settings with Section 4.2 we pretrained our GCN model on architectures with nodes and then transfer the GCN predictor searching on the architecture domain with 7 nodes. For comparison, we run the same algorithm without pretraining. The search method with pretrained GCN predictor finds optimal model after 1.9 samples while the method without pretraining needs 1386.4 samples. As can be seen, pretraining can reach the optimal model 2.7x more efficiently than unpretrained, validating the transfer ability of GCN predictor. Thus, BOGCN-NAS can handle different- scale architectures as long as their operation choices are the same.
5 CONCLUSION
In this work, we propose BOGCN-NAS, a multi-objective NAS method using Bayesian Optimiza- tion with Graph Convolutional Network predictor. We formulate the problem as a multi-objective optimization problem and utilize the efficiency of BO to search top-performance architectures. In- stead of using popular Gaussian Processes surrogate model, we replace with proposed GCN pre- dictor such that graph-based structure can be preserved better. For NAS-specific tasks, we also propose weighted loss focusing on top-performance models. Experimental results show that the proposed algorithm outperforms the SOTA LaNAS single-objective NAS and validate its effi- ciency on multi-objective NAS as well.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Y. Akimoto, S. Shirakawa, N. Yoshinari, K. Uchida, S. Saito, and K. Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In International Conference on Machine Learning. 2019.
B. Baker, O. Gupta, N. Naik, and Raskar. Designing neural network architectures using rein- forcement learning. In International Conference on Learning Representations, 2016. D
C. Bishop. Pattern recognition and machine learning. 2006.
H. Cai, T. Chen, W. Zhang. Yu, and J. Wang. Efficient architecture search by network transfor- mation. In Thirty-Seconel AAAI Conference on Artificial Intelligence, 2018. D
H. Cai, L. Zhu, and Han. Proxylessnas: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations, 2019.
L. Chen, M. Collins, Y. Zhu, G. Papandreou, B. Zoph, F. Schroff. Adam, and Shlens. Searching for efficient multi-scale architectures for dense image prediction. In Advances in Neural Informa- fion Processing Systems, pp. 8699-8710, 2018. D
Y. Chen, T. Yang, X. Zhang, G. Meng. C. Pan, and J. Sun. Detnas: Neural architecture search on object detection. Advances in neural information processing systems, 2019.
X. Chu, B. Zhang, H. Ma. R. Xu, J. Li, and Q. Li. Fast, accurate and lightweight super-resolution with neural architecture search. arXiv preprint arXiv:1901.0720 2019. [
J. Deng, W. Dong, R. Socher, L. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248- 255, 2009. 4.4.2
G. Ghiasi, T. Lin, and Q. Le. Nas-fpn: Learning scalable feature pyramid architecture for object detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7036-7045, 2019.
H. Jin, Q. Song, and X. Hu. Auto-keras: An efficient neural architecture search system. In Pro- ceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2019. 3.3
D. Jones. A taxonomy of global optimization methods based on response surfaces. Journal of global optimization, pp. 345-383 2001. 2.1
K. Kandasamy, W. Neiswanger, J. Schneider, B. Poczos, and E. Xing. Neural architecture search with bayesian optimisation and optimal transport. In Advances Neural Information Processing Systems, 2018. 3.3 D
D. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014. 4.1
Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016. 2.3
X. Li, Y. Zhou, Z. Pan, and J. Feng. Partial order pruning: for best speed/accuracy trade-off in neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9145-9155 2019. C.4
C. Liu, B. Zoph, M. Neumann, J. Shlens, W. Hua, L. Li, L. Fei-Fei, A. Yuille, Huang, and K. Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 19-34, 201 8a.
C. Liu. L. Chen, F. Schroff, H. Adam, W. Hua, A. Yuille, and L. Fei-Fei. Auto-deeplab: Hierar- chical neural architecture search for semantic image segmentation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 82-92, 2019a. D

---

Under review as a conference paper at ICLR 2020
H. Liu, K. Simonyan, O. Vinyals, C. Fermando, and K. Kavukcuoglu. Hierarchical representations for efficient architecture search. In International Conference on Learning Representations, 2018b. D
H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. In International Conference on Learning Representutions, 2019b.
R. Luo, F. Tian, T. Qin, E. Chen, and T. Liu. Neural architecture optimization. In Advances in neural information processing systems, pp.
2018.
M. Luong, D. Dohan, A. Yu, Q. Le, Zoph, and V. Vasudevan. Exploring neural architecture search for language tasks. In International Conference on Learning Representations, 2018. |
M. MARCUS, B. SANTORINI, and M. MARCINKIEWICZ. Building large annotated corpus of english: the penn treebank. Computational Linguistics-AAsooiation for Computational Linguistics, pp. 313-330, 1993.
C.2
R. Marler and J. Arora. Survey multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, pp. 369-395, 2004. 2.2
Mockus, V. Tiesis, and Zilinskas. The application of bayesian methods for seeking the ex- tremum. Towards global optimization, (117-129), 1978.
[ 2.1
H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning, pp. 4092-4101, 2018. T C.2
E. Real, S. Moore, A. Selle, S. Saxena, Y. Suematsu, J. Tan, Q. Le, and A. Kurakin. Large-scale evolution of image classifiers. In Proceedings of the 34th International Conference on Machine Kearning-Volumm 70, pp. 2902-2911, 2017. D
E. Real, A. Aggarwal, Y. Huang, and Q. Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 4780 4780, 2019a.
E. Real, A. Aggarwal, Y. Huang, and Q. Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4780-4789, 2019b.
Scarselli, M. Gori, A. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions Neural Networks, pp. 61-80, 2008. 3.2
C. Sciuto, K. Yu, M. Jaggi, C. Musat, and M. Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint 10XX:x19022.0144440 2019.
J. Snoek, H. Larochelle, and R. Adams. Practical bayesian optimization of machine learning algo- rithms. In Advances in neural information processing systems, pp. 2951-2959, 2012. 3.3
J. Snock. O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, M. Prabhat, and R. Adams. Scalable bayesian optimization using deep neural networks. In International confer-
on machine learning, pp. 2171-2180, 2015. 3.3
D. So, Q. Le, and C. Liang. The evolved transformer. International Conference on Machine Learning, pp. 5877-5886, 2019.
L. Wang, S. Xie, Li, R. Fonseca, and Y. Tian. Sample-efficient neural architecture search by learning action space. arXiv preprint arXiv: 1906.0683, 2019a.
B.1
L. Wang, Y. Zhao, Y. Jinnai, Y. Tian, and R. Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv:1903.11055 2019b. I
4.2 B.I B.2
S. Xie, H. Zheng, C. Liu, and L. Lin. Snas: stochastic neural architecture search. In International Conference Learning Representations, 2019. D
12

---

Under review as a conference paper at ICLR 2020
C. Ying, A. Klein, E. Christiansen, E. Real, K. Murphy, and F. Hutter. Nas-bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pp- 7105-7114, 2019.
I 3.2
B.2
C. Zhang, M. Ren, and R. Urtasun. Graph hypernetworks for neural architecture search. In Interna- tional Conference on Learning Representations, 2019.
H. Zhou, M. Yang, J. Wang, and W. Pan. Bayesnas: A bayesian approach for neural architecture search. In International Conference on Machine Learning. 2019. 4
B. Zoph and Q Le. Neural architecture search with reinforcement learning. In International Con- ference Learning Representations, 2017. D
B. Zoph, V. Vasudevan, Shlens, and Q. Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018.
13

---

Under review as a conference paper at ICLR 2020
Appendices
A ABLATION STUDY
A.1 THE ADVANTAGE OF GCN PREDICTOR AND BAYESIAN OPTIMIZATION
To verify that GCN is superior choice of predictor against others (e.g. MLP, RNN), we replaced GCN in the search algorithm with MLP predictor. And for demonstrating that Bayesian Optimiza- tion indeed improves the performance of our search algorithm, we also remove BLR and use point estimation only. In other words, we select candidate models based only on GCN's s predictive ac- curacies of architectures. Therefore, there are four different models correspondingly: (1) MLP; (2) BOMLP: (3) GCN; (4) BOGCN, where MLP, GCN use predictor only for model selection and BOMLP, BOGCN apply Bayesian Optimization on the strength of respective predictor.
With other settings same with with Section 4.2 we perform single-objective NAS algorithms over 50 rounds and the results of experiments on NASBench and LSTM datasets are shown in Figure As can seen, GCN is able discover the optimal architecture with fewer samples than MLP, which proves the superiority of GCN predictor and our algorithm is more efficient with Bayesian Optimization.
15000
2000
12500
No. Samples
No. of Samples
1500
10000
1000
2500
8
500
0
MLP
BOMLP
GON
BOGCN
MLP
BOMLP
GCN
BOGCN
(a) NASBench
(b) LSTM-128 -2K
Figure 6: Ablation study of Bayesian Optimization and Graph Convolutional Network Predictor. The comparison shows that the efficiency of the search can be boosted by adding Bayesian opti- mization and Graph Convolutional Network modules respectively.
A.2 THE IMPROVEMENT OF EXPONENTIAL WEIGHTED Loss
To prove the improvement of our proposed weighted loss empirically, we compare it with MSE loss. We also design other two weighted losses as following to show the influence of the second-order derivative of added weight. We apply the same settings with Section 4.2 for algorithm performing and the experiment result of single-objective (accuracy) on NASBench is shown Figure 7 As be seen, exponential weighted loss outperforms other three losses, which is consistent with intuition.
N
Loog
log(ū. + 1)11gs - x11
(10)
N log 2
Lisnear
Te llyi 12.
(11)
14

---

Under review as a conference paper at ICLR 2020
100
1824.7
1772.16
1648.52
2465.4
Relative Weight
0.8
4000
No of Sairpeee
0.6
3000
04
2000
loss
02
Log weighted loss weighted loss
1000
weighted
0.0
MSE Loss
Log Weighted
Liner Weighted
Exg
True Accuracy
Weighted
(a) The illustration of four losses considered in this (b) The performance of four losses over 50 rounds. It paper.
can be found that our method can reach the highest efficiency with exponential weighted loss.
Figure 7: Ablation study of Weighted Loss.
B SUPPLEMENTAL EXPERIMENTS
B. TIME COURSE PERFORMANCE COMPARISON
Following Wang et al. 2019h a). besides comparing the number of training architectures sampled until finding the global optimal architecture, we also evaluate the current best models during the searching process As shown in Figure 8 our proposed BOGCN-NAS outperform other search algorithms except for the very beginning on LSTM model searching.
Random Select
0.942
100.0
MCTS
Evo
BOGCN
0.840
98.5
0.559
90.0
0.936
Random Select
97.0
BOGON
96.5
300
500
700
900
1100
1300
1500
1700
1900
100
300
500
700
1900 500
1100
1300
1500
1700
(a) NASBench
(b) LSTM-12K
Figure 8: Current best accuracy during searching. The result demonstrates that our proposed BOGCN-NAS outperforms other search algorithms significantly.
B.2 PREDICTOR TRAINING ON WHOLE SEARCH SPACE
For comparison with previous work (Wang al. 2019b), also train GCN predictor whole NASBench dataset (420 models) (Ying et al. 2019). We use 85% NASBench for training, 10% for validation and remaining 5% for testing. As shown in Figure (the value also the density of architectures around), GCN outperforms others consistently with experiment training fewer data (Section 4.1). Even though the correlations of the GCN and MLP are comparable here. the performance is less important than cases training on fewer data.
15

---

Under review as a conference paper at ICLR 2020
0--
600
000
0.5 Ground Truth
ACC
Grouse Truth-cC
(a) GCN (corr=0.841)
(b) MLP (com==08300)
(c) LSTM (comr=0.743).
Figure 9: Correlation of predicted accuaracy versus ground truth for various predictors on whole dataset. shows that GCN predictor can predict more accurately than other two predictors on whole NASBench.
C DATASET AND SEARCH SPACE
C.I NASBENCH ENCODING
Global Nodw8
Input: O; Conv1 X1: 1; X3nv3xX3: 2; MaxPooling: 3; Output: 4; Global: 5
Operations corresponding
Nade7
Posling Nede
Corv Node
0
0
0
0
1
0
0
1X1
3X3
3X3
Node
Input Node
One-HHot Encoded
Adjacency Matrix (8
Feature Matrix [8X
Figure 10: The encoding scheme of an example cell in NASBench.
C.2 LSTM- DATASET
To create LSTM model dataset, follow the same setting proposed by ENAS (hham al. 2018), we use adjacency matrix and a list of operators to represent an LSTM cell, and randomly sampled 12K cell structures from that domain, because the cells have natural graph structures, it is easy to feed them directly into GCN and conduct training. Due to the limitation on computational resources, only sample architectures with number of nodes less than equal to 8, and trained each cell for 10 epochs on PTB dataset (MARCUS et al. 1993). We use perplexity as performance measure for the cells.
C.3 NASNET SEARCH SPACE
We follow the search space setting of DARTS (Liu et al. 2019b), in which the architecture is stacked by the learned cell. The cell consists of 4 blocks, two inputs (the output of previous cell and the previous previous cell) and one output. There are 8 types operations allowed: 3 x 3 and separable convolutions, average pooling, identity, and zero. Similar previous work (Liu et al. 2018a). apply the same
and x 5 dilated separable convolutions,
3 max pooling, 3 x
16

---

Under review as a conference paper at ICLR 2020
cell architecture for both "normal" and "reduction" layer. For adapting to proposed GCN predictor, we regard the operation as the node and regard the data flow as the edge. The encoding illustrated in Appendices
e examples
C.4 RESNET STYLE SEARCH SPACE
We follow the setting of Li et al. (211 to prepare the ResNet style search space. This search space aims to find when to perform down- wwwn--anling and when to double the channels. The ResNet style backbone consists of 5 stages with different resolutions from input images. The spatial size of Stage 1 to 5 is gradually down-sampled by the factor of 2. suggested in [L et al. (2019), we fixed one 3 x 3 convolution layer (stride = 2) in Stage-1 and the beginning of Stage-2. We use the block setting as bottleneck residual block in ResNet. Then, the backbone architecture encoding string looks like "1211 211 1111 12111", where "_" separates each stage with different resolution, "1" means regular block with no change of channels and "2" indicated the number of base channels is doubled in this block. The base channel size is 64. In Section 4.4, we just take "-, 1, 2" as three different operations and encode architectures as a series of strings. We train the model generated from this search space for 40 epochs with fast convergence learning rate schedule. Each architecture can be evaluated in 4 hours on one server with 8 V100 GPU machines.
D NAS RELATED WORK
NAS aims at automatically finding a neural network architecture for certain task such as CV and NPL (Chen et al. 2018; Liu al., 2019aa] Chen al., (219)) and different datasets without human's labor of designing networks. Particularly, in real applications, the objective of NAS is more preferred be obtaining decent accuracy under limited computational budget. Thus a multi-objective
NAS is more practical setting than only focusing on accuracy. There are several approaches in
NAS area: I) Reinforcement learning-based algorithm. Baker et al. (2016): Zoph Le (207)); Cai et al. (2018) train an RNN policy controller to generate sequence of actions to design cell structure for a specify CNN architecture; 2) Evolution- based algorithm. Real et al. (2017): ): Liu et al. (2018b);
Real al. (2019a) try to evolve architectures Network Morphism by mutating the current best architectures and explore new potential models; 3) Gradient- algorithm Liu et al. (2019b); Cai al. (2019); Xie al. (2019) define architecture parameter for continuous relaxation of the discrete search space, thus allowing differentiable optimization of the architecture. 4) Bayesian Optimization-based algorithm. (Kandasamy et al. 2018 and (Jin et al. 2019) define the heuristic distances between architectures and apply BO with Gaussian Processes. Among those algorithms, most existing methods focus on single objective (accuracy), others adding computation constraints as regularization loss in the gradient-bart based method or as a reward in the RL-based algorithm. In contrast, our method reformulates the multi-objective NAS as a non-dominate sorting problem and further enables an efficient search over flexible customized search space.
E BEST FOUND MODELS
E.1 NASNET SEARCH SPACE
Figure Ia and I1c show the found architectures from the open domain search on NASNet search space by method.
E.2 RESNET STYLE SEARCH SPACE
Figure 12 13 and 14 show the found architectures from the open domain search on ResNet style search space by our method.
17

---

Under review as a conference paper at ICLR 2020
sep. Poir 36.3
Ponneet
c (l-2)
skop cocnect
cone 313
skip ConFecT
c_.k)
sep.
c (K-1)
come 303
max gool
(a) VI (normal and reduction cell)
(b) VI cell encoding
3x3
< -
malk poopppoo_or
upp 355
14]
<p. max pool 33
(_(222
Bikk
(c) V2 (normal cell and reduction cell)
(d) V2 cell encoding
Figure The found models in NASNet search space.
5tage2
Stage2
Staged
Stages
Stages
Image
CN-R
Rlock
Block
Bookk
Black
Block
Block
Block
Block
Blook
Block
Block
Block
Block
Blook
Block
Figure 12: MI ("1
1122")
Stage1
Stage?
Stage3
Stago4
Stages
Image
C-M-R
Block
Black
Block
Block
Block
Black
Block
Block
Block
Block
Black
Arch code
64
Figure 13: M2 (11 11 112 111111122111 1")
Book
602
Arch-odd
Figure M3 ("1 2111121111 211111")
18


Reviews:
[{"review_id": "SylLqFmiYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provide a NAS algorithm using Bayesian Optimization with Graph Convolutional Network predictor. The method apply GCN as a surrogate model to adaptively discover and incorporate nodes structure to approximate the performance of the architecture. The method further considers an efficient multi-objective search which can be flexibly injected into any sample-based NAS pipelines to efficiently find the best speed/accuracy trade-off.\n\nThe paper is well-written. The experiments are abundant. However, the paper has following drawbacks that need to be further concerned:\n\n1.\tIn my opinion, the key point of the paper has nothing to do with GCN or multi-objective. The important part is to use BO and EI to sample new architecture. However, no theoretical proof is provided to guarantee that the performance is getting better during while loop in Algorithm 1.\n2.\tEq.(9) focuses more on models with higher accuracy. However, those models with bad performance will be predicted inaccurately and may have a higher score than good models. For model with ground-truth near 0, arbitrary predicted score results in the same loss. Eq.(9) seems cannot prevent this situation from happening.\n3.\tTable 1 compare different architectures with GCN. However, the LSTM is the worst architecture used among the 3 different architectures in the original paper (Alpha-X), which makes the comparison unfair.\n4.\tTable 2 shows the number of architectures trained. However, the proposed method need to update GCN multiple times during searching, which makes the comparison unfair.\n5.\tTable 2 shows the number of training models before finding the best model. It is meaningless when used in reality, which often contains more than 10^10 different architectures and the best architecture is unknown. In my opinion, the performance of the top1 architecture predicted by the proposed method is much important.\n6.\tAlgorithm 1 uses Pareto front, which does not exist when doing experiments on single-objective search. More details should be clarified.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1eGfMLzcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "--Summary--\nThe authors present an algorithm BOGCN-NAS which combines bayesian optimization and GCNs for searching over NN architectures. The authors emphasize that this method can be used for multi-objective optimization and run experiments over NAS-Bench, LSTM-12K and ResNet models. \n\n--Method--\n\nMethodologically, the contribution is somewhat weak. The main technical contribution is to use a GCN to get a global representation of a graph, which can then be used for downstream regression tasks such as predicting accuracy. It’s not clear how much the GCN generalizes in being able to encode arbitrarily large architectures. The two main examples offered are NAS-Bench and LSTM-12K focus on optimizing cell architectures which contain a handful of nodes e.g. (5 in the case of NAS-101).\n\nGraph embeddings:\nThe authors have not considered other graph embeddings to use in their Bayesian regression setup. E.g. see https://arxiv.org/pdf/1903.11835.pdf for a list.\n\nBayes-opt:\nIn Algo1, step 5. The authors randomly sample a number of architectures in order to calculate EI scores on them. For large discrete combinatorial search spaces, this approach will not scale.\n\nMulti-objective optimization:\nIt’s not clear why GCNs or BO is required for this. Any predictor that generates multiple metrics could substitute in order to create a pareto-curve. Even multi-objective RL based approaches could suffice. Thus multi-objective opt only seems like a minor/tangential contribution.\n\n--Experiments--\nThe main claim of the paper is that this approach works well  for the multi-objective case. However, the results only look at two objectives #params vs accuracy. There’s a pretty strong correlation between the two. It’s unclear how the method generalizes when objectives are not correlated. The authors need to thoroughly demonstrate other objectives/find suitable benchmarks for the same as clearly NAS-101 will not suffice.\n\nOther concerns:\n - Table 1 has correlations using 1000 training architectures. Why 1000? Why not 50 (that’s how sec 4.2 is initialized). Also, the correlation results are less impressive in Figure 9.\n - Table 1 lists the number of params that the predictor uses. Why is this important? How about comparing with a linear regressor?\n - The results in Sec 4.3 are using random as the only baseline. This is a pretty weak baseline.\n - In sec 4.4, the authors pick models M1, M2 and M3 as candidate examples.. How were these chosen ?\n - Sec 4.5 transfer learning results are pretty weak. Transfer across datasets is much more interesting e.g. between ImageNet and Cifar-10.\n\nOverall, this paper has some interesting results, which show that GCNs can be useful models to encode graph structured inputs. However, the methodological and experimental results can definitely be strengthened. The authors may consider the following:\nAddress how GCNs can model and scale to general architecture spaces than a small number of nodes in a cell.\nAddress how to sample better over combinatorial search spaces than random in the inner loop of BO.\nStrengthen MO-opt results. Use better baselines than random and different objectives than accuracy vs #params.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklMcrr0YB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed BOGCN-NAS that encodes current architecture with Graph convolutional network (GCN) and uses the feature extracted from GCN as the input to perform a Bayesian regression (predicting bias and variance, See Eqn. 5-6). They use Bayesian Optimization to pick the most promising next model with Expected Improvement, train it and take its resulting accuracy/latency as an additional training sample, and repeat. \n\nThey tested the framework on both single-objective and multi-objective tasks.  On the single-objective (accuracy task). They tested it on NasBench and LSTM-12K, two NAS datasets with pre-trained models and their performance. They obtained very good performance on both, beating LaNAS (previous SoTA) by 7.8x higher sample efficiency. On multiple-objective, they show higher efficiency in finding Pareto frontier models, compared to random search. \n\nOne main question I have is whether the next model is chosen given the current prediction model? For NasBench, did you run your predictor for all (420k minus explored) models and pick the one that maximizes Expected Improvement? Note that LaNAS is more efficient in that manner by sampling directly on polytopes formed by linear constraints. If so, how do you pick the next candidate models in open domain setting?\n\nIt looks like Eqn. 9 biases the training heavily towards high accuracy region, which is a hack. Although in the Appendix (Fig. 7) the authors have already perform some analysis on the effect of different weight terms, I wonder whether there is a more problem-independent way of doing it. The MCTS in LaNAS is one way that automatically focuses the search on the important regions. Currently, the proposed approach might limit the usability of the proposed method to other situations when accuracy is no longer that important. \n\nThe performance is really impressive in the NasBench and LSTM dataset. The paper mentioned that “BO can really predict the precious model to explore next” but didn’t provide an examples in the paper. I would whether the author could visualize it in the next revision, which would be very cool. \n\nDo you have open domain search research in single-objective search? \n\nWhy not use NasNet architecture for a fair comparison with other NAS papers?\n\nIn Appendix, Fig. 6 shows that even without GCN and BO, a single MLP already achieves global optimal solution in LSTM-12K dataset with ~850 samples, already beating all the previous methods (Random, Reg Evolution, MCTS and LaNAS). If that’s the case, I wonder how much roles the proposed methods (BO + GCN) play during search? Also what do you mean by “without BO”? Do you only predict the mean and assume all variance is constant? \n\n=====Post Rebuttal======\nI have read other reviewers' comments and the rebuttal. \n\nOne of the main problems in this paper is an unfair comparison against LaNAS. LaNAS only uses a single sample at each leaf, while they sample 100% to 0.1% of the models, evaluate them with the current BO model and find the best. For NasBench-101 with 420K models, even sampling 0.1% each time means ~400 samples and the performance (from the rebuttal) seems to degrade substantially from 100% case (1464.4->4004.4). This means that almost 3x more samples are needed, compared to what they claimed. \n\nI agree with the authors that calling BO function is super fast so maybe this is fine. However, on the open domain experiments, their performance is also not better than LaNAS+c/o, which they didn't list in the rebuttal. I listed it here:\n\nModel                      \tParams       \tTop-1 err\tNo. of samples truly evaluated\n-----------------------------------------------------------------------------------------------------------------\nBOGCN+cutout (V1)\t   3.1M \t          2.74\t                      200\nBOGCN+cutout (V2)\t   3.5M \t          2.61\t                      400\nLaNAS+c/o                       3.2M              2.53±0.05                    803\n\nOverall this paper is on the borderline. I don't mind if the paper gets rejected. For now I lower the score to 3. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use Graph Convolutional Networks (GCNs) in Bayesian optimization for neural architecture search. While the paper title includes multi-objective, this component appears to only be a posthoc evaluation of the Pareto front of networks evaluated using a single-objective search -- this could be performed for any method that evaluates more than one network. Performance on NAS-Bench-101 appears to be very good. 

In the private discussion of reviewers and AC, several issues were raised, including whether the approach is compared fairly to LaNAS and whether the GCN will predict well for large search spaces. Also, unfortunately, no code is provided, making it unclear whether the work is reproducible. The reviewers unanimously agreed on a weak rejection score.

I concur with this assessment and therefore recommend rejection.

Decision: Reject