Neural Architecture Search by Learning Action Space for Monte Carlo Tree Search
Authors: Linnan Wang
Saining Xie
Teng Li
Rodrigo Fonseca
Yuandong Tian
Venue:  (2020)
Keywords: MCTS
Neural Architecture Search
Search

Abstract: Neural Architecture Search (NAS) has emerged as a promising technique for automatic neural network design. However, existing NAS approaches often utilize manually designed action space, which is not directly related to the performance metric to be optimized (e.g., accuracy). As a result, using manually designed action space to perform NAS often leads to sample-inefficient explorations of architectures and thus can be sub-optimal. In order to improve sample efficiency, this paper proposes Latent Action Neural Architecture Search (LaNAS) that learns actions to recursively partition the search space into good or bad regions that contain networks with concentrated performance metrics, i.e., low variance. During the search phase, as different architecture search action sequences lead to regions of different performance, the search efficiency can be significantly improved by biasing towards the good regions. On the largest NAS dataset NASBench-101, our experimental results demonstrated that LaNAS is 22x, 14.6x, 12.4x, 6.8x, 16.5x more sample-efficient than Random Search, Regularized Evolution, Monte Carlo Tree Search, Neural Architecture Optimization, and Bayesian Optimization, respectively. When applied to the open domain, LaNAS achieves 98.0% accuracy on CIFAR-10 and 75.0% top1 accuracy on ImageNet in only 803 samples, outperforming SOTA AmoebaNet with 33x fewer samples.

