BANANAS: Bayesian Optimization with Neural Networks for Neural Architecture Search
Authors: Colin White
Willie Neiswanger
Yash Savani
Venue:  (2020)
Keywords: neural architecture search
Bayesian optimization

Abstract: Neural Architecture Search (NAS) has seen an explosion of research in the past few years. A variety of methods have been proposed to perform NAS, including reinforcement learning, Bayesian optimization with a Gaussian process model, evolutionary search, and gradient descent. In this work, we design a NAS algorithm that performs Bayesian optimization using a neural network model.

We develop a path-based encoding scheme to featurize the neural architectures that are used to train the neural network model. This strategy is particularly effective for encoding architectures in cell-based search spaces. After training on just 200 random neural architectures, we are able to predict the validation accuracy of a new architecture to within one percent of its true accuracy on average. This may be of independent interest beyond Bayesian neural architecture search.

We test our algorithm on the NASBench dataset (Ying et al. 2019), and show that our algorithm significantly outperforms other NAS methods including evolutionary search, reinforcement learning, and AlphaX (Wang et al. 2019). Our algorithm is over 100x more efficient than random search, and 3.8x more efficient than the next-best algorithm. We also test our algorithm on the search space used in DARTS (Liu et al. 2018), and show that our algorithm is competitive with state-of-the-art NAS algorithms on this search space.

Under review as a conference paper at ICLR 2020
BANANAS: BAYESIAN OPTIMIZATION WITH NEURAL NETWORKS FOR NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Neural Architecture Search (NAS) has seen an explosion of research in the past few years. A variety of methods have been proposed to perform NAS, including reinforcement learning. Bayesian optimization with Gaussian process model, evolutionary search, and gradient descent. In this work, we design NAS algorithm that performs Bayesian optimization using a neural network model.
We develop a path-based encoding scheme to featurize the neural architectures that are used to train the neural network model. This strategy is particularly effective for encoding architectures in cell-based search spaces. After training on just 200 random neural architectures, we are able to predict the validation accuracy new architecture to within one percent of its true accuracy average, for popular search spaces. This may be independent interest beyond Bayesian neural architecture search.
We our algorithm on the NASBench (Ying et al. 2019) and DARTS (Liu al. 2018) search spaces, and we show that our algorithm outperforms other NAS methods including evolutionary search, reinforcement learning, AlphaX (Wang al. 2019), ASHA, DARTS, and TPE. Our algorithm is over 100x more efficient than random search, and 3.8x more efficient than the next-best algorithm on the NASBench dataset. As there have been problems with fair and reproducible experimental evauations in the field of NAS, we adhere to the recent NAS research checklist (Lindauer and Hutter 2019) to facilitate NAS research. In particular, our implementation has been made publicly available, including all details needed to fully reproduce our results.
INTRODUCTION
Since the deep learning revolution in 2012, neural networks have been growing increasingly more specialized and more complex (Krizhevsky et al.) 2012 Huang et al. 2017 Szegedy et al., 2017). Developing new state-of-the-art architectures often takes vast amount of engineering and domain knowledge. A new area of research, neural architecture search (NAS), seeks to automate this process. Since the popular NASNet paper (Zoph & Le (0117), there has been a flurry of research on neural architecture search (Liu et al.
2018a| Pham et al. 2018: Liu al. 2018b Kandasamy al. 2018
Elsken et al. 2018 Jin et al., 2018) Sciuto et al., 2019 Cortes et al. [211]] Baker et al. 2016 Liu
et al. 2017). Many methods have been proposed for NAS, including random search, evolutionary
search, reinforcement learning, Bayesian optimization, and gradient descent. Each technique has its advantages and disadvantages. For example, reinforcement learning with controller neural network can learn very complex policies. However, as some past work has argued, NAS is an optimization problem find the architecture with the lowest validation error so there is no explicit need to maintain state and transition function, and this approach may require evaluating larger number of architectues to achieve the same result as other methods (Kandasamy et al. 2018 Elsken et al.. 2018,Jiang et al. 2017). Alternatively, Bayesian optimization with a Gaussian process model is leading method for zeroth order optimization of expensive-to-evaluatt functions, which is precisely the setting of deep learning model selection. Although Bayesian optimization has seen great success in hyperparameter optimization (Golovin et al. 2017: Li et al. 2016) for deep models, host of difficulties arise when using Bayesian optimization for neural architecture search. For example, while there is a substantial body work on Bayesian optimization over Euclidean spaces, using Bayesian optimization for NAS has far required specifying distance function between neural

---

Under review as a conference paper at ICLR 2020
Ippul Architacturas
Fath Encodiigg
BANANAS Neural Network
Accurncy Protictions and Uncertaintt Estimetes
Figure 1: Illustration of the meta neural network in the BANANAS algorithm.
architectures, in order to define surrogate model. This is often a cumbersome task involving tuning hyperparameters of the distance function (Kandasamy et al. 2018 Jin et al. 2018). Furthermore, Bayesian optimization most commonly uses a Gaussian process (GP) model, and it can be quite challenging to achieve highly accurate prediction performance with GPs, given the potentially high dimensional input architectures (Elsken al. 2018).
In this work, we run Bayesian optimization with a neural network model. That is, in every iteration of Bayesian optimization, we train a meta neural network predict the accuracy of unseen neural architectures in the search space. This procedure avoids the aforementioned problems with Bayesian optimization NAS: the model is powerful enough to predict neural network accuracies, and there is no need to construct distance function between neural networks by hand. Furthermore..sinng neural network model scales far better than GP model, avoids the computatiionallyinteesii matrix inversion operation.
Training a meta neural network to predict the accuracy neural architectures is challenging task. The majority of popular NAS algorithms are deployed over a directed acyclic graph (DAG) search space the set of possible architectures is comprised the set of all DAGs of a certain size, together with all possible combinations of operations on each node (Zoph & Le. 2017 Pham et al. 2018
Liu et al.) [201b;; Ying et al.) 2019). This poses roadblock when using meta neural network to predict the accuracies of neural architectures, since graph structures are difficult for neural networks to understand directly from the adjacency matrix (Zhou et al.) 2018).
use a path-based encoding scheme to encode neural architecture, which drastically improves the predictive accuracy of our meta neural network. Each binary feature represents a unique path through the DAG from the input layer to the output layer. This method improves the accuracy of meta neural network by factor of 3. With just 200 training points, our meta neural network is able to predict the accuracy unseen neural networks to within one percent on average on the popular NASBench dataset (Ying al.) 2019). This may be of interest beyond Bayesian neural architecture search.
In our Bayesian optimization NAS algorithm, we train an ensemble of neural networks to predict the mean and variance of candidate neural architectures, from which we compute the upper confidence bound (UCB) acquisition function (Srinivas et al. 2009). Finally, we use a mutation algorithm to optimize the acquisition function. We compare our NAS algorithm against a host of block-box optimization NAS algorithms including regularized evolution, reinforcement learning, Bayesian optimization with GP model, AlphaX (Wang et al. 2018). ASHA (Li & Talwalkar 2019), DARTS (Liu et al.) 2018b), and TPE (Bergstra et al. 2011 I). On the NASBench dataset, our method sees significant improvements compared to all other algorithms we tried across 200 trials. It takes the next-best algorithm 3.8 times the number of queries to achieve the same mean test accuracy as our method, and it takes random search more than 100 times the number of queries. On the search space from DARTS, when given budget of 100 neural architecture queries for 50 epochs each, our algorithm achieves best of 2.57% and average of 2. 2.64% test error, which beats all NAS algorithms
2

