Surrogate NAS Benchmarks: Going Beyond the Limited Search Spaces of Tabular NAS Benchmarks
Authors: Arber Zela
Julien Niklas Siems
Lucas Zimmer
Jovita Lukasik
Margret Keuper
Frank Hutter
Venue: ICLR 2022 Poster (2022)
Keywords: neural architecture search
AutoML
benchmarking
surrogate model

Abstract: The most significant barrier to the advancement of Neural Architecture Search (NAS) is its demand for large computational resources, which hinders scientifically sound empirical evaluations of NAS methods. Tabular NAS benchmarks have alleviated this problem substantially, making it possible to properly evaluate NAS methods in seconds on commodity machines. However, an unintended consequence of tabular NAS benchmarks has been a focus on extremely small architectural search spaces since their construction relies on exhaustive evaluations of the space. This leads to unrealistic results that do not transfer to larger spaces. To overcome this fundamental limitation, we propose a methodology to create cheap NAS surrogate benchmarks for arbitrary search spaces. We exemplify this approach by creating surrogate NAS benchmarks on the existing tabular NAS-Bench-101 and on two widely used NAS search spaces with up to $10^{21}$ architectures ($10^{13}$ times larger than any previous tabular NAS benchmark). We show that surrogate NAS benchmarks can model the true performance of architectures better than tabular benchmarks (at a small fraction of the cost), that they lead to faithful estimates of how well different NAS methods work on the original non-surrogate benchmark, and that they can generate new scientific insight. We open-source all our code and believe that surrogate NAS benchmarks are an indispensable tool to extend scientifically sound work on NAS to large and exciting search spaces.