Under review as a conference paper at ICLR 2020
NEURAL ARCHITECTURE SEARCH BY LEARNING ACTION SPACE FOR MONTE CARLO TREE SEARCH
Anonymous authors Paper under double-bling review
ABSTRACT
Neural Architecture Search (NAS) has emerged as promising technique for automatic neural network design. However, existing NAS approaches often utilize manually designed action space, which is not directly related to the performance metric to optimized (e.g., accuracy). As a result, using manually designed action space to perform NAS often leads to sample-inefficier explorations of architectures and thus can be sub-optimal. In order to improve the sample efficiency, this paper proposes Latent Action Neural Architecture Search (LaNAS), which learns actions to recursively partition the search space into good or bad regions that contain networks with concentrated performance metrics, i.e., low variance. During the search phase, as different architecture search action sequences lead to regions with different performance, the search efficiency can be significantly improved by biasing towards the good regions. On NAS datasets, our experimental results demonstrated that LaNAS 37x, 21.7x, 19.3x, 10.7x, 12.3x, 16.5x more samplc-efficient than Random Search, Regularized Evolution, Monte Carlo Tree Search, Neural Architecture Optimization, TPE and SMAC, respectively. When applied to the open domain, LaNAS achieves 98.0% accuracy on CIFAR-10 and 75.0% topl accuracy on ImageNet in only 803 samples, outperforming SOTA AmoebaNet with 33 fewer samples.
INTRODUCTION
During the past two years, there has been growing inter- est in Neural Architecture Search (NAS) that aims to auto- mate the laborious process of designing neural networks. Architectures found by NAS have achieved remarkable results in image classification (Zoph and Le (2016); Real
entire design space Q
promising region
region
Actions linear classifler bifurcates
B
et al. (2018), ), object detection and segmentation Ghiasi et (2019); Chen al. (2019); Liu et al. (2019)),
well as other domains such as language tasks (Luong èt al. (2018); So et al. (2019)).
D
Starting from hand-designed discrete model space and ac- tion space, NAS utilizes search techniques explore the search space and find the best performing architectures with respect a single multiple objectives (e.g., accu- racy, latency, or memory), and preferably with minimal search cost.
Sampling sub-space
Figure I: tecture Search: Starting from the entire model space, at each search stage we learn action (or of linear con- straints) to separate good from bad mod- els for providing distinctive rewards for better searching.
Latent Action Neural Archi-
However, one common issue faced by the previous works on NAS is that the action space needs be manually de- signed. The action space proposed by Zoph et al.] (2018) involves sequential actions to construct network, such as selecting two nodes, and choosing their operations. Other
prior works including reinforcement learning based (Zoph
and Le (2166); [akerr et al.) (2016)), evolution based (Real al. (2018) 2017)), and MCTS- based (Wang et al. (2019); Negrinho and Gordon (2017) approaches, all use manually designed action spaces. As suggested in Sciuto et (2119) and Talwalkar (2019): Xie et al. (219). action

---

and Under review as a conference paper at ICLR 2020
sequentaal
sangles
0.023
the current best
6.70-
R:t9
accurncy
global
8.48
samples
global
sequental
0.75
500
1856
global
sequentaal
accuracy
ith sample
(a) Visuaitzation of MCTS scorch trees
(b) Roward distribution at two child nodes
(c) Search efficioncy
Figure 2: Illustration of motivation: (a) visualizes the MCTS search trees using sequent ial and global action space. The node value (i.e. accuracy) is higher if the color is darker. (b) For given node, the reward distributions for its children. is the average distance over all nodes. gl obbal better separates the search space by network quality, and provides distinctive reward in recognizing promising path. (c) As a result, global finds the best network much faster than sequent ial.
space design alone can be critical to network performance. Furthermore, it is often the case that manually designed action space is not related the performance that needs be optimized. In Sec we demonstrate example where subtly different action space can lead to significantly different search efficiency. Finally, unlike games that generally have a predefined action space (e.g.. Atari, Chess and Go), in NAS, it is the final network that matters rather than the specific path of the search, which gives a large playground for action space learning.
Based on the above observations, we propose Latent Action Neural Architecture Search(LaNAS) that learns the action space to maximize search efficiency for performance metrics. Previous methods typically construct an architecture from empty network by sequentially applying predefined actions, e.g. adding layers, setting the kernel or depth, resulting in a state space that provides undiscriminating rewards to inform the search (Fig. 2h sequentiall LaNAS takes dual approach and treats each action as a linear constraint that intersects with the search space S2 to bifurcate it into a good and bad region that contains networks with similar performance metric (Fig. D Once multiple actions are recursively applied to the entire search space, the search space is clearly separated (e.g. Fig. 22p global. Fig. 4) into regions that provide more informative rewards, thereby greatly improving the search efficiency. To achieve this goal, LaNAS iterates between learning and searching stage. In the learning stage, each action in LaNAS learned to partition the model space into high-performance and cow-performance regions, to achieve accurate performance prediction. In the searching stage, LaNAS applies MCTS on the learned action space to sample more model architectures. The learned actions provide informed guide for MCTS to sample from performance-promiss the adaptive exploration in MCTS collects more data to progressively refine learned actions to zoom into more promising regions for further improving the sample efficiency. The iterative process is jump-started by first collecting a few random samples.
regions, while
We show that LaNAS yields tremendous acceleration diverse set of benchmark tasks, including publicly available NASBench-100 101 (420,000 NASNet models trained on CIFAR-10) (Ying et al. (2019)), our self-curated ConyNet-60K (60,000 plain VGG-style ConvNets trained CIFAR-I0), and LSTM-10K (10,000 LSTM cells trained on PTB). Our algorithm consistently finds the best performing architecture all three tasks with least order of fewer samples (on average) than Random Search, Regularized Evolution, MCTS, Neural Architecture Optimization and Bayesian Optimization. In the open domain search scenario, our algorithm finds network that achieves 98.0% accuracy on CIFAR-10 and 75.0% topl accuracy (mobile setting) on ImageNet in only 803 samples, using 33x fewer samples and achieving higher accuracy than AmoebaNet (Real al.) (2018)). Moreover, we empirically demonstrate that the learned latent actions can transfer to new search task to further boost efficiency. Finally, we provide empirical observations to illustrate the search dynamics and analyze the behavior of our approach. We also conduct various ablation studies in together with a partition analysis to provide guidance determining search deploying LaNAS in practice.
A MOTIVATING EXAMPLE
To demonstrate the importance action space in NAS, we start with a motivating example. Consider simple scenario of designing plain Convolutional Neural Network (CNN) for CIFAR-10 image
2

---

Under review as a conference paper at ICLR 2020
SEARCH PHASE
LEARNING PHASE
sempling
beckgroozeggtte
Learning actions:
A
Ri
orgi $20.0)
Frad
AS= Union8s,
Figure 3: An overview of LaNAS: LaNAS is an iterative algorithm which each iteration comprises search phase and learning phase. The search phase uses MCTS to samples networks, while the learning phase learns a linear model between network hyper-paramen parameters and their accuracies.
classification. The primitive operation is Conv-ReI.U layer. Free structural parameters that
vary include network depth I. 21, 3, 4, 5), number filter channels C = {322, 64) and kernel size K 13 3,5 5 5}. This configuration results in search space of 1,364 networks. To perform the search, there are two natural choices of the action space: sequent i and global. sequent ial comprises actions the following order: adding layer setting kernel size K₁, setting filter channel Cj. The actions are repeated L times. On the other hand, global uses the following actions instead: [Setting network depth L, setting kernel size KI....,, setting filter channel J. For these two action spaces, MCTS is employed to perform the search. Note that both action spaces can cover the entire search space but have very different search trajectories.
Fig. aaa visualizes the search for these two action spaces. Actions in global clearly separates desired and undesired network clusters, while actions in sequent lead to network clusters with mixture of good or bad networks in terms of performance. As result, the overall distribution of accuracy along the search path (Fig. (Fig.E(b) (()) shows concentration behavior for global, which not the case for sequent in ial. We also demonstrate the overall search performance in Fig As shown in the figure, global finds desired networks much faster than sequential.
This observation suggests that changing the action space can lead very different search behavior and thus potentially better sample efficiency. In other words, an early exploration on the network depth critical. Increasing the depth is optimization direction that can potentially lead to better model accuracy. One might come across a natural question from this motivating example. Is it possible find principle way distinguish a good action space from bad action space in NAS? Is it possible to learn an action space such that it can best fit the performance metric to be optimized?
LEARNING LATENT ACTIONS
In this section, we describe LaNAS, which comprises two phases: (1) learning phase, and (2) search phase. Fig. presents high level description of LaNAS, of which the corresponding algorithms are further described in Alg
3.1 LEARNING PHASE
In the learning phase at iteration we have a dataset D2 [(a,, v1) obtained from previous explorations. Each data point (a,, v.) in D, has two components: a, represents network attributes (e.g., depth, number of filters, kernel size, connectivity, etc) and v; represents the performance metric estimated from training (or from pre-trained dataset such as NASBench-1011 Our goal is to learn good action space from D, to guide future exploration as well as to find the model with the desired performance metric efficiently.
Starting from the entire search space Ω the learnt actions recursively (and greedily) split it into smaller regions such that the estimation of performance metric becomes accurate. This helps us prune away poor regions as soon as possible and increase the sample efficiency of NAS.
In particular, we model the recursive splitting process tree. The node corresponds the entire model space Ω while each tree node j corresponds to region 22 (Fig. I]. At each tree node we partition 22 into disjoint regions 22 UkE(g) such that on each child region Qg, the estimation of performance metric V(Qe)) is the most accurate (or equivalently, has lowest variance).
3

---

Under review as a conference paper at ICLR 2020
At each node j. learn classifier that embodies latent action to split the model space Qz- The linear classifier takes the portion of the dataset that falls into its own region De n n. The performance of region f2 ((22), is estimated by 1/N Lie Dt. To minimize the variance of ((Q+) for all child nodes, we learn linear regressor ʃj that minimizes LiED,na, (f)(a)) - uu)². Once learned, the parameters of fj and (S2,) form a linear constraint that bifurcates 22 into a good region (> ()2)) and bad region (s ((2g)) for sampling. For convenience, the left child always represents the good region. The partition threshold ((2)), combined with fz. forms two latent actions at node j. going left (a.) > V ((2z)) and going right (fy (a.) S (S2,))
Note that we need to initialize each node classifier properly with few random samples to establish initial boundary in the search space. An ablation study on the number samples for initialization provided in Fig. 7
3.2 SEARCH PHASE
Once actions are learned, the search phase follows. The search uses the learned actions to sample more architectures a as well as their performance v. and store (a,, U;) in dataset D, to refine the action space in the next learning phase. Note that in the search phase, the tree structure and the parameters of those classifiers are fixed and static. Instead, the search phase learns to decide which region f2 on tree leaves to sample a, with proper balance between the exploration of less known Q2 and exploitation of promising 22-
Following the construction of the classifier at each node, trivial go-left greedy based search strategy can be used to exclusively exploit the most promising 94 defined by the current action space. However, this is not good strategy since it only exploits the current action space, which is learned from the current samples and may not optimal. There can good model regions that are hidden in the right (or bad) leaves that need to be explored.
In order to overcome this issuc, we use Monte Carlo Tree Search (MCTS) as the search method, which has the characteristics of adaptive exploration, and has shown superior efficiency in various tasks. MCTS keeps track of visiting statistics at each node to achieve the balance between exploitation of existing good region and exploration of new region. In lieu of MCTS, search phase also has select, sampling and backpropagate stages. LaNAS skips the expansion stage in regular MCTS since the connectivity of our search tree is static. When the action space is updated, previous sampled networks and their performance metrics in D; are reused and redirected to (maybe different) nodes in initializing visitation counts n(s) and node values v(s). When there is no learned action space, we random sample the model space to get jump started.
Algorithm 1: LaNAS search procedure.
Algorithm Subroutines in Alg.
Data: specifications of the search domain Function get ucb (Xneatt Thert Tourt! 0.5
Function ref_constraints (s pa_phth)
constraints=
for node E s_path do W,b mode-.. (aallgg-pramm()) (), X node.
return Kaexi 20//
(log(Reur)) if Nnent *
Rnezt
Anezt
if node on left then constraints. add Wa + b X) else constraints. (aadr Wa + X)
else +00
begin
while target do
for E Tree.N do n.g.train()
return constraints
7 Function uob_select (c= (r=root)
8 path =
for i :ori=1- 1 #sclects do
leaf,path = ucb sclect(root) constraints
while not leaf do path.add(c)
10
get_ pol_constraintsppuhh
luos = = -ett_ucb(clefft.x c.eettn, c.n), Fuch get pet_ucb(c.rggtt... c.right. c.n)
11
network =
sanpplingcconsstraintt))
12
acc network.troint
12
if luco > Fucs then c c.left else c= c.right
13
back - propagate(netwwork acc)
return path,
4

---

Under review as a conference paper at ICLR 2020
3.3 LANAS PROCEDURES
Learning phase: (Alg.1 line 6 + 7) the learning phase is to train fa at every node j. With more samples, f becomes more accurate, and ((22)) becomes closer to (22z). However, as MCTS biases towards selecting good samples, LaNAS will zoom into the promising hyper-space to further improve the sample efficiency. We provided an analysis of such search dynamics in Fig. 4
Search phase: (Alg.1 1 line 8 + 13) the search phase consists of major steps. 1) select w.r.t UCB: the calculation of UCB follows the standard definition in AAurr al. (2002). We present the equation of TUCB in Fig. 3 The input to TUCB is the number of visits of current node n(s) and next nodes n(ss, a), and the next node value v(s, a), where s stands for a node, and a stands for an action. Therefore, the next node is deterministic given 8 and a. At node j, the number of visits n(s) is determined by the number of samples in D, n S2,, while v(s) is determined by ((2)). The selecting policy Tuce takes the node with the largest UCB score. Starting from root, we follow Tach to traverse down to leaf (Alg. 3 line 7-13). 2) sampling from leaf: the select traverses path from the root to leaf, and each node in the path carries a linear classifier, W. a; + b, = e(s). If the path goes to left child, i.e. W. a, a,+ bg 2 u(s), ag E S2 and < v(s) otherwise. If the original model space is convex, then any selected path corresponds to several linear constraints and thus defines a convex polytope. Sampling in polytope is known be efficient using Gibbson sampling (Bishop] 2006 or hit-and-run sampler (Smith, 1996). While our implementation uses Gibbson sampling, other method also available (c.g., hit hit--nnd-rut LaNAS back- pack-propagates the reward, i.e. accuracy, to update the node statistics n(s) and u(s). It also back- proppaaasss the sampled network so that every parent node j keeps the network in D, n S2 for training.
3) back-propagate reward: after training the sampled network,
3.4 RELATIONSHIP TO OTHER BLACK-BOX OPTIMIZATIONS
Bayesian Optimization (BO). Bayesian Optimization is popular method for black-box optimiza-
tion (Snoek et al. 2012 2015 Wang et al. 2013 Gardner et al., 2014). While BO only uses fixed kernel which makes it harder to adapt to function with uneven smoothness, LaNAS uses MCTS and online action space learning to dynamically adapt itself towards the important region of the space, and thus achieves better performance in the presence of decent amount of samples is available.
Sequential Model-based Global Optimization (SMAC).SMAC (Hutter et al. 2011 is a generic black box optimization framework when function evaluation is expensive. SMAC (summarized in Appendix A.3) approximates the expensive evaluation with predictions from surrogate model é, and proposes the next sample by optimizing an acquisition function (S) on the search space P using Φb LaNAS can be viewed as an instantiation of SMAC framework, but overcomes substantial computational difficulties at different stage. In NAS, the architecture space is huge (~ 10 and taking ar gmazzeenn 6x) is hard with conventional approaches. Prior works have focused on combining the landscape information of acquisition function with Evolutionary A Algorithm (EA) to maximize S(a, Φt) (Bergstra al., 2011 Kandasamy al. 2019 Hansen, 2006), as will show in Fig. b))C), the high dimensional 32 in NAS is too large for EA to work well. The contribution of this work is to propose a new search model that utilizes regression tree as a surrogate model and MCTS as the acquisition function. Instead of solve an optimization every iterations, the tree surrogate learns to partition f fai), i E Ω to pinpoint the promising region for the MCTS acquisition function, and it becomes more accurate as the search progresses as shown by Fig. 4 thereby more efficient.
Regression/Decision Tree.LaNAS is similar Decision/Reegression tree that recursively splits the data into smaller and smaller bins, and makes decision/ppediction at the leaves. While deci- sion/regression tree does it in one shot, LaNAS augments it with online components (e.g., exploration with MCTS, retraining splitting function). As result, LaNAS is able to drive itself towards interesting regions that initial samples do not touch.
5