---

Under review as a conference paper at ICLR 2020
with which we could fairly compare (e.g., same search space used, and same hyperparameters for the final training).
Our NAS algorithm has several moving parts, including the meta neural network. the path- feature encoding of neural architectures, the acquisition function, and the acquisition optimization strategy. We thorough ablation study by removing each piece of the algorithm separately. We show all components are necessary to achieve the best performance. Finally, to adhere to recent calls for reproducible NAS research (Ying al.) 2019 Li & Talwalkar| 2019; Lindauer & Hutter 2019), we address all points in the NAS research checklist (Lindauer & Hutter 2019) and will make our anonymized code is available at https:: www. www.bgitthb.............. www.cccrre///aaaaaa.......
Our contributions. We summarize our main contributions below.
We propose novel path-based encoding scheme for neural architectures. This is method for featurizing neural architectures by enumerating paths along the DAG from the input node to the output node. When predicting the validation accuracy of neural networks, using this featurization drastically improves the performance compared to standard encodings such as the adjacency matrix encoding, making it feasible to use a meta neural network as a model in Bayesian optimization.
We design Bayesian optimization algorithm using meta neural network model to perform NAS over cell- based search spaces. We use an ensemble of neural networks to output a mean and variance for each candidate architecture and then use the UCB acquisition function to guide the search. We perform an extensive study of our algorithm and show it performs on par superior to several state-of-the-art NAS algorithms on two different search spaces.
2 RELATED WORK
Neural architecture search have been studied since at least the 1990s (Floreano et al. 2008 Kitano
1990;
Stanley & Miikkulainen 2002), but the field was revitalized when NASNet gained significant
attention (Zoph & Le 2017). There has been a flurry of recent work, where the most popular
techniques include evolutionary algorithms (Shah al., (008)) reinforcement learning (Zoph & Le
2017 Pham et al. 2018 Liu et al. 2018a Tan & Le 2019), Bayesian optimization (Kandasamy et al.
2018 Jin et al.) 2018 Zhou et al. 2019), and gradient descent (Liu et al. (0018b). Recent papers have
called for fair and reproducible experiments in the future (Li & Talwalkar [2019] Sciuto et al.) 2019
Ying et al. 2019). In this vein, the NASBench dataset was created, which contains over 400k neural architectures with precomputed training, validation, and test accuracy (Ying et al. 2019). A recent algorithm, AlphaX, uses a meta neural network to perform NAS (Wang et al. [2018), where the meta neural network is trained to make small changes to the current architecture, given adjacency matrix fcaturizations of neural architectures. See the recent survey on NAS (Elsken et al. al. (2018) for more information on NAS research. There are many additional recent NAS papers (Maziarz al. 2018
Borsos et al.
2019 Wang et al. 2019).
Bayesian optimization is leading technique for zeroth order optimization when function queries
are expensive (Rasmussen) 2003 Frazier 2018). and it has seen great success in hyperparameter
optimization for deep learning (Rasmussen) 2003 Golovin al., 2017 Li al. 2016). Most work
has focused on Euclidean or categorical input domains using a GP model [Rasmussen 2003 Golovin
al.
2017: Frazier 2018 Snoek et al., 2012). There has also been some previous work on using
neural network models in Bayesian optimization (Snock et al. 2015 Springenberg et al. 2016
Perrone al. 2017), applied to the task of hyperparameter optimization.
There are several approaches for predicting the validation accuracy of neural networks using a layer-wise encoding of the neural architectures (Deng et al., 2017 Istrate et al. 2019). or predicting the learning curve of different neural architectures (Klein et al. 20177; Domban et al. 2015 Baker
ct al.
2017). Ensembles of neural networks a popular approach for uncertainty estimates (Beluch)
et al.
2018 Lakshminarayanan et al. 2017: Choi et al. 2016). For more discussion on related work,
see Appendix A
3 PRELIMINARIES
We give background three key ingredients of NAS algorithms, well as Bayesian optimization.
3

---

