NAS-Bench-x11 and the Power of Learning Curves
Authors: Shen Yan
Colin White
Yash Savani
Frank Hutter
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural architecture search

Abstract: While early research in neural architecture search (NAS) required extreme computational resources, the recent releases of tabular and surrogate benchmarks have greatly increased the speed and reproducibility of NAS research. However, two of the most popular benchmarks do not provide the full training information for each architecture. As a result, on these benchmarks it is not possible to evaluate many types of multi-fidelity algorithms, such as learning curve extrapolation, that require evaluating architectures at arbitrary epochs. In this work, we present a method using singular value decomposition and noise modeling to create surrogate benchmarks, NAS-Bench-111, NAS-Bench-311, and NAS-Bench-NLP11, that output the full training information for each architecture, rather than just the final validation accuracy. We demonstrate the power of using the full training information by introducing a learning curve extrapolation framework to modify single-fidelity algorithms, showing that it leads to improvements over popular single-fidelity algorithms which claimed to be state-of-the-art upon release.

NAS-Bench-xII and the Power of Learning Curves
Shen Yan",, Colin White'?, Yash Savani", Frank Hutter Michigan State University, Abacus.AI, 3 Carnegie Mellon University, University of Freiburg, Bosch Center for Artificial Intelligence
Abstract
While early research in neural architecture search (NAS) required extreme compu- tational resources, the recent releases of tabular and surrogate benchmarks have greatly increased the speed and reproducibility of NAS research. However, two of the most popular benchmarks do not provide the full training information for each architecture. As a result, on these benchmarks it is not possible run many types of multi multi-fidelity techniques, such as learning curve extrapolation, that require evaluating architectures at arbitrary epochs. In this work, we present a method using singular value decomposition and noise modeling create surrogate bench- marks, MAS--ench-Ile 111, NAS- Bench-311, 1, and NAS-B Bench-NLPII I, that output the full training information for each architecture, rather than just the final validation accuracy. We demonstrate the power of using the full training information by introducing a learning curve extrapolation framework to modify single-fidelity algorithms, showing that it leads to improvements over popular single-fidelity algo- rithms which claimed to be state-of-the-art upon release. Our code and pretrained models are available at wtthttps:// /gthtb...........g com/ automm/nass mench-xx11
Introduction
In the past few years, algorithms for neural architecture search (NAS) have been used to automatically find architectures that achieve state-of-the-art performance various datasets [82] 53 38 13) In
2019, there were calls for reproducible and fair comparisons within NAS research 34 57 75 36
due to both the lack of a consistent training pipeline between papers and experiments with enough trials to reach statistically significant conclusions. These concerns spurred the release of tabular benchmarks, such as NAS-Bench-100 1011 (76] and NAS-Bench-201
created by fully training all architectures in search spaces of size 423 624 and 6 466, respectively. These benchmarks allow researchers easily simulate NAS experiments, making it possible run fair NAS comparisons and to run enough trials to reach statistical significance at very little computational cost or carbon emissions 17 Recently, to extend the benefits of tabular NAS benchmarks to larger, more realistic NAS search spaces which cannot be evaluated exhaustively, it was proposed to construct surrogate benchmarks [60] The first such surrogate benchmark
NAS-Bench-301 [60]. which models 38 search space of size 10 architectures. It was created by fully training 60 000
the DARTS
architectures (both drawn randomly and chosen by top NAS methods) and then fitting a surrogate model that can estimate the performance of all of the remaining architectures. Since 2019, dozens of papers have used these NAS benchmarks to develop new algorithms (67 55 73
64 59].
An unintended side-effect of the release of these benchmarks is that it became significantly easier to devise single fidelity NAS algorithms: when the NAS algorithm chooses evaluate an architecture, the architecture is fully trained and only the validation accuracy at the final epoch of training is outputted. This is because
301 only contains the architectures' accuracy epoch 100,
"Equal contribution. Correspondence to yanshen6@msu.. edu, col colinbabacus. ai. fhêcs, uni tmi-freshi frmi-freebuug.dee
ysavaniecsssss ysaaauuniiia.y..iieeee.e.. cmu, edu,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

NAS-Bench-111
NAS-Rench-111
NAS-Bench-211 arch
NAS-Bench-211 arch
1.0
1.0
0.9
0.8
Vordd acouscy
voll acodrs
0.7
0.6
0.6
0.5
0.8
Valt
0.4
Thue C
0.4
Trae IC
voldd
0.4
Prodicted moan LC
True LC
0.5
True LC
Prodicted mean LC
0.7
Prodicted LC
Predicted
0.7
Predited
Prodicted LC
0.3
Predicted LE
Predicted
Predicted LE
Predicted
90% region
90% region
50% region
90% region
0.0
0.0
25
50
75
100
Epochs
Epochs
Epochs
Epochs
NAS Bench 311 arch 1
NAS Bench 311 arch
NAS NLPch NLP11 arch
NAS Bench-NLeh1 arch
95.0
55.0
0.8
Wird acopte
54.9
2
94.0
0.7
0.7
54.8
04.8
Veld
0.6
True LC
Predicted mean
0.6
Predicted mean LC
True
04.5
True LC
Predicted mean
04.7
Prodicted mean LC
Predictod LC
Prodicted LC
Predicted LC
Predicted LC
0.4
Predicted 92% region
Predicted
94.5
Prodicted
01.5
Prodicted
0.3
0.4
region
94.4
90' region
01.4
90% region
25
75
100
50
100
20
Epocits
Epociss
Bsochs
Etochs
Figure 1: Each image shows the true learning curve vs. the learning curve predicted by our surrogate models, with and without predicted noise modeling. We also plot the 90% confidence interval of the predicted noise distribution. We plot two architectures each for I, and NAS-Bench-NLPII.
111, MAS-Bench-221,
and WAS-Bench-100 only contains the accuracies at epochs 4. 12, 36, and 108 (allowing single fidelity or very limited multi-iidelity approaches). MAS-Beech--201 does allow queries on the entire learning curve (every epoch). but it is smaller in size (6 466) than NAS-Bench-101 (423 624) or NAS-Bench-301 (1028).
real world experiment, since training architectures to convergence is computationally intensive, researchers will often run multi-fudelity algorithms: the NAS algorithm can train architectures to any desired epoch. Here, the algorithm can make use of speedup techniques such as learning curve extrapolation (LCE) [63] 8 [ 28 and successive halving [35 [4 [2] 29). Although multi-fidelin techniques are often used in the hyperparameter optimization community 20
21 35 14 63),
they have been under-utilized by the NAS community in the last few years.
In this work, we fill in this gap by releasing NLP11, surrogate benchmarks with full learning curve information for train, validation, and test loss and accuracy for all architectures, significantly extending
1 111, MAS-Bench-31 1, and NAS-Bench-
Be-eB-nnnhh- NAS-Bench-301 and IAS-Bench-NLP 30, respectively. With these benchmarks, researchers can easily incorporate multi- fidelity techniques, such as early stopping and LCE into their NAS algorithms. Our technique for creating these benchmarks can be summarized as follows. We use training dataset of architectures (drawn randomly and chosen by top NAS methods) with good coverage over the search space, along with full learning curves, to fit model that predicts the full learning curves of the remaining architectures. We employ three techniques to fit the model: (I) dimensionality reduction of the learning curves, (2) prediction of the top singular value coefficients, and (3) noise modeling. These techniques can be used in the future to create new NAS benchmarks as well. To ensure that our surrogate benchmarks are highly accurate, we report statistics such as Kendall Tau rank correlation and Kullback Leibler divergence between ground truth learning curves and predicted learning curves on separate test sets. See Figure for examples of predicted learning curves the test sets.
To demonstrate the power of using the full learning curve information, we present a framework for converting single-fidelit NAS algorithms into multi-fidelity algorithms using LCE. We apply our framework to popular single-fidelity NAS algorithms, such as regularized evolution [53], local search 168], and BANANAS [67] all of which claimed state-of-the-an art upon release, showing that they can be further improved across four search spaces. Finally, we also benchmark multi- fidlii- algorithms such Hyperband 35 and BOHB [4] alongside fidellty algorithms. Overall, our work bridges the gap between different areas of AutoML and will allow researchers to easily develop effective
and LCE techniques in the future. To promote reproducibility, we release our code and we follow the NAS best practices checklist [36], providing the details in Appendix A
Our contributions. We summarize our main contributions below.
2