Published as a conference paper at ICLR 2022
SURROGATE NAS BENCHMARKS: GOING BEYOND THE LIMITED SEARCH SPACES OF TABULAR NAS BENCHMARKS
Arber Zela'; Julien Siems'; Lukas Zimmer Jovita Lukasik², Margret Keuper?, Frank Hutter
1 University of Freiburg, University of Mannheim, 3 Bossh Center for Al
ABSTRACT
The most significant barrier to the advancement of Neural Architecture Search (NAS) is its demand for large computational resources, which hinders scientifically sound empirical evaluations of NAS methods. Tabular NAS benchmarks have alleviated this problem substantially, making it possible to properly evaluate NAS methods in seconds commodity machines. However, unintended consequence of tabular NAS benchmarks has been a focus on extremely small architectural search spaces since their construction relies on exhaustive evaluations of the space. This leads to unrealistic results that do not transfer to larger spaces. To overcome this fundamental limitation, we propose a methodology to create cheap NAS surrogate benchmarks for arbitrary search spaces. We exemplify this approach by creating surrogate NAS benchmarks on the existing tabular NAS-Bench-ID 101 and two widely used NAS search spaces with up to 10 architectures (1023 times larger than any previous tabular NAS benchmark). We show that surrogate NAS benchmarks can model the true performance of architectures better than tabular benchmarks (at a small fraction of the cost), that they lead to faithful estimates how well different NAS methods work on the original non-surrogate benchmark, and that they can generate new scientific insight. We open-source all our code and believe that surrogate NAS benchmarks are indispensable tool to extend scientifically sound work on NAS to large and exciting search spaces.
INTRODUCTION
Neural Architecture Search (NAS) has seen huge advances in search efficiency, but the field has recently been criticized substantially for non-reprodueible research, strong sensitivity of results to
carefully-chosen training pipelines, hyperparameters and even random seeds (Yang et al. 2020 Li & Talwalkar 2020; Lindauer & Hutter 2020 (hhu et al., 20200 Yu et al., 2020). A leading cause that complicates reproducible research in NAS is the computational cost of even just single evaluations of NAS algorithms, not least in terms of carbon emissions (Patterson et al.) 2021 Li et al., 2021a).
Tabular NAS benchmarks, such NAS-Bench- 101 (Ying al. 2019) and MAS-Bench-24 (Dong & Yang 2020), have been a game-changer for reproducible NAS research, for the first time allowing sci- entifically sound empirical evaluations of NAS methods with many seeds in minutes, while ruling confounding factors, such as different search spaces, training pipelines or hardware/softwar versions.
This success has recently led the creation of many additional tabular NAS benchmarks, such as NAS-Bench- shot (Zela et al. 2020b), NATS-Bench (Dong et al. 2021), NAS-HPO-bende (Klein Hutter 2019). NAS-Bench- WKA.PPKKKlyllliiii (Klyuchnikov et al.) 2020p, MAS-Bench-
(Mehrotra et al. 2021), and HW-NAS-Bent (Li et al. 2021b) (see Appendix A. for more details on these previous NAS benchmarks).
However, these tabular NAS benchmarks rely on exhaustive evaluation of all architectures in search space, limiting them to unrealistically small search spaces (so far containing only between 6k and 423k architectures). This is far shot from standard spaces used in the NAS literature, which
Equul contribution. Email to: [zelas aa @cs. uni frei-rreiii Frreiburg.d

---

Published as a conference paper at ICLR 2022
contain more than 10 architectures Zoph & Le 2017: Liu al. 2019 Wu al.
2019a). This
discrepancy can cause results gained on tabular NAS benchmarks to not generalize to realistic search spaces; e.g., promising anytime results of local search tabular NAS benchmarks were indeed shown to not transfer to realistic search spaces (White et al. 2020a).
Making things worse, discussed in the panel of the most recent NAS workshop at ICLR 2021, to succeed in automatically discovering qualitatively new types of architectures (such as, e.g., Transformers (Vaswani al., 2017)) the NAS community will have focus on even more expressive search spaces in the future. To not give up the recent progress in terms of reproducibility that tabular NAS benchmarks have brought, we thus need to develop their equivalent for arbitrary search spaces. That is the goal of this paper.
Our contributions. Our main contribution is introduce the concept of surrogate NAS benchmarks that can be constructed for arbitrary NAS search spaces and allow for the same cheap query interface as tabular NAS benchmarks. We substantiate this contribution as follows:
1. We demonstrate that a surrogate fitted on a subset of architectures can model the true performance of architectures better than tabular benchmark (Section 2).
2. We showcase our methodology by building surrogate benchmarks realistically-sized NAS search space (up to 10 possible architectures, i..., 10 times more than any previous tabular NAS benchmark), thoroughly evaluating range of regression models as surrogate candidates, and showing that strong generalization performance is possible even in large spaces (Section 3
3. We show that the search trajectories of various NAS optimizers running on the surrogate bench- marks closely resemble the ground truth trajectories. This enables sound simulations of runs usually requiring thousands of GPU hours in a few seconds
single CPU machine (Section
4. We demonstrate that surrogate benchmarks can help in generating new scientific insights by rectifying a previous hypothesis on the performance of local search in large spaces (Section 4
To foster reproducibility, we open-source all our code, data, and surrogate NAS benchmarks
2 MOTIVATION CAN WE DO BETTER THAN A TABULAR BENCHMARK?
We start by motivating the of surrogate benchmarks by expos- ing an issue of tabular benchmarks that has largely gone unnoticed. Tabular benchmarks are built around a costly, exhaustive evalu- ation of all possible architectures in search space, and when an architecture's performance is queried, the tabular benchmark sim- ply returns the respective table entry. The issue with this process is that the stochasticity of mini-batch training is also reflected in the performance of an architecture i, hence making it random variable Y,. Therefore, the table only contains results of a few draws y/ Y; (existing NAS benchmarks feature up 3 runs per architecture). Given the variance in these evaluations, tabular benchmark acts as simple estimator that assumes independent random variables, and thus estimates the performance of an architecture based only on previous evaluations of the same architecture. From a machine learning perspective, knowing that similar architectures tend to yield similar performance and that the variance of individual evaluations can be high (both shown to be the case by Ying et (2019),, it is natural assume that better estimators may exist. In the remainder of this section, we empirically verify this hypothesis and show that surrogate benchmarks can provide better performance estimates than tabular benchmarks based on less data.
Model
Mean Absolute Error (MAF)
1, 3]
2,11, 3]
3, (1,
Tab. Surr.
4.534c-3
4.546e-3
4.539e-3
3,446e-3
3,455e-3
3,441e-3
Table 1: MAE between perfor- mance predicted by a tab./surr. benchmark fitted with one seed each, and the true performance of evaluations with the two other seeds. Test seeds in brackets.
Setup. For the analysis in this section, we choose benchmark and a Graph Isomorphism Network (GIN, Xu al. (2019a)) as our surrogate model. Each architecture 2; in JAS-Bench-101 contains 3 validation accuracies y/ v² ya from training
101 (Ying et al. 2019) as a tabular
https: : / thub. www.b...oo/....oooooooooooo...oo cwm/autionnnnoeocc oml //w./annbbbbahonneee
We used GIN implementation by Errica al. 2020 see Appendix for details on training the GIN.
2

---

Published as a conference paper at ICLR 2022
with 3 different seeds. We excluded all diverged models with less than 50% validation accuracy any of the three evaluations in one of the seeds, c.g., Dtroin {(z y )} and evaluate the other two, e.g., Diest {(z,, v,
We split this dataset to train the GIN surrogate model on
where of = (v? + u /
Results. We compute the mean absolute error MAE Σ, 1. of the surrogate model trained on Dirasn [(=;, ): where ýJ the predicted validation accuracy and n |Dtest], Table 1 shows
n
that the surrogate model yields a lower MAE than the tabular benchmark. i.e. MAE Σ -
We also report the mean squared error and Kendall tau correlation coefficient in Table in the appendix showing that the ranking between architectures is also predicted better by the surrogate. We repeat the experiment in cross- voos-vaaliation fashion w.r.t to the seeds and conclude: In contrast to single tabular entry, the surrogate model learns to smooth out the noise
Next, we fit the GIN surrogate on subsets of Dtrein and show in Figure [ how its performance scales with the amount of training data used. The surrogate model performs better than the tabular benchmark when the training set has more than ~21,500 architectures. (Note that Drest remains the same as in the previous experiment, i.e., it includes all 423k architectures in MAS-Benel 1enchh-01.) As result, we conclude that: A surrogate model can yield strong predictive performance when only subset of the search space is available as training data.
Moan Aboolute Ertor
Surrogate
10-2
Number of architectures from NB-101
Figure 1: Number of architectures used for training the GIN surrogate model vs MAE the NAS-Bende 101 dataset.
These empirical findings suggest that we can create reliable surrogate benchmarks for much larger and more realistic NAS spaces, which are infeasible to be exhaustively evaluated (as would be required to construct tabular benchmarks).
3 GOING BEYOND SPACE SIZE LIMITS WITH SURROGATE BENCHMARKS
We now introduce the general methodology that we propose to effectively build realistic and reliable surrogate NAS benchmarks. We showcase this methodology by building surrogate benchmarks on two widely used search spaces and datasets, namely DARTS (Liu et al.. 2019) + CIFAR-10 10 and FBNet [Wu et al. (019a) + CIFAR-100. Having verified our surrogate NAS benchmark methodology on these well-known spaces, we strongly encourage the creation of additional future surrogate NAS benchmarks a broad range of large and exciting search spaces, and the compute time saved by replacing expensive real experiments on the DARTS or FBNet space with cheap experiments on our surrogate versions of them might already be used for this purpose.
We name our surrogate benchmarks depending on the space and surrogate model considered as follows: Surr-NAS-Benche (space (surrogate) (or, SNB- (pace] ) (surrogatee for short). For example, we introduce SNB DARTS -GIN, which is a surrogate benchmark on the DARTS space and uses GIN [Xu et al. 2019a) as surrogate model.
CNB-(space)
3.1 GENERAL METHODOLOGY AND NARRR-NAS-BECHREE
We first explain our methodology for the DARTS (iu et al. 2019) search space, which consists of more than 10 architectures. We selected this search space for two main reasons: (1) due to the huge number of papers building on DARTS and extending it, the DARTS search space, applied to CIFAR-10 the most widely used non-tabular NAS benchmark in the literature, and as such provides convincing testbed for our surrogate benchmarks" and (2) the surrogate benchmark we construct frees up the substantial compute resources that are currently being invested for experiments
We note that the average estimation emror of tabular benchmarks could be reduced by factor of vk by performing runs per architecture. The error of surrogate models would also shrink when they hased on more data, but as grows large tabular benchmarks would become competitive with surrogate models.
'n particular, the alternative of first constructing new non-tabular benchmark and then building surrogate benchmark for it would have heen susceptible many confounding factors.
3

---

Published as a conference paper at ICLR 2022
on this non-tabular benchmark; we hope that these will instead be used to study additional novel and more exciting spaces and/or datasets.
3.1.1 SURROGATE MODEL CANDIDATES
We are interested in predicting a metric y E Y C R. such as accuracy or runtime, given an architecture encoding x: E X. A surrogale model can be any regression model Φ X Y, however, picking the right surrogate to learn this mapping can be non-trivial. This of course depends on the structure and complexity of the space, e.g., if the architecture blocks have a hierarchical structure or if they are just composed by stacking layers sequentially, and the number of decisions that have to be made at every node or edge in the graph.
Due to the graph representation of the architectures commonly used in NAS, Graph Convolutional Networks (GCNs) are frequentl used as NAS predictors (Wen et al.] 2019; Ning et al. 2020 Lukasik et al. 202T). In particular, the GIN (Xu et al., (019a) is good fit since several works have found it to perform well on many benchmark datasets (Errica et al. 2020 Hu et al. 2020 Dwivedi et al. 2020), especially when the space contains many isomorphic graphs. Other interesting choices could be the DiffPool (Ying et al.) 2018) model, which can effectively model hicrarchically--trueee
spaces, or Graph Transformer Networks (GTN) Yun et al. 2019) for more complex heterogeneous graph structures.
Nevertheless, as shown in White al. (2021b), simpler models can already provide reliable perfor- mance estimates when carefully tuned. We compare the GIN to a variety of common regression models. We evaluate Random Forests (RF) and Support Vector Regression (SVR) using imple- mentations from scikit-learn (Pedregosa et al. (011). We also evaluate the tree-basee gradient boosting methods XGBoost (Chen & Guestrin (016)) LGBoost (Ke et al. 2017) and NGBoost (Duan)
it al. 2020), recently used for predictor-based NAS (Luo et al. 2020). We comprehensively review architecture performance prediction in Appendix A.2
We would like to note the relation between our surrogate model candidates and performance predictors in a NAS algorithm (White et al., 2021b), e.g., in Bayesian Optimization (BO). In principle. any
type of NAS predictor can be used, including zero-shot proxies (Mellor et al.
2021: Abdelfattah
al. 2021), , one-shot models (Brock al. 2018 Bender et al. 2018
2020
Zhao et al.
(021)
learning curve extrapolation methods (Domhan et al., 2015 Baker et al.
2017
Klein et al.
201 7).
and model-based proxies (Ru et al.) 2021; Ma et al. 2019 Shi et al. 2020 White et 201 Since
White et al. (202 found model-based proxies to work best in the regime of relatively high available initialization time (the time required to produce the training data) and low query time (the time required make prediction) we use these types of performance predictors for our surrogates. If we were also willing to accept somewhat higher query times, then combined models that extrapolate initial learning curves based full learning curves of previous architectures (Baker et al. 2017 Klein et al. 2017) would be a competitive alternative (White et al. 2021b).
3.1.2 DATA COLLECTION
As the search spaces we aim to attack with surrogate NAS benchmarks are far too large to be exhaustively evaluated, care has to be taken when sampling the architectures which will be used to train the surrogate models. Sampling should yield good overall coverage of the architecture space while also providing special focus on the well- pell-performing regions that optimizers tend to exploit.
Our principal methodology for sampling in the search space is inspired by Eggensperger et al. (2015). who collected unbiased data about hyperparameter spaces by random search (RS), as well as biased regions by running hyperparameter optimizers. This is
and denser samples in desirable for a surrogate benchmark since we are interested in evaluating NAS methods that exploit such good regions of the space.
We now describe how we collected the dataset NAS benchmarks on the DARTS search space. The search space itself is detailed in Appendix C.I Table 5 in the appendix lists the 10 NAS methods we used to collect architectures in good regions
we use for our case study of surrogate
of the space, and how many samples we collected with each (about 50k in total). Additionally, we
evaluated 11k architectures in for the analysis conducted the dataset and surrogates. We refer Appendices C.2 and for
regions for better coverage and another 10k
4

---

Published as a conference paper at ICLR 2022
details on the data collection and the optimizers, respectively. Appendix C.4 shows the performance of the various optimizers in this search space and visualizes their overall coverage of the space. as well as the similarity between sampled architectures using t-SNE (van der Maaten & Hinton 2008) in Figure [2] Besides showing good overall coverage, some well-performing architectures in the search space form distinct clusters which mostly located outside the main cloud of points. This clearly indicates that architectures with similar performance are close to each other in the architecture space. We also observe that different optimizers sample different architectures (see Figure in the appendix). Appendix C.5 provides statistics of the space concerning the influence of the cell topologies and the operations, and Appendix JoppendijCC.6deeeeeeee [Csedrees the full training pipeline used for all architectures. In total, our ENB-DARTS dataset consists of ~60k architectures and their performances on CIFAR-10 (Krizhevsky) 2009). We split the collected data into train/val/test splits, which we will use to train, tune and evaluate our surrogates throughout the experiments.
Finally, we would like to point out that, in hindsight, adding training data of well- pell-rerfoming regions may be less important for surrogate NAS benchmark than for surrogate HPO benchmark: Appendix [:3 shows that surrogates based purely on random evaluations also yield competitive performance. We believe that this is result of HPO search spaces containing many configurations that yield dysfunctional models, which is less common for architectures in many NAS search spaces, hence allowing random search cover the search space well enough to build strong surrogates.
3.1.3 EVALUATING THE DATA FIT
Similarly to Wen al. (2019), Baker et al. (017) and White et al. (2021b), we assess the quality of the data fit via the coefficient of determination (R²) and the Kendall rank correlation coefficient (T). Since Kendall r is sensitive to noisy evaluations, following Yu et al. (2020) we use a sparse Kendall Tau (sKT), which ignores rank changes at 0.1 %% accuracy precision, by rounding the predicted validation accuracy prior to computing т. We compute such metrics on a separate test set of architectures, never used to train tune the hyperparameters of the surrogate models.
As we briefly mentioned above, our main goal is to obtain similar learning trajectories (architecture performance vs. runtime) when running NAS optimizers the surrogate benchmark and the real benchmark. The ranking of architectures is therefore one of the most important metrics to pay attention to since most NAS optimizers are scale-invariant, i.e., they will find the same solution for the function (z) and a f(x), with scalar a.
For applying the surrogate model candidates described above on our dataset gate models using the multi-fidelity Bayesian optimization method BOHB (Falkner et al. 2018); details on their respective hyperpa- rameter search spaces are given in Table in the appendix. We use train/val/test splits (0.8/0. 1/0.1) stratified across the NAS methods used for the data collection. This means that the ratio of architectures from a particular optimizer is constant across the splits, e.g., the test set contains 50% of its architectures from RS since RS was used to trained and evaluated. We provide additional details on the preprocessing of the architectures for the surrogate models in Appendix [E.]] As Table shows, our three best-performing models were LGBoost, XGBoost, and GIN; therefore, we focus our analysis on these in the following.
Test
Model
we tuned the hyperparameters of all surro-
R²
SKT
LGBoost
0.892
0,816
XCBoost
0.832
0.817
GIN
0.832
0.778
NGBoost
0.810
0.759
0.709
0.677
MLP (Path enc.)
0.704
0.697
RF
0.679
0.683
-SSV
0.675
0.660
obtain 50% of the total architectures
Table Performance of dif- ferent regression models fitted
on the -DRRTARTS dataset.
In addition to evaluating the data fit on our data splits, we investigate the impact of parameter-free operations and the cell topology in Appendices E.6 (..7 respectively. We find that all of LGBoost, XGBoost, and GIN accurately predict the drop in performance when increasingly replacing operations with parameter-fi operations in a normal cell of the DARTS search space.
3.1.4 MODELS OF RUNTIME AND OTHER METRICS
To allow evaluations of multi-objectivee NAS methods, and to allow using "simulated wallelock time" on the x axis of plots, also predict the runtime of architecture evaluations. For this, we train an LGB model with the runtime as targets (see Appendix CoppendixE.4]foor for details); this runtime also logged for all architectures in dataset SNB-DARTS Runtime prediction is less challenging than performance
5

---

Published as a conference paper at ICLR 2022
prediction, resulting in excellent fit of our LGB runtime model the test set (sKT: 0.936, R²: 0.987). Other metrics of architectures, such as the number of parameters and multiply-adds, do not require surrogate model but can be queried exactly.
3.1.5 NOISE MODELING
The aleatoric uncertainty the architecture evaluations is of practical relevance since it not only determines the robustness of particular architecture when trained with stochastic optimization algorithm, but it can also steer the trajectories of certain NAS optimizers and yield very different results when run multiple times. Therefore, modeling such noise in the architecture evaluations is an important step towards proper surrogate benchmarking.
A simple way model such uncertainty is to ensem- bles of the surrogate model. Ensemble methods are com- monly used to improve predictive performance (Dietterich)
Model
MAE 1, [2.3.455]
Mean
KL div.
Tabular
1.38c 3
undef.
undef.
GIN
1.13e-3
0.6e-3 3
16.4
2000). Moreover, ensembles of deep neural networks, so- called deep ensembles (Lakshminarayanan et al. 2017). have been proposed as a simple and yet powerful (Ova- dia al., 2019) way to obtain predictive uncertainty. We therefore create an ensemble of 10 base learners for each of our three best performing models (GIN, XGB, LGB) using a 10-fold cross-validatie for our train and validation split, as well as different initializations.
LGB
1.33e-3
0.3e-3
68.9
XGB
1.51e-3
0.3e-3
134.4
Table 3: Metries for the selected surro- gate models on 500 architectures that were evaluated 5 times.
To assess the quality of our surrogates' predictive uncertainty, we compare the predictive distribution of our ensembles to the ground truth. We assume that the noise in the architecture performance is normally distributed and compute the Kullback-Leibler (KI.) divergence between the ground truth accuracy distribution and predicted distribution.
3.1.6 PERFORMANCE OF SURROGATES VS. TABLE LOOKUPS
We now mirror the analysis we carried out for our GIN surrogate on the NB-101 dataset in our motivational example (Section 2) but now using our sisher-dimensional dataset SNB-DARTS. For this, we use of 500 architectures trained with 5 seeds each. We train the surrogates using only one evaluation per architecture (i.e., seed 1) and take the mean accuracy of the remaining ones as ground truth value (i.e., seeds 2-5). We then compare against a tabular model with just one evaluation (seed 1). Table shows that, in the motivational cxample, our GIN and LGB surrogate models yield estimates closer to the ground truth than the table lookup based on one evaluation. This confirms our main finding from Section 2 but this time much larger search space. In terms of noise modeling, we find the GIN ensemble to quite clearly provide the best estimate.
3.1.7 EVALUATING THE NAS SURROGATE BENCHMARKS SNB-DARTS XGB AND SNB-DARTS-GIN
Having assessed the ability of the surrogate models to fit the search space, we now evaluate the surro- gate NAS benchmarks CIIB-DARTS-22 SERTS-XXEE -XB and SNB- SNB-DARTS- DARTS-GIN, comparing cheap evaluations of various NAS algorithms on them against their expensive counterpart on the original non-tabular NAS benchmarks. We note that for the surrogate trajectories, each architecture evaluation is sampled from the surrogate model's 's predictive distribution for the given architecture. Therefore, different optimizer runs lead to different trajectories.
We first compare the trajectories of blackbox optimizers on the true, non non-tabular benchmark vs. on the surrogate benchmark, using surrogates trained on all data. For the true benchmark, show the trajectories we ran to create our dataset (based on a single run per optimizer, since we could not afford repetitions due the extreme compute requirements of 115 GPU days for single run). For the evaluations on the surrogate, on the other hand, we can trivially afford to perform multiple runs.
Results (all data). As Figure 2 shows, both the XGB and the GIN surrogate capture behaviors present in the true benchmark. For instance, the strong improvements of BANANAS and RE are also present on the surrogate benchmark at the correct time. In general, the ranking of the optimizers towards convergence is accurately reflected on the surrogate benchmark. Also, the initial random exploration of algorithms like TPE, RE and DE is captured as the large initial variation in performance

---

Published as a conference paper at ICLR 2022
True Benchmark
GIN Surrogate Benchmark
XGB Surrogate Benchmark
10
RE
validaiin etror
7x
BANANAS
6x
5x
10"
16a 10P
100
10"
102
10"
10'
10"
10"
10a 100
10'
Wallclock
Simulated Wallclock
Simulated Wallclock Time [s]
Figure 2: Anytime performance of different optimizers the real benchmark (left) and the surrogate benchmark (GIN (middle) and XGB (right)) when training ensembles on data collected from all optimizers. Trajectories on the surrogate benchmark are averaged over optimizer runs and the standard deviation is depicted.
True Benchmark
GIN Surrogate Benchmark
XGB Surrogate Benchmark
Dest validation eiter echieved
10
8 80
RE
TPE
BANANAS
RS
60-2
xx
10
100
10 Simulated Wellclock Time [s]
10f 10¹
10a
Wellklock Time [s]
Simullttdd Wallclock Time [s]
Figure 3: Anytime performance of different optimizers on the real benehmark (left) and the surrogate benchmark (GIN (middle) and XGB (right)) when training ensembles only data collected by random search. Trajectories on the surrogate benchmark are averaged over 5 optimizer runs.
indicates. Notably, the XGB surrogate ensemble exhibits a high variation in well-performing regions as well and seems to slightly underestimate the error of the best architectures. The GIN surrogate, on the other hand, shows less variance in these regions but slightly overpredicts for the best architectures.
Note, that due to the size of the search space, random search stagnates and cannot identify one of the best architectures even after tens of thousands of evaluations, with BANANAS finding better architectures orders of magnitude faster. This is correctly reflected in both surrogate benchmarks.
Finally, surrogate NAS benchmarks can also be used to monitor the behavior of one-shot NAS optimizers throughout their search phase, by querying the surrogate model with the currently most promising discrete architecture. We show this evaluation in Appendix F.I
3.1.8 ABLATION STUDIES
Fitting only on random architectures. We also investigate whether it is possible to create surro- gate NAS benchmarks only based on random architectures. To that end, we studied surrogate models based only on the 23746 architectures explored by random search and find that we can indeed obtain realistic trajectories (see Figure 3) but lose some predictive performance regions. For the full description of this experiment see Appendix F33 Nevertheless, such bench- marks have the advantage training data. In an additional experiment, we found that surrogates built on only well- well-performing architectures (92% and above) yielded poor extrapolation to worse architectures, but that surrogate benchmarks based on them still yielded realistic trajectories. We attribute this to NAS optimizers' focus on good architectures. For details, see Appendix [22
the celforerfo
not possibly favouring any NAS optimizer used for the generation of
Leave Oattimztiize--uut (LO00) analysis. Similarly to Eggensperger et al. 2015). we also perform a leave-one-ope wete-oonioottt---oooeee analysis (LOO0) analysis, a form cross-validation on the optimizers we used for data collection, i.e., assess each optimizer with surrogate benchmarks created based on data excluding that gathered by said optimizer (using a stratified 0.9/0.1 I train/val split over the other NAS methods). Figure in the appendix compares the trajectories obtained
7

---

Published as a conference paper at ICLR 2022
from 5 runs in the LOO0 setting on the surrogate benchmark to the groundtruth. The XGB and GIN surrogates again capture the general behavior of different optimizers well, illustrating that characteristics of new optimization algorithms can be captured with the surrogate benchmark.
3.2 USING THE GATHERED KNOWLEDGE TO CONSTRUCT SURR --A---NNSSS--H -BBNE
In Section 3.1
we presented our general methodology for constructing surrogate NAS benchmarks and exemplified it on the DARTS space and CIFAR- 10 dataset. In this section, we make use of the knowledge gathered from those experiments construct a second surrogate benchmark the very different but similarly popular FBNet (Wu et al. 2019a) search space and CIFAR-100 dataset.
The FBNet search space consists of fixed macro architecture with 26 sequentially stacked layers in total. The first and last three layers are fixed, while the other in-between layers have to be searched. There 9 operation choices for every such layer (3 kernel sizes, times 3 possible numbers of filter), yielding total of g se 10 unique architecture configurations. See Appendix D for more details on the search space and training pipeline.
Surrogate models choice. Despite the high cardinality of the space, it has less complex structure compared to the DARTS space. Because this, and also based on its high predictive performance on the DARTS space, we pick XGBoost surrogate model for the FBNNet space. Similarly to SNB-DARTS, we create an ensemble of base learners trained with different initializations.
Data collection and predictive performance. The data collected to create SNB-FBNet comprises 25k architec- tures sampled uniformly at random, split in train/val/test sets 1/0.). Based on the performance of SNB-DARTS -XGG fitted only on randomly sampled data (see Appendix F.3) and
0.02mn
0.35
Rank Correlation porrelation Coeft.
Mean Absalute Error
0.34
3.0034
Tabular MAE
2.0032
Summyste Stearnar
in order obtain a surrogate without sampling bias, we fit the XGB surrogate only on the randomly sampled architec- tures. Using the transferred hyperparameters from the tuned XGB surrogate on the DARTS space already yields 0.84 R² and 0.75 sKT correlation coefficient value on the test set. We additionally collected 1. 1.6k, 1.5k, 1 500, 200 architectures sampled by HEBO (Cowen-Rivers et af.) 2020), RE, TPF, DE and COMBO, respectively, which will use to evaluate the SNB-FBNet - XGB benchmark below.
Tabala Sparmmn
3.0030
0.0528
10a Training data
Figure 4: Number of architectures used for training the XGB surrogate model vs. MAE and rank correla- tion on the FBNet search space.
Noise modeling and performance vs. table lookups. In order to assess the performance of SNB-FENet-XCE towards table lookups, we conduct a similar experiment as we did for SNB -ARIS in Section 3.1.6] We trained a set of 500 randomly sampled architectures times each with different seeds. We then trained the surrogate model on only one seed and compare the predicted performance on this set of 500 architectures to the mean validation error of seeds and 3. surrogate a tabular model which
The latter serves contains only one evaluation per architecture, namely seed in our case. Figure 4 shows that the XGB surrogate is already able outperform the table entries in terms of mean absolute error towards the "ground truth" error when fitted using only 20% of the training data.
"ground truth". Similarly, compare
True Benchmark
XGB Surrogate Benchmark
Dest validaioo error echleves
0.27
0.27
RE
0.26
0.26
0.25
COMBO
TPE
0.25
TPE
COMBO
0.24
DE
DE
HEBO
0.23
0.22
0.22
0.21
0.21
10a
10a
10a
107
10a
10p
10
107
Walklock Time
(Simulated) Wallclock Time
Figure 5: Anytime performance of different optimizers on the real benchmark and the XGB surrogate benchmark when training ensembles on data collected only from random search. Trajectories on the surrogate benchmark are averaged over 5 optimizer runs and the standard error is depicted.
8

---

Published as a conference paper at ICLR 2022
Evaluating the NAS surrogate benchmark -NB-FENet-XGB. In Figure we show the black- box optimizer trajectories on SNB-PBNet (right plot) and the ones on the real FBNet bench- mark (left plot). The XGB surrogate has low variance in well well-porfonning regions of the space, with a slight overprediction of performance (compared to the single RE run possible on the original benchmark). Note that COMBO and TPE have higher overheads for fitting their internal models, which depend on the dimensionality of the architecture space being optimized. Our surrogate model successfully simulates both their performance and this overhead. Finally, similarly the results ob- served in the DARTS space, random search cannot identify good architecture even when evaluating 2500 architectures, with RE and HEBO being at least 8 and 16 times faster, respectively, in finding better architecture. Also, in contrast to the DARTS space, here, the absolute difference between random search and HEBO and RE larger, with 1-2% absolute difference in error.
USING NAS SURROGATE BENCHMARKS TO DRIVE NAS RESEARCH
Finally, we perform case study that demonstrates how surrogate NAS benchmarks can drive NAS research. Coming up with research hypotheses and drawing conclusions when prototyping or evaluating NAS algorithms on less realistic benchmarks is difficult, particularly when these evaluations require high computational budgets. Surrogate NAS benchmarks alleviate this dilemma via their cheap and reliable estimates.
Local Search
To showcase such a scenario, we evaluate Local Searct (LS) on our surrogate benchmarks SNB-DARTS-GIN and SNB-DARTS-XCE as well as the original, non-tabular DARTS benchmark. White et al. (2020a) concluded that I.S does not perform well on such a large space by running it for 11.8 GPU days ( 10t seconds), and we are able to reproduce the same results via SNB ENB-DARTS DARIS- --IN and BNB-DARTS- - in few seconds (see Figure 6) Furthermore, while White et al. (2020a)
Best vallidation achieved
x 10-
LS-TT
8x100
GIN
LS-XBB
BANANAS-GT
7
6x -2
5x
GPU
could not afford longer runs (nor repeats), on our surrogate NAS benchmarks this is trivial. Doing so suggests that LS shows qualitatively different behavior when run for an order of magnitude longer, transitioning from being the worst method (even worse than random search) to being one of the best. We verified this suggestion by running LS for longer on the actual DARTS benchmark (also see Figure 6). This allows us to revise the initial conclusion White et al. (2020a) to: The initial phase of LS works poorly for the DARTS search space, but in the higher-budget regime LS yields state-of-the-ar performance.
10
10"
10 10'
(Simulated) Wallclock Time
Figure 6: Case study results for Local Search. GT is the ground truth, GIN and XGB are results on SNB-DARTS- -IITS-GIN and SNB-DARTS- XGB, respectively.
This case study shows how a surrogate benchmark was already used to cheaply obtain hints on research hypothesis that lead to correcting a previous finding that only held for short runtimes. We look forward to additional uses of surrogate NAS benchmarks along such lines.
CONCLUSIONS AND FUTURE WORK
We proposed the concept of constructing cheap-to-evaluate surrogate NAS benchmarks that can be used as conveniently tabular NAS benchmarks but in contrast these can be built for search spaces of arbitrary size. We showcased this methodology by creating and evaluating several NAS surrogate benchmarks. including for two large search spaces with roughly 1028 and 1021 architectures, respectively, for which the exhaustive evaluation needed to construct a tabular NAS benchmark would be utterly infeasible. We showed that surrogate benchmarks can be more accurate than tabular benchmarks, assessed various possible surrogate models, and demonstrated that they can accurately simulate anytime performance trajectories of various NAS methods at a fraction of the true cost. Finally, we showed how surrogate NAS benchmarks can lead to new scientific findings.
In terms of future work, having access to a variety of challenging benchmarks essential to the sustained development and evaluation of new NAS methods. We therefore encourage the community to expand the scope of current NAS benchmarks to different search spaces, datasets, and problem domains, utilizing surrogate NAS benchmarks to tackle exciting, larger and more complex spaces.
We use the implementation and settings of Local Search provided by White et al. (2020a).

---

order to ensure comparability of results in different published papers, we ask users state the benchmark's version number. So far, we release -GG-AAATSS---Bl..... Published as a conference paper at ICLR 2022
6 ETHICS STATEMENT
Societal Impact. We hope and expect that the NAS practitioner will benefit from our surrogate NAS benchmarks the same way for research on exciting large search spaces as she so far benefited from tabular NAS benchmarks for research on toy search spaces by using them for fast and easy prototyping of algorithms and large-scale (yet cheap) scientific evaluations. We expect that in the next years this will save millions of GPU hours (which will otherwise be spent on running expensive NAS benchmarks) and thus help reduce the potentially hefty carbon emissions NAS research (Hao) 2019). It will also ensure that the entire NAS community can partake in exploring large and exciting NAS design spaces, rather than only corporations with enormous compute power, thereby further democratizing NAS research.
Limitations & Guidelines for Using Surrogate Benchmarks. We would like to point out that there exists risk that prior knowledge about the surrogate model used in particular benchmark could lead to the design of algorithms that overfit that benchmark. To this end, we recommend the following best practices ensure safe and fair benchmarking of NAS methods on surrogate NAS benchmarks:
The surrogate model should be treated black-box function, hence only be used for performance prediction and not exploited to extract, e.g., gradient information.
We discourage benchmarking methods that internally use the same model as the surrogate model picked in the surrogate benchmark (e.g. GNN-based Bayesian optimization should not only be benchmarked using a GIN surrogate benchmark).
We encourage running experiments on versions of surrogate benchmarks that are based on (1) all available training architectures and (2) only architectures collected with uninformed methods, such as random search or space-filling designs. As shown in Appendix F.3 (1) yields better predictive models, but (2) avoids any potential bias (in the sense of making more accurate predictions for architectures explored by particular type of NAS optimizer) and can still yield strong benchmarks.
ENN-DARTS--GN--O
SNB-DARTS XGB AGB-rand-vl.0. 0, and SNB-FRNet -ww-E-Nett-----------
SNE-DARTS-GIN--eame
Due to the flexibility of surrogate NAS benchmarks to tackle arbitrary search spaces, we expect that the community will create many such benchmarks in the future, just like it already created many tabular NAS benchmarks Ying et al. (2019); Dong & Yang (2000); et al. (2020b); Dong al. (202T): Klein Hutter (2019); Klyuchnikov et al. (2020); Mehrotra et al. (2021 Li al.
(2021b). We therefore collect best practices for the creation of such new surrogate NAS benchmarks in Appendix
ACKNOWLEDGMENNTS
We thank the anonymous reviewers for suggesting very insightful experiments, in particular the experiments for NAS benchmarks based only on random architectures. The authors acknowledge funding by the Robert Bosch GmbH, by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme through grant no. 716721, by BMBF grants DeToL and RenormalizedFlows (O1IS 19077C), and by the Deutsche Forschungsgemeinsce German Research Foundation) under grant number 4 116928828 This research was partially supported by TAILOR, project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
(DFG,
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight nas. International Conference on Learning Representations, 2021.
N. Awad. N. Mallik, and Hutter. Differential evolution for neural architecture search (dehb). In International Conference on Learning Representations (ICLR) Neural Architecture Search (NAS) Workshop, 2020.
B. Baker, O. Gupta, R. Raskar, and N. Naik. Accelerating Neural Architecture Search using Performance Prediction. In NeurlPS Workshop Mela-Learning, 2017.
R. Baptista and M. Poloczek. Bayesian optimization of combinatorial structures. In International Conference on Machine Learning (ICML), pp. 462-471, 2018.
Gabriel Bender, Picter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. In International Conference Machine Learning, 2018.
Gabriel Bender, Hanxiao Liu, Bo Chen, Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoc V. Le. Can weight sharing outperform random architecture search? investigation with tunas. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, ((110):281-055 2012.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter op- timization. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
A. Brock, T. Lim, J.M. Ritchie, and N. Weston. SMASH: One-shot model architecture search through hypernetwrrss. In International Conference on Learning Representations, 2018
Chen and C. Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsich. Dr[nas]: Dirichlet neural architecture search. In International Conference on Learning Representations, 2021.
P. Chrabaszez, I. Loshchilov, and F. Hutter. A downsampled variant of imagenet alternative to the cifar datasets. arXiv preprint 1 2017.
Alexander Imani Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan- Rhys Griffiths, Hao Jianye, Jun Wang, Jan Peters, and Haitham Ammar. An empirical study of assumptions in bayesian optimisation. 2020.
B. Deng, J. Yan, and D. Lin. Peephole: Predicting network performance before training. arXiv preprint
2017.
DeVries and G. W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: 708.04 2017.
T. Dietterich. Ensemble Methods in Machine Learning, volume 1857 of Lecture Notes in Computer Science. Springer Berlin Heidelberg. 2000.
Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. optimization of deep neural networks by extrapolation of learning curves. In IJCAI, 2015.
Speeding up automatic hyperparameter
X. Dong and Y. Yang. Searching for robust neural architecture in four gpu hours. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1761-1770, 2019.
X. Dong and Y. Yang. Nas-bench- 102: Extending the scope of reproducible neural architecture search. In International Conference Learning Representations (ICLR), 2020.

---

Published as a conference paper at ICLR 2022
Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats-bench: Benchmarking nas algorithmss for architecture topology and size. IEEE transactions on pattern analysis and machine intelligence, PP, 2021.
T. Duan, A. Avati, D. Ding, Khanh K. Thai, S. Basu, A. Ng, and A. Schuler. Ngboost: Natural gradient boosting for probabilistic prediction. In Proceedings of Machine Learning and Systems 2020. pp. 6138 6148, 2020.
Lukasz Dudziak, Thomas Chau, Mohamed Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas Lane. Brp-nas: Prediction-basse nas using gcns. In Advances in Neural Information Processing Systems, volume 33, pp. 10480-10490. Curran Associates, Inc., 2020.
V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. arXiv preprint 2xXiv:003300088: 2020.
Katharina Eggensperger, Frank Hutter, Holger Hoos, and Kevin Leyton-Brown. Efficient bench- marking of hyperparameter optimizers via surrogates. In AAAI, 2015.
F. Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations (ICLR), 2020.
S Falkner, A Klein, and F. Hutter. BOHB:
Robust and efficient hyperparameter optimization at scale. Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 1437-1446, 2018.
M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learming on Gruphs and Manifolds, 2019.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awan minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pp. 734.734. IEEE, 2005.
Karen Hao. Training a single ai model can emit as much carbon as five cars in their lifetimes, 2019. URL httpt::t////// www. www.ohoooooeeeeee......... wttpeeewcccocm000/////////000000
K. He, X. Zhang, Ren, and J. Sun. Deep Residual Learning for Image Recognition. Computer Vision and Pattern Recognition (CVPR), 2016.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint 2XXv:2005500687, 2020.
J. Hwang, S. Lay, and A. Lippman. Nonparametric multivariate density estimation: a comparative study. IEEE Transactions on Signal Processing, 42(10))2795-288 2810, 1994.
R. Istrate, F. Scheidegger, G. Mariani, D. Nikolopoulos, C. Bekas, and A. C. I. Malossi. Tapas: Train-less accuracy predictor for architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 9927-3934, 2019.
G. Ke, Q. Meng. Т. Finlcy, T. Wang, W. Chen, W. Ma, Q. Ye, and T. Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems 30, pp. 3146-3154, Curran Associates, Inc., 2017.
T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
A. Klein and F. Hutter. Tabular benchmarks for joint architecture and hyperparameter optimization. arXiv preprint arXiv: 1119990599770 2019.
12

---

Published as a conference paper at ICLR 2022
A. Klein, S. Falkner, J. T. Springenberg, and F. Hutter. Learning curve prediction with Bayesian neural networks. In International Conference on Learning Representations (ICLR), 2017.
Aaron Klein, Zhenwen Dai, Frank Hutter, Neil D. Lawrence, and Javier I. González. Meta-surrogate benchmarking for hyperparameter optimization. In NeurIPS, 2019.
N. Klyuchnikov, I. Trofimov, Artemova, M. Salnikov, M. Fedorov, and E. Burnaev. Nas-bench- nip: Neural architecture search benchmark for natural language processing. arXiv preprint arXiv:2006.07/1 16, 2020.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in neural information processing systems, pp- 6402-6413, 2017.
G. Larsson, M. Maire, and G. Shakhnarovich. Fractalnet: Ultra-deep neural networks without residuals. In International Conference on Learning Representations (ICLR), 2017.
Bo Li, Xin Jiang, Donglin Bai, Yuge Zhang, Ningxin Zheng, Xuanyi Dong, Lu Liu, Yuging Yang, and Dongsheng Li. Full-cycle energy consumption benchmark for low-carbon computer vision. ArXiv, abs/2108. 00121108.1466 2021a.
Chaojian Li, Zhongzhi Yu, Yonggan Fu, Yongan Zhang, Yang Zhao, Haoran You, Qixuan Yu, Yue Wang, Cong Hao, and Yingyan Lin. HW-NAS-Bend Hardware-Aware Neural Architecture Search Benchmark. In International Conference Learning Representations, 2021b.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 367-377. PMLR, 22-25 Jul 2020.
M. Lindauer, K. Eggensperger, M. Feurer, A. Biedenkapp. Marben, Müller, and Hutter. Boah: tool suite for multi-fidelity bayesian optimization & analysis of hyperparameters, wwXiv:/98.00670 [cs. [C), 2019.
Marius Lindauer and Frank Hutter. Best practices for scientific research on neural architecture search. Journal of Machine Learning Research, 21 2020.
H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
I. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts, In International Conference on Learning Representations (ICLR), April 2017.
Jovita Lukasik, David Friede, Arber Zela, Heiner Stuckenschmidt, Frank Hutter, and Margret Keuper. Smooth variational graph embeddings for efficient neural architecture search. 2021 International Joint Conference on Neural Networks (JJCN), pp. 1-8, 2021.
R. Luo, X. Tan, R. Wang. T. Qin, E. Chen, and T. Liu. Neural architecture search with gbdt. arXiv preprint ar arXiv:2007.04788 2020.
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), pp. 500-507. IEEE, 2019.
M. D. McKay, R. Beckman, and W. Conover. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42(1): 55-61, 2000.
Abhinav Mehrotra, Alberto Gil C. P. Ramos, Sourav Bhattacharya, Lukasz Dudziak, Ravichander Vipperla, Thomas Chau, Mohamed Abdelfattah, Samin Ishtiaq, and Nicholas Donald Lane. MAS--ench-Aae Reproducible neural architecture search for speech recognition. In International Conference Learning Representations, 2021.
13

---

Published as a conference paper at ICLR 2022
Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley. Neural architecture search without training. In International Conference on Machine Learning. 2021.
Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-based neural architecture encoding scheme for predictor-based nas. In ECCV, 2020.
C. Oh, J. Tomezak, E. Gavves, and M. Welling. Combinatorial bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Systems, pp. 19200,90, 2019.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
David A. Patterson, Joseph Gonzalez, Quoc V. Le, Chen Liang, Lluis-Miqued Munguia, Daniel Rothchild, David R. So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. ArXiv, abs/2104, 10350, 2021.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, et al. Scikit-leam: Machine learning in python. Journal of machine learning research, 12(052))222--2830 2011.
K. Price, R. M. Storn, and J. A. Lampinen. Differential evolution: a practical approach to global optimization. Springer Science & Business Media, 2006.
Esteban Real, Alok Aggarwal, Yamping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael A. Osbore.. Interpretable neural architecture search via bayesian optimisation with Hessfeiler-lehmar kernels. In ICLR, 2021.
Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov. and Liang- Shing-Chich Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. 2018 IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4510-4520 2018
H. Shi, R. Pi, H. Xu, Z. Li, J. T. Kwok, and T. Zhang. Multi-objective neural architecture search via predictive network performance optimization. arXiv preprint arXiv: 1.09336, 2019.
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-base based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 33, 2020.
Y. Shu, W. Wang, and S. Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
I. M. Sobol', On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 7(4):784-80) 802, 1967.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Computer Vision and Pattern Recognition (CVPR), 2015.
Y. Tang, Y. Wang, Y. Xu, H. Chen, B. Shi, C. Xu, C. Xu, Q. Tian, and C. Xu. A semi-supervised assessor of neural architectures. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
L. der Maaten and G. Hinton. Visualizing data using t-sne. Journal of Machine Learning Research (JMLR), 9Nov)
2008
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
W. Wen, H. Liu, H. Li, Y. Chen, G. Bender, and P. Kindermans. Neural predictor for neural architecture search. arXiv preprint arXiv: 2019.
14

---

Published as a conference paper at ICLR 2022
C. White, S. Nolen, and Y. Savani. Local search is state of the art for nas benchmarks. arXiv preprint arXiv:2005.02960, 2020a.
Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. In Advances in Neural Information Processing Systems, 2020b.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In AAAI, 2021a.
Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? In NeurIPS, 2021b.
Bichen Wu, Alvin Wan, Xiangyu Yue, Peter H. Jin, Sicheng Zhao, Noah Golmant, Amir Gholamine- jad, Joseph E. Gonzalez, and Kurt Keutzer. Shift: A zero flop, zero parameter alternative to spatial convolutions, IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 9127-9135, 2018.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Péter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware- efficient convnet design via differentiable neural architecture search. 2019 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 10726-10734, 2019a.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. Yu. comprehensive survey on graph neural networks. arXiv preprini arXiv: 1901,0059, 2019b.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019a.
Y. Xu, Y. Wang, K. Han, H. Chen, Y. Tang, S. Jui, Xu, Q Tian, and C. Xu. Rnas: Architecture 1910.01533, 2019b.
ranking for powerful networks. arXiv preprint
Y. Xu, I.. Xie, X. Zhang, X. Chen, G. Qi, Q. Tian, and H. Xiong. Pe-darts: Partial channel connections for memory-efficient architecture search, In International Conference on Learning Representations, 2020.
A. Yang, P. M. Esperança, and F. M. Carlucci. Nas evaluation is frustratingly hard. In International Conference on Learning Representations, 2020.
C. Ying, A. Klein, F. Christiansen, E. Real, K. Murphy, and F. Hutter. NAS-bench-101 101: Towards reproducible neural architecture search. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1445-7114, 2019.
R. Ying, J. You, Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hicrarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NeurlPS' 18, pp. 4805 4815, Red Hook, NY, USA, 2018. Curran Associates Inc.
K. Yu, R. Ranftl, and M. Salzmann. How to train your super-net: An analysis of training heuristics in weight-sharing nas. arXiv preprint arXiv:2003.0422 04276, 2020.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
A. Zela, T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F. Hutter. Understanding and robustifying differentiable architecture search. In International Conference on Learning Representations, 2020a.
A. Zela, J. Siems, and F. Hutter. NAS-Bench- 1Shot:: Benchmarking and dissecting one-shot neural architecture search. In International Conference on Learning Representations, 2020b.
H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk minimization. International Conference Learning Representations (Workshop Track), 2018.
15

---

Published as a conference paper at ICLR 2022
Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo. Few-shot neural architecture search. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12707-12718. PMLR, 18-24 Jul 2021.
J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434. 2018.
B. Zoph and Q. Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.
16

---

Published as a conference paper at ICLR 2022
A RELATED WORK
A.1 EXISTING NAS BENCHMARKS
Benchmarks for NAS were introduced only recently with NAS-Bench-100 (Ying et al. 2019) as the first among them. SAS-Bench-ID is a tabular benchmark consisting of 4423 unique architectures in cell structured search space evaluated of architectures in the search space, the number nodes and edges was given an upper bound and only three operations are considered. One result of this limitation is that One-Shot NAS methods can only be applied to subspaces of NAS-Bench-IDe 101 as demonstrated in NAS-Benchs 1Sott (Zela et al. 2020b).
CIFAR- 10 (Krizhevsky 2009). To restrict the number
MAS-Bench--211 (Dong & Yang 2020), in contrast, uses a search space with a fixed number of nodes and edges, hence allowing for straight-forward application of one-shot NAS methods. However, this limits the total number of unique architectures to as few as 6466. NAS-Bench-20) includes evaluations of all these architectures on three different datasets, namely CIFAR-10, CIFAR- (Krizhevsky) 2009) and Downsampled Imagenet 16x 16 (Chrabaszez et al. 2017). allowing for transfer learning experiments.
More recently, NATS-Bene's (Dong et al. 2021 was introduced as an extension to introduces a size search space for the number of channels in each cell of a cell-basee macro architecture. Evaluating each configuration in their size search space for one cell, NAT-Bench provides an additional ~22k unique architectures. On the other hand, HW-NAS-Bent (Li et al.. 202 extends the search space of NAS-Bench-201 by measuring different hardware metrics, such as latency and energy consumption on six different devices.
NAS-Bench-NLP [Klycchnikov et al. 2020) was recently proposed as tabular benchmark for NAS in the Natural Language Processing domain. The search space resembles limits the number of edges and nodes constrain the search space size resulting in 14k evaluated architectures.
as
Bench-ASc (Mchrotra et al. (02T) is the first benchmark that enables running NAS algorithms on the automatic scpeech recognition task. The benchmark is still tabular though, which restricts the search space size to around 8k unique architectures.
A.2 NEURAL NETWORK PERFORMANCE PREDICTION
In the past, several works have attempted to predict the performance of neural networks by ex- trapolating learning curves (Domhan et al. 2013] Klein et al.] 2017 Baker et al. (017). A more recent line of work in performance prediction focuses
feature encoding of neural archi- tectures. Peephole (Deng et al., 2017) and TAPAS (Istrate et al., (019)) both use an LSTM to aggregate information about the operations in chain-structured architectures. On the other hand, BANANAS (White et al.) 2021a) introduces path-based encoding of cells that automatically re- solves the computational equivalence of architectures.
Graph Neural Networks (GNNs) (Gori et al. 2005) Kipf & Welling 2017 Zhou et al. 2018 Wu et al.
2019b Dudziak al. 2020). with their capability of learning representations graph-structured structuredd data appear to be natural choice to learning embeddings of NN architectures, Shi et al. (2019) and Wen
al. 2019 trained Graph Convolutional Network (GCN) on subset of NAS- Bench-101 (Ying et al. 2019) showing its effectiveness in predicting the performance of unseen architectures. Moreover, Lukasik et al. (2021) propose smooth variational graph embedding (SVGe) via a variational graph
autoencoder which utilizes a two-sided GNN encoder-decoder model in the space of architectures, which generates valid graphs in the learned latent space and also allows for extrapolation.
Several recent works further adapt the GNN message passing to embed architecture bias via extra weights to simulate the operations such as in GATES (Ning et al. 2020) or integrate additional information the operations (e.g., flop count) (Xu et al. 2019b). Tang et al. (2020) chose to operate GNNs on relation graphs based on architecture embeddings in a metric learning setting, allowing to pose NAS performance prediction
semi-supervised setting.
Finally, White et al. (2021b) evaluate more than 30 different performance predictors on existing NAS benchmarks, ranging from model-based ones zero-cost proxies and learning curve predictors.
17