Under review as a conference paper at ICLR 2020
Search space. Before deploying NAS algorithm, we must define the space of neural networks that the algorithm can search through. Perhaps the most common type of search space for NAS is a
cell-based search space (Zoph & Le 2017 Pham et al.] 2018 Liu et al. 2018b Li & Talwalkrr 2019
Sciuto et al. 2019 Ying et al. 2019). p. A cell consists of a relatively small section of a neural network, usually 6- 12 nodes forming directed acyelic graph (DAG). A neural architecture is then built by repeatedly stacking one or two different cells on top of each other sequentially, possibly separated by specialized layers. The layout of cells and specialized layers called a hyper-archieectuee and this is fixed, while the NAS algorithm searches for the best cells. The search space over cells consists of all possible DAGs of a certain size, where each node can be one of several operations such as X 1 convolution, 3 x 3 convolution, or 3 x 3 max pooling. It is also common to set a restriction on the number of total edges or the in-degree of each node (Ying et al. 2019 Liu et al. 2018b). In this work, we focus on NAS over convolutional cell-based search spaces.
Search strategy. The search strategy is the optimization method that the algorithm uses to find the optimal or near-optimal neural architecture from the search space. There are many varied search strategies, such as Bayesian optimization, evolutionary search, reinforcement learning, and gradient descent. Section 4 we introduce a novel search strategy based on Bayesian optimization with a neural network model using a path-based encoding.
Evaluation method. Many types of NAS algorithms consist of an iterative framework in which the algorithm chooses a neural network to train, computes its validation error, and uses this result to guide the choice of neural network in the next iteration. The simplest instantiation of this approach to train each neural network in fixed way, i.e., the algorithm has black-box access to a function that trains neural network for epochs and then returns the validation error (Pham et al., 2018 Liu al., [2018a] [Shah et al., 2018). Algorithms with black-box evaluation methods can be compared by returning the architecture with the lowest validation error after certain number of queries to the black-box function. There are also multi-fidelity methods, for example, when a NAS algorithm chooses the number of training epochs in addition to the architecture. In this work, show our algorithm far outperforms several other NAS algorithms that use black box optimization, and we discuss multi-fidelity approaches in Section 6
Bayesian optimization. In applications of Bayesian optimization for deep learning, the typical goal is to find a neural architecture and/or set of hyperparameters that lead to an optimal validation error. Formally, Bayesian optimization seeks to compute a' arg min A fa), where A is the search space, and (a) denotes the validation error of architecture a after training on a fixed dataset for a fixed number of epochs. In the standard Bayesian optimization setting, over a sequence of iterations, the results from all previous iterations are used to model the topology of f(A) using the posterior distribution of the model (often a Gaussian process). The next architecture is then chosen by optimizing an acquisition function such as expected improvement (EI) (Močkus) 1975) or upper confidence bound (UCB) (Srinivas et al., 2009). These functions balance exploration with exploitation during the iterative search. We discuss UCB in the next section, and we discuss other acquisition functions in Appendix
4 METHODOLOGY
In this section, we discuss all of the components of our NAS algorithm. Our Bayesian optimization method uses meta neural network to predict the validation error of neural architectures from the search space. First we describe the featurization of neural architectures used in our algorithm. Then we describle how predict mean and uncertainty estimates using an ensemble of meta neural networks. Finally, we describe the acquisition function and acquisition optimization strategy we use, and show how these pieces come together form our final NAS algorithm.
Architecture featurization via path- path- encoding. Prior work aiming to encode or featurize neural networks have proposed using an adjacency matrix-based approach (Wang et al. 2018 Ying et al. 2019 Deng al. 2017 Baker et al. 2017).
The adjacency matrix encoding gives an arbitrary ordering to the nodes, and then gives a binary feature for edge between node i and node j, for all j. Then list of the operations each node
4

---

Under review as a conference paper at ICLR 2020
cut
CaT Back
Gitt Sin
Mack
Figure 2: Hyper-architecture of a NASBench neural network (left). Example of a path encoding of cell (right).
must also be included in the encoding. This is a challenging data structure for NAS algorithm to interpret, because it relies on an arbitrary indexing of the nodes, and each feature is highly dependent on one another. For example, an edge from the input node is useless there is no path from node 2 to the output. Also, even if there is an edge from node 2 to the output, it matters lot whether node is a CONV or a POOL operation. Ying et tested another encoding that is very similar to the adjacency matrix encoding, but the features of each edge are continuous.
We introduce a path-based encoding and show that substantially increases the performance of our deep predictive uncertainty model. Each feature of the path encoding corresponds with directed path from the input to the output of an architecture cell (for example: input>>CONV IXI-CONV 3x3->MP-routput
To encode an architecture, we simply check which of the possible paths it contains (i.c. which paths are present the cell), and write this as a binary vector. Therefore, we do not need to arrange the nodes in any particular order. Furthermore, the features are not nearly as dependent on one another as they are in the adjacency matrix encoding.
The total number of paths is E q' where denotes the number of nodes in the cell, and g denotes the number of operations for each node. For example, the search space from NASBench (Ying et al.) 2019) has Σ 3 = 364 possible paths, and the search space from DARTS (Liu et al. 2018b) has 4 > === 8 18724 possible paths. See Figure 2 (right). Our featurization performs very well on the most popular search spaces, however it may not scale to large search spaces. We discuss this further in Section
Acquisition function and optimization. Many acquisition functions used in Bayesian optimization can be approximately computed using a mean and uncertainty estimate for each input datapoint. We train ensemble of five meta neural networks in order predict new neural architectures. Concretely, we predict the validation error, as well as confidence intervals around the predicted validation error, of neural architectures that we have not yet observed. Suppose we have an ensemble of M neural networks, {f 1M where each fm estimate of the UCB acquisition function via
and uncertainty estimates for
R. We compute an
(a) UCB (afm(a))mm)
36,
Here we use UCB to denote an estimate of a lower confidence bound (since we are performing minimization) for the predictive uncertainty, and 3 is tradeoff parameter control exploration exploitation.
where parameters f DM im (a). and δ 2
(a)
M-1
In each iteration of Bayesian optimization, our goal is to find the neural network from the search space which minimizes the acquisition function. Evaluating the acquisition function for every neural network the search space is computationally infeasible. Instead, we optimize the acquisition function via mutation procedure, where randomly mutate the best architectures that we have trained so far, many times, and then select the architecture from this set which minimizes the acquisition function. A cell is mutated by either adding edge, removing edge, changing one of the operations with some probability.
BANANAS: Bayesian optimization with neural architectures for NAS. Now we present our full NAS algorithm. At the start, draw to random architectures from the search space. Then
5

---

Under review as a conference paper at ICLR 2020
start iterative process, where in iteration train ensemble of meta neural networks on architectures Gu....,. a5-1- Each meta neural network in the ensemble has a different random initialization of the weights and different random ordering of the training set. We create candidate set of architectures by mutating the best architectures we have seen so far, and we choose to train the candidate architecture which minimizes the UCB acquisition function. See Algorithm
Algorithm 1 BANANAS
Input: Search space A, dataset D, parameters fo. T, M, c, k. acquisition function Φ Draw to architectures ao..... ,, ato uniformly at random from A and train them on D Denote (a) as the validation error of a after training For from to to T.
1. Train ensemble of meta neural networks on {(ag. f(a)). (ae. (a)))
2. Generate a set of candidate neural architectures from A by randomly mutating the k architec- tures from {an...., at) with the lowest value of f(a)
3. For each candidate architecture a, evaluate the acquisition function Φ(a)
4. Denote 1 as the candidate architecture with minimum ((a), and evaluate f((a+1)
Output: a" = [ng.
EXPERIMENTS
In this section, discuss experimental setup and results. We give experimental results on the performance the meta neural network itself, as well as the full NAS algorithm compared several NAS algorithms. We start by explaining the two search spaces/datasets that we used.
Search space from NASBench. The NASBench dataset is a tabular dataset designed to facilitate NAS research and fair comparisons between NAS algorithms (Ying al. 2019). It consists of over 423,000 unique neural architectures from a cell-based search space, and each architecture comes with precomputed training. validation, and test accuracies for 108 epochs on CIFAR-10. Most NAS algorithms take several GPU days to complete one trial, however, the NASBench dataset makes it feasible run hundreds of trials of several NAS algorithms.
We give description of the NASBench search space. For the full details, see (Ying et al. 2019). The search space consists of cell with 7 nodes. The first node is the input, and the last node the output. The remaining five nodes can be either x 1 convolution, 3 x 3 convolution, or 3 3 max pooling. The cell can take on any DAG structure from the input to the output with at most 9 edges. The NASBench search space was chosen to contain ResNet-like and Inception-like cells (He et al.) 2016 Szegedy et al. 2016). The syper-architecture consists of nine cells stacked sequentially, with each set of three cells separated by downsampling layers. The first layer before the first cell is convolutional layer, and the hyper-architecture ends with a global average pooling layer and dense layer. See Figure (left).
Search space from DARTS. One of the most popular convolutional cell-based search spaces is the from DARTS (Liu al. 2018b), used for CIFAR-10. The search space consists of two cells with 6 nodes each: convolution cell and a reduction cell, and the hyper-architecture stacks the convolutional and reduction cells. For each cell, the first two nodes the inputs from the previous two cells in the hyper-architecture The next four nodes each contain exactly two edges as input, such that the cell forms a connected DAG. Each edge can take one of seven operations:
3 and 5 x 5 separable convolutions, 3 x 3 and 5 x 5 dilated separable convolutions, 3 x 3 max pooling, 3 x average pooling, identity, and zero (this contrast to NASBench, where the nodes take on operations).
5.1 NASBENCHI EXPERIMENTS
First we evaluate the performance of the meta neural network on the NASBench dataset. The meta neural network consists of sequential fully- coll-cconeecte neural network. The number of layers is set to 10, and each layer has width 20. We use the Adam optimizer with a learning rate of 0.1, and use a mean absolute error loss function. We train the meta neural network 200 architectures, and test.

---

Under review as a conference paper at ICLR 2020
Mutria Escodding (Train Set!
Matrix Eacoding (Tst Sel)
Puth Escoding (Traie Se0
Fulh Encodina (Tast Set)
Deetime ia wort Hetemust
Phodietes case
Dratiiee Seree OuTE Wicerbiaa
Prodictioa uncertality
12
12
12
to-
10 Rrree
34
3.0 Tiree Arrner
7itts Strrer
Th0ce
Figure 3: Predictive uncertainty estimates for architecture validation enror under our ensemble model. We train this model on 200 architectures, and test the adjacency matrix encoding and path encoding on held-out set of architectures well subset of the training set.
Training set size
20
100
500
Train
Test
Train
Test
Train
Test
Adjacency matrix encoding Path-based encoding
0.507
2.977
0.575 0.477
2.626
0.633
2.618
0.384
2.335
1.178
0.317
0.644
Table Meta neural network performance for different featurizations. We report the mean average percent error the training set and the test set for three sizes of the training set.
the standard adjacency matrix encoding well the path encoding discussed in Section 4 See Figure 3 The path- encoding outperforms the adjacency matrix encoding by a factor of with respect absolute error. In Appendix B plot the meta neural network performance with both featurizations for different training set sizes, and we report the training and test errors in Table
Next, we compare BANANAS to five other algorithms. We give brief description of each one.
Random search. The simplest baseline, random search, draws architectures at random and outputs the architecture with the lowest validation error. Despite its simplicity, multiple papers have concluded that random search is a competitive baseline for NAS algorithms (Li & Talwalkar 2019 2019).
Sciuto et al.
Regularized evolution. This algorithm consists of drawing an initial set of cells at random, and then iteratively mutating the best architecture out of sample of all architectures evaluated so far. The architectures with the worst validation error in each iteration are removed from the population. We used the same hyperparameters as in the NASBench paper, but changing the population size from 50 to 30 to account for fewer total queries.
Reinforcement Learning. We used the NASBench implementation of reinforcement learning for NAS (Ying et al.] 2019) based on the REINFORCE algorithm (Williams) 1992). We used this algorithm because prior work has shown that a I-layer LSTM controller trained with PPO is not effective on the NASBench dataset (Ying al. 2019).
AlphaX. AlphaX casts NAS as reinforcement learning problem, using a neural network to guide the search (Wang et al.) 2018). Each iteration, neural network trained select the best action, such as making a small change to, or growing, the current architecture.
TPE. Tree-structured Parzen estimator (TPE) is hyperparameter optimization algorithm based on adaptive Parzen windows. We used the nasbench implementation (Ying et al. 2019).
Bayesian optimization with GP model. We set up Bayesian optimization with Gaussian process model and UCB acquisition. In the Gaussian process, we set the distance function between two neural networks as the sum of the Hamming distances between the adjacency matrices and the list of operations. Note we also used a path-based distance function in our ablation study.
Experimental setup and results. Each NAS algorithm is given a budget of 150 queries. That is, each algorithm can train and output the validation error of at most 150 architectures. Every 10 iterations, return the architecture with the best validation error found by each algorithm far.
7

---

Under review as a conference paper at ICLR 2020
7.4
BANANAS
BANANAS
7.0
adi, enc.
Regularized evolution
tost ertor of bast neural met
BANANAS ad). enc, #2
7.0-
Reinforcement learning
6.8
BayesOpt GP
BayesOpt GP
BayesOpt prior adi, enc.
Alphax
6.6
BANANAS rand. argopt.
test erter of best
Tree-structured Parzen astimator
6.6
6.4
6.2-
6.2
6.0-
6.0-
5.8
5.8
20
40
60
80
100
120
140
20
60
80
100
120
140
neural nets evaluated
neural nets evailuated
Figure 4: Performance of BANANAS compared to benchmarks (left). Ablation study of BANANAS (right). The error bars represent the 30% 70% percentile range.
After all NAS algorithms have completed, we output the test error for each returned architecture. We ran 200 trials for each algorithm. For BANANAS, we use ensemble of size 5 and UCB with S = 0.5 as in Equation [ In each iteration, we chose the top ten candidate architectures to query, to improve runtime and that the algorithm can later be parallelized. Although this strategy may not perform well for continuous search spaces, we found the NASBench search space was discrete enough that this method performs well.
We compared against other black-box optimization algorithms, so we report test error with respect to the number of queries. We note that a plot with respect wall-clock time would look nearly identical, since all NAS algorithms finish the set of 150 queries in roughly the same amount of time. The fastest, random search, takes 46.5 TPU hours, while BANANAS, the slowest, takes 47.0 TPU hours (the average time to train a NASBench architecture is 18.6 minutes on a TPU, reported by (Ying et al.) best
2019h). See Figure 4 (left). BANANAS significantly outperforms all other baselines, and of our knowledge, BANANAS achieves state-of-the-ar error NASBench in the 100-150 queries setting. The standard deviation among 200 trials for all NAS algorithms were between 0.16 and 0.22. BANANAS had the lowest standard deviation, and regularized evolution had the highest standard deviation.
Ablation study. Our NAS algorithm has several moving parts, including the meta neural network model, the path-based feature encoding of neural architectures, the acquisition function, and the acquisition optimization strategy. We run thorough ablation study by removing each piece of the algorithm separately. particular, we compare against the following algorithms: (1) BANANAS where the featurization of each neural architecture is not the path-based encoding, but instead the common adjacency matrix and one-hot list of operations encoding: (2) BANANAS where the featurization of each neural architecture is the continuous variant of the adjacency matrix encoding from the nasbench paper (Ying et al., 2019); (3) BANANAS with a GP model instead of neural network model, where the distance function the GP is computed the Hamming distance between the path- enchhinn vectors; (4) BANANAS with a GP model, where the distance function is computed as the sum of the Hamming distances between the adjacency matrices and the list of operations; (5) BANANAS where the acquisition funtion is optimized by drawing 1000 random architectures, instead of a mutation algorithm. We found that BANANAS significantly outperformed all of these variants. The path aath-encoding had the greatest effect on performance, while the acquisition optimization strategy had the smallest effect on performance. See Figure (right).
we present several more experiments. We give each NAS algorithm a budget of 500 queries instead 150, and we show that BANANAS still outperforms all other algorithms. We discuss different method to use the NASBench dataset (querying random vs mean validation error) and we present results in this setting, showing that our algorithm still performs the best. We also test three other common acquisition functions with BANANAS.
In Appendix B
8

---

Under review as a conference paper at ICLR 2020
NAS Algorithm
Source
Test error
Queries Runtime
Method
Avg
Best
SNAS
Xie et al.
2018)
2.85
1.5
Gradient based
ENAS
Pham al.
201
2.89
0.5
RL
Random search
Liu et al.
2018b)
3.29
4
Random
DARTS
Liu et al.
2018b)
2.76
5
Gradient-
ASHA
Li & Talwalkar
2019
3.03
2.85
700
9
Successive halving
Random search WS
Talwalkar
2019
2.85
2.71
1000
9.7
Random
DARTS
Ours
2.68
2.57
5
Gradient- based
ASHA
Ours
3.08
2.98
700
9
Successive halving
BANANAS
Ours
2.64
2.57
100
11.8
Neural BayesOpt
Table 2: Comparison of the mean test error of the best architectures returned by three NAS algorithms. The runtime is in total GPU-days on a Tesla V100. Note that ASHA queries use varying numbers of epochs.
5.2 DARTS SEARCH SPACE EXPERIMENTS.
We test the BANANAS algorithm on the search space from DARTS. We give BANANAS a budget of 100 queries, where each query involves training neural network for 50 epochs and reporting its validation error. We parallelize the algorithm by choosing 10 neural networks to train in each iteration of Bayesian optimization. The total computation 11.8 GPU days.
To ensure fair comparison by controlling all hyperparameter settings and hardware (Lindauer & Hutter 2019). we re-trained the architectures from papers which used the DARTS search space and reported the final architecture. We report the mean test error over five random seeds of the best architectures found by BANANAS, DARTS, and ASHA (Li & Talwalkar 2019) We trained each architecture using the default hyperparameters from Li and Talwalkar [Li & Talwalkar 2019) for 600 epochs.
The BANANAS architecture achieved an average of 2.64% accuracy, which is state-of-the-art for this search-space and final training parameter settings. See Table We also compare to other NAS algorithms using the DARTS search space, however, the comparison is not perfect due differences in the pytorch version of the final training code (which appears to change the final percent error by ~).)%) We cannot fairly compare our method recent NAS algorithms which use a larger search space than DARTS, or which train the final architecture for significantly more than 600 epochs (Laube Zell 2019 Liang al., 2019 Zhou et al. 2019). Our algorithm significantly beats ASHA, multi-fidelity zeroth order NAS algorithm, and is on par with DARTS, first-order method. We emphasize that since BANANAS a zeroth order method, it allows for easy parallelism, integration with optimizing other hyperparameters, easy implementation, and optimization with respect to other non-differentiable objectives.
In the appendix, we run through the NAS research checklist (Lindauer & Hutter 2019
6 CONCLUSION AND FUTURE WORK
In this work, we propose a novel method for neural architecture search. Our method uses Bayesian optimization with meta neural network model, and we encode the neural architectures using path-based encoding scheme. This allows the meta neural network to accurately predict the validation error of new neural architectures. Our NAS algorithm significantly outperforms all other baselines on the NASBench dataset and outperforms state-of-the-an algorithms the search space from DARTS.
One of the most interesting follow-up ideas is to develop multi-fidelity version of BANANAS. For example, incorporating successive--alliin approach to BANANAS could result in a significant decrease the runtime without substantially sacrificing accuracy. would also be interesting to run algorithm other search spaces and datasets. such Penn TreeBank and ImageNet. Finally, while we demonstrated that our path- mash- featurization performs very well for the most popular cell-based search spaces, our featurization would have trouble scaling to large cell-based search

---

Under review as a conference paper at ICLR 2020
spaces, its dimensionality is exponential in the number of nodes per cell. It would be interesting to modify our approach so that scales better to larger search spaces.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. arXiv preprint arXiv:1611.0216% 2016.
Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. arXiv preprint urXiv:/703) 10823, 2017.
William H Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-paramete, optimization. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2011.
Zalán Borsos, Andrey Khorlin, and Andrea Gesmundo. Transfer nas: Knowledge transfer between search spaces with transformer agents. arXiv preprint 15G6:09000081000 2019.
Youngwon Choi, Yongchan Kwon, Hanbyul Lee, Beom Joon Kim, Myunghee Cho Paik, and Joong- Ho Won. Ensemble of deep convolutional neural networks for prognosis of ischemic stroke. In International Workshop on Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries, 2016.
Corinna Cortes, Xavier Gonzalvo, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Adanet:
Adaptive structural learning of artificial neural networks. In Proceedings of the International Conference on Machine Leurning (ICML), 2017.
Boyang Deng, Junjie Yan, and Dahua Lin. Peephole: Predicting network performance before training. arXiv preprint arXiv: 1712.03331, 2017.
Tobias Domhan, Jost Tobias Springenberg. and Frank Hutter. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In /wwenty-Furth International Joint Conference on Artificial Intelligence, 2015.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv preprint arXiv:1808.053777 2018.
Dario Floreano, Peter Dür,, and Claudio Mattiussi. Neuroevolution: from architectures to learning. Evolutionury intelligence, 1(1):47-62, 2008
Peter Frazier. A tutorial on bayesian optimization. arXiv preprint 1807.0 2018.
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and Sculley. Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1487-1495. ACM, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pallern recognition, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2017.
Roxana Istrate, Florian Scheidegger, Giovanni Mariani, Dimitrios Nikolopoulos, Costas Bekas, and A Cristiano Malossi. Tapas: Train-less accuracy predictor for architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank pac-learnable. In Proceedings the International Conference on Machine Learning (ICML), 2017.
Haifeng Jin, Qingquan Song, and Xia Hu. Auto-keras: Efficient neural architecture search with network morphism. arXiv preprint arXiv: 10282, 2018.
11

