How Powerful are Performance Predictors in Neural Architecture Search?
Authors: Colin White
Arber Zela
Binxin Ru
Yang Liu
Frank Hutter
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural architecture search

Abstract: Early methods in the rapidly developing field of neural architecture search (NAS) required fully training thousands of neural networks. To reduce this extreme computational cost, dozens of techniques have since been proposed to predict the final performance of neural architectures. Despite the success of such performance prediction methods, it is not well-understood how different families of techniques compare to one another, due to the lack of an agreed-upon evaluation metric and optimization for different constraints on the initialization time and query time. In this work, we give the first large-scale study of performance predictors by analyzing 31 techniques ranging from learning curve extrapolation, to weight-sharing, to supervised learning, to zero-cost proxies. We test a number of correlation- and rank-based performance measures in a variety of settings, as well as the ability of each technique to speed up predictor-based NAS frameworks. Our results act as recommendations for the best predictors to use in different settings, and we show that certain families of predictors can be combined to achieve even better predictive power, opening up promising research directions. We release our code, featuring a library of 31 performance predictors.

How Powerful are Performance Predictors in Neural Architecture Search?
Colin White's Arber Zela², Binxin Ru², Yang Liu', Frank Hutter Abacus.A1, University of Freiburg, 3 University of Oxford, Bosch Center for Artificial Intelligence
Abstract
Early methods in the rapidly developing field of neural architecture search (NAS) required fully training thousands of neural networks. To reduce this extreme computational cost, dozens of techniques have since been proposed to predict the final performance of neural architectures. Despite the success of such performance prediction methods, it is not well-understood how different families of techniques compare to one another, due to the lack of an agreed-upon evaluation metric and optimization for different constraints on the initialization time and query time. In this work, we give the first large-scale study of performance predictors by analyzing 31 techniques ranging from learning curve extrapolation, weight-sharing, supervised learning, to zero-cost proxies. We test number of correlation- and rank-based performance measures in a variety settings, as well as the ability of each technique to speed up predictor-basee -baee NAS frameworks, Our results act recommendations for best predictors to use different settings, and we show that certain families of predictors can be combined to achieve even better predictive power, opening up promising research directions. Our code, featuring library of performance predictors, is available at wtthttt:/// thub. com/ wwtaaaattmmnnaaa htmm//ttmm//aaibbbbbbbb nasllib
Introduction
Neural architecture search (NAS) is popular area of machine learning, which aims to automate the process of developing neural architectures for given dataset. Since 2017, a wide variety of NAS techniques have been proposed [78 32 49]. While the first NAS techniques trained thousands of architectures to completion and then evaluated the performance using the final validation accuracy (78). modern algorithms use more efficient strategies to estimate the performance of
tartially-trained even untrained neural networks [11 2 54 34 38).
Recently, many performance prediction methods have been proposed based on training model to predict the final validation accuracy of an architecture just from an encoding of the architecture. Popular choices for these models include Gaussian processes (60 17 [T], neural networks [36] [54]
65 69 tree-based methods [33] 555, and so on. However, these methods often require hundreds of fully-trained architectures to be used as training data, thus incurring high initialization time. In contrast, learning curve extrapolation methods [1] 20 need little or no initialization time, but each individual prediction requires partially training the architecture, incurring high query time. Very recently, a few techniques have been introduced which are fast both in query time and initialization time [38] [], computing predictions based on a single minibatch of data. Finally, using shared weights 45 4 32] is popular paradigm for NAS 73 25]. although the effectiveness of these methods ranking architectures is disputed 3
76
Despite the widespread use of performance predictors, it is not known how methods from different families compare one another. While there have been some analyses on the best predictors within
[colin, Cabacus ai, {zelaa, 0h) uni freibure de, robingrobots. ox. ac uk
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Kendall Tau on NAS-Bench-201 CIFAR-10
Nodeloasedd
Deep Nata
SANANIAS
Extrapolation
XGBoond
NSBoost
LSBoost
Bayts
Treasr
GCN MIP
NAO SemmusS
BGHAMAANN
GP's
LESVVR
BaTT S
Eaily
Metrics
LGE
Edkea
Eary See LOWE
Rog.
Sparso GP
Crese
Van Sparee
Zero-coat Prosies
Weight
Guary time (seconal))
M.
Grasp
OmeShoo
Cov.
SynFFow
cime (Socunds)
Figure I: Categories of performance predictors (left). Kendall Tau rank correlation for performance predictors with respect to initialization time and query time (right). Each type of predictor is plotted differently based on whether it allows variable initialization time and/or variable query time. For example, the sixteen model-based predictors have fixed query time and variable initialization time, so they plotted as curves parallel to the X-Z plane.
each class 41 72). for many predictors, the only evaluation is from the original work that proposed the method. Furthermore, no work has previously compared the predictors across different families of performance predictors. This leads to two natural questions: how do zero-cost methods, model-based methods, learning curve extrapolation methods, and weight sharing methods compare one another across different constraints on initialization time and query time? Furthermore, can predictors from different families be combined to achieve even better performance?
In this work, we answer the above questions by giving the first large-scale study of performance predictors for NAS. We study 31 predictors across four popular search spaces and four datasets: NAS-Bench-201 [33 with CIFAR-10, CIFAR-100, and ( NAS-Bench-101 7 and DARTS 32 with CIFAR-IO, and NAS-Bench-NLP (2] with Penn TreeBank. In order give fair comparison among different classes of predictors, we run full portfolio of experiments, measuring the Pearson correlation and rank correlation metries (Spearman, Kendall Tau, and sparse Kendall Tau), across a variety of initialization time and query time budgets. We run experiments using a training and test set of architectures generated both uniformly random, as well as by mutating the tighest-perfoming encountered during an actual NAS run). Finally, we test the ability of each predictor to speed up NAS
architectures (the latter potentially more closely resembling distributions
algorithms, namely Bayesian optimization [6 54 69 51 and predictor-guided evolution [66] [59]
Since many predictors so far had only been evaluated on one search space, our work shows which predictors have consistent performance across search spaces. Furthermore, by conducting a study with three axes of comparison (see Figure []. and by comparing various types of predictors, more complete view of the state of performance predictor techniques that leads to interesting insights. Notably, we show that the performance of predictors from different families are complementary and can be combined to achieve significantly higher performance. The success of these experiments opens up promising avenues for future work.
see
Overall, our experiments bridge multiple areas of NAS research and act as recommendations for the best predictors to use under different runtime constraints. Our code, based the NASLib library (52). can be used as testing ground for future performance prediction techniques. In order to ensure reproducibility of the original results, we created table clarify which of the 31 predictors had previously published results on a NAS-Bench search space, and how these published results compared to our results (Table 7). We also adhere to the NeurIPS 2021 checklist along with the specialized NAS best practices checklist (3I).
Our contributions. We summarize our main contributions below.
We conduct the first large-scale study of performance predictors for neural architecture search by comparing model-basee methods, learning curve extrapolation methods, zero-cost methods, and weight sharing methods across a variety of settings.
We release a comprehensive library 31 performance predictors on four different search spaces.
We show that different families of performance predictors can be combined to achieve substantially better predictive power than any single predictor.

---

2 Related Work
NAS has been studied since at least the 1990s 19 58]. and has been revitalized in the last few years 778]. While initial techniques focused on reinforcement learning 178, 45 and evolutionary and predictor- based NAS algorithms 655 54 69
search 37 one-shot NAS algorithms [32 12
have recently become popular. We give a brief survey of performance prediction techniques in Section []] For survey on NAS, see [5]. The most widely used type of search space in prior work is the cell-based search space [79,, where the architecture search is over relatively small directed acyclic graph representing an architecture.
A few recent works have compared different performance predictors on popular cell-based search spaces for NAS. Siems et al. [55) studied graph neural networks and tree-based methods, and found that gradient-boosted trees and graph isomorphism networks performed the best. However, the comparison was only on a single search space and dataset, and the explicit goal was to achieve maximum performance given a training set of around 60 000 architectures. Another recent paper [41] studied various aspects of supernetwork training, and separately compared four modell-base methods: random forest, MLP, LSTM, and GATES [42]. However, the comparisons were again on a single search space and dataset and did not compare between multiple families of performance predictors. Other papers have proposed new model-based predictors and compared the new predictors to other model-based baselines 33 65 54 69]. Finally, recent paper analyzed training heuristics to make weight-sharing more effective at ranking architectures [72). To the best of our knowledge, no prior work has conducted comparisons across multiple families of performance predictors.
3 Performance Prediction Methods for NAS
In NAS, given search space A, the goal is to find a" = argmin where f denotes the validation error of architecture after training on fixed dataset for a fixed number of epochs E. Since evaluating (a) typically takes hours (as it requires training neural network from scratch), many NAS algorithms make use of performance predictors to speed up this process. A performance predicior I' is defined generally as any function which predicts the final accuracy or ranking of architectures, without fully training the architectures. That is, evaluating I' should take less time than evaluating f, and (a) a A} should idcally have high correlation rank correlation with {f(a) a E A}.
Each performance predictor is defined by two main routines: an initialization routine which per- forms general compuuaat,,,o, and a query routine which performs the final architecture-specifi computation: it takes as input an architecture specification, and outputs its predicted accuracy. For example, one of the simplest performance predictors early stopping: for any query(a). train a for E/2 epochs instead of E [77]. In this case, there is no general pre-computation, so initialization time is zero. On the other hand, the query time for each input architecture is high because it involves training the architecture for F/2 epochs. In fact, the runtime of the initialization and query routines varies substantially based on the type of predictor. In the context of NAS algorithms, the initialization routine is typically performed once at the start of the algorithm, and the query routine is typically performed many times throughout the NAS algorithm. Some performance predictors also make use of an update routine, when part of the computation from initialization needs to be updated without running the full procedure again (for example, in a NAS algorithm, a model may be updated periodically based on newly trained architectures). Now give overview of the main families of predictors. See Figure [[eft) for a taxonomy of performance predictors.
Model-based (trainable) methods. The most common type of predictor, the model-based pre- dictor, is based on supervised learning. The initialization routine consists of fully training many architectures (i.e., evaluating f(a) for many architectures a E A) to build training set of datapoints {a. fa)) Then a model f' is trained to predict fa) given a. While the initialization time for model- predictors is very high, the query time typically takes less than second, which allows thousands of predictions to made throughout NAS algorithm. The model is also updated regularly based on the new datapoints. These predictors are typically used within BO frameworks [36] 54]. evolutionary frameworks (66), or by themselves (67, to perform NAS. Popular choices for the model include tree-based methods (where the features are the adjacency matrix representation of
3

---

the architectures) B3 |5], graph neural networks [36 54 Gaussian processes 47 51 networks based on specialized encodings of the architecture 69
and neural
Learning curve-based methods. Another family predicts the final performance of architectures using only partially trained network, by extrapolating the learning curve. This is accomplished by fitting the partial learning curve to an ensemble of parametric models M.. or by simply summing the training losses observed so far [50]. Early stopping as described earlier is also learning curve-based method. Learning curve methods do not require any initialization time, yet the query time typically takes minutes or hours, which is orders of magnitude slower than the query time in model-based methods. Learning curve-based methods can be used in conjunction with multi-fidell fidelty algorithms, such as Hyperband or BOHB 27
24
Hybrid methods. Some predictors are hybrids between learning curve and model-based methods. These predictors train model initialization time to predict f(a) given both a and a partial learning curve of a as features. Models in prior work include an SVR (2). or Bayesian neural network 120] Although the query time and initialization time are both high, hybrid predictors tend have strong performance.
Zero-cost methods. Another class of predictors have no initialization time and very short query times (so-called "zero-cost" methods). These predictors compute statistics from just a single for- ward/backward propagation pass for single minibatch of data, by computing the correlation of activations within a network [38], or by adapting saliency metrics proposed in pruning-at-imitaaiizne literatures 23 Similar to learning curve-based methods, since the only computation is specific to each architecture, the initialization time is zero. Zero-cost methods have recently been used to warm start NAS algorithms T
Weight sharing methods. Weight sharing 45
is a popular approach to substantially speed up In this approach, all architectures
NAS, especially in conjunction with a one-shot algorithm 32 12 in the search space are combined to form a single over pher-parameterized supernetork. By training the weights of the supernetwork, all architectures in the search space can be evaluated quickly using this set of weights. To this end, the supernetwork can be used as a performance predictor. This results in NAS algorithms [32] 28 which are significantly faster than sequential NAS algorithms, such as evolution or Bayesian optimization. Recent work has shown that although the shared weights are sometimes not effective at ranking architectures [53 74 76), one-shot NAS techniques using shared
weights still achieve strong performance 773 25
Tradeoff between intialization and query time. The main families mentioned above all have different initialization and query times. The tradeoffs between initialization time, query time, and performance depend on a few factors such the type of NAS algorithm and its total runtime budget, and different settings are needed in different situations. For example, if there are many architectures whose performance we want estimate, then we should have low query time, and if we have high total runtime budget, then we can afford high initialization time. We may also change our runtime budget throughout the run of a single NAS algorithm. For example, the start of a NAS algorithm. we may want to have coarse estimates of a large number of architectures (low initialization time, low query time such as zero-cost predictors). As the NAS algorithm progresses, it is more desirable to receive higher-fun fideliyyyytty predictions on smaller set of architectures (model-based or hybrid predictors). The exact budgets depend on the type of NAS algorithm.
Choice of performance predictors. We analyze 31 performance predictors defined in prior work:
BANANAS (69,, Bayesian Linear Regression 66, BOHAMIANN [57]. BONAS [54] DNGO [56)
Early Stopping with Val. Acc. (c.g. 177 27 16 791) Early Stopping with Val. Loss. [50]. Fisher (
Gaussian Process (GP) 48). GCN (75). Grad Norm M. Grasp (44. Jacobian Covariance (38
LCE 11. LCE-m 20 LcSVR 2 LGBoost/GBDT 33 MLP 69. NAO 335 NGBoost 55
OneShot 73), Random Forest (RF) (55), Random Search with Weight Sharing (RSWS) [26] Sem-
iNAS [4], SNIP 23 SoTL [50]. SoTL-E [50], Sparse GP [3], SynFlow [1]. Variational Sparse
GP 633 and XGBoost (55) For any method that did not have an architecture encoding already
defined (such as the tree-based methods, Ga-based methods, and Bayesian Linear Regression), we use
the standard adjacency matrix encoding, which consists of the adjacency matrix of the architecture
along with one-hot list of the operations [7] 68 By open-sourcing code, we encourage

---

NAS-Bench-NLP
NAS BeSS-Bench220 ImageNet16 120
Kendall Tau on NAS Bench-201 CIFAR-10
(veconds)
Query time (recands)
22
42
42
20
42
23
22
Query time (seconds))
V
22
Int. time (seconds)
Init. time (seconds)
NAS-Dench-101
DARTS
(secomda))
Query time (seconds)
52
52
20
13
20
Init. time (seconds)
Init. time (seconds)
Init time (seconds)
BANANAS
Early Stop (Acc.)
Joceb. Cov.
LeSVR
SoTL-E
SynFlow
Bayes, Reg.
SemiNASS
XGBcest
The performance predictors with the highest Kendall Tau values for all initialization time and query time budgets on Bench-nnh.,, MAS--ench-IPe 101, NAS- Bench-NLP and DARTS. For example, on
Figure 2:
CIFAR- 10 (left) with an initialization time of 10 seconds and query time of 10 seconds, XGBoost achieves a Kendall Tau value of .73 which is the highest value out of the 31 predictors that tested that budget.
implementing more (existing and future) performance predictors which can then be compared the 31 which we focus in this work. In Section B.1 we give descriptions and detailed implementation details for each performance predictor. In Section D we give table that describes for which pre- dictors we were able to reproduce published results, and for which predictors it is not possible (e.g.. since some predictors were released before the creation of NAS benchmarks).
4
Experiments
We now discuss our experimental setup and results. We discuss reproducibility in Sections and and our code (based the NASLib library (52)) is available at htttps://github. com./btooommmmmmmmm naslibb We split up our experiments into two categories: evaluating the performance of each predictor with respect various correlation metrics (Section 4.1), D, and evaluating the ability of each predictor to speed up predictor-based NAS algorithms (Section We start by describing the four NAS benchmarks used in our experiments.
NAS benchmark datasets.
S-S-BBnch-100 71 consists of over 423 000 unique neural architec- tures with precomputed training, validation, and test accuracies after training for 4, 12, 36, and 108 epochs CIFAR-IO [71]. The cell-based search space consists of five nodes which can take any directed acyclic graph (DAG) structure, and each node can be one of three operations. Since learning curve information is only available four epochs, it is not possible
most learning curve extrap- olation methods on NAS-Bench- 101. NAS-Bench-201 [13 consists of 15 625 architectures (out of which 466 are unique after removing isomorphisms [3 Each architecture has full learning curve information for training, validation, and test losses/accuracies for 200 epochs on CIFAR- 10 [22). CIFAR-100, and ImageNet-16-120 [00] The search space consists of cell which a complete DAG with 4 nodes. Each edge can take one of five different operations. The DARTS search space 32 is significantly larger with roughly 18 architectures. The search space consists of two cells, each with seven nodes. The first two nodes are inputs from previous layers, and the intermediate four nodes can take on any DAG structure such that each node has two incident edges. The last node the output node. Each edge can take one of eight operations. In our experiments, we make use of the training data from NAS AAS-Bench-331 (55), which consists of 23 000 architectures drawn uniformly random and trained CIFAR-10 10 for 100 epochs. Finally, the
search space 21 is even
5

---

larger, at 10 LSTM-like cells, each with at most 25 nodes in any DAG structure. Each cell can take one of seven operations. In our experiments, we use the 14 000 architectures drawn uniformly at random and trained on Penn Tree Bank 40 for 50 epochs.
dataset, which consists of
Hyperparameter tuning. Although we used the code directly from the original repositories (some- times making changes when necessary adapt to significantly different levels of hyperparameter tuning. For example, some of the predictors had undergone heavy hyperparameter tuning the DARTS search space (used in MAS-Bench-3011 while other predictors (particularly those from 2017 or earlier) had never been run on cell-based search spaces. Furthermore, most rredector-based NAS algorithms the predictor periodically throughout the NAS algorithm. This is because the bottleneck for predictor- based NAS algorithms typically the training of architectures, not fitting the predictor [56] 30 16). Therefore, it is fairer and also more informative to compare performance predictors which have had the same level of hyperparameter tuning through cross-validation, For each search space, we run random search on each performance predictor for 5000 iterations, with a maximum total runtime of 15 minutes. The final evaluation uses a separate test set. The hyperparameter value ranges for each predictor can be found in Section B.2.
search spaces), the predictors had
utilize cross-validation to tune
4.1 Performance Predictor Evaluation
We evaluate each predictor based on three axes of comparison: initialization time, query time, and performance. We measured performance with respect to several different metries: Pearson correlation and three different rank correlation metrics (Spearman, Kendall Tau, and sparse Kendall Tau [72 55)).
The experimental setup is follows: the predictors are tested with 11 different initialization time budgets and 14 different query time budgets, leading to a total of 154 settings. On MAS--Bench-22 201
CIFAR-10. 10, the 11 initialization time budgets spaced logarithmically from 1 second to 1.8 x 10? seconds on a 1080 Ti GPU (which corresponds to training 1000 random architectures on average) For other search spaces, these times are adjusted based on the average time to train 1000 architectures. The 14 query time budgets are spaced logarithmically from 1 second to 1.8 x 10* seconds (which corresponds to training an architecture for 199 epochs). These times are adjusted for other search spaces based on the training time and different number of epochs. Once the predictor is initialized, we draw a test set of 200 architectures uniformly at random from the search space. For each architecture in the test set, the predictor uses the specified query time budget make a prediction. We then evaluate the quality of the predictions using the metries described above. We average the results over 100 trials for each (initialization time, query time) pair.
which is consistent with experiments conducted in prior work (65 69 34
Results and discussion. Figure CIFAR-IO over initialization time, query time, and Kendall Tau rank correlation. Of the 31 predictors we tested, we found that just seven of them are Parcto-optimal with respect to Kendall Tau, initial- ization time, and query time. That is, only seven algorithms have the highest Kendall Tau value for at least one of the 154 query iine/iniiialization time budgets on NAS-Bench-201 CIFAR-10. This can be seen more clearly in Figure 2 (left), which a view from above Figure [ each lattice point displays the predictor with the highest Kendall Tau value for the corresponding budget. In Figure 2 (right). we plot the Pareto-optimal predictors for five different dataset/search space combinations. In Section B33 we give the full 3D plots and report the variance across trials for each method. In Figure (left) we also plot the Pearson and Spearman correlation coefficients for NAS-Bench-201 CIFAR-T0. The trends between these measures performs better on the rank-based metrics. For the rest of this section, we focus on the popular Kendall Tau metric, giving the full results for the other metrics in Section B.3
D shows full three-dimensional plot for NAS-Bencht on
largely the same, although see that SemiNAS
We see similar trends across DARTS and the two PAS-Bench-200 datasets. MAs--Bnch--LPP also has fairly similar trends, although early stopping performs comparatively stronger. NAS-Bench- is different from the other search spaces both in terms of the topology and the benchmark itself, which we discuss later in this section.
In the low initialization time, low query time region, Jacobian covariance or SynFlow perform well across NAS BescBench-11 and NAS-Bench-200 However, none of the six zero-cost methods perform well on the larger DARTS search space. Weight sharing (which also has low initialization and low query time, as seen in Figure]] I]. did not yield high Kendall Tau values for these search spaces, either,

---

NAS Bench CIFAR 10
NA5 Bench-211 CIFAR-100
NAS Bench 201 Image/eet16
DARTS
Query time (xecords)
Query time (secondt))
-03%
Query time (soconds)
127
-92%
2005
5-60%
>120%
2130%
+102%
x120%
x92%
5110%
5-32%%
Query time
51.0%
+127%
.1.0%
time (seconds)
Init. (seconds)
Init time (secands)
Init. (seconds)
Figure 3: Percentage of OMNI's Kendall Tau value compared to the next-best predictors for each budget constraint.
which is consistent with recent work [53] 74 76.. However, rank correlation is not as crucial to
one-shot NAS algorithms as it is for black box predictor-based methods, as demonstrated by prior one-shot NAS methods that do perform well [25 73 32
28 12]. In the low initialization time, high query time region, sum of training losses (SoTL-E) consistently performed the best, outperforming other learning-cume curve based methods.
The high initialization time, low query time region (especially the bottom row of the plots, correspond- ing to a query time of second) is by far the most competitive region in the recent NAS literature. Sixteen of the 31 predictors had query times under second, because many NAS algorithms designed to initialize (and continually update) performance predictors that are used to quickly query thousands of candidate architectures. GCN and SemiNAS, the specialized GCN//emi-superviiel methods, perform especially well in the first half of this critical region, when the initialization time relatively low. However, boosted tree methods actually performed best in the second half of the critical region where the initialization time is high, which is consistent with prior work 33 (55) Recall that for model-based methods, the initialization time corresponds training architectures to be used as training data for the performance predictor. Therefore, our results suggest that techniques which can extract better latent features of the architectures can make up for a small training dataset, but methods based purely on performance data work better when there is enough such data.
Perhaps the most interesting finding is that KAS-Bench 101/201,, SynFlow which take three seconds each to compute, both outperform all model- methods even after 30 hours of initialization. Put another way, NAS algorithms that make use of model- predictors may be able to see substantial improvements by using Jacobian covariance instead of model-based predictor in the early iterations.
SynFlow and Jacobian covariance,
The Omnipotent Predictor. One conclusion from Figure is that different types of predictors are specialized for specific initialization time and query time constraints. A natural follow-up question is whether different families are complementary and can be combined to achieve stronger performance. In this section, we run proof-of-concepp to answer this question. We combine the best-performing predictors from three different families in a simple way: the best learning curve method (SoTL-E), and the best zero-cost method (Jacobian covariance), are used as additional input features for model-based predictor (we separately test SemiNAS and NGBoost). We call this method OMNI, the well as additional experiments
omnipotent predictor. We give results in Figure B and pseudo-code in Section B.4] In contrast to all other predictors, the performance of OMNI is strong across almost all budget constraints and search spaces. some settings, OMNI achieves a Kendall Tau value 30% higher than the next-best predictors.
The success of OMNI verifies that the information learned by different families of predictors are complementary: the information learned by extrapolating a learning curve, by computing a zero-cost proxy, and by encoding the architecture, all improve performance. We further confirm this by running an ablation study for OMNI in Section B.4 We can hypothesize that each predictor type measures distinct quantities: SOTL-E measures the training speed, zero-cost predictors measure the covariance between activations on different datapoints, and model-based predictors simply learn patterns between the architecture encodings and the validation accuracies. Finally, while we showed a proof-of-concept, there are several promising areas for future work such creating ensembles of the model-based approaches, combining zero-cost methods with model-based methods more sophisticated ways, and giving full quantification of the correlation among different families of predictors.
7

---

Pearson correlation
Spearman rank correlation
Kendall Tau on NAS Bench-201 CIFAR-10
Query tiree (seconds)
Early Stop (Acc.)
CCN
Jacob. Cov.
L:SVV
SeTt-r
Korbe
Gutte fand test teecomal
Not thee (seenedy
Init. time (seconds)
Init. time (seconds)
BANAMA
NNGO
SemiNAS
Sparse CP KGBocst
Fird Norm
teSvR
BOHAMIANK
SoTL
SNP
Stop
Bayes: Reg
Figure 4: The best predictors on MAS-Bench-201 CIFAR-10 with respect to Pearson (left) and Spearman (middle). Kendall Tau values from mutation-based training and test set (right).
NAS-Bench-101: a more complex search space. Figure 2 the plot for NAS-Bench. 101 looks significantly different than the plots for the other search spaces, for two reasons. The first reason is technical one: the NAS-Bench-IU 101 API only gives the validation accuracy at four epochs, and does not give the training loss for any epochs. Therefore, we could not implement SoTT or any learning curve extrapolation method. However, all sixteen the model-based predictors were implemented on MAS-Bench.
In this case, BANANAS significantly outperformed the next-best predictors (GCN and SemiNAS) across every initialization time. One explanation is due to the complexity of the NAS-Bench-10 101 search space: while all AAS-Bench-201 architectures have the same graph topology and DARTS architectures nodes have exactly two incoming edges, the NAS-Bench- 101 search space is much more diverse with architectures ranging from single node and no edges, to five nodes with nine connecting edges. In fact, the architecture encoding used in BANANAS, the path encoding, was designed specifically to deal with the complexity of the JAS-Bench- 101 scarch space (replacing the standard adjacency matrix encoding). To test this explanation, in Appendix [B] we run several of the simpler tree-based and GP-based predictors using the path encoding, and we that these methods now surpass BANANAS in performance.
mutation-based test set. The results from Figure 2 used a test set drawn uniformly at random from the search space (and the training set used by model-based predictors was also drawn uniformly random). However, neighborhood based NAS algorithms such as local search, regularized evolu- tion, and some versions of Bayesian optimization consider architectures which are local perturbations of the architectures encountered so far. Therefore, the predictors used in these NAS algorithms must be able to distinguish architectures which are local mutations of a small set of seed architectures.
We run an experiment which the test set is created by mutating architectures from an initial set of seed architectures. Specifically, we draw a set of 50 random architectures and choose the five with the highest validation accuracy seed architectures. Then we create set of 200 test architectures by randomly mutating up to three attributes of the seed architectures. Therefore, all architectures in the test set are at most an edit distance of three from a seed architecture, where two architectures are a single edit distance away if they differ by one operation or edge.
We create the training set by randomly choosing architectures from the test set and mutating one random attribute. As in all of our experiments, we ensure that the training set and test set are disjoint. (right) we plot the correlation results for NAS-Bench-201 CIFAR-I0. While the zero-cost
In F (right), and learning surve-based approaches have similar performance, the model-based approaches have significantly worse performance compared to the uniform random setting. This because the average edit distance between architectures in the test set is low, making it significantly harder for model-based predictors to distinguish the performance of these architectures, even when using a training set that is based mutations of the test set. In fact, interestingly, the performance of many model-based approaches starts to perform worse after 106 seconds. SemiNAS in particular performs much worse in this setting, and boosted trees have comparatively stronger performance in this setting.
8

---

Evol. NAS Framework, NAS-Rench-301 CIFAR10
Fvol. NAS Framework, NAS-Rench-J0: imagelie16-12 16-120
175
Valdetton enrrr (50
BANANAA
BONAS
Volidation entor
BOHAMANN
Bayes, Un. Reg.
L5 10
34"10
DNGO
593
NLF
LGBoost
35.9
NAO
Runtime (scconds)
Runtime (seconds)
RF
Sparse GP
B0 Framework, MAS Beec--enchhhh- 201 CIFARIO
B0 framework, MAS Bench-201 InageNert6-120
Sparse
55.09
XGBocst
$4.75
NGitoast
OMMENGRos))
2.4
SemiNes
8.25
OMMIScm/NASI
Volldetion
54.00
52.
52.9
39'
Runtime (saconds)
Runtime (seconds)
Figure 5: Validation error vs. runtime for the medictor-guided evolution framework and the Bayesian optimization predictor framework using different predictors.
4.2 Predictor-Based NAS Experiments
Now we evaluate the ability of each model-based performance predictor to speed up NAS. We use two popular predictorbbased NAS methods: the predictor- sradictoo-guided evolution framework [66 59 and the Bayesian optimization + predictor framework [17 36 [5]] The preiictorguided evolution framework an iterative procedure in which the best architectures the current population are mutated to create a set of candidate architectures. A predictor (trained on the entire population) chooses kt architectures which are then evaluated. In our experiments, the candidate pool created by mutating the top five architectures 40 times each, and we set k- = 20. For each predictor, we run predictor-guiis evolution for 25 iterations and average the results over 100 trials. The BO + predictor framework is similar to the evolution framework, but an ensemble of three performance predictors are used so that uncertainty estimates for each prediction can be computed. In each iteration, the candidate architectures whose predictions maximize an acquisition function are then evaluated. Similar to prior work, we use independent Thompson sampling [69, as the acquisition function, and an ensemble is created by using different ordering of the training set and different random weight initializations (if applicable) of the same predictor. In each iteration, the top 20 architectures are chosen from a randomly sampled pool of 200 architectures.
In Figure 5 we present results for both NAS frameworks on NAS-Bench-201 CIFAR-10 and ImageNet 6- 120 for the 16 model-based predictors. We also test OMNI, using its lowest query time setting (consisting of NGBoost Jacobian covariance), and another version of OMNI that replaces NGBoost with SemiNAS. Our results show that the model--ased predictors with the top Kendall Tau rank correlations in the low query time region from Figure 2 performance when applied for NAS: SemiNAS and NAO perform the best for shorter runtime, and boosted trees perform best for longer runtime. OMNI(NGBoosi) consistently outperforms NGBoost, and (MNI(SemiNAAS) often achieves top performance. This suggests that using zero-cost methods in conjunction with model-based methods is promising direction for future study.
also roughly achieve the best
4.3 So, how powerful are performance predictors?
Throughout Section 4 we tested performance predictors in a variety of settings, by varying the search spaces, datasets, runtime budgets, and training/test distributions. We saw largely the same trends among all of our experiments. Interesting findings included the success of zero-cost predictors even when compared to model-based predictors and learning curve extrapolation predictors with longer runtime budgets, and the fact that information from different families of predictors are complementary. When choosing a performance predictor for new applications, we recommend deciding on target initialization time and query time budget, consulting Figures 2 and o and then combining the best

---

predictors from the desired runtime setting, similar to OMNI. For example, if a performance predictor with medium initialization time and low runtime is desired for search space similar 201 or DARTS, we recommend using NGBoost with Jacobian covariance and SynFlow as additional features.
Societal Impact
Our hope is that work will have positive impact on the AutoML community by making it quicker and casier to develop and fairly compare performance predictors. For example, AutoML practitioners easily decide the performance prediction methods best suited to their application, rather than conducting computationally intensive experiments of their library to develop new performance
consult
experiments
own 43.. Furthermore, AutoML researchers prediction techniques and compare new methods to 31 other algorithms across four search spaces. level of abstraction away from real applications.
Since the topic of this work is AutoML, This work may be used to improve deep learning applications, both beneficial (e.g. reducing CO2 emissions), or harmful (e.g. creating language models with heavy bias) to society.
6 Conclusions and Limitations
In this work, we gave the first large-scale study of performance predictors for neural architecture search. We compared 31 different performance predictors, including learning curve extrapolation methods, weight sharing methods, zero-cost methods, and model-based methods. We tested the performance of the predictors in a variety of settings and with respect to different metrics. Although we ran experiments four different search spaces, it will be interesting extend our experiments to even more machine learning tasks beyond image classification and language modeling.
Our new predictor, OMNI, is the first predictor to combine complementary information from three families of performance preditors, leading to substantially improved performance. While the simplic- ity of OMNI is appealing, it also opens up new directions for future work by combining different predictors more sophisticated ways. To facilitate follow-up work, we release our code featuring a library of performance predictors. Our goal is for our repository to grow over time it is used by the community, so that experiments our library can be even more comprehensive.
Acknowledgments and Disclosure of Funding
This work done while CW and YL were employed at Ab. AZ and FH acknowledge support by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme through grant no. 716721, and by BMBF grant DeT BR supported by the Clarendon Fund of University of Oxford.
10

---

References
[1] Mohamed S Abdelfattah, Abhinav Mchrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight In Proceedings of the International Conference Learning Representations (ICLR), 2021.
[2] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. arXiv preprint vrXiv:1705.1083 2017.
[3] Matthias Bauer, Mark van der Wilk, and Carl Edward Rasmussen. Understanding probabilistic sparse gaussian process approximations. arXiv preprint arXiv: 1606.04820 2016.
[4] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Under- standing and simplifying one-shot architecture search. In Proceedings of the International Conference Machine Learning (ICML), pages 550-559, 2018.
[5] Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. Pyro: Deep universal probabilistic programming. The Journal of Machine Learning Research, 20(1):973- 978. 2019.
[6] Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
[7] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search target task and hardware. Proceedings of the International Conference on Learning Representations (ICLR), 2019.
[8] Akshay Chandrashekaran and Ian R Lane. Speeding up hyper-parameter optimization by extrapolation of learning curves using previous builds. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 477 477-492 492. Springer, 2017.
[9] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference knowledge discovery and data mining, pages 785-794, 2016.
[10] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as alternative to the CIFAR datasets. CoRR, abs/1707 100000819, 2017.
[11] Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hy- perparameter optimization of deep neural networks by extrapolation of learning curves. In Founty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[12] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture four gpu hours. In Proceedings of the IEEE Conference computer vision and pattern recognition, pages 1761-1770, 2019.
[13] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
[14] Tony Duan, Avati Anand, Daisy Yi Ding, Khanh K Thai, Sanjay Basu, Andrew Ng, and Alejan- dro Schuler. Ngboost: Natural gradient boosting for probabilistic prediction. In International Conference Machine Learning, pages 2690-2700, PMLR, 2020.
[15] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, arXiv preprint arXiv: 053777 2018.
[16] Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimization at scale. In Proceedings of the International Conference Machine Learning (ICML), 2018.
[17] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing- Neural architecture search with Bayesian optimisation and optimal transport. Adyances in Neural Information Processing Systems, pages 2016-2025, 2018.

---

[18] Guolin Ke, Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 10:3146-3152 2017.
[19] Hiroaki Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex systems, 4(4):461-476, 1990.
[20] Aaron Klein, Stefan Falkner, Jost Tobias Springenberg. and Frank Hutter. Learning curve prediction with Bayesian neural networks. ICLR 2017, 2017.
[21] Nikita Klyuchnikov, Ilya Trofimov, Ekaterina Artemova, Mikhail Salnikov, Maxim Fedorov, and Evgeny Burnaev. Nas-bench-nlp: neural architecture search benchmark for natural language processing. arXiv preprint urXiv:2006.0711 16, 2020.
[22] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[23] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Tom. SNIP: Single-shot network pruning based on connection sensitivity. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
[24] Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparameter tuning. In Proceedings of the Conference on Machine Learning Systems, 2020.
[25] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-awand gradi- ent algorithms for neural architecture search. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[26] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv preprint arXiv: 1902.07638, 2019.
[27] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. arXiv preprins arXiv:1603.06566 2016.
[28] Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping, arXiv preprint arviv: I0::19000 1909.06035, 2019.
[29] Andy Liaw, Matthew Wiener, et al. Classification and regression by randomforest. R news, 2(3):18 22, 2002.
[30] Marius Lindauer, Katharina Eggensperger, Matthias Feurer, Stefan Falkner, André Biedenkapp. and Frank Hutter. Smac v3: Algorithm configuration in python. URL https://githuh. com/autom//SMACC, 2017.
[31] Marius Lindauer and Frank Hutter. Best practices for scientific research on neural architecture search. arXiv preprint arXiv:1909.02455 2019.
[32] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: a 100. 2018
[33] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu. Neural architecture search with gbdt. arXiv preprint arXiv:2007.04780 047805 2020.
[34] Renqian Luo, Xu Tan, Rui Wang. Tao Qin, Enhong Chen, and Tie- Yan Liu. Semi-supervised neural architecture search. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2020.
[35] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture opti- mization. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2018
12

---

[36] Lizheng Ma, Jiaxu Cui, and Bo Yang. Deep neural architecture search with deep graph Bayesian optimization. In 2019 IEEE/WIC/ACM International Conference on Web Intelligence (WI), pages 500-507. IEFE, 2019.
[37] Krzysztof Maziarz, Andrey Khorlin, Quentin de Laroussilhe, and Andrea Gesmundo. Evolutionary-neural hybrid agents for architecture search. arXiv preprint arXiv: 11X.iv:811.0982.. 1.09828, 2018.
[38] Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. Xrviv preprint 046447 2020.
[39] Szymon Jakub Mikler. Snip: Single-shot network pruning based on connection sensitivity. GitHub repository gahaat/SNNPPpprriing 2019.
[40] Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recur- rent neural network based language model. In Annual conference of the international speech communication association, 2010.
[41] Xuefei Ning. Wenshuo Li, Zixuan Zhou, Tianchen Zhao, Yin Zheng, Shuang Liang, Huazhong Yang, and Yu Wang. A surgery of the neural architecture evaluators. arXiv preprint arXiv:2008. 03064, 2020.
[42] Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-baseh neural architecture encoding scheme for predictor- based nas. arXiv preprint arXiv:2004.0188 2020.
[43] David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang, Lluis Mlqisl Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint arXiv:2 10350, 2021.
[44] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning python. the Journal of machine Learning research, 12:2825-2830, 2011.
[45] Hieu Pham, Melody Y Guan, Barret Zoph, Quoe V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint
2018.
[46] Joaquin Quiñonero Candela and Carl Edward Rasmussen. A unifying view of sparse approxi- mate gaussian process regression. J. Mach. Learn. Res., 6: 6:1999-119 1959, December 2005.
[47] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School Machine Learning, pages 63-71. Springer, 2003.
[48] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School on Machine Learning, pages 63-71. Springer, 2003.
[49] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the uaui conference artificial intelligence, volume 33, pages 4780 4789, 2019.
[50] Binxin Ru, Clare Lyle, Lisa Schut, Mark van der Wilk, and Yarin Gal. Revisiting the train loss: efficient performance estimator for neural architecture search. arXiv preprint arXiv:2006.044: 04492, 2020.
[51] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Neural architecture search using Bayesian optimisation with weisfeiler-lehman kernel. arXiv preprint arXiv:2006.07556. 2020.
[52] Michael Ruchte, Arber Zela, Julien Siems, Josif Grabocka, and Frank Hutter. Naslib: modular and flexible neural architecture search library, 2020.
[53] Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint 1rXiv:1902.08144 08142 2019.
13

---

[54] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. Advances Neural Information Processing Systems, 33, 2020.
[55] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- Nas-bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv 2020.
preprint arXiv:2008..0977
[56] 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, pages 2171-21888 2015.
[57] Jost Tobias Springenherg, Aaron Klein, Stefan Falkner, and Frank Hutter. Bayesian optimization with robust Bayesian neural networks. In Advances in Neural Information Processing Systems, pages 4134-4142, 2016.
[58] Kenneth O Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99-127, 2002.
[59] Yanan Sun, Xian Sun, Yuhan Fang, and Gary Yen. A training protocol for performance pre- dictors of evolutionary neural architecture search algorithms. arXiv preprint arXiv:2008. 13187, 2020.
[60] Kevin Swersky, David Duvenaud, Jasper Snock. Frank Hutter, and Michael Osborne. Raiders of the lost architecture: Kernels for Bayesian optimization in conditional parameter spaces, In NIPS workshop on Bayesian Optimization in Theory and Practice, December 2013.
[61] Hidenori Tanaka, Daniel Kumin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.05467, 2020.
[62] Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferenc Huszár. Faster gaze prediction with dense networks and fisher pruning. arXiv preprint 0rXiv:1801.0577 2018
[63] Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial Intelligence and Statistics, pages 567-574, 2009.
[64] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
[65] Linnan Wang, Yiyang Zhao, Yuu Jinnai, and Rodrigo Fonseca. Alphax: exploring neu- ral architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv:1805.07440, 2018.
[66] Chen Wei, Chuang Niu, Yiping Tang, and Jimin Liang. Npenas: Neural predictor guided evolution for neural architecture search. arXiv preprint arXiv:2003. 12857, 2020.
[67] Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. arXiv preprint arXiv: 19/2.0084, 2019.
[68] Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[69] Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[70] Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
[71] Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. arXiv preprint arXiv: 1902 2019.
14

---

[72] Kaicheng Yu, Rene Ranftl, and Mathieu Salzmann. How to train your super-net: An analysis of training heuristics weight-sharing nas. arXiv preprint arXiv:2003.04276, 2020.
[73] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakehi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
[74] Arber Zela, Julien Siems, and Frank Hutter. Nas-bench- sshttl: one-shot neural architecture search. In Proceedings of the International Conference Learning Representations (ICLR), 2020.
Benchmarking and dissecting
[75] Yuge Zhang, Neural predictor for neural architecture search. GitHub repository ultmas- terhheurdprediicooppxorrrr, 2020.
[76] Yuge Zhang. 7ejun Lin, Junyang Jiang. Quanlu Zhang, Yujing Wang. Hui Xue, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing in neural architecture search. arXiv preprint 2rXiv:2001.01431, 2020.
[77] Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi. Xuesen Zhang, and Wanli Ouyang. Econas: Finding proxies for economical neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11396-11 1404, 2020.
[78] Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
[79] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697-8710, 2018
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our abstract and introduction accurately reflect our paper.
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We discuss the ethics guidelines Section
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [N/A] We did not include theoretical results.
(b) Did you include complete proofs of all theoretical results? [N/A] We did not include theoretical results.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We included all code, data, and instructions in the supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] All training details are specified in the supplementary material. (c) Did report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] We ran 100 trials for all experiments. Our plots that are performance vs. runtime (c.g. Figure 5) have error bars. For Pareto-optimality plots (e.g. Figure 7 see the supplementary material for the error bars for all 31 predictors. (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We report the compute time and resources used in Section 4 and in the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/reelusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We eite the creators of all code, data, and models used.
(b) Did you mention the license of the assets? [Yes] We mention the licenses in the supplementary material.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] We do include new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] We did not use or release any datasets with personal data. (e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] The data we are using does not contain personal information or offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not run experiments with human subjects.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] We did not experiments with human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did run experiments with human subjects.
16


Reviews:
[{"review_id": "spPnNtIjhWX", "reviewer": "Reviewer_Z9bu", "summary": "This paper compares 3 kinds of performance predictors, model based predictors, learning curve based predictor and zero nas predictors. They benchmark the performance of all 31 predictors against 5 benchmarks: NAS-Bench101, DARTS, NASBench201 and NLP.\n\nIn addition to this, they also incorporate SOTL-E and jacobian variance as addition features to NGBOOST and SemiNAS predictors and demonstrate that it improves the performance over all 3 of them. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "Comparing all the predictors and analyzing about how they perform with respect to initialization time and query time is definitely useful for the community. \n\nThey were able to empirically demonstrate some hunches that the community had such as 1) Zero cost NAS techniques do not perform well on larger DARTS space 2) Surrogate models using latent features of architectures would generalize well when one does not have a lot of training data. \n\nWhile the experiments and the insights provided in the paper are useful, none of it is a revelation or surprising. For instance, the tree based methods developed recently are able to outperform model based methods but it takes a lot longer to train them. This paper does not have enough novelty to be accepted as a conference paper. However, this is a good starting point for people who are new to the field. It might be good to expand this paper by adding more algorithmic details of various flavors of performance predictors and make it a survey paper instead.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1) While SoTL and SoTL-E perform well empirically, it is theoretically not valid to use sum of training losses to predict the performance of a network.  A network with lower training loss might also be overfitting and not generalize, while a network with regularization such as dropout, l2 etc might have a higher training loss but still generalize well.\n\n2) It might be better if you didn't include SoTL and SoTL-E in your list of 31 predictors as well.\n\n3) Given that the we know the learning curves of all the architectures in the NAS benchmarks, why not include all the architectures in the test set, rather than only 200? That will give us an actual overview of how these predictors perform on that search space.\n\n4) Given that OMNI has a SEMINAS variant as well, please generate figures corresponding to Figure 3 and 10 to quantify how much it improves over SEMINAS too.\n\n5) Please include OMNI in figure 4 to show its efficacy in ranking architectures that are close to each other.\n\n6) Another useful experiment to perform would be to test how stable the predictors are to various train/test splits and random seeds. \n\n7) I understand that the predictors included in the paper are all those which have open source repositories. It is useful to include other state of the art (SOTA) learning curve predictors ([1] ; [2]; 3) and SOTA model based predictors [4] to a more complete analysis of the performance predictors.\n\n[1] Learning curve prediction with Bayesian neural networks, Klein et al.\n[2] Learning to Rank Learning Curves, Wistuba et al.\n[3] Speeding up hyperparameter optimization by extrapolation of learning curves using previous builds, Chandrasekhar et al.\n[4] Neural Architecture Search in A Proxy Validation Loss Landscape, Li et al.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mnB7na7R1OT", "reviewer": "Reviewer_sow2", "summary": "The paper give a large-scale comparison of performance predictors in NAS. The results act as recommendations for the best predictors to use in different settings. The author also show that certain families of predictors can be combined to achieve even better predictive power.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(a) The paper proposed a large-scale comprehensive comparison of performance predictors in NAS, the choice of predictors range from learning curve extrapolation, to weight-sharing, to 10 supervised learning and zero-cost proxies. The survey itself is beneficial to the NAS community.\n(b) The paper proposed a new predictor OMNI, to combine complementary information from three families of performance predictors, leading to substantially improved performance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(a) The paper has well-study the ranking performance of predictors, however I believe in NAS, sampling (of arch and peformmance pairs) also plays a important role and can largely affect the final performance of NAS predictors. As a result I believe sampling should be decoupled in the evaluation of predictor-based NAS, e.g. BANANNAS/ BONAS which use guided sampling method, should fall into a different category and compared seperately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "_l1LaKvW14B", "reviewer": "Reviewer_eo6y", "summary": "The authors identify and benchmark a plethora of recently proposed techniques for predicting neural network architecture performance on a task without doing a full training run. \n\nThey begin by grouping each technique into categories: model-based, learning-curve-based, zero-cost, and weight-sharing. When viewed like this it becomes clear that there is a need for a common benchmark to distinguish the performance of the different approaches. \n\nTo compare under one framework, evaluation is done with respect to two variables: initialization time (time spent preparing the model) and query time (time spent retrieving predictions from the model).\n\nThe authors then present their own method, OMNI, which performs NAS using a blend of model-based, learning-curve-based, and zero-cost predictors. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a solid paper and should be accepted. There is nothing hugely surprising or significant in it, and there are no real deep insights uncovered, so I'm not sure it merits being a \"seminal paper\". However, the experiments are thorough, logically conducted and answer previously unanswered questions. I think overall this work will be helpful and insightful to the neural architecture search (NAS) subfield. \n\n**Originality:** This is a novel investigation into (and combination of) pre-existing techniques. Analysing different predictors under a single framework (via query/init times) is a new way of looking at NAS and allows us to ask interesting questions.  Related work is adequately cited.\n\n**Quality:** The submission is technically sound, and the reader leaves the paper with the impression that each claim has been thoughtfully evaluated. The choice of methods seems to give a reasonable coverage of the space of existing work and the authors are careful to address problems with comparative analysis (especially with regard to hyperparameter setup). \n\n**Clarity:** The submission is very clearly written and organized. It's easy to glean the main takeaways and the logical flow of the paper makes sense. I feel confident that there is enough detail in the paper that would allow me to reproduce each of the results. \n\n**Significance:** The results of the paper come in the form of clear takeaways which I'm sure will be of practical use to anyone hoping to use neural architecture search. The results from the experiments are a unique dataset which will allow for the exploration of further lines of research. \n\n## Positive points:\n- The paper is very well written and structured, and comes with clear, robustly verified takeaways\n- Open sourced code \n- This is an experiment-heavy paper, which I suppose you would expect from a characterization task like this. The experiments cover a wide range of datasets and techniques, and at the end the authors present a combined method which appears to robustly outperform using a single approach. \n- There are many interesting visualisations with pleasantly surprising results — the fact that the benefits of using different predictors can be combined and are complementary is both interesting and useful as an insight.\n\n## Points to address:\n1. I found the use of the terms: initialization, query and update a little confusing. In the case of a zero-cost proxy, does “initialization time” ever change? Whereas for something like XGBoost, does “initialization” really mean “training”?\n2. When do we explicitly want to trade off query and initialization time? At the end of section 4 the authors state “we recommend deciding on a target initialization time and query time budget”. I understand that the two aspects were needed to design a comparison framework for various methods, but I’m struggling to think of a scenario in which this is a trade-off that’s useful to be able to make, or what might motivate me to have a preference for one or the other? \n3. It’s an enormous topic, but I would have liked to see a slightly more fundamental investigation of what drives the various performance predictors. Is there anything that can be extracted from the best performing methods on various NAS-benchmarks to address what exactly each one is measuring? Since the different techniques appear to be complementary, is it likely that they are measuring different things? I suspect this question is out of scope for this paper (which is already packed with insights), but it would be great to have some quantification of this.\n4. I would also have liked to see some more “baseline” methods. For instance, what if you use number of parameters/flops as a zero-cost proxy? \n5. Minor visual note: the plot titles in figures 3 and 5 aren’t aligned properly.\n\n## General questions\n\nI think this is a really interesting piece of work that leaves the reader with many things to ponder! I therefore have some more general questions for the authors, that I don’t think necessarily need to be addressed in the paper but would be interested to hear about (I will continue numbering them in case you would like to reply to them specifically):\n\n6. Regarding NAS-Bench-201, the authors state \"6 466 are unique after removing isomorphisms” — do they have a citation for this? \n7. On line 279 the authors state: “The NAS-Bench-101 API only gives the validation accuracy at four epochs”. Is this true? This seems surprising!\n8. The authors mention that the training and test sets are architectures drawn uniformly at random from the search space — could they confirm that these are two separate sets? I.e. there’s no chance of resampling the same architecture?\n9. During the mutation-based test set experiments the authors limit the test architectures to be “at most an edit distance of three from a seed architecture”. How is edit distance calculated? Is it a distance between binary adjacency matrices? If so, is the edit distance of replacing e.g. a conv1x1 with a conv3x3 the same as the edit distance of replacing a conv3x3 with an identity? Again, it’s not necessary to include anything in the paper, but I would be intrigued to hear the authors thoughts on how different measurements of “distance” might impact this set of experiments. Can we use e.g. the distance between scalar outputs of zero-cost measures as “edit distances” between architectures? \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concerns about societal impact beyond any other work on neural networks.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3SC8-PM4eN2", "reviewer": "Reviewer_RXE7", "summary": "Neural Architecture Search (NAS) aims to find the network architectures with the best accuracies -- or best size/accuracy tradeoffs -- from within a human-defined search space. The submission evaluates a number of different heuristics for ranking different candidate architectures in a search space. The submission claims to evaluate 31 different techniques which fall into several categories (e.g., early stopping, learning curve extrapolation, supervised learning, one-shot models, zero-shot metrics). The submission claims that different techniques work better for different compute budgets (e.g., low setup cost/low search cost vs. high setup cost/high search cost). It also claims that combining techniques from different families (e.g., supervised learning + zero-shot metrics) can lead to better results than using any one technique on its own. Experimental results are reported on NASBench-101, NASBench-201, the NASBench-301/DARTS search space, and NASBench-NLP.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Contributions:** The submission evaluates/compares a number of previously proposed NAS techniques from several popular categories:\n1. Supervised training methods which sample a set of (random) architectures, measure the performance (accuracy) of each one, and then use the resulting  `<architecture, accuracy>` pairs to train a regression model which can predict the accuracies of unseen architectures.\n2. Curve extrapolation (\"learning-curved based\") methods which try to predict a network's accuracy at the end of training by measuring its accuracy at each of the first `K` epochs of training.\n3. One-shot NAS methods which train a single set of shared weights which can be used to evaluate/rank many different candidate architectures in the search space.\n4. Zero-shot NAS methods which try to rank different candidate architectures based on a few batches of data using randomly initialized weights.\n\n**Results:** The submission (not surprisingly) claims that different techniques are optimal in different ranges. For example, it claims that Jacobian Covariance, a zero-shot technique, performs best in the very low-cost regime, whereas simply training network architectures from scratch for a shortened number of steps performs best in the high-cost regime. Both of these claims seem plausible.\n\nPerhaps more interesting -- and more surprising -- is the submission's claim that if the goal is to maximize the correlation between predicted and observed (ground-truth) model accuracies, \"Of the 31 predictors we tested, we found that just seven of them are Pareto-optimal with respect to Kendall Tau, initialization time, and query time. That is, only seven algorithms have the highest Kendall Tau value for at least one of the 154 query time/initialization time budgets on NAS-Bench-201 CIFAR-10\" (L217). Similar trends are reported for the other datasets.\n\nIn addition to evaluating different techniques' abilities to rank different candidate architectures in a search space (e.g., rank-correlation between predicted and ground-truth accuracies), the submission also evaluates: (i) each technique's ability to estimate which of two similar-looking architectures will have a higher accuracy, and (ii) the effects of ensembling different techniques, e.g., a supervised technique + zero-shot NAS.\n\n**Significance:** The findings, if valid, can be potentially useful for practitioners who want to know which classes of NAS techniques to focus on. One risk in trying to evaluate so many different techniques in a single paper is that the authors might not spend enough time ensuring that each individual technique is properly implemented and well-optimized. The authors take a number of reasonable steps to try to mitigate this concern:\n1. They try to use the authors' original implementations of different techniques in many cases (L186). However, looking at the Appendix and included source code, I have the impression that some techniques are evaluated using snippets of code from the original authors' implementation whereas others are reimplemented from scratch.\n2. Hyper-parameters are re-tuned by the submission's authors to help control for the fact that different techniques probably received different amounts of hyper-parameter tuning in the past.\n3. The final evaluation uses a separate held-out test set. (Good ML practice.)\n\nGiven the sheer number of architectures evaluated by the submission, this seems like a reasonable evaluation protocol. However, it comes with the caveat that if a technique is found *not* to work well by the submission's authors, it can be unclear whether that's because of a flaw in the technique itself or whether the submission's implementation of that technique is implemented incorrectly / insufficiently tuned.\n\nThe submission's claim that ensembling different NAS techniques (e.g., NGBoost + Jacobian covariance) can lead to significantly improved performance seems intuitive and potentially relevant for practitioners. This seems like a direction that's received relatively little attention for the NAS community. While it comes with the downside of making the NAS implementation significantly more complex, I still think reporting these results is a nontrivial research contribution.\n\n**Clarity:** The submission seems well-written, polished, and easy to understand.\n\n**Post-rebuttal update:** The discussion and reproducibility table provided by the authors does a good job of addressing my concerns about whether the original methods were reproduced faithfully, and I've increased my rating from 6 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The quality of ML algorithms tends to be sensitive to hyper-parameters and small implementation details, so the reliability of the submission's claims may depend on the quality of the submission's authors' implementations of different NAS techniques. However, this is as much a general concern about the type of work (trying to evaluate/compare/rank 30+ techniques in a single paper) than about authors' specific implementation.\n\nThe most effective mitigation I can think of is to verify that the submission's implementation is able to reproduce the results reported by the original authors of a given technique. I don't think the submission's authors are doing this, but I might've missed something. (I haven't checked the paper's appendix too closely.)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an in-depth investigation of existing techniques. The experiments support the claims/questions in the paper well. The authors engaged well during the discussion phase to clarify all reviewers' concerns. The findings are likely going to be very useful to the NAS community.
Decision: Accept (Poster)