---

Published as a conference paper at ICLR 2022
A.3 COMPARISON BETWEEN NAS AND HPO SURROGATE BENCHMARKS
Finally, we highlight the similarities and differences of surrogate benchmarks for NAS and hyper- parameter optimization (HPO) (Eggensperger al. 2013 Klein et al. 2019). Ultimately, the NAS problem can indeed be formulated as an HPO problem and some algorithms designed for HPO can indeed be evaluated on NAS benchmarks; however, this does require that they can handle the corresponding high-dimensional categorical hyperparameter space typical of NAS benchmarks (c.g., 34 hyperparameters for the DARTS space; 22 hyperparameters for the FBNet space). This difference in dimensionality makes a qualitative difference: in HPO, benchmark with few hyperparameters makes a lot sense, as that is actually the most frequent use case of HPO. But this is not the case for NAS, which typically consists of much higher-dimension several existence proofs that is indeed possible to build good-enougl surrogate benchmarks for nigh-dimensional NAS spaces. We also showed for the first time that surrogate benchmarks can have lower error than tabular benchmarks and demonstrated an exemplary use of surrogate NAS benchmarks drive research hypotheses in case study; neither of these has been done for surrogate HPO benchmarks. Furthermore, we also study the possibility of using pure random search to generate the architectures base our surrogate on; this turned out to work very well for NAS surrogate benchmarks but would work very poorly for typical higher-dimensional HPO surrogate benchmarks, because many hyperparameters. when set poorly, completely break performance, whereas poor architectural choices still yielded relevant results that could inform the model building. Finally, NAS benchmarks are also far more expensive than typical HPO benchmarks. This calls even more for the necessity of careful methodology on how to construct surrogate benchmarks for NAS.
spaces. In this work, gave
B TRAINING DETAILS FOR THE GIN IN THE MOTIVATION
We set the GIN to have hidden dimension of 64 with 4 hidden layers resulting in around 440k parameters. We trained for 30 epochs with a batch size of 128. We chose the MSE loss function and add logarithmic transformation to emphasize the data fit on well-performing architectures.
Model
Mean Squared Error (MSF)
Kendall tau
1. 1, 3]
2, [1,
3, [1,
1, [2, 3]
2, [1
3, [1, 21
Tab.
5,44e-5
5,43e-5
5.34e-5
0.83
0.83
0.83
Surr.
3.02e-5
3.07e-5
3.02e-5
0.87
0.87
0.87
Table 4: MSE and Kendall tau correlation between performance predicted by a tab/surr. benchmark fitted with one seed each, and the true performance of evaluations with the two other seeds (see Section 2}. Test seeds in brackets.
C THE SURR-NAS-BENCEE
DATASET
C.I SEARCH SPACE
We use the same architecture search space as in DARTS (Liu et al., 2019). Specifically, the normal and reduction cell each consist of a DAG with 2 input nodes (receiving the output feature maps from the previous and sevious-previous cell), 4 intermediate nodes (each adding element-wise feature maps from two previous nodes in the cell) and output node (coneatenating the outputs of all intermediate nodes). Input and intermediate nodes connected by directed edges representing one of the following operations: Sep. conv x 3, Sep. conv x 5, Dil. conv 3, Dil. conv 5 5, Max pooling 3 3, Avg. pooling x 3, Skip connection.
C.2 DATA COLLECTION
To achieve good global coverage, we use random search to evaluate ~23k architectures, We note that space-filling designs such as quasi-random sequences, e.g. Sobol sequences (Sobol' 1967). or Latin Hypercubes (McKay et 2000) and Adaptive Submodularity (Golovin & Krause 2011 may also provide good initial coverage.
18

---

Published as a conference paper at ICLR 2022
Random search is supplemented by data which collect from running a variety of optimizers, representing Bayesian Opti- mization (BO), evolutionary algorithms and One-Shot Optimiz- ers. We used Sew.oof-PPazee--sttiii
NAS methods
# eval
Regaza
23746
(TPE) (Bergstra et al. 201T) implemented by Falkner al. (2018) as a baseline BÔ method. Since several recent works have proposed to ap- ply BO over combinatorial spaces (Oh et al. 2019 Baptista & Poloczek 2018) we also used COMBO (Oh et al., (019). We included BANANAS (White al. 2021a) as our third BO method, which uses a neural network with path-based encoding as a surrogate model and hence scales better with the number of function evaluations. As two representatives of evolutionary approaches to NAS, we chose Regularized Evolu- tion (RE) (Real et al. 2019) as it is still one of the state-of-the art methods in discrete NAS and Differential Eyolution (Price) al. 2006) implemented by Awad et al. 2020). Accounting
Evolution
DE RF
Aasiiia 2020
46.39
7275
TPF Beyen qal 2011
6741
BO
BANANAS Wateeln 200
2243
COMBO
745
DARTS Unreaal
2053
One-Shot
PC-DARTS
1588
Clanet
GDAS
Yeag 2015
234
Table 5: NAS methods used to cover the search space and the num- ber of architectures (not necessarily unique) gathered by them during search.
for the surge in interest in One-Shot NAS, our collected data collection also entails evaluation of
architectures from search trajectories of DARTS (Liu et al.
2019), GDAS (Dong & Yang 2019).
DrNAS (Chen et al. 2021 and PC-DARTS (Xu et al. 2020) For details on the architecture training
details, we refer to Section C.
For each architecture a E A. the dataset contains the following metries: train/validation/tes accuracy, training time and number of model parameters.
C.3 DETAILS ON EACH OPTIMIZER
In this section we provide the hyperparameters used for the evaluations of NAS optimizers for the collection of our dataset. Many of the optimizers require a specialized representation function on an architecture space because most of them are general HPO optimizers. As recently shown by White al. (2020b), this representation can be critical for the performance of a NAS optimizer. Whenever the representation used by the Optimizer did not act directly on the graph representation, such as in RE, we detail how we represented the architecture for the optimizer. All optimizers were set to optimize the validation error.
BANANAS. We initialized BANANAS with 100 random architectures and modified the opti- mization of the surrogate model neural network, by adding early stopping based on a 90%/10% train/validation split and lowering the number of ensemble models to be trained from 5 to 3. These changes to bananas avoided a computational bottleneck in the training of the neural network.
COMBO, COMBO only attempts to maximize the acquisition function after the entire initial design (100 architectures) has completed. For workers which are done carlier, sample a random architecture, hence increasing the initial design by the number of workers (30) we used for running the experiments. The search space considered in our work is larger than all search spaces evaluated in COMBO (Oh et al. 2019) and we regard not simply binary architectural choices, as we have to make choices about pairs of edges. Hence, we increased the number of initial samples for ascent acquisition function optimization from 20 to 30. Unfortunately. the optimization of the GP already became the bottleneck of the BO after around 600 function evaluations, leading many workers waiting for new jobs to be assigned.
Representation: In contrast to the COMBO's original experimental setting, the DARTS search requires choices based on pairs of parents of intermediate nodes where the number of choices increase with the index of the intermediate nodes. The COMBO representation therefore consists the graph cartesian product of the combinatorial choice graphs, increasing in size with each intermediate node. In addition, there exist 8 choices over the number of parameters for the operation in cell.
Differential Evolution. DE was started with generation size of 100. As we used a parallelized implementation, the workers would have to wait for one generation plus its mutations to be completed for selection to start. We decided to keep the workers busy by training randomly sampled architectures in this case, random architectures provide good coverage of the space. However, different
19

---

Published as a conference paper at ICLR 2022
methods using asynchronous DE selection would also be possible. Note, that the DE implementation by Awad et al. (2020). performs boundary checks and resamples components of any individual that exceeds I.0. We use the randl mutation operation which generally favors exploration over exploitation.
Representation: DE uses vector representation for each individual in the population. Categorical
choices are scaled to lie within the unit interval [O, 1] and are rounded to the nearest category when converting back the discrete representation in the implementation by Awad al. (2020). Similarly to COMBO, we represent the increasing number of parent pair choices for the intermediate nodes by interpreting the respective entries have an increasing number of sub-intervals in [0, 1].
DARTS, GDAS, PC-DARTS and DrNAS. We collected the architectures found by all of the above one-shot optimizers with their default search hyperparameters. We performed multiple searches for each one-shot optimizer.
RE. To allow for good initial coverage before mutations start, we decided randomly sample 3000 architectures as initial population. RE then proceeds with sample size of 100 to extract well performing architectures from the population and mutates them. During mutations RE first decides whether to mutate the normal reduction cell and then proceeds to perform either parent change, an operation change or no mutation.
TPE. For TPE we use the default settings as also used by BOHB. We use the Kernel-Density- Estimator surrogate model and build two models where the good configs are chosen as the top 15%. The acquisition function's 's expected improvement is optimized by sampling 64 points.
Heteroscedastic and Evolutionary Bayesian Optimisation solver (HEBO) is the winning optimizer of the NeurlPS 2020 Black-Box Optimisation challenge @ observations of improvements that BO components yield on a variety benchmarks. particular, HEBO uses enhanced surrogate model which can handle non-stationarity and heteroscedasticity during the marginal likelihood maximization. In our experiments we use a random forest surrogate model instead of the default Gaussian Process one, while the other components of HEBO remain unchanged with their respective default values.
HEBO.
HEBO was designed after careful
1.00
C.4 OPTIMIZER PERFORMANCE
Cumulative prob.
0.75
The trajectories from the different NAS optimizers yield quite different performance distributions. This can be seen in Figure 7 which shows the ECDF of the validation errors of the architectures evaluated by each optimizer. As the computational budgets allocated to each optimizer vary widely, this data does not allow for a fair comparison between the optimizers. However, it is worth mentioning that the evaluations of BANANAS feature the best dis- tribution of architecture performances, followed by PC-DARTS, DrNAS, DE, GDAS, and RE. TPE only evaluated marginally better architectures than RS, while COMBO and DARTS evaluated the worst ar- chitectures.
BARTS
0.50
DRNAS
CDAS
0.25
PC. DARTS
RE
RS
0.00
TPE
0.05
0.1
0.2
Validation error
Figure 7:
Empirical Cumulative Density Function (ECDF) pl comparing all optimiz- good regions of
ers. Optimizers which cover the search space feature higher values in the low validation error region.
We also perform a t-SNE analysis on the data collected by the different optimizers in Figure 13 We find that RE discovers well-performing architectures which form clusters distinct from the architectures found via RS. We observe that COMBO searched previously unexplored areas of the search space. BANANAS, which found some of the best architectures. explores clusters outside the main cluster. However, it heavily exploits regions at the cost of exploration. We argue that this is result of the optimization of the acquisition function via random mutations based on the previously found iterates, rather than on new random architectures. DE is the only optimizer which finds well performing architectures in the center of the embedding space.
hhttps://bbbchi 11egee com/ Teaee ricerebaa
20

---

Published as a conference paper at ICLR 2022
C.5 INFLUENCE OF CELL TOPOLOGY AND OPERATIONS
In this section, we investigate the influence of the cell topology and the operations on the performance of the architectures our setting, The discovered properties of the search space inform our choice of metrics for the evaluation of different surrogate models.
First, we study how the validation error depends on the depth of architectures. Figure visualizes the per- formance distribution of normal and reduction cells of different depti by approximating empirical distri- butions with a kernel density estimation used violin plots (Hwang et al. 1994). We observe that the per- formance distributions are similar for the normal and
Validation accuracy
0.95
2
$1
reduction cells with the same cell depth. Although cells all depths can reach high performances, shal- lower cells
0.9
slightly favored. Note that these observations are subject to changes in the hyperpa- rameter setting, e.g. training for more epochs may render deeper cells more competitive. The best-found architecture features a normal and reduction cell of depth 4. Color-coding the cell depth in our t-SNE projection also confirms that the t-SNE analysis captures the cell depth well as a structural property It also reinforces that the search space is well-covered.
0.002
0.004
Standard deviation
Figure 8: Standard deviation of the val. accu- racy for multiple architecture evaluations.
(c.f. Figure 11
Validation error
normal
Cell Depth
0.2
reduction
4
0.1
DE
GDAS
DARTS
COMBO
PC_DARTS
TPE
DRNAS
RE
BANANAS RS
0.05
3
4
5
6
Cell depth
Figure 9: Distribution validation error for different cell depth.
Figure 10: Comparison between the normal and reduction cell depth for the architectures found by each optimizer.
also show the distribution normal and reduction cell depths each optimizer Figure I0 to get sense for the diversity between the discovered architectures. We observe that DARTS and BANANAS generally find architectures with shallow reduction cell and a deeper normal cell, while the reverse is true for RE. DE, TPE. COMBO and RS appear to find normal and reduction cells with similar cell depth.
Aside from the cell topology, architecture performance. The DARTS search space contains operation choices without parameters such Skip-Connection, Max Pooling 3 and Avg Pooling 3 3. We visualize the influence of these parameter-free free operations on the validation error in the normal and reduction cell in Figure 2 respectively Figure 14 While pooling operations in the normal cell seem to have negative impact on performance, a small number of skip connections improves the overall performance. This is somewhat expected, since the normal cell is dimension preserving and skip connections help training by improving gradient flow like in ResNets (He et al.) 2016). In the reduction cell, the number of parameter-free operations has less effect as shown Figure 14 contrast to the normal cell
also
dataset to study the influence of operations the
We follow the definition of cell depth used by Shu al. through the cell.
2020 i.c. the length of the longest simple path
21

---

Published as a conference paper at ICLR 2022
50
Normal Cell Depth
Architecture Ranking
2nd component
2nd component
50
40k
25
0
20k
-25
4
-50
-50
-50
0
50
50
50
1st component
1st component
Figure 11: t-SNE projection colored by the depth of the normal cell.
Figure 12: t-SNE visualization of the sampled architectures ranked by validation accuracy.
where 2-3 skip-connection. lead to generally better performance, the reduction cell shows no similar trend. For both cells, however, featuring many parameter-free operations significantly deteriorates performance. We therefore expect that good surrogate also models this case as poorly performing region.
C.6 TRAINING DETAILS
Each architecture was evaluated on CIFAR-10 (Krizhevsky) 2009) using the standard 40k, 10k, 10k split for train, validation and test set. The networks were trained using SGD with momentum 0.9, initial learning rate of 0.025 and a cosine anmealing schedule (Loshchilov Hutter 2017). annealing towards 10
We apply a variety of common data augmentation techniques which differs from previous NAS benchmarks where the training accuracy of many evaluated architectures reached 100% (Ying et al. 2019] Dong & Yang/ 2020) indicating overfitting on the training set. We used CutOut VDevs & Taylor 2017) with cutout length 16 and MixUp (Zhang al.) 2018) with alpha 0.2. For regularization. we used an auxiliary tower (Szegedy et al. 2015) with a weight of 0.4 and DropPath (Larsson et al. 2017) with drop probability of 0.2. We trained each architecture for 100 epochs with batch size of 96, using 32 initial channels and cell layers. We chose these values to be close to the proxy model used by DARTS while also achieving good performance.
C.7 NOISE IN ARCHITECTURE EVALUATIONS
Validation error
0.2
Num avg pool
discussed in Section the noise architec- ture evaluations can be large enough for surro- gate models to yield more realistic estimates of architecture performance than tabular bench-
Num max pool
Num skip conn.
0.1
mark based on a single evaluation per architec- ture. To study the magnitude of this noise Mur-NASS-Bench-DAAe
we evaluated 500 ar- chitectures randomly sampled from our Differ- ential Evolution (DE) (Awad et al. 2020) run with 5 different seeds each. We chose DE be- cause it both explored and exploited well; see Figure [3] We find mean standard deviation of 1.6e33for the final validation accuracy, which slightly less than the noise observed in NAS- Bench-101 (Ying et al. 2019); one possible reason for this could be a more robust training
0.05
0
7 8 Num operations
Figure 14: Distribution of validation error in depen- dence of the number of parameter-free operations in the reduction cell. Violin plots are cut off at the respective observed minimum and maximum value.
pipeline. Figure shows that, while the noise
tends to be lower for the best architectures, a correct ranking based on a single evaluation still difficult. Finally, compare the MAE when estimating the architecture performance from only one
22

---

Published as a conference paper at ICLR 2022
BANANAS
COMBO
DARTS
50000
40
20
0
-20
40
40000
DE
DRNAS
GDAS
40
20
-20
-3000
Architecture Ranking
-40
PC PC_TS
RE
40
200000
TPE
40
110000
-50
0
50
Visualization exploration of different parts of the architectural t-SNE embedding space for all optimizers used for data collection. The architecture ranking by validation accuracy (lower better) global over the entire data collection of all optimizers.
Figure 13:
sample to the results from Table I Here, also find slightly lower MAE of 1.38c-3 than for WAS-Bench-100
D
THE SURR-NAS-BENCH
DATASET
D.1 SEARCH SPACE
The FBNet (wu et al. 2019a) search space consists a sequence of stacked layers, out of which 22 need to be searched. The first and last three layers have fixed operations, while the rest can have one out total of candidate blocks. These include a skip connection "block" and the rest of the block choices are inspired by the MobileNetV2 (Sandler et al. 2018) and ShiftNet (Wu et al. 2018). Their strructure contains a point-wise x convolution, a K x K depthwise convolution where denotes the kernel size, and another 1xl convolution. ReLU is applied only after the first 1x1 convolution and the depthwise convolution, but not after the last Ix1 convolution. A skip connection adding the input the output is used if the output dimension remains the same the input one. Overall, the
23

---

Published as a conference paper at ICLR 2022
block choices are: {k3_ el, 133 Aa__e_2__3__________ k3 ___ k5 _55_e1, k5 15__k___e k k5_e3,,__, k5 _5__6, skip), where denotes the kernel size, e the expansion ratio and g if group convolution is used.
D.2 TRAINING DETAILS
Each architecture was evaluated on CIFAR-I00 (Krizhevsky 2009) using the standard 40k, 10k, 10k split for train, validation and test set. The networks were trained using SGD with momentum 0.9, batch size 256, initial learning rate 0.025, L2 regularization with 0.0005 coefficient and a cosine annealing (Loshchilov & Hutter 2017) schedule towards O. We furthermore apply sharpness minimization (Foret et al. 2021 for better generalization. We also apply label smoothing with a smoothing factor of 0.1.
E SURROGATE MODEL ANALYSIS
PREPROCESSING OF THE GRAPH TOPOLOGY
DGN preprocessing DGN were implemented using PyTorch Geometric (Fey Lenssen 2019 which supports the aggregation of edge attributes. Hence, architecture cells, by assigning the embedded operations to the edges. The nodes are labeled as input, intermediate and output nodes. We represent the DARTS graph shown in Figure 15| by connecting the output node of each cell type with the inputs of the other cell, allowing information from both cells be aggregated per node during message passing. Note the self-loop on the output node of the normal cell, which we found necessary to get the best performance.
naturally represent the DARTS
Preprocessing for other surrogate models Since we make of the framework implemented by BOHB (Falkner et al.) 2018) to easily parallelize the architecture search algorithms across many compute nodes, we also represent our search space using ConfigSpace LLindauer et al. 2019). More precisely, we encode each pair of incoming edges for a cell as one choice of a categorical parameter. For instance, for node in the normal cell, we add parameter i inputs. setttsss_eee___ee_eeeeeeee
with the
choices of edge pairs 0_1, 0 0_2,, 2,0 0_3,0_33__00_ 3, 1_ 1_3, 2_3. The edge operations are then implemented as categorical parameters for each edge and are only active if the corresponding edge was chosen. For instance, in the example above, if the incoming edge 0 is sampled, the parameter associated with the edge from node to node becomes activate and one operation is sampled. We provide the configuration space with code. For all non-DGN based surrogate models, vector representation configuration given by ConfigSpace as input to the model. This vector representation contains value between and for each parameter in the configuration space.
use the
E.2 DETAILS ON THE GIN
Normal
The GIN implementation on the Open Graph Bench- mark (OGB) (Hu et al. 2020) uses virtual nodes (ad- ditional nodes which connected to all nodes in the graph) to boost performance as well as generalization and consistently achieves good performance their public leaderboards. Other GNNs from Errica et al. (2020), such DGCNN and DiffPool, performed worse in our initial experiments and are therefore not considered.
Reduction
Following recent work in Predictor-based NAS (Ning) al., 22200) Xu et al. 2019b), we use per batch ranking loss because the ranking of an architecture is intermediate nodes in blue and outputs red. equally important to an accurate prediction of the validation accuracy in a NAS setting. We use the ranking loss formulation by GATES (Ning et al. 2020) which is hinge pair-wise ranking loss with margin m=0.1.
Figure 15: Architecture with inputs in green,
httts://gi
/Confi gSpace)
24