---

Under review as a conference paper at ICLR 2020
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. In Advances in Neural Information Processing Systems, pp. 2016-2025, 2018.
Hiroaki Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex systems, 4(4):461-476, 1990.
Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction with bayesian neural networks. ICLR 2017, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2012.
Harold J Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Engineering, 86(1):97-106, 1964.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, pp. 9402-6413,22 2017.
Kevin Alexander Laube and Andreas Zell. Prune and replace nas. arXiv preprint arXiv.190.007520 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv: 2019.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel sandit-based approach to hyperparameter optimization. arXiv preprint arXiv: 1603.0660006660 2016.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu Hc, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv preprint /909 00005, 2019.
Marius Lindauer and Frank Hutter, Best practices for scientific research on neural architecture search. arXiv preprint arXiv:
2019.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hi- erarchical representations for efficient architecture search. arXiv preprint arXiv:1711.000 2017.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055. 09055, 2018b.
Krzysztof Maziarz, Andrey Khorlin, Quentin de Laroussilhe, and Andrea Gesmundo. Evolutionary- neural hybrid agents for architecture search. arXiv preprint
2018.
Jonas Močkus. On bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference, pp. 400-404. Springer, 1975.
Willie Neiswanger, Kirthevasan Kandasamy, Barnabas Poczos, Jeff Schneider, and Eric Xing. Probo: framework for using probabilistic programming in bayesian optimization. arXiv preprint 151 2019.
Valerio Perrone, Rodolphe Jenatton, Matthias Seeger, and Cedric Archambeau. Multiple adaptive bayesian linear regression for scalable bayesian optimization with warm start. arXiv preprint 172iv: 2017.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint arXiv: 802.032063 2018.
12