---

Under review as a conference paper at ICLR 2020
leftmost leaves: 15, 16
10
0.03
rightmost leaves: 28, 29 noda15
Dat 1
Divergence
8, 7
0.02
probabilty distribution
nods
Pj p/(acc)
P) (acc)
4- 07" mp]
0.01
5000 semples
0.00
node28
93
94
92
node29
P) (acc)
at 700 samples
10:14
P] (acc)
o). 1,
200 semples
2000
4000
6000
8000
1000d
90 accuracy
samples
(a) Search dynamics: KL-divergence and mean distance
(b) Search dynamics: sample distribution vs. dataset distribution
Figure 4: Evaluations of search (ynamics:(a) KL-divergence of Pj and Pł dips and bounces back. 80 continues grow, showing the average metric e over different nodes becomes higher when the search progresses. (b) sample distribution Pj approximates dataset distribution př when the number of samples E [200, 700]. The search algorithm then zooms into the promising sub-domain, as shown by the growth of ūy when n E [700, 5000).
EXPERIMENT
We performed extensive experiments on both offline collected benchmark datasets (c.g.. NAS- Bench Ying et al. (2019)) and open search domain to validate the effectiveness of LaNAS.
4.1 ANALYSIS OF SEARCH ALGORITHM
We analyze LaNAS by looking into the dynamics of sample distributions on tree leaves during the search. We used NASBench- 101 in experiments to form constrained search space that contains 420K models. NASBench-Ie 101 provides us with the true distribution of model accuracy, given any subset of model specifications, or equivalently collection of actions (or constraints). By construction, left nodes contain regions of the good metric while right nodes contain regions of the poor metric. Therefore, each node j. we can construct reference distribution pz (v) by training toward the entire dataset to partition the search space into small regions with concentrated performances on leaves. We compare pj (v) with the estimated distribution P (v), where n is the number of accumulated samples in Dj n S2 at the node j. Since the reference distribution p1 (v) is static, comparing p) (v) to pf (v) enables us see the variations of 92 on tree leaves w.r.t the growing samples. To provide quantitative view, we also calculated the KL-divergence DKLPp [IIpā]. and their mean value 0j = Egg [u] and E,- Egg [o).
In our experiments, we use complete binary tree with the height of 5. We label nodes 0- 0-14 as internal nodes, and nodes 15-29 leaves. By definition, Vis Vi.... > Big reflected by 16,28,0 in Fig. 4p. At the beginning of the search (n 200 for random initialization), Pi6, are expected to smaller than Pis.16. and p2s, 20 are expected to be larger than Pis. because the tree still learns to partition at that time. With more samples (n 700), Pj starts to approximate 700
Př. manifested by the increasing similarity between 115, 28.29 and Pic.10,28 28,8,,88,88 29. and the decreasing DEL in Fig. 4.. This is because MCTS explores the under-explored regions. As the search continues (n + 5000), LaNAS explores deeper into promising regions and p" is biased toward the region with good performance, deviated from pj. As a result, D bounces back in Fig. 4h. The mean 700,5000 P16
accuracy of P1s successfully minimizes the variance of rewards on search path making architectures with similar metrics concentrated in region, and LaNAS correctly ranks the regions on tree leaves. These search dynamics show how our model adapts to different stages during the course of the search, and validate its effectiveness for the purpose of searching.
700,5000 Puss
700,5000
700,5000 in Fig. 4/b indicates that LaNAS P22
4.2 PERFORMANCE ON NAS DATASETS
Evaluating on NAS Datasets: We use NASBench-101 (Ying al. (2019) one benchmark that contains over 420K NASNet CNN models. For each network, it records the architectures and their accuracy for fast retrieval by NAS algorithm, avoiding time-consuming model retraining. In addition, we construct two more datasets for benchmarking, ConvNet-60K (60K plain ConvNet models, VGG- style, no residual connections, trained on CIFAR-10) and 10T (10K LSTT cells trained on

---

Under review as a conference paper at ICLR 2020
LaNAS: Cp =011, init 10, select= 10
LaNAS:
Cp 0.1, Init = 10, select= 10
LaNAS: Cp
10, Init 10, select
60.8
the cureent bast atc.
0.940
50g
250
best gel
60.7
current best
0.750
0.935
0.725
60.5
100
0.930
Neces Artkiatto Caker (4
0.700
60.4
SMAC don Farcu Facton Canmanorri))
0.675
0.920
10
16
30
0.650
LIMM
10
sample
sample
sample
10000
Hoarples to glbba aptrnel
400000
Pomplee to glaba bptims
60000
Aoamooea globoll optinal
8000
200000
200000
4400
100000
20000
2000
Rondor 6E
MCTS
N6O
30
27
LaNAG
Rawion RE MCTS MA
GMAdd THE
LSNAS
(a) NASBench-420K large
(b) ConvNet-60K, medium
(c) LSMM-10K, small
NASBench, ConvNet-60k and LSTM-10K Each search algorithm is repeated 100 times on each datasets with different random seeds. The top row shows the time-course of the search algorithms (current best accuracy with interquartile range), while the bottom row illustrates the number of samples to reach the global optimum. NASBench-420K limits the edges S and LSTM-10K limits the edges 9, rendering huge number of architectures untrained in the search space. We compared to SMAC and TPE on ConvNet-60k as ConvNet-60k contains the accuracy of all the architectures in the search space,
Figure 5: Evaluations of sample-efficiency
PTB) to further validate the effectiveness of LaNAS. In each task, we perform an independent search for 100 times with different random seeds. The mean performance, along with the 25th and 75th percentile, is shown in Fig 5)
compare LaNAS with a diverse types of search algorithms, from Random Search, gradient based NAS, evolutionary algorithms, to Monte Carlo Tree Search (MCTS), and with a strong focus on Bayesian Optimization. Random Search finds the global optimum in expected n/2 samples. Regularized Evolution (Real et al. (2019) ) is type of evolutionary algorithm that achieves SoTA performance for image recognition. Our implementation of Regula aarilaiii zed Evolution on is from NASBench- 10 We used AlphaX as our MCTS implementation. It adopts manual action space that incrementally builds up a network, and the predictions set to per rollout. Neural Architecture Opt imi zat ion (NAO) (Luo et al. (2018) is gradient based NAS method that finds the architecture on performance predictor in a continuous embedding space with gradient descent. We adopted NAO from its public release" at Regression Tree removes MCTS from LaNAS, and RT always sample from the most promising node. Bayesi Optimi zat on (RO) is competitive method for the black box optimization. We implemented Bo that used Gaussian Process as the surrogate model and Expected Improvement (EI) as the acquisition function based on h However, the vanilla BO suffers from the scaling issue that incurs O(n²) cost, where n is the number of samples. To mitigate this issue, we apply BO on collected samples using a similar strategy to SGD that splits the entire samples into batches, then iteratively fits BO at batch size of 2000 for 2 epochs on NASBench-4200 and ConvNet-60ks We also compared LaNAS to other BO variants that does not have the cubic scaling issue such as TPE (Bergstra et al.) (201 from HyperOpt [ and SMAC-random forest (utter et al. (2013)) from SMAC Additionally, we
Baselines:
compared the latest BO package Dragonfly (Kandasamy et al. 2019 Since Dragonfly is too
expensive to collect 10 samples, we only compared to Dragonfly in Fig (b)).
"hargs//gthhaa.com/yyrrrrrryngg "htpps//githu..cco

---

Under review as a conference paper at ICLR 2020
the current best arc
0.775
the -ucceeee beedt axd
-0.440
0.7%
0.23%
6.5%
0.750
20-3
10
100%
0.935
gap best
0.725
oce to the
0.930
0.700
50
60
20-1
0.675
Prman Commaneeii UnM
0.925
heman maten TPC)
0.650
200
400
0.920
250
500
750
1000
200
50
200
sample
sample
sample
sample
(a) ConvNet
(b) NASBench-Node6
(c) optimize acquisition with TPE
(d) optimize acquisition with RE
Figure 6: (a-b) Comparing LaNAS to several mainstream BO methods: though BO and TPE works well when samples E [0, 200] on ConvNet and when samples E [0, 500] on NASBench- Node6 (a subset NASBench containing 62010 6-nodes networks), LaNAS quickly dominates the performance afterwards. This highlights the different focuses of LaNAS and BO methods. (c- diillustrations of the limitation of BO methods: optimizing the acquisition function with Tree Parzen Estimator (TPE) and Regularized Evolution (RE) using different budgets, that represent the max number of queries to a surrogate model in optimizing the acquisition. We denote the budgets as the percentages of ConvNet dataset.
Analysis of Results: Fig. 5 demonstrates that LaNAS consistently outperforms the baselines by significant margins on three separate tasks. Particularly, on NASBench, LaNAS is on average using 37x, 21.7x, 19.3x, 10.7x, 25.6x fewer samples than Random Sea rch, eegularizen Evolution, MCTS, NAO and Bayes iinnnann aptimization to find the global optimum. On ConvNet-60K, LaNAS used 12.3x, 16.5x and 25.3x fewer samples than TPE, SMAC-randon forest and our relaxed BO. On LSTM, LaNAS still performs the best despite that the dataset is small. Additionally, LaNAS is 2.3x, 5.4x, 1.8x faster than Regress ion Tree on NASBench, ConvNet and LSTM, demonstrating the effectiveness of MCTS to LaNAS. The substantial speedup w.r.t MCTS that uses a fixed action space also validates the effectiveness of learned actions.
To highlight the different focuses of BO methods and LaNAS, we also compared the first 500 samples on ConvNet-60K and the first 1000 samples on NASeench-Node6. NASBench-Node6 is subset of NASBench that contains networks with nodes=6. Since edges in NASBench <. 9, NASBench- have most networks trained in the search space. Fig. iiddicates and TPE and BO (no relaxation) are fast in the first few hundreds samples, but LaNAS quickly catches up afterwards. This indicates BO and TPE give good results under limited budget, while LaNAS intends to find the global optimum in the least samples.
In LaNAS, the action space is learned so that in each node, the representing search space can be partitioned into a separate good/had region using linear classifier based on the network attributes (e.g., depth/ of the network). With the learned action space, the resulting search space clearly separates good/bad regions, and the search is biased towards the regions that contain better archi- tectures, therefore becoming more efficient. Besides, with more samples, Fig. 4 shows LaNAS zooms in the promising regions pinpointing more promising regions to further improve the efficiency. Random Search gives poor performance, in particular in a large search space like NASBench. Regularized zed Evolut ion utilizes static exploration strategy that maintains pool of top 500 architectures for random mutations, which is not guided by previous search experience. BO is worse than LaNAS on NASBench and ConvNet due to our training relaxation. Though Bayes i an Optimi commization (BO) (no relaxation) shows slightly worse performance than LaNAS small LST,-10K, maximizes the acquisition on the entire search space which is not possible for high dimensional NAS problem that typical search space contains over 10"7 samples. To show the influence from the quality of acquisition maximization, we also upgraded the vanilla BO to maximize the acquisition function with Regularized Evolution and TPE. The baseline is the case that using the surrogate to predict all (100%) the architectures in the search space, as in the vanilla BO on LSTM. Fig. 6 (-d) shows the apparent performance deterioration after reducing the optimization budget. Please noted evaluating 0.01 % or 1003 architectures in the search space is still not practical for NAS.
4.3 PERFORMANCE ON OPEN DOMAIN SEARCH
To be consistent with existing works, also evaluated LaNAS on the NASNet open search domain.
Search space: Our search space is consistent with the widely adopted NASNet (Zoph et al. (2018)) The operations are 3x3, 5x5 and 7x7 max pool, 3x3, 5x5, 7x7 depth-separable cony, 1x1 convolution
8

---

Under review as a conference paper at ICLR 2020
Table 1: Results on CIFAR-10, c'o is cutout.
Table 2: Results on ImageNet (mobile setting)
Model
Filters
Params
Topl err
M
GPU days
Model
FLOPs
Params
top1 / topS err
NASNet-Ascl
32
3.3 M
2.65
20000
2000
NASNet-A
7oph ct al.
2018
564M
5,3 M
26.0/8.4
AmoebaNet- BouebaNet-Beelo
36
2.8 M
2.55++0.05
27000
31.50
NASNet-B
Zaph cl a.
2018
488M
5.3 M
27.7
PNASNet-5
48
3.2
+0.00
1160
225
NASNet-C
Zoph (2)8))
558M
4.9 M
27.5/9.0
NAO
36
10.6 M
3.18
1000
200
AmoebaNet-A
[Keal et ml
2018
555M
5.1 M
25.5/8.0
ENAS+c/o
4.6 M
2.89
0.45
AmoebaNet-B
Real al.
2018
555M
5,3
26.0/8.5
DARTS+clo
36
3.3 M
2.7610.00
1.5
AmorbaNNt-CC
Real al.
2018
570M
6.4 M
24.3/7.6
BayesNAS+clo
2.81 04
PNASNe-
Lau all
25.8.88.1
ASNG-NAS+clo
32
3.9 M
2.83+0.14
0.11
DARTS
(Liu eurera at
201 Kb
574M
4.7 M
26.7/8,7
FBNet
ear
2211
375M
5.5 M
25.1
LaNet
32
3.2 M
3.13 03
803
150
RandWire
WS
(019
583M
5.6
25.1/7.8
LaNet-clo
32
3.2 M
2.53
803
150
BayeaNAS
Zhou ot a.
2019
3.9 M
26,5
NAO+clo
128
128.0 M
2.11
1000
200
LaNet
570M
5.1 M
25.0/7.7
AmoebaNet-Beed Beooo
128
34,9 M
2.13
27000
3150
LaNot-olo
128
38.7 M
1.99
803
150
M: nimher of samples selected.
18514
Issaples to global optmaal
Patrcee ts glopol sptiuum
14000
0.9435
tree height
36000
15000
12400
the qurrent best acc
0.9430
30000
12500
92800
24000
10000
0.9625
Ink=0
int=100
18000
7000
in0=200
12000
5000
+000
0.9620
2n002000
4n0-400
100 200 300 400
0.005
8:06
0.9415
0
20000
40000
#select
In sample
(a) tree height vs. #select, -0.
(b) choice of classifier (c) performance at different C
(d) #samples for init
Figure 7: Ablation study: (a) the effect of different tree heights and #select in MCTS. Number in each entry is #samples to reach global optimal. (b) the choice of predictor for splitting search space, (c) the effect of C in UCB toward the performance on nasbench. (d) the effect of #samples for initialization toward the search performance.
and identity. The number of nodes within a cell is 7, and we constructed the network by stacking cell 6 times. Existing works in NAS tends to have very different sizes of search space according to Table.3 in |Radosavovic et al. (019). Though we follow NASBench- 101 and PNAS to share the normal and reduction cell in constructing the network, our search space contains 4.36 1017 architectures, which is decent large for evaluations.
During the search phase, we set filters to 32 and pre-trained an architecture for 120 epochs. Then we selected top-20 architectures collected from the search, and re-trained them for 600 epochs to acquire the final accuracy Table. We reused the training logic from DARTS and their training settings. The height of search tree is 8; we used 200 random samples for the initialization, and #select = 50.
Experiment setup:
Table. I compares our results in the context of searching NASNet style architecture on CIFAR-10. 10. We found the best performing architecture (LaNet) at the 803th sample. LaNet demonstrates an average accuracy of 97.4 97.47% (#filters 32, #params 3.22M) and 98.01% % (#filters 128, #params 38. 38.7M), which is better than all existing NAS-based results on CIFAR-10. It is worth noting that we achieved this accuracy with 33x fewer samples than AmoebaNet. Though one-shot learning methods, e.g. Liu et al. (2018b); Zhou et al.] (2019); Akimoto et al. 2019). and their weight sharing variants, e.g. Pham et al. (2018). exhibit weaker performance, they render much lower search costs for greatly reducing network evaluation costs with techniques such as transfer learning or approximating final weights with only training iteration. Fig. 5 indicates the search model is cheap to run, but evaluating networks during the search costs the majority of GPU days. Both NAO and ENAS show that weight sharing has greatly sped up network evaluations; our approach can also benefit from weight sharing to reduce the end-to-end search time. On the other hand, one shot learning methods show small difference to LaNAS in accuracy, e.g. -0.8%. at much less cost. However, as suggested in Fig. 5 almost 99.9% search costs, i.e. samples, is at improving the last 1% accuracy. Therefore, one-shot learning is fast to yield a reasonable result, while LaNAS aims at giving the best accuracy with the fewest samples.

---

Under review as a conference paper at ICLR 2020
4.4 TRANSFER LEARNING
cifar100 aczuracy
50.0
Improvement
W7.
Transfer LaNet to ImageNet:
Transferring the best performing architecture (found through searching) from CIFARIO 10 to ImageNet has al- ready been a standard technique. Following the
0.0
72.9
20.0
mobile setting (Zoph et al. (2018)), Table. 2 shows that LaNet found on CIFAR-1O, when transferred to ImageNet mobile setting (FI.OPs are constrained under 600M), achieves compet- itive performance.
% dataset used transfer learning
nendom search
Inmoceered addame
from CIFAILO
(a) intra-task transfer
(b) inter-task transfer
Figure 8: Latent actions transfer: learned la- tent actions can generalize within the same task or across different tasks, further boost search efficiency.
Intra-task latent action transfer: We learn ac-
tions from subset (1%, 5%, 10%, 20% 60%) of NASBench and test their transferability to the remaining dataset, as shown in Fig. 8a Interestingly, the improvement remain steady after 10%. Consistent with Fig. is enough to use 10% of the samples to learn the action space.
Inter-task latent action transfer: We compare 100 architectures selected by LaNAS from see 4.3 (on CIFAR10) with 100 random trials. Networks are trained for 100 epochs on CIFAR-100 and their performances are compared. Fig. 8b indiccattes that inter-task action transfer is also beneficial.
4.5 ABLATION STUDIES
The effect of tree height and #selects: Fig. 7a relates tree height (f) and the number of selects (#selects) to the search performance. In Fig. each entry represents #samples to achieve optimality on NASBench, averaged over 100 runs. A deeper tree leads to better performance, since the model space is partitioned by more leaves. Similarly. small #select results in more frequent updates of action space allowing the tree to make up-to-date decisions, and thus leads to improvement. On the other hand, the number of classifiers increases exponentially the tree goes deeper, and small #selects incurs frequent learning phase. Therefore, both can significantly increase the computation cost.
Fig 7b shows that using linear classifier performs better than an multi-layer perceptron (MLP) classifier. This indicates that adding complexity to decision boundary of actions may not help with the performance. Conversely, performance can get degraded due potentially higher difficulties in optimization.
Choice of classitiers:
#samples for initialization: We need to initialize each node classifier properly with a few samples to establish the initial boundary in the search space. As shown in Fig 7d cold start is necessary (init > 0 better than init = 0). Also, small ini==100-400 converges to top 5% performance much faster than init=2000, while init=2000 gets the best performance faster (Fig. 7d).
The effect of e in UCB: Fig. 7c shows that the exploration term, 20
2log(nourt)
improves the
Bnezt
overall performance
increases from 0 0.1, while using large c, e.g. 0.5 and 1, is not desired for over-exploring. Each values of c represents the LaNAS performance on NASBench in 100 runs. Please noted LaNAS is still the leading algorithm on NASBench even using a sub-optimum (e.g. C or 1). We find that setting e to 0.1 max(X) empirically works well on 3 datasets in Fig
FUTURE WORK
Recent work shared model (Luo et al. (2018); Pham et al. (2018) improves the training efficiency by reusing trained components from the similar previously explored architectures, e.g., weight sharing (Liu et al. (2018b) Luo et al. (2018): Pham al. (018)). Our work focuses sample- efficiency and is complementary to the above techniques.
To encourage reproducibility in NAS research, various of architecture search baselines have been discussed in /Sciuto et al. (2019); Li and Talwalkar (2019). We will also open source the proposed framework, together with the three NAS benchmark datasets used in experiments.
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. arXiv preprint arXiv: 1.Xiv:190500 0ee.119555.8555 2019.
Auer, Cesa- Desa-Bianchi, and Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47(2-3):235-22) 2002.
B. Baker, O. Gupta, N. Naik, and R. Raskar. Designing neural network architectures using reinforce- ment learning. arXiv preprint 161.v2:61..02666 2016.
Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for hyper--prameeee optimization. In Advances in neural information processing systems, pages 2546-2554, 2011.
C. M. Bishop. Pattern recognition and machine learning. Springer Science+ Business Media, 2006.
Y. Chen, T. Yang, X. Zhang, G. Meng, C. Pan, and J. Sun. Detnas: Neural architecture search on object detection. arXiv preprint arXiv: 10979, 2019.
R. Gardner, M. Kusner, Z. Xu, K. Q Weinberger, and P. Cunningham. Bayesian optimization with incquality constraints. In ICML, pages 937-945, 2014.
G. Ghiasi, T.-Y. Lin, R. Pang, and Q Le. Nas-fpn: Learning scalable feature pyramid architecture for object detection, arXiv preprint arXiv:1904.07392, 2019.
N. Hansen. The ema evolution strategy: a comparing review. In Towards new evolutionary computation, pages 75-102. Springer, 2006.
Hutter, H. H. Hoos, and K. Leyton-Brown Sequential model-based optimization for general algorithm configuration. In International conference learning and intelligent optimization, pages 507-523. Springer, 2011.
F. Hutter, H. Hoos, and K. Leyton-Brown, An evaluation of sequential model-based optimization for expensive blackbox functions. Proceedings of the 15th annual conference companion on Genetic and evolutionary compulation, pages 1209-1216. ACM, 2013.
K. Kandasamy, K. R. Vysyaraju, W. Neiswanger, Paria, C. Collins, J. Schneider, B. Poczos, and F. P. Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. arXiv preprint urXiv:/90333 06694, 2019.
L. Li and A. Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv: arXiv:1902..00 (902:9902.0033 2019.
C. Liu, B. Zoph, M. Neumann, J. Shlens, W. Hua, L.-J. Li, L. Fei-Fei, A. Yuille, J. Huang, and K. Murphy. Progressive neural architecture search, Proceedings of the European Conference on Computer Vision (ECCV), pages 19-34, 2018a.
C. Liu, L.-C Chen, F. Schroff, H. Adam, W. Hua, Yuille, and L. Fei-Fei. Auto-deeplab: Hierarchi- cal neural architecture search for semantic image segmentation. arXiv preprint 11X.:11911.0295, 2019.
H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. arXiv preprint 1806v 1805.0906..0 2018b.
R. Luo, Tian, T. Qin, E. Chen, and T.-Y. Liu. Neural architecture optimization. In Advances in neural information processing systems, pages 7816-7827. 2018.
M.-T. Luong, D. Dohan, A. W. Yu, Q L., B. Zoph, and V. Vasudevan. Exploring neural architecture search for language tasks. arXiv preprint vrXiv:1901.02985 2018.
C. Mallows, Letters to the editor. The American Statistician, 45(3):256-22) 2622, 1991. doi: 10. 1080/ 0003 305. 1991. 10475815.
11

---

Under review as a conference paper at ICLR 2020
R. Negrinho and G. Gordon. Deeparchitect: Automatically designing and training deep architectures. arXiv preprint arXiv: (et1::777408792,, 2017.
H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning, pages
2018.
1. Radosavovic, J. Johnson, S. Xie, W.-Y. Lo, and P. Dollár. On network design spaces for visual recognition. arXiv preprint arXiv: 13214 2019.
E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. Le, and A. Kurakin. Large-scale evolution of image classifiers. In Proceedings of the 34th International Conference on Machine Learning- Vollume 70, pages 2902-2911. JMLR. org, 2017.
E. Real, A. Aggarwal, Huang, and Q. V. Le. Regularized evolution for image classifier architecture search. arXiv preprint arXiv:/802.011 000.00188....8,,,... 2018.
E. Real, A. Aggarwal, Huang, and Q. V. Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4780-4789, 2019.
C. Sciuto, K. Yu, M. Jaggi, C. Musat, and M. Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint arXiv:1902.08142 2019.
R. L. Smith. The hit-and-run sampler: globally reaching markov chain sampler for generating arbitrary multivariate distributions. Proceedings of the 28th conference on Winter simulation, pages 260-264. IEEE Computer Society, 1996.
Snoek, H. Larochelle, and R. P. Adams. Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pages 2951-2959, 2012.
Snoek, O. Rippel, Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, M. Prabhat, and R. Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning. pages 2171-2180, 2015.
D. R. So, C. Liang, and Q Le. The evolved transformer. arXiv preprini arXi: 2019.
Wang, Zhao, Jinnai, Tian, and R. Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint
2019.
Z. Wang, M. Zoghi, Hutter, D. Matheson, and N. De Freitas. Bayesian optimization in high dimensions via random embeddings. In Twenty-Thirl International Joint Conference Artificial Intelligence, 2013.
B. Wu, X. Dai, P. Zhang, Y. Wang, F. Sun, Y. Wu, Y. Tian, P. Vajda, Y. Jia, and K. Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. arXiv preprint arXiv:1812.0344 2018.
Xie, A. Kirillov, Girshick, and K. He. Exploring randomly wired neural networks for image recognition. arXiv preprint arXiv: 1904.01599, 2019.
C. Ying, A. Klein, E. Real, E. Christiansen, K. Murphy, and Hutter. Nas-bench- 101: Towards reproducible neural architecture search. arXiv preprint arXiv: (etp:::92209.33 2019.
H. Zhou, M. Yang, Wang, and W. Pan. Bayesnas: bayesian approach for neural architecture search. arXiv preprint
2019.
B. Zoph and Q V. Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv: 16115787 2016.
B. Zoph, Vasudevan, Shlens, and Q. Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference computer vision and pullern recognition, pages 8697-8710, 2018
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 NAS DATASETS AND EXPERIMENT SETUP:
NAS dataset enables directly querying model's performance, e.g. accuracy. This allows for truly evaluating a search algorithm by repeating hundreds of independent searches without involving the actual training. NASBench- 101 Ying al. (201)) is the only publicly available NAS dataset that contains over 420K DAG style networks for image recognition. However, a search algorithm might overfit NASBench-101, losing the generality. This motivates us collect another 2 NAS datasets, one is for image recognition using sequential CNN and the other is for language modeling using LSTM.
Collecting ConvNNet60OK dataset: following similar set in collecting 1,364 networks in sec free structural parameters that can vary are: network depth D {1, 3, 4, 5,6, 7, 8), number of filter channels C = (32, 64, 96) and kernel size K = {3 x 3, 5 x 5). We train every possible architecture 100 epochs, and collect their final test accuracy in the dataset.
Collecting LSTM-10K dataset: following similar LSTM cell definition in Pham et al. (0188) we represent a LSTM cell with a connectivity matrix and a node list of operators. The choice of operators is limited to either fully connected layer followed by RELU or an identity layer, while the connectivity limited to 6 nodes. We randomly sampled 10K architectures from this constrained search domain, and training them following the exact same setup in Liu et al. (2018b). Then we keep the test perplexity as the performance metric for NAS.
A.2 OPEN DOMAIN SEARCH AND EXPERIMENT SETUP:
The best convolutional cell found by LaNAS visualized below. We constructed LaNet by stacking this cell 6 times. #arg min
correct
120p omnect
Hkp connect
sop 1107 363
A.3 SEQUENTIAL MODEL-BASED GLOBAL OPTIMIZATION (SMBO):
Algorithm 3: psudo-codes for Sequential Model-bases Global Optimization (SMBO).
INPUT: D, of collected samples, Ω search space, S acquisition function, & surrogate model 2 Function SMBO (f, Mo, S)
De + 0 for t t 1 do Srg (e) hard evaluate in NAS due large Q 4 expensive to general applications
evaluate f(a")
7
D441 Dj (a", (aa))
01+1 =ftt di on D
return/ D.
A.4 PARTITION ANALYSIS
The sample efficiency, i.e. the number of samples to find the global optimal, is closely related to the partition quality of each tree nodes. Here we seek an upper bound for the number of samples in the leftmost leaf (the most promising region) characterize the sample efficiency.
13

---

Under review as a conference paper at ICLR 2020
Assumption Civen search domain Q2 containing finte samples N, there exists a probabilistic density f such that P(a < b) - (v))d, where the performance of a network a.
With this assumption, we can count the number of networks in the accuracy range of [a, b] by N P(a S v b). Since E [0, 1] and 01)) < oc, the following holds (Mallows (1991))
EE Mo)l < ov
is the mean performance in Ω2 and M, the median performance. Note v [0, 1]. and let's denote = ( F.. Therefore, the maximal distance from e to M, is E + dui and the number of networks fo+eto f(u)do), denoted as 6. Therefore, the root partitions S2 into two sets that have S + 5 architectures.
falling between d and My N mar(S M, f(v)do, JM.
Theorem Given search tree of height h, the sub-domain represented by the leftmost leaf contains at most 8max (1 2x + N architectures, and 8max is the largest partition error from the node the leftmost path.
The theorem indicates that LaNAS is approximating the global optimum the speed of N/2h. suggesting 1) the performance improvement will remain near plateau as (verified by Fig 7a). while the computational costs (2 -1 nodes) exponentially increase; the performance improvement w.r.t random search (cost ~ N/2) is more obvious on a large search space (verified by Fig.5 (a)-xc)).
Proof Theorem: In the worst scenario, the left child is always assigned with the large partition; and let's s recursively apply this all the way down to the leftmost leaf h times, resulting in 8hh + 6h-1
8 8h-2
+
is related to and dss note 5 with more samples as 24 I 2 6mar 2h + 24
N
and o, becomes more accurate.
A.5 ORIGINAL FIG.5 IN LOG SCALE
current best 855
0.940
0.78
the Corrent besF gel
WCTS
Rande
0.935
best
60.6
SXn
0.930
Random
Begel Erolatonitet
0.74
RE
Random
NCTS
0.925
0.72
NA0
60.3
Labenn Actionct (N
0.920
10a
10a
0.79
10
10'
10a
60.2
10
10*
sample
ith sample
sample
(a) NASBench-420k. large
(b) ConvNet-60K, medium
(c) LSTM-10K small
Figure 9: previous Fig.5 in log scale.
14


Reviews:
[{"review_id": "rygGRaKpFB", "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": "In this paper, the authors propose a strategy for neural architecture search. The basic idea is effectively to model the accuracy of architectures in the search space, and use this model to select subsequent architectures with a MCTS-like procedure.\n\nOverall, my primary concern with the paper is a lack of context in the larger field of model based optimization. To be clear, the authors' method is clearly an instantiation of model based optimization. However, much of the paper is arguably written as though this needs to be invented from first principles. For example, much of section 3 is arguably a specific instantiation of the basic model based optimization loop, and much of the discussion on global versus sequential search exists in this literature as well.\n\nI believe the paper would be greatly improved by (1) providing this context, and (2) explaining the authors' approach within this context. Much of the discussion contrasting arbitrary action spaces with handcrafted ones are somewhat lost in the actual experimental setup: For example, the ConvNet-60K and LSTM-10K datasets have well specified parameter spaces. Beyond this, I'd like the authors to contrast the surrogate tree model used with simple CART trees: the fitting procedure in section 3.1 is quite similar to standard methods used to fit regression trees. \n\nAdditionally in the same context, a significant amount of related work is missing. The use of tree models for model based optimization have been considered before (e.g., SMAC), although the MCTS acquisition with a single tree surrogate is novel as far as I am aware. Other recent methods in model based optimization exist, including those with specific application to architecture search that explicitly outperform the basic Bayesian optimization algorithm (e.g. NASBot), and I'm therefore not sure if the comparison to the most basic instantiation of BayesOpt is appropriate. \n\nBeyond this, the experimental performance of the authors' method seems quite good on the tasks considered, and at least a substantial subset of the baselines considered are recent. I would therefore not be upset to see the paper published and would be willing to increase my score; however, I believe the framing of the paper needs substantial imrpovement.", "extra_scores": {"experience_assessment": "I have read many 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 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": {}}, {"review_id": "SklX1dlw9r", "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 introduces a Neural Architecture Search algorithm that attempts to solve the problems of the existing NAS only utilizing manually designed action space (not related to the performance). The paper proposes LaNAS which is based on an MCTS algorithm to partition the search space into tree nodes by the performance in the tree structure. The performance of the method is shown in the NASBench-101 dataset and Cifar-10 open domain search.\n\nI lean to reject this paper because (1) the motivation is not well justified by the experiments, (2) the comparison on NASBench-101 is not convincing, (3) some important explanation of the method is missing.\n\nMain arguments\nThe main contribution of the paper is using a learned action space in MCTS rather than a manually designed MCTS algorithm for NAS. However, as far as I know, the MCTS approach for the NAS problem is not a standard solution for NAS (which is not proved to be practically useful in other people’s papers) which diminishes the contribution of the improvements of MCTS in NAS.\n\nLack of the main comparison. For the motivation of the proposed method, the authors mention the drawbacks of other NAS methods used fixed action space in their RL or MCTS module. However, the authors only show that using a learned action space in MCTS is better than a fixed MCTS algorithm in the experiments. What about using a learned action space in the RL module such as PPO in NAS comparing to the fixed one?\n\nThe comparison of NASBench-101 is not convincing. The authors compared with the BO method and claimed that the method is 16.5x more efficient than BO. However, the recently released paper “BANANAS: Bayesian Optimization with Neural Networks for Neural Architecture Search” said that their method is 3.8x more efficient than the one proposed here, which is quite confusing.\n\nSome important explanation of the methods is missing. Throughout the paper, the method to sample from a leaf node is only mentioned in 3.3. However, the corresponding sampling method is unclear. The paper only mentions that MCMC has been adopted to sample from the target subspace. In my opinion, it is not so trivial to use MCMC here and should be elaborated in more detail. Otherwise, people cannot use it.\n\nAs given in figure 3, if c is set to be a very small number, the search is similar to simply using a series of predictors and always samples the models with better-predicted accuracies. Is MCTS really useful here? To show the effectiveness of MCTS, it is recommended to experiment on different values of c.\n\nResults given in the upper row of Fig.5 is not useful. In practice, it is already painful to sample about 1000 models and train them for the Cifar-10 dataset. It is more useful to see how this method behaves in the range of (0,1000). However, in Fig.5, different methods are all overlapping in this range and hard to tell whether this method is better than other methods\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 thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1e0K7nTqH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 describes a new neural architecture search method based on monte-carlo tree search that dynamically adapts the action space.\nThe methods consists of two stages. In the first stage, the learning stage, the action space is divided into good and bad regions based on a tree structure. In the seconds stage, new data is generated by sampling new architecture with monte-carlo tree search. Those two stages are iterated with new incoming data.\n\nThe paper proposes an interesting approach which achieves competitive results compared to state-of-the-art methods.\nIn general the paper is well written and easy to follow. However,  I haven't fully understood  how the model space is divided at different nodes. What exactly is the splitting criterium? Are the splits axis aligned?\n\nFurther comments:\n\n- Figure 4 a and b seemed to be flipped?\n\n- Figure 5 top row would be easier to parse if the x-axis is on a log scale.\n\n- Could you also include other Bayesian optimization methods, such as SMAC or TPE, which should competitive performance on NASBench101 and do not suffer from a cubic scaling\n\n\n\npost rebuttal\n------------------\n\n\nI thank the authors for performing additional experiments and clarifying my questions. First of all, I would like to stress that I still think the approach seems promising.\nHowever, I am not entirely convinced by the empirical results.  While the proposed method converges faster to the global optimum than other methods, it is only able to improve by a little epsilon in terms of validation accuracy,  which could indicate overfitting on these tabular benchmarks. Furthermore, in the beginning Bayesian optimisation based methods consistently perform better which might be in practice more relevant for these highly expensive optimisation problems.  Because of that, I keep my initial score. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an MCTS method for neural architecture search (NAS). Evaluations on NAS-Bench-101 and other datasets are promising. Unfortunately, no code is provided, which is very important in NAS to overcome the reproducibility crisis.

Discussion:
The authors were able to answer several questions of the reviewers. I also do not share the concern of AnonReviewer2 that MCTS hasn't been used for NAS before; in contrast, this appears to be a point in favor of the paper's novelty. However, the authors' reply concerning Bayesian optimization and the optimization of its acquisition function is strange: using the ConvNet-60K dataset with 1364 networks, it does not appear to make sense to use only 1% or even only 0.01% of the dataset size as a budget for optimizing the acquisition function. The reviewers stuck to their rating of 6,3,3.

Overall, I therefore recommend rejection. 
Decision: Reject