---

Published as a conference paper at ICLR 2022
True Benchmark
GIN Surrogate Benchmark
XGB Surrogate Benchmark
Dest validetion etror athieves
x 10
BANANAS
RE
Xx
60
1x
10"
1007
10"
10'
10
10a
10
10'
10
10a
10"
30
10'
Wallclock Time
Simulated Wallclock Time [s]
Simulated Wallclock Time
Figure 16: Anytime performance of blackbox optimizers, comparing performance achieved on the real benchmark and on surrogate benchmarks built with GIN and XGB in an LOO0 fashion.
E.3 DETAILS ON HPO
All detailed table for the hyperparameter ranges for the HPO and the best values found by BOHB are listed in Table We used fixed budget of 128 epochs for the GNN, minimum budget of 4 epochs and maximum budget of 128 epochs for the MLP and a fixed budget for all remaining model.
E.4 HPO FOR RUNTIME PREDICTION MODEL
Our runtime prediction model is LGB model trained on the runtimes of architecture evaluations of DE. This is because we partially evaluated the architectures utilizing different CPUs. Hence, we only choose to train on the evaluations carried out by the same optimizer on the same hardware to keep a consistent estimate of the runtime. DE is good choice in this case because it both explored and exploited the architecture space well. The HPO space used for the LGB runtime model is the same used for the LGB surrogate model.
E.5 LEAVE ONE-OPTIMIZER OUT ANALYSIS
The results in Table 7 for SNB-DARTS show that the rank correlation between the predicted and observed validation accuracy remains high even when a well-performing optimizer such as RE is left out. A detailed scatter plot of the predicted performance against the true performance for each optimizer and surrogate model in an LOOO analysis is provided in Figure [8 and Figure [9 Predicting BANANAS in the LOOO fashion yields a lower rank correlation, because predominantly selects well-performing architectures, which are harder to rank; however, the high R²2 shows that fit is still good. Conversely, leaving out DARTS causes low R but still high rank correlation; this due to architectures with many skip connections the DARTS data that are overpredicted.
The surrogates extrapolate well enough these regions to identify that they contain poor architectures that rank worse than those in other areas of the space (which is the most important property we would like predict correctly); but without having seen training data of extremely poor architectures with many skip connections they cannot predict how bad exactly these architectures are.
This can be improved by fitting the surrogate on data that contains more such architectures, something we study further in Appendix F.T
To avoid poor predictions in such boundary cases, in our guidelines for creating surrogate NAS benchmarks (Appendix GG) we recommend adding architectures from known areas of poor performance the training data.
E.6 PARAMETER-FRIE OPERATIONS
Several works have found that methods based on DARTS (Liu et al. 2019) are prone to finding sub-optimal architectures that contain many, even only, parameter-free free operations (max. pooling, avg. pooling or skip connections) and perform poorly (Zela et al. 2020a). We therefore evaluated the surrogate models on such architectures by replacing random selection of operations in cell with one type of parameter-fe free operations to match a certain ratio of parameter- -free operations in a cell. This analysis is carried out over the test of the surrogate models and hence contains architectures
25

---

Published as a conference paper at ICLR 2022
Default Value
Model
Hyperparameter
Range
Log-trann Log-transform
Hidden dim.
[16. 256]
true
24
Num. Layers
[2, 10]
false
Dropout Prob.
[0, IJ
false
0.035
Learning
[1c-3, 1c-2]
0.0777
Learning rate min.
const.
0.0
GIN Batch size
const.
51
Undirected graph
[truc, falsc]
false
Pairwise ranking loss
[tre,, fulse]
true
Self-Loops
ttuee false]
Loss log transform
[true, false]
true
Node degree one-hot
true
Num. Layers
[1, 10]
Layer width
[16, 256]
true
31
Dropout Prob.
const.
0.0
BANANAS
Learning rate
[le-3, le-1]
true
0.0021
Learning rate min.
const.
0.0
Batch size
[16. 128]
122
Loss log transform
[true, falke]
Pairwisc ranking loss
ttuee false]
false
Early Stopping
Rounds
const.
100
Booster
gbtree
Max. depth
[1. 15]
false
13
Min. child weight
[1. 100]
true
39
XGBoost
Col. sample hylevel
[0.0, 1.0]
false
0.6909
sample bytree
[0.0, 1.0]
false
lamhda
[0.001, 1000]
31,3933
alpha
[0.001, 1000]
true
0,2417
Learning rate
[0.001,
truc
0.00824
Early stop. rounds
100
Max. depth
[1]
false
18
Num. leaves
[10, 100]
false
40
Max. bin
(100,400]
false
336
Feature Fraction
[0.1. 1.0]
false
0.1532
LGBoost
Min. child weight
[0.001, 10]
true
0,5822
Lambda L1
[0.001, 1000]
0.0115
Lambda 1.2
[0.001, 1000]
true
134.5075
Boosting type
const.
gbdi
Learning rate
[0.001, 0.1]
true
0.0218
Num. estimators
[16. 128]
truc
116
Min. samples split.
[2. 20)
false
Random
Min. samples leaf
[1, 20]
false
Forest
Max. features Bootstrap
[0.1, 1.0]
false
0.1706
[true, false]
false
[1.0. 20.0]
true
3,066
enef. 0
[-0.5, 0.5]
false
0.1627
degree
[1. 128]
true
epsilon
(0.01.0.99)
true
0.0251
gamma kernel shrinking tol
[scale, auto]
auto
[linear, rbf, poly, sigmoid)
sigmoid
[truc, false]
false
[0.0001, 0.01]
0.0021
[1.0, 20.0]
truc
5,3131
cuef. 0 degree
[-0.5, 0.5]
false
-0.3316
[1. 128]
true
128
gamma
[scale. auto]
scale
μ-SVR
kernel
[lineur, rbf, poly, sigmoid]
rbf
nu shrinking
[0.01, 1.0]
false
0.1839
[true, false]
true
[0.0001, 0.01]
Table 6: Hyperparameters of the surrogate models and the default values found via HPO. The "Range" column denotes the ranges that the HPO algorithm used for sampling the hyperparameter values and the "Log-traue -oog-rransform column if sampling distribution was log- log-transformed not.
26

---

Published as a conference paper at ICLR 2022
Model
No RE:
No DE
No COMBO
No TPE:
No BANANAS
No DARTS
No PC DARTS
No DeNAS
No GDAS
LGB
0.917
0.892
0.919
0.857
0,909
-0.093
0.826
0.699
0.429
21a
XGB
0.907
0.888
0.876
0,842
0,911
-0.151
0.817
0.631
0.672
GIN
0.856
0,864
0.775
0.789
0.881
0.115
0.661
0.790
0,572
LGB
0.834
0,782
0,833
0.770
0.592
0,780
0.721
0.694
0.595
0.780
GIN
0.798
0.757
0.737
0.718
0.567
0.765
0.645
0.706
0.607
Table Leave One-Onne-neeeeeeeee Oett--ppimii-Ouut performance of the best surrogate models. Note that the config- urations sampled by DARTS are mostly composed with skip connections (Zela al. (2200a), but still the surrogate manages to rank them fairly good (high sKT) even though not providing a good estimate of the accuracy.
collected by all optimizers. For a more robust analysis, we repeated this experiment times for each ratio of operations to replace.
shows that both the GIN and the XGB model correctly predict that the accuracy drops with too many parameter-free operations, particularly for skip connections. The groundtruth of architectures with only parameter-free operations is displayed XGB captures the slight performance improvement of using a few skip connections better. LGB failed to capture this trend but performed very similarly to XGB for the high number of parameter-free free operations.
Results Figure 21
scatter plot. Out of the two models,
X
E.7 CELL TOPOLOGY ANALYSIS
sKendall Tau
0.80
Furthermore, we analyze how accurate changes in the cell topology (rather than in the oper- ations) are modeled by the surrogates. We collected groundtruth data by evaluating
0.75
GIN
X
Ih [k+1)k 180 different cell topologies
LGB
0.70
(not accounting for isomorphisms) with fixed sets of operations. We assigned the same ar- chitecture the normal and reduction cell, to focus on the effect of the cell topology. We sampled 10 operation sets uniformly at random, leading to 1800 architectures groundtruth for this analysis.
XGB
3
6
Cell Depth
Comparison between GIN, XGB and LGB in the cell topology analysis.
Figure 17:
We evaluated all architectures and group the results based on the cell depth. For each of the possible cell depths, we then computed the sparse Kendall т rank correlation between the predicted and true validation accuracy.
Results of the cell topology analysis are shown in Figure 17 We observe that LGB slightly outperforms XGB, both of which perform better on deeper cells. The GIN performs best for the shallowest cells.
Results
F BENCHMARK ANALYSIS
F.1 ONE-SHOT TRAJECTORIES
Surrogate NAS benchmarks, like Www--NAA--Becc--AARTTE can also be used to monitor the behavior of one-shot NAS optimizers throughout their search phase, by querying the surrogate model with the currently most promising discrete architecture. This can be extremely useful in many scenarios since uncorrelated proxy (performance of the one-shot model) and true objectives (performance of the fully trained discretized architecture) can lead to potential failure modes, e.g., to a case where the found architectures contain only skip connections in the normal cell (Zela et al., 2020a b) Dong & Yang 2020) (we study such a failure case in Appendix F. to ensure robustness of the surrogates in said case). We demonstrate this case in similar LO00 analysis for the black-box optimizers,
27

---

Published as a conference paper at ICLR 2022
GIN
LGB
XGB
95
DARTS True
90
85
95
BANANAS
True
90
85
95
COMBO
True
90
85
95
DE
True
90
85
95
RE
True
90
85
85
90
95
85
90 Predicted
95
85
90
95
Predicted
Predicted
Figure 18:
Scatter plots of the predicted performance against the true performance of different surrogate models on the test set in Leave-One- Seave--ne-Optimizer- Out setting.
28

---

Published as a conference paper at ICLR 2022
GIN
LGB
XGB
95
TPE
True
90
85
95
PC DARTS
True
90
85
95
GDAS
True
90
85
95
DRNAS
True
90
85
85
90
95
85
90 Predicted
95
85
90 Predicted
95
Predicted
Figure 19; (continued) Scatter plots of the predicted performance against the true performance of different surrogate models on the test set in LeaveOne-Oppimizer-- setting.
29

---

Published as a conference paper at ICLR 2022
using evaluations of the discrete architectures from each search epoch of multiple runs of DARTS, PC-DARTS and GDAS as ground-trus truth. Figure 22 shows that the surrogate trajectories closely resemble the true trajectories.
To obtain groundtruth trajectories for DARTS, PC-DARTS and GDAS, we performed 5 runs for each optimizer with 50 search epochs and evaluated the architecture obtained by discretizing the one-shot model at each search epoch. For DARTS, in addition to the default search space, we collected trajectories the constrained search spaces from Zela et al. (2020a) cover a failure case where DARTS diverges and finds architectures that only contain skip connections in the normal cell. To show that our benchmark able to predict this divergent behavior, we show surrogate trajectories when training on all data, when leaving out the trajectories under consideration from the training data, and when leaving out DARTS data in Figure 20
All data
LOTO
LOO0
0.10
0.10
0.30
GIN
0.00
0.00
0.08
0.07
0.07
0.07
0.05
0.05
0.05
0.05
Epochs
Epochs
Epochs
Figure 20: Ground truth (GT) and surrogate trajectories on constrained search space where the surrogates are trained with all data, leaving out the trajectories under consideration (LOTO), and leaving out all DARTS architectures (LO00).
0.2 Num avg pool Num max pool Num skip conn.
Validation error
0.2
avg.
0.2
Num. avg. pool
Num. max pool
Num. max pool
slip conn.
Num. slip conn.
Validation
Validation
0.1
0.1
0.05
0.05
0
1 2
6 (c) XGB
3
Num operations
Num. operations
Num, operations
(a) Surr-NAS CAAS-Benc--D Bench-DARTSS
(b) GIN
Figure 21: (Left) Distribution of validation error in dependence of the number of parameter-free operations the normal cell the of the GIN and XGB surrogate model. The collected groundtruth data is shown as scatter plot. Violin plots are cut off the respective observed minimum and maximum value.
dataset. (Middle and Right) Predictions
True Benchmark
GIN Surrogate Benchmark
XGB Surrogate Benchmark
0.09
DARTS PC GDAS
0.08
0.07
0.06
0.05
10
20
30
40
50
0
10
20
30
40
50
10
20
30
40
50
Epochs
Epochs
Epochs
Figure 22: Anytime performance of one-shot optimizers, comparing performance achieved on the real benchmark and surrogate benchmarks built with GIN and XGB in LOO0 fashion.
30

---

Published as a conference paper at ICLR 2022
While the surrogates model the divergence in all cases, they still overpredict the architectures with only skip connections in the normal cell especially when leaving out all data from DARTS. The bad performance of these architectures is predicted more accurately when including data from other DARTS runs. This can be attributed to the fact that the surrogate models have not seen any, respectively very few data, in this region of the search space. Nevertheless, it is modeled bad-perforning region and we expect that this could be further improved on by including additional training data accordingly, since including all data in training shows that the models are capable of capturing this behavior.
ABLATION STUDY: FITTING SURROGATE MODELS ONLY ON WELL-PERFOOR PERFORMING REGIONS F.2
OF THE SEARCH SPACE
To assess whether fitted GIN ensemble and an XGB ensemble model only on architectures that achieved a validation accuracy above 92%. We then tested on all architectures that achieved a validation below 92%.
architectures are important for the surrogate benchmark, we
Indeed, we observe that the resulting surrogate model overpredicts accuracy in regions of the space with poor performance, resulting a low R² of -0. 142 and sparse Kendall tau of 0.293 for the GIN. The results for one member of the GIN ensemble are shown in Figure 23 The XGB model achieved similar results. Next, to study whether these weaker surrogate models can still be used to benchmark NAS optimizers, benchmarks based on these surrogate models. Figure 25 shows that these surrogate models indeed suffice accurately predict the performance achieved by Random Search and BANANAS function of time.
also studied optimization trajectories of NAS optimizers surrogate
F.3 ABLATION STUDY: FITTING SURROGATE MODELS ONLY WITH RANDOM DATA
In this section, we would like to take the Conpe--On-Opimmzzer-Oo analysis from Sec- tion 3.1.7 one step further by leaving out all architectures that were collected from NAS optimizers other than random search. While the LOO0 analysis removes some "bias" from the benchmark ("bias" referring its precision a subspace), there still is possibility that different optimizers used explore similar subspaces, and leaving out one of them still yields "bias" induced from similar optimizer used for generating training data. For instance, the t-SNE analysis from Figure 13 suggests that some optimizers ex- ploit very distinct regions (e.g.. BANANAS and DE) while others exploit regions somewhat similar to others (c.g.. RE and PC-DARTS). The exploration behavior, on the other hand, quite similar across optimizers since most of them perform random sampling in the beginning. Thus, in the following, we investigate whether we can create benchmark that has no prior information about solutions any optimizer might find.
95
90
True
85
80
75
89
90
91
92
93
94
Predicted
Figure 23: Scatter plot of GIN predictions on archi- tectures that achieved below 92% validation accuracy.
To that end, we studied surrogate models based i) only on the 23746 architectures explored by random search and ii) only on 23 746 (47.3%) architectures of the original training set (sampled in a stratified manner, i.e., using 47.3% of the architectures from each of our sources of architectures).
First, we investigated the difference the predictive performance of surrogates based on these two different types of architectures. Specifically, we fitted our GNN and XGB surrogate models different subsets of the respective training sets and assess their predictions on unseen architectures from all optimziers as test set. Figure 24 shows that including architectures from optimizer trajectories in the training set consistently yields significantly better generalization.
Next, we also studied the usefulness of surrogate benchmarks based the 23 746 random architec- tures, compared to surrogate benchmarks based on the 23 746 architectures sampled a stratified manner from the original set of architectures. Specifically, we used them to assess the best per-
31