---

Under review as a conference paper at ICLR 2020
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School Machine Learning, pp. 63-71. Springer, 2003.
Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint arXiv: 190.001220..1112
Syed Asif Raza Shah, Wenji Wu, Qiming Lu, Liang Zhang. Sajith Sasidharan, Phil DeMar, Chin Guok, John Macauley, Eric Pouyoul, Jin Kim, et al. Amoebanet: An sdn-enabled network service for big data science. Journal of Network and Computer Applications, 119:70-82, 2018.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2012.
Jasper Snoek, Oren Rippel. Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180 2015.
Jost Tobias Springenberg, Aaron Klein, Stefan Falkner, and Frank Hutter. Bayesian optimization with robust bayesian neural networks. In Advances in Neural Information Processing Systems, pp- 4134 4142, 2016
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3395, 2009.
Kenneth O Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99-127, 2002.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception- resnet and the impact of residual connections on learning. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Mingxing Tan and Quoc V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint ArXi: 19966, 2019.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-29)) 1933.
Linnan Wang, Yiyang Zhao, Yuu Jinnai, and Rodrigo Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv: 0804007440, 2018.
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning action space. arXiv preprint 19de::996...88... 2019.
Ronald J Williams. Simple statistical gradient- algorithms for connectionist reinforcement learning. Machine learning, pp. 229-256, 1992.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arXiv: 1812.09926 2018
Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. arXiv preprint 2019.
Hongpeng Zhou, Minghao Yang, Jun Wang. and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. arXiv preprint arXiv:1905.04919 2019.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08455 2018.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In Proceedings of the International Conference Learning Representations (ICLR), 2017.
13