---

Table Overview of existing NAS benchmarks. We introduce NAS- 1ithh-111,,,,,, 111, -311, and -NLP11
Benchmark
Size
Queryable
Based on
Full train info
NAS-Bench-
423k
NAS-Bench-201
6k
AAS-Bench-301
10
DARTS
AAS-Bench-NLP
1053
X
8k
NAS-Bench-
423k
V
NAS-Benche 101
NAS- JaS-Bench-311
10
DARTS NAS-Bench-NLP
NAS- 1AS-Bench-NLP11
1053
V
We develop a technique to create surrogate NAS benchmarks that include the full training information for each architecture, including train, validation, and loss and accuracy learning curves. This technique can be used to create future NAS benchmarks on any search space.
We apply technique to create NAS-Bench-1IL 111, MAS-Bench-311 and NAS-Bence Lench-NLP1L, which allow researchers to easily develop multi-fidelity NAS algorithms that achieve higher performance than fingle-fieeltty techniques.
We present a framework for converting fogllefidelity NAS algorithms into multi- multi-fidelity NAS algorithms using learning curve extrapolation, and we show that our framework allows popular state-of-the NAS algorithms to achieve further improvements.
Related Work
NAS has been studied since least the late 1980s 43
26 62 and has recently seen a resurgence 82
44 [2 22 533 18] Weight sharing algorithms have become popular due to their computational efficiency
77
51 78 Recent advances performance prediction 65
46
59
69 55 67 and other iterative techniques [14 45 have reduced the runtime gap between iterative
and weight sharing techniques. For detailed surveys on NAS, we suggest referring to B
Learning curve extrapolation. Several methods have been proposed to estimate the final validation accuracy of neural network by extrapolating the Icarning curve of a partially trained neural network. Techniques include fitting the partial curve to ensemble of various parametric functions (8), predicting the performance based on the derivatives the learning curves partially trained neural network configurations [1.. summing the training losses [54), using the basis functions as the output layer of a Bayesian neural network [28), using previous learning curves as basis function extrapolators [4), using the positive-definite covariance kernel capture variety of training curves [63], or using a Bayesian recurrent neural network [15]. While this work we focus on multi-fidelity optimization utilizing learning curve-based extrapolation, another main category of methods lie in bandit-basee algorithm selection [35] [4 29 [9 40 and the fidelities can be further adjusted according to the previous observations or learning rate scheduler 20 27).
NAS benchmarks. NAS-Bench-100 776, tabular NAS benchmark, was created by defining a search space size 423 624 unique architectures and then training all architectures from search space on C1FAR-10 until 108 epochs. However, the train, validation, and test accuracies are only reported for epochs 4, 12, 36, and 108, and the training, validation, and test losses are not reported. PAAS-Bench-shorf [80] defines subset of the NAS-Bench-LD 101 search space that allows [T contains 15 625 architectures, which 466
one-shot algorithms to be run. NAS-Bench- unique up to isomorpisms. It comes with full learning curve information three datasets: CIFAR-10 31, CIFAR-100 100 311. and ImageNet16 120 77. Recently, NAS-Benche Bench-201 was extended architecture size well as architecture topology.
to NATS-Bench [9] which searches
Virtually every published NAS method for image classification the last three years evaluates on the DARTS search space with 10FAR-10 [61] The DARTS search space (38) consists of 10 neural
architectures, making computationally prohibitive create tabular benchmark. To overcome this
fundamental limitation and query architectures in this much larger search space, NAS-Bench-301 [60

---

evaluates various regression models trained on sample of 60 000 architectures that is carefully created to cover the whole search space. The surrogate models allow users to query the validation accuracy (at epoch 100) and training time for any of the 1018 architectures in the DARTS search space. However, since the surrogates do not predict the entire learning curve, it is not possible to run multi-fidelity algorithms.
NAS-Bench-NLP [30] a search space for language modeling tasks, The search space consists of 100s architectures, of which 322 are evaluated on Penn Tree Bank [42), containing the training, validation, and test losses/accuracies from epochs 1 to 50. Since only 342 of 10ts architectures can be queried, this dataset cannot be directly used for NAS experiments.
WAS-Bench-ASR [41] recent tabular NAS benchmark for speech recognition. The search space consists of 2442 architectures with full learning curve information. For an overview of NAS benchmarks, see Table
3 Creating Surrogate Benchmarks with Learning Curves
In this section, we describe our technique to create surrogate model that outputs realistic learning curves, and then we apply this technique to create MAS-Bench-111 Bench-NLPI1. Our technique applies to any type of learning curve, including train/test losses and accuracies. For simplicity, the following presentation assumes validation accuracy learning curves.
and NAS-
3.1
General Technique
Given a search space D, let (z,; yi) D denote one datapoint, where 2; E Rd is the architecture encoding (e.g., one-hot adjacency matrix (76 66)), and E [0, 1 is learning curve of validation accuracies drawn from a distribution (ax;) based on training the architecture for Fmax epochs on fixed training pipeline with a random initial seed. Without loss of generality, each learning curve y, can be decomposed into two parts: one part that is deterministic and depends only on the architecture encoding, and another part that is based on the inherent noise in the architecture training pipeline. Formally, y/ = Y (æ:)] + Ej, where E|Y (æx)] E [0. 1] Ff is fixed and depends only on æ;, and E [0, 1] E comes from noise distribution Z; with expectation 0 for all epochs. In practice, E[Y(z) [z:)] can be estimated by averaging a large set of learning curves produced by training architecture æ; with different initial seeds. We represent such estimate as yt-
Our goal is to create a surrogate model that takes as input any architecture encoding 2; and outputs distribution of learning curves that mimics the ground truth distribution. We assume that we are given two datasets, Draiin and Diest, of architecture and learning curve pairs. We use Durain (often size 10 000) to train the surrogate, and we use Diest for evaluation. We describe the process of creating Derain and Diest for specific search spaces in the next section. In order to predict a learning curve distribution for each architecture, we split up our approach into two separate processes: we train model f: IR + [0, 1] to predict the deterministic part of the learning curve, D; and we train a noise model pp(c y, x), parameterized by o, to simulate the random draws from Z,.
Surrogate model training. Training a model ff to predict mean learning curves is a challenging task, since the training datapoints Dunin consist only of single (or few) noisy learning curve(s) y: for each xy. Furthermore, Emax is typically length 100 or larger, meaning that f must predict high-dimensional output. We propose a technique to help with both of these challenges: we use the training data to learn compression and decompression functions C₁ : [0, 1] 1 + [0, 1] and de : [0, 1| + [0, 1] Emas respectively, for h < Fmaa- The surrogate trained to predict compressed learning curves es (y:) of size l from the corresponding architecture encoding a;, and then each prediction can be reconstructed to a full learning curve using dy. A good compression model should not only cause the surrogate prediction to become significantly faster and simpler, but should also reduce the noise in the learning curves, since would only save the most important information in the compressed representations. That is, (dg o cx) (yr) should be less noisy version of y;: Therefore, models trained on C (y:) tend to have better generalization ability and do not overfit to the noise in individual learning curves.
We test two compression techniques: singular value decomposition (SVD) 16) and variational autoencoders (VAFs) 225) and we show later that SVD performs better. We give the details of SVD here and describe the VAE compression algorithm in Appendix C Formally, we take the singular value decomposition of matrix S of dimension ( [Draiin) Emax) created by stacking together the

---

Singular for
Reconstructed
Roconstruction enee
Singular values for
0.007
0.030
Recanstraccdd LC
0.6
Wike (mmpormente)
0.008
Reconutrucced
true (roray)
Valld accurary
0.6
10t
0.004
0.4
0.003
Ground truth Reconstructed LC, kei Reconstrarted LC, km4
0.002
0.2
0.031
Reconstracted km16
10
20
30
0.000
20
60
60 Epochs
80
100
Num, components K
Kum.
The singular values from the SVD decomposition of the learning curves (LC) (left). The MSE of a reconstructed LC, showing that is closest the true mean LC, while larger values of k overfit to the noise of the LC (middle). An LC reconstructed using different values of le (right).
Figure 2:
learning curves from all architectures in D Performing the truncated SVD on the learning curve matrix S allow us to create functions e and dg that correspond to the optimal linear compression of S. In Figure 2 (left), we that for architectures in the NAS-Bench-10) search space, there is a steep dropoff of importance after the first six singular values, which intuitively means that most of the information for each learning curve is contained in its first six singular values. In Figure 2 (middle), we compute the mean squared error (MSE) of the reconstructed learning curves (d4 o c&) (y:) compared a test of ground truth learning curves averaged over several initial seeds (approximating Ex()x;)), The lowest MSE is achieved at k = 6, which implies that k = 6 is the value where the compression function minimizes reconstruction error without overfitting to the noise of individual learning curves. We further validate this in Figure (right) by plotting (dg- o c&) (y:) for different values of k. Now that we have compression and decompression functions, we train surrogate model with as features and Cr (1x) as the label, for architectures in D We test. [ and MLPs for the surrogate model.
L.Booot
23 XGBoost
Noise modeling. The final step for creating realistic surrogate benchmark is to add noise model, so that the outputs are noisy learning curves. We first create new dataset of predicted e; values, which we call residuals, by subtracting the reconstructed mean learning curves from the real learning curves in Drain That is, é, = y: - (dg cx) (3/) is the residual for the ith learning curve. Since the training data only contains accurately estimate the distribution Z, for each architecture without making further assumptions. We assume that the noise comes from isotropic Gaussian distribution, and we consider two other noise assumptions: (/) the noise distribution is the same for all architectures (to create baselines, or for very homogeneous search spaces), and (2) for each architecture, the noise in small window of epochs iid. In Appendix[C] C, we estimate the extent to which all of these assumptions hold true. Assumption (I) suggests two potential (baseline) noise models: (i) a simple sample standard deviation statistic, R Buss where
(or few) learning curve(s) per architecture 2; it is not possible to
D Duaul
Dirain
To sample the noise using this model, we sample from (O, diag(o)). (ii) The second model is Gaussian kernel density estimation (GKDE) model (58) trained on the residuals to create multivariate Gaussian kernel density estimate for the noise. Assumption (2) suggests one potential noise model: (iii) model that is trained to estimate the distribution of the noise over window of epochs of a specific architecture. For each architecture and each epoch, the model is trained to estimate the sample standard deviation of the residuals within a window centered around that epoch.
Throughout this section, we described two compression methods (SVD and VAE), three surrogate models (LGB, XGB, and MLP), and three noise models (stddev, GKDE, and sliding window), for total of eighteen disctinct approaches. the next section, we describe the methods we will use to evaluate these approaches.
5

---

3.2 Surrogate Benchmark Evaluation
The performance of a surrogate benchmark depends on factors such as the size of the training set of architecture + learning curve pairs, the length of the learning curves, and the extent to which the distribution of learning curves satisfy the noise assumptions discussed in the previous section. It is important to thoroughly evaluate surrogate benchmarks before their use in NAS research, and so we present number of different methods for evaluation, which we will use to evaluate the surrogate benchmarks we create in the next section.
We evaluate both the predicted mean learning curves and the predicted noise distributions using held- out test sets Drstt To evaluate the mean learning curves, we compute the coefficient of determination (R2) 700 and Kendall Tau (KT) rank correlation 24 between the of predicted mean learning curves and the set of true learning curves, both at the final epoch and averaged over all epochs. To measure KT rank correlation for a specific epoch n, we find the number of concordant, P. and discordant, Q, pairs of predicted and true learning curve values for that epoch. The number of concordant pairs given by the number of pairs, ((is. Vi,n), (új.n; Uj.n)), where either both Vin > Ij.n and Vi.n > Vj.n. or both Ds.n < Új.n and Vj.n < Yi.n- We can then calculate KT = P-QQ While these metrics can be used to compare surrogate predictions and have been used in prior work 660, the rank correlation values are affected by the inherent noise in the learning curves even an oracle would have R² and KT values smaller than 1.0 because architecture training is noisy. In order give reference values, we also compute the KT of the set of true learning curves averaged over 2, 3, or 4 independent random seeds.
P-Q
The next metric to be used in Section is the Kullback Leibler (KL) divergence between the ground truth distribution of noisy learning curves, and the predicted distribution of noisy learning curves on test set. Since we can only estimate the ground truth distribution, we assume the ground truth is an isotropic Gaussian distribution. Then we measure the KL divergence between the true and predicted learning curves for architecture by the following formula:
DEL (yilli))
log
Egg Eggn
Fmnax
(Hys M.ge) )a S.g. (Mr. 11g.) tr Sog Eyy
}
2E
where (v..g.)) is diagonal matrix with the entries (g..)))) representing the sample variance of the k-th epoch, and ( is the sample mean for either learning curves (y:, 9.}-
The final metric is the probability of certain anomalies which we call spike anomalies. Even if the KL divergences between the surrogate benchmark distributions and the ground-truth distributions are low, anomalies in the learning curves still throw off NAS algorithms. For example, there may be anomalies that cause some learning curves to have a much higher maximum validation accuracy than their final validation accuracy. In order to test for these anomalies, first compute the largest value x such that there are fewer than 5% of learning curves whose maximum validation accuracy is higher than their final validation accuracy, percentage of surrogate learning curves whose maximum validation accuracy æ higher than their final validation accuracy. The goal is for this value to be close to 5%.
the real set of learning curves. Then, compute the
3.3 Creating NAS-Bench-11), 111, -211, -311, and -NLP11
Now we describe the creation of W'AS-Bench-11l NAS-Bench-3i1 and NAS-Bench-NL.P1. We also create
purely to evaluate our technique (since NAS-Bench-201 already has complete learning curves). Our code and pretrained models are available at //tttps://gthhii com/ automl/nas-bena
As described above, test two different compression methods (SVD, VAE), three different surrogate models (LGB, XGB, MLP), and three different noise models (stddev, GKDE, sliding window) for a total of eighteen distinct approaches. See Appendix C full ablation study and Table 2 for a summary using the best techniques for each search space. See Figure ] for a visualization of predicted learning curves from the test set of each search space using these models.
First, we describe the creation of NAS-Bench-Ile 111. Since the NAS-Bench- 101 tabular benchmark (76) consists only of accuracies at epochs 4, 12, 36, and 108 (and without losses), we train new set of architectures and save the full learning curves. Similar to prior work [12 60), we sample set of architectures with good overall coverage while also focusing the high nigh-performing regions exploited