---

Published as a conference paper at ICLR 2022
formance achieved by various NAS optimizers function of time. Comparing the trajectories in Figure 3 (based on purely random architectures for training) and Figure 26 (based on 23 746 architectures sampled in stratified manner), we find that the surrogates fitted only random architectures work just as well as the surrogates that use architectures from NAS optimizers.
GNN GIN RS
XGB RS
GNN GIN mixed
XGB mixed
95
R = 0.57
2 T 0.67
R = 0.73 T= 0.72
R² = 0.65
Train ratio 5%
94
T= 0.67
T= 0.67
True
92
91
95
Train ratio 20%
R = 0.73
R = 0.67
R = 0.81
2²= = 0.83
94
T= 0.72
0.72
T 0.76
0.77
True
93
91
95
Train ratio 60%
R = 0.75
R² 0271
R 0.84 T= 0.79
0.87 T= 0.82
T= 0.75
T= 0.75
True
93
92
95
Train ratio 80%
R = 0.73
R² = 0.72 T= 0.76
R² 0.86 T= T= 0.79
R² 0.90 T 0.85
94
T= 0.75
True
92
91
Train ratio 100%
R² = 0.75
R² = 0.73
R² 0.87
R² 0.90 T= 0.85
94
T 0.75
T 0.76
T 0.80
True
93
91
92
94
92
94
92
94
92
94
Predicted
Predicted
Predicted
Predicted
Figure 24: Scatter plots of the predicted performance against the true performance of the GNN GIN/XGB surrogate models trained with different ratios of training data. "RS" indicates that the training set only includes architectures from random search, "mixed" indicates the training set includes architectures from all optimizers. Training set sizes are identical for the two cases. The test set contains architectures from all optimizers. For better display, we show 1000 randomly sampled architectures (blue) and 1000 architectures sampled from the top 1000 architectures (orange). For each case also show the R² and Kendall-r coefficients the whole test set.
32