---

Under review as a conference paper at ICLR 2020
A RELATED WORK CONTINUED
Neural architecture search. Evolutionary algorithms for neural architecture search have been studied since at least the 1990s (Floreano et al. 2008 Kitano 1990, Stanley & Miikkulainen, 2002).
This research area was revitalized when NASNet gained significant attention (Zoph & Le 2017).
NASNet is reinforcement learning algorithm for NAS which achieves state-of-the art results on CIFAR-10 and PTB; however, the algorithm requires 3000 GPU days to train. NASNet spurred a number of follow-up up work, eventually pushing the required computation for NAS on CIFAR- 10 and
PTB to under 10 GPU days (Pham et al., 2018: Liu et al.) 20 by Ying et al. 2019 Kandasamy
et al. 2018: Jin et al. 2018 [Shah et al. 2018). Some of the most popular techniques for NAS include
evolutionary algorithms (Shah et al. (0188) reinforcement learning (Zoph & Le 2017 7 Pham ct al.
2018
Liu et al., 2018a Tan & Le. (2019), Bayesian optimization (Kandasamy al. 2018 Jin ct al.
2018
and gradient descent (Liu et al. 2018b).
Recent papers have called for fair and reproducible experiments in the future Li & Talwalkar 2019 Sciuto et al.] [211]] Ying et al.] (2019). In this vein, the NASBench dataset was created, which contains over 400k neural architectures with precomputed training, validation, and test accuracy (Ying et al. 2019).
A recent algorithm, AlphaX, uses meta neural network to perform NAS (Wang et al. 2018). This is a similar high-level idea to our work but with many key differences. Their search is progressive, and each iteration makes a small change to the current neural network, rather than choosing a completely new neural network. Therefore, their meta neural network is trained to optimize the selection of new actions as well as to predict the performance of the new progressive network. Furthermore, they use an adjacency matrix fcaturization for the inputs to the meta neural network, which we find to perform worse than our path-based encoding.
Bayesian optimization. Bayesian optimization is leading technique for zeroth order optimization
when function queries expensive (Rasmussen) 2003) Frazier 2018), and has seen great success
in hyperparameter optimization for deep learning [Rasmussen 2003 Golovin et al., 2017 7 Li et al.
2016). The majority of Bayesian optimization literature has focused on Euclidean categorical input domains, and has used GP model (Rasmussen) 2003 Golovin et al. 2017 Frazier 2018 Snoek ct al. 2012). There has also been some previous work on using neural network models in Bayesian optimization (Snock et al. 2015 Springenberg et al. (0166), applied to the task of hyperparameter optimization. Recently, there have been couple works that use Bayesian optimization with GPs for NAS (Kandasamy et al. 2018 Jin et al. 2018).
Predicting neural network accuracy. There are several approaches for predicting the validation accuracy of neural networks, such as a layer-wise encoding of neural networks with an LSTM algorithm (Deng al. 2017). ), and layer-wise encoding and dataset features to predict the accuracy for neural network + dataset pairs (Istrate et al.) 2019). There is also work in predicting the learning curve of neural networks for hyperparameter optimization (Klein al. 2017 Domhan al. 2015)
or NAS (Baker et al. 2017) using Bayesian techniques.
Hyperparameter optimization using Bayesian optimization with neural networks. Snoek et al. showed that Bayesian optimization can scale by using neural network to set up a kernel and a posterior distribution, instead of a Gaussian process (Snock et al. 2012). Springenberg et al. give similar results using a stochastic gradient Hamiltonian Monte Carlo approach (Springenberg et al. 2016). Perrone et al. show how to apply warm start to Bayesian optimization with neural networks (Perrone et al. 2017).
B ADDITIONAL EXPERIMENTS
In this section, we present more experiments for the meta neural network and for BANANAS. We also discuss our experimental setup in more detail.
14

---