---

Table Evaluation of the surrogate benchmarks on test sets. For NAS-Bench- 111 and NAS-Bench- NLP11, 1, we use architecture accuracies as additional features to improve performance.
Benchmark
Avg. I²²
Final I2
Avg. KT
Final KT
Avg. KL
Final KL
NAS-Bench. 111
0,529
0.630
0.531
0.645
2.016
1.061
MAS-Bench-1ae 111 (w. accs)
0.630
0.853
0,611
0.794
1.710
0,926
NAS Bench-311
0.779
0.800
0.728
0.788
0.905
0.600
NAS-Bench-NLP11
0.327
0.292
0.449
0.416
NAS-Bench-NIPPH (w. accs)
0,906
0.882
0.862
0.820
by NAS algorithms. Specifically, we sample 861 architectures generated uniformly at random, 149 architectures generated by 30 trials of BANANAS, local search, and regularized evolution, and all 91 architectures which contain fewer than five nodes, for total of 1 101 architectures. We kept our training pipeline as close as possible to the original pipeline. See Appendix C for the full training details. We find that SVD-LGB-window and WVD--GB-GKDD achieve the best performance. Since the tabular benchmark already exists, we can substantially improve the accuracy of our surrogate by using the accuracies from the tabular benchmark (at epochs 4, 12, 36, 108) as additional features along with the architecture encoding. This substantially improves the performance of the surrogate, as shown in Table The large difference between the average KT and last epoch KT values show that the learning curves are very noisy (which is also evidenced in Figure I On separate test set that contains two seeds evaluated per architecture, we show that the KT values for NAS-Bench-I 11 are roughly equivalent to those achieved by a 1-seed tabular benchmark (Appendix T
Next, we create NAS-Bench-311 by using the training data from NAS-Bench-301, which consists of 40 000 random architectures along with 26 000 additional architectures generated by evolution (63,, Bayesian optimization 3 67 47,, and one-shot (38 72 coverage over the search space. EVD-LGB-GKOD model performing well is consistent with prior work that notes DARTS is very homogeneous 77 NAS-Bench-31 achieves average and last epoch KT values of 0.728 and 0.788, respectively. This is comparable the last epoch KT of 0.817 reported by NAS-Bench-30 600 despite optimizing for the full learning curve rather than only the final epoch. Furthermore, our KL divergences in Table 2 surpasses the top value of 16.4 reported by Appendix Table 5] we show that the mean model in even than a set of learning curves averaged over four random seeds, by using a separate test set from the NAS- S-S--Bech-330 301 dataset which evaluates 500 architectures with 5 seeds each. We also show that the percentage of spike anomalies for real vs. surrogate data (defined the previous section) 5 5% and 7.02%, respectively.
10 6 techniques in order to achieve good achieves the best performance. The GKDE
(for KL divergence, lower is better). In achieves higher rank correlation
Finally, we create NAS-Bench-NLPII by using the HAS-Bench-NNL dataset consisting of 14 322 architectures drawn uniformly at random. Due to the extreme size of the search space (1083), we achieve an average and final epoch KT of 0.449 and 0.416. respectively. Since there are no architectures trained multiple times on the MAS-Bench-NLP dataset [30], we cannot compute the KL divergence or additional metrics. To create a stronger surrogate, we add the first three epochs of the learning curve as features in the surrogate. This improves the average and final epoch KT values to 0.862 and 0.820, respectively. To use this surrogate, any architecture to be predicted with the surrogate must be trained for three epochs. Note that the small difference between the average and last epoch KT values indicates that the learning curves have very little noise, which can also be seen in Figure T This technique can be used to improve the performance of other surrogates too, such as MASS-Benc--31 1. For MAS--Benc-3311 1,, we find that adding the validation accuracies from the first three epochs as additional epochs, improves the average and final epoch KT from 0.728 and 0.788 to 0.749 and 0.795, respectively.
We also create MAS-Bench- 1 to further evaluate our surrogate creation technique (only for evalua- tion purposes, since WASS-Bnnc--20 -01 already has complete learning curves). We train the surrogate on 90% of architectures from WVD-LGB-window achieves the best performance. The average and final KT values are 0.701 and 0.842, respectively, which is on par with a I 1-seed tabular benchmark (see Table We also show that the percentage of spike anomalies for real vs. surrogate data (defined the previous section) 5% and 10.14%, respectively.
(14 062 architectures) and test on the remaining 10%.
7

---

4 The Power of Learning Curve Extrapolation
Now we describe a simple framework for converting single-fidelity NAS algorithms to multi fyyllifi NAS algorithms using learning curve extrapolation techniques. We show that this framework is able to substantially improve the performance of popular algorithms such as regularized evolution [53).
BANANAS [67] and local search 668 48).
A single-fidelity algorithm is an algorithm which iteratively chooses an architecture based on its history, which is then fully trained to Emax epochs. To exploit parallel resources, many single- fidelity algorithms iteratively output several architectures at a time, instead of just one. In Algo- rithm 1 present pseudocode for generic single- fideeeiiiiitt algorithm. For example, for local search, gen_candidated would output the neighbors of the architecture with the best accuracy in history.
Our framework makes use of learning curve extrapolation (LCE) techniques g to predict the final validation accuracies of all architecture choices after only training for a small number of epochs. See Algorithm 2 After each iteration of gen_ sen__andiddee candidates, only the architectures predicted by LCE() to be the top percentage of validation accuracies of history are fully trained. For example, when the framework is applied to local search, in each iteration, all neighbors only the most promising architectures are trained up to Emax epochs. This simple modification can substantially improve the runtime efficiency of popular NAS algorithms by weeding out unpromising architectures before they are fully trained.
trained to Etew epochs, and
Any LCE technique can be used, and in our experiments in Section 5 we use weighted probabilistic modeling (WPM) 8 and learning curve support vector regressor (LeSVR) M. The first technique, WPM S is function that takes partial learning curve as input, and then extrapolates it by fitting the learning curve to a set of parametric functions, using MCMC to sample the most promising fit. The second technique, LcSVR M. is model-based learning curve extrapolation technique: after generating an initial set of training architectures, a support vector regressor is trained to predict the final validation accuracy from the architecture encoding and partial learning curve.
Algorithm 1 Single-Fidelity Algorithm
Algorithm LCE Framework
I: initialize history
1: initialize history
2: while < fmax
2: while fmax :
3: arches
camdeaadddatteaanee (anittrteeshisttrry) (history)
3: arches cen__aanidates (history))
4: acca = train (arches, epoch=Fmms)
4: accs = train(arches, etoch=Ei..)
5: history. update (arches, accs)
5: sorted_by-pred = LCE(arches, accs)
6: Return arch with the highest acc
6: arches borteed_y__pred[:too
7: accs train (arches, epoch=Eaxx
8: history. update (arches, accs)
9: Return arch with the highest acc
5
Experiments
In this section, we benchmark single-fidelity and multi-fidelity NAS algorithms, including popular ex- isting single-fidelity and multi-fidelity algorithms, as well algorithms created using our framework defined in the previous section. In the experiments, we use our three surrogate benchmarks defined in Section well NAS-Bench-201.
NAS algorithms. For single-fidelity algorithms, we implemented random search (RS) 3 local
search (LS) 68 48 regularized evolution (REA) (53) and BANANAS [67] For multi-fidelity
handit-based algorithms, we implemented Hyperband (HB) 35 and Bayesian optimization Hyper- band (BOHB) [4]. For all methods, we use the original implementation whenever possible. See Appendix D for deseription, implementation details, and hyperparameter details for each method. Finally, we use our framework from Section 4o create six new multi-fidelit algorithms: BANANAS, I.S, and REA are each augmented using WPM and LcSVR. This gives us a total of algorithms.
Experimental setup. For each search space, we run each algorithm for a total wall-clock time that is equivalent to running 500 iterations of the single-fidelity algorithms for NAS-Bench- 11l and
8

---

NAS-Bench-311, and 100 iterations for MAS--Bnch-200 and NAS- MAS--Bench-NLP11 For example, the average time to train a NAS- NAS-Bench-111 architecture to 108 epochs is roughly 10 seconds, so we set the maximum runtime on NAS-Bench-11 I to roughly 5 10 seconds. We run 30 trials of each NAS algorithm and compute the mean and standard deviation.
Results. We evaluate BANANAS, L.S, and REA compared to their augmented WPM and SVR versions in Figure 3 (NAS-Bench-311) and Appendix D (all other search spaces). Across four search spaces, we see that WPM and SVR improve all algorithms in almost all settings. The improvements are particularly strong for the larger TAS-Bench-111 and NAS-Bench-311 search spaces. We also see that for each single-fidelity algorithm, the LcSVR variant often outperforms the WPM variant. This suggests that model-based techniques for extrapolating learning curves are more reliable than extrapolating each learning curve individually, which has also been noted in prior work 66
In Figure 4 we compare single- and multi-fidellity algorithms on four search spaces, along with the three SVR-based al- gorithms from Figure 3] Across all search spaces, an SVR- based algorithm is the top-perforning algorithm. Specifically, BANANAS-SVR performs the best on MAS--ench-111.. NAS- Bench-311, 11, and the best on NAS JAS-Bench-201. Note that HB and BOHB may not perform well on search spaces with low correlation be- tween the relative rankings of architectures using low fidelities and high fidelities (such as NAS- Bes----B----------- 101 [76] and NAS-
NAS-Bench-313 CIFAR10
and LS-SVR performs
Valid. regret
10:22
BANANAS
BANANAS WRM
BANANAS-SUR
LS
LS-WPM
LS-SVR
Bench-201 [TT) since HB-based methods will predict the final accuracy of partially trained architectures directly from the last trained accuracy (i.e., extrapolating the learning curve as a constant after the last seen accuracy). On the other hand, SVR- based approaches use model that can learn more complex relationships between accuracy at early epoch vs. accuarcy at the final epoch, and are therefore more robust to this type of search space.
REA-WPM
REA-SVR
10a
10a
Runtime (seconds)
Figure 3: LCE Framework applied to single-fidelity algorithms on NAS- Bench-311.
In Appendix D we perform an ablation study on the epoch which the SVR and WPM methods start extrapolating in our framework (i.c.. we ablate Esow from Algorithm D. We find that for most search spaces, running SVR and WPM based NAS methods by starting the LCC at roughly 20% of the total number of epochs performs the best. Any earlier, and there is not enough information to accurately extrapolate the learning curve. Any later, and the LCE sees diminishing returns because less time is saved by early stopping the training.
6 Societal Impact
Our hope is that our work will make it quicker and casier for researchers to run fair experiments and give reprodueible conclusions. In particular, the surrogate benchmarks allow AutoML researchers to develop NAS algorithms directly on CPU, as opposed to using a GPU, which may decrease the carbon emissions from GPU-based NAS research [50] 17.. In terms of our proposed ÑAS speedups, these techniques are level of abstraction away from real applications, but they can indirectly impact the broader society. For example, this work may facilitate the creation of new high-performing NAS techniques, which can then be used to improve various deep learning methods, both beneficial (e.g. algorithms that reduce CO2 emissions), or harmful (e.g. algorithms that produce deep fakes).
7 Conclusions, Limitations, and Guidelines
In this work, we released three benchmarks for neural architecture search based on three popular search spaces, which substantially improve the capability of existing benchmarks due to the avail- ability of the full learning curve for train/validation/test loss and accuracy for each architecture. Our techniques to generate these benchmarks, which includes singular value decomposition of the learning curve and noise modeling, can be used to model the full learning curve for future surrogate NAS benchmarks as well.

---

Bench. CIFARLO
NAS Bench-311 311 CIFAR10
NAS-Bench-NLPI PTB
Valid. regret
regret
30
Perplexity
207
KHODOO Wine
101
10P
10P
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
NAS-Bench-201 CIFAR10
NAS-Bench-201 CIFAR100
NAS MAS-Bench-201 ImageNet16-122
10
Valid. regret
regret
Valid.
SCHOSCA
SCHOACA
Lon4
12a Runtime (seconds)
10
10'
20'
10'
307
Runtime (seconds)
Runtime (seconds)
Figure 4: NAS results on six different combinations of search spaces and datasets. For every setting, an SVR augmented method performs best.
Furthermore, we demonstrated the power of the full learning curve information by introducing a framework that converts single-fidelity NAS algorithms into multi-fidelity NAS algorithms that make use of learning curve extrapolation techniques. This framework improves the performance of recent popular single-fidelity algorithms which claimed to be tfte-of-theeard upon release.
While we believe our surrogate benchmarks will help advance scientific research in NAS, a few guidelines and limitations are important to keep in mind. As with prior surrogate benchmarks [60), we give the following two caveats. (1) We discourage evaluating NAS methods that use the same internal techniques those used in the surrogate model. For example, any NAS method that makes use of variational autoencoders or XGBoost should not be benchmarked using our VAE-XGB surrogate benchmark. (2) As the surrogate benchmarks are likely to evolve as new training data is added, or as better techniques for training a surrogate are devised, we recommend reporting the surrogate benchmark version number whenever running experiments.
(3) When creating new surrogate benchmarks, before use in NAS, it is important to give a thorough evaluation such as the evaluation methods described in Section 3.2
We also note the following strengths and limitations for specific benchmarks. Our surrogate benchmark gives strong mean performance even with just 101 architectures used as training data, due to the existence of the four extra validation accuracies from NAS-Bench- 101 that can be used additional features. We hope that all future tabular benchmarks will save the full learning curve information from the start so that the creation of an ffter-the-face extended benchmark is not necessary.
1 111
Although all of our surrogates had strong mean performance, the noise model was strongest only for DAS-Bench-311, 11,, which had training dataset of size 60k, as evidenced especially because of the rate of spike anomalics, described in Scction 3.2 This can be mitigated by adding more training data.
Since the the accuracy of the first three epochs are added as features, we recommend using this benchmark by training architectures for three epochs before querying the surrogate. Therefore, benchmarking 111 and NAS WMSS-Bench-311. but still offers a 15x speedup compared to a NAS experiment without this benchmark. We still release the version of NAS-Bench-NV a warning that the observed NAS trends may differ from the true NAS trends. We expect that the performance of these benchmarks will improve over time, as data for more trained architectures become available.
surrogate benchmark achieves significantly stronger performance when
NAS algorithms are slower than for
1 that does not use the first three accuracies as features but with
10

---

Acknowledgments and Disclosure of Funding
Work done while the first three authors were working at Abacus FH acknowledges support by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme through grant no. 716721, BMBF grant DeToL,, and TAILOR, project funded by EU Horizon 2020 research and innovation programme under GA No 952215. We thank Kaicheng Yu for his discussions with this project.
References
[1] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. In ICLR Workshop, 2018.
[2] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Under- standing and simplifying one-shot architecture search. In ICML, 2018.
[3] James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In NeurlPS, 2011.
[4] Akshay Chandrashekaran and Ian R Lane. Speeding up hyper-parameter optimization by extrapolation of learning curves using previous builds. In ECML-PKDD, 2017.
[5] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[6] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. Drnas: Dirichlet neural architecture search. In ICLR, 2021.
[7] Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. In arXiv: 08889, 2017.
[8] Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperpa- rameter optimization of deep neural networks by extrapolation of learning curves. In IJCAI, 2015.
[9] Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats-bench: Benchmarking nas algorithms for architecture topology and size. In PAMI, 2021.
[10] Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four gpu hours. In CVPR, 2019.
[11] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In ICLR, 2020.
[12) Katharina Eggensperger, Frank Hutter, Holger Hoos, and Kevin Leyton-Brown. Efficient benchmarking of hyperparameter optimizers surrogates. In AAAI, 2015.
[13] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. In JMLR, 2019.
[14] Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimization scale. In JCML, 2018.
[15] Matilde Gargiani, Aaron Klein, Stefan Falkner, and Frank Hutter. Probabilistic rollouts for learning curve extrapolation across hyperparameter settings. arXiv preprint arXiv: 19.004452, 2019.
[16] Gene Golub and William Kahan. Calculating the singular values and pseudo-inverse of matrix. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis, 2(2):205-224, 1965.
[17] Karen Hao. Training a single model can emit as much carbon as five cars in their lifetimes. MIT Technology Review, 2019.

---

[18] Hanzhang Hu, John Langford, Rich Caruana, Saurajit Mukherjee, Eric Horvitz, and Debadeepta Dey. Efficient forward architecture search. In NewrIPS, 2019.
[19] Yimin Huang, Yujun Li, Hanrong Ye, Zhenguo Li, and Zhihua Zhang. An asymptotically optimal multi-armed bandit algorithm and hyperparameter optimization. arXiv preprint arXiv:2007.05670, 2020.
[20] Kirthevasan Kandasamy, Gautam Dasarathy, Junier B. Oliva, Jeff Schneider, and Barnabas Poczos. Multi-fidelity gaussian process bandit optimisation. In NeurlPS, 2016.
[21] Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabas Poczos. Multi-fidelity bayesian optimisation with continuous approximations. In JMLR, 2017.
[22] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poezos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. In NewrIPS, 2018.
[23] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tin-Yan Liu. Lightghm: highly efficient gradient boosting decision tree. In NewrIPS, 2017.
[24] Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81 19, 1938.
[25] Diederik Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, 2014.
[26] Hiroaki Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex systems, 4(4):461-476, 1990.
[27] Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets. In AISTATS, 2017.
[28] Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction with bayesian neural networks. In ICLR, 2017.
[29] Aaron Klein, Louis Tiao, Thibaut Lienart, Cedric Archambeau, and Matthias Seeger. Model-based asynchronous hyperparameter and neural architecture search. arXiv preprint arXiv:2003.10865. 2020.
[30] Nikita Klyuchnikov, Ilya Trofimov, Ekaterina Artemova, Mikhail Salnikov, Maxim Fedorov, and Evgeny Burnaev. Nas-bench-nlp: neural architecture search benchmark for natural language processing. arXiv preprint arXiv:2006.07/ 16, 2020.
[31] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[32] Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparameter tuning. In MLSys Conference, 2020.
[33] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradi- ent algorithms for neural architecture search. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[34] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In UAI, 2019.
[35] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadch, and Ameet Talwalkar. Hyper- band: A novel bandit-based approach to hyperparameter optimization. In JMLR, 2018.
[36] Marius Lindauer and Frank Hutter. Best practices for scientific research on neural architecture search. In JMLR, 2020.
[37] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In ECCV, 2018
12

---

[38] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In ICLR, 2019.
[39] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie- Yan Liu. Semi-supervised neural architecture search. In NeurIPS, 2020.
[40] Neeratyoy Mallik and Noor Awad. Dehb: Evolutionary hyperband for scalable, robust and efficient hyperparameter optimization. In IJCAI, 2021.
[41] Abhinav Mehrotra, Alberto Gil P. Ramos, Sourav Bhattacharya, Łukasz Dudziak, Ravichan- der Vipperla, Thomas Chau, Mohamed S Abdelfattah,, Samin Ishtiaq, and Nicholas Donald Lane, Nas-bench-asr: Reproducible neural architecture search for speech recognition. In ICLR, 2021.
[42] Tomá's Mikolov, Martin Karafiát, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Recur- rent neural network based language model. In Annual conference of the international speech communication association, 2010.
[43] Geoffrey F Miller, Peter M Todd, and Shailesh Hegde. Designing neural networks using genetic algorithms. In ICGA, volume 89, pages 379-384, 1989.
[44] Renato Negrinho and Geoff Gordon. Deeparchitect: Automatically designing and training deep architectures. arXiv preprint arXiv:1704.08799 2017.
[45] Vu Nguyen, Sebastian Schulze, and Michael Osbore. Bayesian optimization for iterative learning. In NeurlPS, 2020.
[46] Xuefei Ning, Wenshuo Li, Zixuan Zhou, Tianchen Zhao, Yin Zheng, Shuang Liang, Huazhong Yang, and Yu Wang. A surgery of the neural architecture evaluators. arXiv preprint vrXiv:2008.03064 2020.
[47] Changyong Oh, Jakub M Tomczak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. arXiv preprint 1rXiv:1902.0000 2019.
[48] T Den Ottelander, Arkadiy Dushatskiy, Marco Virgolin, and Peter AN Bosman. Local search a remarkably strong baseline for neural architecture search. International Conference on Evolutionary Caltii-rrtteionn Optimization, 2021.
[49] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
[50] David Patterson, Joseph Gonzalez, Quoc Le, Chen Liang, Lluis-Miquel Munguia, Daniel Rothchild, David So, Maud Texier, and Jeff Dean. Carbon emissions and large neural network training. arXiv preprint arXiv:2104.1033 2021.
[51] Houwen Peng, Hao Du, Hongyuan Yu, Qi Li, Jing Liao, and Jianlong Fu. Cream of the crop: Distilling prioritized paths for one-shot neural architecture search. In NewriPS, 2020.
[52] Hieu Pham, Melody Y Guan, Barret Zoph, Quoe V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In ICML, 2018.
[53] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
[54] Binxin Ru, Clare Lyle, Lisa Schut, Mark van der Wilk, and Yarin Gal. Revisiting the train loss: an efficient performance estimator for neural architecture search. arXiv preprint a006v:2006.0 04492, 2020.
[55] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Neural architecture search using bayesian optimisation with leismeiler-lehman kernel. In ICLR, 2021.
13

---

[56] Michael Ruchte, Arber Zela, Julien Siems, Josif Grabocka, and Frank Hutter. Naslib: modular and flexible neural architecture search library, 2020.
[57] Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020.
[58] David W Scott. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
[59] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. In NeurIPS, 2020.
[60] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas-bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008..997 2020.
[61] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- bench-301 and the case for surrogate benchmarks for neural architecture search: Openreview response, 2021.
[62] Kenneth Stanley and Risto Mikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99-127, 2002.
[63] Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Freeze-thaw bayesian optimization. arXiv preprint arXiv: 1406.3896, 2014.
[64] Chen Wei, Chuang Niu, Yiping Tang, and Jimin Liang. Npenas: Neural predictor guided evolution for neural architecture search. arXiv preprint arXiv:2003. 12857, 2020.
[65] Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. ECCV, 2020.
[66] Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. In NeurlPS, 2020.
[67] Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In AAAI, 2021.
[68]
Colin White, Sam Nolen, and Yash Savani. Local search is state of the for nas benchmarks. In UAI, 2021.
[69] Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? arXiv preprint arXiv:2104.01 2021.
[70] Sewall Wright. Correlation and causation. Journal of Agricultural Research, 20:557-580, 1921.
[71] Lingxi Xie, Xin Chen, Kaifeng Bi, Longhui Wei, Yuhui Xu, Zhengsu Chen, Lanfei Wang, An Xiao, Jianlong Chang, Xiaopeng Zhang, et al. Weight-sharing neural architecture search: A battle to shrink the optimization gap. arXiv preprint 2008::00008.1455, 2020.
[72] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-efficient architecture search. In ICLR, 2019.
[73] Shen Yan, Kaiqiang Song, Fei Liu, and Mi Zhang. Cate: Computation-aware neural architecture encoding with transformers. In ICML, 2021.
[74] Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? In NeurlPS, 2020.
[75] Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. In ICLR, 2020.
[76] Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. 10s- Towards reproducible neural architecture search. In ICML, 2019.
14

---

[77] Shan You, Tao Huang, Mingmin Yang. Fei Wang, Chen Qian, and Changshui Zhang. Greedynas: Towards fast one-shot nas with greedy supernet. In CVPR, 2020.
[78] Kaicheng Yu, Rene Ranftl, and Mathieu Salzmann. Landmark regularization: Ranking guided super-net training in neural architecture search. In CVPR, 2021.
[79] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
[80] Arber Zela, Julien Siems, and Frank Hutter. Aas-bench-Ishotl. Benchmarking and dissecting one-shot neural architecture search. In ICLR, 2020.
[81] Yuge Zhang, Zejun Lin, Junyang Jiang, Quanlu Zhang, Yujing Wang. Hui Xue, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing in neural architecture search. arXiv preprint arXiv:2001.0143) 2020.
[82] Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017.
[83] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In CVPR, 2018.
15

---

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


Reviews:
[{"review_id": "hobGmWmv8G-", "reviewer": "Reviewer_S4sg", "summary": "Existing NAS benchmark datasets (e.g., NAS-Bench-101) do not provide full training information of architectures, which make it infeasible to evaluate the multi-fidelity algorithms (e.g., learning curve extrapolation). To address these issues, this paper create surrogate benchmark datasets, namely NAS-Bench-111, NAS-Bench-311 and NAS-Bench-NLP11, with singular value decomposition and noise modeling methods. Extensive experimental results with the full training information on these datasets show the superiority of the proposed method.", "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": "## Positive points:\n1. The paper presents a method to extend the existing single-fidelity benchmarks to multi-fidelity ones with full training information.\n2. The authors create NAS-Bench-111, NAS-Bench-311, and NAS-Bench-NLP11 benchmark datasets, which may be beneficial to develop new NAS algorithm.\n\n## Negative points:\n1. Does the proposed method apply to real world NAS application? In practice, given a dataset, we may have no available training information of any architectures. In this case, how to apply the proposed method? It would be limited if the proposed method is only able to extend the existing NAS benchmarks.\n2. In line 220, why do the authors sample architectures from BANANAS, local search and regularized evolution?\n3. In line 225, the authors mention that the method is able to improve the performance with the accuracies from the tabular benchmark (at epochs 4, 12, 36, 108) as additional features. More details of this should be provided.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Us800Q_124q", "reviewer": "Reviewer_xYsu", "summary": "This paper proposes another benchmark dataset for NAS, NAS-Bench-x11. Compared to the original benchmarks NAS-Bench-101, NAS-Bench-301 and NAS-Bench-NLP, NAS-Bench-x11 contains the full training\ninformation for each candidate architecture especially the learning curves so that it allows multi-fidelity NAS algorithms\n\nNAS-Bench-x11 is a surrogate benchmark, which trains a surrogate model to predict the learning curve of the vast amount of candidate architectures. Prediction of the learning curve can be accomplished by singular value decomposition and noise modeling. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThe paper is well motivated and clearly written. The paper is clear about limitations too.\n\nI think this paper will be valuable to the community.  The created NAS-bench-x11 contains the full training information of different architectures, which may make it more convenient to analyse NAS algorithms and promote further NAS algorithm design. The idea of predicting the learning curve is very interesting to me. \n\nThe authors conducted extensive experiments to demonstrate the effectiveness of the proposed method.  \n\nWeakness:\n\nThis paper is a completion of the previously created benchmarks. Providing learning curves is also considered before in NAS-Bench-201, which weakens the novelty of this paper. So I recommend a weak acceptence.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "BF1Ppe8n_Q6", "reviewer": "Reviewer_GXqH", "summary": "Existing NAS benchmarks often only include the architecture performance at the final or some selected checkpoint epochs. However, per-epoch information is essential for developing and evaluating multi-fidelity NAS algorithms. This work proposed to fit a surrogate model to predict the learning curve given an architecture encoding. Utilizing the proposed predictor, the author extends three existing benchmarks NASBench-101, NASBench-301, and NASBench-NLP to include per-epoch accuracies. Further, to demonstrate the necessity of developing multi-fidelity algorithms for NAS, the author also describes a procedure to extend the single-fidelity algorithms to multi-fidelity ones by using learning curve extrapolation to filter out candidate proposals with partial training. Despite possible room for improvements on the performance of the learning curve predictor used, the proposed method would enable researchers to develop and rapidly test multi-fidelity NAS algorithms. I vote for acceptance.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The contribution of this paper is relevant to the NAS community and would accelerate research on multi-fidelity NAS algorithms.\n2. The performance of the proposed learning curve predictor model is overall satisfactory.\n3. The author adopted the proposed method to extend three existing benchmarks to include per-epoch information.\n\nWeakness:\n1. The author reported ranking correlation and KL divergence between the predicted learning curve and ground truth. The numbers seem reasonable, but the errors are still non-negligible. It is unclear how misleading these errors would be if someone tries to develop multi-fidelity algorithms by querying the proposed extended benchmark. How would the existing multi-fidelity NAS algorithms perform under the proposed benchmark, over ground-truth data? This might be doable for NASBench201 or NASBench111 (the version created without using information about the given 4 checkpoint epochs), as they provide ground-truth accuracies on at least some checkpoints?\n\nComments and Questions:\n1. For NASBench-NLP, using the accuracy from the first few epochs as features significantly improves the learning curve predictor's performance. Can we also expect visible improvements on other spaces, if the info of the first few epochs is also provided?\n\n2. You mentioned in para 355 that future surrogate works should save full learning curve info to avoid the need for any extra extensions. But surrogate benchmarks like NASBench-301 only train a small portion of the architectures fully, and the large majority part of the search space will be benched by the predictor. So it seems that such surrogate benchmark would still need to be extended with learning curve prediction anyway. Could you elaborate more on this?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "0r08DKCXCen", "reviewer": "Reviewer_NYyv", "summary": "The authors describe a mechanism to predict learning curves which they use to generate surrogate benchmarks from existing NAS-Bench versions without learning curves. The authors explore different ways to create learning curve embeddings, different ways to predict these embeddings using the architecture representation as an input and different ways to model the training noise. Furthermore, the authors discuss a short study on using learning curve extrapolation in context of speeding-up NAS.", "questions": "", "limitations": "", "rating": 5, "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": "The authors provide a good description of their method, alternative ways to solve each problem faced and support their decisions with empirical evidence.\n\nMy main concern is about the usefulness of this surrogate benchmark which has problems as partly discussed by the authors. It remains unclear what impact these problems would have.\n\nThe noise modelling in this paper leads to artifacts we would not see in real learning curves. First, it is very unlikely that the noise is architecture- and hyperparameter-independent. Second, given just the very few examples in Figure 1 we observe that the predicted learning curve in early epochs can already exceed to highest value of the entire learning curve (possibly due to very high noise levels).\nIn general, all surrogate benchmarks have the problem that they introduce some sort of bias which will not match what you would see in reality. Therefore, these datasets are more similar to synthetic datasets than real ones. They might be nice to prototype but I wouldn’t use them to evaluate NAS methods.\n\nThe experiment on combining learning curve extrapolation is a nice reminder for the NAS community to keep these approaches in mind when comparing different approaches. However, it provides no novelty since these methods have been used in the context of NAS already (see [1]).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper adds learning curve information to popular NAS benchmarks via a surrogate model. This is valuable to the community since it opens up current NAS benchmarks to multi-fidelity search approaches. Furthermore it demonstrates a compeling 'template' that can be used for creating new NAS benchmarks on new search spaces where it is not feasible to create tabular benchmarks due to the sheer size of the search space. 

During the review process a number of improvements have come about with the reviewers, especially when engaging with NYyv with respect to top architecture predictions. It is strongly recommended that the authors include this new information in the paper. In this vein, the paper should clearly mark the limitations of this benchmark and how NAS researchers should consume this benchmark and interpret the outcomes of their search algorithms.

This benchmark is going to be widely used by the community. So the quality of the software release and ease-of-usage is quite critical. Please pay a lot of attention to making sure that the package can be installed and run easily via standard Python package distribution channels like pip/conda and the associated data/surrogate models can be installed in one-click and there are plenty of examples to showcase how to use the benchmark. 

Decision: Accept (Poster)