---

Published as a conference paper at ICLR 2022
BANANAS
RS
Best validation error achieved
x 10"2
True
8 10-2
GIN
XGB
7x
6 10-2
x 10-2
104
10 Wallclock Time [s]
10
107
104
10
10
107
Simulated Wallclock Time [s]
Figure 25: Comparison between the observed true trajectory of BANANAS and RS with the surrogate benchmarks only trained on well performing regions of the space
True Benchmark
GIN Surrogate Benchmark
XGB Surrogate Benchmark
Best valication error achieved
10
8 80-1
TPE
BANANAS
60
-0-2
10a
107
10a
10
10a
104
10a 10a 10"
Wallclock Time [s]
Simulated Wallelock Time [s]
Simulated Wallclock Time [s]
Figure 26: Anytime performance of different optimizers on the real benchmark (left) and the surrogate benchmark (GIN (middle) and XGB (right)) when training ensembles on 47.3% of the data collected from all optimizers. Trajectories the surrogate benchmark are averaged over 5 optimizer runs.
Given this positive result for surrogates based purely random architectures, we conclude that is indeed possible to create surrogate NAS benchmarks that are by design free bias towards any particular NAS optimizer (other than random search). While the inclusion of architectures generated with NAS optimizers in the training set substantially improves performance predictions of individual architectures, realistic trajectories of incumbent performance as function of time can also be obtained with surrogate benchmarks based solely on random architectures. We note that the "unbiased"" benchmark could possibly be further improved by utilizing more sophisticated space-filling sampling methods, such as the ones mentioned in Appendix C.2 or by deploying surrogate models that extrapolate well.
F.4 EVALUATING THE SURROGATE BENCHMARK BUILT ON THE NAS BENCH- 101 DATA
True Benchmork
Surrogate Benchmark
19
10a1
Test regret
rogret
10-2
10-2
13
107
10a
107
2.00
112
10'
walcclock
spellctoct
Figure Anytime performance RE and RS on the tabular NAS-Benchh benchmark (left) and on the surrogate benchmark version of it using the GIN model (right).
33