Under review as a conference paper at ICLR 2020
Adjarency Est encoding. training size 20
Adjacency Est encoding, training set size 100 Adjacency list encoding, training set size 500
prodictdd SrTEr
12
14
1.0
122
14
Fue percent error
percent arror
true percent umor
Path encoding. training set size 20
Potth encoding, training set size 100
Path encading, training set size 500
sata
predictos porcent srer
predicte percent erter
12-
12
-2-
predict perpent
1.0
12
14
12
percent
Figure 5: Performance of the neural network with adjacency matrix encoding (row and path encoding (row 2). The training set is in blue, and the test set is in orange.
B. META NEURAL NETWORK EXPERIMENTS
We plot the meta neural network performance with both featurizations for training sets size 20, 100, and 500. We the same experimental setup described in Section See Figure 5 We note that a training set of size 20 neural networks is realistic at the start of a NAS algorithm, and size 200 is realistic near the middle end of NAS algorithm.
B.2 NASBENCH EXPERIMENTS
We run three more experiments on NASBench: rumning the algorithms with a budget of 500 queries rather than 150, testing out different acquisition functions with BANANAS, and using a slightly different validation error metric. All algorithms were run with 200 trials unless otherwise noted.
NAS algorithms running for 500 queries. In our main set of experiments, we gave each NAS algorithm budget of 150 queries. That is, each NAS algorithm can only choose 150 architectures to train and evaluate. Now we give each NAS algorithm a budget of 500 queries. See (lefte largely see the same trends, although the gap between BANANAS and regularized evolution becomes smaller after query 400.
Acquisition functions. We tested BANANAS with three other common acquisition function in addition to UCB: expected improvement (EI) (Močkus 1975), probability of improvement (PI) (Kush
ner 1964), and Thompson sampling (TS) (Thompson 1933). First give the formal definitions of each acquisition function.
Suppose have trained collection of M predictive models, {.fm LM where fm A R. Following previous work (Neiswanger et al. 2019), we use the following acquisition function estimates for input architecture A:
15

---

Under review as a conference paper at ICLR 2020
6.0
BANANAS
BANANAS (EI)
BANANAS
Regula rzed ovolutien
tast eiror of bast neural net
BANANAS (TS)
test eitor of best neura
Reinforcement leamning
6.6
BANANAS
Opt prior
6.4-
6.4
6.2
6.0
0
100
200
300
400
500
20
60
100
120
140
neural nets ovaluated
neuraal nets evailuated
Figure 6: NAS algorithms with budget of 500 queries (left). Comparison of different acquisition functions (right).
Φm(()) = [ [m((a) >
- fmm(4) [m)(a)] fSam
Urrin
(Ymin - -y) (f. dy
Mmin
Ummi
(2)
= || N (ff:0²)
Bmn
Φ1((x)) E [m((v) >>
Y/min
(3)
00
ΦuCu(I) (x) UCB (z) = Bō
(4)
ΦTS (x) ( fm) mn Unif (1)
(5)
In these acquisition function definitions, (xx) = if is true and O otherwise, and we are making normal approximation for our model's posterior predictive density, where we estimate parameters
f f= = fm (z), and ă to denote some estimate of lower confidence bound for the posterior predictive density (note that we use a lower confidence bound rather than an upper confidence bound since we are performing minimization), and 3 is tradeoff parameter. In experiments we set B 0.5.
3 Ems: (z))))))))² In the UCB acquisition function, we use UCB M-1
See Figure 6 (right). see that the acquisition function has little effect on the performance of BANANAS, though UCB performs best.
Mean vs. random validation error. the NASBench dataset, each architecture was trained to 108 epochs three separate times with different random seeds. The NASBench paper conducted experiments by choosing a random validation error when querying each architecture, and then reporting the mean test eггог at the conclusion of the NAS algorithm. We found that the mismatch (choosing random validation error, but mean test error) added extra noise that would not be present during real-life NAS experiment. Another way to conduct experiments mean validation error and mean test error. This is the method we used in Section 5 and the previous experiments from this section. Perhaps the most realistic experiment would be to validation error and the test eттor corresponding to that validation error, however, the NASBench dataset does explicitly give this functionality. In Figure 7 we give results in the setting of the NASBench paper, using random validation error and mean test error. We ran each algorithm for 500 trials. Note that the test error across the board is higher because the correlation between validation and test error is lower (i.e., validation error is noisier than normal). BANANAS still performs the best out of algorithms that we tried. see the trends are largely unchanged, although Bayesian optimization with GP model performs better than regularized evolution. A possible explanation is that Bayesian optimization with a GP model is better-suited to handle noisy data than regularized evolution.
NASBench is to
random
C BEST PRACTICES CHECKLIST FOR NAS RESEARCH
The area NAS has seen problems with reproducibility. as well as fair empirical comparisons, even more than most other areas of machine learning. Following calls for fair and reproducible NAS
16

---

Under review as a conference paper at ICLR 2020
6.8
Random search
Regularized evolution
6.7
Reinforcement learning
BayesOpt w. GP prior
6.6
Lest error best
6.4
6.3
6.2
20
40
60
80
100
120
140
neural evalusted
Figure 7: NAS experiments with random validation error and mean test error.
research (Li & Talwalkar| 2 Sciuto et al. 2019; Ying et al., 2019). best practices checklist was recently created (Lindauer & Hutter 2019). order to promote fair and reproducible NAS research, we address all points on the checklist, and we encourage future papers to do the same.
Code for the training pipeline used to evaluate the final architectures. We used two of the most popular search spaces in NAS research, the NASBench search space, and the DARTS search space. For NASBench, the accuracy of all architectures were precomputed. For the DARTS search space, we released our fork of the DARTS repo, which is forked from the DARTS repo designed specifically for reproducible experiments (Li & Talwalkar 2019). making trivial changes to account for pytorch 1.2.0.
Code for the search space. We used the popular and publicly avaliable NASBench and DARTS search spaces with no changes.
Hyperparameters used for the final evaluation pipeline, as well as random seeds. We left all hyperparameters unchanged. We trained the architectures found by BANANAS, ASHA, and DARTS five times each, using random seeds 0, 1, 2, 3, 4.
For all NAS methods you compare, did you use exactly the same NAS benchmark, including the same dataset, search space, and code for training the architectures and hyperparameters for that code? Yes, we did this by virtue of the NASBench dataset. For the DARTS experiments, we used the reported architectures (found using the same search space and dataset as our method), and then we trained the final architectures using the same code, including hyperparameters. We compared different NAS methods using exactly the same NAS benchmark.
Did you control for confounding factors? Yes, we used the same setup for all of our NASBench experiments. For the DARTS search space, we compared our algorithm two other algorithms using the same setup (pytorch version, CUDA version, etc). Across training over 5 seeds for each algorithm, we used different GPUs, which we found to have no greater
effect than using a different random seed.
Did you run ablation studies? Yes, we ran a thorough ablation study.
Did you use the same evaluation protocol for the methods being compared? Yes, we used the same evaluation protocol for all methods and we tried multiple evaluation protocols.
Did you compare performance over time? In main NASBench plots, we compared per- formance to number of queries, since all of our comparisons were to black-boo box optimization algorithms. Note that the number of queries almost perfectly correlated with runtime. We computed the run time and found all algorithms were between 46.5 and 47.0 TPU hours.
Did you compare to random search? Yes.
Did you perform multiple runs of your experiments and report seeds? We ran 200 trials of our NASBench experiments. Since we ran so many trials, we did not report random seeds. We ran four total trials of BANANAS on the DARTS search space. Currently we do not have fully deterministic version of BANANAS on the DARTS search space (which would be harder to implement as the algorithm runs on 10 GPUs). However, the average final error across trials within 0. %
17

---

Under review as a conference paper at ICLR 2020
Did you use tabular or surrogate benchmarks for in in-depth evaluations Yes, we used NAS- Bench.
Did you report how you tuned hyperparameters, and what time and resources this required? We performed light hyperparameter tuning for the meta neural network to choose the number of layers, layer size, learning rate, and number of epochs. In general, we found our algorithm
work well without hyperparameter tuning.
Did you report the time for the entire end-to-end NAS method? We reported time for the entire end-to-end NAS method.
Did you report all details of your experimental setup? We reported all details of our experimental setup.
18


Reviews:
[{"review_id": "HJlGpWShFS", "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": "\nThe paper introduces a new encoding for cell structures to improve efficiency of neural architecture search methods.\nAs a second contribution the paper proposes Bayesian optimization with an ensemble of neural networks as probabilistic model for the objective function.\nBoth contributions combined show superior performance on the Nasbench101 benchmark as well as competitive performance on the DARTS search space.\n\nWhile the paper identifies an important problem - encoding of architectures - I do not think the paper is ready for acceptance.\n\nAbout the encodings:\n\nFirst, using different encodings to enable better architecture search has been investigated by others before.\nFor example, Ying et al. also provided different encodings of the adjacency matrix for Nasbench101 besides the used binary encoding and it seems that different methods work well with different encodings.\nAlso in the work by Kandasamy et al. they presented an encoding for architecture, such that Bayesian optimization can be applied.\n\nSecond, the encoding described in the paper lacks some intuition.\n\n - How does enumerating all paths and encoding them as a binary vector convey more information than just using the adjacency matrix?\n\n - Lead isomorphic graphs, which for example occur in Nasbench101, to the same encoding?\n\n - It seems somewhat counter intuitive to use a large binary vector (more than 18000 dimensional vector for the DARTS space) as encoding for Bayesian optimization which is known to struggle with high dimensional input spaces.\n\n\nAbout the Bayesian optimization strategy:\n\nThe proposed probabilistic model for Bayesian optimization seems straight forward and simple. Also here, previous work (Snoek et al, Springenberg et al., Perrone et al)  already proposed to use neural networks and ,in order to be more convincing, the paper should include a comparison to these methods.\nFurthermore, the paper should clarify how the diversity in the neural network ensemble is enforced. Are the neural networks trained with different random initialization? How does it compare to the method proposed by Lakshminarayanan et al. which showed better performance for neural network ensembles based only on different random initialization?\n\n\nMinor comments:\n\n\n- In the Nasbench101 paper other Bayesian optimization strategies (e.g SMAC, BOHB, TPE) showed strong performance. The results would be more convincing if these methods are included in the comparison.\n\n- Following the empirical protocol by Ying et al. the results would be easier to parse if the Figure 3  could report the log test regret on the y-axis. I am also missing a figure that shows the robustness of the method across independent runs.\n\n- How are invalid architectures in the Nasbench101 (e.g architectures that violate the max edge constraint) treated in the experiments?\n\n- I think the paper is missing the following references:\n\nSimple and scalable predictive uncertainty estimation using deep ensembles\nB Lakshminarayanan, A Pritzel, C Blundell\nAdvances in Neural Information Processing Systems, 6393-6395\n\nScalable hyperparameter transfer learning\nV Perrone, R Jenatton, M Seeger, C Archambeau\nAdvances in Neural Information Processing Systems, 6845-6855\n\n\n\npost rebuttal\n------------------\n\n\nI thank the authors for answering my questions regarding the path encoding and taking the time to improve the empirical evaluation of the paper. While I think that the paper has improved, I am afraid that the contributions of the paper are still not strong enough to reach the bar of acceptance because of the following reasons: \n\n- The path encoding is an interesting approach and seems to improve upon just using the adjacency matrix directly, it doesn't scale and, hence, it remain somewhat unclear how valuable it is in practice. \n\n- More importantly, I am not convinced that the proposed neural network model represents a sufficient contribution. After some discussion with the authors, they agree that existing BO methods based on neural networks could also be applied to this setting and even say that they may perform well with the path encoding. However, they are not include them in the comparison and only promise to add them for the final evaluation.  I am concerned that if it turns out that other methods perform as well or even better, it would dramatically lower the contribution of the paper.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "B1xcs9UwFB", "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": "The paper considers the neural architecture search using Bayesian optimisation. The paper first propose a path-based encoding scheme to featurise the neural architectures. A path encoding of a cell is created by enumerating all possible paths from the input node to the output node. Then, they propose to train 5 neural networks and ensemble these networks to get the prediction (including the predictive value and uncertainty). The paper optimises the acquisition function via a mutation procedure, where we randomly mutate the best architectures that we have trained so far, many times, and then select the architecture from this set which minimizes the acquisition function.\n\nWhile the writing is readable and the experiments seem promising, the reviewer thinks that the novelty and contribution of the paper are limited. Particularly, using 5 neural networks for estimating the uncertainty is less convincing. This is because it would have been better if we can train a Bayesian neural network to provide the uncertainty quantification directly.\n\n\nMinor:\nPage 5: “randomly randomly”\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1eaRF43YH", "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 develop a path-based encoding scheme to featurize the neural architectures that are used to train the neural network model, and design a NAS algorithm that performs Bayesian optimization using a neural network model. The experiments show the priority of the proposed method.\n\nIn general, this paper is easy to follow, but the contribution is limited. The author did not give a clear explanation of why does this method work. There are several problems that exist in the paper:\n\n1.\tThe paper introduced a path-based encoding scheme, which seems have nothing different from enumerating all possible paths. Any additional operations should be clarified in the paper.\n2.\tThe method retains new architectures with high UCB value. However, the author did not prove that a higher UCB value leads to a better architecture. Eq.(1) trained several different networks to predict the accuracy. However, when using early stop stragegy, the intermediate accuracy is not convincing, and the new architecture selected based on UCB may not perform well when training with full epochs. If early stop is not used, there is no need  to predict the accuracy with different networks.\n3.\tIn my opinion, Algorithm 1 is a simplified traditional Evolutionary Algorithm, which only have mutation operation and do not have selection and crossover operation, and has limited novelty.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper uses Bayesian optimization with neural networks for neural architecture search. 
One of the contributions is a path-based encoding that enumerates every possible path through a cell search space. This encoding is shown to be surprisingly powerful, but it will not scale to large cell-based search spaces or non-cell-based search spaces. The availability of code, as well as the careful attention to reproducibility is much appreciated and a factor in favor of the paper.

In the discussion, it surfaced that a comparison to existing Bayesian optimization approaches using neural networks would have been possible, while the authors initially did not think that this would be the case. The authors promised to include these comparisons in the final version, but, as was also discussed in the private discussion between reviewers and AC, this is problematic since it is not clear what these results will show. Therefore, the one reviewer who was debating about increasing their score did in the end not do so (but would be inclined to accept a future version with a clean and thorough comparison to baselines). 

All reviewers stuck with their score of "weak reject", leaning to borderline. I read the paper myself and concur with this judgement. I recommend rejection of the current version, with an encouragement to submit to another venue after including a comparison to BO methods based on neural networks.
Decision: Reject