---

Published as a conference paper at ICLR 2022
In this section run both regularized evolution (RE) and random search (RS) on the tabular WAS-Beench 101 (Ying et al. 2019) benchmark and on the surro- gate version of it, that we construct by fitting the GIN surrogate subset of the data available in NAS- Bench-101. Note that we had to make some changes the GIN in order to be consistent with the graph representation in MAS-Bench- 101, i.e. operations being nodes, rather than in the edges of the graph. We also did tune the hyperparameters of the GIN on separate validation set using BOHB (Falkner et al. 2018). In Figure 27 we plot the RE and RS incumbent trajectories, when ran on both the tabular NAS-Bench- 101 benchmark (left plot) and on the GIN surrogate version of (right plot). The axis shows the test regret of the incumbent trajectories. As we can see, even though the performance is slightly overestimated by the surrogate benchmark in the very end of the curves, the ranking is still preserved.
Spearman correlation coeff.: 0.8948
0.28
True validation error
0.26
0.24
0.22
0.22
0.24 0.26
Predicted validation error
Figure 28: Scatter plot showing the predicted validation error by the XGBoost model of the configurations in the incumbent trajectory of one RE run (1000 function evaluations) on SNB-FBNet (x axis) vs. the true validation error values of the same configurations when retrained from scratch (y axis).
F.5 RETRAINING THE INCUMBENT TRAJECTORIES THE SURROGATE BENCHMARK
In Figure 28 we plot the predicted validation error by the XGBoost model of the configurations in the RE incumbent trajectory (one of the red lines in Figure 5 right plot) on SNB-FBNG when retrained from scratch. As one can see the ranking still preserved (Kendall Tau correlation coefficient of 0.73 and Spearman rank correlation coefficient of 0.895) even though the performance is slightly overestimated for some configurations at the end of the trajectory.
vs. the true validation error values of the same configurations
G GUIDELINES FOR CREATING SURROGATE BENCHMARKS
In order help with the design of realistic surrogate benchmarks in the future, provide the following list of guidelines:
Data Collection: The data collected for the NAS benchmark should provide (1) a good overall coverage, (2) explore strong regions of the space well, and (3) optimally also cover special areas in which poor generalization performance may otherwise be expected. We would like to stress that depending on the search space, a good overall coverage may already be sufficient to correctly assess the ranking of different optimizers, but as shown in Appendix [F3 additional architectures from strong regions of the space allow to increase the fidelity of the surrogate model.
1. A good overall coverage can be obtained by random search (as in our case), but one could also imagine using better space-filling designs or adaptive methods for covering the space even better. In order to add additional varied architectures, one could also think about fitting one or surrogate models to the data collected thus far, finding the regions of maximal predicted uncertainty, evaluate architectures there and add them to the collected data, and iterate. This would constitute an active learning approach.
2. convenient and efficient way to identify regions of strong architectures run NAS methods. In this case, the found regions should not only be based on the strong architectures one NAS method finds but rather on set strong and varied NAS methods (such as, our case, one-shot methods and different types of discrete methods, such as Bayesian optimization and evolution). order to add additional strong architectures, one could also think about fitting one or more several surrogate models to the data collected thus far, finding the predicted optima of these models, evaluate and add them to the collected data and iterate. This would constitute a special type of Bayesian optimization.
3. Special areas in which poor generalization performance may otherwise be expected may, in our case, e.g., include architectures with many parameterless connections, and in particular, skip connections. Other types of encountered failure modes would also be useful to cover.
34

---

Published as a conference paper at ICLR 2022
Surrogate Models: As mentioned in the guidelines for using surrogate benchmark (see Section 5 benchmarking an algorithm that internally uses the same model type as the surrogate model should be avoided. Therefore, to provide benchmark for diverse set of algorithms, we recommend providing different types of surrogate models with a surrogate benchmark. Also, in order to guard against possible of "bias" in surrogate benchmark (in the sense of making more accurate predictions for architectures explored by particular type of NAS optimizer), we recommend to provide two versions of surrogate: one based on all available training architectures (including those found by NAS optimizers), and one based only on the data gathered for overall coverage.
Verification: As a means to verify surrogate models, we stress the importance of leave-one- optimizer-out experiments both for data fit and benchmarking, which simulate the benchmarking "'unseen optimizers.
Since most surrogate benchmarks will continue grow for some time after their first release, to allow apples-to-apples comparisons, we strongly encourage to only release surrogate benchmarks with version number.
In order to allow the evaluation of multi multi-objective NAS methods, we encourage the logging of as many relevant metrics of the evaluated architectures other than accuracy as possible, including training time, number of parameters, and multiply-adds.
Alongside a released surrogate benchmark, we strongly encourage to release the training data its surrogate(s) constructed on, well as the test data used to validate it.
In order to facilitate checking hypotheses gained using the surrogate benchmarks in real experiments, the complete source code for training the architectures should be open-sourced alongside the repository, allowing to easily go back and forth between querying the model and gathering new data.
H REPRODUCIBILITY STATEMENT
For our reproducibility statement, the "NAS Best Practices Checklist" (Lindauer & Hutter 2020 which was recently released to improve reproducibility neural architecture search.
1. Best Practices for Releasing Code
For all experiments you report:
(a) Did you release code for the training pipeline used evaluate the final architectures? [Yes] Follow link in the footnote of page 2 (Section I. The training pipeline and hyperparameters used train the architectures are clearly specified in the corresponding scripts.
(b) Did you release code for the search space Yes]] The used search spaces are the ones from DARTS (Liu et al. 2019) and FBNet (Wu et al. (019a).
(c) Did you release the hyperparameters used the final evaluation pipeline, as well as random seeds? [Yes] Follow link in the footnote of page 2 (Section T). We released our code, which includes the seeds and final evaluation pipeline used. The hyperparameters for training the architectures are fixed, while the ones for training the surrogate models are optimized using BOHB (Flknnrr et al. 2018).
(d) Did you release code for your NAS method? [Yes] All of our code for benchmarking NAS methods is available by following the same link to the codebase.
(e) Did you release hyperparameters for your NAS method, well random seeds? [Yes] The hyperparameters we used are also available.
2. Best practices for comparing NAS methods
(a) For all NAS methods you compare, did you use exactly the same NAS benchmark, including the same dataset (with the same training-test split), search space and code for training the architectures and hyperparameters for that code? [Yes] Refer to Section for details.
(b) Did you control for confounding factors (different hardware, versions of DL libraries, different runtimes for the different methods)? [Yes] We trained all the architectures the same GPU (Nvidia RTX2080 Ti) and used the same versions of the used libraries run all NAS methods.
35

---

Published as a conference paper at ICLR 2022
(c) Did you run ablation studies? [Yes] We show ablation studies in Section 3.1.8
(d) Did you use the same evaluation protocol for the methods being compared?? [Yes]
(e) Did you compare performance over time? [Yes] We typically compare the anytime performance of black-box NAS optimizers for a specified time budget. See the figures Section 3 for examples.
(f) Did you compare to random search? [Yes] We did include random search in our experiments in Section and data collection.
g Did you perform multiple runs of your experiments and report seeds? [Yes] We run the black-box optimizers on the surrogate benchmark multiple times and average the results.
(h) Did you use tabular or surrogate benchmarks for in-depth evaluations? [Yes] This is in fact the main purpose of our paper: to introduce realistic surrogate NAS benchmarks.
3. Best practices for reporting important details
(a) Did you report how you tuned hyperparameters. and what time and resources this required? [Yes] We reported this information Section 3.1.3
(b) Did you report the time for the entire end-to-end NAS method (rather than, e.g., only for the search phase)? [Yss] Our results the end-to-end time.
(c) Did you report all the details of your experimental setup? [Yes] We did include all details of the setup in Section 3
36


Reviews:
[{"review_id": "zmcgkPe5Vwo", "reviewer": "Reviewer_t8ZB", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros. \n1. the authors have made several significant improvement over the past submission and I'm happy to see that. Compared to the prior submission, the authors have included results on CIFAR10, CIFAR100, and ImageNet. I thank authors for doing that, however, there is still some concerns for me to see this work get published.\n\nCons:\n1. Apparently this work is using black box optimization to perform NAS. However the selected benchmark baselines are pretty old. I'd suggest authors taking a look at the recent public benchmark results from here: https://bbochallenge.com/ (the black box optimization challenges held at NeurIPS 2021). And update the paper accordingly to track the recent advance in the field. Essentially NAS is no different from those test functions.\n2. All the results are plotted by the wall time, which is a bit tricky in NAS. The costs of querying a surrogate model can be cheap, but sample-efficiency (#samples over accuracy) is far more important to NAS as the cost of evaluations are the main bottleneck, not the search. Please correct me if I'm wrong, but I don't think you consider the cost of evaluations in the wall time.\n3. Please diversify the tasks. Here I mean different tasks, e.g. detection or segmentation, rather than image recognition with different datasets and models. \n\n\n\n", "summary_of_the_paper": "Overview: This work proposes a new NAS benchmark based on the results of surrogate models prediction. This surrogate model is able to predict all architectures in DARTS search space, which is about 10^18 possible architectures. The author compared the predict performance among different type of surrogate models and also leveraged surrogate models to investigate different NAS methods.", "summary_of_the_review": "I have been reviewing this paper for a few times, and I appreciate the effort that the authors have put to update the paper. However, the current draft can not truly reflect the recent advancement in the field, and it may mislead the future. Once the author have address my concerns 1, 2, I'm open to accept this paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tmNLCXiWNwV", "reviewer": "Reviewer_yTPb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Overall, the paper is well-written but it does not contain significant contributions.\nThe two main contributions are the use of a surrogate to create a surrogate benchmark and the creation of an interesting new search space for NAS.\n\nI see little contribution of demonstrating how to create a surrogate benchmark for NAS. This has been done earlier for hyperparameter optimization as pointed out by the authors themselves and NAS is nothing but a specific type of hyperparameter optimization. Additionally, Yan et al. presented with their paper \"NAS-Bench-x11 and the Power of Learning Curves\" already one way to create surrogate benchmarks for NAS.\nWhile the authors claim that a larger search space might be of huge interest for the community, no evidence for this claim was provided. There is no reason to believe that a larger search space is more interesting than a smaller one if not chosen correctly. Furthermore, the search space considered (among others) is the DARTS search space which is well-known and well-explored by the community. Datasets such as CIFAR-10 and CIFAR-100 are used in many NAS papers and the community is already overfitting to these tasks such that they started looking for more challenging problems. Concluding, I do not see this benchmark to be particularly useful.\n\nThe authors don't discuss all the shortcomings of their benchmark. It is important to point out that the most efficient NAS methods do not evaluate an architecture completely. Methods such as DARTS or Hyperband search differently and it seems like that these methods cannot be evaluated on this benchmark. While methods exist that evaluate architectures completely, they have no practical purpose since they are simply too expensive to run.\n\nA comment on societal impact: The authors claim that millions of GPU hours will be saved and carbon emissions will be reduced. This is a bold statement and not supported by any evidence. What we have learned from the very first NAS benchmark is that it led to more and more NAS benchmarks, only spending more GPU hours. If the authors want to take the societal impact section seriously, they should consider the risk that they have potentially wasted energy and hardware for no reason.", "summary_of_the_paper": "The authors present another benchmark tabular benchmark for neural architecture search. In contrast to most other works, only few architectures are actually trained while the remaining ones are imputed using a regression model.", "summary_of_the_review": "Overall a well-written paper with no significant novelties. The presented benchmark does not seem to be a useful addition to the vast amount of already existing benchmarks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YNuPtfi7x1_", "reviewer": "Reviewer_1eb8", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Pros:\n- **Clear motivation**: This work addresses 1) the limitations of small tabular benchmarks, 2) the expensive time and compute cost of large non-tabular search space. For instance, 60k models are sampled from the DARTS search space and their performance are predicted using the surrogate model. This creates a tabular benchmark which is much bigger than NAS-Bench-2.\n- **Comprehensive analysis**: The paper has considered potential issues of using surrogate models and has proposed ways to work around them. For example, to yield good coverage of the search space and to train a strong surrogate model, a sampling scheme is used to collect models by random search as well as high performing models by 10 NAS methods.\n- **Guidline for future research**: The paper summarizes several best practices to create surrogate NAS benchmarks for new search spaces. It is particular important as there are many promising architectures that are not currently covered in DARTS, or NAS-Bench-1/2. For example, research in transformer-like architectures are increasingly popular. This paper provides a feasible method to fast evaluate new search spaces.\n\nCons:\n- **Search trajectories**: The paper has done lots of experiments to show that the search trajectories running on the surrogate benchmark closely resemble the ground truth. However, it is unclear if the searched models (via surrogate and via ground truth) are also similar. For example, a surrogate may underestimate the error of certain region of the search space, and the NAS method may be guided to favour models in that region. Even though the search trajectory may look right, the models explored could be different from the ground truth. If you take the models searched by different NAS methods on SNB-DARTS and train them, do they still preserve the same ranking?\n- **Performance on unseen models**: In SNB-DARTS, 60k architectures are sampled and 0.8 of them are used to train the surrogate model. Since the search is performed on the same 60k search space, it is not suprising for the surrogate model to perform well. How about the unseen models in the DARTS search space? Similarly, NAS-Bench-1 has 423k architectures, which is bigger than SNB-DARTS. Any insight on how SNB-NAS-Bench-1 compare to the tabular NAS-Bench-1?", "summary_of_the_paper": "The authors propose a method to create surrogate benchmark for NAS. By modelling and predicting the performance of neural architecture in the search space, a much larget search space can be covered without expensive training.", "summary_of_the_review": "Overall, the paper is very well written. It is clearly motivated and supported by lots of ablation studies. The dataset and search space might not be SOTA, but it does provide a promising practice for future NAS research. There are a few questions that I would like the authors to clarify, otherwise, I would recommend acceptance of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "H2gRPgnGllU", "reviewer": "Reviewer_pRnV", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "In general, this is a good NAS paper that explored a new direction -- surrogate NAS benchmarks. I believe this work stand between 8 and 10. Please see my detailed comments below.\n\nStrengths:\n- In this work, the authors proposed a novel family of NAS benchmark -- surrogate NAS benchmark. This can break the limitations of existing NAS benchmarks -- the search space is unrealistically small.\n- The effectiveness and usability of the proposed new surrogate NAS benchmarks have been systemically evaluated and analyzed.\n- This work brings some fresh ideas and artifacts to the NAS community. Given various bottlenecks, the development of the NAS research is significantly slowed down. This work can potentially help bring some new insights.\n- Section 2 is interesting that the surrogate model can yield strong/better predictive performance than standalone training.\n- All codes have been released.\n- We can see many NAS benchmarks were accepted in the top venues this year. The contribution, novelty, analysis of this work is above the most recent published NAS benchmarks.\n\nWeakness:\n- As surrogate HPO benchmarks have been proposed, it would be good to have a deep analysis on the comparison with that.\n- I do not find other clear weaknesses.\n\nMinor issues:\n- In the first paragraph, the authors cited (Hao, 2019) for carbon emissions. A more proper reference for the carbon emissions of NAS algorithms would be \"Carbon Emissions and Large Neural Network Training\" and \"Full-Cycle Energy Consumption Benchmark for Low-Carbon Computer Vision\", which particularly discussed the carbon emissions of NAS methods.\n- Some works have been officially accepted and then it is suggested to cite their official version instead of arxiv version, such as Dong et al 2020 NATS-Bench arxiv 2020 -> TPAMI 2021", "summary_of_the_paper": "This work explored how to use surrogate models to expand the existing (and limited) neural architecture search -- NAS -- benchmark. The new expanded benchmark is named as surrogate NAS benchmark. All codes are open-sourced, which demonstrated the good reproducibility of this work. The authors have conducted extensive experiments to demonstrate the usability of this new surrogate NAS benchmark and showed much analysis of existing NAS methods on this new benchmark.", "summary_of_the_review": "A good paper for the NAS community; hits a sweet spot for the current bottleneck of the reproducible NAS and the scientific research of NAS. I would strongly recommend accepting this work for ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a methodology to create cheap NAS surrogate benchmarks for arbitrary search spaces. Certainly, the work is interesting and useful, with comprehensive studies to validate such approach. It should be credited as belonging to the first efforts of introducing and comprehensively studying the concept of surrogate NAS benchmarks. In AC's opinion, it is a solid paper that will (or has already) inspire many follow up works. The paper is well written. 

This paper received highly mixed ratings. Although the authors might not see, all reviewers actually participated in the private discussions. Reviewer 1eb8 indicated hesitation in her/his support. Reviewer yTPb stated that if not considering the arXiv complicacy, she/he "would certainly raise score by one level".  AC also reached out to Reviewer yTPb about her/his mentioned possibility of updating scores, and got confirmed that her/his original opinions wasn't changing after rebuttals. Besides, AC agrees the arXiv/NeurIPS complicacy shouldn't brought into the current discussion, and ignored that factor during decision making. 

The main sticking (and considered-as-valid) critique is on the relatively outdated and incomplete selection of baselines. As a benchmark paper, it should capture and diversify the recent methods. For example, the authors might consider adding: https://botorch.org/docs/papers (latest methods in Bayesian Optimization) https://github.com/facebookresearch/LaMCTS (latest methods in Monte Carlo Tree Search) https://facebookresearch.github.io/nevergrad/ (latest methods in Evolutionary algorithms)

Given the above concerns, AC considers this paper to sit on the borderline, and perhaps with pros outweighing the cons. Hence, a weak accept decision is recommended at this moment.
Decision: Accept (Poster)